Search

A collection of sets displays a proximity gap with respect to some property if for every set in the collection, either (i) all members are δ-close to the property in relative Hamming distance or (ii) only a tiny fraction of members are δ-close to the property. In particular, no set in the collection has roughly half of its members δ-close to the property and the others δ-far from it. We show that the collection of affine spaces displays a proximity gap with respect to Reed--Solomon (RS) codes, even over small fields, of size polynomial in the dimension of the code, and the gap applies to any δ smaller than the Johnson/Guruswami--Sudan list-decoding bound of the RS code.We also show near-optimal gap results, over fields of (at least) linear size in the RS code dimension, for δ smaller than the unique decoding radius. Concretely, if δ is smaller than half the minimal distance of an RS code V ⊂ Fnq, then every affine space is either entirely δ-close to the code or, alternatively, at most an (n/q)-fraction of it is δ-close to the code. Finally, we discuss several applications of our proximity gap results to distributed storage, multi-party cryptographic protocols, and concretely efficient proof systems. We prove the proximity gap results by analyzing the execution of classical algebraic decoding algorithms for Reed--Solomon codes (due to Berlekamp--Welch and Guruswami--Sudan) on a formal element of an affine space. This involves working with Reed--Solomon codes whose base field is an (infinite) rational function field. Our proofs are obtained by developing an extension (to function fields) of a strategy of Arora and Sudan for analyzing low-degree tests. [ABSTRACT FROM AUTHOR]

To address the limitations of the Raft consensus algorithm, such as the lack of support for Byzantine fault tolerance, performance bottleneck of the leader single node, and high leader election delay, an improved Byzantine fault tolerance consensus algorithm called RaBFT based on Raft is proposed. The distribution process of log messages is optimized by utilizing the secret sharing technique to make it Byzantine fault tolerance, and the role of the committee is introduced to share the communication pressure of the leader, thereby resolving the performance bottleneck issue of the leader single node. The leader election algorithm based on a dynamic committee improves the speed of leader election and reduces the time required for leader election. The experimental results show that RaBFT algorithm has a significant improvement in throughput and consensus delay in the log replication phase, and has a lower leader election delay, RaBFT algorithm can improve the efficiency and performance of the system, it is a safe and efficient consensus algorithm. [ABSTRACT FROM AUTHOR]

Ciphertext-policy attribute-based encryption (CP-ABE) is widely employed for secure data sharing and access control. However, its dependence on a single authority introduces security and performance challenges. Despite the existence of multi-authority CPABE approaches, persistent issues such as single points of failure and high computation cost on the user side remain. This study proposes a novel solution named blockchain-based and decentralized attribute-based encryption (BDAE) for data sharing. BDAE enhances traditional scheme by integrating blockchain and distributed key generation technology. The scheme employs an (n, t) threshold secret sharing algorithm, coupled with the Pedersen verifiable secret sharing method, for attribute key generation. This combination ensures key credibility, facilitates joint attribute management, and addresses single bottleneck and key verification issues. Integrated into a blockchain system, the scheme utilizes smart contracts for fine-grained access control and outsourced computing. Blockchain's decentralization and access logs make data sharing tamper-resistant and auditable. Moreover, simulation comparisons demonstrate that the scheme effectively reduces decryption overhead on the user side, meeting practical application requirements. [ABSTRACT FROM AUTHOR]

We propose a verifiable (t,n)-threshold secret sharing scheme using Lagrange interpolation and secure cryptographic hash functions. This scheme is an improvement of Shao’s scheme [Inform. Sci. 278 (2014) 104–109]. In our variant, verification of shares is achieved through computation of their multiplicative inverses in conjunction with a secure hash function such as SHA-3. This idea results in a significant size reduction, in comparison with Shao’s scheme, to the shares assigned to each participant. Applications of the proposed scheme include sharing of cryptographic keys, access codes, etc. Furthermore, we improve our construction to present a method for secret sharing with adjustable access structure. This can further be extended to a secret sharing scheme with essential participants, where any authorized set of participants must meet a threshold in the number of essential participants it contains. While our proposal has smaller share sizes compared to Shao’s scheme, it also adds the capabilities of changeable parameters and essential participants. [ABSTRACT FROM AUTHOR]

The interplanetary File system (IPFS) provides data communication using plaintext over distributed and decentralized systems. Up till now, the security of data has mostly been established using keys. To facilitate classified data communication within a Closed User Group (CUG), services of IPFS private swarm are required to render additional content encryption. Currently, there is no inherent security built into IPFS. This paper presents an application DMaya on IPFS to provide keyless encryption on IPFS based on the Quasigroup-based Secret Sharing Scheme (QSS). IPFS is used as a storage medium, irrespective of the nature of data. Data security in decentralized mode with IPFS is provided with DMaya. The classified data of all types (i.e. video data, audio data, text data, and image data) when subjected to DMaya application, are fragmented into smaller fragments then processed by the probabilistic Quasigroup-based Secret Sharing (QSS) Scheme. DMaya keyless encryption generates the metadata tag file at the source node. The recipient node within the same private IPFS swarm, on receipt of metadata tag file reconstructs the original data with DMaya application. [ABSTRACT FROM AUTHOR]

In this paper, we design unconditionally secure multi-party computation (MPC) protocols in the asynchronous communication setting with optimal resilience. Our protocols are secure against a computationally unbounded malicious adversary characterized by an adversary structure Z , which enumerates all possible subsets of potentially corrupt parties. We present protocols with both perfect-security, as well as with statistical-security. While the protocols in the former class achieve all the security properties in an error-free fashion, the protocols belonging to the latter category achieve all the security properties except with a negligible error. Our perfectly secure protocol incurs an amortized communication of O (| Z | 2) bits per multiplication. This improves upon the protocol of Choudhury and Pappu (INDOCRYPT 2020) with the least known amortized communication complexity of O (| Z | 3) bits per multiplication. On the other hand, our statistically secure protocol incurs an amortized communication of O (| Z |) bits per multiplication. This is the first statistically secure asynchronous MPC protocol against general adversaries. Previously, perfectly secure and statistically secure MPC with an amortized communication cost of O (| Z | 2) and O (| Z |) bits, respectively, per multiplication was known only in the relatively simpler synchronous communication setting (Hirt and Tschudi in ASIACRYPT, Springer, 2013). [ABSTRACT FROM AUTHOR]

In a verifiable secret sharing (VSS) scheme, each participant can check cheating by the dealer or the other participants. In this work, we construct a VSS scheme with the strongest level of computational security and prove its security in the standard model. This scheme is secure against active attack and does not use bilinear pairing and hash function. [ABSTRACT FROM AUTHOR]

Secure multi-party computation (MPC) is a fundamental problem in secure distributed computing. An MPC protocol allows a set of n mutually distrusting parties with private inputs to securely compute any publicly known function of their inputs, by keeping their respective inputs as private as possible. While several works in the past have addressed the problem of designing communication-efficient MPC protocols in the synchronous communication setting, not much attention has been paid to the design of efficient MPC protocols in the asynchronous communication setting. In this work, we focus on the design of efficient asynchronous MPC (AMPC) protocol with statistical security, tolerating a computationally unbounded adversary, capable of corrupting up to t parties out of the n parties. The seminal work of Ben-Or, Kelmer and Rabin (PODC 1994) and later Abraham, Dolev and Stern (PODC 2020) showed that the optimal resilience for statistically secure AMPC is t < n / 3 . Unfortunately, the communication complexity of the protocol presented by Ben-Or et al. is significantly high, where the communication complexity per multiplication is Ω (n 13 κ 2 log n) bits (where κ is the statistical-security parameter). To the best of our knowledge, no work has addressed the problem of improving the communication complexity of the protocol of Ben-Or et al. In this work, our main contributions are the following. We present a new statistically secure AMPC protocol with the optimal resilience t < n / 3 , where the communication complexity is O (n 4 κ) bits per multiplication. Apart from improving upon the communication complexity of the protocol of Ben-Or et al., our protocol is relatively simpler and based on very few sub-protocols, unlike the protocol of Ben-Or et al. which involves several layers of sub-protocols. A central component of our AMPC protocol is a new and simple protocol for verifiable asynchronous complete secret-sharing (ACSS), which is of independent interest. As a side result, we give the security proof for our AMPC protocol in the standard universal composability (UC) framework of Canetti (FOCS 2001, JACM 2020), which is now the de facto standard for proving the security of cryptographic protocols. This is unlike the protocol of Ben-Or et al., which was missing the formal security proofs. [ABSTRACT FROM AUTHOR]

Abstract Today, cloud storage services increased the popular for data storage in the cloud and retrieve from any location without any time limitations. One of the most important demands required in cloud is secured data transmission in un-trusted cloud applications. Particularly, secure and efficient multiparty communications in Untrusted Cloud Environments (UCE) attract widespread attentions. The equipment used in UCE have the particularity of being heterogeneous and UCE communication environment are asynchronous networks in which multiple users cannot transmit their messages simultaneously. How to ensure secure communication between these heterogeneous intelligent devices is a major challenge for multiparty communication applied in UCE. In such an asynchronous environment, the asynchronous transmission can cause security problems in cryptographic functions. Therefore, how to implement rational secret sharing (RSS) in an asynchronous model of the UCE networks has become a burning research topic. The RSS refers to finding a solution composed of strategies to encourage players in the secret reconstruction to act honestly even players are rational to act for their own interest. If each player plays the game for the best response to the best response of other players, the game is in Nash equilibrium. The objective of an RSS is to achieve the Nash equilibrium state corresponding to the global optima. In this paper, we propose an information-theoretic secure RSS in asynchronous model for UCE. Our design uses Petersen’s VSS to allow every player to divide his share into multiple pieces for other players. Then, shares can be revealed asynchronously. If any player acts maliciously, his share can be recovered by other players. This feature can encourage players to act honestly since any malicious action (i.e., either revealing a fake share or refusing to release one) is useless. Our scheme is practically valuable for secure group-oriented applications in UCE.

Today, cloud storage services increased the popular for data storage in the cloud and retrieve from any location without any time limitations. One of the most important demands required in cloud is secured data transmission in un-trusted cloud applications. Particularly, secure and efficient multiparty communications in Untrusted Cloud Environments (UCE) attract widespread attentions. The equipment used in UCE have the particularity of being heterogeneous and UCE communication environment are asynchronous networks in which multiple users cannot transmit their messages simultaneously. How to ensure secure communication between these heterogeneous intelligent devices is a major challenge for multiparty communication applied in UCE. In such an asynchronous environment, the asynchronous transmission can cause security problems in cryptographic functions. Therefore, how to implement rational secret sharing (RSS) in an asynchronous model of the UCE networks has become a burning research topic. The RSS refers to finding a solution composed of strategies to encourage players in the secret reconstruction to act honestly even players are rational to act for their own interest. If each player plays the game for the best response to the best response of other players, the game is in Nash equilibrium. The objective of an RSS is to achieve the Nash equilibrium state corresponding to the global optima. In this paper, we propose an information-theoretic secure RSS in asynchronous model for UCE. Our design uses Petersen's VSS to allow every player to divide his share into multiple pieces for other players. Then, shares can be revealed asynchronously. If any player acts maliciously, his share can be recovered by other players. This feature can encourage players to act honestly since any malicious action (i.e., either revealing a fake share or refusing to release one) is useless. Our scheme is practically valuable for secure group-oriented applications in UCE. [ABSTRACT FROM AUTHOR]

Secure computation enables n mutually distrustful parties to compute a function over their private inputs jointly. In 1988, Ben-Or, Goldwasser, and Wigderson (BGW) proved that any function can be computed with perfect security in the presence of a malicious adversary corrupting at most t < n / 3 parties. After more than 30 years, protocols with perfect malicious security, and round complexity proportional to the circuit’s depth, still require (verifiably) sharing a total of O (n 2) values per multiplication. In contrast, only O(n) values need to be shared per multiplication to achieve semi-honest security. Sharing Ω (n) values for a single multiplication seems to be the natural barrier for polynomial secret-sharing-based multiplication. In this paper, we construct a new secure computation protocol with perfect, optimal resilience and malicious security that incurs (verifiably) sharing O(n) values per multiplication. Our protocol requires a constant number of rounds per multiplication. Like BGW, it has an overall round complexity that is proportional only to the multiplicative depth of the circuit. Our improvement is obtained by a novel construction for weak VSS for polynomials of degree 2t, which incurs the same communication and round complexities as the state-of-the-art constructions for VSS for polynomials of degree t. Our second contribution is a method for reducing the communication complexity for any depth 1 sub-circuit to be proportional only to the size of the input and output (rather than the size of the circuit). This implies protocols with sub-linear communication complexity (in the size of the circuit) for perfectly secure computation for important functions like matrix multiplication. [ABSTRACT FROM AUTHOR]

In $(k, n)$ threshold secret sharing, a secret is converted into $n$ shares such that any threshold $k$ or more shares allow for the reconstruction of this secret; however, the total storage cost increases. By contrast, asymmetric secret sharing reduces the total shares to be stored. When implementing secret sharing in the cloud, if malicious players submit forged shares during the reconstruction process, the reconstructed value will differ from the original secret. Therefore, a method that quickly verifies the integrity of the restored secret should be developed. Many research papers investigate cheater detection/identification for $(k, n)$ threshold secret sharing. However, most of them require additional information, such as an authenticator. Harn et al. proposed a method for cheat detection using only the shares for $(k, n)$ threshold secret sharing. In this study, we improved and extended the method proposed by Harn et al. to realize the detection and identification of shares forgery (cheating) in asymmetric secret sharing suitable for a cloud system. The proposed method uses the shares generated during asymmetric secret sharing to reconstruct and verify the secret. We also included an attack that assumes a cloud system and shows that most methods cannot work against it. Finally, we discussed the requirements for a secret sharing scheme suitable for the cloud and showed that the proposed method is ideal for use in a cloud environment.

A non-interactive publicly verifiable multi secret sharing (PVMSS) scheme is a secret sharing scheme that the dealer shares multiple secrets among the participants and anyone can verify the validity of the shares by using the public information. For the first time, we propose a new PVMSS scheme based on the homogeneous linear recursions (HLR) and discrete logarithms equality (DLEQ) protocol. Compared with the previous PVMSS schemes, it has better performance and various methods for the recovery phase. Moreover, we prove its security with a formal method. [ABSTRACT FROM AUTHOR]

Incorporation of fog computing with low latency, preprocession (e.g., data aggregation) and location awareness, can facilitate fine-grained collection of smart metering data in smart grid and promotes the sustainability and efficiency of the grid. Recently, much attention has been paid to the research on smart grid, especially in protecting privacy and data aggregation. However, most previous works do not focus on privacy-preserving data aggregation and function computation query on enormous data simultaneously in smart grid based on fog computation. In this paper, we construct a novel verifiable privacy-preserving data collection scheme supporting multi-party computation(MPC), named VPDC-MPC, to achieve both functions simultaneously in smart grid based on fog computing. VPDC-MPC realizes verifiable secret sharing of users’ data and data aggregation without revealing individual reports via practical cryptosystem and verifiable secret sharing scheme. Besides, we propose an efficient algorithm for batch verification of share consistency and detection of error reports if the external adversaries modify the SMs’ report. Furthermore, VPDC-MPC allows both the control center and users with limited resources to obtain arbitrary arithmetic analysis (not only data aggregation) via secure multi-party computation between cloud servers in smart grid. Besides, VPDC-MPC tolerates fault of cloud servers and resists collusion. We also present security analysis and performance evaluation of our scheme, which indicates that even with tradeoff on computation and communication overhead, VPDC-MPC is practical with above features. [ABSTRACT FROM AUTHOR]

Secret sharing schemes are being widely used to distribute a secret between various participants so that an authorized subset of participants belonging to appropriate access structures can reconstruct this secret. However, a dealer might get corrupted by adversaries and may influence this secret sharing or the reconstruction process. Verifiable secret sharing (VSS) overcomes this issue by adding a verifiability protocol to the original secret sharing scheme. This article proposes a computationally secure publicly verifiable secret sharing scheme based on the three‐dimensional cellular automata (3D‐CA). Unlike the more widely used linear secret sharing schemes or secret sharing scheme based on the Chinese remainder theorem, our proposed scheme performs the secret sharing using 3D‐CA. The secret is considered one of the initial configurations of the 3D‐CA, and the following configurations are devised to be the shares distributed among the participants. Update mechanisms and various rules make it hard for an adversary to corrupt or duplicate a share. To make it even more efficient, we have added a verifiability layer such that a dealer posts a public share and private share to each shareholder. The verifiability layer reduces the interaction between dealer and participants and hence increases the security. The randomness of the shares has been calculated using the National Institute of Standards and Technology statistical test suite. [ABSTRACT FROM AUTHOR]

Collaborative recommending systems aim to predict a potential user‐item rating on the basis of remaining ones. Since, in several contexts, sharing of other users' ratings may be prevented by confidentiality concerns, several works have effectively addressed the design of privacy preserving recommenders. Still, most of the proposed solutions rely on advanced cryptographic methodologies, whose may conflict with the simplicity and viability requirements of real world deployments. In contrast, we propose an approach which does not require any complex cryptography. We show that whenever we can tolerate recommendations based on average values, we can transform the recommender into a privacy‐preserving one, by using two noncolluding replicas of the same system, and by distributing randomly "blinded" data to these replicas. To protecting each user's rating, a key asset of our approach is the ability to conceal which specific items are rated by which users. Our proposal is secure under the honest‐but‐curious attacker's assumption, and we show how it can be extended to guarantee robustness also against malicious adversaries. Finally, as a proof‐of‐concept, we present an implementation of the proposed approach for our motivating use case—collaborative assessment of computer/network vulnerabilities without revealing which of them affect one own infrastructure. [ABSTRACT FROM AUTHOR]

The emergence of ubiquitous computing and different disruptive technologies caused magnificent development in information and communication technology. Likewise, cybercriminals are also carefully considering different newer ways of attacks. Protecting the confidentiality, integrity, and authentication of sensitive information is the day's major challenge. Secret sharing is a method that allows a trusted authority (the dealer) to distribute a secret or a number of secrets among some target participants with the intention that certain predetermined groups of participants can collaborate to recover the secret or secrets. Any other group formed by the participants cannot do so. Threshold secret sharing (TSS) is a particular form of secret sharing. It permits any group consisting of at least a specific number (called the threshold) of participants to reconstruct the secret or secrets. However, any group with fewer than the specified number of participants is forbidden to do so. It provides tolerance against single point of failure (SPOF), which has attracted a large number of researchers to contribute in this field. It has the potential to be implemented in numerous practical and secure applications. In this paper, we present a comprehensive survey of a variety of existing threshold secret sharing schemes. We have identified various aspects of developing secure and efficient secret sharing schemes. We have also highlighted some of the applications based on secret sharing. Finally, the open challenges and future research directions in the field of secret sharing are identified and discussed. [ABSTRACT FROM AUTHOR]

A verifiable (t, n) threshold quantum secret sharing scheme with sequential communication was proposed recently. In this work, we analyze its security and then give two new participant attacks. Using the first participant attack, the first participant can obtain the dealer's secrets by himself with nonzero probability without being detected. Using the second participant attack, a dishonest participant can gain access to the dealer's secrets by himself in the secret reconstruction phase while he can make the other participants recover false secrets instead of the real ones without being detected. Furthermore, we present an effective way to prevent these attacks.

A publicly verifiable secret sharing (PVSS) scheme enjoys the public verification and the lower cost of communication than VSS scheme. However, the existing PVSS schemes cannot be applied in the scenarios of the devices with low computation ability and do not share the multiple secrets among all participants efficiently. In this paper, an efficient publicly verifiable multi-secret sharing scheme with outsourcing secret reconstruction is proposed. Each participant only spends a small amount of computational cost to recover multiple secrets because of the expensive burden of computation and verifiability is outsourced to the cloud service provider (CSP). Moreover, the CSP knows no information of the secrets, and the participants have the abilities to verify the returned result. We also prove that our scheme is secure under the hardness assumption of the discrete logarithm problem and the modified generalized bilinear inversion problem.

In this paper, we focus on the research of non-interactive secure multi-party computation. At first, we propose a fully homomorphic non-interactive verifiable secret sharing (FHNVSS) scheme. In this scheme, shareholders can generate shares of any-degree polynomials of shared numbers without interaction, and the dealer can verify the correctness of shares sent by shareholders without interaction. We implemented the FHNVSS scheme in Python with a detailed performance evaluation. According to our tests, the performance of FHNVSS is satisfactory. For instance, when the request is a 10-degree polynomial of secret value, generating a response takes about 0.0017263 s; verifying a response takes about 0.1221394 s; recovering a result takes about 0.0003862 s. Besides, we make an extension on the FHNVSS scheme to obtain a fully non-interactive secure multi-party computation, called AntNest. In the AntNest scheme, distrustful parties can jointly calculate a any-degree negotiated function, the inputs of which are inputs of all parties, without interaction, and each party can verify the correctness of responses sent by parties without interaction. To the best of our knowledge, it is the first work to realize that parties can jointly calculate any-degree function, the inputs of which are inputs of all parties, without interaction.

A non-interactive (t; n)-publicly verifiable secret sharing scheme (non-interactive (t; n)-PVSS scheme) is a (t; n)-secret sharing scheme in which anyone, not only the participants of the scheme, can verify the correctness of the produced shares without interacting with the dealer and participants. The (t; n)-PVSS schemes have found a lot of applications in cryptography because they are suitable for real-life scenarios in which an external verifier is required to check the correctness of the produced shares without interacting with the dealer and participants. In this paper, we propose a non-interactive (t; n)-PVSS scheme using the non-homogeneous linear recursions (NHLRs), and prove its security with a formal method. We compare the computational complexity of our scheme with that of Schoenmakers's scheme and show that our non-interactive (t; n)-PVSS scheme runs faster than Schoenmakers's scheme when n = 5 and n t d 2n+9 n e. The communicational complexity of our scheme is almost equal to that of Schoenmakers's scheme. [ABSTRACT FROM AUTHOR]

Vehicular ad hoc networks (VANET) is seen as an effective solution to ensure the driving safety and efficiency. As a key foundation, the road side unit (RSU) connect with each other to form a backbone network in VANET. The authentication of RSUs is the main tasks to prevent the secure communication in VANET suffering from various attacks caused by cunning adversaries. In this paper, we propose a new type of verifiable secret sharing (VSS) scheme based on bivariate polynomial to achieving the RSU authentication in a secret sharing way. Our proposed VSS based authentication includes two phases. In phase 1, the t RSUs that participate in secret reconstruction collaborate to detect whether there exist illegitimate ones; in phase 2, the t legitimate RSUs reveal their shares for secret reconstruction, and the fake shares can be identified. Our VSS facilitates the RSU authentication since (1) any RSUs participate in secret reconstruction can be confirmed legitimate, (2) any fake shares revealed in secret reconstruction can be identified, (3) a globalized group temporary session key will be established after the VSS process. In addition, our VSS scheme is unconditional secure since the security of our VSS is not based on any computational assumption. [ABSTRACT FROM AUTHOR]