Multiparty computation secure against continual memory leakage
56
Citation
60
Reference
10
Related Paper
Citation Trend
Abstract:
We construct a multiparty computation (MPC) protocol that is secure even if a malicious adversary, in addition to corrupting 1-ε fraction of all parties for an arbitrarily small constant ε >0, can leak information about the secret state of each honest party. This leakage can be continuous for an unbounded number of executions of the MPC protocol, computing different functions on the same or different set of inputs. We assume a (necessary) "leak-free" preprocessing stage. We emphasize that we achieve leakage resilience without weakening the security guarantee of classical MPC. Namely, an adversary who is given leakage on honest parties' states, is guaranteed to learn nothing beyond the input and output values of corrupted parties. This is in contrast with previous works on leakage in the multi-party protocol setting, which weaken the security notion, and only guarantee that a protocol which leaks l bits about the parties' secret states, yields at most l bits of leakage on the parties' private inputs. For some functions, such as voting, such leakage can be detrimental.Keywords:
Security parameter
Leakage (economics)
Information leakage
Memory leak
In a data-driven society, individuals and companies encounter numerous situations where private information is an important resource. How can parties handle confidential data if they do not trust everyone involved? This text is the first to present a comprehensive treatment of unconditionally secure techniques for multiparty computation (MPC) and secret sharing. In a secure MPC, each party possesses some private data, while secret sharing provides a way for one party to spread information on a secret such that all parties together hold full information, yet no single party has all the information. The authors present basic feasibility results from the last 30 years, generalizations to arbitrary access structures using linear secret sharing, some recent techniques for efficiency improvements, and a general treatment of the theory of secret sharing, focusing on asymptotic results with interesting applications related to MPC.
Access structure
Data Sharing
Private information retrieval
Shared resource
Cite
Citations (482)
Secret sharing refers to method for distributing a secret among a group of participants. It is also known as secret splitting. In this, each of the participants is allocated a share of the secret. The individual share doesn't carry any information. The secret can be reconstructed only when a sufficient number or all of shares are combined together. Secret-sharing schemes are important tools in cryptography and they are used as building blocks in many secure protocols, e.g., general protocol for multiparty computation, Byzantine agreement, threshold cryptography, access control, attribute-based encryption, and generalized oblivious transfer. Visual secret sharing, aka Visual Cryptography, provides a very powerful technique by which visual secret can be distributed into two or more shares. When the shares are combined together, the original visual secret can be discovered. In this paper, as first part, many types of secret sharing schemes are examined. Secondly we proposed two variant of a secret sharing scheme using Gray code and XOR operation. The Gray code is used to construct the shares and the XOR operation is used to reconstruct the secret. The proposed method can be used as a cryptographic algorithm and also for secret sharing as well as visual secret sharing.
Shamir's Secret Sharing
Shared secret
Visual cryptography
Access structure
AKA
Code (set theory)
Bitwise operation
Cite
Citations (16)
FUNCTION AND SECRET SHARING EXTENSIONS FOR BLAKLEY AND ASMUTH-BLOOM SECRET SHARING SCHEMES Ilker Nadi Bozkurt M.S. in Computer Engineering Supervisor: Assist. Prof. Dr. Ali Aydin Selcuk August, 2009 Threshold cryptography deals with situations where the authority to initiate or perform cryptographic operations is distributed amongst a group of individuals. Usually in these situations a secret sharing scheme is used to distribute shares of a highly sensitive secret, such as the private key of a bank, to the involved individuals so that only when a sufficient number of them can reconstruct the secret but smaller coalitions cannot. The secret sharing problem was introduced independently by Blakley and Shamir in 1979. They proposed two different solutions. Both secret sharing schemes (SSS) are examples of linear secret sharing. Many extensions and solutions based on these secret sharing schemes have appeared in the literature, most of them using Shamir SSS. In this thesis, we apply these ideas to Blakley secret sharing scheme. Many of the standard operations of single-user cryptography have counterparts in threshold cryptography. Function sharing deals with the problem of distribution of the computation of a function (such as decryption or signature) among several parties. The necessary values for the computation are distributed to the participants using a secret sharing scheme. Several function sharing schemes have been proposed in the literature with most of them using Shamir secret sharing as the underlying SSS. In this work, we investigate how function sharing can be achieved using linear secret sharing schemes in general and give solutions of threshold RSA signature, threshold Paillier decryption and threshold DSS signature operations. The threshold RSA scheme we propose is a generalization of Shoup’s Shamir-based scheme. It is similarly robust and provably secure under the static adversary model. In threshold cryptography the authorization of groups of people are decided
Shared secret
Shamir's Secret Sharing
Access structure
Cite
Citations (1)
In 1979, secret sharing scheme was first proposed by Shamir. In a secret sharing scheme, each participant receives a secret share in such a way that only authorized subsets can reconstruct the secret. Compare with Shamir's scheme, Juan and Huang proposed an efficient secret sharing scheme from room square in 2005. Their scheme gave a practical algorithm to reduce the computation complexity by using room square, and obtained as (n - 1, n)-threshold secret sharing scheme. However, there is not any (t, n)-threshold secret sharing scheme for t les n - 2 with more efficient than Shamir's scheme has been proposed. For this reason, this paper utilizes the characteristic of cycle to design four (t, n)-threshold secret sharing schemes for t = n - 2. These proposed schemes are not only more efficient than previous related works in the computational complexity, but also with the information rate is approximated optimal value 1. In addition, we combine the proposed scheme and the property of room square to present a new multi-secret sharing scheme in this paper.
Shamir's Secret Sharing
Square (algebra)
Access structure
Cite
Citations (2)
In general, the (k,n)-threshold secret sharing scheme cannot be used to perform an information-theoretically secure secret computation for n<2k-1. Therefore, our research team has been focusing on conditions under which secret computation can be performed securely for n<2k-1, and proposed a secret computation method that is safe against malicious adversaries. However, this method is inefficient because it performs all operations as secret computations. In this paper, we divide the arithmetic operations into precomputations and secret computations and show that we can achieve faster secret computation than the conventional method by concentrating the operations that require communication in precomputation.
Precomputation
Secure two-party computation
Shamir's Secret Sharing
Cite
Citations (0)
A secret sharing scheme is a system designed to share a piece of information or the secret among a group of people such that only authorized people can reconstruct the secret from their shares. Since Blakley and Shamir proposed threshold secret sharing schemes in 1979 independently, many secret sharing schemes have been constructed. In this paper, we present several threshold schemes that are generalizations of Shamir's secret sharing scheme.
Shamir's Secret Sharing
Shared secret
Access structure
Cite
Citations (27)
Shamir's Secret Sharing
Shared secret
Cite
Citations (365)
It is a central problem in secret sharing to understand the access structures of secret sharing schemes. In Chen and Kramer, secret sharing schemes from algebraic-geometric codes and their applications in secure multiparty computation were proposed and studied. For any given finite field , these secret sharing schemes are ideal ramp secret sharing schemes and allow arbitrarily many players. In this correspondence, we give the access structures explicitly for the elliptic secret sharing schemes from algebraic-geometric (AG) codes associated with elliptic curves. Based on higher degree rational points on elliptic curves, we also construct some nonideal secret sharing schemes with weighted threshold structures.
Shamir's Secret Sharing
Access structure
Shared secret
Cite
Citations (10)
Secret sharing schemes are very important techniques for the key management in cryptography and for the distributed computation. In 1979, Shamir [6] proposed a threshold secret sharing scheme in which one secret is divided into w pieces (shares) and are delivered to w users such that only groups of t or more users (t < w) could cooperately reconstruct the secret. In this paper, by extending the method of Shamir, we present a scheme for sharing simultaneously several secrets which is more effective in using memory space and computation time w.r.t the consecutive application of several times the Shamir’s original scheme for each secret to be shared.
Shamir's Secret Sharing
Shared secret
Access structure
Cite
Citations (0)
Shamir's Secret Sharing
Cite
Citations (154)