International Association
for Cryptologic Research

We prove the first meta-complexity characterization of a quantum cryptographic primitive. We show that one-way puzzles exist if and only if there is some quantum samplable distribution of binary strings over which it is hard to approximate Kolmogorov complexity. Therefore, we characterize one-way puzzles by the average-case hardness of a *uncomputable* problem. This brings to the quantum setting a recent line of work that characterizes classical cryptography with the average-case hardness of a meta-complexity problem (Liu-Pass (FOCS 2020), Ilango-Ren-Santhanam (STOC 2022) and others). Moreover, since the average-case hardness of Kolmogorov complexity over *classically* polynomial-time samplable distributions characterizes one-way functions, this result poses one-way puzzles as a natural generalization of one-way functions to the quantum setting. Furthermore, our equivalence goes through probability estimation, giving us the additional equivalence that one-way puzzles exist if and only if there is a quantum samplable distribution over which probability estimation is hard. We also observe that the oracle worlds of Kretschmer (TQC 2021) and Kretschmer, Qian, Sinha and Tal rule out any relativizing characterization of one-way puzzles by the hardness of a problem in NP or QMA, which means that it may not be possible with current techniques to characterize one-way puzzles with another meta-complexity problem.

A Random Oracle Combiner (ROC), introduced by Dodis et al. (CRYPTO ’22), takes two hash functions h_1, h_2 from m bits to n bits and outputs a new hash function C from m′ to n′ bits. This function C is guaranteed to be indifferentiable from a fresh random oracle as long as one of h1 and h_2 (say, h_1) is a random oracle, while the other (h_2) can “arbitrarily depend” on h_1. The work of Dodis et al. also built the first length-preserving ROC, where n′ = n. Unfortunately, despite this feasibility result, this construction has several deficiencies. From the practical perspective, it could not be directly applied to existing Merkle-Damgård-based hash functions, such as SHA2 or SHA3. From the theoretical perspective, it required h_1 and h_2 to have input length m > 3λ, where λ is the security parameter. To overcome these limitations, Dodis et al. conjectured — and left as the main open question — that the following (salted) construction is a length-preserving ROC: C_{h_1,h_2}^{Z_1,Z_2}(M ) = h_1^* (M, Z_1) ⊕ h_2^*(M, Z_2), where Z_1, Z_2 are random salts of appropriate length, and f^∗ denotes the Merkle-Damgård extension of a given compression function f. As our main result, we resolve this conjecture in the affirmative. For practical use, this makes the resulting combiner applicable to existing, Merkle-Damgård-based hash functions. On the theory side, it shows the existence of ROCs only requiring optimal input length m = λ + O(1).

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.