Cutting-edge cryptography through the lens of secret sharing.

*(English)*Zbl 1429.94061Summary: 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 it can be thought of as combining the features of multiparty non-interactive key exchange and standard secret sharing. Qualified sets can agree on a key which remains pseudorandom for unqualified sets. 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 general-purpose 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.

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 it can be thought of as combining the features of multiparty non-interactive key exchange and standard secret sharing. Qualified sets can agree on a key which remains pseudorandom for unqualified sets. 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 general-purpose 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.

PDF
BibTeX
XML
Cite

\textit{I. Komargodski} and \textit{M. Zhandry}, Inf. Comput. 263, 75--96 (2018; Zbl 1429.94061)

Full Text:
DOI

##### References:

[1] | Komargodski, I.; Zhandry, M., Cutting-edge cryptography through the lens of secret sharing, (Theory of Cryptography - 13th International Conference, TCC 2016-A, (2016)), 449-479 · Zbl 1382.94131 |

[2] | Shamir, A., How to share a secret, Commun. ACM, 22, 11, 612-613, (1979) · Zbl 0414.94021 |

[3] | Blakley, G. R., Safeguarding cryptographic keys, (Proceedings of AFIPS National Computer Conference, vol. 48, (1979)), 313-317 |

[4] | (2018), Wikipedia, Two-man rule |

[5] | Beimel, A., Secret-sharing schemes: a survey, (3rd International Workshop on Coding and Cryptology, IWCC, (2011)), 11-46 · Zbl 1272.94074 |

[6] | Benaloh, J. C.; Leichter, J., Generalized secret sharing and monotone functions, (8th Annual International Cryptology Conference, CRYPTO, (1988)), 27-35 |

[7] | Karchmer, M.; Wigderson, A., On span programs, (8th Annual Structure in Complexity Theory Conference, (1993)), 102-111 |

[8] | Naor, M., Secret sharing for access structures beyond P, slides, (2006) |

[9] | Komargodski, I.; Naor, M.; Yogev, E., Secret-sharing for NP, J. Cryptol., 30, 2, 444-469, (2017) · Zbl 1377.94057 |

[10] | Garg, S.; Gentry, C.; Sahai, A.; Waters, B., Witness encryption and its applications, (Symposium on Theory of Computing Conference, STOC, (2013)), 467-476 · Zbl 1293.94066 |

[11] | Zhandry, M., How to avoid obfuscation using witness prfs, (Theory of Cryptography - 13th International Conference, TCC 2016-A, Lect. Notes Comput. Sci., vol. 9563, (2016), Springer), 421-448 · Zbl 1382.94170 |

[12] | Boneh, D.; Waters, B., Constrained pseudorandom functions and their applications, (Advances in Cryptology - ASIACRYPT ’13, (2013)), 280-300 · Zbl 1314.94057 |

[13] | Sahai, A.; Waters, B., Slides on functional encryption, (2008), Available at |

[14] | Boneh, D.; Sahai, A.; Waters, B., Functional encryption: definitions and challenges, (8th Theory of Cryptography Conference, (2011)), 253-273 · Zbl 1295.94027 |

[15] | Barak, B.; Goldreich, O.; Impagliazzo, R.; Rudich, S.; Sahai, A.; Vadhan, S. P.; Yang, K., On the (im)possibility of obfuscating programs, J. ACM, 59, 2, 6, (2012), preliminary version appeared in CRYPTO 2001 · Zbl 1281.68118 |

[16] | Garg, S.; Gentry, C.; Halevi, S.; Raykova, M.; Sahai, A.; Waters, B., Candidate indistinguishability obfuscation and functional encryption for all circuits, (54th Annual IEEE Symposium on Foundations of Computer Science, FOCS, (2013)), 40-49 |

[17] | Sahai, A.; Waters, B., How to use indistinguishability obfuscation: deniable encryption, and more, (Symposium on Theory of Computing, STOC, (2014)), 475-484 · Zbl 1315.94102 |

[18] | Boneh, D.; Zhandry, M., Multiparty key exchange, efficient traitor tracing, and more from indistinguishability obfuscation, (34th Annual Cryptology Conference, CRYPTO, (2014)), 480-499 · Zbl 1310.94130 |

[19] | Brakerski, Z.; Rothblum, G. N., Virtual black-box obfuscation for all circuits via generic graded encoding, (11th Theory of Cryptography Conference, TCC, (2014)), 1-25 · Zbl 1310.94134 |

[20] | Barak, B.; Garg, S.; Kalai, Y. T.; Paneth, O.; Sahai, A., Protecting obfuscation against algebraic attacks, (Advances in Cryptology - EUROCRYPT, (2014)), 221-238 · Zbl 1332.94055 |

[21] | Pass, R.; Seth, K.; Telang, S., Indistinguishability obfuscation from semantically-secure multilinear encodings, (34th Annual Cryptology Conference, CRYPTO, (2014)), 500-517 · Zbl 1343.94076 |

[22] | Gentry, C.; Lewko, A. B.; Sahai, A.; Waters, B., Indistinguishability obfuscation from the multilinear subgroup elimination assumption, (IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS, (2015), IEEE Computer Society), 151-170 |

[23] | Applebaum, B.; Brakerski, Z., Obfuscating circuits via composite-order graded encoding, (12th Theory of Cryptography Conference, TCC, (2015)), 528-556 · Zbl 1382.94049 |

[24] | Zimmerman, J., How to obfuscate programs directly, (Advances in Cryptology - EUROCRYPT 2015, vol. 9057, (2015)), 439-467 · Zbl 1371.68054 |

[25] | Gentry, C.; Gorbunov, S.; Halevi, S., Graph-induced multilinear maps from lattices, (TCC 2015, vol. 9015, (2015)), 498-527 · Zbl 1315.94076 |

[26] | Desmedt, Y.; Frankel, Y., Threshold cryptosystems, (Advances in Cryptology - CRYPTO, (1989)), 307-315 |

[27] | Santis, A. D.; Desmedt, Y.; Frankel, Y.; Yung, M., How to share a function securely, (26th Annual ACM Symposium on Theory of Computing, STOC, (1994)), 522-533 · Zbl 1345.94094 |

[28] | Beimel, A.; Burmester, M.; Desmedt, Y.; Kushilevitz, E., Computing functions of a shared secret, SIAM J. Discrete Math., 13, 3, 324-345, (2000) · Zbl 0949.68114 |

[29] | Boyle, E.; Gilboa, N.; Ishai, Y., Function secret sharing, (Advances in Cryptology - EUROCRYPT, (2015)), 337-367 · Zbl 1371.94664 |

[30] | Garg, S.; Gentry, C.; Halevi, S., Candidate multilinear maps from ideal lattices, (Advances in Cryptology - EUROCRYPT, (2013)), 1-17 · Zbl 1300.94055 |

[31] | Komargodski, I.; Moran, T.; Naor, M.; Pass, R.; Rosen, A.; Yogev, E., One-way functions and (im)perfect obfuscation, (55th Annual IEEE Symposium on Foundations of Computer Science, FOCS, (2014)), 374-383 |

[32] | Boyle, E.; Goldwasser, S.; Ivan, I., Functional signatures and pseudorandom functions, (Proceedings of the 17th International Conference on Practice and Theory in Public-Key Cryptography, (2014)), 501-519 · Zbl 1290.94145 |

[33] | Kiayias, A.; Papadopoulos, S.; Triandopoulos, N.; Zacharias, T., Delegatable pseudorandom functions and applications, (Proceedings of the 20th Annual ACM Conference on Computer and Communications Security, (2013)), 669-684 |

[34] | Goldwasser, S.; Gordon, S. D.; Goyal, V.; Jain, A.; Katz, J.; Liu, F.; Sahai, A.; Shi, E.; Zhou, H., Multi-input functional encryption, (Advances in Cryptology - EUROCRYPT, (2014)), 578-602 · Zbl 1327.94048 |

[35] | Grigni, M.; Sipser, M., Monotone complexity, (Proceedings of LMS Workshop on Boolean Function Complexity, (1992)), 57-75 · Zbl 0766.68040 |

[36] | Jafargholi, Z.; Kamath, C.; Klein, K.; Komargodski, I.; Pietrzak, K.; Wichs, D., Be adaptive, avoid overcommitting, (Advances in Cryptology - CRYPTO 2017, Lect. Notes Comput. Sci., vol. 10401, (2017), Springer), 133-163 · Zbl 1407.94123 |

[37] | Cramer, R.; Damgård, I.; Nielsen, J. B., Secure Multiparty Computation and Secret Sharing, (2015), Cambridge University Press · Zbl 1322.68003 |

[38] | Naor, M., Bit commitment using pseudorandomness, J. Cryptol., 4, 2, 151-158, (1991) · Zbl 0731.68033 |

[39] | Håstad, J.; Impagliazzo, R.; Levin, L. A.; Luby, M., A pseudorandom generator from any one-way function, SIAM J. Comput., 28, 4, 1364-1396, (1999) · Zbl 0940.68048 |

[40] | D. Boneh, A. Silverberg, Applications of multilinear forms to cryptography, IACR Cryptology ePrint Archive, 2002, 80. |

[41] | Coron, J.; Lepoint, T.; Tibouchi, M., New multilinear maps over the integers, (Advances in Cryptology - CRYPTO, (2015)), 267-286 · Zbl 1375.94116 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.