International Association
for Cryptologic Research

We show that the widely-used Schnorr signature scheme meets existential unforgeability under chosen-message attack (EUF-CMA) in the random oracle model (ROM) if the circular discrete-logarithm (CDL) assumption holds in the underlying group. CDL is a new, non-interactive and falsifiable variant of the discrete-logarithm (DL) assumption that we introduce. Our reduction is completely tight, meaning the constructed adversary against CDL has essentially the same running time and success probability as the assumed forger. This serves to justify the size of the underlying group for Schnorr signatures used in practice. To our knowledge, we are the first to exhibit such a reduction. Indeed, prior work required interactive and non-falsifiable assumptions (Bellare and Dai, INDOCRYPT 2020) or additional idealized models beyond the ROM like the algebraic group model (Fuchsbauer, Plouviez and Seurin, EUROCRYPT 2020). To further demonstrate the applicability of CDL, we show that Sparkle+ (Crites, Komlo and Maller, CRYPTO 2023), a threshold signing scheme for Schnorr, is tightly secure (under static corruptions) assuming CDL. Finally, we justify CDL by showing it holds in two carefully chosen idealized models that idealize different aspects of the assumption.

We initiate the study of the black-box complexity of private- key functional encryption (FE). Of central importance in the private-key setting is the inner-product functionality, which is currently only known from assumptions that imply public-key encryption, such as Decisional Diffie-Hellman or Learning-with-Errors. As our main result, we rule out black-box constructions of private-key inner-product FE from random oracles. This implies a black-box separation between private-key inner- product FE from all symmetric-key primitives implied by random oracles (e.g., symmetric-key encryption, collision-resistant hash functions). Proving lower bounds for private-key functional encryption schemes introduces challenges that were absent in prior works. In particular, the combinatorial techniques developed by prior works for proving black-box lower bounds are only useful in the public-key setting and predicate encryption settings, which all fail for the private-key FE case. Our work develops novel combinatorial techniques based on Fourier analysis to overcome these barriers. We expect these techniques to be widely useful in future research in this area.

Extending a line of work leveraging program obfuscation to instantiate random oracles (ROs) (\emph{e.g.}, Hohenberger \emph{et al.}, EUROCRYPT 2014, Kalai \emph{el al.}, CRYPTO 2017), we show that, using program obfuscation and other suitable assumptions, there exist standard-model hash functions that suffice to instantiate the classical RO-model encryption transforms OAEP (Bellare and Rogaway, EUROCRYPT 1994) and Fujisaki-Okamoto (EUROCRYPT 1998) under IND-CCA. Our result for Fujisaki-Okamoto employs a simple modification to the scheme that may be interesting for the current NIST PQC competition. For the most part, our instantiations do not require much stronger assumptions on the base schemes compared to their corresponding RO-model proofs. For example, to instantiate low-exponent RSA-OAEP, the assumption we need on RSA is sub-exponential partial one-wayness, matching the assumption on RSA needed by Fujisaki \emph{et al.} (J.~Cryptology 2004) in the RO model up to sub-exponentiality. Similarly, for the part of Fujisaki-Okamoto that upgrades indistinguishability under plaintext-checking to attack (OW-PCA) to IND-CCA, we again do not require much stronger assumptions up to sub-exponentiality. We obtain our hash functions in a unified way, extending a technique of Brzuska and Mittelbach (ASIACRYPT 2014). We incorporate into their technique: (1) extremely lossy functions (ELFs), a notion by Zhandry (CRYPTO 2016), and (2) \emph{multi-bit} auxiliary-input point function obfuscation (MB-AIPO). While MB-AIPO is impossible in general (Brzuska and Mittelbach, ASIACRYPT 2014), we give plausible constructions for the special cases we need, which may be of independent interest. We stress that our hash functions are not practical, but are meant to justify that when using the transforms in practice with cryptographic hashing, the end goal is plausible.

The generic-group model (GGM) has been very successful in making the analyses of many cryptographic assumptions and protocols tractable. It is, however, well known that the GGM is "uninstantiable," i.e., there are protocols secure in the GGM that are insecure when using any real-world group. This motivates the study of standard-model notions formalizing that a real-world group in some sense "looks generic." We introduce a standard-model definition called pseudo-generic group (PGG), where we require exponentiations with base an (initially) unknown group generator to result in random-looking group elements. In essence, our framework delicately lifts the influential notion of Universal Computational Extractors of Bellare, Hoang, and Keelveedhi (BHK, CRYPTO 2013) to a setting where the underlying ideal reference object is a generic group. The definition we obtain simultaneously generalizes the Uber assumption family, as group exponents no longer need to be polynomially induced. At the core of our definitional contribution is a new notion of algebraic unpredictability, which reinterprets the standard Schwartz-Zippel lemma as a restriction on sources. We prove the soundness of our definition in the GGM with auxiliary-input (AI-GGM). Our remaining results focus on applications of PGGs. We first show that PGGs are indeed a generalization of Uber. We then present a number of applications in settings where exponents are not polynomially induced. In particular we prove that simple variants of ElGamal meet several advanced security goals previously achieved only by complex and inefficient schemes. We also show that PGGs imply UCEs for split sources, which in turn are sufficient in several applications. As corollaries of our AI-GGM feasibility, we obtain the security of all these applications in the presence of preprocessing attacks. Some of our implications utilize a novel type of hash function, which we call linear-dependence destroyers (LDDs) and use to convert standard into algebraic unpredictability. We give an LDD for low-degree sources, and establish their plausibility for all sources by showing, via a compression argument, that random functions meet this definition.

Classically, selective-opening attack (SOA) has been studied for \emph{randomized} primitives, like randomized encryption schemes and commitments. The study of SOA for deterministic primitives, which presents some unique challenges, was initiated by Bellare \emph{et al.} (PKC 2015), who showed negative results. Subsequently, Hoang \emph{et al.} (ASIACRYPT 2016) showed positive results in the non-programmable random oracle model. Here we show the first positive results for SOA security of deterministic primitives in the \emph{standard} (RO devoid) model. Our results are: \begin{itemize} \item Any $2t$-wise independent hash function is SOA secure for an unbounded number of ``$t$-correlated'' messages, meaning any group of up to $t$ messages are arbitrarily correlated. \item A construction of a deterministic encryption scheme with analogous security, combining a regular lossy trapdoor function with a $2t$-wise independent hash function. \item The one-more-RSA problem of Bellare \emph{et al.} (J.~Cryptology 2003), which can be seen as a form of SOA, is hard under the $\Phi$-Hiding Assumption with large enough encryption exponent. \end{itemize} Somewhat surprisingly, the last result yields the first proof of RSA-based Chaum's blind signature scheme (CRYPTO 1982) based on a ``standard'' computational assumption. Notably, it avoids the impossibility result of Pass (STOC 2011) because lossiness of RSA endows the scheme with non-unique signatures.

We show new partial and full instantiation results under chosen-ciphertext security for the widely implemented and standardized RSA-OAEP encryption scheme of Bellare and Rogaway (EUROCRYPT 1994) and two variants. Prior work on such instantiations either showed negative results or settled for “passive” security notions like IND-CPA. More precisely, recall that RSA-OAEP adds redundancy and randomness to a message before composing two rounds of an underlying Feistel transform, whose round functions are modeled as random oracles (ROs), with RSA. Our main results are: Either of the two oracles (while still modeling the other as a RO) can be instantiated in RSA-OAEP under IND-CCA2 using mild standard-model assumptions on the round functions and generalizations of algebraic properties of RSA shown by Barthe, Pointcheval, and Báguelin (CCS 2012). The algebraic properties are only shown to hold at practical parameters for small encryption exponent ( $$e=3$$ ), but we argue they have value for larger e as well. Both oracles can be instantiated simultaneously for two variants of RSA-OAEP, called “ t -clear” and “ s -clear” RSA-OAEP. For this we use extractability-style assumptions in the sense of Canetti and Dakdouk (TCC 2010) on the round functions, as well as novel yet plausible “XOR-type” assumptions on RSA. While admittedly strong, such assumptions may nevertheless be necessary at this point to make positive progress. In particular, our full instantiations evade impossibility results of Shoup (J. Cryptology 2002), Kiltz and Pietrzak (EUROCRYPT 2009), and Bitansky et al. (STOC 2014). Moreover, our results for s -clear RSA-OAEP yield the most efficient RSA-based encryption scheme proven IND-CCA2 in the standard model (using bold assumptions on cryptographic hashing) to date.

The literature on leakage-resilient cryptography contains various leakage models that provide different levels of security. In the bounded leakage model (Akavia et al.—TCC 2009 ), it is assumed that there is a fixed upper bound L on the number of bits the attacker may leak on the secret key in the entire lifetime of the scheme. Alternatively, in the continual leakage model (Brakerski et al.—FOCS 2010 , Dodis et al.—FOCS 2010 ), the lifetime of a cryptographic scheme is divided into “time periods” between which the scheme’s secret key is updated. Furthermore, in its attack the adversary is allowed to obtain some bounded amount of leakage on the current secret key during each time period. In the continual leakage model, a challenging problem has been to provide security against leakage on key updates , that is, leakage that is a function of not only the current secret key but also the randomness used to update it. We propose a modular approach to overcome this problem based on program obfuscation. Namely, we present a compiler that transforms any public key encryption or signature scheme that achieves a slight strengthening of continual leakage resilience, which we call consecutive continual leakage resilience, to one that is continual leakage resilient with leakage on key updates, assuming indistinguishability obfuscation (Barak et al.—CRYPTO 2001 , Garg et al.—FOCS 2013 ). Under stronger forms of obfuscation, the leakage rate tolerated by our compiled scheme is essentially as good as that of the starting scheme. Our compiler is derived by making a connection between the problems of leakage on key updates and so-called sender-deniable encryption (Canetti et al.—CRYPTO 1997 ), which was recently constructed based on indistinguishability obfuscation by Sahai and Waters (STOC 2014 ). In the bounded leakage model, we give an approach to constructing leakage-resilient public key encryption from program obfuscation based on the public key encryption scheme of Sahai and Waters (STOC 2014 ). In particular, we achieve leakage-resilient public key encryption tolerating L bits of leakage for any L from $${\mathsf {iO}} $$ iO and one-way functions. We build on this to achieve leakage-resilient public key encryption with optimal leakage rate of $$1-o(1)$$ 1 - o ( 1 ) based on stronger forms of obfuscation and collision-resistant hash functions. Such a leakage rate is not known to be achievable in a generic way based on public key encryption alone. We then develop additional techniques to construct public key encryption that is (consecutive) continual leakage resilient under appropriate assumptions, which we believe is of independent interest.

We give a framework for trapdoor-permutation-based sequential aggregate signatures (SAS) that unifies and simplifies prior work and leads to new results. The framework is based on ideal ciphers over large domains, which have recently been shown to be realizable in the random oracle model. The basic idea is to replace the random oracle in the full-domain-hash signature scheme with an ideal cipher. Each signer in sequence applies the ideal cipher, keyed by the message, to the output of the previous signer, and then inverts the trapdoor permutation on the result. We obtain different variants of the scheme by varying additional keying material in the ideal cipher and making different assumptions on the trapdoor permutation. In particular, we obtain the first scheme with lazy verification and signature size independent of the number of signers that does not rely on bilinear pairings.Since existing proofs that ideal ciphers over large domains can be realized in the random oracle model are lossy, our schemes do not currently permit practical instantiation parameters at a reasonable security level, and thus we view our contribution as mainly conceptual. However, we are optimistic tighter proofs will be found, at least in our specific application.

Order-revealing encryption (ORE) is a primitive for outsourcing encrypted databases which allows for efficiently performing range queries over encrypted data. Unfortunately, a series of works, starting with Naveed et al. (CCS 2015), have shown that when the adversary has a good estimate of the distribution of the data, ORE provides little protection. In this work, we consider the case that the database entries are drawn identically and independently from a distribution of known shape, but for which the mean and variance are not (and thus the attacks of Naveed et al. do not apply). We define a new notion of security for ORE, called parameter-hiding ORE, which maintains the secrecy of these parameters. We give a construction of ORE satisfying our new definition from bilinear maps.