Protecting Distributed Primitives Against Leakage: Equivocal Secret Sharing and More
Document Open Access Logo

Protecting Distributed Primitives Against Leakage: Equivocal Secret Sharing and More

Authors Carmit Hazay, Muthuramakrishnan Venkitasubramaniam, Mor Weiss

PDF
Thumbnail PDF

File

LIPIcs.ITC.2022.3.pdf
  • Filesize: 0.77 MB
  • 24 pages

Document Identifiers

Author Details

Carmit Hazay
  • Bar-Ilan University, Ramat-Gan, Israel
  • carmit.hazay@biu.ac.il
Muthuramakrishnan Venkitasubramaniam
  • Georgetown University, Washington, DC, USA
  • mv783@georgetown.edu
Mor Weiss
  • Bar-Ilan University, Ramat-Gan, Israel
  • mor.weiss@biu.ac.il

Funding

  • Hazay, Carmit: Supported by the BIU Center for Research in Applied Cryptography and Cyber Security in conjunction with the Israel National Cyber Bureau in the Prime Minister’s Office, and by ISF grant No. 1316/18.
  • Weiss, Mor: Supported by the BIU Center for Research in Applied Cryptography and Cyber Security in conjunction with the Israel National Cyber Bureau in the Prime Minister’s Office.

Acknowledgements

We thank the anonymous ITC`22 reviewers for helpful comments.

Cite As Get BibTex

Carmit Hazay, Muthuramakrishnan Venkitasubramaniam, and Mor Weiss. Protecting Distributed Primitives Against Leakage: Equivocal Secret Sharing and More. In 3rd Conference on Information-Theoretic Cryptography (ITC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 230, pp. 3:1-3:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.ITC.2022.3

Abstract

Leakage-resilient cryptography aims to protect cryptographic primitives from so-called "side channel attacks" that exploit their physical implementation to learn their input or secret state. Starting from the works of Ishai, Sahai and Wagner (CRYPTO`03) and Micali and Reyzin (TCC`04), most works on leakage-resilient cryptography either focus on protecting general computations, such as circuits or multiparty computation protocols, or on specific non-interactive primitives such as storage, encryption and signatures. This work focuses on leakage-resilience for the middle ground, namely for distributed and interactive cryptographic primitives.
Our main technical contribution is designing the first secret-sharing scheme that is equivocal, resists adaptive probing of a constant fraction of bits from each share, while incurring only a constant blowup in share size. Equivocation is a strong leakage-resilience guarantee, recently introduced by Hazay et al. (ITC`21). Our construction is obtained via a general compiler which we introduce, that transforms any secret-sharing scheme into an equivocal scheme against adaptive leakage. An attractive feature of our compiler is that it respects additive reconstruction, namely, if the original scheme has additive reconstruction, then the transformed scheme has linear reconstruction.
We extend our compiler to a general paradigm for protecting distributed primitives against leakage, and show its applicability to various primitives, including secret sharing, verifiable secret sharing, function secret sharing, distributed encryption and signatures, and distributed zero-knowledge proofs. For each of these primitives, our paradigm transforms any construction of the primitive into a scheme that resists adaptive party corruptions, as well as adaptive probing leakage of a constant fraction of bits in each share when the share is stored in memory (but not when it is used in computations). Moreover, the transformation incurs only a constant blowup in the share size, and respects additive reconstruction - an important feature for several of these primitives, such as function secret sharing and distributed encryption.

Subject Classification

ACM Subject Classification
  • Theory of computation → Cryptographic primitives
  • Theory of computation → Cryptographic protocols
Keywords
  • Leakage Resilience
  • Secret Sharing
  • Equivocal Secret Sharing
  • Verifiable Secret Sharing
  • Function Secret Sharing
  • Threshold Encryption
  • Distributed Zero-Knowledge Proofs

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Divesh Aggarwal, Ivan Damgård, Jesper Buus Nielsen, Maciej Obremski, Erick Purwanto, João L. Ribeiro, and Mark Simkin. Stronger leakage-resilient and non-malleable secret sharing schemes for general access structures. In CRYPTO, pages 510-539, 2019. Google Scholar
  2. Adi Akavia, Shafi Goldwasser, and Vinod Vaikuntanathan. Simultaneous hardcore bits and cryptography against memory attacks. In TCC, Proceedings, pages 474-495, 2009. Google Scholar
  3. Marcin Andrychowicz, Stefan Dziembowski, and Sebastian Faust. Circuit compilers with o(1/log (n)) leakage rate. In EUROCRYPT, Proceedings, Part II, pages 586-615, 2016. Google Scholar
  4. Saikrishna Badrinarayanan and Akshayaram Srinivasan. Revisiting non-malleable secret sharing. In EUROCRYPT, pages 593-622, 2019. Google Scholar
  5. Marshall Ball, Dana Dachman-Soled, Siyao Guo, Tal Malkin, and Li-Yang Tan. Non-malleable codes for small-depth circuits. In FOCS, pages 826-837, 2018. Google Scholar
  6. Marshall Ball, Dana Dachman-Soled, Mukul Kulkarni, and Tal Malkin. Non-malleable codes for bounded depth, bounded fan-in circuits. In EUROCRYPT, pages 881-908, 2016. Google Scholar
  7. Donald Beaver. Efficient multiparty protocols using circuit randomization. In Joan Feigenbaum, editor, CRYPTO, volume 576, pages 420-432. Springer, 1991. Google Scholar
  8. Fabrice Benhamouda, Akshay Degwekar, Yuval Ishai, and Tal Rabin. On the local leakage resilience of linear secret sharing schemes. In CRYPTO, Proceedings, pages 531-561, 2018. Google Scholar
  9. Nir Bitansky, Ran Canetti, Shafi Goldwasser, Shai Halevi, Yael Tauman Kalai, and Guy N. Rothblum. Program obfuscation with leaky hardware. In ASIACRYPT, Proceedings, pages 722-739, 2011. Google Scholar
  10. Nir Bitansky, Ran Canetti, and Shai Halevi. Leakage-tolerant interactive protocols. In TCC, Proceedings, pages 266-284, 2012. Google Scholar
  11. Nir Bitansky, Dana Dachman-Soled, and Huijia Lin. Leakage-tolerant computation with input-independent preprocessing. In CRYPTO, Proceedings, Part II, pages 146-163, 2014. Google Scholar
  12. Andrej Bogdanov, Yuval Ishai, Emanuele Viola, and Christopher Williamson. Bounded indistinguishability and the complexity of recovering secrets. In CRYPTO, pages 593-618, 2016. Google Scholar
  13. Dan Boneh, Elette Boyle, Henry Corrigan-Gibbs, Niv Gilboa, and Yuval Ishai. How to prove a secret: Zero-knowledge proofs on distributed data via fully linear PCPs. IACR Cryptol. ePrint Arch., 2019:188, 2019. URL: https://eprint.iacr.org/2019/188.
  14. Dan Boneh, Elette Boyle, Henry Corrigan-Gibbs, Niv Gilboa, and Yuval Ishai. Zero-knowledge proofs on secret-shared data via fully linear PCPs. In CRYPTO, Proceedings, Part III, pages 67-97, 2019. Google Scholar
  15. Elette Boyle, Nishanth Chandran, Niv Gilboa, Divya Gupta, Yuval Ishai, Nishant Kumar, and Mayank Rathee. Function secret sharing for mixed-mode and fixed-point secure computation. In EUROCRYPT, pages 871-900, 2021. Google Scholar
  16. Elette Boyle, Sanjam Garg, Abhishek Jain, Yael Tauman Kalai, and Amit Sahai. Secure computation against adaptive auxiliary information. In CRYPTO, pages 316-334, 2013. Google Scholar
  17. Elette Boyle, Niv Gilboa, and Yuval Ishai. Function secret sharing: Improvements and extensions. In CCS, pages 1292-1303, 2016. Google Scholar
  18. Elette Boyle, Shafi Goldwasser, Abhishek Jain, and Yael Tauman Kalai. Multiparty computation secure against continual memory leakage. In STOC, Proceedings, pages 1235-1254, 2012. Google Scholar
  19. Elette Boyle, Shafi Goldwasser, and Yael Tauman Kalai. Leakage-resilient coin tossing. In DISC, Proceedings, pages 181-196, 2011. Google Scholar
  20. Elette Boyle, Gil Segev, and Daniel Wichs. Fully leakage-resilient signatures. In EUROCRYPT, Proceedings, pages 89-108, 2011. Google Scholar
  21. Gabriel Bracha. An asynchronous (n-1)/3-resilient consensus protocol. In PODC, pages 154-162, 1984. Google Scholar
  22. Zvika Brakerski and Shafi Goldwasser. Circular and leakage resilient public-key encryption under subgroup indistinguishability - (or: Quadratic residuosity strikes back). In CRYPTO, Proceedings, pages 1-20, 2010. Google Scholar
  23. Zvika Brakerski, Yael Tauman Kalai, Jonathan Katz, and Vinod Vaikuntanathan. Overcoming the hole in the bucket: Public-key cryptography resilient to continual memory leakage. In FOCS, pages 501-510, 2010. Google Scholar
  24. Zvika Brakerski and Gil Segev. Better security for deterministic public-key encryption: The auxiliary-input setting. In CRYPTO, Proceedings, pages 543-560, 2011. Google Scholar
  25. Gianluca Brian, Antonio Faonio, and Daniele Venturi. Continuously non-malleable secret sharing for general access structures. In TCC, pages 211-232, 2019. Google Scholar
  26. Ran Canetti, Cynthia Dwork, Moni Naor, and Rafail Ostrovsky. Deniable encryption. In CRYPTO, pages 90-104, 1997. Google Scholar
  27. Ran Canetti, Sunoo Park, and Oxana Poburinnaya. Fully deniable interactive encryption. In CRYPTO, pages 807-835, 2020. Google Scholar
  28. Nishanth Chandran, Bhavana Kanukurthi, Sai Lakshmi Bhavana Obbattu, and Sruthi Sekar. Adaptive extractors and their application to leakage resilient secret sharing. In CRYPTO, pages 595-624, 2021. Google Scholar
  29. Eshan Chattopadhyay, Jesse Goodman, Vipul Goyal, Ashutosh Kumar, Xin Li, Raghu Meka, and David Zuckerman. Extractors and secret sharing against bounded collusion protocols. In FOCS, pages 1226-1242, 2020. Google Scholar
  30. Seung Geol Choi, Dana Dachman-Soled, Tal Malkin, and Hoeteck Wee. Black-box construction of a non-malleable encryption scheme from any semantically secure one. In TCC, pages 427-444, 2008. Google Scholar
  31. Seung Geol Choi, Dana Dachman-Soled, Tal Malkin, and Hoeteck Wee. A black-box construction of non-malleable encryption from semantically secure encryption. J. Cryptol., 31(1):172-201, 2018. Google Scholar
  32. Giovanni Di Crescenzo, Richard J. Lipton, and Shabsi Walfish. Perfectly secure password protocols in the bounded retrieval model. In TCC, Proceedings, pages 225-244, 2006. Google Scholar
  33. Dana Dachman-Soled, Feng-Hao Liu, and Hong-Sheng Zhou. Leakage-resilient circuits revisited - optimal number of computing components without leak-free hardware. In EUROCRYPT, Proceedings, Part II, pages 131-158, 2015. Google Scholar
  34. Ivan Damgård, Frédéric Dupuis, and Jesper Buus Nielsen. On the orthogonal vector problem and the feasibility of unconditionally secure leakage-resilient computation. In ICITS, Proceedings, pages 87-104, 2015. Google Scholar
  35. Francesco Davì, Stefan Dziembowski, and Daniele Venturi. Leakage-resilient storage. In SCN, Proceedings, pages 121-137, 2010. Google Scholar
  36. Scott E. Decatur, Oded Goldreich, and Dana Ron. A probabilistic error-correcting scheme. IACR Cryptol. ePrint Arch., 1997:5, 1997. Google Scholar
  37. Scott E. Decatur, Oded Goldreich, and Dana Ron. Computational sample complexity. SIAM J. Comput., 29(3):854-879, 1999. Google Scholar
  38. Whitfield Diffie and Martin E. Hellman. New directions in cryptography. IEEE Trans. Inf. Theory, 22(6):644-654, 1976. Google Scholar
  39. Yevgeniy Dodis, Shafi Goldwasser, Yael Tauman Kalai, Chris Peikert, and Vinod Vaikuntanathan. Public-key encryption schemes with auxiliary inputs. In TCC, Proceedings, pages 361-381, 2010. Google Scholar
  40. Yevgeniy Dodis, Kristiyan Haralambiev, Adriana López-Alt, and Daniel Wichs. Cryptography against continuous memory attacks. In FOCS, pages 511-520, 2010. Google Scholar
  41. Yevgeniy Dodis, Yael Tauman Kalai, and Shachar Lovett. On cryptography with auxiliary input. In STOC, Proceedings, pages 621-630, 2009. Google Scholar
  42. Stefan Dziembowski. Intrusion-resilience via the bounded-storage model. In TCC, Proceedings, pages 207-224, 2006. Google Scholar
  43. Stefan Dziembowski and Sebastian Faust. Leakage-resilient circuits without computational assumptions. In TCC, Proceedings, pages 230-247, 2012. Google Scholar
  44. Stefan Dziembowski and Krzysztof Pietrzak. Intrusion-resilient secret sharing. In FOCS, Proceedings, pages 227-237, 2007. Google Scholar
  45. Antonio Faonio and Daniele Venturi. Non-malleable secret sharing in the computational setting: Adaptive tampering, noisy-leakage resilience, and improved rate. In CRYPTO, pages 448-479, 2019. Google Scholar
  46. Sebastian Faust, Tal Rabin, Leonid Reyzin, Eran Tromer, and Vinod Vaikuntanathan. Protecting circuits from leakage: the computationally-bounded and noisy cases. In EUROCRYPT, Proceedings, pages 135-156, 2010. Google Scholar
  47. Tore Kasper Frederiksen, Yehuda Lindell, Valery Osheter, and Benny Pinkas. Fast distributed RSA key generation for semi-honest and malicious adversaries. In CRYPTO, pages 331-361, 2018. Google Scholar
  48. Taher El Gamal. A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Transactions on Information Theory, 31(4):469-472, 1985. Google Scholar
  49. Sanjam Garg, Abhishek Jain, and Amit Sahai. Leakage-resilient zero knowledge. In CRYPTO, Proceedings, pages 297-315, 2011. Google Scholar
  50. Shafi Goldwasser and Guy N. Rothblum. Securing computation against continuous leakage. In CRYPTO, Proceedings, pages 59-79, 2010. Google Scholar
  51. Shafi Goldwasser and Guy N. Rothblum. How to compute in the presence of leakage. In FOCS, pages 31-40, 2012. Google Scholar
  52. Vipul Goyal, Yuval Ishai, Hemanta K. Maji, Amit Sahai, and Alexander A. Sherstov. Bounded-communication leakage resilience via parity-resilient circuits. In FOCS, pages 1-10, 2016. Google Scholar
  53. Vipul Goyal and Ashutosh Kumar. Non-malleable secret sharing. In STOC, Proceedings, pages 685-698, 2018. Google Scholar
  54. Vipul Goyal and Ashutosh Kumar. Non-malleable secret sharing for general access structures. In CRYPTO, Proceedings, Part I, pages 501-530, 2018. Google Scholar
  55. Venkatesan Guruswami and Mary Wootters. Repairing Reed-Solomon codes. In STOC, Proceedings, pages 216-226, 2016. Google Scholar
  56. Carmit Hazay, Gert Læssøe Mikkelsen, Tal Rabin, Tomas Toft, and Angelo Agatino Nicolosi. Efficient RSA key generation and threshold Paillier in the two-party setting. J. Cryptol., 32(2):265-323, 2019. Google Scholar
  57. Carmit Hazay, Muthuramakrishnan Venkitasubramaniam, and Mor Weiss. ZK-PCPs from leakage-resilient secret sharing. In ITC, 2021. Google Scholar
  58. Carmit Hazay, Muthuramakrishnan Venkitasubramaniam, and Mor Weiss. Protecting distributed primitives against leakage: Equivocal secret sharing and more. IACR Cryptol. ePrint Arch., 2022:497, 2022. Google Scholar
  59. Yuval Ishai, Manoj Prabhakaran, Amit Sahai, and David A. Wagner. Private circuits II: keeping secrets in tamperable circuits. In EUROCRYPT, pages 308-327, 2006. Google Scholar
  60. Yuval Ishai, Amit Sahai, and David A. Wagner. Private circuits: Securing hardware against probing attacks. In CRYPTO, pages 463-481, 2003. Google Scholar
  61. Ali Juma and Yevgeniy Vahlis. Protecting cryptographic keys against continual leakage. In CRYPTO, Proceedings, pages 41-58, 2010. Google Scholar
  62. Yael Tauman Kalai and Leonid Reyzin. A survey of leakage-resilient cryptography. In Providing Sound Foundations for Cryptography: On the Work of Shafi Goldwasser and Silvio Micali, pages 727-794. ACM, 2019. Google Scholar
  63. Bhavana Kanukurthi, Sai Lakshmi Bhavana Obbattu, Sruthi Sekar, and Jenit Tomy. Locally reconstructable non-malleable secret sharing. IACR Cryptol. ePrint Arch., 2021:657, 2021. Google Scholar
  64. Paul Kocher, Jann Horn, Anders Fogh, Daniel Genkin, Daniel Gruss, Werner Haas, Mike Hamburg, Moritz Lipp, Stefan Mangard, Thomas Prescher, Michael Schwarz, and Yuval Yarom. Spectre attacks: Exploiting speculative execution. In SP, pages 1-19, 2019. Google Scholar
  65. Paul C. Kocher. Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems. In CRYPTO, Proceedings, pages 104-113, 1996. Google Scholar
  66. Paul C. Kocher, Joshua Jaffe, and Benjamin Jun. Differential power analysis. In CRYPTO, Proceedings, pages 388-397, 1999. Google Scholar
  67. Ashutosh Kumar, Raghu Meka, and Amit Sahai. Leakage-resilient secret sharing against colluding parties. In FOCS, pages 636-660, 2019. Google Scholar
  68. Fuchun Lin, Mahdi Cheraghchi, Venkatesan Guruswami, Reihaneh Safavi-Naini, and Huaxiong Wang. Non-malleable secret sharing against affine tampering. CoRR, abs/1902.06195, 2019. Google Scholar
  69. Fuchun Lin, Mahdi Cheraghchi, Venkatesan Guruswami, Reihaneh Safavi-Naini, and Huaxiong Wang. Leakage-resilient secret sharing in non-compartmentalized models. In ITC, pages 7:1-7:24, 2020. Google Scholar
  70. Yehuda Lindell and Ariel Nof. Fast secure multiparty ECDSA with practical distributed key generation and applications to cryptocurrency custody. In CCS, pages 1837-1854, 2018. Google Scholar
  71. Moritz Lipp, Michael Schwarz, Daniel Gruss, Thomas Prescher, Werner Haas, Anders Fogh, Jann Horn, Stefan Mangard, Paul Kocher, Daniel Genkin, Yuval Yarom, and Mike Hamburg. Meltdown: Reading kernel memory from user space. In USENIX Security, pages 973-990, 2018. Google Scholar
  72. Hemanta K. Maji, Hai H. Nguyen, Anat Paskin-Cherniavsky, Tom Suad, and Mingyuan Wang. Leakage-resilience of the shamir secret-sharing scheme against physical-bit leakages. In EUROCRYPT, pages 344-374, 2021. Google Scholar
  73. Hemanta K. Maji, Anat Paskin-Cherniavsky, Tom Suad, and Mingyuan Wang. Constructing locally leakage-resilient linear secret-sharing schemes. In CRYPTO, pages 779-808, 2021. Google Scholar
  74. Silvio Micali and Leonid Reyzin. Physically observable cryptography (extended abstract). In TCC, pages 278-296, 2004. Google Scholar
  75. Eric Miles. Iterated group products and leakage resilience against NC¹. In ITCS, pages 261-268, 2014. Google Scholar
  76. Eric Miles and Emanuele Viola. Shielding circuits with groups. In STOC, pages 251-260, 2013. Google Scholar
  77. Moni Naor and Gil Segev. Public-key cryptosystems resilient to key leakage. In CRYPTO, Proceedings, pages 18-35, 2009. Google Scholar
  78. Jesper Buus Nielsen and Mark Simkin. Lower bounds for leakage-resilient secret sharing. In EUROCRYPT, Proceedings, Part I, pages 556-577, 2020. Google Scholar
  79. Guy N. Rothblum. How to compute under 𝒜𝒞⁰ leakage without secure hardware. In CRYPTO, Proceedings, pages 552-569, 2012. Google Scholar
  80. Amit Sahai and Brent Waters. How to use indistinguishability obfuscation: deniable encryption, and more. In STOC, pages 475-484, 2014. Google Scholar
  81. Akshayaram Srinivasan and Prashant Nalini Vasudevan. Leakage resilient secret sharing and applications. In CRYPTO, Proceedings, pages 480-509, 2019. Google Scholar
  82. Ivan Tjuawinata and Chaoping Xing. Leakage-resilient secret sharing with constant share size. CoRR, abs/2105.03074, 2021. URL: http://arxiv.org/abs/2105.03074.
  83. Kang Yang, Xiao Wang, and Jiang Zhang. More efficient MPC from improved triple generation and authenticated garbling. In CCS, pages 1627-1646. ACM, 2020. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact