International Association
for Cryptologic Research

Unique signatures are digital signatures with exactly one unique and valid signature for each message. The security reduction for most unique signatures has a natural reduction loss (in the existentially unforgeable against chosen-message attacks, namely EUF-CMA, security model under a non-interactive hardness assumption). In Crypto 2017, Guo {\it et al.} proposed a particular chain-based unique signature scheme where each unique signature is composed of $n$ BLS signatures computed sequentially like a blockchain. Under the computational Diffie-Hellman assumption, their reduction loss is $n\cdot q_H^{1/n}$ for $q_H$ hash queries and it is logarithmically tight when $n=\log{q_H}$. However, it is currently unknown whether a better reduction than logarithmical tightness for the chain-based unique signatures exists.

We show that the proposed chain-based unique signature scheme by Guo {\it et al.} must have the reduction loss $q^{1/n}$ for $q$ signature queries when each unique signature consists of $n$ BLS signatures. We use a meta reduction to prove this lower bound in the EUF-CMA security model under any non-interactive hardness assumption, and the meta-reduction is also applicable in the random oracle model. We also give a security reduction with reduction loss $4\cdot q^{1/n}$ for the chain-based unique signature scheme (in the EUF-CMA security model under the CDH assumption). This improves significantly on previous reduction loss $n\cdot q_H^{1/n}$ that is logarithmically tight at most. The core of our reduction idea is a {\em non-uniform} simulation that is specially invented for the chain-based unique signature construction.

We consider the McEliece cryptosystem with a binary Goppa code $C \subset \mathbb{F}_2^n$ specified by an irreducible Goppa polynomial $g(x) \in \mathbb{F}_{2^m}[x]$ and Goppa points $(\alpha_1, \ldots, \alpha_n) \in \mathbb{F}_{2^m}^n$. Since $g(x)$ together with the Goppa points allow for efficient decoding, these parameters form McEliece secret keys. Such a Goppa code $C$ is an $(n-tm)$-dimensional subspace of $\mathbb{F}_2^n$, and therefore $C$ has co-dimension $tm$. For typical McEliece instantiations we have $tm \approx \frac n 4$.

We show that given more than $tm$ entries of the Goppa point vector $(\alpha_1, \ldots, \alpha_n)$ allows to recover the Goppa polynomial $g(x)$ and the remaining entries in polynomial time. Hence, in case $tm \approx \frac n 4$ roughly a fourth of a McEliece secret key is sufficient to recover the full key efficiently.

Let us give some illustrative numerical examples. For ClassicMcEliece with $(n,t,m)=(3488,64,12)$ on input $64\cdot 12+1=769$ Goppa points, we recover the remaining $3488-769=2719$ Goppa points in $\mathbb{F}_{2^{12}}$ and the degree-$64$ Goppa polynomial $g(x) \in \mathbb{F}_{2^{12}}[x]$ in $1$ minute.

For ClassicMcEliece with $(n,t,m)=(8192,128,13)$ on input $128\cdot 13+1=1665$ Goppa points, we recover the remaining $8192-1665=6529$ Goppa points in $\mathbb{F}_{2^{13}}$ and the degree-$128$ Goppa polynomial $g(x) \in \mathbb{F}_{2^{13}}[x]$ in $5$ minutes.

Our results also extend to the case of erroneous Goppa points, but in this case our algorithms are no longer polynomial time.

Functional commitments (Libert et al.~[ICALP'16]) allow a party to commit to a vector $\vec v$ of length $n$ and later open the commitment at functions of the committed vector succinctly, namely with communication logarithmic or constant in $n$. Existing constructions of functional commitments rely on trusted setups and have either $O(1)$ openings and $O(n)$ parameters, or they have short parameters generatable using public randomness but have $O(\log n)$-size openings. In this work, we ask whether it is possible to construct functional commitments in which both parameters and openings can be of constant size. Our main result is the construction of the first FC schemes matching this complexity. Our constructions support the evaluation of inner products over small integers; they are built using groups of unknown order and rely on succinct protocols over these groups that are secure in the generic group and random oracle model.

The most common application for side-channel attacks is the extraction of secret information, such as key material, from the implementation of a cryptographic algorithm. However, using side-channel information, we can extract other types of information related to the internal state of a computing device, such as the instructions executed and the content of registers. We used machine learning to build a side-channel disassembler for the ARM-Cortex M0 architecture, which can extract the executed instructions from the power traces of the device. Our disassembler achieves a success rate of 99% under ideal conditions and 88.2% under realistic conditions when distinguishing between groups of instructions. We also provide an overview of the lessons learned in relation to data preparation and noise minimization techniques.

In this paper we study the effect of using small prime numbers within the Joye-Libert public key encryption scheme. We introduce two novel versions and prove their security. We further show how to choose the system's parameters such that the security results hold. Moreover, we provide a practical comparison between the cryptographic algorithms we introduced and the original Joye-Libert cryptosystem.

Protocols solving the Distributed Discrete Logarithm (DDLog) problem are a core component of many recent constructions of group-based homomorphic secret sharing schemes. On a high-level, these protocols enable two parties to transform multiplicative shares of a secret into additive share locally without any communication. Due to their important applications, various generic optimized DDLog protocols were proposed in the literature, culminating in the asymptotically optimal generic protocol of Dinur, Keller, and Klein (J. Cryptol. 2020) solving DDLog in time $T$ with error probability $O(W/T^2)$ when the magnitude of the secret is bounded by $W$.

Given that DDLog is solved repeatedly with respect to a fixed group in its applications, a natural approach for improving the efficiency of DDLog protocols could be via leveraging some precomputed group-specific advice. To understand the limitations of this approach, we revisit the distributed discrete logarithm problem in the preprocessing model and study the possible time-space trade-offs for DDLog in the generic group model. As our main result, we show that, in a group of size $N$, any generic DDLog protocol for secrets of magnitude $W$ with parties running in time $T$ using precomputed group-specific advice of size $S$ has success probability \[ \epsilon = O\left(\dfrac{T^2}{W} + \dfrac{\max\{S,\log W\} \cdot T^2}{N}\right). \] Thus, assuming $N \geq W \log W$, we get a lower bound $ST^2= \Omega(\epsilon N)$ on the time-space trade-off for DDLog protocols using large advice of size $S= \Omega(N/W)$. Interestingly, for DDLog protocols using \emph{small advice} of size $S=O(N/W)$, we get a lower bound $T^2=\Omega(\epsilon W)$ on the running time, which, in the constant-error regime, asymptotically matches the running time of the DDLog protocol \emph{without any advice} of Dinur et al. (J. Cryptol. 2020). In other words, we show that generic DDLog protocols achieving constant success probability do not benefit from any advice of size $S= O(N/W)$ in the online phase of the DDLog problem.

Verifiable Delay Functions (VDFs) are a set of new crypto- graphic schemes ensuring that an agent has spent some time (evaluation phase) in a unparalleled computation. A key requirement for such a construction is that the verification of the computation’s correctness has to be done in a significantly shorter time than the evaluation phase. This has led VDFs to recently gain exposure in large-scale decentralized projects as a core component of consensus algorithms or spam-prevention mechanisms. In this work, due to the increasing relevance and the lack of literature, we will focus on the optimization of the verification phase of Wesolowski’s VDF and provide a three-axis of improvement concerning multi-exponentiation computation, prime testing techniques, and hash- ing tricks. We will show that our optimizations reduce the computation time of the verification phase between 12% and 35% for the range of parameters considered.

This paper proposes a new block cipher called HARPOCRATES, which is different from traditional SPN, Feistel, or ARX designs. The new design structure that we use is called the substitution convolution network. The novelty of the approach lies in that the substitution function does not use fixed S-boxes. Instead, it uses a key-driven lookup table storing a permutation of all 8-bit values. If the lookup table is sufficiently randomly shuffled, the round sub-operations achieve good confusion and diffusion to the cipher. While designing the cipher, the security, cost, and performances are balanced, keeping the requirements of encryption of data-at-rest in mind. The round sub-operations are massively parallelizable and designed such that a single active bit may make the entire state (an 8 × 16 binary matrix) active in one round. We analyze the security of the cipher against linear, differential, and impossible differential cryptanalysis. The cipher’s resistance against many other attacks like algebraic attacks, structural attacks, and weak keys are also shown. We implemented the cipher in software and hardware; found that the software implementation of the cipher results in better throughput than many well-known ciphers. Although HARPOCRATES is appropriate for the encryption of data-at-rest, it is also well-suited in data-in-transit environments.

An important open problem in supersingular isogeny-based cryptography is to produce, without a trusted authority, concrete examples of ''hard supersingular curves,'' that is, concrete supersingular curves for which computing the endomorphism ring is as difficult as it is for random supersingular curves. Or, even better, to produce a hash function to the vertices of the supersingular ℓ-isogeny graph which does not reveal the endomorphism ring, or a path to a curve of known endomorphism ring. Such a hash function would open up interesting cryptographic applications. In this paper, we document a number of (thus far) failed attempts to solve this problem, in the hopes that we may spur further research, and shed light on the challenges and obstacles to this endeavour. The mathematical approaches contained in this article include: (i) iterative root-finding for the supersingular polynomial; (ii) gcd's of specialized modular polynomials; (iii) using division polynomials to create small systems of equations; (iv) taking random walks in the isogeny graph of abelian surfaces; and (v) using quantum random walks.

Permutation polynomials of finite fields have many applications in Coding Theory, Cryptography and Combinatorics. In the first part of this paper we present a new family of local permutation polynomials based on a class of symmetric subgroups without fixed points, the so called e-Klenian groups. In the second part we use the fact that bivariate local permutation polynomials define Latin Squares, to discuss several constructions of Mutually Orthogonal Latin Squares (MOLS) and, in particular, we provide a new family of MOLS on size a prime power.

As integrated circuit (IC) design and manufacturing have become highly globalized, hardware security risks become more prominent as malicious parties can exploit multiple stages of the supply chain for profit. Two potential targets in this chain are third-party intellectual property (3PIP) vendors and their customers. Untrusted parties can insert hardware Trojans into 3PIP circuit designs that can both alter device functionalities when triggered or create a side channel to leak sensitive information such as cryptographic keys. To mitigate this risk, the absence of Trojans in 3PIP designs should be verified before integration, imposing a major challenge for vendors who have to argue their IPs are safe to use, while also maintaining the privacy of their designs before ownership is transferred. To achieve this goal, in this work we employ modern cryptographic protocols for zero-knowledge proofs and enable 3PIP vendors prove an IP design is free of Trojan triggers without disclosing the corresponding netlist. Our approach uses a specialized circuit compiler that transforms arbitrary netlists into a zero-knowledge-friendly format, and introduces a versatile Trojan detection module that maintains the privacy of the actual netlist. We evaluate the effectiveness of our methodology using selected benchmarks.

Homomorphic encryption is one of the most secure solutions for processing sensitive information in untrusted environments, and there have been many recent advances towards its efficient implementation for the evaluation of linear functions and approximated arithmetic. However, the practical performance when evaluating arbitrary (nonlinear) functions is still a major challenge for HE schemes. The TFHE scheme [Chillotti et al., 2016] is the current state-of-the-art for the evaluation of arbitrary functions, and, in this work, we focus on improving its performance. We divide this paper into two parts. First, we review and implement the main techniques to improve performance or error behavior in TFHE proposed so far. For many, this is the first practical implementation. Then, we introduce novel improvements to several of them and new approaches to implement some commonly used procedures. We also show which proposals can be suitably combined to achieve better results. We provide a single library containing all the reviewed techniques as well as our original contributions. Our implementation is up to 1.2 times faster than previous ones with a similar optimization level, and our novel techniques provide speedups of up to 2.83 times on algorithms such as the Full-Domain Functional Bootstrap (FDFB).

In this paper, we propose the first key-recovery side-channel attack on Classic McEliece, a KEM finalist in the NIST Post-quantum Cryptography Standardization Project. Our novel idea is to design an attack algorithm where we submit special ciphertexts to the decryption oracle that correspond to cases of single errors. Decoding of such cipher-texts involves only a single entry in a large secret permutation, which is part of the secret key. Through an identified leakage in the additive FFT step used to evaluate the error locator polynomial, a single entry of the secret permutation can be determined. Reiterating this for other entries leads to full secret key recovery.

The attack is described using power analysis both on the FPGA reference implementation and a software implementation running on an ARM Cortex-M4. We use a machine-learning-based classification algorithm to determine the error locator polynomial from a single trace. The attack is fully implemented and evaluated in the Chipwhisperer framework and is successful in practice. For the smallest parameter set, it is using about 300 traces for partial key recovery and less than 800 traces for full key recovery, in the FPGA case. A similar number of traces are required for a successful attack on the ARM software implementation.

Automated search methods based on Satisfiability Modulo Theories (SMT) problems are being widely used to evaluate the security of block ciphers against distinguishing attacks. While these methods provide a systematic and generic methodology, most of their software implementations are limited to a small set of ciphers and attacks, and extending these implementations requires significant effort and expertise.

In this work we present CASCADA, an open-source Python library to evaluate the security of cryptographic primitives, specially block ciphers, against distinguishing attacks with bit-vector SMT solvers. The tool CASCADA implements the bit-vector property framework herein proposed and several SMT-based automated search methods to evaluate the security of ciphers against differential, related-key differential, rotational-XOR, impossible-differential, impossible-rotational-XOR, related-key impossible-differential, linear and zero-correlation cryptanalysis. The library CASCADA is the result of a huge engineering effort, and it provides many functionalities, a modular design, an extensive documentation and a complete suite of tests.

ARX algorithms are a class of symmetric-key algorithms constructed by Addition, Rotation, and XOR. To evaluate the resistance of an ARX cipher against differential and impossible-differential cryptanalysis, the recent automated methods employ constraint satisfaction solvers to search for optimal characteristics or impossible differentials. The main difficulty in formulating this search is finding the differential models of the non-linear operations. While an efficient bit-vector differential model was obtained for the modular addition with two variable inputs, no differential model for the modular addition by a constant has been proposed so far, preventing ARX ciphers including this operation from being evaluated with automated methods.

In this paper, we present the first bit-vector differential model for the $n$-bit modular addition by a constant input. Our model contains $O(\log_2(n))$ basic bit-vector constraints and describes the binary logarithm of the differential probability. We describe an SMT-based automated method that includes our model to search for differential characteristics of ARX ciphers including constant additions. We also introduce a new automated method for obtaining impossible differentials where we do not search over a small pre-defined set of differences, such as low-weight differences, but let the SMT solver search through the space of differences. Moreover, we implement both methods in our open-source tool \texttt{ArxPy} to find characteristics and impossible differentials of ARX ciphers with constant additions in a fully automated way. As some examples, we provide related-key impossible differentials and differential characteristics of TEA, XTEA, HIGHT, LEA, SHACAL-1, and SHACAL-2, which achieve better results compared to previous works.

Implantable Medical Devices (IMDs) are widely deployed today and often use wireless communication. Establishing a secure communication channel to these devices is vital, however, also challenging in practice. To address this issue, numerous researchers have proposed IMD key exchange protocols, in particular ones that leverage an Out-Of-Band (OOB) channel such as audio, vibration and physiological signals. These solutions have advantages over traditional key exchange, e.g., their plug-and-play nature. However, such protocols are often constructed in an ad-hoc manner and lack stringent evaluation of their security, usability and deployability properties. In this paper, we systematize this area and derive a solid theoretical footing to compare different OOB-based approaches. We review related work in that light and show the shortcomings of previous approaches. We then make the core observation that security imperfections in OOB channels can be mitigated by incorporating password-authenticated key agreement. Accordingly, we propose a new construction for OOB key exchange and formalize the security level. We then derive three protocols from it that only require an inertial sensor in the IMD, which is already available in advanced devices. We analyze those protocols with the proposed formalism to highlight shortcomings and advantages depending on specific practical scenarios.

Bulletproofs++ is a new protocol based on Bulletproofs and Bulletproofs+ for shorter range proofs and confidential transactions with multiple types of currency supporting multiparty proving. Both the range proofs and confidential transactions use a permutation argument based on the logarithmic derivative of a polynomial encoding the elements of a multiset of field elements. This protocol makes the multiplicities legible to the proof system and is linear in the elements of the multiset.

Using the permutation argument, as well as a new variant of the weighted inner product argument for weighted norms, Bulletproofs++ range proofs can support larger bases and achieve much smaller witness sizes. For a 64 bit range, representing the value as 16 hexadecimal digits reduces the length of the witness per commitment by a factor of approximately 6, asymptotically approaching 8 as the number of values increases. The proof size for a single value using Curve25519 is 416 bytes, which is 160 bytes smaller than Bulletproofs+. This technique has a small asymptotic affect on the witness size, going from O(n) to O(n/log n) where n is the number of bits required to encode all the values to be proven.

For confidential transactions, the ``elements" of the multiset are the types of currency and the multiplicities are the amounts for each input. Since the argument is linear in the elements of the set, multiple provers can show that all the inputs and outputs for a transaction satisfy typed conservation of money without breaking their mutual privacy. This confidential transaction protocol has essentially the same structure as the generic base range proof and can be added to a range proof at minimal additional cost to make a confidential transaction protocol.

Digital signature is an essential primitive in cryptography, which can be used as the digital analogue of handwritten signatures but also as a building block for more complex systems. In the latter case, signatures with specific features are needed, so as to smoothly interact with the other components of the systems, such as zero-knowledge proofs. This has given rise to so-called signatures with efficient protocols, a versatile tool that has been used in countless applications. Designing such signatures is however quite difficult, in particular if one wishes to withstand quantum computing. We are indeed aware of only one post-quantum construction, proposed by Libert et al. at Asiacrypt'16, yielding very large signatures and proofs. In this paper, we propose a new construction that can be instantiated in both standard lattices and structured ones, resulting in each case in dramatic performance improvements. In particular, the size of a proof of message-signature possession, which is one of the main metrics for such schemes, can be brought down to less than 650 KB. As our construction retains all the features expected from signatures with efficient protocols, it can be used as a drop-in replacement in all systems using them, which mechanically improves their own performance, and has thus an impact on many applications.

Indifferentiability is a powerful notion in cryptography. If a construction is proven to be indifferentiable from an ideal object, it can under certain assumptions instantiate that ideal object in higher-level constructions. Indifferentiability is a particularly useful model for cryptographic hash functions, and myriad results are known proving that a hash function behaves like a random oracle under the assumption that the underlying primitive (typically a compression function, a block cipher, or a permutation) is random. Recently, advances have been made in proving indifferentiability of one-way functions with fixed input length. One such example is truncation of a permutation. If one evaluates a random permutation on an input value concatenated with a fixed initial value, and truncates the output, one obtains a construction that is indifferentiable from a random function up to a certain bound (Dodis et al., FSE 2009; Choi et al., ASIACRYPT 2019). Security of this construction, however, is in part determined by the length of the initial value; omission of this fixed value yields an insecure construction.

In this paper, we reconsider truncation of a permutation, and prove that the construction is indifferentiable from a random oracle, even if this fixed initial value is replaced by a randomized value. This randomized value may be the same for different evaluations of the construction, or freshly generated, up to the discretion of the adversary. The security level is the same as that of truncation with fixed initial value, up to collisions in the randomized value.

We show that our construction has immediate implications in the context of parallel variable-length digest generation. In detail, we describe Cascade-MGF, that operates on top of any cryptographic hash function and uses the hash function output as randomized initial value in truncation. We demonstrate that Cascade-MGF compares favorably over earlier parallel variable-length digest generation constructions, namely Counter-MGF and Chained-MGF, in almost all settings.

ver the last years, the rise of the IoT, and the connection of mobile - and hence physically accessible - devices, immensely enhanced the demand for fast and secure hardware implementations of cryptographic algorithms which offer thorough protection against SCA attacks. Among a variety of proposed countermeasures against SCA, masking has transpired to be a promising candidate, attracting significant attention in both, academia and industry. Here, abstract adversary models have been derived, aiming to accurately model real-world attack scenarios, while being sufficiently simple to enable formally proving the SCA resilience of masked implementations on an algorithmic level. In the context of hardware implementations, the robust probing model has become highly relevant for proving SCA resilience due to its capability to model physical defaults like glitches and data transitions. As constructing a correct and secure masked variant of large and complex circuits is a challenging task, a new line of research has recently emerged, aiming to design small, masked subcircuits - realizing for instance a simple AND gate - which still guarantee security when composed to a larger circuit. Although several designs realizing such composable subcircuits - commonly referred to as gadgets - have been proposed, negligible research was conducted in order to find trade-offs between different overhead metrics, like randomness requirement, latency, and area consumption. In this work, we present HPC3, a hardware gadget which is trivially composable under the notion of PINI in the glitch-extended robust probing model. HPC3 realizes a two-input AND gate in one clock cycle which is generalized for any arbitrary security order. Existing state-of-the-art PINI gadgets either require a latency of two clock cycles or are limited to first-order security. In short, HPC3 enables the designer to trade double the randomness for half the latency compared to existing gadgets, providing high flexibility and enabling the designer to gain significantly more speed in real-time applications.