International Association
for Cryptologic Research

Recent work has introduced the “Quantum-Computation Classical-Communication” (QCCC) (Chung et. al.) setting for cryptog- raphy. There has been some evidence that One Way Puzzles (OWPuzz) are the natural central cryptographic primitive for this setting (Khurana and Tomer). For a primitive to be considered central it should have sev- eral characteristics. It should be well behaved (which for this paper we will think of as having amplification, combiners, and universal construc- tions); it should be implied by a wide variety of other primitives; and it should be equivalent to some class of useful primitives. We present combiners, correctness and security amplification, and a universal con- struction for OWPuzz. Our proof of security amplification uses a new and cleaner version construction of EFI from OWPuzz (in comparison to the result of Khurana and Tomer) that generalizes to weak OWPuzz and is the most technically involved section of the paper. It was pre- viously known that OWPuzz are implied by other primitives of interest including commitments, symmetric key encryption, one way state gen- erators (OWSG), and therefore pseudorandom states (PRS). However we are able to rule out OWPuzz’s equivalence to many of these primitives by showing a black box separation between general OWPuzz and a re- stricted class of OWPuzz (those with efficient verification, which we call EV − OWPuzz). We then show that EV − OWPuzz are also implied by most of these primitives, which separates them from OWPuzz as well. This separation also separates extending PRS from highly compressing PRS answering an open question of Ananth et. al.

Suppose we have two hash functions h1 and h2, but we trust the security of only one of them. To mitigate this worry, we wish to build a hash combiner C^{h1,h2} which is secure so long as one of the underlying hash functions is. This question has been well-studied in the regime of collision resistance. In this case, concatenating the two hash function outputs clearly works. Unfortunately for practice, a long series of works (Boneh and Boyen, CRYPTO’06; Pietrzak, Eurocrypt’07; Pietrzak, Crypto’08) showed no (noticeably) better combiner for collision resistance is possible. In this work, we revisit this pessimistic state of affairs, motivated the observation that collision-resistance is insufficient for many interesting applications of cryptographic hash functions anyway. Thus, we believe (and argue) the right formulation of the “hash combiner” is to build what we call random oracle (RO) combiners, utilizing stronger assumptions for stronger constructions. Indeed, we circumvent the previous lower bounds for collision resistance by constructing a simple length-preserving RO combiner C^{h1,h2}_{Z1,Z2} (M ) = h1(M, Z1) ⊕ h2(M, Z2), where Z1, Z2 are random salts of appropriate length. We show that this extra randomness is necessary for RO combiners, and indeed our construction is somewhat tight with this lower bound. On the negative side, we show that one cannot generically apply the composition theorem to further replace “monolithic” hash functions h1 and h2 by some simpler indifferentiable (such as the Merkle-Damgard transformation) from smaller components, such as fixed-length compression functions. Finally, despite this issue, we directly prove collision resistance of the Merkle-Damgard variant of our combiner, where h1 and h2 are replaced by iterative Merkle-Damgard hashes applied to a fixed-length compression function. Thus, we can still subvert the concatenation barrier for collision-resistance combiners while utilizing practically small fixed-length components underneath.

A backdoored Pseudorandom Generator (PRG) is a PRG which looks pseudorandom to the outside world, but a saboteur can break PRG security by planting a backdoor into a seemingly honest choice of public parameters, pk, for the system. Backdoored PRGs became increas- ingly important due to revelations about NIST’s backdoored Dual EC PRG, and later results about its practical exploitability. Motivated by this, at Eurocrypt’15 Dodis et al. [20] initiated the ques- tion of immunizing backdoored PRGs. A k-immunization scheme repeat- edly applies a post-processing function to the output of k backdoored PRGs, to render any (unknown) backdoors provably useless. For k = 1, [20] showed that no deterministic immunization is possible, but then constructed “seeded” 1-immunizer either in the random oracle model, or under strong non-falsifiable assumptions. As our first result, we show that no seeded 1-immunization scheme can be black-box reduced to any efficiently falsifiable assumption. This motivates studying k-immunizers for k ≥ 2, which have an ad- ditional advantage of being deterministic (i.e., “seedless”). Indeed, prior work at CCS’17 [35] and CRYPTO’18 [7] gave supporting evidence that simple k-immunizers might exist, albeit in slightly different settings. Un- fortunately, we show that simple standard model proposals of [35,7] (including the XOR function [7]) provably do not work in our setting. On a positive, we confirm the intuition of [35] that a (seedless) random oracle is a provably secure 2-immunizer. On a negative, no (seedless) 2-immunization scheme can be black-box reduced to any efficiently falsi- fiable assumption, at least for a large class of natural 2-immunizers which includes all “cryptographic hash functions.” In summary, our results show that k-immunizers occupy a peculiar place in the cryptographic world. While they likely exist, and can be made practical and efficient, it is unlikely one can reduce their security to a “clean” standard-model assumption.

Recently, the area of Key Transparency (KT) has received a lot of attention, as it allows the service provider to provide auditable and verifiable proofs regarding authenticity of public keys used by various participants. Moreover, it is highly preferable to do it in a privacy-preserving ways, so that users and auditors do not learn anything beyond what is necessary to keep the service provider accountable. Abstractly, the problem of building such systems reduces to constructing so called append-only Zero-Knowledge Sets (aZKS). Unfortunately, none of the previous aZKS constructions adequately addressed the problem of key rotation, which would provide Post-Compromise Security (PCS) in case the server in compromised. In this work we address this concern, and refine an extension of aZKS called Rotatable ZKS (RZKS). In addition to addressing the PCS concern, our notion of RZKS has several other attractive features, such as stronger soundness notion (called extractability), and the ability for a stale communication party to quickly catch up with the current epoch, while ensuring the the server did not erase any of the past data. Of independent interest, we also introduce and build a new primitive called Rotatable Verifiable Random Function (VRF), and show how to build RZKS in a modular fashion from rotatable VRF, ordered accumulators and append-only vector commitment schemes.