## CryptoDB

### Recently updated IACR publications

CryptoDB is periodically updated by manual and automatic processes. Whenever a paper is added or modified it will appear in this list, e.g., when a video appears.

A separate history of changes tracks schema and process changes. There is further information about CryptoDB in the documentation.

**Year**

**Venue**

**Title**

2022

ASIACRYPT

SIDH Proof of Knowledge
Abstract

We show that the soundness proof for the De Feo--Jao--Plût identification scheme (the basis for supersingular isogeny Diffie--Hellman (SIDH) signatures) contains an invalid assumption, and we provide a counterexample for this assumption---thus showing the proof of soundness is invalid. As this proof was repeated in a number of works by various authors, multiple pieces of literature are affected by this result. Due to the importance of being able to prove knowledge of an SIDH key (for example, to prevent adaptive attacks), soundness is a vital property.
Surprisingly, the problem of proving knowledge of a specific isogeny turns out to be considerably more difficult than was perhaps anticipated.
The main results of this paper are a sigma protocol to prove knowledge of a walk of specified length in a supersingular isogeny graph, and a second one to additionally prove that the isogeny maps some torsion points to some other torsion points (as seen in SIDH public keys).
Our scheme also avoids the SIDH identification scheme soundness issue raised by Ghantous, Pintore and Veroni. In particular, our protocol provides a non-interactive way of verifying correctness of SIDH public keys, and related statements, as protection against adaptive attacks.
Post-scriptum: Some months after this work was completed and made public, the SIDH assumption was broken in a series of papers by several authors.
Hence, in the standard SIDH setting, some of the statements studied here now have trivial polynomial time non-interactive proofs.
Nevertheless our first sigma protocol is unaffected by the attacks, and our second protocol may still be useful in present and future variants of SIDH that escape the attacks.

2022

ASIACRYPT

The Abe-Okamoto Partially Blind Signature Scheme Revisited
Abstract

Partially blind signatures, an extension of ordinary blind signatures, are a primitive with wide applications in e-cash and electronic voting. One of the most efficient schemes to date is the one by Abe and Okamoto (CRYPTO 2000), whose underlying idea - the OR-proof technique - has served as the basis for several works.
We point out several subtle flaws in the original proof of security, and provide a new detailed and rigorous proof, achieving similar bounds as the original work. We believe our insights on the proof strategy will find useful in the security analyses of other OR-proof-based schemes.

2022

TCHES

One Truth Prevails: A Deep-learning Based Single-Trace Power Analysis on RSA–CRT with Windowed Exponentiation
Abstract

In this paper, a deep-learning based power/EM analysis attack on the state-of-the-art RSA–CRT software implementation is proposed. Our method is applied to a side-channel-aware implementation with the Gnu Multi-Precision (MP) Library, which is a typical open-source software library. Gnu MP employs a fixed-window exponentiation, which is the fastest in a constant time, and loads the entire precomputation table once to avoid side-channel leaks from multiplicands. To conduct an accurate estimation of secret exponents, our method focuses on the process of loading the entire precomputation table, which we call a dummy load scheme. It is particularly noteworthy that the dummy load scheme is implemented as a countermeasure against a simple power/EM analysis (SPA/SEMA). This type of vulnerability from a dummy load scheme also exists in other cryptographic libraries. We also propose a partial key exposure attack suitable for the distribution of errors inthe secret exponents recovered from the windowed exponentiation. We experimentally show that the proposed method consisting of the above power/EM analysis attack, as well as a partial key exposure attack, can be used to fully recover the secret key of the RSA–CRT from the side-channel information of a single decryption or a signature process.

2022

ASIACRYPT

Flashproofs: Efficient Zero-Knowledge Arguments of Range and Polynomial Evaluation with Transparent Setup
Abstract

We propose Flashproofs, a new type of efficient special honest verifier zero-knowledge arguments with a transparent setup in the discrete logarithm (DL) setting. First, we put forth gas-efficient range arguments that achieve $O(N^{\frac{2}{3}})$ communication cost, and involve $O(N^{\frac{2}{3}})$ group exponentiations for verification and a slightly sub-linear number of group exponentiations for proving with respect to the range $[0, 2^N-1]$, where $N$ is the bit length of the range. For typical confidential transactions on blockchain platforms supporting smart contracts, verifying our range arguments consumes only 237K and 318K gas for 32-bit and 64-bit ranges, which are comparable to 220K gas incurred by verifying the most efficient zkSNARK with a trusted setup (EUROCRYPT \textquotesingle 16) at present. Besides, the aggregation of multiple arguments can yield further efficiency improvement. Second, we present polynomial evaluation arguments based on the techniques of Bayer \& Groth (EUROCRYPT \textquotesingle 13). We provide two zero-knowledge arguments, which are optimised for lower-degree ($D \in [3, 2^9]$) and higher-degree ($D > 2^9$) polynomials, where $D$ is the polynomial degree. Our arguments yield a non-trivial improvement in the overall efficiency. Notably, the number of group exponentiations for proving drops from $8\log D$ to $3(\log D+\sqrt{\log D})$. The communication cost and the number of group exponentiations for verification decrease from $7\log D$ to $(\log D + 3\sqrt{\log D})$. To the best of our knowledge, our arguments instantiate the most communication-efficient arguments of membership and non-membership in the DL setting among those not requiring trusted setups. More importantly, our techniques enable a significantly asymptotic improvement in the efficiency of communication and verification (group exponentiations) from $O(\log D)$ to $O(\sqrt{\log D})$ when multiple arguments satisfying different polynomials with the same degree and inputs are aggregated.

2022

TCC

Beyond Uber: Instantiating Generic Groups via PGGs
Abstract

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.

2022

ASIACRYPT

Authenticated Encryption with Key Identification
Abstract

Authenticated encryption with associated data (AEAD) forms the core of much of symmetric cryptography, yet the standard techniques for modeling AEAD assume recipients have no ambiguity about what secret key to use for decryption. This is divorced from what occurs in practice, such as in key management services, where a message recipient can store numerous keys and must identify the correct key before decrypting. Ad hoc solutions for identifying the intended key are deployed in practice, but these techniques can be inefficient and, in some cases, have even led to practical attacks. Notably, to date there has been no formal investigation of their security properties or efficacy.
We fill this gap by providing the first formalization of nonce-based AEAD that supports key identification (AEAD-KI). Decryption now takes in a vector of secret keys and a ciphertext and must both identify the correct secret key and decrypt the ciphertext. We provide new formal security definitions, including new key robustness definitions and indistinguishability security notions. Finally, we show several different approaches for AEAD-KI and prove their security.

2022

ASIACRYPT

Non-interactive Mimblewimble transactions, revisited
Abstract

Mimblewimble is a cryptocurrency protocol that promises to overcome notorious blockchain scalability issues and provides user privacy. For a long time its wider adoption has been hindered by the lack of non-interactive transactions, that is, payments for which only the sender needs to be online.
Yu proposed a way of adding non-interactive transactions to stealth addresses to Mimblewimble, but this turned out to be flawed. Building on Yu and integrating ideas from Burkett, we give a fixed scheme and provide a rigorous security analysis strenghtening the previous security model from Eurocrypt'19.
Our protocol is considered for implementation by MimbleWimbleCoin and a variant is now deployed as MimbleWimble Extension Blocks (MWEB) in Litecoin.

2022

TCC

A Tight Computational Indistinguishability Bound of Product Distributions
Abstract

Assume that distributions X_0,X_1 (respectively Y_0,Y_1) are d_X (respectively d_Y) indistinguishable for circuits of a given size. It is well known that the product distributions X_0Y_0,X_1Y_1 are d_X+d_Y indistinguishable for slightly smaller circuits. However, in probability theory where unbounded adversaries are considered through statistical distance, it is folklore knowledge that in fact X_0Y_0 and X_1Y_1 are d_x+d_y-d_x*d_y indistinguishable, and also that this bound is tight.
We formulate and prove the computational analog of this tight bound. Our proof is entirely different from the proof in the statistical case, which is non-constructive. As a corollary, we show that if X and Y are d indistinguishable, then k independent copies of X and k independent copies of Y are almost 1-(1-d)^k indistinguishable for smaller circuits, as against d*k using the looser bound. Our bounds are useful in settings where only weak (i.e. non-negligible) indistinguishability is guaranteed. We demonstrate this in the context of cryptography, showing that our bounds yield simple analysis for amplification of weak oblivious transfer protocols.

2022

ASIACRYPT

Encryption to the Future A Paradigm for Sending Secret Messages to Future (Anonymous) Committees
Abstract

A number of recent works have constructed cryptographic protocols with flavors of adaptive security by having a randomly-chosen anonymous committee run at each round. Since most of these protocols are stateful, transferring secret states from past committees to future, but still unknown, committees is a crucial challenge. Previous works have tackled this problem with approaches tailor-made for their specific setting, which mostly rely on using a blockchain to orchestrate auxiliary committees that aid in the state hand-over process. In this work, we look at this challenge as an important problem on its own and initiate the study of Encryption to the Future (EtF) as a cryptographic primitive. First, we define a notion of an EtF scheme where time is determined with respect to an underlying blockchain and a lottery selects parties to receive a secret message at some point in the future. While this notion seems overly restrictive, we establish two important facts: 1. if used to encrypt towards parties selected in the “far future”, EtF implies witness encryption for NP over a blockchain; 2. if used to encrypt only towards parties selected in the “near future”, EtF is not only sufficient for transferring state among committees as required by previous works, but also captures previous tailor-made solutions. To corroborate these results, we provide a novel construction of EtF based on witness encryption over commitments (cWE), which we instantiate from a number of standard assumptions via a construction based on generic cryptographic primitives. Finally, we show how to use “near future” EtF to obtain “far future” EtF with a protocol based on an auxiliary committee whose communication complexity is independent of the length of plaintext messages being sent to the future.

2022

TCC

Bet-or-Pass: Adversarially Robust Bloom Filters
Abstract

A Bloom filter is a data structure that maintains a succinct and probabilistic representation of a set of elements from a universe. It supports approximate membership queries. The price of the succinctness is allowing some error, namely false positives: for any element not in the set, it might answer `Yes' but with a small (non-negligible) probability.
When dealing with such data structures in adversarial settings, we need to define the correctness guarantee and formalize the requirement that bad events happen infrequently and those false positives are appropriately distributed. Recently, several papers investigated this topic, suggesting different robustness definitions.
In this work, we try to unify this line of research and propose several robustness notions for Bloom filters that allow the adaptivity of queries. The goal is that a robust Bloom filter should behave like a random biased coin even against an adaptive adversary. The robustness definitions are formalized by the type of test the Bloom filter should withstand. We then explore the relationships between these notions and highlight the notion of Bet-or-Pass as capturing the desired properties of such a data structure.

2022

ASIACRYPT

Triply Adaptive UC NIZK
Abstract

Non-interactive zero knowledge (NIZK) enables a prover, to prove that a statement in an NP
language is valid, given an accepting witness, without leaking any information about the witness. We study universally composable (UC) NIZKs which are secure against adaptive corruption of parties and provides adaptive soundness, i.e. the statement is adaptively chosen by a malicious prover based on the setup string distribution. The only known adaptively secure NIZK protocols either fail to achieve full adaptive soundness or rely on non-falsifiable knowledge assumptions. We construct the first NIZK protocols which are triply adaptive - secure against adaptive corruptions, guarantees adaptive soundness and satisfies adaptive zero knowledge, from falsifiable assumptions. We do so using the following methodology:
- We define a new ideal functionality, denoted as F_NICOM, for non-interactive commitment schemes in the UC framework.
- We define and construct Sigma protocols which satisfy triply adaptive security in the F_NICOM model.
- By relying on correlation intractable (CI) hash functions, we compile a triply adaptively secure Sigma protocol (in F_NICOM model) into a triply adaptive UC-NIZK argument in the F_NICOM+common reference string (crs) model.
In addition to CI hash functions, our compiler requires standard cryptographic primitives - non-interactive equivocal commitments and public key encryption with obliviously samplable ciphertexts, for implementing F_NICOM in the crs model. We instantiate our framework by demonstrating that most statically secure Sigma protocols can be proven to be triply adaptively secure in the F_NICOM model, hence, bridging the gap between static and adaptive security for NIZKs. Our NIZK arguments can be concretely based on assumptions, like LWE, or LPN and DDH.

2022

TCC

Universally Composable Sigma-protocols in the Global Random-Oracle Model
Abstract

Numerous cryptographic applications require efficient non-interactive zero-knowledge proofs of knowledge (NIZKPoK) as a building block. Typically they rely on the Fiat-Shamir heuristic to do so, as security in the random-oracle model is considered good enough in practice. However, there is a troubling disconnect between the stand-alone security of such a protocol and its security as part of a larger, more complex system where several protocols may be running at the same time. Provable security in the general universal composition model (GUC model) of Canetti et al. is the best guarantee that nothing will go wrong when a system is part of a larger whole, even when all parties share a common random oracle. In this paper, we prove the minimal necessary properties of generally universally composable (GUC) NIZKPoK in any global random-oracle model, and show how to achieve efficient and GUC NIZKPoK in both the restricted programmable and restricted observable (non-programmable) global random-oracle models.

2022

ASIACRYPT

An Analysis of the Algebraic Group Model
Abstract

The algebraic group model (AGM), formalized by Fuchsbauer, Kiltz, and Loss, has recently received significant attention. One of the appealing properties of the AGM is that it is viewed as being (strictly) weaker than the generic group model (GGM), in the sense that hardness results for algebraic algorithms imply hardness results for generic algorithms, and generic reductions in the AGM (namely, between the algebraic formulations of two problems) imply generic reductions in the~GGM. We highlight that as the GGM and AGM are currently formalized, this is not true: hardness in the AGM may not imply hardness in the GGM, and a generic reduction in the AGM may not imply a similar reduction in the~GGM.

2022

ASIACRYPT

Enhancing Differential-Neural Cryptanalysis
Abstract

In CRYPTO 2019, Gohr shows that well-trained neural networks can perform cryptanalytic distinguishing tasks superior to traditional differential distinguishers. Moreover, applying an unorthodox key guessing strategy, an 11-round key-recovery attack on a modern block cipher Speck32/64 improves upon the published state-of-the-art result. This calls into the next questions. To what extent is the advantage of machine learning (ML) over traditional methods, and whether the advantage generally exists in the cryptanalysis of modern ciphers? To answer the first question, we devised ML-based key-recovery attacks on more extended round-reduced Speck32/64. We achieved an improved 12-round and the first practical 13-round attacks. The essential for the new results is enhancing a classical component in the ML-based attacks, that is, the neutral bits. To answer the second question, we produced various neural distinguishers on round-reduced Simon32/64 and provided comparisons with their pure differential-based counterparts.

2022

ASIACRYPT

Towards Case-Optimized Hybrid Homomorphic Encryption -Featuring the Elisabeth Stream Cipher-
Abstract

Hybrid Homomorphic Encryption (HHE) reduces the amount of computation client-side and bandwidth usage in a Fully Homomorphic Encryption (FHE) framework. HHE requires the usage of specific symmetric schemes that can be evaluated homomorphically efficiently. In this paper, we introduce the paradigm of Group Filter Permutator (GFP) as a generalization of the Improved Filter Permutator paradigm introduced by M ́eaux et al. From this paradigm, we specify Elisabeth , a family of stream cipher and give an instance: Elisabeth-4. After proving the security of this scheme, we provide a Rust implementation of it and ensure its performance is comparable to state-of-the-art HHE. The true strength of Elisabeth lies in the available operations server-side: while the best HHE applications were limited to a few multiplications server-side, we used data sent through Elisabeth-4 to homomorphically evaluate a neural network inference. Finally, we discuss the improvement and loss between the HHE and the FHE framework and give ideas to build more efficient schemes from the Elisabeth family.

2022

ASIACRYPT

EvalRound Algorithm in CKKS Bootstrapping
Abstract

Homomorphic encryption (HE) has open an entirely new world up in the privacy-preserving use of sensitive data by conducting computations on encrypted data. Amongst many HE schemes targeting on computation in various contexts, Cheon--Kim--Kim--Song (CKKS) scheme is distinguished since it allows computations for encrypted real number data, which have greater impact in real-world applications.
CKKS scheme is a levelled homomorphic encryption scheme, consuming one level for each homomorphic multiplication. When the level runs out, a special computational circuit called bootstrapping is required in order to conduct further multiplications. The algorithm proposed by Cheon et al. has been regarded as a standard way to do bootstrapping in the CKKS scheme, and it consists of the following four steps: ModRaise, CoeffToSlot, EvalMod and SlotToCoeff. However, the steps consume a number of levels themselves, and thus optimizing this extra consumption has been a major focus of the series of recent research.
Among the total levels consumed in the bootstrapping steps, about a half of them is spent in CoeffToSlot and SlotToCoeff steps to scale up the real number components of DFT matrices and round them to the nearest integers. Each scale-up factor is very large so that it takes up one level to rescale it down. Scale-up factors can be taken smaller to save levels, but the error of rounding would be transmitted to EvalMod and eventually corrupt the accuracy of bootstrapping.
EvalMod aims to get rid of the superfluous $qI$ term from a plaintext $\pt + qI$ resulting from ModRaise, where $q$ is the bottom modulus and $I$ is a polynomial with small integer coefficients. EvalRound is referred to as its opposite, obtaining $qI$. We introduce a novel bootstrapping algorithm consisting of ModRaise, CoeffToSlot, EvalRound and SlotToCoeff, which yields taking smaller scale-up factors without the damage of rounding errors.

2022

ASIACRYPT

A Universally Composable Non-Interactive Aggregate Cash System
Abstract

Mimblewimble is a privacy-preserving cryptocurrency, providing the functionality of transaction aggregation. Once certain coins have been spent in Mimblewimble, they can be deleted from the UTXO set. This is desirable: now storage can be saved and computation cost can be reduced. Fuchsbauer et al. (EUROCRYPT 2019) abstracted Mimblewimble as an Aggregate Cash System (ACS) and provided security analysis via game-based definitions.
In this paper, we revisit the ACS, and focus on {\em Non-interactive} ACS, denoted as NiACS. We for the first time propose a simulation-based security definition and formalize an ideal functionality for NiACS. Then, we construct a NiACS protocol in a hybrid model which can securely realize the ideal NiACS functionality in the Universal Composition (UC) framework. In addition, we propose a building block, which is a variant of the ElGamal encryption scheme that may be of independent interest. Finally, we show how to instantiate our protocol, and obtain the first NiACS system with UC security.

2022

ASIACRYPT

On Secure Ratcheting with Immediate Decryption
Abstract

Ratcheting protocols let parties securely exchange messages in environments in which state exposure attacks are anticipated. While, unavoidably, some promises on confidentiality and authenticity cannot be upheld once the adversary obtains a copy of a party's state, ratcheting protocols aim at confining the impact of state exposures as much as possible. In particular, such protocols provide forward security (after state exposure, past messages remain secure) and post-compromise security (after state exposure, participants auto-heal and regain security).
Ratcheting protocols serve as core components in most modern instant messaging apps, with billions of users per day. Most instances, including Signal, guarantee immediate decryption (ID): Receivers recover and deliver the messages wrapped in ciphertexts immediately when they become available, even if ciphertexts arrive out-of-order and preceding ciphertexts are still missing. This ensures the continuation of sessions in unreliable communication networks, ultimately contributing to a satisfactory user experience. While initial academic treatments consider ratcheting protocols without ID, Alwen et al (EC'19) propose the first ID-aware security model, together with a provably secure construction. Unfortunately, as we note, in their protocol a receiver state exposure allows for the decryption of all prior undelivered ciphertexts. As a consequence, from an adversary's point of view, intentionally preventing the delivery of a fraction of the ciphertexts of a conversation, and corrupting the receiver (days) later, allows for correctly decrypting all suppressed ciphertexts. The same attack works against Signal.
We argue that the level of (forward-)security realized by the protocol of Alwen et al, and mandated by their security model, is considerably lower than both intuitively expected and technically possible. The main contributions of our work are thus a careful revisit of the security notions for ratcheted communication in the ID setting, together with a provably secure proof-of-concept construction. One novel component of our model is that it reflects the progression of physical time. This allows for formally requiring that (undelivered) ciphertexts automatically expire after a configurable amount of time.

2022

ASIACRYPT

Horizontal racewalking using radical isogenies
Abstract

We address three main open problems concerning the use of radical isogenies, as presented by Castryck, Decru and Vercauteren at Asiacrypt 2020, in the computation of long chains of isogenies of fixed, small degree between elliptic curves over finite fields. Firstly, we present an interpolation method for finding radical isogeny formulae in a given degree N, which by-passes the need for factoring division polynomials over large function fields. Using this method, we are able to push the
range for which we have formulae at our disposal from N ≤ 13 to N ≤ 37. Secondly, using a combination of known techniques and ad-hoc manipulations, we derived optimized versions of these formulae for N ≤ 19, with some instances performing more than twice as fast as their counterparts from 2020. Thirdly, we solve the problem of understanding the correct choice of radical when walking along the surface between supersingular elliptic curves over Fp with p ≡ 7 mod 8; this is non-trivial for even N and was only settled for N = 4 by Onuki and Moriya at PKC 2022. We give a conjectural statement for all even N and prove it for N ≤ 14. The speed-ups obtained from these techniques are substantial: using 16-isogenies, the computation of long chains of 2-isogenies over 512-bit prime fields can be improved by a factor 3, and the previous implementation of CSIDH using radical isogenies can be sped up by about 12%.

2022

ASIACRYPT

SwiftEC: Shallue--van de Woestijne Indifferentiable Function to Elliptic Curves
Abstract

Hashing arbitrary values to points on an elliptic curve is a required
step in many cryptographic constructions, and a number of techniques have
been proposed to do so over the years. One of the first ones was due to
Shallue and van de Woestijne (ANTS-VII), and it had the interesting
property of applying to essentially all elliptic curves over finite
fields. It did not, however, have the desirable property of being
*indifferentiable from a random oracle* when composed with a random
oracle to the base field.
Various approaches have since been considered to overcome this
limitation, starting with the foundational work of Brier et al. (CRYPTO
2011). For example, if f: F_q→E(F_q) is the Shallue--van de
Woestijne (SW) map and H, H' are *two* independent random oracles,
we now know that m↦f(H(m))+f(H'(m)) is
indifferentiable from a random oracle. Unfortunately, this approach has
the drawback of being twice as expensive to compute than the
straightforward, but not indifferentiable, m↦f(H(m)).
Most other solutions so far have had the same issue: they are at least as
costly as two base field exponentiations, whereas plain encoding maps
like f cost only one exponentiation. Recently, Koshelev (DCC 2022)
provided the first construction of indifferentiable hashing at the cost
of one exponentiation, but only for a very specific class of curves
(some of those with j-invariant 0), and using techniques that are unlikely to
apply more broadly.
In this work, we revisit this long-standing open problem, and observe
that the SW map actually fits in a one-parameter family (f_u)_{u∈F_q}
of encodings, such that for independent random oracles H, H',
F: m↦f_{H'(m)}(H(m)) is indifferentiable. Moreover, on a
very large class of curves (essentially those that are either of odd
order or of order divisible by 4), the one-parameter family admits a
rational parametrization, which lets us compute F at almost the same
cost as small f, and finally achieve indifferentiable hashing to most
curves with a single exponentiation.
Our new approach also yields an improved variant of the Elligator Squared
technique of Tibouchi (FC 2014) that represents points of arbitrary
elliptic curves as close-to-uniform random strings.

2022

TCC

Asymptotically Free Broadcast in Constant Expected Time via Packed VSS
Abstract

Broadcast is an essential primitive for secure computation. We focus in this paper on optimal resilience (i.e., when the number of corrupted parties $t$ is less than a third of the computing parties $n$), and with no setup or cryptographic assumptions.
While broadcast with worst case $t$ rounds is impossible, it has been shown [Feldman and Micali STOC'88, Katz and Koo CRYPTO'06] how to construct protocols with expected constant number of rounds in the private channel model. However, those constructions have large communication complexity, specifically $\bigO(n^2L+n^6\log n)$ expected number of bits transmitted for broadcasting a message of length $L$. This leads to a significant communication blowup in secure computation protocols in this setting.
In this paper, we substantially improve the communication complexity of broadcast in constant expected time. Specifically, the expected communication complexity of our protocol is $\bigO(nL+n^4\log n)$. For messages of length $L=\Omega(n^3 \log n)$, our broadcast has no asymptotic overhead (up to expectation), as each party has to send or receive $\bigO(n^3 \log n)$ bits. We also consider parallel broadcast, where $n$ parties wish to broadcast $L$ bit messages in parallel. Our protocol has no asymptotic overhead for $L=\Omega(n^2\log n)$, which is a common communication pattern in perfectly secure MPC protocols. For instance, it is common that all parties share their inputs simultaneously at the same round, and verifiable secret sharing protocols require the dealer to broadcast a total of $\bigO(n^2\log n)$ bits.
As an independent interest, our broadcast is achieved by a \emph{packed verifiable secret sharing}, a new notion that we introduce. We show a protocol that verifies $\bigO(n)$ secrets simultaneously with the same cost of verifying just a single secret. This improves by a factor of $n$ the state-of-the-art.

2022

ASIACRYPT

Zero-Knowledge Protocols for the Subset Sum Problem from MPC-in-the-Head with Rejection
Abstract

We propose (honest verifier) zero-knowledge arguments for the modular subset sum problem. Previous combinatorial approaches, notably one due to Shamir, yield arguments with cubic communication complexity (in the security parameter). More recent methods, based on the MPC-in-the-head technique, also produce arguments with cubic communication complexity.
We improve this approach by using a secret-sharing over small integers (rather than modulo q) to reduce the size of the arguments and remove the prime modulus restriction. Since this sharing may reveal information on the secret subset, we introduce the idea of rejection to the MPC-in-the-head paradigm. Special care has to be taken to balance completeness and soundness and preserve zero-knowledge of our arguments. We combine this idea with two techniques to prove that the secret vector (which selects the subset) is well made of binary coordinates.
Our new protocols achieve an asymptotic improvement by producing arguments of quadratic size. This improvement is also practical: for a 256-bit modulus q, the best variant of our protocols yields 13KB arguments while previous proposals gave 1180KB arguments, for the best general protocol, and 122KB, for the best protocol restricted to prime modulus. Our techniques can also be applied to vectorial variants of the subset sum problem and in particular the inhomogeneous short integer solution (ISIS) problem for which they provide an efficient alternative to state-of-the-art protocols when the underlying ring is not small and NTT-friendly. We also show the application of our protocol to build efficient zero-knowledge arguments of plaintext and/or key knowledge in the context of fully-homomorphic encryption. When applied to the TFHE scheme, the obtained arguments are more than 20 times smaller than those obtained with previous protocols. Eventually, we use our technique to construct an efficient digital signature scheme based on a pseudo-random function due to Boneh, Halevi, and Howgrave-Graham.

2022

ASIACRYPT

Exploring SAT for Cryptanalysis: (Quantum) Collision Attacks against 6-Round SHA-3
Abstract

In this work, we focus on collision attacks against instances of \shac hash family in both classical and quantum settings.
Since the 5-round collision attacks on \shacc-256 and other variants proposed by Guo \etal at JoC~2020, no other essential progress has been published.
With a thorough investigation, we identify that the challenges of extending such collision attacks on \shac to more rounds lie in the inefficiency of differential trail search.
To overcome this obstacle, we develop a \sat automatic search toolkit. The tool is used in multiple intermediate steps of the collision attacks and exhibits surprisingly high efficiency in differential trail search and other optimization problems encountered in the process.
As a result, we present the first 6-round classical collision attack on \shakea with time complexity \cpshake, which also forms a quantum collision attack with quantum time \cpshakeq, and the first 6-round quantum collision attack on \shacc-224 and \shacc-256 with quantum time \cpshattf and \cpshatfs, where $S$ represents the hardware resources of the quantum computer.
The fact that classical collision attacks do not apply to 6-round \shacc-224 and \shacc-256 shows the higher coverage of quantum collision attacks, which is consistent with that on SHA-2 observed by Hosoyamada and Sasaki at CRYPTO~2021.

2022

ASIACRYPT

Stretching Cube Attacks: Improved Methods to Recover Massive Superpolies
Abstract

Cube attacks exploit the algebraic properties of symmetric ciphers by recovering a special polynomial, the superpoly, and subsequently the secret key. When the algebraic normal forms of the corresponding Boolean functions are not available, the division property based approach allows to recover the exact superpoly in a clever way. However, the computational cost to recover the superpoly becomes prohibitive as the number of rounds of the cipher increases. For example, the nested monomial predictions (NMP) proposed at ASIACRYPT 2021 stuck at round 845 for \trivium. To alleviate the bottleneck of the NMP technique, i.e., the unsolvable model due to the excessive number of monomial trails, we shift our focus to the so-called valuable terms of a specific middle round that contribute to the superpoly. Two new techniques are introduced, namely, Non-zero Bit-based Division Property (NBDP) and Core Monomial Prediction (CMP), both of which result in a simpler MILP model compared to the MILP model of MP. It can be shown that the CMP technique offers a substantial improvement over the monomial prediction technique in terms of computational complexity of recovering valuable terms. Combining the divide-and-conquer strategy with these two new techniques, we catch the valuable terms more effectively and thus avoid wasting computational resources on intermediate terms contributing nothing to the superpoly. As an illustration of the power of our techniques, we apply our framework to \trivium, \grain, \kreyvium and \acorn. As a result, the computational cost of earlier attacks can be significantly reduced and the exact ANFs of the superpolies for 846-, 847- and 848-round \trivium, 192-round \grain, 895-round \kreyvium and 776-round \acorn can be recovered in practical time, even though the superpoly of 848-round \trivium contains over 500 million terms; this corresponds to respectively 3, 1, 1 and 1 rounds more than the previous best results. Moreover, by investigating the internal properties of M\"obius transformation, we show how to perform key recovery using superpolies involving full key bits, which leads to the best key recovery attacks on the targeted ciphers.

2022

ASIACRYPT

A Non-heuristic Approach to Time-space Tradeoffs and Optimizations for BKW
Abstract

Blum, Kalai and Wasserman (JACM 2003) gave the first sub-exponential algorithm to solve the Learning Parity with Noise (LPN) problem. In particular, consider the LPN problem with constant noise and dimension $n$. The BKW solves it with space complexity $2^{\frac{(1+\epsilon)n}{\log n}}$ and time/sample complexity $2^{\frac{(1+\epsilon)n}{\log n}}\cdot 2^{\Omega(n^{\frac{1}{1+\epsilon}})}$ for small constant $\epsilon\to 0^+$.
We propose a variant of the BKW by tweaking Wagner's generalized birthday problem (Crypto 2002) and adapting the technique to a $c$-ary tree structure. In summary, our algorithm achieves the following:
\begin{enumerate}
\item {\bf (Time-space tradeoff).} We obtain the same time-space tradeoffs for LPN and LWE as those given by Esser et al. (Crypto 2018), but without resorting to any heuristics. For any $2\leq c\in\mathbb{N}$, our algorithm solves the LPN problem with time complexity $2^{\frac{\log c(1+\epsilon)n}{\log n}}\cdot 2^{\Omega(n^{\frac{1}{1+\epsilon}})}$ and space complexity $2^{\frac{\log c(1+\epsilon)n}{(c-1)\log n}}$, where one can use Grover's quantum algorithm or Dinur et al.'s dissection technique (Crypto 2012) to further accelerate/optimize the time complexity.
\item {\bf (Time/sample optimization).}
A further adjusted variant of our algorithm solves the LPN problem with sample, time and space complexities all kept at $2^{\frac{(1+\epsilon)n}{\log n}}$ for $\epsilon\to 0^+$, saving factor $2^{\Omega(n^{\frac{1}{1+\epsilon}})}$ in time/sample compared to the original BKW, and the variant of Devadas et al. (TCC 2017).
\item {\bf (Sample reduction).} Our algorithm provides an alternative to Lyubashevsky's BKW variant (RANDOM 2005) for LPN with a restricted amount of samples. In particular, given $Q=n^{1+\epsilon}$ (resp., $Q=2^{n^{\epsilon}}$) samples, our algorithm saves a factor of $2^{\Omega(n)/(\log n)^{1-\kappa}}$ (resp., $2^{\Omega(n^{\kappa})}$) for constant $\kappa \to 1^-$ in running time while consuming roughly the same space, compared with Lyubashevsky's algorithm.
\end{enumerate}
In particular, the time/sample optimization benefits from a careful analysis of the error distribution among the correlated candidates, which was not studied by previous rigorous approaches such as the analysis of Minder and Sinclair (J.Cryptology 2012) or Devadas et al. (TCC 2017).

2022

ASIACRYPT

Memory-Tight Multi-Challenge Security of Public-Key Encryption
Abstract

We give the first examples of public-key encryption schemes which can be proven to achieve multi-challenge, multi-user CCA security via reductions that are tight in time, advantage, and memory. Our constructions are obtained by applying the KEM-DEM paradigm to variants of Hashed ElGamal and the Fujisaki-Okamoto transformation that are augmented by adding uniformly random strings to their ciphertexts. The reductions carefully combine recent proof techniques introduced by Bhattacharyya'20 and Ghoshal-Ghosal-Jaeger-Tessaro'22. Our proofs for the augmented ECIES version of Hashed-ElGamal make use of a new computational Diffie-Hellman assumption wherein the adversary is given access to a pairing to a random group, which we believe may be of independent interest.

2022

ASIACRYPT

Linear-map Vector Commitments and their Practical Applications
Abstract

Vector commitments (VC) are a cryptographic primitive that allow one to commit to a vector and then “open” some of its positions efficiently. Vector commitments are increasingly recognized as a central tool to scale highly decentralized networks of large size and whose content is dynamic. In this work, we examine the demands on the properties that an ideal vector commitment should satisfy in the light of the emerging plethora of practical applications and propose new constructions that improve the state-of-the-art in several dimensions and offer new tradeoffs. We also propose a unifying framework that captures several constructions and show how to generically achieve some properties from more basic ones.

2022

ASIACRYPT

Concurrently Composable Non-Interactive Secure Computation
Abstract

We consider the feasibility of non-interactive secure two-party computation (NISC) in the plain model satisfying the notion of superpolynomial-time simulation (SPS). While stand-alone secure SPS-NISC protocols are known from standard assumptions (Badrinarayanan et al., Asiacrypt 2017), it has remained an open problem to construct a concurrently composable SPS-NISC.
Prior to our work, the best protocols require 5 rounds (Garg et al., Eurocrypt 2017), or 3 simultaneous-message rounds (Badrinarayanan et al., TCC 2017).
In this work, we demonstrate the first concurrently composable SPS-NISC. Our construction assumes the existence of:
* a non-interactive (weakly) CCA-secure commitment,
* a stand-alone secure SPS-NISC with subexponential security,
and satisfies the notion of “angel-based” UC security (i.e., UC with a superpolynomial-time helper) with perfect correctness.
We additionally demonstrate that both of the primitives we use (albeit only with polynomial security) are necessary for such concurrently composable SPS-NISC with perfect correctness. As such, our work identifies essentially necessary and sufficient primitives for concurrently composable SPS-NISC with perfect correctness in the plain model.

2022

ASIACRYPT

GUC-Secure Commitments via Random Oracles: New Impossibility and Feasibility
Abstract

In the UC framework, protocols must be subroutine respecting; therefore, shared trusted setup might cause security issues. To address this drawback, Generalized UC (GUC) framework is introduced by Canetti {\em et al.} (TCC 2007).
In this work, we investigate the impossibility and feasibility of GUC-secure commitments using global random oracles (GRO) as the trusted setup. In particular, we show that it is impossible to have a 2-round (1-round committing and 1-round opening) GUC-secure commitment in the global observable RO model by Canetti {\em et al.} (CCS 2014). We then give a new round-optimal GUC-secure commitment that uses only Minicrypt assumptions (i.e. the existence of one-way functions) in the global observable RO model. Furthermore, we also examine the complete picture on round complexity of the GUC-secure commitments in various global RO models.

2022

ASIACRYPT

A Modular Approach to the Security Analysis of Two-Permutation Constructions
Abstract

Constructions based on two public permutation calls are very common in today's cryptographic community. However, each time a new construction is introduced, a dedicated proof must be carried out to study the security of the construction. In this work, we propose a new tool to analyze the security of these constructions in a modular way. This tool is built on the idea of the classical mirror theory for block cipher based constructions, such that it can be used for security proofs in the ideal permutation model. We present different variants of this public permutation mirror theory such that it is suitable for different security notions.
We also present a framework to use the new techniques, which provides the bad events that need to be excluded in order to apply the public permutation mirror theory. Furthermore, we showcase the new technique on three examples: the Tweakable Even-Mansour cipher by Cogliati et al. (CRYPTO '15), the two permutation variant of the pEDM PRF by Dutta et al. (ToSC '21(2)), and the two permutation variant of the nEHtM_p MAC algorithm by Dutta and Nandi (AFRICACRYPT '20). With this new tool we prove the multi-user security of these constructions in a considerably simplified way.

2022

TCC

Quantum Rewinding for Many-Round Protocols
Abstract

We investigate the security of succinct arguments against quantum adversaries. Our main result is a proof of knowledge-soundness in the post-quantum setting for a class of multi-round interactive protocols, including those based on the recursive folding technique of Bulletproofs.
To prove this result, we devise a new quantum rewinding strategy, the first that allows for rewinding across many rounds. This technique applies to any protocol satisfying natural multi-round generalizations of special soundness and collapsing. For our main result, we show that recent Bulletproofs-like protocols based on lattices satisfy these properties, and are hence sound against quantum adversaries.

2022

TCC

How to Obfuscate MPC Inputs
Abstract

We introduce the idea of input obfuscation for secure two-party computation (io2PC). Sup-
pose Alice holds a private value x and wants to allow clients to learn f (x, yi), for their choice
of yi, via a secure computation protocol. The goal of io2PC is for Alice to encode x so that an
adversary who compromises her storage gets only oracle access to the function f (x, ·). At the
same time, there must be a 2PC protocol for computing f (x, y) that takes only this encoding
(and not the plaintext x) as input.
We show how to achieve io2PC for functions that have virtual black-box (VBB) obfuscation
in either the random oracle model or generic group model. For functions that can be VBB-
obfuscated in the random oracle model, we provide an io2PC protocol by replacing the random
oracle with an oblivious PRF. For functions that can be VBB-obfuscated in the generic group
model, we show how Alice can instantiate a “personalized” generic group. A personalized generic
group is one where only Alice can perform the algebraic operations of the group, but where she
can let others perform operations in that group via an oblivious interactive protocol.

2022

TCC

Fully Succinct Batch Arguments for NP from Indistinguishability Obfuscation
Abstract

Non-interactive batch arguments for $\mathsf{NP}$ provide a way to amortize the cost of $\mathsf{NP}$ verification across multiple instances. In particular, they allow a prover to convince a verifier of multiple $\mathsf{NP}$ statements with communication that scales sublinearly in the number of instances.
In this work, we study fully succinct batch arguments for $\mathsf{NP}$ in the common reference string (CRS) model where the length of the proof scales not only sublinearly in the number of instances $T$, but also sublinearly with the size of the $\mathsf{NP}$ relation. Batch arguments with these properties are special cases of succinct non-interactive arguments (SNARGs); however, existing constructions of SNARGs either rely on idealized models or strong non-falsifiable assumptions. The one exception is the Sahai-Waters SNARG based on indistinguishability obfuscation. However, when applied to the setting of batch arguments, we must impose an a priori bound on the number of instances. Moreover, the size of the common reference string scales linearly with the number of instances.
In this work, we give a direct construction of a fully succinct batch argument for $\mathsf{NP}$ that supports an unbounded number of statements from indistinguishability obfuscation and one-way functions. Then, by additionally relying on a somewhere statistically-binding (SSB) hash function, we show how to extend our construction to obtain a fully succinct and updatable batch argument. In the updatable setting, a prover can take a proof $\pi$ on $T$ statements $(x_1, \ldots, x_T)$ and "update" it to obtain a proof $\pi'$ on $(x_1, \ldots, x_T, x_{T + 1})$. Notably, the update procedure only requires knowledge of a (short) proof for $(x_1, \ldots, x_T)$ along with a single witness $w_{T + 1}$ for the new instance $x_{T + 1}$. Importantly, the update does not require knowledge of witnesses for $x_1, \ldots, x_T$.

2022

ASIACRYPT

Practical Provably Secure Flooding for Blockchains
Abstract

In recent years, permisionless blockchains have received a lot of attention both from industry and academia, where substantial effort has been spent to develop consensus protocols that are secure under the assumption that less than half (or a third) of a given resource (e.g., stake or computing power) is controlled by corrupted parties. The security proofs of these consensus protocols usually assume the availability of a network functionality guaranteeing that a block sent by an honest party is received by all honest parties within some bounded time. To obtain an overall protocol that is secure under the same corruption assumption, it is therefore necessary to combine the consensus protocol with a network protocol that achieves this property under that assumption. In practice, however, the underlying network is typically implemented by flooding protocols that are not proven to be secure in the setting where a fraction of the considered total weight can be corrupted. This has led to many so-called eclipse attacks on existing protocols and tailor-made fixes against specific attacks.
To close this apparent gap, we present the first practical flooding protocol that provably delivers sent messages to all honest parties after a logarithmic number of steps. We prove security in the setting where all parties are publicly assigned a positive weight and the adversary can corrupt parties accumulating up to a constant fraction of the total weight. This can directly be used in the proof-of-stake setting, but is not limited to it. To prove the security of our protocol, we combine known results about the diameter of Erdős–Rényi graphs with reductions between different types of random graphs. We further show that the efficiency of our protocol is asymptotically optimal.
The practicality of our protocol is supported by extensive simulations for different numbers of parties, weight distributions, and corruption strategies. The simulations confirm our theoretical results and show that messages are delivered quickly regardless of the weight distribution, whereas protocols that are oblivious of the parties' weights completely fail if the weights are unevenly distributed. Furthermore, the average message complexity per party of our protocol is within a small constant factor of such a protocol.

2022

ASIACRYPT

Towards Tight Security Bounds for OMAC, XCBC and TMAC
Abstract

OMAC --- a single-keyed variant of CBC-MAC by Iwata and Kurosawa --- is a widely used and standardized (NIST FIPS 800-38B, ISO/IEC 29167-10:2017) message authentication code (MAC) algorithm. The best security bound for OMAC is due to Nandi who proved that OMAC's pseudorandom function (PRF) advantage is upper bounded by $ O(q^2\ell/2^n) $, where $ q $, $ \ell $, and $ n $, denote the number of queries, maximum permissible query length (in terms of $ n $-bit blocks), and block size of the underlying block cipher, respectively. In contrast, there is no attack with matching lower bound. Indeed, the best known attack on OMAC is the folklore birthday attack achieving a lower bound of $ \Omega(q^2/2^n) $. In this work, we close this gap for a large range of message lengths. Specifically, we show that OMAC's PRF security is upper bounded by $ O(q^2/2^n + q\ell^2/2^n)$. In practical terms, this means that for a $ 128 $-bit block cipher, and message lengths up to $ 64 $ Gigabyte, OMAC can process up to $ 2^{64} $ messages before rekeying (same as the birthday bound). In comparison, the previous bound only allows $ 2^{48} $ messages. As a side-effect of our proof technique, we also derive similar tight security bounds for XCBC (by Black and Rogaway) and TMAC (by Kurosawa and Iwata). As a direct consequence of this work, we have established tight security bounds (in a wide range of $\ell$) for all the CBC-MAC variants, except for the original CBC-MAC.

2022

TCC

Collusion-Resistant Copy-Protection for Watermarkable Functionalities
Abstract

Copy-protection is the task of encoding a program into a quantum state to prevent illegal duplications. A line of recent works studied copy-protection schemes under "1 -> 2 attacks": the adversary receiving one program copy can not produce two valid copies. However, under most circumstances, vendors need to sell more than one copy of a program and still ensure that no duplicates can be generated. In this work, we initiate the study of collusion-resistant copy-protection in the plain model. Our results are twofold:
* For the first time, we show that all major watermarkable functionalities can be copy-protected (including unclonable decryption, digital signatures, and PRFs). Among these, copy-protection of digital signature schemes is not known before. The feasibility of copy-protecting all watermarkable functionalities is an open question raised by Aaronson et al. (CRYPTO' 21)
* We make all the above schemes k bounded collusion-resistant for any polynomial k, giving the first bounded collusion-resistant copy-protection for various functionalities in the plain model.

2022

TCC

On Black-Box Constructions of Time and Space Efficient Sublinear Arguments from Symmetric-Key Primitives
Abstract

Zero-knowledge proofs allow a prover to convince a verifier of a statement without revealing anything besides its validity. A major bottleneck in scaling sub-linear zero-knowledge proofs is the high space requirement of the prover, even for NP relations that can be verified in a small space.
In this work, we ask whether there exist complexity-preserving (i.e. overhead w.r.t time and space are minimal) succinct zero-knowledge arguments of knowledge with minimal assumptions while making only black-box access to the underlying primitives. We essentially resolve this question up to polylogarithmic factors. Namely, for every NP relation that can be verified in time T and space S, we construct a public-coin zero-knowledge argument system that is black-box based on collision-resistant hash-functions (CRH) where the prover runs in time $\O(T)$ and space $\O(S)$, the verifier runs in time $\O(T/S+S)$ and space $\O(\kappa)$ and the communication is $\O(T/S)$, where $\kappa$ is the statistical security parameter. Using the Fiat-Shamir heuristic, our construction yields the first complexity-preserving ZK-SNARK based on CRH (via a black-box construction). Furthermore, we give evidence that reducing the proof length below $\O(T/S)$ will be hard using existing techniques by arguing the space-complexity of constant-distance error correcting codes.

2022

ASIACRYPT

Identity-Based Matchmaking Encryption from Standard Assumptions
Abstract

In this work, we propose the first identity-based matchmaking encryption (IB-ME) scheme under the standard assumptions in the standard model. This scheme is proven to be secure under the symmetric external Diffie-Hellman (SXDH) assumption in prime order bilinear pairing groups. In our IB-ME scheme, all parameters have constant number of group elements and are simpler than those of previous constructions. Previous works are either in the random oracle model or based on the q-type assumptions, while ours is built directly in the standard model and based on static assumptions, and does not rely on other crypto tools.
More concretely, our IB-ME scheme is constructed from a variant of two-level anonymous IBE. We observed that this two-level IBE with anonymity and unforgeability satisfies the same functionality of IB-ME, and its security properties cleverly meet the two requirements of IB-ME (Privacy and Authenticity). The privacy property of IB-ME relies on the anonymity of this two-level IBE, while the authenticity property is corresponding to the unforgeability in the 2nd level. This variant of two-level IBE is built from dual pairing vector spaces, and both security reductions rely on dual system encryption.

2022

ASIACRYPT

A Modular Approach to the Incompressibility of Block-Cipher-Based AEADs
Abstract

Incompressibility is one of the most fundamental security goals in white-box cryptography.
Given recent advances in the design of efficient and incompressible block ciphers such as SPACE, SPNbox and WhiteBlock,
we demonstrate the feasibility of reducing incompressible AEAD modes to incompressible block ciphers.
We first observe that several existing AEAD modes of operation, including CCM, GCM(-SIV), and OCB, would be all insecure against white-box adversaries even when used with an incompressble block cipher.
This motivates us to revisit and formalize incompressibility-based security definitions for AEAD schemes and for block ciphers, so that we become able to design modes and reduce their security to that of the underlying ciphers.
Our new security notion for AEAD, which we name whPRI, is an extension of the pseudo-random injection security in the black-box setting.
Similar security notions are also defined for other cryptosystems such as privacy-only encryption schemes.
We emphasize that whPRI ensures quite strong authenticity against white-box adversaries:
existential unforgeability beyond leakage.
This contrasts sharply with previous notions which have ensured either no authenticity or only universal unforgeability.
For the underlying ciphers we introduce a new notion of whPRP, which extends that of PRP in the black-box setting.
Interestingly, our incompressibility reductions follow from a variant of public indifferentiability.
In particular, we show that a practical whPRI-secure AEAD mode can be built from a whPRP-secure block cipher: We present a SIV-like composition of the sponge construction (utilizing a block cipher as its underlying primitive) with the counter mode and prove that such a construction is (in the variant sense) public indifferentiable from a random injection.
To instantiate such an AEAD scheme, we propose a 256-bit variant of SPACE, based on our conjecture that SPACE should be a whPRP-secure cipher.

2022

TCC

Lower Bounds for the Number of Decryption Updates in Registration-Based Encryption
Abstract

Registration-based encryption (Garg, Hajiabadi, Mahmoody, Rahimi, TCC'18) is a primitive that aims to offer what identity-based encryption offers without the key-escrow problem. In RBE, parties generate their secret keys, a key curator (KC) manages the public keys and updates the compact public parameter, and everyone can use the updated public parameter to securely encrypt messages for individuals.
A major downside of RBE is that parties might need to periodically receive extra information from the KC, called decryption updates, that help them decrypt successfully. Current RBE schemes with n registered parties require \Omega(log n) number of updates while the public parameter is of length poly(log n). This leads to the following natural question: are so many decryption updates necessary for RBE schemes? Indeed, it would be desirable to have RBEs with only a constant number of updates.
In this paper, we prove almost tight lowerbounds for the number of updates in RBE schemes. More generally, we prove a trade-off between the number of updates in RBEs and the length of the public parameter, as long as the update times are fixed, which is a natural property that holds for all known RBE constructions. In particular, we prove that for any RBE scheme for n \geq \binom{k+d}{d+1} identities and d updates that arrive at fixed times, the public parameter needs to be of length \Omega(k). In particular, our lower bound shows that RBE systems with public parameters of length poly(\log n) require almost logarithmic \Omega(log n / log log n) number of updates.

2022

TCC

Poly Onions: Achieving Anonymity in the Presence of Churn
Abstract

Onion routing is a popular approach towards anonymous communication. Practical implementations are widely used (for example, Tor has millions of users daily), but are vulnerable to various traffic correlation attacks, and the theoretical foundations, despite recent progress, still lag behind.
In particular, all works that model onion routing protocols and prove their security only address a single run, where each party sends and receives a single message of fixed length, once. Moreover, they all assume a static network setting, where the parties are stable throughout the lifetime of the protocol. In contrast, real networks have a high rate of churn (nodes joining and exiting the network), real users want to send multiple messages, and realistic adversaries may observe multiple runs of the protocol.
We initiate a formal treatment of onion routing in a setting with multiple runs over a dynamic network with churn. We provide definitions of both security and anonymity in this setting, and constructions that satisfy them. In particular, we define a new cryptographic primitive called \emph{Poly Onions} and show that it can be used to realize our definitions.

2022

TCC

Bounded Functional Encryption for Turing Machines: Adaptive Security from General Assumptions
Abstract

The recent work of Agrawal et al., [Crypto '21] and Goyal et al. [Eurocrypt '22] concurrently introduced the notion of dynamic bounded collusion security for functional encryption (FE) and showed a construction satisfying the notion from identity based encryption (IBE). Agrawal et al., [Crypto '21] further extended it to FE for Turing machines in non-adaptive simulation setting from the sub-exponential learining with errors assumption (LWE). Concurrently, the work of Goyal et al. [Asiacrypt '21] constructed attribute based encryption (ABE) for Turing machines achieving adaptive indistinguishability based security against bounded (static) collusions from IBE, in the random oracle model. In this work, we significantly improve the state of art for dynamic bounded collusion FE and ABE for Turing machines by achieving \emph{adaptive} simulation style security from a broad class of assumptions, in the standard model. In more detail, we obtain the following results:
\begin{enumerate}
\item We construct an adaptively secure (AD-SIM) FE for Turing machines, supporting dynamic bounded collusion, from sub-exponential LWE. This improves the result of Agrawal et al. which achieved only non-adaptive (NA-SIM) security in the dynamic bounded collusion model.
\item Towards achieving the above goal, we construct a \emph{ciphertext policy} FE scheme (CPFE) for circuits of \emph{unbounded} size and depth, which achieves AD-SIM security in the dynamic bounded collusion model from IBE and \emph{laconic oblivious transfer} (LOT). Both IBE and LOT can be instantiated from a large number of mild assumptions such as the computational Diffie-Hellman assumption, the factoring assumption, and polynomial LWE. This improves the construction of Agrawal et al. which could only achieve NA-SIM security for CPFE supporting circuits of unbounded depth from IBE.
\item We construct an AD-SIM secure FE for Turing machines, supporting dynamic bounded collusions, from LOT, ABE for NC1 (or NC) and private information retrieval (PIR) schemes which satisfy certain properties. This significantly expands the class of assumptions on which AD-SIM secure FE for Turing machines can be based. In particular, it leads to new constructions of FE for Turing machines including one based on polynomial LWE and one based on the combination of the bilinear decisional Diffie-Hellman assumption and the decisional Diffie-Hellman assumption on some specific groups. In contrast the only prior construction by Agrawal et al. achieved only NA-SIM security and relied on \emph{sub-exponential} LWE.
To achieve the above result, we define the notion of CPFE for read only RAM programs and succinct FE for LOT, which may be of independent interest.
\item We also construct an \emph{ABE} scheme for Turing machines which achieves AD-IND security in the \emph{standard model} supporting dynamic bounded collusions. Our scheme is based on IBE and LOT. Previously, the only known candidate that achieved AD-IND security from IBE by Goyal et al. relied on the random oracle model. \end{enumerate}

2022

TCC

Leakage-resilient Linear Secret-sharing against arbitrary Bounded-size Leakage Family
Abstract

Motivated by leakage-resilient secure computation of circuits with addition and multiplication gates, this work studies the leakage-resilience of linear secret-sharing schemes with a small reconstruction threshold against any {\em bounded-size} family of joint leakage attacks, \ie, the leakage function can leak {\em global} information from all secret shares.
We first prove that, with high probability, the Massey secret-sharing scheme corresponding to a random linear code over a finite field $F$ is leakage-resilient against any $\ell$-bit joint leakage family of size at most $\abs{F}^{k-2.01}/8^\ell $, where $k$ is the reconstruction threshold. Our result (1) bypasses the bottleneck due to the existing Fourier-analytic approach, (2) enables secure multiplication of secrets, and (3) is near-optimal. We use combinatorial and second-moment techniques to prove the result.
Next, we show that the Shamir secret-sharing scheme over a prime-order field $F$ with randomly chosen evaluation places and with threshold $k$ is leakage-resilient to any $\ell$-bit joint leakage family of size at most $\abs{F}^{2k-n-2.01}/(k!\cdot 8^\ell)$ with high probability. We prove this result by marrying our proof techniques for the first result with the existing Fourier analytical approach. Moreover, it is unlikely that one can extend this result beyond $k/n\leq0.5$ due to the technical hurdle of the Fourier-analytic approach.

2022

TCC

Secure Non-interactive Simulation from Arbitrary Joint Distributions
Abstract

{\em Secure non-interactive simulation} (SNIS), introduced in {EUROCRYPT} 2022, is the information-theoretic analog of {\em pseudo-correlation generators}.
SNIS allows parties, starting with samples of a source correlated private randomness, to non-interactively and securely transform them into samples from a different correlated private randomness.
Determining the feasibility, rate, and capacity of SNIS is natural and essential for the efficiency of secure computation.
This work initiates the study of SNIS, where the target distribution $(U,V)$ is a random sample from the {\em binary symmetric or erasure channels}; however, the source distribution can be arbitrary.
In this context, our work presents:
\begin{enumerate}
\item The characterization of all sources that facilitate such SNIS,
\item An upper and lower bound on their maximum achievable rate, and
\item Exemplar SNIS instances where non-linear reductions achieve optimal efficiency; however, any linear reduction is insecure.
\end{enumerate}
These results collectively yield the fascinating instances of {\em computer-assisted search} for secure computation protocols that identify ingenious protocols that are more efficient than all known constructions.
Our work generalizes the algebraization of the simulation-based definition of SNIS as an approximate eigenvector problem.
The following foundational and general technical contributions of ours are the underpinnings of the results mentioned above.
\begin{enumerate}
\item Characterization of Markov and adjoint Markov operators' effect on the Fourier spectrum of reduction functions.
\item A new concentration phenomenon in the Fourier spectrum of reduction functions.
\item A powerful statistical-to-perfect lemma with broad consequences for feasibility and rate characterization of SNIS.
\end{enumerate}
Our technical analysis relies on Fourier analysis over large alphabets with arbitrary measure, the orthogonal Efron-Stein decomposition, and junta theorems of Kindler-Safra and Friedgut.
Our work establishes a fascinating connection between the rate of SNIS and the maximal correlation,
a prominent information-theoretic property.
Our technical approach motivates the new problem of ``security-preserving dimension reduction'' in harmonic analysis, which may be of independent and broader interest.

2022

ASIACRYPT

Short-lived zero-knowledge proofs and signatures
Abstract

We introduce the short-lived proof, a non-interactive proof of knowledge with a novel feature: after a specified period of time, the proof is no longer convincing. This time-delayed loss of soundness happens "naturally" without further involvement from the prover or any third party. We propose definitions for short-lived proofs as well as the special case of short-lived signatures. We show several practical constructions built using verifiable delay functions (VDFs). The key idea in our approach is to allow any party to forge any proof by executing a large sequential computation. Some constructions achieve a stronger property called reusable forgeability in which one sequential computation allows forging an arbitrary number of proofs of different statements. We also introduces two novel types of VDFs, re-randomizable VDFs and zero-knowledge VDFs, which may be of independent interest. Our constructions for short-lived Sigma-protocols and signatures are practically efficient for provers and verifiers, adding a few hundred bytes of overhead and tens to hundreds of milliseconds of proving/verification time.

2022

ASIACRYPT

Functional Encryption with Secure Key Leasing
Abstract

Secure software leasing is a quantum cryptographic primitive that enables us to lease software to a user by encoding it into a quantum state. Secure software leasing has a mechanism that verifies whether a returned software is valid or not. The security notion guarantees that once a user returns a software in a valid form, the user no longer uses the software.
In this work, we introduce the notion of secret-key functional encryption (SKFE) with secure key leasing, where a decryption key can be securely leased in the sense of secure software leasing. We also instantiate it with standard cryptographic assumptions. More specifically, our contribution is as follows.
- We define the syntax and security definitions for SKFE with secure key leasing.
- We achieve a transformation from standard SKFE into SKFE with secure key leasing without using additional assumptions. Especially, we obtain bounded collusion-resistant SKFE for P/poly with secure key leasing based on post-quantum one-way functions since we can instantiate bounded collusion-resistant SKFE for P/poly with the assumption.
Some previous secure software leasing schemes capture only pirate software that runs on an honest evaluation algorithm (on a legitimate platform). However, our secure key leasing notion captures arbitrary attack strategies and does not have such a limitation.
As an additional contribution, we introduce the notion of single-decryptor FE (SDFE), where each functional decryption key is copy-protected. Since copy-protection is a stronger primitive than secure software leasing, this notion can be seen as a stronger cryptographic primitive than FE with secure key leasing. More specifically, our additional contribution is as follows.
- We define the syntax and security definitions for SDFE.
- We achieve collusion-resistant single-decryptor PKFE for P/poly from post-quantum indistinguishability obfuscation and quantum hardness of the learning with errors problem.

2022

TCC

One-Time Programs from Commodity Hardware
Abstract

One-time programs, originally formulated by Goldwasser et al.~\cite{goldwasser2008one}, are a powerful cryptographic primitive with compelling applications. Known solutions for one-time programs, however, require specialized secure hardware that is not widely available (or, alternatively, access to blockchains and very strong cryptographic tools).
In this work we investigate the possibility of realizing one-time programs from a recent and now more commonly available hardware functionality: the {\em counter lockbox}. A counter lockbox is a stateful functionality that protects an encryption key under a user-specified password, and enforces a limited number of incorrect guesses. Counter lockboxes have become widely available in consumer devices and cloud platforms.
We show that counter lockboxes can be used to realize one-time programs for general functionalities. We develop a number of techniques to reduce the number of counter lockboxes required for our constructions, that may be of independent interest.

2022

ASIACRYPT

Efficient Adaptively-Secure Byzantine Agreement for Long Messages
Abstract

We investigate the communication complexity of Byzantine agreement
protocols for long messages against an adaptive adversary. In this setting, prior $n$-party protocols either achieved a communication complexity of $O(nl\cdot\poly(\kappa))$ or $O(nl + n^2 \cdot \poly(\kappa))$ for $l$-bit long messages and security parameter $\kappa$. We improve the state of the art by presenting protocols with communication complexity $O(nl + n \cdot \poly(\kappa))$ in both the synchronous and asynchronous communication models. The synchronous protocol tolerates $t \le (1-\epsilon) \frac{n}{2}$ corruptions and assumes a VRF setup, while the asynchronous protocol tolerates $t \le (1-\epsilon) \frac{n}{3}$ corruptions under further cryptographic assumptions. Our protocols are very simple and combine subcommittee election with the recent approach of Nayak et al. (DISC'20). Surprisingly, the analysis of our protocols is 'all but simple' and involves an interesting new application of Mc Diarmid's inequality to obtain 'almost optimal' corruption thresholds.

2022

ASIACRYPT

Efficient NIZKs from LWE via Polynomial Reconstruction and ``MPC in the Head''
Abstract

All existing works building non-interactive zero-knowledge (NIZK) arguments for NP from the Learning With Errors (LWE) assumption have studied instantiating the Fiat-Shamir paradigm on a parallel repetition of an underlying honest-verifier zero knowledge (HVZK) sigma protocol, via an appropriately built correlation-intractable (CI) hash function from LWE. This technique has inherent efficiency losses that arise from parallel repetition.
In this work, we show how to make use of the more efficient ``MPC in the Head'' technique for building an underlying honest-verifier protocol upon which to apply the Fiat-Shamir paradigm. To make this possible, we provide a new and more efficient construction of CI hash functions from LWE, using efficient algorithms for polynomial reconstruction as the main technical tool.
We stress that our work provides a new and more efficient ``base construction'' for building LWE-based NIZK arguments for NP. Our protocol can be the building block around which other efficiency-focused bootstrapping techniques can be applied, such as the bootstrapping technique of Gentry et al. (Journal of Cryptology 2015).

2022

ASIACRYPT

Instantiability of Classical Random-Oracle-Model Encryption Transforms
Abstract

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.

2022

TCC

Permissionless Clock Synchronization with Public Setup
Abstract

The permissionless clock synchronization problem asks how it is possible for a population of parties to maintain a system-wide synchronized clock, while their participation rate fluctuates —possibly very widely— over time. The underlying assumption is that parties experience the passage of time with roughly the same speed, but however they may disengage and engage with the protocol following arbitrary (and even chosen adversarially) participation patterns. This (classical) problem has received renewed attention due to the advent of blockchain protocols, and recently it has been solved in the setting of proof of stake, i.e., when parties are assumed to have access to a trusted PKI setup [Badertscher et al., Eurocrypt ’21].
In this work, we present the first proof-of-work (PoW)-based permissionless clock synchro- nization protocol. Our construction relies on an honest majority of computational power that, for the first time, is described in a fine-grain timing model that does not utilize a global clock that exports the current time to all parties. As a secondary result of independent interest, our protocol gives rise to the first PoW-based ledger consensus protocol that does not rely on an external clock for the time-stamping of transactions and adjustment of the PoW difficulty.

2022

TCC

Candidate Trapdoor Claw-Free Functions from Group Actions with Applications to Quantum Protocols
Abstract

Trapdoor Claw-free Functions (TCFs) are two-to-one trapdoor functions where it is computationally hard to find a claw, i.e., a colliding pair of inputs. TCFs have recently seen a surge of renewed interest due to new applications to quantum cryptography: as an example, TCFs enable a classical machine to verify that some quantum computation has been performed correctly. In this work, we propose a new family of (almost two-to-one) TCFs based on conjectured hard problems on isogeny-based group actions. This is the first candidate construction that is not based on lattice-related problems and the first scheme (from any plausible post-quantum assumption) with a deterministic evaluation algorithm. To demonstrate the usefulness of our construction, we show that our TCF family can be used to devise a computational test of qubit, which is the basic building block used in general verification of quantum computations.

2022

ASIACRYPT

Rotatable Zero Knowledge Sets: Post Compromise Secure Auditable Dictionaries with application to Key Transparency
Abstract

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.

2022

TCC

PPAD is as Hard as LWE and Iterated Squaring
Abstract

One of the most fundamental results in game theory is that every game has a Nash equilibrium, an assignment of (randomized) strategies to players with the stability property that no individual player can benefit from deviating from the assigned strategy. It is not known how to efficiently *compute* such a Nash equilibrium --- the computational complexity of this task is characterized by the class PPAD, but the relation of PPAD to other problems and well-known complexity classes is not precisely understood. In recent years there has been mounting evidence, based on cryptographic tools and techniques, showing the hardness of PPAD.
We continue this line of research by showing that PPAD is as hard as *learning with errors* and the *iterated squaring* problem, two standard problems in cryptography. Our work improves over prior hardness results that relied either on (1) sub-exponential assumptions, or (2) relied on ``obfustopia,'' which can currently be based on a particular combination of three assumptions. Our work additionally establishes *public-coin* hardness for PPAD (computational hardness for a publicly sampleable distribution of instances) that seems out of reach of the obfustopia approach.
Following the work of Choudhuri et al. (STOC 2019) and subsequent works, our hardness result is obtained by constructing an *unambiguous and incrementally-updateable* succinct non-interactive argument for IS, whose soundness relies on polynomial hardness of LWE. The result also implies a verifiable delay function with unique proofs, which may be of independent interest.

2022

TCC

Pseudorandom (Function-Like) Quantum State Generators: New Definitions and Applications
Abstract

Pseudorandom quantum states (PRS) are efficiently constructible states that are computationally indistinguishable from being Haar-random, and have recently found cryptographic applications. We explore new definitions and applications of pseudorandom states, and present the following contributions:
- We study variants of pseudorandom \emph{function-like} state (PRFS) generators, introduced by Ananth, Qian, and Yuen (CRYPTO'22), where the pseudorandomness property holds even when the generator can be queried adaptively or in superposition. We show feasibility of these variants assuming the existence of post-quantum one-way functions.
- We show that PRS generators with logarithmic output length imply commitment and encryption schemes with \emph{classical communication}. Previous constructions of such schemes from PRS generators required quantum communication.
- We give a simpler proof of the Brakerski--Shmueli (TCC'19) result that polynomially-many copies of uniform superposition states with random binary phases are indistinguishable from Haar-random states.
- We also show that logarithmic output length is a sharp threshold where PRS generators start requiring computational assumptions.

2022

TCC

The Parallel Reversible Pebbling Game: Analyzing the Post-Quantum Security of iMHFs
Abstract

The classical (parallel) black pebbling game is a useful abstraction which allows us to analyze the resources (space, space-time, cumulative space) necessary to evaluate a function $f$ with a static data-dependency graph $G$. Of particular interest in the field of cryptography are data-independent memory-hard functions $f_{G,H}$ which are defined by a directed acyclic graph (DAG) $G$ and a cryptographic hash function $H$. The pebbling complexity of the graph $G$ characterizes the amortized cost of evaluating $f_{G,H}$ multiple times as well as the total cost to run a brute-force preimage attack over a fixed domain $\mathcal{X}$, i.e., given $y \in \{0,1\}^*$ find $x \in \mathcal{X}$ such that $f_{G,H}(x)=y$. While a classical attacker will need to evaluate the function $f_{G,H}$ at least $m=|\mathcal{X}|$ times a quantum attacker running Grover's algorithm only requires $O(\sqrt{m})$ blackbox calls to a quantum circuit $C_{G,H}$ evaluating the function $f_{G,H}$. Thus, to analyze the cost of a quantum attack it is crucial to understand the space-time cost (equivalently width times depth) of the quantum circuit $C_{G,H}$. We first observe that a legal black pebbling strategy for the graph $G$ does not necessarily imply the existence of a quantum circuit with comparable complexity --- in contrast to the classical setting where any efficient pebbling strategy for $G$ corresponds to an algorithm with comparable complexity evaluating $f_{G,H}$. Motivated by this observation we introduce a new parallel reversible pebbling game which captures additional restrictions imposed by the No-Deletion Theorem in Quantum Computing. We apply our new reversible pebbling game to analyze the reversible space-time complexity of several important graphs: Line Graphs, Argon2i-A, Argon2i-B, and DRSample. Specifically, (1) we show that a line graph of size $N$ has reversible space-time complexity at most $O(N^{1+\frac{2}{\sqrt{\log N}}})$. (2) We show that any $(e,d)$-reducible DAG has reversible space-time complexity at most $O(Ne+dN2^d)$. In particular, this implies that the reversible space-time complexity of Argon2i-A and Argon2i-B are at most $O(N^2 \log \log N/\sqrt{\log N})$ and $O(N^2/\sqrt[3]{\log N})$, respectively. (3) We show that the reversible space-time complexity of DRSample is at most $O(N^2 \log \log N/\log N)$. We also study the cumulative pebbling cost of reversible pebblings extending a (non-reversible) pebbling attack of Alwen and Blocki on depth-reducible graphs.

2022

TCC

Scalable and Transparent Proofs over All Large Fields, via Elliptic Curves (ECFFT Part II)
Abstract

Concretely efficient interactive oracle proofs (IOPs) are of interest due to their applications to scaling
blockchains, their minimal security assumptions, and their potential future-proof resistance to quantum attacks.
Scalable IOPs, in which prover time scales quasilinearly with the computation size and verifier time scales poly-logarithmically with it, have been known to exist thus far only over a set of finite fields of negligible density, namely, over ``FFT-friendly'' fields that contain a sub-group of size $2^\rounds$.
Our main result is to show that scalable IOPs can be constructed over \emph{any} sufficiently large finite field, of size that is at least quadratic in the length of computation whose integrity is proved by the IOP. This result has practical applications as well, because it reduces the proving and verification complexity of cryptographic statements that are naturally stated over pre-defined finite fields which are not ``FFT-friendly''.
Prior state-of-the-art scalable IOPs relied heavily on arithmetization via univariate polynomials and Reed--Solomon codes over FFT-friendly fields. To prove our main result and extend scalability to all large finite fields, we generalize the prior techniques and use new algebraic geometry codes evaluated on sub-groups of elliptic curves (elliptic curve codes).
We also show a new arithmetization scheme that uses the rich and well-understood group structure of elliptic curves to reduce statements of computational integrity to other statements about the proximity of functions evaluated on the elliptic curve
to the new family of elliptic curve codes.

2022

ASIACRYPT

Algebraic Meet-in-the-Middle Attack on LowMC
Abstract

By exploiting the feature of partial nonlinear layers, we propose a new technique called algebraic meet-in-the-middle (MITM) attack to analyze the security of LowMC, which can reduce the memory complexity of the simple difference enumeration attack over the state-of-the-art. Moreover, while an efficient algebraic technique to retrieve the full key from a differential trail of LowMC has been proposed at CRYPTO 2021, its time complexity is still exponential in the key size. In this work, we show how to reduce it to constant time when there are a sufficiently large number of active S-boxes in the trail. With the above new techniques, the attacks on LowMC and LowMC-M published at CRYPTO 2021 are further improved, and some LowMC instances could be broken for the first time. Our results seem to indicate that partial nonlinear layers are still not well-understood.

2022

TCC

Vector Commitments over Rings and Compressed $\Sigma$-Protocols
Abstract

Compressed $\Sigma$-Protocol Theory (CRYPTO 2020) presents an ``alternative'' to Bulletproofs that achieves the same communication complexity while adhering more elegantly to existing $\Sigma$-protocol theory, which enables their techniques to be directly applicable to other widely used settings in the context of ``plug \& play'' algorithmics.
Unfortunately, their techniques are restricted to arithmetic circuits over \emph{prime} fields, which rules out the possibility of using more machine-friendly moduli such as powers of $2$, which have proven to improve efficiency in applications.
In this work we show that such techniques can be generalized to the case of arithmetic circuits modulo \emph{any} number.
This enables the use of powers of $2$, which can prove to be beneficial for efficiency, but it also facilitates the use of other moduli that might prove useful in different applications.
In order to achieve this, we first present an instantiation of the main building block of the theory of compressed $\Sigma$-protocols, namely compact vector commitments.
Our construction, which may be of independent interest, is homomorphic modulo \emph{any} positive integer $m$, a result that was not known in the literature before.
Second, we generalize Compressed $\Sigma$-Protocol Theory from finite fields to $\mathbb{Z}_m$.
The main challenge here is ensuring that there are large enough challenge sets as to fulfill the necessary soundness requirements, which is achieved by considering certain ring extensions.
Our techniques have direct application for example to verifiable computation on homomorphically encrypted data.

2022

TCC

Adaptive versus Static Multi-oracle Algorithms, and Quantum Security of a Split-key PRF
Abstract

In the first part of the paper, we show a generic compiler that transforms any oracle algorithm that can query multiple oracles adaptively, i.e., can decide on which oracle to query at what point dependent on previous oracle responses, into a static algorithm that fixes these choices at the beginning of the execution. Compared to naive ways of achieving this, our compiler controls the blow up in query complexity for each oracle individually, and causes a very mild blow up only.
In the second part of the paper, we use our compiler to show the security of the very efficient hash-based split-key PRF proposed by Giacon, Heuer and Poettering (PKC 2018), in the quantum random oracle model. Using a split-key PRF as the key-derivation function gives rise to a secure a KEM combiner. Thus, our result shows that the hash-based construction of Giacon et al. can be safely used in the context of quantum attacks, for instance to combine a well-established but only classically-secure KEM with a candidate KEM that is believed to be quantum-secure.
Our security proof for the split-key PRF crucially relies on our adaptive-to-static compiler, but we expect our compiler to be useful beyond this particular application. Indeed, we discuss a couple of other, known results from the literature that would have profitted from our compiler, in that these works had to go though serious complications in oder to deal with adaptivity.

2022

ASIACRYPT

Statistical Decoding 2.0: Reducing Decoding to LPN
Abstract

The security of code-based cryptography relies primarily on the hardness of generic decoding with linear codes. The best generic decoding algorithms are all improvements of an old algorithm due to Prange: they are known under the name of information set decoders (ISD).
A while ago, a generic decoding algorithm which does not belong to this family was proposed: statistical decoding.
It is a randomized algorithm that requires the computation of a large set of parity-checks of moderate weight, and uses some kind of majority voting on these equations to recover the error. This algorithm was long forgotten because even the best variants of it
performed poorly when compared to the simplest ISD algorithm.
We revisit this old algorithm by using parity-check equations in a more general way. Here the parity-checks are used to get LPN samples with a secret which is part of the error and the LPN noise is related to the weight of the parity-checks we produce. The corresponding LPN problem is then solved by standard Fourier techniques. By properly choosing the method of producing these low weight equations and the size of the LPN problem, we are able to outperform in this way significantly information set decodings at code rates smaller than 0.3. It gives for the first time after 60 years, a better decoding algorithm for a significant range which does not belong to the ISD family.

2022

TCC

ABE for Circuits with Constant-Size Secret Keys and Adaptive Security
Abstract

An important theme in the research on attribute-based encryption (ABE) is minimizing the sizes of secret keys and ciphertexts. In this work, we present two new ABE schemes with *constant-size* secret keys, i.e., the key size is independent of the sizes of policies or attributes and dependent only on the security parameter $\lambda$.
- We construct the first key-policy ABE scheme for circuits with constant-size secret keys, ${|\mathsf{sk}_f|=\mathrm{poly}(\lambda)}$, which concretely consist of only three group elements. The previous state-of-the-art scheme by [Boneh et al., Eurocrypt '14] has key size polynomial in the maximum depth $d$ of the policy circuits, ${|\mathsf{sk}_f|=\mathrm{poly}(d,\lambda)}$. Our new scheme removes this dependency of key size on $d$ while keeping the ciphertext size the same, which grows linearly in the attribute length and polynomially in the maximal depth, ${|\mathsf{ct}_{\mathbf{x}}|=|\mathbf{x}|\mathrm{poly}(d,\lambda)}$.
- We present the first ciphertext-policy ABE scheme for Boolean formulae that simultaneously has constant-size keys and succinct ciphertexts of size independent of the policy formulae, namely, ${|\mathsf{sk}_f|=\mathrm{poly}(\lambda)}$ and ${|\mathsf{ct}_{\mathbf{x}}|=\mathrm{poly}(|\mathbf{x}|,\lambda)}$. Concretely, each secret key consists of only two group elements. Previous ciphertext-policy ABE schemes either have succinct ciphertexts but non-constant-size keys [Agrawal--Yamada, Eurocrypt '20, Agrawal--Wichs--Yamada, TCC '20], or constant-size keys but large ciphertexts that grow with the policy size as well as the attribute length. Our second construction is the first ABE scheme achieving *double succinctness*, where both keys and ciphertexts are smaller than the corresponding attributes and policies tied to them.
Our constructions feature new ways of combining lattices with pairing groups for building ABE and are proven selectively secure based on LWE and in the generic (pairing) group model. We further show that when replacing the LWE assumption with its adaptive variant introduced in [Quach--Wee--Wichs FOCS '18], the constructions become adaptively secure.

2022

TCC

Secure Sampling with Sublinear Communication
Abstract

Random sampling from specified distributions is an important tool with wide applications for analysis of large-scale data. In this paper we study how to randomly sample when the distribution is partitioned among two parties' private inputs. Of course, a trivial solution is to have one party send a (possibly encrypted) description of its weights to the other party who can then sample over the entire distribution (possibly using homomorphic encryption). However, this approach requires communication that is linear in the input size which is prohibitively expensive in many settings. In this paper, we investigate secure 2-party sampling with sublinear communication for many standard distributions. We develop protocols for L_1, and L_2 sampling. Additionally, we investigate the feasibility of sublinear product sampling, showing impossibility for the general problem and showing a protocol for a restricted case of the problem. We additionally show how such product sampling can be used to instantiate a sublinear communication 2-party exponential mechanism for differentially-private data release.

2022

TCC

Verifiable Private Information Retrieval
Abstract

A computational PIR scheme allows a client to privately query a database hosted on a single server without downloading the entire database. We introduce the notion of verifiable PIR (vPIR) where the server can convince the client that the database satisfies certain properties without additional rounds and while keeping the communication sub-linear. For example, the server can prove that the number of rows in the database that satisfy a predicate P is exactly n.
We define security by modeling vPIR as an ideal functionality and following the real-ideal paradigm. Starting from a standard PIR scheme, we construct a vPIR scheme for any database property that can be verified by a machine that reads the database once and maintains a bounded size state between rows. We also construct vPIR with public verification based on LWE or on DLIN. The main technical hurdle is to demonstrate a simulator that extracts a long input from an adversary that sends a single short message.
Our vPIR constructions are based on the notion of batch argument for NP. As contribution of independent interest, we show that batch arguments are equivalent to quasi-arguments---a relaxation of SNARKs which is known to imply succinct argument for various sub-classes of NP.

2022

TCC

Four-Round Black-Box Non-Malleable Commitments from One-Way Permutations
Abstract

We construct the first four-round non-malleable commitment scheme based solely on the black-box use of one-to-one one-way functions.
Prior to our work, all non-malleable commitment schemes based on black-box use of polynomial-time cryptographic primitives require more than 16 rounds of interaction.
A key tool for our construction is a proof system that satisfies a new definition of security that we call non-malleable zero-knowledge with respect to commitments. In a nutshell, such a proof system can be safely run in parallel with any (potentially interactive) commitment scheme. We provide an instantiation of this tool using the MPC-in-the-Head approach in combination with BMR. The resulting protocol makes black-box use of one-to-one one-way functions.

2022

TCC

Forward-Secure Encryption with Fast Forwarding
Abstract

Forward-secure encryption (FSE) allows communicating parties to refresh their keys across epochs, in a way that compromising the current secret key leaves all prior encrypted communication secure. We investigate a novel dimension in the design of FSE schemes: fast-forwarding (FF). This refers to the ability of a stale communication party, that is "stuck" in an old epoch, to efficiently "catch up" to the newest state, and frequently arises in practice. While this dimension was not explicitly considered in prior work, we observe that one can augment prior FSEs -- both in symmetric- and public-key settings -- to support fast-forwarding which is sublinear in the number of epochs. However, the resulting schemes have disadvantages: the symmetric-key scheme is a security parameter slower than any conventional stream cipher, while the public-key scheme inherits the inefficiencies of the HIBE-based forward-secure PKE.
To address these inefficiencies, we look at the common real-life situation which we call the bulletin board model, where communicating parties rely on some infrastructure -- such as an application provider -- to help them store and deliver ciphertexts to each other. We then define and construct FF-FSE in the bulletin board model, which addresses the above-mentioned disadvantages. In particular,
* Our FF-stream-cipher in the bulletin-board model has: (a) constant state size; (b) constant normal (no fast-forward) operation; and (c) logarithmic fast-forward property. This essentially matches the efficiency of non-fast-forwardable stream ciphers, at the cost of constant communication complexity with the bulletin board per update.
* Our public-key FF-FSE avoids HIBE-based techniques by instead using so-called updatable public-key encryption (UPKE), introduced in several recent works (and more efficient than public-key FSEs). Our UPKE-based scheme uses a novel type of "update graph" that we construct in this work. Our graph has constant in-degree, logarithmic diameter, and logarithmic "cut property" which is essential for the efficiency of our schemes. Combined with recent UPKE schemes, we get two FF-FSEs in the bulletin board model, under DDH and LWE.

2022

TCC

Parallelizable Delegation from LWE
Abstract

We present the first non-interactive delegation scheme for P with time-tight parallel prover
efficiency based on standard hardness assumptions. More precisely, in a time-tight delegation
scheme—which we refer to as a SPARG (succinct parallelizable argument)—the prover’s parallel
running time is t + polylog(t), while using only polylog(t) processors and where t is the length
of the computation. (In other words, the proof is computed essentially in parallel with the
computation, with only some minimal additive overhead in terms of time).
Our main results show the existence of a publicly-verifiable, non-interactive, SPARG for P
assuming polynomial hardness of LWE. Our SPARG construction relies on the elegant recent
delegation construction of Choudhuri, Jain, and Jin (FOCS’21) and combines it with techniques
from Ephraim et al (EuroCrypt’20).
We next demonstrate how to make our SPARG time-independent—where the prover and
verifier do not need to known the running-time t in advance; as far as we know, this yields
the first construction of a time-tight delegation scheme with time-independence based on any
hardness assumption.
We finally present applications of SPARGs to the constructions of VDFs (Boneh et al,
Crypto’18), resulting in the first VDF construction from standard polynomial hardness assumptions (namely LWE and the minimal assumption of a sequentially hard
function).

2022

TCC

Post-Quantum Insecurity from LWE
Abstract

We show that for many fundamental cryptographic primitives, proving classical security under the learning-with-errors (LWE) assumption, does \emph{not} imply post-quantum security. This is despite the fact that LWE is widely believed to be post-quantum secure, and our work does not give any evidence otherwise. Instead, it shows that post-quantum insecurity can arise inside cryptographic constructions, even if the assumptions are post-quantum secure.
Concretely, our work provides (contrived) constructions of pseudorandom functions, CPA-secure symmetric-key encryption, message-authentication codes, signatures, and CCA-secure public-key encryption schemes, all of which are proven to be classically secure under LWE via black-box reductions, but demonstrably fail to be post-quantum secure. All of these cryptosystems are stateless and non-interactive, but their security is defined via an interactive game that allows the attacker to make oracle queries to the cryptosystem. The polynomial-time quantum attacker can break these schemes by only making a few \emph{classical} queries to the cryptosystem, and in some cases, a single query suffices.
Previously, we only had examples of post-quantum insecurity under post-quantum assumptions for stateful/interactive protocols. Moreover, there appears to be a folklore belief that for stateless/non-interactive cryptosystems with black-box proofs of security, a quantum attack against the scheme should translate into a quantum attack on the assumption. This work shows otherwise. Our main technique is to carefully embed interactive protocols inside the interactive security games of the above primitives.
As a result of independent interest, we also show a 3-round \emph{quantum disclosure of secrets (QDS)} protocol between a classical sender and a receiver, where a quantum receiver learns a secret message in the third round but, assuming LWE, a classical receiver does not.

2022

TCC

Oblivious-Transfer Complexity of Noisy Coin-Toss via Secure Zero Communication Reductions
Abstract

In $p$-noisy coin-tossing, Alice and Bob obtain fair coins which are of
opposite values with probability $p$. Its Oblivious-Transfer (OT) complexity
refers to the least number of OTs required by a semi-honest perfectly secure
2-party protocol for this task. We show a tight bound of $\Theta(\log 1/p)$
for the OT complexity of $p$-noisy coin-tossing. This is the first instance
of a lower bound for OT complexity that is independent of the input/output
length of the function.
We obtain our result by providing a general connection between the OT complexity of
randomized functions and the complexity of Secure Zero Communication
Reductions (SZCR), as recently defined by Narayanan et al. (TCC 2020), and
then showing a lower bound for the complexity of an SZCR from noisy
coin-tossing to (a predicate corresponding to) OT.

2022

TCC

Sublinear Secure Computation from New Assumptions
Abstract

Secure computation enables mutually distrusting parties to jointly compute a function on their secret inputs, while revealing nothing beyond the function output. A long-running challenge is understanding the required communication complexity of such protocols---in particular, when communication can be sublinear in the circuit representation size of the desired function. For certain functions, such as Private Information Retrieval (PIR), this question extends to even sublinearity in the input size.
We develop new techniques expanding the set of computational assumptions for sublinear communication in both settings:
1) Circuit size. We present sublinear-communication protocols for secure evaluation of general layered circuits, given any 2-round rate-1 batch oblivious transfer (OT) protocol with a particular ``decomposability'' property.
In particular, this condition can be shown to hold for the recent batch OT protocols of (Brakerski et al. Eurocrypt 2022), in turn yielding a new sublinear secure computation feasibility: from Quadratic Residuosity (QR) together with polynomial-noise-rate Learning Parity with Noise (LPN).
Our approach constitutes a departure from existing paths toward sublinear secure computation, all based on fully homomorphic encryption or homomorphic secret sharing.
2) Input size. We construct single-server PIR based on the Computational Diffie-Hellman (CDH) assumption, with polylogarithmic communication in the database input size n. Previous constructions from CDH required communication Omega(n).
In hindsight, our construction comprises of a relatively simple combination of existing tools from the literature.

2022

ASIACRYPT

New Algorithms and Analyses for Sum-Preserving Encryption
Abstract

We continue the study of sum-preserving encryption schemes, in which
the plaintext and ciphertext are both integer vectors with the same sum.
Such encryption schemes were recently constructed and analyzed by
Tajik, Gunasekaran, Dutta, Ellia, Bobba, Rosulek, Wright, and
Feng (NDSS 2019) in the context of image encryption. Our first main
result is to prove a mixing-time bound for the construction given by
Tajik et al. using path coupling. We then provide new sum-preserving
encryption schemes by describing two practical ways to rank and unrank the
values involved in sum-preserving encryption, which can then be
combined with the rank-encipher-unrank technique from format-preserving
encryption. Finally, we compare the efficiency of the Tajik et al.
construction and our new ranking constructions based on performance tests
we conducted on prototype implementations.

2022

ASIACRYPT

PointProofs, Revisited
Abstract

Vector commitments allow a user to commit to a vector of
length n using a constant-size commitment while being able to locally
open the commitment to individual vector coordinates. Importantly, the
size of position-wise openings should be independent of the dimension
n. Gorbunov, Reyzin, Wee, and Zhang recently proposed PointProofs
(CCS 2020), a vector commitment scheme that supports non-interactive
aggregation of proofs across multiple commitments, allowing to drastically reduce the cost of block propagation in blockchain smart contracts.
Gorbunov et al. provide a security analysis combining the algebraic group
model and the random oracle model, under the weak n-bilinear Diffie-
Hellman Exponent assumption (n-wBDHE) assumption. In this work,
we propose a novel analysis that does not rely on the algebraic group
model. We prove the security in the random oracle model under the n-
Diffie-Hellman Exponent (n-DHE) assumption, which is implied by the
n-wBDHE assumption considered by Gorbunov et al. We further note
that we do not modify their scheme (and thus preserve its efficiency) nor
introduce any additional assumption. Instead, we prove the security of
the scheme as it is via a strictly improved analysis.

2022

TCC

Public-Key Encryption from Homogeneous CLWE
Abstract

The homogeneous continuous LWE (hCLWE) problem is to distinguish samples of a specific high-dimensional Gaussian mixture from standard normal samples. It was shown to be at least as hard as Learning with Errors, but no reduction in the other direction is currently known.
We present four new public-key encryption schemes based on the hardness of hCLWE, with varying tradeoffs between decryption and security errors, and different discretization techniques. Our schemes yield a polynomial-time algorithm for solving hCLWE using a Statistical Zero-Knowledge oracle.

2022

TCC

On the Impossibility of Algebraic Vector Commitments in Pairing-Free Groups
Abstract

Vector Commitments allow one to (concisely) commit to a vector of messages so that one can later (concisely) open the commitment at selected locations. In the state of the art of vector commitments, {\em algebraic} constructions have emerged as a particularly useful class, as they enable advanced properties, such as stateless updates, subvector openings and aggregation, that are for example unknown in Merkle-tree-based schemes.
In spite of their popularity, algebraic vector commitments remain poorly understood objects. In particular, no construction in standard prime order groups (without pairing) is known.
In this paper, we shed light on this state of affairs by showing that a large class of concise algebraic vector commitments in pairing-free, prime order groups are impossible to realize.
Our results also preclude any cryptographic primitive that implies the algebraic vector commitments we rule out, as special cases.
This means that we also show the impossibility, for instance, of succinct polynomial commitments and functional commitments (for all classes of functions including linear forms) in pairing-free groups of prime order.

2022

TCC

Random-Index Oblivious RAM
Abstract

We study the notion of {\em Random-index ORAM} (RORAM), which is a weak form of ORAM where the Client is limited to asking for random elements of the $N$-items memory rather than specific ones (and, possibly, modify them). That is, whenever the client issues a request, it gets in return a pair $(r,x_r)$ where $r\in_R[N]$ is a random index and $x_r$ is the content of the $r$-th memory item. Then, the client can also modify the content to some new value $x'_r$.
We first argue that for certain applications the limited functionality of RORAM still suffices. These include various applications of sampling (or sub-sampling), and in particular the very-large-scale MPC application in the setting of~ Benhamouda et al. \cite{BGG+20}. Clearly, RORAM can be implemented using any ORAM scheme (by the Client selecting the random $r$'s by himself), but the hope is that the limited functionality of RORAM can make it faster and easier to implement than ORAM. Indeed, our main contributions are several RORAM schemes (both of the hierarchical-type and the tree-type) of lighter complexity than that of ORAM.

2022

TCC

Achievable CCA2 Relaxation for Homomorphic Encryption
Abstract

Homomorphic encryption (HE) protects data in-use, but can be computationally expensive. To avoid the costly bootstrapping procedure that refreshes ciphertexts, some works have explored client-aided outsourcing protocols, where the client intermittently refreshes ciphertexts for a server that is performing homomorphic computations. But is this approach secure against malicious servers?
We present a CPA-secure encryption scheme that is completely insecure in this setting. We define a new notion of security, called \emph{funcCPA}, that we prove is sufficient. Additionally, we show:
- Homomorphic encryption schemes that have a certain type of circuit privacy -- for example, schemes in which ciphertexts can be ``sanitized" -- are funcCPA-secure.
- In particular, assuming certain existing HE schemes are CPA-secure, they are also funcCPA-secure.
- For certain encryption schemes, like Brakerski-Vaikuntanathan, that have a property that we call oblivious secret key extraction, funcCPA-security implies circular security -- i.e., that it is secure to provide an encryption of the secret key in a form usable for bootstrapping (to construct fully homomorphic encryption).
Namely, funcCPA-security lies strictly between CPA-security and CCA2-security (under reasonable assumptions), and has an interesting relationship with circular security, though it is not known to be equivalent.

2022

ASIACRYPT

On Rejection Sampling in Lyubashevsky's Signature Scheme
Abstract

Lyubashevsky’s signatures are based on the Fiat-Shamir with
aborts paradigm, whose central ingredient is the use of rejection sampling
to transform secret-dependent signature samples into samples from (or
close to) a secret-independent target distribution. Several choices for the
underlying distributions and for the rejection sampling strategy can be
considered. In this work, we study Lyubashevsky’s signatures through
the lens of rejection sampling, and aim to minimize signature size given
signing runtime requirements. Several of our results concern rejection
sampling itself and could have other applications.
We prove lower bounds for compactness of signatures given signing run-
time requirements, and for expected runtime of perfect rejection sampling
strategies. We also propose a Rényi-divergence-based analysis of Lyuba-
shevsky’s signatures which allows for larger deviations from the target
distribution, and show hyperball uniforms to be a good choice of distri-
butions: they asymptotically reach our compactness lower bounds and
offer interesting features for practical deployment. Finally, we propose
a different rejection sampling strategy which circumvents the expected
runtime lower bound and provides a worst-case runtime guarantee.

2022

TCC

Secure Non-Interactive Reducibility is Decidable
Abstract

Secure Non-Interactive Reductions (SNIR) is a recently introduced, but fundamental cryp- tographic primitive. The basic question about SNIRs is how to determine if there is a SNIR from one 2-party correlation to another. While prior work provided answers for several pairs of correlations, the possibility that this is an undecidable problem in general was left open. In this work we show that the existence of a SNIR between any pair of correlations can be determined by an algorithm.
At a high-level, our proof follows the blueprint of a similar (but restricted) result by Khorasgani et al. But combining the spectral analysis of SNIRs by Agrawal et al. (Eurocrypt 2022) with a new variant of a “junta theorem” by Kindler and Safra, we obtain a complete resolution of the decidability question for SNIRs. The new junta theorem that we identify and prove may be of independent interest.

2022

ASIACRYPT

Group Action Key Encapsulation and Non-Interactive Key Exchange in the QROM
Abstract

In the context of quantum-resistant cryptography, cryptographic group actions offer an abstraction of isogeny-based cryptography in the Commutative Supersingular Isogeny Diffie-Hellman (CSIDH) setting.
In this work, we revisit the security of two previously proposed natural protocols: the Group Action Hashed ElGamal key encapsulation mechanism (GA-HEG KEM) and the Group Action Hashed Diffie-Hellman non-interactive key-exchange (GA-HDH NIKE) protocol.
The latter protocol has already been considered to be used in practical protocols such as Post-Quantum WireGuard (S&P '21) and OPTLS (CCS '20).
We prove that active security of the two protocols in the Quantum Random Oracle Model (QROM) inherently relies on very strong variants of the Group Action Strong CDH problem, where the adversary is given arbitrary quantum access to a DDH oracle. That is, quantum accessible Strong CDH assumptions are not only sufficient but also necessary to prove active security of the GA-HEG KEM and the GA-HDH NIKE protocols.
Furthermore, we propose variants of the protocols with QROM security from the classical Strong CDH assumption, i.e., CDH with classical access to the DDH oracle.
Our first variant uses key confirmation and can therefore only be applied in the KEM setting.
Our second but considerably less efficient variant is based on the twinning technique by Cash et al. (EUROCRYPT '08) and in particular yields the first actively secure isogeny-based NIKE with QROM security from the standard CDH assumption.

2022

ASIACRYPT

YOLO YOSO: Fast and Simple Encryption and Secret Sharing in the YOSO Model
Abstract

Achieving adaptive (or proactive) security in cryptographic protocols is notoriously difficult due to the adversary's power to dynamically corrupt parties as the execution progresses. Inspired by the work of Benhamouda \textit{et al.} in TCC 2020, Gentry \textit{et al.} in CRYPTO 2021 introduced the YOSO (You Only Speak Once) model for constructing adaptively (or proactively) secure protocols in massively distributed settings (\textit{e.g.} blockchains). In this model, instead of having all parties execute an entire protocol, smaller \emph{anonymous committees} are randomly chosen to execute each individual round of the protocol. After playing their role, parties encrypt protocol messages towards the the next anonymous committee and erase their internal state before publishing their ciphertexts.
However, a big challenge remains in realizing YOSO protocols: \emph{efficiently} encrypting messages towards anonymous parties selected at random without learning their identities, while proving the encrypted messages are valid with respect to the protocol. In particular, the protocols of Benhamouda \textit{et al.} and of Gentry \textit{et al.} require showing ciphertexts contain valid shares of secret states. We propose concretely efficient methods for encrypting a protocol's secret state towards a random anonymous committee. We start by proposing a very simple and efficient scheme for encrypting messages towards randomly and anonymously selected parties. We then show constructions of publicly verifiable secret (re-)sharing (PVSS) schemes with concretely efficient proofs of (re-)share validity that can be generically instantiated from encryption schemes with certain linear homomorphic properties. In addition, we introduce a new PVSS with proof of sharing consisting of just two field elements, which as far as we know is the first achieving this, and may be of independent interest. Finally, we show that our PVSS schemes can be efficiently realized from our encyption scheme.

2022

ASIACRYPT

Efficient Zero-Knowledge Arguments in Discrete Logarithm Setting: Sublogarithmic Proof or Sublinear Verifier
Abstract

We propose three interactive zero-knowledge arguments for arithmetic circuit of size N in the common random string model, which can be converted to be non-interactive by Fiat-Shamir heuristics in the random oracle model. First argument features O( log N ) communication and round complexities and O(N) computational complexity for the verifier. Second argument features O(log N ) communication and O( N ) computational complexity for the verifier. Third argument features O(log N ) communication and O( N log N ) computational complexity for the verifier. Contrary to first and second arguments, the third argument is free of reliance on pairing-friendly elliptic curves. The soundness of three arguments is proven under the standard discrete logarithm and/or the double pairing assumption, which is at least as reliable as the decisional Diffie-Hellman assumption.

2022

TCHES

Composite Enclaves: Towards Disaggregated Trusted Execution
Abstract

The ever-rising computation demand is forcing the move from the CPU to heterogeneous specialized hardware, which is readily available across modern datacenters through disaggregated infrastructure. On the other hand, trusted execution environments (TEEs), one of the most promising recent developments in hardware security, can only protect code confined in the CPU, limiting TEEs’ potential and applicability to a handful of applications. We observe that the TEEs’ hardware trusted computing base (TCB) is fixed at design time, which in practice leads to using untrusted software to employ peripherals in TEEs. Based on this observation, we propose composite enclaves with a configurable hardware and software TCB, allowing enclaves access to multiple computing and IO resources. Finally, we present two case studies of composite enclaves: i) an FPGA platform based on RISC-V Keystone connected to emulated peripherals and sensors, and ii) a large-scale accelerator. These case studies showcase a flexible but small TCB (2.5 KLoC for IO peripherals and drivers), with a low-performance overhead (only around 220 additional cycles for a context switch), thus demonstrating the feasibility of our approach and showing that it can work with a wide range of specialized hardware.

2022

ASIACRYPT

Counting Vampires: From Univariate Sumcheck to Updatable ZK-SNARK
Abstract

We propose a univariate sumcheck argument $\mathfrak{Count}$ of essentially
optimal communication efficiency of one group element. While the previously
most efficient univariate sumcheck argument of Aurora is based on polynomial
commitments, $\mathfrak{Count}$ is based on inner-product commitments. We
use $\mathfrak{Count}$ to construct a new pairing-based updatable and
universal zk-SNARK $\mathfrak{Vampire}$ with the shortest known argument
length (four group and two finite field elements) for $\mathsf{NP}$. In addition,
$\mathfrak{Vampire}$ uses the aggregated polynomial commitment scheme of
Boneh et al.

2022

TCHES

Breaking Masked Implementations of the Clyde-Cipher by Means of Side-Channel Analysis - A Report on the CHES Challenge Side-Channel Contest 2020
Abstract

In this paper we present our solution to the CHES Challenge 2020, the task of which it was to break masked hardware respective software implementations of the lightweight cipher Clyde by means of side-channel analysis. We target the secret cipher state after processing of the first Sbox layer. Using the provided trace data we obtain a strongly biased posterior distribution for the secret-shared cipher state at the targeted point; this enables us to see exploitable biases even before the secret sharing based masking. These biases on the unshared state can be evaluated one S-box at a time and combined across traces, which enables us to recover likely key hypotheses S-box by S-box.
In order to see the shared cipher state, we employ a deep neural network similar to the one used by Gohr, Jacob and Schindler to solve the CHES 2018 AES challenge. We modify their architecture to predict the exact bit sequence of the secret-shared cipher state. We find that convergence of training on this task is unsatisfying with the standard encoding of the shared cipher state and therefore introduce a different encoding of the prediction target, which we call the scattershot encoding. In order to further investigate how exactly the scattershot encoding helps to solve the task at hand, we construct a simple synthetic task where convergence problems very similar to those we observed in our side-channel task appear with the naive target data encoding but disappear with the scattershot encoding.
We complete our analysis by showing results that we obtained with a classical method (as opposed to an AI-based method), namely the stochastic approach, that we generalize for this purpose first to the setting of shared keys. We show that the neural network draws on a much broader set of features, which may partially explain why the neural-network based approach massively outperforms the stochastic approach. On the other hand, the stochastic approach provides insights into properties of the implementation, in particular the observation that the S-boxes behave very different regarding the easiness respective hardness of their prediction.

2022

TCC

Steganography-Free Zero-Knowledge
Abstract

We revisit the well-studied problem of preventing steganographic communication in multi-party communications. While this is known to be a provably impossible task, we propose a new model that allows circumventing this impossibility. In our model, the parties first publish a single message during an honest \emph{non-interactive} pre-processing phase and then later interact in an execution phase. We show that in this model, it is indeed possible to prevent any steganographic communication in zero-knowledge protocols. Our solutions rely on standard cryptographic assumptions.

2022

ASIACRYPT

Anonymous Public Key Encryption under Corruptions
Abstract

Anonymity of public key encryption (PKE) requires that, in a multi-user scenario, the PKE ciphertexts do not leak information about which public keys are used to generate them. Corruptions are common threats in the multi-user scenario but anonymity of PKE under corruptions is less studied in the literature. In TCC 2020, Benhamouda et al. first provide a formal characterization for anonymity of PKE under a specific type of corruption. However, no known PKE scheme is proved to meet their characterization.
To the best of our knowledge, all the PKE application scenarios which require anonymity also require confidentiality. However, in the work by Benhamouda et al., different types of corruptions for anonymity and confidentiality are considered, which can cause security pitfalls. What's worse, we are not aware of any PKE scheme which can provide both anonymity and confidentiality under the same types of corruptions.
In this work, we introduce a new security notion for PKE called ANON-RSO$_{k}\&$C security, capturing anonymity under corruptions. We also introduce SIM-RSO$_{k}\&$C security which captures confidentiality under the same types of corruptions. We provide a generic framework of constructing PKE scheme which can achieve the above two security goals simultaneously based on a new primitive called key and message non-committing encryption (KM-NCE). Then we give a general construction of KM-NCE utilizing a variant of hash proof system (HPS) called Key-Openable HPS. We also provide Key-Openable HPS instantiations based on the matrix decisional Diffie-Hellman assumption. Therefore, we can obtain various concrete PKE instantiations achieving the two security goals in the standard model with \emph{compact} ciphertexts. Furthermore, for some PKE instantiation, its security reduction is \emph{tight}.

2022

ASIACRYPT

Jammin' on the deck
Abstract

Currently, a vast majority of symmetric-key cryptographic schemes are built as block cipher modes. The block cipher is designed to be hard to distinguish from a random permutation and this is supported by cryptanalysis, while (good) modes can be proven secure if a random permutation takes the place of the block cipher. As such, block ciphers form an abstraction level that marks the border between cryptanalysis and security proofs. In this paper, we investigate a re-factored version of symmetric-key cryptography built not around the block ciphers but rather the deck function: a keyed function with arbitrary input and output length and incrementality properties. This allows for modes of use that are simpler to analyze and still very efficient thanks to the excellent performance of currently proposed deck functions. We focus on authenticated encryption (AE) modes with varying levels of robustness. Our modes have built-in support for sessions, but are also efficient without them.
As a by-product, we define a new ideal model for AE dubbed the jammin cipher. Unlike the OAE2 security models, the jammin cipher is both a operational ideal scheme and a security reference, and addresses real-world use cases such as bi-directional communication and multi-key security.

2022

TCHES

Can’t Touch This: Inertial HSMs Thwart Advanced Physical Attacks
Abstract

In this paper, we introduce a novel countermeasure against physical attacks: Inertial Hardware Security Modules (IHSMs). Conventional systems have in common that their security requires the crafting of fine sensor structures that respond to minute manipulations of the monitored security boundary or volume. Our approach is novel in that we reduce the sensitivity requirement of security meshes and other sensors and increase the complexity of any manipulations by rotating the security mesh or sensor at high speed—thereby presenting a moving target to an attacker. Attempts to stop the rotation are easily monitored with commercial MEMS accelerometers and gyroscopes. Our approach leads to an HSM that can easily be built from off-the-shelf parts by any university electronics lab, yet offers a level of security that is comparable to commercial HSMs. We have built a proof-of-concept hardware prototype that demonstrates solutions to the concept’s main engineering challenges. As part of this proof-of-concept, we have found that a system using a coarse security mesh made from commercial printed circuit boards and an automotive high-g-force accelerometer already provides a useful level of security.

2022

TCHES

GE vs GM: Efficient side-channel security evaluations on full cryptographic keys
Abstract

Security evaluations for full cryptographic keys is a very important
research topic since the past decade. An efficient rank estimation algorithm
was proposed at FSE 2015 to approximate the empirical guessing entropy
remaining after a side-channel attack on a full AES key, by combining
information from attacks on each byte of the key independently. However,
these could not easily scale to very large keys over 1024 bits. Hence, at
CHES 2017, it was proposed a new approach for scalable security evaluations
based on Massey's guessing entropy, which was shown tight and scalable to
very large keys, even beyond 8192 bits. Then, at CHES 2020, it was proposed a
new method for estimating the empirical guessing entropy for the case of
full-key evaluations, showing also important divergences between
the empirical guessing entropy and Massey's guessing entropy.
However, there has been some confusion in recent
publications of side-channel evaluation methods relying on these two
variants of the guessing entropy. Furthermore, it remained an open
problem to decide which of these methods should be used and in which context,
particularly given the wide acceptance of the empirical guessing entropy
in the side-channel community and the relatively little use of the other.
In this paper, we tackle this open problem through several contributions.
First of all, we provide an unitary presentation of both versions
of the guessing entropy, allowing an easy comparison of the two metrics.
Secondly, we compare the two metrics using a set of common and relevant
indicators, as well as three different datasets for side-channel evaluations
(simulated, AVR XMEGA 8-bit microcontroller and a 32-bit device).
We used these indicators and datasets also to compare the three full-key
evaluation methods from FSE~2015, CHES~2017 and CHES~2020, allowing us
to provide a clear overview of the usefulness and limitations of each
method. Furthermore, our analysis has enabled us to find a new
method for verifying the soundness of a leakage model, by comparing
both versions of the guessing entropy. This method can be easily extended
to full-key evaluations, hence leading to a new useful method
for side-channel evaluations.

2022

ASIACRYPT

Random Sources in Private Computation
Abstract

We consider multi-party information-theoretic private computation. Such computation inherently requires the use of local randomness by the parties, and the question of minimizing the total number of random bits used for given private computations has received considerable attention in the literature.
In this work we are interested in another question: given a private computation, we ask how many of the players need to have access to a random source, and how many of them can be deterministic parties. We are further interested in the possible interplay between the number of random sources in the system and the total number of random bits necessary for the computation.
We give a number of results. We first show that, perhaps surprisingly, t players (rather than t+1) with access to a random source are sufficient for the information-theoretic t-private computation of any deterministic functionality over n players for any t<n/2; by a result of (Kushilevitz and Mansour, PODC'96), this is best possible. This means that, counter intuitively, while private computation is impossible without randomness, it is possible to have a private computation even when the adversary can control *all* parties who can toss coins (and therefore sees all random coins). For randomized functionalities we show that t+1 random sources are necessary (and sufficient).
We then turn to the question of the possible interplay between the number of random sources and the necessary number of random bits. Since for only very few settings in private computation meaningful bounds on the number of necessary random bits are known, we consider the AND function, for which some such bounds are known. We give a new protocol to 1-privately compute the n-player AND function, which uses a single random source and 6 random bits tossed by that source. This improves, upon the currently best known results (Kushilevitz et al., TCC 2019), at the same time the number of sources and the number of random bits ((Kushilevitz et al., TCC 2019) gives a 2-source, 8-bits protocol). This result gives maybe some evidence that for 1-privacy, using the minimum necessary number of sources one can also achieve the necessary minimum number of random bits. We believe however that our protocol is of independent interest for the study of randomness in private computation.

2022

TCHES

VITI: A Tiny Self-Calibrating Sensor for Power-Variation Measurement in FPGAs
Abstract

On-chip sensors, built using reconfigurable logic resources in field programmable gate arrays (FPGAs), have been shown to sense variations in signalpropagation delay, supply voltage and power consumption. These sensors have been successfully used to deploy security attacks called Remote Power Analysis (RPA) Attacks on FPGAs. The sensors proposed thus far consume significant logic resources and some of them could be used to deploy power viruses. In this paper, a sensor (named VITI) occupying a far smaller footprint than existing sensors is presented. VITI is a self-calibrating on-chip sensor design, constructed using adjustable delay elements, flip-flops and LUT elements instead of combinational loops, bulky carry chains or latches. Self-calibration enables VITI the autonomous adaptation to differing situations (such as increased power consumption, temperature changes or placement of the sensor in faraway locations from the circuit under attack). The efficacy of VITI for power consumption measurement was evaluated using Remote Power Analysis (RPA) attacks and results demonstrate recovery of a full 128-bit Advanced Encryption Standard (AES) key with only 20,000 power traces. Experiments demonstrate that VITI consumes 1/4th and 1/16th of the area compared to state-of-the-art sensors such as time to digital converters and ring oscillators for similar effectiveness.

2022

TCHES

A Power to Pulse Width Modulation Sensor for Remote Power Analysis Attacks
Abstract

Field-programmable gate arrays (FPGAs) deployed on commercial cloud services are increasingly gaining popularity due to the cost and compute benefits offered by them. Recent studies have discovered security threats than can be launched remotely on FPGAs that share the logic fabric between trusted and untrusted parties, posing a danger to designs deployed on cloud FPGAs. With remote power analysis (RPA) attacks, an attacker aims to deduce secret information present on a remote FPGA by deploying an on-chip sensor on the FPGA logic fabric. Information captured with the on-chip sensor is transferred off the chip for analysis and existing on-chip sensors demand a significant amount of bandwidth for this task as a result of their wider output bit width. However, attackers are often left with the only option of using a covert communication channel and the bandwidth of such channels is generally limited. This paper proposes a novel area-efficient on-chip power sensor named PPWM that integrates a logic design outputting a pulse whose width is modulated by the power consumption of the FPGA. This pulse is used to clear a flip-flop selectively and asynchronously, and the single-bit output of the flip-flop is used to perform an RPA attack. This paper demonstrates the possibility of successfully recovering a 128-bit Advanced Encryption Standard (AES) key within 16,000 power traces while consuming just 25% of the bandwidth when compared to the state of the art. Moreover, this paper assesses the threat posed by the proposed PPWM to remote FPGAs including those that are deployed on cloud services.

2022

ASIACRYPT

Revisiting Related-Key Boomerang attacks on AES using computer-aided tool
Abstract

In recent years, several MILP models were introduced to search automatically for boomerang distinguishers and boomerang attacks on block ciphers. However, they can only be used when the key schedule is linear. Here, a new model is introduced to deal with nonlinear key schedules as it is the case for {\mbox{\tt AES}}. This model is more complex and actually it is too slow for exhaustive search. However, when some hints are added to the solver, it found the current best related-key boomerang attack on {\mbox{\tt AES-192}} with $2^{124}$ time, $2^{124}$ data, and $2^{79.8}$ memory complexities, which is better than the one presented by Biryukov and Khovratovich at ASIACRYPT 2009 with complexities $2^{176}/2^{123}/2^{152}$ respectively. This represents a huge improvement for the time and memory complexity, illustrating the power of MILP in cryptanalysis.

2022

TCHES

An energy and area efficient, all digital entropy source compatible with modern standards based on jitter pipelining
Abstract

This paper proposes an energy and area efficient entropy source, suitable for true random number generation, accompanied with a stochastic model in a 28 nm CMOS technology. The design uses a jitter pipelining architecture together with an increased timing resolution to achieve a maximal throughput of 298 Mbit/s and a best energy efficiency of 1.46 pJ/bit at a supply of 0.8 V. The generated random bits pass the NIST SP 800-90B IID tests with a min entropy rate of 0.933 bit/bit, which is more than required by the AIS-31 standard. The all digital design allows for effortless transfer to other technology nodes, taking advantage of all benefits related to further technology scaling.

2022

TCHES

Will You Cross the Threshold for Me? Generic Side-Channel Assisted Chosen-Ciphertext Attacks on NTRU-based KEMs
Abstract

In this work, we propose generic and novel side-channel assisted chosenciphertext attacks on NTRU-based key encapsulation mechanisms (KEMs). These KEMs are IND-CCA secure, that is, they are secure in the chosen-ciphertext model. Our attacks involve the construction of malformed ciphertexts. When decapsulated by the target device, these ciphertexts ensure that a targeted intermediate variable becomes very closely related to the secret key. An attacker, who can obtain information about the secret-dependent variable through side-channels, can subsequently recover the full secret key. We propose several novel CCAs which can be carried through by using side-channel leakage from the decapsulation procedure. The attacks instantiate three different types of oracles, namely a plaintext-checking oracle, a decryptionfailure oracle, and a full-decryption oracle, and are applicable to two NTRU-based schemes, which are NTRU and NTRU Prime. The two schemes are candidates in the ongoing NIST standardization process for post-quantum cryptography. We perform experimental validation of the attacks on optimized and unprotected implementations of NTRU-based schemes, taken from the open-source pqm4 library, using the EM-based side-channel on the 32-bit ARM Cortex-M4 microcontroller. All of our proposed attacks are capable of recovering the full secret key in only a few thousand chosen ciphertext queries on all parameter sets of NTRU and NTRU Prime. Our attacks, therefore, stress on the need for concrete side-channel protection strategies for NTRUbased KEMs.

2022

TCHES

Exploring Feature Selection Scenarios for Deep Learning-based Side-channel Analysis
Abstract

One of the main promoted advantages of deep learning in profiling side-channel analysis is the possibility of skipping the feature engineering process. Despite that, most recent publications consider feature selection as the attacked interval from the side-channel measurements is pre-selected. This is similar to the worst-case security assumptions in security evaluations when the random secret shares (e.g., mask shares) are known during the profiling phase: an evaluator can identify points of interest locations and efficiently trim the trace interval. To broadly understand how feature selection impacts the performance of deep learning-based profiling attacks, this paper investigates three different feature selection scenarios that could be realistically used in practical security evaluations. The scenarios range from the minimum possible number of features (worst-case security assumptions) to the whole available traces.
Our results emphasize that deep neural networks as profiling models show successful key recovery independently of explored feature selection scenarios against first-order masked software implementations of AES-128. First, we show that feature selection with the worst-case security assumptions results in optimal profiling models that are highly dependent on the number of features and signal-to-noise ratio levels. Second, we demonstrate that attacking raw side-channel measurements with small deep neural networks also provides optimal models, which shorten the gap between worst-case security evaluations and online (realistic) profiling attacks. In all explored feature selection scenarios, the hyperparameter search always indicates a successful model with up to eight hidden layers for MLPs and CNNs, suggesting that complex models are not required for the considered datasets. Our results demonstrate the key recovery with less than ten attack traces for all datasets for at least one of the feature selection scenarios. Additionally, in several cases, we can recover the target key with a single attack trace.

2022

TCHES

Redshift: Manipulating Signal Propagation Delay via Continuous-Wave Lasers
Abstract

We propose a new laser injection attack Redshift that manipulates signal propagation delay, allowing for precise control of oscillator frequencies and other behaviors in delay-sensitive circuits. The target circuits have a significant sensitivity to light, and a low-power continuous-wave laser, similar to a laser pointer, is sufficient for the attack. This is in contrast to previous fault injection attacks that use high-powered laser pulses to flip digital bits. This significantly reduces the cost of the attack and extends the range of possible attackers. Moreover, the attack potentially evades sensor-based countermeasures configured for conventional pulse lasers. To demonstrate Redshift, we target ring-oscillator and arbiter PUFs that are used in cryptographic applications. By precisely controlling signal propagation delays within these circuits, an attacker can control the output of a PUF to perform a state-recovery attack and reveal a secret key. We finally discuss the physical causality of the attack and potential countermeasures.

2022

TCHES

Towards a Formal Treatment of Logic Locking
Abstract

Logic locking aims to protect the intellectual property of a circuit from a fabricator by modifying the original logic of the circuit into a new “locked” circuit such that an entity without the key should not be able to learn anything about the original circuit. While logic locking provides a promising solution to outsourcing the fabrication of chips, unfortunately, several of the proposed logic locking systems have been broken. The lack of established secure techniques stems in part from the absence of a rigorous treatment toward a notion of security for logic locking, and the disconnection between practice and formalisms. We seek to address this gap by introducing formal definitions to capture the desired security of logic locking schemes. In doing so, we investigate prior definitional efforts in this space, and show that these notions either incorrectly model the desired security goals or fail to capture a natural “compositional” property that would be desirable in a logic locking system. Finally we move to constructions. First, we show that universal circuits satisfy our security notions. Second, we show that, in order to do better than universal circuits, cryptographic assumptions are necessary.

2022

ASIACRYPT

Full Quantum Equivalence of Group Action DLog and CDH, and More
Abstract

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.

2022

TCC

On the Worst-Case Inefficiency of CGKA
Abstract

Continuous Group Key Agreement (CGKA) is the basis of modern Secure Group Messaging (SGM) protocols. At a high level, a CGKA protocol enables a group of users to continuously compute a shared (evolving) secret while members of the group add new members, remove other existing members, and perform state updates. The state updates allow CGKA to offer desirable security features such as forward secrecy and post-compromise security.
CGKA is regarded as a practical primitive in the real-world. Indeed, there is an IETF Messaging Layer Security (MLS) working group devoted to developing a standard for SGM protocols, including the CGKA protocol at their core. Though known CGKA protocols seem to perform relatively well when considering natural sequences of performed group operations, there are no formal guarantees on their efficiency, other than the O(n) bound which can be achieved by trivial protocols, where n is the number of group numbers. In this context, we ask the following questions and provide negative answers.
1. Can we have CGKA protocols that are efficient in the worst case? We start by answering this basic question in the negative. First, we show that a natural primitive that we call Compact Key Exchange (CKE) is at the core of CGKA, and thus tightly captures CGKA’s worst-case communication cost. Intuitively, CKE requires that: first, n users non-interactively generate key pairs and broadcast their public keys, then, some other special user securely communicates to these n users a shared key. Next, we show that CKE with communication cost o(n) by the special user cannot be realized in a black-box manner from public-key encryption and one-way functions, thus implying the same for CGKA, where n is the corresponding number of group members.
2. Can we realize one CGKA protocol that works as well as possible in all cases? Here again, we present negative evidence showing that no such protocol based on black-box use of public-key encryption and one-way functions exists. Specifically, we show two distributions over sequences of group operations such that no CGKA protocol obtains optimal communication costs on both sequences.