International Association for Cryptologic Research

International Association
for Cryptologic Research


Alexander Poremba


On the Two-sided Permutation Inversion Problem
Gorjan Alagic Chen Bai Alexander Poremba Kaiyan Shi
<p> In the permutation inversion problem, the task is to find the preimage of some challenge value, given oracle access to the permutation. This fundamental problem in query complexity appears in many contexts, particularly cryptography. In this work, we examine the setting in which the oracle allows for quantum queries to both the forward and the inverse direction of the permutation—except that the challenge value cannot be submitted to the latter. Within that setting, we consider three options for the inversion algorithm: whether it can get quantum advice about the permutation, whether the query algorithm can restrict the distribution with which the challenge input is sampled, and whether it must produce the entire preimage (search) or only the first bit (decision). We prove several theorems connecting the hardness of the resulting variations of the permutation inversion problem and establish lower bounds for them. Our results show that, perhaps surprisingly, the permutation inversion problem does not become significantly easier when the adversary is granted oracle access to the inverse—provided it cannot query the challenge itself. </p>
Quantum One-Wayness of the Single-Round Sponge with Invertible Permutations
Joseph Carolan Alexander Poremba
Sponge hashing is a novel class of cryptographic hash algorithms which underlies the current international hash function standard SHA3. In a nutshell, a sponge function takes as input a bit-stream of any length and processes it via a simple iterative procedure: it repeatedly feeds each block of the input into a so-called block function, and then produces a short digest which consists of a subset of the final output bits. While much is known about the post-quantum security of the sponge in the case when the block function is modeled as a random function or permutation, the case of invertible permutations has so far remained a fundamental open problem. In this work, we make new progress towards overcoming this barrier and show several results. First, we prove the ``double-sided zero-search'' conjecture proposed by Unruh (eprint' 2021) and show that finding zero-pairs in a random $2n$-bit permutation requires at least $\Omega(2^{n/2})$ many queries---and this is tight due to Grover's algorithm. At the core of our proof lies a novel ``symmetrization argument'' which uses insights from the theory of Young subgroups. Second, we consider more general variants of the double-sided search problem and show similar query lower bounds for them. As an application, we prove the quantum one-wayness of the single-round sponge with invertible permutations in the quantum random oracle model.
Publicly-Verifiable Deletion via Target-Collapsing Functions
James Bartusek Dakshita Khurana Alexander Poremba
This work re-examines the goal of building cryptosystems with publicly-verifiable deletion. We introduce target-collapsing as a weakening of collapsing, analogous to how second preimage resistance weakens collision resistance. That is, target-collapsing requires indistinguishability between superpositions and mixtures of preimages of an honestly sampled image. We show that target-collapsing hashes enable publicly-verifiable deletion, proving conjectures from [Poremba, ITCS'23] and demonstrating that the Dual-Regev encryption (and corresponding FHE) schemes support $\PVD$ under the learning with errors assumption. We build on this framework to obtain a variety of primitives supporting publicly-verifiable deletion ($\PVD$) from weak cryptographic assumptions, including: - Commitments with $\PVD$ assuming the existence of injective one-way functions, or more generally, {\em almost-regular} one-way functions. Along the way, we demonstrate that (partial) target-collapsing hashes can be built from almost-regular one-way functions. - Public-key encryption with $\PVD$ assuming trapdoored variants of injective (or almost-regular) one-way functions. - Public-key encryption with $\PVD$ assuming pseudorandom group actions, by demonstrating that the scheme of [Hhan, Morimae, and Yamakawa, Eurocrypt'23] has $\PVD$. - $X$ with $\PVD$ for $X \in \{$attribute-based encryption, quantum fully-homomorphic encryption, witness encryption, time-revocable encryption$\}$, assuming $X$ and trapdoored variants of injective (or almost-regular) one-way functions.
Weakening Assumptions for Publicly-Verifiable Deletion
We develop a simple compiler that generically adds publicly-verifiable deletion to a variety of cryptosystems. Our compiler only makes use of one-way functions (or one-way state generators, if we allow the public verification key to be quantum). Previously, similar compilers either relied on indistinguishability obfuscation along with any one-way function (Bartusek et. al., ePrint:2023/265), or on almost-regular one-way functions (Bartusek, Khurana and Poremba, CRYPTO 2023).
Revocable Cryptography from Learning with Errors
Quantum cryptography leverages many unique features of quantum information in order to construct cryptographic primitives that are oftentimes impossible classically. In this work, we build on the no-cloning principle of quantum mechanics and design cryptographic schemes with key-revocation capabilities. We consider schemes where secret keys are represented as quantum states with the guarantee that, once the secret key is successfully revoked from a user, they no longer have the ability to perform the same functionality as before. We define and construct several fundamental cryptographic primitives with key-revocation capabilities, namely pseudorandom functions, secret-key and public-key encryption, and even fully homomorphic encryption. Our constructions either assume the quantum subexponential hardness of the learning with errors problem or are based on new conjectures. Central to all our constructions is our approach for making the Dual-Regev encryption scheme (Gentry, Peikert and Vaikuntanathan, STOC 2008) revocable.