Volume
LIPIcs, Volume 230
3rd Conference on Information-Theoretic Cryptography (ITC 2022)
-
Part of:
Series:
Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Conference on Information-Theoretic Cryptography (ITC)
Event
ITC 2022, July 5-7, 2022, Cambridge, MA, USAEditor
Publication Details
- published at: 2022-06-30
- Publisher: Schloss Dagstuhl – Leibniz-Zentrum für Informatik
- ISBN: 978-3-95977-238-9
- DBLP: db/conf/icits/itc2022
Access Numbers
- Detailed Access Statistics available here
-
Total Document Accesses (updated on a weekly basis):
0PDF Downloads
Documents
No documents found matching your filter selection.
Document
Complete Volume
LIPIcs, Volume 230, ITC 2022, Complete Volume
Abstract
LIPIcs, Volume 230, ITC 2022, Complete Volume
Cite as
3rd Conference on Information-Theoretic Cryptography (ITC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 230, pp. 1-328, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@Proceedings{dachmansoled:LIPIcs.ITC.2022,
title = {{LIPIcs, Volume 230, ITC 2022, Complete Volume}},
booktitle = {3rd Conference on Information-Theoretic Cryptography (ITC 2022)},
pages = {1--328},
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},
URN = {urn:nbn:de:0030-drops-164775},
doi = {10.4230/LIPIcs.ITC.2022},
annote = {Keywords: LIPIcs, Volume 230, ITC 2022, Complete Volume}
}
Document
Front Matter
Front Matter, Table of Contents, Preface, Conference Organization
Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as
3rd Conference on Information-Theoretic Cryptography (ITC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 230, pp. 0:i-0:xii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{dachmansoled:LIPIcs.ITC.2022.0,
author = {Dachman-Soled, Dana},
title = {{Front Matter, Table of Contents, Preface, Conference Organization}},
booktitle = {3rd Conference on Information-Theoretic Cryptography (ITC 2022)},
pages = {0:i--0:xii},
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.0},
URN = {urn:nbn:de:0030-drops-164780},
doi = {10.4230/LIPIcs.ITC.2022.0},
annote = {Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
Multi-Server PIR with Full Error Detection and Limited Error Correction
Abstract
An 𝓁-server Private Information Retrieval (PIR) scheme allows a client to retrieve the τ-th element a_τ from a database a = (a₁,…,a_n) which is replicated among 𝓁 servers. It is called t-private if any coalition of t servers learns no information on τ, and b-error correcting if a client can correctly compute a_τ from 𝓁 answers containing b errors. This paper concerns the following problems: Is there a t-private 𝓁-server PIR scheme with communication complexity o(n) such that a client can detect errors with probability 1-ε even if 𝓁-1 servers return false answers? Is it possible to add error correction capability to it? We first formalize a notion of (1-ε)-fully error detecting PIR in such a way that an answer returned by any malicious server depends on at most t queries, which reflects t-privacy. We then prove an impossibility result that there exists no 1-fully error detecting (i.e., ε = 0) PIR scheme with o(n) communication. Next, for ε > 0, we construct 1-private (1-ε)-fully error detecting and (𝓁/2-O(1))-error correcting PIR schemes which have n^{o(1)} communication, and a t-private one which has O(n^{c}) communication for any t ≥ 2 and some constant c < 1. Technically, we show generic transformation methods to add error correction capability to a basic fully error detecting PIR scheme. We also construct such basic schemes by modifying certain existing PIR schemes which have no error detection capability.
Cite as
Reo Eriguchi, Kaoru Kurosawa, and Koji Nuida. Multi-Server PIR with Full Error Detection and Limited Error Correction. In 3rd Conference on Information-Theoretic Cryptography (ITC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 230, pp. 1:1-1:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{eriguchi_et_al:LIPIcs.ITC.2022.1,
author = {Eriguchi, Reo and Kurosawa, Kaoru and Nuida, Koji},
title = {{Multi-Server PIR with Full Error Detection and Limited Error Correction}},
booktitle = {3rd Conference on Information-Theoretic Cryptography (ITC 2022)},
pages = {1:1--1:20},
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.1},
URN = {urn:nbn:de:0030-drops-164796},
doi = {10.4230/LIPIcs.ITC.2022.1},
annote = {Keywords: Private Information Retrieval, Error Detection, Error Correction}
}
Document
Property-Preserving Hash Functions and Combinatorial Group Testing
Abstract
Property-preserving hash (PPH) function is a class of hash functions that allows an evaluation of the property of inputs from their hash values. Boyle {et al}. at ITCS 2019 recently introduced it and considered the robustness of PPH against an adversary who accesses the internal randomness of PPH, and proposed two robust PPH constructions for a weak form of Hamming distance predicate. The second construction received attention for its short hash value, although it relies on an ad-hoc security assumption. The first construction, which is entirely hash-based and based on the classical collision-resistance assumption, has been largely overlooked. We study their first construction and discover its close connection to a seemingly different field of hash/MAC-based (adversarial) error detection using the theory of Combinatorial Group Testing (CGT). We show some consequences of this discovery. In particular, we show that some existing proposals in the field of CGT-based error detection can be converted into a PPH for the Hamming distance property, and they immediately improve and generalize Boyle {et al}. ’s hash-based PPH proposal. We also show that the idea of Boyle {et al}. is useful in the context of a variant of CGT problem.
Cite as
Kazuhiko Minematsu. Property-Preserving Hash Functions and Combinatorial Group Testing. In 3rd Conference on Information-Theoretic Cryptography (ITC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 230, pp. 2:1-2:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{minematsu:LIPIcs.ITC.2022.2,
author = {Minematsu, Kazuhiko},
title = {{Property-Preserving Hash Functions and Combinatorial Group Testing}},
booktitle = {3rd Conference on Information-Theoretic Cryptography (ITC 2022)},
pages = {2:1--2:14},
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.2},
URN = {urn:nbn:de:0030-drops-164809},
doi = {10.4230/LIPIcs.ITC.2022.2},
annote = {Keywords: Hash function, Property-Preserving Hash, Combinatorial Group Testing, Provable Security}
}
Document
Protecting Distributed Primitives Against Leakage: Equivocal Secret Sharing and More
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
Maliciously Circuit-Private FHE from Information-Theoretic Principles
Abstract
Fully homomorphic encryption (FHE) allows arbitrary computations on encrypted data. The standard security requirement, IND-CPA security, ensures that the encrypted data remain private. However, it does not guarantee privacy for the computation performed on the encrypted data. Statistical circuit privacy offers a strong privacy guarantee for the computation process, namely that a homomorphically evaluated ciphertext does not leak any information on how the result of the computation was obtained. Malicious statistical circuit privacy requires this to hold even for maliciously generated keys and ciphertexts. Ostrovsky, Paskin and Paskin (CRYPTO 2014) constructed an FHE scheme achieving malicious statistical circuit privacy.
Their construction, however, makes non-black-box use of a specific underlying FHE scheme, resulting in a circuit-private scheme with inherently high overhead.
This work presents a conceptually different construction of maliciously circuit-private FHE from simple information-theoretical principles. Furthermore, our construction only makes black-box use of the underlying FHE scheme, opening the possibility of achieving practically efficient schemes. Finally, in contrast to the OPP scheme in our scheme, pre- and post-homomorphic ciphertexts are syntactically the same, enabling new applications in multi-hop settings.
Cite as
Nico Döttling and Jesko Dujmovic. Maliciously Circuit-Private FHE from Information-Theoretic Principles. In 3rd Conference on Information-Theoretic Cryptography (ITC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 230, pp. 4:1-4:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{dottling_et_al:LIPIcs.ITC.2022.4,
author = {D\"{o}ttling, Nico and Dujmovic, Jesko},
title = {{Maliciously Circuit-Private FHE from Information-Theoretic Principles}},
booktitle = {3rd Conference on Information-Theoretic Cryptography (ITC 2022)},
pages = {4:1--4: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.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2022.4},
URN = {urn:nbn:de:0030-drops-164826},
doi = {10.4230/LIPIcs.ITC.2022.4},
annote = {Keywords: Fully Homomorphic Encryption, FHE, Homomorphic Encryption, Oblivious Transfer, Malicious Statistical Circuit Privacy, Multi-Hop, Information Theory, Cryptography}
}
Document
From Privacy-Only to Simulatable OT: Black-Box, Round-Optimal, Information-Theoretic
Abstract
We present an information-theoretic transformation from any 2-round OT protocol with only game-based security in the presence of malicious adversaries into a 4-round (which is known to be optimal) OT protocol with simulation-based security in the presence of malicious adversaries.
Our transform is the first satisfying all of the following properties at the same time:
- It is in the plain model, without requiring any setup assumption.
- It only makes black-box usage of the underlying OT protocol.
- It is information-theoretic, as it does not require any further cryptographic assumption (besides the existence of the underlying OT protocol). Additionally, our transform yields a cubic improvement in communication complexity over the best previously known transformation.
Cite as
Varun Madathil, Chris Orsini, Alessandra Scafuro, and Daniele Venturi. From Privacy-Only to Simulatable OT: Black-Box, Round-Optimal, Information-Theoretic. In 3rd Conference on Information-Theoretic Cryptography (ITC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 230, pp. 5:1-5:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{madathil_et_al:LIPIcs.ITC.2022.5,
author = {Madathil, Varun and Orsini, Chris and Scafuro, Alessandra and Venturi, Daniele},
title = {{From Privacy-Only to Simulatable OT: Black-Box, Round-Optimal, Information-Theoretic}},
booktitle = {3rd Conference on Information-Theoretic Cryptography (ITC 2022)},
pages = {5:1--5:20},
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.5},
URN = {urn:nbn:de:0030-drops-164836},
doi = {10.4230/LIPIcs.ITC.2022.5},
annote = {Keywords: Oblivious Transfer, Black-Box compiler, Malicious Security, Plain Model}
}
Document
On the Distributed Discrete Logarithm Problem with Preprocessing
Abstract
Protocols solving the Distributed Discrete Logarithm (DDLog) problem are a core component of many recent constructions of group-based homomorphic secret sharing schemes. On a high-level, these protocols enable two parties to transform multiplicative shares of a secret into additive share locally without any communication. Due to their important applications, various generic optimized DDLog protocols were proposed in the literature, culminating in the asymptotically optimal generic protocol of Dinur, Keller, and Klein (J. Cryptol. 2020) solving DDLog in time T with error probability O(W/T²) when the magnitude of the secret is bounded by W.
Given that DDLog is solved repeatedly with respect to a fixed group in its applications, a natural approach for improving the efficiency of DDLog protocols could be via leveraging some precomputed group-specific advice. To understand the limitations of this approach, we revisit the distributed discrete logarithm problem in the preprocessing model and study the possible time-space trade-offs for DDLog in the generic group model. As our main result, we show that, in a group of size N, any generic DDLog protocol for secrets of magnitude W with parties running in time T using precomputed group-specific advice of size S has success probability ε = O (T²/W + max{S,log W} ⋅ T²/N) . Thus, assuming N ≥ W log W, we get a lower bound ST² = Ω(ε N) on the time-space trade-off for DDLog protocols using large advice of size S = Ω(N/W). Interestingly, for DDLog protocols using small advice of size S = O(N/W), we get a lower bound T² = Ω(ε W) on the running time, which, in the constant-error regime, asymptotically matches the running time of the DDLog protocol without any advice of Dinur et al. (J. Cryptol. 2020). In other words, we show that generic DDLog protocols achieving constant success probability do not benefit from any advice of size S = O(N/W) in the online phase of the DDLog problem.
Cite as
Pavel Hubáček, Ľubica Jančová, and Veronika Králová. On the Distributed Discrete Logarithm Problem with Preprocessing. In 3rd Conference on Information-Theoretic Cryptography (ITC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 230, pp. 6:1-6:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{hubacek_et_al:LIPIcs.ITC.2022.6,
author = {Hub\'{a}\v{c}ek, Pavel and Jan\v{c}ov\'{a}, \v{L}ubica and Kr\'{a}lov\'{a}, Veronika},
title = {{On the Distributed Discrete Logarithm Problem with Preprocessing}},
booktitle = {3rd Conference on Information-Theoretic Cryptography (ITC 2022)},
pages = {6:1--6: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.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2022.6},
URN = {urn:nbn:de:0030-drops-164847},
doi = {10.4230/LIPIcs.ITC.2022.6},
annote = {Keywords: Distributed discrete logarithm problem, preprocessing, generic group model}
}
Document
A Note on the Complexity of Private Simultaneous Messages with Many Parties
Abstract
For k = ω(log n), we prove a Ω(k²n / log(kn)) lower bound on private simultaneous messages (PSM) with k parties who receive n-bit inputs. This extends the Ω(n) lower bound due to Appelbaum, Holenstein, Mishra and Shayevitz [Journal of Cryptology, 2019] to the many-party (k = ω(log n)) setting. It is the first PSM lower bound that increases quadratically with the number of parties, and moreover the first unconditional, explicit bound that grows with both k and n. This note extends the work of Ball, Holmgren, Ishai, Liu, and Malkin [ITCS 2020], who prove communication complexity lower bounds on decomposable randomized encodings (DREs), which correspond to the special case of k-party PSMs with n = 1. To give a concise and readable introduction to the method, we focus our presentation on perfect PSM schemes.
Cite as
Marshall Ball and Tim Randolph. A Note on the Complexity of Private Simultaneous Messages with Many Parties. In 3rd Conference on Information-Theoretic Cryptography (ITC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 230, pp. 7:1-7:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{ball_et_al:LIPIcs.ITC.2022.7,
author = {Ball, Marshall and Randolph, Tim},
title = {{A Note on the Complexity of Private Simultaneous Messages with Many Parties}},
booktitle = {3rd Conference on Information-Theoretic Cryptography (ITC 2022)},
pages = {7:1--7:12},
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.7},
URN = {urn:nbn:de:0030-drops-164855},
doi = {10.4230/LIPIcs.ITC.2022.7},
annote = {Keywords: Secure computation, Private Simultaneous Messages}
}
Document
Multiparty Computation with Covert Security and Public Verifiability
Abstract
Multiparty computation protocols (MPC) are said to be secure against covert adversaries if the honest parties are guaranteed to detect any misbehavior by the malicious parties with a constant probability. Protocols that, upon detecting a cheating attempt, additionally allow the honest parties to compute certificates, which enable third parties to be convinced of the malicious behavior of the accused parties, are called publicly verifiable. In this work, we make several contributions to the domain of MPC with security against covert adversaries.
We identify a subtle flaw in a protocol of Goyal, Mohassel, and Smith (Eurocrypt 2008), meaning that their protocol does not allow to identify a cheating party, and show how to fix their original construction to obtain security against covert adversaries.
We present generic compilers that transform arbitrary passively secure preprocessing protocols, i.e. protocols where the parties have no private inputs, into protocols that are secure against covert adversaries and publicly verifiable. Using our compiler, we construct the first efficient variants of the BMR and the SPDZ protocols that are secure and publicly verifiable against a covert adversary that corrupts all but one party, and also construct variants with covert security and identifiable abort.
We observe that an existing impossibility result by Ishai, Ostrovsky, and Seyalioglu (TCC 2012) can be used to show that there exist certain functionalities that cannot be realized by parties, that have oracle-access to broadcast and arbitrary two-party functionalities, with information-theoretic security against a covert adversary.
Cite as
Peter Scholl, Mark Simkin, and Luisa Siniscalchi. Multiparty Computation with Covert Security and Public Verifiability. In 3rd Conference on Information-Theoretic Cryptography (ITC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 230, pp. 8:1-8:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{scholl_et_al:LIPIcs.ITC.2022.8,
author = {Scholl, Peter and Simkin, Mark and Siniscalchi, Luisa},
title = {{Multiparty Computation with Covert Security and Public Verifiability}},
booktitle = {3rd Conference on Information-Theoretic Cryptography (ITC 2022)},
pages = {8:1--8: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.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2022.8},
URN = {urn:nbn:de:0030-drops-164861},
doi = {10.4230/LIPIcs.ITC.2022.8},
annote = {Keywords: Multi-party computation, covert security, public verifiability}
}
Document
On Seedless PRNGs and Premature Next
Abstract
Pseudorandom number generators with input (PRNGs) are cryptographic algorithms that generate pseudorandom bits from accumulated entropic inputs (e.g., keystrokes, interrupt timings, etc.). This paper studies in particular PRNGs that are secure against premature next attacks (Kelsey et al., FSE '98), a class of attacks leveraging the fact that a PRNG may produce an output (which could be seen by an adversary!) before enough entropy has been accumulated. Practical designs adopt either unsound entropy-estimation methods to prevent such attacks (as in Linux’s /dev/random) or sophisticated pool-based approaches as in Yarrow (MacOS/FreeBSD) and Fortuna (Windows).
The only prior theoretical study of premature next attacks (Dodis et al., Algorithmica '17) considers either a seeded setting or assumes constant entropy rate, and thus falls short of providing and validating practical designs. Assuming the availability of random seed is particularly problematic, first because this requires us to somehow generate a random seed without using our PRNG, but also because we must ensure that the entropy inputs to the PRNG remain independent of the seed. Indeed, all practical designs are seedless. However, prior works on seedless PRNGs (Coretti et al., CRYPTO '19; Dodis et al., ITC '21, CRYPTO'21) do not consider premature next attacks.
The main goal of this paper is to investigate the feasibility of theoretically sound seedless PRNGs that are secure against premature next attacks. To this end, we make the following contributions:
1) We prove that it is impossible to achieve seedless PRNGs that are secure against premature-next attacks, even in a rather weak model. Namely, the impossibility holds even when the entropic inputs to the PRNG are independent. In particular, our impossibility result holds in settings where seedless PRNGs are otherwise possible.
2) Given the above impossibility result, we investigate whether existing seedless pool-based approaches meant to overcome premature next attacks in practical designs provide meaningful guarantees in certain settings. Specifically, we show the following.
3) We introduce a natural condition on the entropic input and prove that it implies security of the round-robin entropy accumulation PRNG used by Windows 10, called Fortuna. Intuitively, our condition requires the input entropy "not to vary too wildly" within a given round-robin round.
4) We prove that the "root pool" approach (also used in Windows 10) is secure for general entropy inputs, provided that the system’s state is not compromised after system startup.
Cite as
Sandro Coretti, Yevgeniy Dodis, Harish Karthikeyan, Noah Stephens-Davidowitz, and Stefano Tessaro. On Seedless PRNGs and Premature Next. In 3rd Conference on Information-Theoretic Cryptography (ITC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 230, pp. 9:1-9:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{coretti_et_al:LIPIcs.ITC.2022.9,
author = {Coretti, Sandro and Dodis, Yevgeniy and Karthikeyan, Harish and Stephens-Davidowitz, Noah and Tessaro, Stefano},
title = {{On Seedless PRNGs and Premature Next}},
booktitle = {3rd Conference on Information-Theoretic Cryptography (ITC 2022)},
pages = {9:1--9:20},
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.9},
URN = {urn:nbn:de:0030-drops-164870},
doi = {10.4230/LIPIcs.ITC.2022.9},
annote = {Keywords: seedless PRNGs, pseudorandom number generators, PRNG, Fortuna, premature next}
}
Document
Refuting the Dream XOR Lemma via Ideal Obfuscation and Resettable MPC
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.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
Revisiting Collision and Local Opening Analysis of ABR Hash
Abstract
The question of building the most efficient tn-to-n-bit collision-resistant hash function H from a smaller (say, 2n-to-n-bit) compression function f is one of the fundamental questions in symmetric key cryptography. This question has a rich history, and was open for general t, until a recent breakthrough paper by Andreeva, Bhattacharyya and Roy at Eurocrypt'21, who designed an elegant mode (which we call ABR) achieving roughly 2t/3 calls to f, which matches the famous Stam’s bound from CRYPTO'08. Unfortunately, we have found serious issues in the claims made by the authors. These issues appear quite significant, and range from verifiably false statements to noticeable gaps in the proofs (e.g., omissions of important cases and unjustified bounds).
We were unable to patch up the current proof provided by the authors. Instead, we prove from scratch the security of the ABR construction for the first non-trivial case t = 11 (ABR mode of height 3), which was incorrectly handled by the authors. In particular, our result matches Stam’s bound for t = 11. While the general case is still open, we hope our techniques will prove useful to finally settle the question of the optimal efficiency of hash functions.
Cite as
Chandranan Dhar, Yevgeniy Dodis, and Mridul Nandi. Revisiting Collision and Local Opening Analysis of ABR Hash. In 3rd Conference on Information-Theoretic Cryptography (ITC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 230, pp. 11:1-11:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{dhar_et_al:LIPIcs.ITC.2022.11,
author = {Dhar, Chandranan and Dodis, Yevgeniy and Nandi, Mridul},
title = {{Revisiting Collision and Local Opening Analysis of ABR Hash}},
booktitle = {3rd Conference on Information-Theoretic Cryptography (ITC 2022)},
pages = {11:1--11:22},
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.11},
URN = {urn:nbn:de:0030-drops-164890},
doi = {10.4230/LIPIcs.ITC.2022.11},
annote = {Keywords: ABR hash, collision resistance, local opening}
}
Document
A Fully-Constructive Discrete-Logarithm Preprocessing Algorithm with an Optimal Time-Space Tradeoff
Abstract
Identifying the concrete hardness of the discrete logarithm problem is crucial for instantiating a vast range of cryptographic schemes. Towards this goal, Corrigan-Gibbs and Kogan (EUROCRYPT '18) extended the generic-group model for capturing "preprocessing" algorithms, offering a tradeoff between the space S required for storing their preprocessing information, the time T required for their online phase, and their success probability. Corrigan-Gibbs and Kogan proved an upper bound of Õ(S T²/N) on the success probability of any such algorithm, where N is the prime order of the group, matching the known preprocessing algorithms.
However, the known algorithms assume the availability of truly random hash functions, without taking into account the space required for storing them as part of the preprocessing information, and the time required for evaluating them in essentially each and every step of the online phase. This led Corrigan-Gibbs and Kogan to pose the open problem of designing a discrete-logarithm preprocessing algorithm that is fully constructive in the sense that it relies on explicit hash functions whose description lengths and evaluation times are taken into account in the algorithm’s space-time tradeoff.
We present a fully constructive discrete-logarithm preprocessing algorithm with an asymptotically optimal space-time tradeoff (i.e., with success probability Ω̃(S T²/N)). In addition, we obtain an algorithm that settles the corresponding tradeoff for the computational Diffie-Hellman problem. Our approach is based on derandomization techniques that provide rather weak independence guarantees. On the one hand, we show that such guarantees can be realized in our setting with only a minor efficiency overhead. On the other hand, exploiting such weak guarantees requires a more subtle and in-depth analysis of the underlying combinatorial structure compared to that of the known preprocessing algorithms and their analyses.
Cite as
Lior Rotem and Gil Segev. A Fully-Constructive Discrete-Logarithm Preprocessing Algorithm with an Optimal Time-Space Tradeoff. In 3rd Conference on Information-Theoretic Cryptography (ITC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 230, pp. 12:1-12:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{rotem_et_al:LIPIcs.ITC.2022.12,
author = {Rotem, Lior and Segev, Gil},
title = {{A Fully-Constructive Discrete-Logarithm Preprocessing Algorithm with an Optimal Time-Space Tradeoff}},
booktitle = {3rd Conference on Information-Theoretic Cryptography (ITC 2022)},
pages = {12:1--12:16},
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.12},
URN = {urn:nbn:de:0030-drops-164905},
doi = {10.4230/LIPIcs.ITC.2022.12},
annote = {Keywords: Discrete logarithm, Preprocessing}
}
Document
Revisiting the Uber Assumption in the Algebraic Group Model: Fine-Grained Bounds in Hidden-Order Groups and Improved Reductions in Bilinear Groups
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.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
Universally Composable Almost-Everywhere Secure Computation
Abstract
Most existing work on secure multi-party computation (MPC) ignores a key idiosyncrasy of modern communication networks, that there are a limited number of communication paths between any two nodes, many of which might even be corrupted. The problem becomes particularly acute in the information-theoretic setting, where the lack of trusted setups (and the cryptographic primitives they enable) makes communication over sparse networks more challenging. The work by Garay and Ostrovsky [EUROCRYPT'08] on almost-everywhere MPC (AE-MPC), introduced "best-possible security" properties for MPC over such incomplete networks, where necessarily some of the honest parties may be excluded from the computation.
In this work, we provide a universally composable definition of almost-everywhere security, which allows us to automatically and accurately capture the guarantees of AE-MPC (as well as AE-communication, the analogous "best-possible security" version of secure communication) in the Universal Composability (UC) framework of Canetti. Our results offer the first simulation-based treatment of this important but under-investigated problem, along with the first simulation-based proof of AE-MPC. To achieve that goal, we state and prove a general composition theorem, which makes precise the level or "quality" of AE-security that is obtained when a protocol’s hybrids are replaced with almost-everywhere components.
Cite as
Nishanth Chandran, Pouyan Forghani, Juan Garay, Rafail Ostrovsky, Rutvik Patel, and Vassilis Zikas. Universally Composable Almost-Everywhere Secure Computation. In 3rd Conference on Information-Theoretic Cryptography (ITC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 230, pp. 14:1-14:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{chandran_et_al:LIPIcs.ITC.2022.14,
author = {Chandran, Nishanth and Forghani, Pouyan and Garay, Juan and Ostrovsky, Rafail and Patel, Rutvik and Zikas, Vassilis},
title = {{Universally Composable Almost-Everywhere Secure Computation}},
booktitle = {3rd Conference on Information-Theoretic Cryptography (ITC 2022)},
pages = {14:1--14:25},
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.14},
URN = {urn:nbn:de:0030-drops-164929},
doi = {10.4230/LIPIcs.ITC.2022.14},
annote = {Keywords: Secure multi-party computation, universal composability, almost-everywhere secure computation, sparse graphs, secure message transmission}
}
Document
Static vs. Adaptive Security in Perfect MPC: A Separation and the Adaptive Security of BGW
Abstract
Adaptive security is a highly desirable property in the design of secure protocols. It tolerates adversaries that corrupt parties as the protocol proceeds, as opposed to static security where the adversary corrupts the parties at the onset of the execution. The well-accepted folklore is that static and adaptive securities are equivalent for perfectly secure protocols. Indeed, this folklore is backed up with a transformation by Canetti et al. (EUROCRYPT'01), showing that any perfectly secure protocol that is statically secure and satisfies some basic requirements is also adaptively secure. Yet, the transformation results in an adaptively secure protocol with inefficient simulation (i.e., where the simulator might run in super-polynomial time even if the adversary runs just in polynomial time). Inefficient simulation is problematic when using the protocol as a sub-routine in the computational setting.
Our main question is whether an alternative efficient transformation from static to adaptive security exists. We show an inherent difficulty in achieving this goal generically. In contrast to the folklore, we present a protocol that is perfectly secure with efficient static simulation (therefore also adaptively secure with inefficient simulation), but for which efficient adaptive simulation does not exist (assuming the existence of one-way permutations).
In addition, we prove that the seminal protocol of Ben-Or, Goldwasser and Wigderson (STOC'88) is secure against adaptive, semi-honest corruptions with efficient simulation. Previously, adaptive security of the protocol, as is, was only known either for a restricted class of circuits, or for all circuits but with inefficient simulation.
Cite as
Gilad Asharov, Ran Cohen, and Oren Shochat. Static vs. Adaptive Security in Perfect MPC: A Separation and the Adaptive Security of BGW. In 3rd Conference on Information-Theoretic Cryptography (ITC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 230, pp. 15:1-15:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{asharov_et_al:LIPIcs.ITC.2022.15,
author = {Asharov, Gilad and Cohen, Ran and Shochat, Oren},
title = {{Static vs. Adaptive Security in Perfect MPC: A Separation and the Adaptive Security of BGW}},
booktitle = {3rd Conference on Information-Theoretic Cryptography (ITC 2022)},
pages = {15:1--15:16},
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.15},
URN = {urn:nbn:de:0030-drops-164933},
doi = {10.4230/LIPIcs.ITC.2022.15},
annote = {Keywords: secure multiparty computation, perfect security, adaptive security, BGW protocol}
}
Document
Tight Estimate of the Local Leakage Resilience of the Additive Secret-Sharing Scheme & Its Consequences
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.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
Information-Theoretic Distributed Point Functions
Abstract
A distributed point function (DPF) (Gilboa-Ishai, Eurocrypt 2014) is a cryptographic primitive that enables compressed additive secret-sharing of a secret weight-1 vector across two or more servers. DPFs support a wide range of cryptographic applications, including efficient private information retrieval, secure aggregation, and more. Up to now, the study of DPFs was restricted to the computational security setting, relying on one-way functions. This assumption is necessary in the case of a dishonest majority.
We present the first statistically private 3-server DPF for domain size N with subpolynomial key size N^{o(1)}. We also present a similar perfectly private 4-server DPF. Our constructions offer benefits over their computationally secure counterparts, beyond the superior security guarantee, including better computational complexity and better protocols for distributed key generation, all while having comparable communication complexity for moderate-sized parameters.
Cite as
Elette Boyle, Niv Gilboa, Yuval Ishai, and Victor I. Kolobov. Information-Theoretic Distributed Point Functions. In 3rd Conference on Information-Theoretic Cryptography (ITC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 230, pp. 17:1-17:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{boyle_et_al:LIPIcs.ITC.2022.17,
author = {Boyle, Elette and Gilboa, Niv and Ishai, Yuval and Kolobov, Victor I.},
title = {{Information-Theoretic Distributed Point Functions}},
booktitle = {3rd Conference on Information-Theoretic Cryptography (ITC 2022)},
pages = {17:1--17:14},
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.17},
URN = {urn:nbn:de:0030-drops-164957},
doi = {10.4230/LIPIcs.ITC.2022.17},
annote = {Keywords: Information-theoretic cryptography, homomorphic secret sharing, private information retrieval, secure multiparty computation}
}