CryptoDB
Eldon Chung
NOTE: imports for ToSC and TCHES are no longer functioning.
ORCID: 0000-0002-0048-4610
Publications
Year
Venue
Title
2023
CRYPTO
Extractors: Low Entropy Requirements Colliding With Non-Malleability
Abstract
Two-source extractors are deterministic functions that, given two independent weak sources of randomness,
output a (close to) uniformly random string of bits. Cheraghchi and Guruswami (TCC 2015) introduced two-
source non-malleable extractors that combine the properties of randomness extraction with tamper resilience.
Two-source non-malleable extractors have since then attracted a lot of attention, and have very quickly become
fundamental objects in cryptosystems involving communication channels that cannot be fully trusted. Various
applications of two-source non-malleable extractors include in particular non-malleable codes, non-malleable
commitments, non-malleable secret sharing, network extraction, and privacy amplification with tamperable
memory.
The best known constructions of two-source non-malleable extractors are due to Chattopadhyay, Goyal, and
Li (STOC 2016), Li (STOC 2017), and Li (CCC 2019). All of these constructions require both sources to have
min-entropy at least 0.99n, where n is the bit-length of each source.
In this work, we introduce collision-resistant randomness extractors. This allows us to design a compiler
that, given a two-source non-malleable extractor, and a collision-resistant extractor, outputs a two-source non-
malleable extractor that inherits the non-malleability property from the non-malleable extractor, and the entropy
requirement from the collision-resistant extractor. Nested application of this compiler leads to a dramatic
improvement of the state-of-the-art mentioned above. We obtain a construction of a two-source non-malleable
extractor where one source is required to have min-entropy greater than 0.8n, and the other source is required to
have only polylog(n) min-entropy. Moreover, the other parameters of our construction, i.e., the output length,
and the error remain comparable to prior constructions.
2022
TCC
On Secret Sharing, Randomness, and Random-less Reductions for Secret Sharing
Abstract
Secret-sharing is one of the most fundamental primitives in cryptography, and has found several applications. All known constructions of secret sharing (with the exception of those with a pathological choice of parameters) require access to uniform randomness. However, in practice it is extremely challenging to generate a source of uniform randomness. This has led to a large body of research devoted to designing randomized algorithms and cryptographic primitives from imperfect sources of randomness. Motivated by this, Bosley and Dodis (TCC 2007) asked whether it is even possible to construct a $2$-out-of-$2$ secret sharing scheme without access to uniform randomness.
In this work, we make significant progress towards answering this question. Namely, we resolve this question for secret sharing schemes with important additional properties: $1$-bit leakage-resilience and non-malleability. We prove that, for not too small secrets, it is impossible to construct any $2$-out-of-$2$ leakage-resilient or non-malleable secret sharing scheme without access to uniform randomness.
Given that the problem of whether $2$-out-of-$2$ secret sharing requires uniform randomness has been open for more than a decade, it is reasonable to consider intermediate problems towards resolving the open question. In a spirit similar to NP-completeness, we also study how the existence of a $t$-out-of-$n$ secret sharing without access to uniform randomness is related to the existence of a $t'$-out-of-$n'$ secret sharing without access to uniform randomness for a different choice of the parameters $t,n,t',n'$.
Coauthors
- Divesh Aggarwal (2)
- Eldon Chung (2)
- Maciej Obremski (2)
- João Ribeiro (1)