International Association
for Cryptologic Research

Abelian group actions appear in several areas of cryptography, especially isogeny-based post-quantum cryptography. A natural problem is to relate the analogues of the computational Diffie-Hellman (CDH) and discrete logarithm (DLOG) problems for abelian group actions. Galbraith, Panny, Smith and Vercauteren (Mathematical Cryptology '21) gave a quantum reduction of DLOG to CDH, assuming a CDH oracle with perfect correctness. Montgomery and Zhandry (Asiacrypt '22, best paper award) showed how to convert an unreliable CDH circuit into one that is correct with overwhelming probability. However, while a theoretical breakthrough, their reduction is quite inefficient: if the CDH oracle is correct with probability $q$ then their algorithm to amplify the success requires on the order of $1/q^{21}$ calls to the CDH oracle. We revisit this line of work and give a much simpler and tighter algorithm. Our method only takes on the order of $1/q^{4}$ CDH oracle calls and is much conceptually simpler than the Montgonery-Zhandry reduction. Our algorithm is also fully black-box, whereas the Montgomery-Zhandry algorithm is slightly non-black-box. Our main tool is a thresholding technique that replaces the comparison of distributions in Montgomery-Zhandry with testing equality of thresholded sets. We also give evidence that $1/q^{2}$ calls to the CDH oracle (or perhaps even more) is necessary, showing that it will be potentially difficult to substantially improve our method further.

A sequential function is, informally speaking, a function f for which a massively parallel adversary cannot compute "substantially" faster than an honest user with limited parallel computation power. Sequential functions form the backbone of many primitives that are extensively used in blockchains such as verifiable delay functions (VDFs) and time-lock puzzles. Despite this widespread practical use, there has been little work studying the complexity or theory of sequential functions. Our main result is a black-box oracle separation between sequential functions and one-way functions: in particular, we show the existence of an oracle O that implies a sequential function but not a one-way function. This seems surprising since sequential functions are typically constructed from very strong assumptions that imply one-way functions and also since time-lock puzzles are known to imply one-way functions (Bitansky et al., ITCS '16). We continue our exploration of the theory of sequential functions. We show that, informally speaking, the decisional, worst-case variant of a certain class of sequential function called a continuous iterative sequential function (CISF) is PSPACE-complete. A CISF is, in a nutshell, a sequential function f that can be written in the form f(k, x) = g^k (x) for some function g where k is an input determining the number of "rounds" the function is evaluated. We then show that more general forms of sequential functions are not contained in PSPACE relative to a random oracle. Given these results, we then ask if it is possible to build any interesting cryptographic primitives from sequential functions that are not one-way. It turns out that even if we assume just the existence of a CISF that is not one-way, we can build certain "fine-grained" cryptographic primitives where security is defined similarly to traditional primitives with the exception that it is only guaranteed for some (generally polynomial) amount of time. In particular, we show how to build "fine-grained" symmetric key encryption and "fine-grained" MACs from a CISF. We also show how to build fine-grained public-key encryption from a VDF with a few extra natural properties and indistinguishability obfucsation (iO) for null circuits. We do not assume one-way functions. Finally, we define a primitive that we call a commutative sequential function--essentially a sequential function that can be computed in sequence to get the same output in two different ways--and show that it implies fine-grained key exchange.

We construct a quantum money/quantum lightning scheme from class group actions on elliptic curves over F_p. Our scheme, which is based on the invariant money construction of Liu et al. (Eurocrypt '23), is simple to describe and we believe it to be the most instantiable and well-defined quantum money construction known so far. The security of our quantum lightning construction is exactly equivalent to the (conjectured) hardness of constructing two uniform superpositions over elliptic curves in an isogeny class which is acted on simply transitively by an exponentially large ideal class group. However, we needed to advance the state of the art of isogenies in order to achieve our scheme. In partcular, we show: An efficient (quantum) algorithm for sampling a uniform superposition over a cryptographically large isogeny class. A method for specifying polynomially many generators for the class group so that polynomial-sized products yield an exponential-sized subset of class group, modulo a seemingly very modest assumption. Achieving these results also requires us to advance the state of the art of the (pure) mathematics of elliptic curves, and we are optimistic that the mathematical tools we developed in this paper can be used to advance isogeny-based cryptography in other ways.

This work provides both negative and positive results for publicly verifiable quantum money. ** In the first part, we give a general theorem, showing that a certain natural class of quantum money schemes from lattices cannot be secure. We use this theorem to break the recent quantum money proposal of Khesin, Lu, and Shor. ** In the second part, we propose a framework for building quantum money and quantum lightning we call invariant money which abstracts and formalizes some ideas of quantum money from knots by Farhi et al.(ITCS'12) and its precedent work by Lutomirski et al.(ICS'10). In addition to formalizing this framework, we provide concrete hard computational problems loosely inspired by classical knowledge-of-exponent assumptions, whose hardness would imply the security of *quantum lightning*, a strengthening of quantum money where not even the bank can duplicate banknotes. ** We discuss potential instantiations of our framework, including an oracle construction using cryptographic group actions and instantiations from rerandomizable functional encryption, isogenies over elliptic curves, and knots.

Cryptographic group actions are a relaxation of standard cryptographic groups that have less structure. This lack of structure allows them to be plausibly quantum resistant despite Shor's algorithm, while still having a number of applications. The most famous example of group actions are built from isogenies on elliptic curves. Our main result is that CDH for abelian group actions is quantumly equivalent to discrete log. Galbraith et al. (Mathematical Cryptology) previously showed perfectly solving CDH to be equivalent to discrete log quantumly; our result works for any non-negligible advantage. We also explore several other questions about group action and isogeny protocols.

Algebraic structure lies at the heart of much of Cryptomania as we know it. An interesting question is the following: instead of building (Cryptomania) primitives from concrete assumptions, can we build them from simple Minicrypt primitives endowed with additional algebraic structure? In this work, we affirmatively answer this question by adding algebraic structure to the following Minicrypt primitives: One-Way Function (OWF) Weak Unpredictable Function (wUF) Weak Pseudorandom Function (wPRF) The algebraic structure that we consider is group homomorphism over the input/output spaces of these primitives. We also consider a “bounded” notion of homomorphism where the primitive only supports an a priori bounded number of homomorphic operations in order to capture lattice-based and other “noisy” assumptions. We show that these structured primitives can be used to construct many cryptographic protocols. In particular, we prove that: (Bounded) Homomorphic OWFs  (HOWFs) imply collision-resistant hash functions, Schnorr-style signatures and chameleon hash functions. (Bounded) Input-Homomorphic weak UFs  (IHwUFs) imply CPA-secure PKE, non-interactive key exchange, trapdoor functions, blind batch encryption (which implies anonymous IBE, KDM-secure and leakage-resilient PKE), CCA2 deterministic PKE, and hinting PRGs (which in turn imply transformation of CPA to CCA security for ABE/1-sided PE). (Bounded) Input-Homomorphic weak PRFs  (IHwPRFs) imply PIR, lossy trapdoor functions, OT and MPC (in the plain model). In addition, we show how to realize any CDH/DDH-based protocol with certain properties in a generic manner using IHwUFs/IHwPRFs, and how to instantiate such a protocol from many concrete assumptions. We also consider primitives with substantially richer structure, namely Ring IHwPRFs and L-composable IHwPRFs . In particular, we show the following: Ring IHwPRFs with certain properties imply FHE. 2-composable IHwPRFs imply (black-box) IBE, and L -composable IHwPRFs imply non-interactive $$(L+1)$$ ( L + 1 ) -party key exchange. Our framework allows us to categorize many cryptographic protocols based on which structured Minicrypt primitive implies them. In addition, it potentially makes showing the existence of many cryptosystems from novel assumptions substantially easier in the future.

We present a new framework for building round-optimal (two-round) adaptively secure MPC. We show that a relatively weak notion of OT that we call indistinguishability OT with receiver oblivious sampleability (r-iOT) is enough to build two-round, adaptively secure MPC against malicious adversaries in the CRS model. We then show how to construct r-iOT from CDH, LPN, or isogeny-based assumptions that can be viewed as group actions (such as CSIDH and CSI-FiSh). This yields the first concrete constructions of two-round adaptively secure MPC against malicious adversaries from CDH, LPN, or isogeny-based assumptions. We further extend our non-isogeny results to the plain model, achieving (to the best of our knowledge) the first construction of two-round adaptively secure MPC against semi-honest adversaries in the plain model from LPN. Our results allow us to build two-round adaptively secure MPC against malicious adversaries from essentially all of the well-studied assumptions in cryptography. In addition, our constructions from isogenies or LPN provide the first post-quantum alternatives to LWE-based constructions for round-optimal adaptively secure MPC. Along the way, we show that r-iOT also implies non-committing encryption (NCE), thereby yielding the first constructions of NCE from isogenies or LPN.

Isogeny-based assumptions have emerged as a viable option for quantum-secure cryptography. Recent works have shown how to build efficient (public-key) primitives from isogeny-based assumptions such as CSIDH and CSI-FiSh. However, in its present form, the landscape of isogenies does not seem very amenable to realizing new cryptographic applications. Isogeny-based assumptions often have unique efficiency and security properties, which makes building new cryptographic applications from them a potentially tedious and time-consuming task. In this work, we propose a new framework based on group actions that enables the easy usage of a variety of isogeny-based assumptions. Our framework generalizes the works of Brassard and Yung (Crypto'90) and Couveignes (Eprint'06). We provide new definitions for group actions endowed with natural hardness assumptions that model isogeny-based constructions amenable to group actions such as CSIDH and CSI-FiSh. We demonstrate the utility of our new framework by leveraging it to construct several primitives that were not previously known from isogeny-based assumptions. These include smooth projective hashing, dual-mode PKE, two-message statistically sender-private OT, and Naor-Reingold style PRF. These primitives are useful building blocks for a wide range of cryptographic applications. We introduce a new assumption over group actions called Linear Hidden Shift (LHS) assumption. We then present some discussions on the security of the LHS assumption and we show that it implies symmetric KDM-secure encryption, which in turn enables many other primitives that were not previously known from isogeny-based assumptions.

Algebraic structure lies at the heart of Cryptomania as we know it. An interesting question is the following: instead of building (Cryptomania) primitives from concrete assumptions, can we build them from simple Minicrypt primitives endowed with some additional algebraic structure? In this work, we affirmatively answer this question by adding algebraic structure to the following Minicrypt primitives:One-Way Function (OWF)Weak Unpredictable Function (wUF)Weak Pseudorandom Function (wPRF) The algebraic structure that we consider is group homomorphism over the input/output spaces of these primitives. We also consider a “bounded” notion of homomorphism where the primitive only supports an a priori bounded number of homomorphic operations in order to capture lattice-based and other “noisy” assumptions. We show that these structured primitives can be used to construct many cryptographic protocols. In particular, we prove that: (Bounded) Homomorphic OWFs (HOWFs) imply collision-resistant hash functions, Schnorr-style signatures and chameleon hash functions.(Bounded) Input-Homomorphic weak UFs (IHwUFs) imply CPA-secure PKE, non-interactive key exchange, trapdoor functions, blind batch encryption (which implies anonymous IBE, KDM-secure and leakage-resilient PKE), CCA2 deterministic PKE, and hinting PRGs (which in turn imply transformation of CPA to CCA security for ABE/1-sided PE).(Bounded) Input-Homomorphic weak PRFs (IHwPRFs) imply PIR, lossy trapdoor functions, OT and MPC (in the plain model). In addition, we show how to realize any CDH/DDH-based protocol with certain properties in a generic manner using IHwUFs/IHwPRFs, and how to instantiate such a protocol from many concrete assumptions.We also consider primitives with substantially richer structure, namely Ring IHwPRFs and L-composable IHwPRFs. In particular, we show the following: Ring IHwPRFs with certain properties imply FHE.2-composable IHwPRFs imply (black-box) IBE, and L-composable IHwPRFs imply non-interactive $$(L+1)$$ (L+1)-party key exchange. Our framework allows us to categorize many cryptographic protocols based on which structured Minicrypt primitive implies them. In addition, it potentially makes showing the existence of many cryptosystems from novel assumptions substantially easier in the future.

Securely managing encrypted data on an untrusted party is a challenging problem that has motivated the study of a wide variety of cryptographic primitives. A special class of such primitives allows an untrusted party to transform a ciphertext encrypted under one key to a ciphertext under another key, using some auxiliary information that does not leak the underlying data. Prominent examples of such primitives in the symmetric setting are key-homomorphic (weak) PRFs, updatable encryption, and proxy re-encryption. Although these primitives differ significantly in terms of their constructions and security requirements, they share two important properties: (a) they have secrets with structure or extra functionality, and (b) all known constructions of these primitives satisfying reasonably strong definitions of security are based on concrete public-key assumptions, e.g., DDH and LWE. This raises the question of whether these objects inherently belong to the world of public-key primitives, or they can potentially be built from simple symmetric-key objects such as pseudorandom functions. In this work, we show that the latter possibility is unlikely. More specifically, we show that:Any (bounded) key-homomorphic weak PRF with an abelian output group implies a (bounded) input-homomorphic weak PRF, which has recently been shown to imply not only public-key encryption  but also a variety of primitives such as PIR, lossy TDFs, and even IBE.Any ciphertext-independent updatable encryption scheme that is forward and post-compromise secure implies PKE. Moreover, any symmetric-key proxy re-encryption scheme with reasonably strong security guarantees implies a forward and post-compromise secure ciphertext-independent updatable encryption, and hence PKE. In addition, we show that unbounded (or exact) key-homomorphic weak PRFs over abelian groups are impossible in the quantum world. In other words, over abelian groups, bounded key-homomorphism is the best that we can hope for in terms of post-quantum security. Our attack also works over other structured primitives with abelian groups and exact homomorphisms, including homomorphic one-way functions and input-homomorphic weak PRFs.