4 Search Results for "Shamir, Dana"

Document
DOI: 10.4230/LIPIcs.FSTTCS.2022.14
More Verifier Efficient Interactive Protocols for Bounded Space

Authors: Joshua Cook

Published in: LIPIcs, Volume 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)

Abstract
Let TISP[T, S], BPTISP[T, S], NTISP[T, S] and CoNTISP[T, S] be the set of languages recognized by deterministic, randomized, nondeterministic, and co-nondeterministic algorithms, respectively, running in time T and space S. Let ITIME[T_V, T_P] be the set of languages recognized by an interactive protocol where the verifier runs in time T_V and the prover runs in time T_P. For S = Ω(log(n)) and T constructible in time log(T) S + n, we prove: TISP[T, S] ⊆ ITIME[Õ(log(T) S + n), 2^O(S)] BPTISP[T, S] ⊆ ITIME[Õ(log(T) S + n), 2^O(S)] NTISP[T, S] ⊆ ITIME[Õ(log(T)^2 S + n), 2^O(S)] CoNTISP[T, S] ⊆ ITIME[Õ(log(T)^2 S + n), 2^O(S)] . The best prior verifier time is from Shamir [Shamir, 1992; Lund et al., 1990]: TISP[T, S] ⊆ ITIME[Õ(log(T)(S + n)), 2^O(log(T)(S + n))]. Our prover is faster, and our verifier is faster when S = o(n). The best prior prover time uses ideas from Goldwasser, Kalai, and Rothblum [Goldwasser et al., 2015]: NTISP[T, S] ⊆ ITIME[Õ(log(T) S² + n), 2^O(S)]. Our verifier is faster when log(T) = o(S), and for deterministic algorithms. To our knowledge, no previous interactive protocol for TISP simultaneously has the same verifier time and prover time as ours. In our opinion, our protocol is also simpler than previous protocols.
Cite as

Joshua Cook. More Verifier Efficient Interactive Protocols for Bounded Space. In 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 250, pp. 14:1-14:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{cook:LIPIcs.FSTTCS.2022.14,
  author =	{Cook, Joshua},
  title =	{{More Verifier Efficient Interactive Protocols for Bounded Space}},
  booktitle =	{42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)},
  pages =	{14:1--14:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-261-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{250},
  editor =	{Dawar, Anuj and Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2022.14},
  URN =		{urn:nbn:de:0030-drops-174067},
  doi =		{10.4230/LIPIcs.FSTTCS.2022.14},
  annote =	{Keywords: Interactive Proofs, Verifier Time, Randomized Space, Nondeterministic Space, Fine Grain Complexity}
}
Document
DOI: 10.4230/LIPIcs.ITC.2022.13
Revisiting the Uber Assumption in the Algebraic Group Model: Fine-Grained Bounds in Hidden-Order Groups and Improved Reductions in Bilinear Groups

Authors: Lior Rotem

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

Abstract
We prove strong security guarantees for a wide array of computational and decisional problems, both in hidden-order groups and in bilinear groups, within the algebraic group model (AGM) of Fuchsbauer, Kiltz and Loss (CRYPTO '18). As our first contribution, we put forth a new fine-grained variant of the Uber family of assumptions in hidden-order groups. This family includes in particular the repeated squaring function of Rivest, Shamir and Wagner, which underlies their time-lock puzzle as well as the main known candidates for verifiable delay functions; and a computational variant of the generalized BBS problem, which underlies the timed commitments of Boneh and Naor (CRYPTO '00). We then provide two results within a variant of the AGM, which show that the hardness of solving problems in this family in a less-than-trivial number of steps is implied by well-studied assumptions. The first reduction may be applied in any group (and in particular, class groups), and is to the RSA assumption; and our second reduction is in RSA groups with a modulus which is the product of two safe primes, and is to the factoring assumption. Additionally, we prove that the hardness of any computational problem in the Uber family of problems in bilinear groups is implied by the hardness of the q-discrete logarithm problem. The parameter q in our reduction is the maximal degree in which a variable appears in the polynomials which define the specific problem within the Uber family. This improves upon a recent result of Bauer, Fuchsbauer and Loss (CRYPTO '20), who obtained a similar implication but for a parameter q which is lower bounded by the maximal total degree of one of the above polynomials. We discuss the implications of this improvement to prominent group key-exchange protocols.
Cite as

Lior Rotem. Revisiting the Uber Assumption in the Algebraic Group Model: Fine-Grained Bounds in Hidden-Order Groups and Improved Reductions in Bilinear Groups. In 3rd Conference on Information-Theoretic Cryptography (ITC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 230, pp. 13:1-13:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{rotem:LIPIcs.ITC.2022.13,
  author =	{Rotem, Lior},
  title =	{{Revisiting the Uber Assumption in the Algebraic Group Model: Fine-Grained Bounds in Hidden-Order Groups and Improved Reductions in Bilinear Groups}},
  booktitle =	{3rd Conference on Information-Theoretic Cryptography (ITC 2022)},
  pages =	{13:1--13:13},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2022.13},
  URN =		{urn:nbn:de:0030-drops-164910},
  doi =		{10.4230/LIPIcs.ITC.2022.13},
  annote =	{Keywords: Algebraic group model, Uber assumption, Bilinear groups, Hidden-order groups}
}
Document
DOI: 10.4230/LIPIcs.ITC.2022.16
Tight Estimate of the Local Leakage Resilience of the Additive Secret-Sharing Scheme & Its Consequences

Authors: Hemanta K. Maji, Hai H. Nguyen, Anat Paskin-Cherniavsky, Tom Suad, Mingyuan Wang, Xiuyu Ye, and Albert Yu

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

Abstract
Innovative side-channel attacks have repeatedly exposed the secrets of cryptosystems. Benhamouda, Degwekar, Ishai, and Rabin (CRYPTO-2018) introduced local leakage resilience of secret-sharing schemes to study some of these vulnerabilities. In this framework, the objective is to characterize the unintended information revelation about the secret by obtaining independent leakage from each secret share. This work accurately quantifies the vulnerability of the additive secret-sharing scheme to local leakage attacks and its consequences for other secret-sharing schemes. Consider the additive secret-sharing scheme over a prime field among k parties, where the secret shares are stored in their natural binary representation, requiring λ bits - the security parameter. We prove that the reconstruction threshold k = ω(log λ) is necessary to protect against local physical-bit probing attacks, improving the previous ω(log λ/log log λ) lower bound. This result is a consequence of accurately determining the distinguishing advantage of the "parity-of-parity" physical-bit local leakage attack proposed by Maji, Nguyen, Paskin-Cherniavsky, Suad, and Wang (EUROCRYPT-2021). Our lower bound is optimal because the additive secret-sharing scheme is perfectly secure against any (k-1)-bit (global) leakage and (statistically) secure against (arbitrary) one-bit local leakage attacks when k = ω(log λ). Any physical-bit local leakage attack extends to (1) physical-bit local leakage attacks on the Shamir secret-sharing scheme with adversarially-chosen evaluation places, and (2) local leakage attacks on the Massey secret-sharing scheme corresponding to any linear code. In particular, for Shamir’s secret-sharing scheme, the reconstruction threshold k = ω(log λ) is necessary when the number of parties is n = O(λ log λ). Our analysis of the "parity-of-parity" attack’s distinguishing advantage establishes it as the best-known local leakage attack in these scenarios. Our work employs Fourier-analytic techniques to analyze the "parity-of-parity" attack on the additive secret-sharing scheme. We accurately estimate an exponential sum that captures the vulnerability of this secret-sharing scheme to the parity-of-parity attack, a quantity that is also closely related to the "discrepancy" of the Irwin-Hall probability distribution.
Cite as

Hemanta K. Maji, Hai H. Nguyen, Anat Paskin-Cherniavsky, Tom Suad, Mingyuan Wang, Xiuyu Ye, and Albert Yu. Tight Estimate of the Local Leakage Resilience of the Additive Secret-Sharing Scheme & Its Consequences. In 3rd Conference on Information-Theoretic Cryptography (ITC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 230, pp. 16:1-16:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{maji_et_al:LIPIcs.ITC.2022.16,
  author =	{Maji, Hemanta K. and Nguyen, Hai H. and Paskin-Cherniavsky, Anat and Suad, Tom and Wang, Mingyuan and Ye, Xiuyu and Yu, Albert},
  title =	{{Tight Estimate of the Local Leakage Resilience of the Additive Secret-Sharing Scheme \& Its Consequences}},
  booktitle =	{3rd Conference on Information-Theoretic Cryptography (ITC 2022)},
  pages =	{16:1--16:19},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2022.16},
  URN =		{urn:nbn:de:0030-drops-164943},
  doi =		{10.4230/LIPIcs.ITC.2022.16},
  annote =	{Keywords: leakage resilience, additive secret-sharing, Shamir’s secret-sharing, physical-bit probing leakage attacks, Fourier analysis}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2021.21
Explicit Space-Time Tradeoffs for Proof Labeling Schemes in Graphs with Small Separators

Authors: Orr Fischer, Rotem Oshman, and Dana Shamir

Published in: LIPIcs, Volume 217, 25th International Conference on Principles of Distributed Systems (OPODIS 2021)

Abstract
In distributed verification, our goal is to verify that the network configuration satisfies some desired property, using pre-computed information stored at each network node. This is formally modeled as a proof labeling scheme (PLS): a prover assigns to each node a certificate, and then the nodes exchange their certificates with their neighbors and decide whether to accept or reject the configuration. Subsequent work has shown that in some specific cases, allowing more rounds of communication - so that nodes can communicate further across the network - can yield shorter certificates, trading off the space required to store the certificate against the time required for verification. Such tradeoffs were previously known for trees, cycles, and grids, or for proof labeling schemes where all nodes receive the same certificate. In this work we show that in large classes of graphs, every one-round PLS can be transformed into a multi-round PLS with shorter certificates. We give two constructions: given a 1-round PLS with certificates of 𝓁 bits, in graphs families with balanced edge separators of size s(n), we construct a t-round PLS with certificates of size Õ(𝓁 ⋅ s(n) / t), and in graph families with an excluded minor and maximum degree Δ, we construct a t-round PLS with certificates of size Õ(𝓁 ⋅ Δ / √t). Our constructions are explicit, and we use erasure codes to exploit the larger neighborhood viewed by each node in a t-round PLS.
Cite as

Orr Fischer, Rotem Oshman, and Dana Shamir. Explicit Space-Time Tradeoffs for Proof Labeling Schemes in Graphs with Small Separators. In 25th International Conference on Principles of Distributed Systems (OPODIS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 217, pp. 21:1-21:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{fischer_et_al:LIPIcs.OPODIS.2021.21,
  author =	{Fischer, Orr and Oshman, Rotem and Shamir, Dana},
  title =	{{Explicit Space-Time Tradeoffs for Proof Labeling Schemes in Graphs with Small Separators}},
  booktitle =	{25th International Conference on Principles of Distributed Systems (OPODIS 2021)},
  pages =	{21:1--21:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-219-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{217},
  editor =	{Bramas, Quentin and Gramoli, Vincent and Milani, Alessia},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2021.21},
  URN =		{urn:nbn:de:0030-drops-157969},
  doi =		{10.4230/LIPIcs.OPODIS.2021.21},
  annote =	{Keywords: proof-labeling schemes, space-time tradeoffs, families with excluded minor}
}
  • Refine by Author
  • 1 Cook, Joshua
  • 1 Fischer, Orr
  • 1 Maji, Hemanta K.
  • 1 Nguyen, Hai H.
  • 1 Oshman, Rotem
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Cryptographic primitives
  • 1 Networks
  • 1 Security and privacy → Cryptanalysis and other attacks
  • 1 Security and privacy → Cryptography
  • 1 Theory of computation → Distributed algorithms
  • Show More...

  • Refine by Keyword
  • 1 Algebraic group model
  • 1 Bilinear groups
  • 1 Fine Grain Complexity
  • 1 Fourier analysis
  • 1 Hidden-order groups
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 4 2022

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 Imprint Privacy Contact