21 Search Results for "Wichs, Daniel"

Volume

LIPIcs, Volume 163

1st Conference on Information-Theoretic Cryptography (ITC 2020)

ITC 2020, June 17-19, 2020, Boston, MA, USA

Editors: Yael Tauman Kalai, Adam D. Smith, and Daniel Wichs

Document
DOI: 10.4230/LIPIcs.ITC.2022.10
Refuting the Dream XOR Lemma via Ideal Obfuscation and Resettable MPC

Authors: Saikrishna Badrinarayanan, Yuval Ishai, Dakshita Khurana, Amit Sahai, and Daniel Wichs

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

Abstract
We provide counterexamples to the "dream" version of Yao’s XOR Lemma. In particular, we put forward explicit candidates for hard predicates, such that the advantage of predicting the XOR of many independent copies does not decrease beyond some fixed negligible function, even as the number of copies gets arbitrarily large. We provide two such constructions: - Our first construction is in the ideal obfuscation model (alternatively, assuming virtual black-box obfuscation for a concrete class of circuits). It develops a general framework that may be of broader interest, and allows us to embed an instance of a resettably-secure multiparty computation protocol into a one-way function. Along the way, we design the first resettably-secure multiparty computation protocol for general functionalities in the plain model with super-polynomial simulation, under standard assumptions. - The second construction relies on public-coin differing-inputs obfuscation (PCdiO) along with a certain form of hash-function security called extended second-preimage resistance (ESPR). It starts with a previously known counterexample to the dream direct-product hardness amplification based on ESPR, and uses PCdiO to upgrade it into a counterexample for the XOR lemma. Prior to our work, even completely heuristic counterexamples of this type were not known.
Cite as

Saikrishna Badrinarayanan, Yuval Ishai, Dakshita Khurana, Amit Sahai, and Daniel Wichs. Refuting the Dream XOR Lemma via Ideal Obfuscation and Resettable MPC. In 3rd Conference on Information-Theoretic Cryptography (ITC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 230, pp. 10:1-10:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{badrinarayanan_et_al:LIPIcs.ITC.2022.10,
  author =	{Badrinarayanan, Saikrishna and Ishai, Yuval and Khurana, Dakshita and Sahai, Amit and Wichs, Daniel},
  title =	{{Refuting the Dream XOR Lemma via Ideal Obfuscation and Resettable MPC}},
  booktitle =	{3rd Conference on Information-Theoretic Cryptography (ITC 2022)},
  pages =	{10:1--10:21},
  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.10},
  URN =		{urn:nbn:de:0030-drops-164885},
  doi =		{10.4230/LIPIcs.ITC.2022.10},
  annote =	{Keywords: XOR Lemma, Resettable MPC, Obfuscation}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2022.56
Small-Box Cryptography

Authors: Yevgeniy Dodis, Harish Karthikeyan, and Daniel Wichs

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

Abstract
One of the ultimate goals of symmetric-key cryptography is to find a rigorous theoretical framework for building block ciphers from small components, such as cryptographic S-boxes, and then argue why iterating such small components for sufficiently many rounds would yield a secure construction. Unfortunately, a fundamental obstacle towards reaching this goal comes from the fact that traditional security proofs cannot get security beyond 2^{-n}, where n is the size of the corresponding component. As a result, prior provably secure approaches - which we call "big-box cryptography" - always made n larger than the security parameter, which led to several problems: (a) the design was too coarse to really explain practical constructions, as (arguably) the most interesting design choices happening when instantiating such "big-boxes" were completely abstracted out; (b) the theoretically predicted number of rounds for the security of this approach was always dramatically smaller than in reality, where the "big-box" building block could not be made as ideal as required by the proof. For example, Even-Mansour (and, more generally, key-alternating) ciphers completely ignored the substitution-permutation network (SPN) paradigm which is at the heart of most real-world implementations of such ciphers. In this work, we introduce a novel paradigm for justifying the security of existing block ciphers, which we call small-box cryptography. Unlike the "big-box" paradigm, it allows one to go much deeper inside the existing block cipher constructions, by only idealizing a small (and, hence, realistic!) building block of very small size n, such as an 8-to-32-bit S-box. It then introduces a clean and rigorous mixture of proofs and hardness conjectures which allow one to lift traditional, and seemingly meaningless, "at most 2^{-n}" security proofs for reduced-round idealized variants of the existing block ciphers, into meaningful, full-round security justifications of the actual ciphers used in the real world. We then apply our framework to the analysis of SPN ciphers (e.g, generalizations of AES), getting quite reasonable and plausible concrete hardness estimates for the resulting ciphers. We also apply our framework to the design of stream ciphers. Here, however, we focus on the simplicity of the resulting construction, for which we managed to find a direct "big-box"-style security justification, under a well studied and widely believed eXact Linear Parity with Noise (XLPN) assumption. Overall, we hope that our work will initiate many follow-up results in the area of small-box cryptography.
Cite as

Yevgeniy Dodis, Harish Karthikeyan, and Daniel Wichs. Small-Box Cryptography. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 56:1-56:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{dodis_et_al:LIPIcs.ITCS.2022.56,
  author =	{Dodis, Yevgeniy and Karthikeyan, Harish and Wichs, Daniel},
  title =	{{Small-Box Cryptography}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{56:1--56:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.56},
  URN =		{urn:nbn:de:0030-drops-156527},
  doi =		{10.4230/LIPIcs.ITCS.2022.56},
  annote =	{Keywords: Block Ciphers, S-Box, Cryptography}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.ITC.2020
LIPIcs, Volume 163, ITC 2020, Complete Volume

Authors: Yael Tauman Kalai, Adam D. Smith, and Daniel Wichs

Published in: LIPIcs, Volume 163, 1st Conference on Information-Theoretic Cryptography (ITC 2020)

Abstract
LIPIcs, Volume 163, ITC 2020, Complete Volume
Cite as

1st Conference on Information-Theoretic Cryptography (ITC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 163, pp. 1-352, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@Proceedings{taumankalai_et_al:LIPIcs.ITC.2020,
  title =	{{LIPIcs, Volume 163, ITC 2020, Complete Volume}},
  booktitle =	{1st Conference on Information-Theoretic Cryptography (ITC 2020)},
  pages =	{1--352},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-151-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{163},
  editor =	{Tauman Kalai, Yael and Smith, Adam D. and Wichs, Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2020},
  URN =		{urn:nbn:de:0030-drops-121048},
  doi =		{10.4230/LIPIcs.ITC.2020},
  annote =	{Keywords: LIPIcs, Volume 163, ITC 2020, Complete Volume}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.ITC.2020.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Yael Tauman Kalai, Adam D. Smith, and Daniel Wichs

Published in: LIPIcs, Volume 163, 1st Conference on Information-Theoretic Cryptography (ITC 2020)

Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as

1st Conference on Information-Theoretic Cryptography (ITC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 163, pp. 0:i-0:xiv, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{taumankalai_et_al:LIPIcs.ITC.2020.0,
  author =	{Tauman Kalai, Yael and Smith, Adam D. and Wichs, Daniel},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{1st Conference on Information-Theoretic Cryptography (ITC 2020)},
  pages =	{0:i--0:xiv},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-151-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{163},
  editor =	{Tauman Kalai, Yael and Smith, Adam D. and Wichs, Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2020.0},
  URN =		{urn:nbn:de:0030-drops-121057},
  doi =		{10.4230/LIPIcs.ITC.2020.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
DOI: 10.4230/LIPIcs.ITC.2020.1
Separating Local & Shuffled Differential Privacy via Histograms

Authors: Victor Balcer and Albert Cheu

Published in: LIPIcs, Volume 163, 1st Conference on Information-Theoretic Cryptography (ITC 2020)

Abstract
Recent work in differential privacy has highlighted the shuffled model as a promising avenue to compute accurate statistics while keeping raw data in users' hands. We present a protocol in this model that estimates histograms with error independent of the domain size. This implies an arbitrarily large gap in sample complexity between the shuffled and local models. On the other hand, we show that the models are equivalent when we impose the constraints of pure differential privacy and single-message randomizers.
Cite as

Victor Balcer and Albert Cheu. Separating Local & Shuffled Differential Privacy via Histograms. In 1st Conference on Information-Theoretic Cryptography (ITC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 163, pp. 1:1-1:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{balcer_et_al:LIPIcs.ITC.2020.1,
  author =	{Balcer, Victor and Cheu, Albert},
  title =	{{Separating Local \& Shuffled Differential Privacy via Histograms}},
  booktitle =	{1st Conference on Information-Theoretic Cryptography (ITC 2020)},
  pages =	{1:1--1:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-151-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{163},
  editor =	{Tauman Kalai, Yael and Smith, Adam D. and Wichs, Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2020.1},
  URN =		{urn:nbn:de:0030-drops-121068},
  doi =		{10.4230/LIPIcs.ITC.2020.1},
  annote =	{Keywords: Differential Privacy, Distributed Protocols, Histograms}
}
Document
DOI: 10.4230/LIPIcs.ITC.2020.2
d-Multiplicative Secret Sharing for Multipartite Adversary Structures

Authors: Reo Eriguchi and Noboru Kunihiro

Published in: LIPIcs, Volume 163, 1st Conference on Information-Theoretic Cryptography (ITC 2020)

Abstract
Secret sharing schemes are said to be d-multiplicative if the i-th shares of any d secrets s^(j), j∈[d] can be converted into an additive share of the product ∏_{j∈[d]}s^(j). d-Multiplicative secret sharing is a central building block of multiparty computation protocols with minimum number of rounds which are unconditionally secure against possibly non-threshold adversaries. It is known that d-multiplicative secret sharing is possible if and only if no d forbidden subsets covers the set of all the n players or, equivalently, it is private with respect to an adversary structure of type Q_d. However, the only known method to achieve d-multiplicativity for any adversary structure of type Q_d is based on CNF secret sharing schemes, which are not efficient in general in that the information ratios are exponential in n. In this paper, we explicitly construct a d-multiplicative secret sharing scheme for any 𝓁-partite adversary structure of type Q_d whose information ratio is O(n^{𝓁+1}). Our schemes are applicable to the class of all the 𝓁-partite adversary structures, which is much wider than that of the threshold ones. Furthermore, our schemes achieve information ratios which are polynomial in n if 𝓁 is constant and hence are more efficient than CNF schemes. In addition, based on the standard embedding of 𝓁-partite adversary structures into ℝ^𝓁, we introduce a class of 𝓁-partite adversary structures of type Q_d with good geometric properties and show that there exist more efficient d-multiplicative secret sharing schemes for adversary structures in that family than the above general construction. The family of adversary structures is a natural generalization of that of the threshold ones and includes some adversary structures which arise in real-world scenarios.
Cite as

Reo Eriguchi and Noboru Kunihiro. d-Multiplicative Secret Sharing for Multipartite Adversary Structures. In 1st Conference on Information-Theoretic Cryptography (ITC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 163, pp. 2:1-2:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{eriguchi_et_al:LIPIcs.ITC.2020.2,
  author =	{Eriguchi, Reo and Kunihiro, Noboru},
  title =	{{d-Multiplicative Secret Sharing for Multipartite Adversary Structures}},
  booktitle =	{1st Conference on Information-Theoretic Cryptography (ITC 2020)},
  pages =	{2:1--2:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-151-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{163},
  editor =	{Tauman Kalai, Yael and Smith, Adam D. and Wichs, Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2020.2},
  URN =		{urn:nbn:de:0030-drops-121079},
  doi =		{10.4230/LIPIcs.ITC.2020.2},
  annote =	{Keywords: Secret sharing scheme, multiplicative secret sharing scheme, multipartite adversary structure}
}
Document
DOI: 10.4230/LIPIcs.ITC.2020.3
Efficient MPC with a Mixed Adversary

Authors: Martin Hirt and Marta Mularczyk

Published in: LIPIcs, Volume 163, 1st Conference on Information-Theoretic Cryptography (ITC 2020)

Abstract
Over the past 20 years, the efficiency of secure multi-party protocols has been greatly improved. While the seminal protocols from the late 80’s require a communication of Ω(n⁶) field elements per multiplication among n parties, recent protocols offer linear communication complexity. This means that each party needs to communicate a constant number of field elements per multiplication, independent of n. However, these efficient protocols only offer active security, which implies that at most t<n/3 (perfect security), respectively t<n/2 (statistical or computational security) parties may be corrupted. Higher corruption thresholds (i.e., t≥ n/2) can only be achieved with degraded security (unfair abort), where one single corrupted party can prevent honest parties from learning their outputs. The aforementioned upper bounds (t<n/3 and t<n/2) have been circumvented by considering mixed adversaries (Fitzi et al., Crypto' 98), i.e., adversaries that corrupt, at the same time, some parties actively, some parties passively, and some parties in the fail-stop manner. It is possible, for example, to achieve perfect security even if 2/3 of the parties are faulty (three quarters of which may abort in the middle of the protocol, and a quarter may even arbitrarily misbehave). This setting is much better suited to many applications, where the crash of a party is more likely than a coordinated active attack. Surprisingly, since the presentation of the feasibility result for the mixed setting, no progress has been made in terms of efficiency: the state-of-the-art protocol still requires a communication of Ω(n⁶) field elements per multiplication. In this paper, we present a perfectly-secure MPC protocol for the mixed setting with essentially the same efficiency as the best MPC protocols for the active-only setting. For the first time, this allows to tolerate faulty majorities, while still providing optimal efficiency. As a special case, this also results in the first fully-secure MPC protocol secure against any number of crashing parties, with optimal (i.e., linear in n) communication. We provide simulation-based proofs of our construction.
Cite as

Martin Hirt and Marta Mularczyk. Efficient MPC with a Mixed Adversary. In 1st Conference on Information-Theoretic Cryptography (ITC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 163, pp. 3:1-3:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{hirt_et_al:LIPIcs.ITC.2020.3,
  author =	{Hirt, Martin and Mularczyk, Marta},
  title =	{{Efficient MPC with a Mixed Adversary}},
  booktitle =	{1st Conference on Information-Theoretic Cryptography (ITC 2020)},
  pages =	{3:1--3:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-151-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{163},
  editor =	{Tauman Kalai, Yael and Smith, Adam D. and Wichs, Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2020.3},
  URN =		{urn:nbn:de:0030-drops-121083},
  doi =		{10.4230/LIPIcs.ITC.2020.3},
  annote =	{Keywords: Multi-party Computation, Communication Cost}
}
Document
DOI: 10.4230/LIPIcs.ITC.2020.4
Practical Relativistic Zero-Knowledge for NP

Authors: Claude Crépeau, Arnaud Y. Massenet, Louis Salvail, Lucas Shigeru Stinchcombe, and Nan Yang

Published in: LIPIcs, Volume 163, 1st Conference on Information-Theoretic Cryptography (ITC 2020)

Abstract
In a Multi-Prover environment, how little spatial separation is sufficient to assert the validity of an NP statement in Perfect Zero-Knowledge ? We exhibit a set of two novel Zero-Knowledge protocols for the 3-COLorability problem that use two (local) provers or three (entangled) provers and only require exchanging one edge and two bits with two trits per prover. This greatly improves the ability to prove Zero-Knowledge statements on very short distances with very basic communication gear.
Cite as

Claude Crépeau, Arnaud Y. Massenet, Louis Salvail, Lucas Shigeru Stinchcombe, and Nan Yang. Practical Relativistic Zero-Knowledge for NP. In 1st Conference on Information-Theoretic Cryptography (ITC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 163, pp. 4:1-4:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{crepeau_et_al:LIPIcs.ITC.2020.4,
  author =	{Cr\'{e}peau, Claude and Massenet, Arnaud Y. and Salvail, Louis and Stinchcombe, Lucas Shigeru and Yang, Nan},
  title =	{{Practical Relativistic Zero-Knowledge for NP}},
  booktitle =	{1st Conference on Information-Theoretic Cryptography (ITC 2020)},
  pages =	{4:1--4:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-151-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{163},
  editor =	{Tauman Kalai, Yael and Smith, Adam D. and Wichs, Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2020.4},
  URN =		{urn:nbn:de:0030-drops-121091},
  doi =		{10.4230/LIPIcs.ITC.2020.4},
  annote =	{Keywords: Multi-Prover Interactive Proofs, Relativistic Commitments, 3-COLorability, Quantum Entanglement, Non-Locality}
}
Document
DOI: 10.4230/LIPIcs.ITC.2020.5
Use Your Brain! Arithmetic 3PC for Any Modulus with Active Security

Authors: Hendrik Eerikson, Marcel Keller, Claudio Orlandi, Pille Pullonen, Joonas Puura, and Mark Simkin

Published in: LIPIcs, Volume 163, 1st Conference on Information-Theoretic Cryptography (ITC 2020)

Abstract
Secure multiparty computation (MPC) allows a set of mutually distrustful parties to compute a public function on their private inputs without revealing anything beyond the output of the computation. This paper focuses on the specific case of actively secure three-party computation with an honest majority. In particular, we are interested in solutions which allow to evaluate arithmetic circuits over real-world CPU word sizes, like 32- and 64-bit words. Our starting point is the novel compiler of Damgård et al. from CRYPTO 2018. First, we present an improved version of it which reduces the online communication complexity by a factor of 2. Next, we replace their preprocessing protocol (with arithmetic modulo a large prime) with a more efficient preprocessing which only performs arithmetic modulo powers of two. Finally, we present a novel "postprocessing" check which replaces the preprocessing phase. These protocols offer different efficiency tradeoffs and can therefore outperform each other in different deployment settings. We demonstrate this with benchmarks in a LAN and different WAN settings. Concretely, we achieve a throughput of 1 million 64-bit multiplications per second with parties located in different continents and 3 million in one location.
Cite as

Hendrik Eerikson, Marcel Keller, Claudio Orlandi, Pille Pullonen, Joonas Puura, and Mark Simkin. Use Your Brain! Arithmetic 3PC for Any Modulus with Active Security. In 1st Conference on Information-Theoretic Cryptography (ITC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 163, pp. 5:1-5:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{eerikson_et_al:LIPIcs.ITC.2020.5,
  author =	{Eerikson, Hendrik and Keller, Marcel and Orlandi, Claudio and Pullonen, Pille and Puura, Joonas and Simkin, Mark},
  title =	{{Use Your Brain! Arithmetic 3PC for Any Modulus with Active Security}},
  booktitle =	{1st Conference on Information-Theoretic Cryptography (ITC 2020)},
  pages =	{5:1--5:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-151-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{163},
  editor =	{Tauman Kalai, Yael and Smith, Adam D. and Wichs, Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2020.5},
  URN =		{urn:nbn:de:0030-drops-121104},
  doi =		{10.4230/LIPIcs.ITC.2020.5},
  annote =	{Keywords: Secure Multiparty Computation, Information Theoretic Security}
}
Document
DOI: 10.4230/LIPIcs.ITC.2020.6
Expander Graphs Are Non-Malleable Codes

Authors: Peter Michael Reichstein Rasmussen and Amit Sahai

Published in: LIPIcs, Volume 163, 1st Conference on Information-Theoretic Cryptography (ITC 2020)

Abstract
Any d-regular graph on n vertices with spectral expansion λ satisfying n = Ω(d³log(d)/λ) yields a O((λ^{3/2})/d)-non-malleable code for single-bit messages in the split-state model.
Cite as

Peter Michael Reichstein Rasmussen and Amit Sahai. Expander Graphs Are Non-Malleable Codes. In 1st Conference on Information-Theoretic Cryptography (ITC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 163, pp. 6:1-6:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{rasmussen_et_al:LIPIcs.ITC.2020.6,
  author =	{Rasmussen, Peter Michael Reichstein and Sahai, Amit},
  title =	{{Expander Graphs Are Non-Malleable Codes}},
  booktitle =	{1st Conference on Information-Theoretic Cryptography (ITC 2020)},
  pages =	{6:1--6:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-151-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{163},
  editor =	{Tauman Kalai, Yael and Smith, Adam D. and Wichs, Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2020.6},
  URN =		{urn:nbn:de:0030-drops-121114},
  doi =		{10.4230/LIPIcs.ITC.2020.6},
  annote =	{Keywords: Non-Malleable Code, Expander Graph, Mixing Lemma}
}
Document
DOI: 10.4230/LIPIcs.ITC.2020.7
Leakage-Resilient Secret Sharing in Non-Compartmentalized Models

Authors: Fuchun Lin, Mahdi Cheraghchi, Venkatesan Guruswami, Reihaneh Safavi-Naini, and Huaxiong Wang

Published in: LIPIcs, Volume 163, 1st Conference on Information-Theoretic Cryptography (ITC 2020)

Abstract
Leakage-resilient secret sharing has mostly been studied in the compartmentalized models, where a leakage oracle can arbitrarily leak bounded number of bits from all shares, provided that the oracle only has access to a bounded number of shares when the leakage is taking place. We start a systematic study of leakage-resilient secret sharing against global leakage, where the leakage oracle can access the full set of shares simultaneously, but the access is restricted to a special class of leakage functions. More concretely, the adversary can corrupt several players and obtain their shares, as well as applying a leakage function from a specific class to the full share vector. We explicitly construct such leakage-resilient secret sharing with respect to affine leakage functions and low-degree multi-variate polynomial leakage functions, respectively. For affine leakage functions, we obtain schemes with threshold access structure that are leakage-resilient as long as there is a substantial difference between the total amount of information obtained by the adversary, through corrupting individual players and leaking from the full share vector, and the amount that the reconstruction algorithm requires for reconstructing the secret. Furthermore, if we assume the adversary is non-adaptive, we can even make the secret length asymptotically equal to the difference, as the share length grows. Specifically, we have a threshold scheme with parameters similar to Shamir’s scheme and is leakage-resilient against affine leakage. For multi-variate polynomial leakage functions with degree bigger than one, our constructions here only yield ramp schemes that are leakage-resilient against such leakage. Finally, as a result of independent interest, we show that our approach to leakage-resilient secret sharing also yields a competitive scheme compared with the state-of-the-art construction in the compartmentalized models.
Cite as

Fuchun Lin, Mahdi Cheraghchi, Venkatesan Guruswami, Reihaneh Safavi-Naini, and Huaxiong Wang. Leakage-Resilient Secret Sharing in Non-Compartmentalized Models. In 1st Conference on Information-Theoretic Cryptography (ITC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 163, pp. 7:1-7:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{lin_et_al:LIPIcs.ITC.2020.7,
  author =	{Lin, Fuchun and Cheraghchi, Mahdi and Guruswami, Venkatesan and Safavi-Naini, Reihaneh and Wang, Huaxiong},
  title =	{{Leakage-Resilient Secret Sharing in Non-Compartmentalized Models}},
  booktitle =	{1st Conference on Information-Theoretic Cryptography (ITC 2020)},
  pages =	{7:1--7:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-151-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{163},
  editor =	{Tauman Kalai, Yael and Smith, Adam D. and Wichs, Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2020.7},
  URN =		{urn:nbn:de:0030-drops-121124},
  doi =		{10.4230/LIPIcs.ITC.2020.7},
  annote =	{Keywords: Leakage-resilient cryptography, Secret sharing scheme, Randomness extractor}
}
Document
DOI: 10.4230/LIPIcs.ITC.2020.8
Lower Bounds for Function Inversion with Quantum Advice

Authors: Kai-Min Chung, Tai-Ning Liao, and Luowen Qian

Published in: LIPIcs, Volume 163, 1st Conference on Information-Theoretic Cryptography (ITC 2020)

Abstract
Function inversion is the problem that given a random function f: [M] → [N], we want to find pre-image of any image f^{-1}(y) in time T. In this work, we revisit this problem under the preprocessing model where we can compute some auxiliary information or advice of size S that only depends on f but not on y. It is a well-studied problem in the classical settings, however, it is not clear how quantum algorithms can solve this task any better besides invoking Grover’s algorithm [Grover, 1996], which does not leverage the power of preprocessing. Nayebi et al. [Nayebi et al., 2015] proved a lower bound ST² ≥ ̃Ω(N) for quantum algorithms inverting permutations, however, they only consider algorithms with classical advice. Hhan et al. [Minki Hhan et al., 2019] subsequently extended this lower bound to fully quantum algorithms for inverting permutations. In this work, we give the same asymptotic lower bound to fully quantum algorithms for inverting functions for fully quantum algorithms under the regime where M = O(N). In order to prove these bounds, we generalize the notion of quantum random access code, originally introduced by Ambainis et al. [Ambainis et al., 1999], to the setting where we are given a list of (not necessarily independent) random variables, and we wish to compress them into a variable-length encoding such that we can retrieve a random element just using the encoding with high probability. As our main technical contribution, we give a nearly tight lower bound (for a wide parameter range) for this generalized notion of quantum random access codes, which may be of independent interest.
Cite as

Kai-Min Chung, Tai-Ning Liao, and Luowen Qian. Lower Bounds for Function Inversion with Quantum Advice. In 1st Conference on Information-Theoretic Cryptography (ITC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 163, pp. 8:1-8:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{chung_et_al:LIPIcs.ITC.2020.8,
  author =	{Chung, Kai-Min and Liao, Tai-Ning and Qian, Luowen},
  title =	{{Lower Bounds for Function Inversion with Quantum Advice}},
  booktitle =	{1st Conference on Information-Theoretic Cryptography (ITC 2020)},
  pages =	{8:1--8:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-151-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{163},
  editor =	{Tauman Kalai, Yael and Smith, Adam D. and Wichs, Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2020.8},
  URN =		{urn:nbn:de:0030-drops-121134},
  doi =		{10.4230/LIPIcs.ITC.2020.8},
  annote =	{Keywords: Cryptanalysis, Data Structures, Quantum Query Complexity}
}
Document
DOI: 10.4230/LIPIcs.ITC.2020.9
Out-Of-Band Authenticated Group Key Exchange: From Strong Authentication to Immediate Key Delivery

Authors: Moni Naor, Lior Rotem, and Gil Segev

Published in: LIPIcs, Volume 163, 1st Conference on Information-Theoretic Cryptography (ITC 2020)

Abstract
Given the inherent ad-hoc nature of popular communication platforms, out-of-band authenticated key-exchange protocols are becoming widely deployed: Key exchange protocols that enable users to detect man-in-the-middle attacks by manually authenticating one short value. In this work we put forward the notion of immediate key delivery for such protocols, requiring that even if some users participate in the protocol but do not complete it (e.g., due to losing data connectivity or to other common synchronicity issues), then the remaining users should still agree on a shared secret. A property of a similar flavor was introduced by Alwen, Coretti and Dodis (EUROCRYPT '19) asking for immediate decryption of messages in user-to-user messaging while assuming that a shared secret has already been established - but the underlying issue is crucial already during the initial key exchange and goes far beyond the context of messaging. Equipped with our immediate key delivery property, we formalize strong notions of security for out-of-band authenticated group key exchange, and demonstrate that the existing protocols either do not satisfy our notions of security or are impractical (these include, in particular, the protocols deployed by Telegram, Signal and WhatsApp). Then, based on the existence of any passively-secure key-exchange protocol (e.g., the Diffie-Hellman protocol), we construct an out-of-band authenticated group key-exchange protocol satisfying our notions of security. Our protocol is inspired by techniques that have been developed in the context of fair string sampling in order to minimize the effect of adversarial aborts, and offers the optimal tradeoff between the length of its out-of-band value and its security.
Cite as

Moni Naor, Lior Rotem, and Gil Segev. Out-Of-Band Authenticated Group Key Exchange: From Strong Authentication to Immediate Key Delivery. In 1st Conference on Information-Theoretic Cryptography (ITC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 163, pp. 9:1-9:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{naor_et_al:LIPIcs.ITC.2020.9,
  author =	{Naor, Moni and Rotem, Lior and Segev, Gil},
  title =	{{Out-Of-Band Authenticated Group Key Exchange: From Strong Authentication to Immediate Key Delivery}},
  booktitle =	{1st Conference on Information-Theoretic Cryptography (ITC 2020)},
  pages =	{9:1--9:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-151-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{163},
  editor =	{Tauman Kalai, Yael and Smith, Adam D. and Wichs, Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2020.9},
  URN =		{urn:nbn:de:0030-drops-121146},
  doi =		{10.4230/LIPIcs.ITC.2020.9},
  annote =	{Keywords: End-to-end encryption, out-of-band authentication, key exchange}
}
Document
DOI: 10.4230/LIPIcs.ITC.2020.10
Hardness vs. (Very Little) Structure in Cryptography: A Multi-Prover Interactive Proofs Perspective

Authors: Gil Segev and Ido Shahaf

Published in: LIPIcs, Volume 163, 1st Conference on Information-Theoretic Cryptography (ITC 2020)

Abstract
The hardness of highly-structured computational problems gives rise to a variety of public-key primitives. On one hand, the structure exhibited by such problems underlies the basic functionality of public-key primitives, but on the other hand it may endanger public-key cryptography in its entirety via potential algorithmic advances. This subtle interplay initiated a fundamental line of research on whether structure is inherently necessary for cryptography, starting with Rudich’s early work (PhD Thesis '88) and recently leading to that of Bitansky, Degwekar and Vaikuntanathan (CRYPTO '17). Identifying the structure of computational problems with their corresponding complexity classes, Bitansky et al. proved that a variety of public-key primitives (e.g., public-key encryption, oblivious transfer and even functional encryption) cannot be used in a black-box manner to construct either any hard language that has NP-verifiers both for the language itself and for its complement, or any hard language (and even promise problem) that has a statistical zero-knowledge proof system - corresponding to hardness in the structured classes NP ∩ coNP or SZK, respectively, from a black-box perspective. In this work we prove that the same variety of public-key primitives do not inherently require even very little structure in a black-box manner: We prove that they do not imply any hard language that has multi-prover interactive proof systems both for the language and for its complement - corresponding to hardness in the class MIP ∩ coMIP from a black-box perspective. Conceptually, given that MIP = NEXP, our result rules out languages with very little structure. Already the cases of languages that have IP or AM proof systems both for the language itself and for its complement, which we rule out as immediate corollaries, lead to intriguing insights. For the case of IP, where our result can be circumvented using non-black-box techniques, we reveal a gap between black-box and non-black-box techniques. For the case of AM, where circumventing our result via non-black-box techniques would be a major development, we both strengthen and unify the proofs of Bitansky et al. for languages that have NP-verifiers both for the language itself and for its complement and for languages that have a statistical zero-knowledge proof system.
Cite as

Gil Segev and Ido Shahaf. Hardness vs. (Very Little) Structure in Cryptography: A Multi-Prover Interactive Proofs Perspective. In 1st Conference on Information-Theoretic Cryptography (ITC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 163, pp. 10:1-10:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{segev_et_al:LIPIcs.ITC.2020.10,
  author =	{Segev, Gil and Shahaf, Ido},
  title =	{{Hardness vs. (Very Little) Structure in Cryptography: A Multi-Prover Interactive Proofs Perspective}},
  booktitle =	{1st Conference on Information-Theoretic Cryptography (ITC 2020)},
  pages =	{10:1--10:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-151-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{163},
  editor =	{Tauman Kalai, Yael and Smith, Adam D. and Wichs, Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2020.10},
  URN =		{urn:nbn:de:0030-drops-121154},
  doi =		{10.4230/LIPIcs.ITC.2020.10},
  annote =	{Keywords: Hardness vs. Structure, Black-box Constructions, Interactive Proofs}
}
  • Refine by Author
  • 4 Wichs, Daniel
  • 2 Sahai, Amit
  • 2 Segev, Gil
  • 2 Smith, Adam D.
  • 2 Tauman Kalai, Yael
  • Show More...

  • Refine by Classification
  • 6 Theory of computation → Cryptographic primitives
  • 5 Security and privacy → Information-theoretic techniques
  • 4 Security and privacy → Cryptography
  • 4 Theory of computation → Computational complexity and cryptography
  • 4 Theory of computation → Cryptographic protocols
  • Show More...

  • Refine by Keyword
  • 2 Secret sharing scheme
  • 1 3-COLorability
  • 1 Anonymous messages
  • 1 Black-box Constructions
  • 1 Block Ciphers
  • Show More...

  • Refine by Type
  • 20 document
  • 1 volume

  • Refine by Publication Year
  • 19 2020
  • 2 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