TY - GEN
T1 - Cutting-edge cryptography through the lens of secret sharing
AU - Komargodski, Ilan
AU - Zhandry, Mark
N1 - Publisher Copyright:
© International Association for Cryptologic Research 2016.
PY - 2016
Y1 - 2016
N2 - Secret sharing is a mechanism by which a trusted dealer holding a secret “splits” the secret into many “shares” and distributes the shares to a collection of parties. Associated with the sharing is a monotone access structure, that specifies which parties are “qualified” and which are not: any qualified subset of parties can (efficiently) reconstruct the secret, but no unqualified subset can learn anything about the secret. In the most general form of secret sharing, the access structure can be any monotone NP language. In this work, we consider two very natural extensions of secret sharing. In the first, which we call distributed secret sharing, there is no trusted dealer at all, and instead the role of the dealer is distributed amongst the parties themselves. Distributed secret sharing can be thought of as combining the features of multiparty non-interactive key exchange and standard secret sharing, and may be useful in settings where the secret is so sensitive that no one individual dealer can be trusted with the secret. Our second notion is called functional secret sharing, which incorporates some of the features of functional encryption into secret sharing by providing more fine-grained access to the secret. Qualified subsets of parties do not learn the secret, but instead learn some function applied to the secret, with each set of parties potentially learning a different function. Our main result is that both of the extensions above are equivalent to several recent cutting-edge primitives. In particular, general-purpose distributed secret sharing is equivalent to witness PRFs, and generalpurpose functional secret sharing is equivalent to indistinguishability obfuscation. Thus, our work shows that it is possible to view some of the recent developments in cryptography through a secret sharing lens, yielding new insights about both these cutting-edge primitives and secret sharing.
AB - Secret sharing is a mechanism by which a trusted dealer holding a secret “splits” the secret into many “shares” and distributes the shares to a collection of parties. Associated with the sharing is a monotone access structure, that specifies which parties are “qualified” and which are not: any qualified subset of parties can (efficiently) reconstruct the secret, but no unqualified subset can learn anything about the secret. In the most general form of secret sharing, the access structure can be any monotone NP language. In this work, we consider two very natural extensions of secret sharing. In the first, which we call distributed secret sharing, there is no trusted dealer at all, and instead the role of the dealer is distributed amongst the parties themselves. Distributed secret sharing can be thought of as combining the features of multiparty non-interactive key exchange and standard secret sharing, and may be useful in settings where the secret is so sensitive that no one individual dealer can be trusted with the secret. Our second notion is called functional secret sharing, which incorporates some of the features of functional encryption into secret sharing by providing more fine-grained access to the secret. Qualified subsets of parties do not learn the secret, but instead learn some function applied to the secret, with each set of parties potentially learning a different function. Our main result is that both of the extensions above are equivalent to several recent cutting-edge primitives. In particular, general-purpose distributed secret sharing is equivalent to witness PRFs, and generalpurpose functional secret sharing is equivalent to indistinguishability obfuscation. Thus, our work shows that it is possible to view some of the recent developments in cryptography through a secret sharing lens, yielding new insights about both these cutting-edge primitives and secret sharing.
UR - http://www.scopus.com/inward/record.url?scp=84954157021&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84954157021&partnerID=8YFLogxK
U2 - 10.1007/978-3-662-49099-0_17
DO - 10.1007/978-3-662-49099-0_17
M3 - Conference contribution
AN - SCOPUS:84954157021
SN - 9783662490983
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 449
EP - 479
BT - Theory of Cryptography - 3th International Conference, TCC 2016-A, Proceedings
A2 - Kushilevitz, Eyal
A2 - Malkin, Tal
PB - Springer Verlag
T2 - 13th International Conference on Theory of Cryptography, TCC 2016
Y2 - 10 January 2016 through 13 January 2016
ER -