DROPS

Document

DOI: 10.4230/LIPIcs.ITC.2022.3

Protecting Distributed Primitives Against Leakage: Equivocal Secret Sharing and More

Authors: Carmit Hazay, Muthuramakrishnan Venkitasubramaniam, and Mor Weiss

Published in: LIPIcs, Volume 230, 3rd Conference on Information-Theoretic Cryptography (ITC 2022)

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.

Cite as

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)

Copy BibTex To Clipboard

@InProceedings{hazay_et_al:LIPIcs.ITC.2022.3,
  author =	{Hazay, Carmit and Venkitasubramaniam, Muthuramakrishnan and Weiss, Mor},
  title =	{{Protecting Distributed Primitives Against Leakage: Equivocal Secret Sharing and More}},
  booktitle =	{3rd Conference on Information-Theoretic Cryptography (ITC 2022)},
  pages =	{3:1--3:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-238-9},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{230},
  editor =	{Dachman-Soled, Dana},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2022.3},
  URN =		{urn:nbn:de:0030-drops-164817},
  doi =		{10.4230/LIPIcs.ITC.2022.3},
  annote =	{Keywords: Leakage Resilience, Secret Sharing, Equivocal Secret Sharing, Verifiable Secret Sharing, Function Secret Sharing, Threshold Encryption, Distributed Zero-Knowledge Proofs}
}

Document

DOI: 10.4230/LIPIcs.ITC.2021.6

ZK-PCPs from Leakage-Resilient Secret Sharing

Authors: Carmit Hazay, Muthuramakrishnan Venkitasubramaniam, and Mor Weiss

Published in: LIPIcs, Volume 199, 2nd Conference on Information-Theoretic Cryptography (ITC 2021)

Abstract

Zero-Knowledge PCPs (ZK-PCPs; Kilian, Petrank, and Tardos, STOC `97) are PCPs with the additional zero-knowledge guarantee that the view of any (possibly malicious) verifier making a bounded number of queries to the proof can be efficiently simulated up to a small statistical distance. Similarly, ZK-PCPs of Proximity (ZK-PCPPs; Ishai and Weiss, TCC `14) are PCPPs in which the view of an adversarial verifier can be efficiently simulated with few queries to the input. Previous ZK-PCP constructions obtained an exponential gap between the query complexity q of the honest verifier, and the bound q^* on the queries of a malicious verifier (i.e., q = poly log (q^*)), but required either exponential-time simulation, or adaptive honest verification. This should be contrasted with standard PCPs, that can be verified non-adaptively (i.e., with a single round of queries to the proof). The problem of constructing such ZK-PCPs, even when q^* = q, has remained open since they were first introduced more than 2 decades ago. This question is also open for ZK-PCPPs, for which no construction with non-adaptive honest verification is known (not even with exponential-time simulation). We resolve this question by constructing the first ZK-PCPs and ZK-PCPPs which simultaneously achieve efficient zero-knowledge simulation and non-adaptive honest verification. Our schemes have a square-root query gap, namely q^*/q = O(√n) where n is the input length. Our constructions combine the "MPC-in-the-head" technique (Ishai et al., STOC `07) with leakage-resilient secret sharing. Specifically, we use the MPC-in-the-head technique to construct a ZK-PCP variant over a large alphabet, then employ leakage-resilient secret sharing to design a new alphabet reduction for ZK-PCPs which preserves zero-knowledge.

Cite as

Carmit Hazay, Muthuramakrishnan Venkitasubramaniam, and Mor Weiss. ZK-PCPs from Leakage-Resilient Secret Sharing. In 2nd Conference on Information-Theoretic Cryptography (ITC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 199, pp. 6:1-6:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{hazay_et_al:LIPIcs.ITC.2021.6,
  author =	{Hazay, Carmit and Venkitasubramaniam, Muthuramakrishnan and Weiss, Mor},
  title =	{{ZK-PCPs from Leakage-Resilient Secret Sharing}},
  booktitle =	{2nd Conference on Information-Theoretic Cryptography (ITC 2021)},
  pages =	{6:1--6:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-197-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{199},
  editor =	{Tessaro, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2021.6},
  URN =		{urn:nbn:de:0030-drops-143250},
  doi =		{10.4230/LIPIcs.ITC.2021.6},
  annote =	{Keywords: Zero Knowledge, Probabilisitically Checkable Proofs, PCPs of Proximity, Leakage Resilience, Secret Sharing}
}

Search Results

Documents authored by Venkitasubramaniam, Muthuramakrishnan

Protecting Distributed Primitives Against Leakage: Equivocal Secret Sharing and More

Abstract

Cite as

ZK-PCPs from Leakage-Resilient Secret Sharing

Abstract

Cite as

Thanks for your feedback!

Could not send message