International Association
for Cryptologic Research

We give a first construction of an ϵ-balanced hash family based on linear transformations of vectors in $\mathbb{F}_2$, where ϵ = 1/(2n − 1) for n-bit hash values, regardless of the message size. The parameter n is also the bit length of the input blocks and the internal state, and can be chosen arbitrarily without design changes, This hash family is fast, easily parallelized, and requires no initial setup. A secure message authentication code can be obtained by combining the hash family with a pseudo random function. These features make the hash family attractive for memory integrity protection, while allowing generic use cases.

ASCON is a family of cryptographic primitives for authenticated encryption and hashing introduced in 2015. It is selected as one of the ten finalists in the NIST Lightweight Cryptography competition. Since its introduction, ASCON has been extensively cryptanalyzed, and the results of these analyses can indicate the good resistance of this family of cryptographic primitives against known attacks, like differential and linear cryptanalysis. Proving upper bounds for the differential probability of differential trails and for the squared correlation of linear trails is a standard requirement to evaluate the security of cryptographic primitives. It can be done analytically for some primitives like AES. For other primitives, computer assistance is required to prove strong upper bounds for differential and linear trails. Computer-aided tools can be classified into two categories: tools based on general-purpose solvers and dedicated tools. General-purpose solvers such as SAT and MILP are widely used to prove these bounds, however they seem to have lower capabilities and thus yield less powerful bounds compared to dedicated tools. In this work, we present a dedicated tool for trail search in ASCON. We arrange 2-round trails in a tree and traverse this tree in an efficient way using a number of new techniques we introduce. Then we extend these trails to more rounds, where we also use the tree traversal technique to do it efficiently. This allows us to scan much larger spaces of trails faster than the previous methods using general-purpose solvers. As a result, we prove tight bounds for 3-rounds linear trails, and for both differential and linear trails, we improve the existing upper bounds for other number of rounds. In particular, for the first time, we prove bounds beyond $2^{-128}$ for 6 rounds and beyond $2^{-256}$ for 12 rounds of both differential and linear trails.

While being decentralized, secure, and reliable, Bitcoin and many other blockchain-based cryptocurrencies suffer from scalability issues. One of the promising proposals to address this problem is off-chain payment channels. Since, not all nodes are connected directly to each other, they can use a payment network to route their payments. Each node allocates a balance that is frozen during the channel's lifespan. Spending and receiving transactions will shift the balance to one side of the channel. A channel becomes unbalanced when there is not sufficient balance in one direction. In this case, we say the effective lifespan of the channel has ended. In this paper, we develop a mathematical model to predict the expected effective lifespan of a channel based on the network's topology. We investigate the impact of channel unbalancing on the payment network and individual channels. We also discuss the effect of certain characteristics of payment channels on their lifespan. Our case study on a snapshot of the Lightning Network shows how the effective lifespan is distributed, and how it is correlated with other network characteristics. Our results show that central unbalanced channels have a drastic effect on the network performance.

Recently, Aaronson et al. (arXiv:2009.07450) showed that detecting interference between two orthogonal states is as hard as swapping these states. While their original motivation was from quantum gravity, we show its applications in quantum cryptography.

1. We construct the first public key encryption scheme from cryptographic non-abelian group actions. Interestingly, ciphertexts of our scheme are quantum even if messages are classical. This resolves an open question posed by Ji et al. (TCC ’19). We construct the scheme through a new abstraction called swap-trapdoor function pairs, which may be of independent interest.

2. We give a simple and efficient compiler that converts the flavor of quantum bit commitments. More precisely, for any prefix X, Y $\in$ {computationally,statistically,perfectly}, if the base scheme is X-hiding and Y-binding, then the resulting scheme is Y-hiding and X-binding. Our compiler calls the base scheme only once. Previously, all known compilers call the base schemes polynomially many times (Crépeau et al., Eurocrypt ’01 and Yan, Asiacrypt ’22). For the security proof of the conversion, we generalize the result of Aaronson et al. by considering quantum auxiliary inputs.

Cloud storage and computing offers significant convenience and management efficiency in the information era. Privacy protection is a major challenge in cloud computing. Public key encryption with keyword search (PEKS) is an ingenious tool for ensuring privacy and functionality in certain scenario, such as ensuring privacy for data retrieval appearing in the cloud computing. Despite many attentions received, PEKS schemes still face several challenges in practical applications, such as low computational efficiency, high end-to-end delay, vulnerability to inside keyword guessing attacks(IKGA) and key management defects in the multi-user environment.

In this work, we introduce three Ring-LWE/ISIS based PEKS schemes: (1) Our basic PEKS scheme achieves high level security in the standard model. (2) Our PAEKS scheme utilizes the sender's private key to generate an authentication when encrypting, which can resist IKGA. (3) Our IB-PAEKS scheme not only can resist IKGA, but also significantly reduces the complexity of key management in practical applications. Experimental results indicate that the first scheme provides lower end-to-end delay and higher computational efficiency compared to similar ones, and that our last two schemes can provide more secure properties with little additional overhead.

Since the formalization of Verifiable Delay Functions (VDF) by Boneh et al. in 2018, VDFs have been adopted for use in blockchain consensus protocols and random beacon implementations. However, the impending threat to VDF-based applications comes in the form of Shor’s algorithm running on quantum computers in the future which can break the discrete logarithm and integer factorization problems that existing VDFs are based on. Clearly, there is a need for quantum-secure VDFs. In this paper, we propose ZKBdf, which makes use of ZKBoo, a zero knowledge proof system for verifiable computation, as the basis for realizing a quantum-secure VDF. We describe the algorithm, provide the security proofs, implement the scheme and measure the execution and size requirements. In addition, as ZKBdf extends the standard VDF with an extra “Prover-secret” feature, new VDF use-cases are also explored.

The promise of scalable quantum computing is causing major upheaval in the domain of cryptography and security. In this perspective paper, we review the progress towards the realization of large-scale quantum computing. We further summarize the imminent threats towards existing cryptographic primitives. To address this challenges, there is a consolidated effort towards the standardization of new cryptographic primitives, namely post-quantum cryptography (PQC). We discuss the underlying mathematical problems that define different classes of PQC candidates, and their resistance to an adversary having access to large Quantum computer. In parallel to this thread of research, several classical cryptographic primitives have been ported to the Quantum world as well. We discuss, in that context - Quantum Key Distribution (QKD), Physically Unclonable Function (PUF) and True Random Number Generator (TRNG). For those implementations, we take a sneak preview in the resulting implementation-related vulnerabilities.

We present a full proof of security of the original random oblivious transfer extension protocol of Keller, Orsini, and Scholl (CRYPTO '15), without altering that protocol as written. Our result circumvents a recent negative result of Roy (CRYPTO '22), which shows that a key lemma in the original proof of KOS is false. Our proof leverages a new simulation strategy, and a careful analysis of that protocol's "correlation check". We thus reestablish evidence of security for this important, widely used protocol.

In this paper, we present an original algorithm to generate session keys and a subsequent generalized ElGamal-type cryptosystem. The scheme here presented has been designed to prevent both linear and brute force attacks using on one hand rectangular matrices, and on the other achieving very high complexity. Moreover, analytical attacks are NP-hard. An interesting result of our protocol is that the secret shared key is an invariant obtained from both public and private information using usual multiplications of matrices, either in numerical or F_(2^m ) polynomial fields so that both sorts of operations could be eventually combined to increase even more the security against classical and quantum attacks.

Distributed key generation (DKG) protocols are an essential building block for threshold cryptosystems. Many DKG protocols tolerate up to $t_s
In this work, we ask whether one can design a protocol that achieves security guarantees in either scenario. We show a complete characterization of network-agnostic DKG protocols, showing that the tight bound is $t_a+2t_s
Our protocols incur the same communication complexity as state-of-the-art DKG and MPC protocols with optimal resilience in their respective purely synchronous and asynchronous settings, thereby showing that network-agnostic security comes for free.

A functional commitment scheme enables a user to concisely commit to a function from a specified family, then later concisely and verifiably reveal values of the function at desired inputs. Useful special cases, which have seen applications across cryptography, include vector commitments and polynomial commitments.

To date, functional commitments have been constructed (under falsifiable assumptions) only for functions that are essentially linear, with one recent exception that works for arbitrarily complex functions. However, that scheme operates in a strong and non-standard model, requiring an online, trusted authority to generate special keys for any function inputs that may need to be opened.

In this work, we give the first functional commitment scheme for nonlinear functions---indeed, for all functions of any bounded complexity---under a standard setup and a falsifiable assumption. More specifically, the setup is "transparent," requiring only public randomness (and not any trusted entity), and the assumption is the hardness of the standard Short Integer Solution (SIS) lattice problem. Our construction also has other attractive features, including: stateless updates via generic composability; excellent asymptotic efficiency for the verifier, and also for the committer in important special cases like vector and polynomial commitments, thanks to preprocessing (which can even be outsourced to an untrusted party); and post-quantum security, since it is based on SIS.

Being capable of updating cryptographic algorithms is an inevitable and essential practice in cryptographic engineering. This cryptographic agility, as it has been called, is a fundamental desideratum for long term cryptographic system security that still poses significant challenges from a modeling perspective. For instance, current formulations of agility fail to express the fundamental security that is expected to stem from timely implementation updates, namely the fact that the system retains some of its security properties provided that the update is performed prior to the deprecated implementation becoming exploited.

In this work we put forth a novel framework for expressing updateability in the context of cryptographic primitives within the universal composition model. Our updatable ideal functionality framework provides a general template for expressing the security we expect from cryptographic agility capturing in a fine-grained manner all the properties that can be retained across implementation updates. We exemplify our framework over two basic cryptographic primitives, digital signatures and non-interactive zero-knowledge (NIZK), where we demonstrate how to achieve updateability with consistency and backwards-compatibility across updates in a composable manner. We also illustrate how our notion is a continuation of a much broader scope of the concept of agility introduced by Acar, Belenkiy, Bellare, and Cash in Eurocrypt 2010 in the context of symmetric cryptographic primitives.

We share two small but general observations on the vectorization problem for group actions, which appear to have been missed by the existing literature. The first observation is pre-quantum: explicit examples show that, for classical adversaries, the vectorization problem cannot in general be reduced to the parallelization problem. The second observation is post-quantum: by combining a method for solving systems of linear disequations due to Ivanyos with a Kuperberg-style sieve, one can solve the hidden shift problem, and therefore the vectorization problem, for any finite abelian $2^tp^k$-torsion group in polynomial time and using mostly classical work; here $t, k$ are any fixed non-negative integers and $p$ is any fixed prime number.

A functional commitment (FC) scheme allows one to commit to a vector $\vec{x}$ and later produce a short opening proof of $(f, f(\vec{x}))$ for any admissible function $f$. The security of FC schemes, called evaluation binding, ensures that it is hard to open the commitment to the same function $f$ and different outputs $y \neq y'$. Unlike succinct non-interactive arguments (SNARG) which provide a stronger soundness guarantee but typically require non-falsifiable assumptions, the evaluation binding of FC schemes can often be based on falsifiable assumptions and is sufficient for certain applications such as constructing homomorphic signatures (HS). Since their inception, FC schemes supporting ever more expressive classes of functions have been proposed, with the state-of-the-art supporting low-degree polynomial maps.

In this work we construct the first FC schemes for circuits, based on either pairing-based or lattice-based falsifiable assumptions. Our FCs require to fix a-priori only the maximal width of the circuit to be evaluated, and have opening proofs whose size only depends on the depth of the circuit. We obtain our results in two steps. First, we introduce a new tool which we call chainable functional commitment (CFC), and show that CFCs for quadratic polynomial maps generically imply an FC for bounded-width circuits. Then, we show how to efficiently instantiate CFCs for quadratic polynomial maps over either pairing groups or lattices.

Using a recent transformation from FC to HS, we obtain the first pairing- and lattice-based constructions of HS for bounded-width, but unbounded-depth, circuits. Prior to this work, the only HS for general circuits is lattice-based and requires bounding the circuit depth at setup time.

In this paper, we perform a systematic study of functions $f: \mathbb{Z}_{p^e} \to \mathbb{Z}_{p^e}$ and categorize those functions that can be represented by a polynomial with integer coefficients. More specifically, we cover the following properties: necessary and sufficient conditions for the existence of an integer polynomial representation; computation of such a representation; and the complete set of equivalent polynomials that represent a given function.

As an application, we use the newly developed theory to speed up bootstrapping for the BGV and BFV homomorphic encryption schemes. The crucial ingredient underlying our improvements is the existence of null polynomials, i.e. non-zero polynomials that evaluate to zero in every point. We exploit the rich algebraic structure of these null polynomials to find better representations of the digit extraction function, which is the main bottleneck in bootstrapping. As such, we obtain sparse polynomials that have 50% fewer coefficients than the original ones. In addition, we propose a new method to decompose digit extraction as a series of polynomial evaluations. This lowers the time complexity from $\mathcal{O}(\sqrt{pe})$ to $\mathcal{O}(\sqrt{p}\sqrt[^4]{e})$ for digit extraction modulo $p^e$, at the cost of a slight increase in multiplicative depth. Overall, our implementation in HElib shows a significant speedup of a factor up to 2.6 over the state-of-the-art.

We unify the state-of-the-art bootstrapping algorithms for BGV and BFV in a single framework, and show that BGV and BFV can be bootstrapped with identical complexity. This result corrects a claim by Chen and Han (Eurocrypt 2018) that BFV is more efficient to bootstrap than BGV. We also fix an error in their optimized procedure for power-of-two cyclotomics, which occurs for some parameter sets.

Our analysis is simpler, yet more general than earlier work, in that it simultaneously covers both BGV and BFV. Furthermore, we also design and implement a high-level open source software library for bootstrapping in the Magma Computer Algebra System. It is the first library to support both BGV and BFV bootstrapping in full generality, with all recent techniques (including the above fixes) and trade-offs.

A cryptographic accumulator is a space- and time-efficient data structure with associated algorithms used for secure membership testing. In the growing space of digital credentials, accumulators found in managing a set of valid credentials, giving efficient and anonymous methods for credential holders to prove their validity. Unlike traditional credentials like digital signatures, one can easily revoke credentials with an accumulator; however, each revocation forces existing credential holders to engage in an expensive update process. Previous works make this faster and easier by sacrificing anonymity. To improve performance without compromising privacy, we present ALLOSAUR, a multi-party accumulator based on pairings. In ALLOSAUR, we eliminate the cost of accumulating new credentials, let "credential managers" manage the accumulator values with secure multiparty computation, and allow anonymous credential updates with a square-root reduction in communication costs as compared to existing work.

A deployed digital credential system is a vast and complicated system, and existing formalisms do not fully address the scope or power of a real-world adversary. We develop a thorough UC-style formalism that allows arbitrary malicious behaviour from an adversary controlling a minority of credential managers and arbitrary numbers of users, credentials, and verifiers. In our new formalism we present a novel definition of privacy that captures as much anonymity as possible while accounting for inevitable losses from interaction with the system. The detail in our formalism reveals real-world issues in existing accumulator constructions, all of which ALLOSAUR avoids.

Our proof-of-concept implementation can update over 1000 revocations with less than half a second of total computation and 16 kB communication, at least a 5x improvement over the previous state-of-the-art in both metrics.

Post-quantum cryptography represents a category of cryptosystems resistant to quantum algorithms. Recently, NIST launched a process to standardize one or more of such algorithms in the key encapsulation mechanism and signature categories. Such schemes are under the scrutiny of their mathematical security, but they are not side-channel secure at the algorithm level. That is why their side-channel vulnerabilities must be assessed by the research community. In this paper, we present a non-profiled correlation electromagnetic analysis against an FPGA implementation of the chosen NIST key-encapsulation mechanism standard, CRYSTALS-Kyber. The attack correlates an electromagnetic radiation model of the polynomial multiplication execution with the captured traces. With 166,620 traces, this attack correctly recovers 100% of the subkeys. Furthermore, a countermeasure is presented for securing the target implementation against the presented attack.

Success Rate (SR) is empirically and theoretically a common metric for evaluating the performance of side-channel attacks. Intuitive expressions of success rate are desirable since they reveal and explain the functional dependence on relevant parameters, such as number of measurements and Signal-to-Noise Ratio (SNR), in a straightforward manner. Meanwhile, existing works more or less expose unsolved fundamental problems, such as strong leakage assumption, difficulty in interpretation of principle, inaccurate evaluation, and inconsideration of high-order SR. In this paper, we first provide an intuitive framework that statistical tests embedded in different univariate DPA attacks are unified as analyzing and comparing visualized vectors in a Euclidean space by using different easy-to-understand metrics. Then, we establish a unified framework to abstract and convert the security evaluations to the problem of finding a boundary in the Euclidean space. With expressions of the boundary, judging whether a DPA attack succeeds in sense of $o^{th}$-order becomes fairly efficient and intuitive, and the corresponding SR can be calculated theoretically by integral. Finally, we propose an algorithm that is capable of estimating arbitrary order of SR effectively. Our experimental results verify the theory and highlight the superiority. We believe our research raises many new perspectives for comparing and evaluating side-channel attacks, countermeasures and implementations.

A hash-and-sign signature based on preimage-sampleable function (PSF) (Gentry et al. [STOC 2008]) is secure in the Quantum Random Oracle Model (QROM) if the PSF is collision-resistant (Boneh et al. [ASIACRYPT 2011]) or one-way (Zhandry [CRYPTO 2012]). However, trapdoor functions (TDFs) in code-based and multivariate-quadratic-based (MQ-based) signatures are not PSFs; for example, underlying TDFs of the Courtois-Finiasz-Sendrier (CFS), Unbalanced Oil and Vinegar (UOV), and Hidden Field Equations (HFE) signatures are not surjection. Thus, such signature schemes adopt probabilistic hash-and-sign with retry. This paradigm is secure in the (classical) Random Oracle Model (ROM), assuming that the underlying TDF is non-invertible; that is, it is hard to find a preimage of a given random value in the range (e.g., Sakumoto et al. [PQCRYPTO 2011] for the modified UOV/HFE signatures). Unfortunately, there is no known security proof for the probabilistic hash-and-sign with retry in the QROM. We give the first security proof for the probabilistic hash-and-sign with retry in the QROM, assuming that the underlying non-PSF TDF is non-invertible. Our reduction from the non-invertibility is tighter than the existing ones that apply to only signature schemes based on PSFs. We apply the security proof to code-based and MQ-based signatures. Moreover, we extend the proof into the multi-key setting by using prefix hashing (Duman et al. [ACM CCS 2021]).