International Association
for Cryptologic Research

The modular squaring operation has attracted significant attention due to its potential in constructing cryptographic time-lock puzzles and verifiable delay functions. In such applications, it is important to understand precisely how quickly a modular squaring operation can be computed, even in parallel on dedicated hardware.

We use tools from circuit complexity and number theory to prove concrete numerical lower bounds for squaring on a parallel machine, yielding nontrivial results for practical input bitlengths. For example, for $n=2048$, we prove that every logic circuit (over AND, OR, NAND, NOR gates of fan-in two) computing modular squaring on all $n$-bit inputs (and any modulus that is at least $2^{n-1}$) requires depth (critical path length) at least $12$. By a careful analysis of certain exponential Gauss sums related to the low-order bit of modular squaring, we also extend our results to the average case. For example, our results imply that every logic circuit (over any fan-in two basis) computing modular squaring on at least $76\%$ of all $2048$-bit inputs (for any RSA modulus that is at least $2^{n-1}$) requires depth at least $9$.

We present MAGIC, a mode for authenticated encryption that simultaneously supports encryption, message authentication and error correction, all with the same code. In MAGIC, the same code employed for cryptographic integrity is also the parity used for error correction. To correct errors, MAGIC employs the Galois Hash transformation, which due to its bit linearity can perform corrections in a similar way as other codes do (e.g., Reed Solomon). To provide a cryptographically strong MAC, MAGIC encrypts the output of the Galois Hash using a secret key. To analyze the security of this construction we adapt the definition of the MAC adversary so that it is applicable to systems that combine message authentication with error correction. We demonstrate that MAGIC offers security in the order of O(2^(N/2)) with N being the tag size.

In this report, we analyze the hardware implementations of 10 candidates for Round 2 of the NIST lightweight cryptography standardization process. These candidates are Ascon, DryGASCON, Elephant, Gimli, PHOTON-Beetle, Pyjamask, Romulus, Subterranean, TinyJAMBU and Xoodyak. Specifically, we study the implementations of these algorithms when synthesized using the TSMC 65nm and FDSOI 28nm technologies and Synopsys Design Compiler, targeting various performance trade-offs and different use-cases. We show how different candidates stack-up against such trade-offs. We base our benchmarking parameters and metrics on real-world use-cases, such as high-speed applications, lightweight communication protocols and internet payloads.

Ascon, DryGASCON, and Shamash are submissions to NIST's lightweight cryptography standardization process and have similar designs. We analyze these algorithms against subspace trails, truncated differentials, and differential-linear distinguishers. We provide probability one 4-round subspace trails for DryGASCON-256, 3-round subspace trails for \DryGASCON-128, and 2-round subspace trails for \Shamash permutations. Moreover, we provide the first 3.5-round truncated differential and 5-round differential-linear distinguisher for DryGASCON-128. Finally, we improve the data and time complexity of the 4 and 5-round differential-linear attacks on Ascon.

This work presents a detailed study of the classical security of the post-quantum supersingular isogeny key encapsulation (SIKE) protocol using a realistic budget-based cost model that considers the actual computing and memory costs that are needed for cryptanalysis. In this effort, we design especially-tailored hardware accelerators for the time-critical isogeny computations that we use to model an ASIC-powered instance of the van Oorschot-Wiener (vOW) parallel collision search algorithm. We then extend the analysis to AES and SHA-3 in the context of the NIST post-quantum cryptography standardization process to carry out a parameter analysis based on our cost model. This analysis, together with the state-of-the-art quantum security analysis of SIKE, indicates that the current SIKE parameters offer a wide security margin, which in turn opens up the possibility of using significantly smaller primes that would enable more efficient and compact implementations with reduced bandwidth. Our improved cost model and analysis can be applied widely to other cryptographic settings and primitives, and can have implications for other post-quantum candidates in the NIST process.

Authenticated encryption (AE) is used in a wide variety of applications, potentially in settings for which it was not originally designed. Recent research tries to understand what happens when AE is not used as prescribed by its designers. A question given relatively little attention is whether an AE scheme guarantees "key commitment'': ciphertext should decrypt to a valid plaintext only under the key that was used to generate the ciphertext. As key commitment is not part of AE's design goal, AE schemes in general do not satisfy it. Nevertheless, one would not expect this seemingly obscure property to have much impact on the security of actual products. In reality, however, products do rely on key commitment. We discuss three recent applications where missing key commitment is exploitable in practice. We provide proof-of-concept attacks via a tool that constructs AES-GCM ciphertext which can be decrypted to two plaintexts valid under a wide variety of file formats, such as PDF, Windows executables, and DICOM. Finally we discuss two solutions to add key commitment to AE schemes which have not been analyzed in the literature: one is a generic approach that adds an explicit key commitment scheme to the AE scheme, and the other is a simple fix which works for AE schemes like AES-GCM and ChaCha20Poly1305, but requires separate analysis for each scheme.

In the last few years a new design paradigm, the so-called ARX (modular addition, rotation, exclusive-or) ciphers, have gained popularity in part because of their non-linear operation's seemingly `inherent resilience' against Differential Power Analysis (DPA) Attacks: the non-linear modular addition is not only known to be a poor target for DPA attacks, but also the computational complexity of DPA-style attacks grows exponentially with the operand size and thus DPA-style attacks quickly become practically infeasible. We however propose a novel DPA-style attack strategy that scales linearly with respect to the operand size in the chosen-message attack setting.

We study the problem of enforcing circuit privacy for the homomorphic evaluation of quantum circuits. We present a generic transformation from semi-honest to malicious circuit privacy for quantum fully homomorphic encryption (QFHE). Our compiler assumes minimal structural properties of the underlying QFHE scheme, which are satisfied by recent candidate constructions [Mahadev, FOCS 2018]. Thus we obtain a maliciously circuit private QFHE scheme, assuming the quantum hardness of (a circular variant of) the learning with errors (LWE) problem. This immediately implies the existence of a two-round secure function evaluation protocol for quantum circuits with input-indistinguishable security for the client (holding a quantum state $\ket{\psi}$) and unbounded simulation security for the server (evaluating a quantum circuit $C$).

Secret sharing was proposed primarily in 1979 to solve the problem of key distribution. In recent decades, researchers have proposed many improvement schemes. Among all these schemes, the verifiable multi-secret sharing (VMSS) schemes are studied sufficiently, which share multiple secrets simultaneously and perceive malicious dealer as well as participants. By pointing out that the schemes presented by Dehkordi and Mashhadi in 2008 cannot detect some vicious behaviors of the dealer, we propose two new VMSS schemes by adding validity check in the verification phase to overcome this drawback. Our new schemes are based on XTR public key system, and can realize $GF(p^{6})$ security by computations in $GF(p^{2})$ without explicit constructions of $GF(p^{6})$, where $p$ is a prime. Compared with the VMSS schemes using RSA and linear feedback shift register (LFSR) public key cryptosystems, our schemes can achieve the same security level with shorter parameters by using trace function. What's more, our schemes are much simpler to operate than those schemes based on Elliptic Curve Cryptography (ECC). In addition, our schemes are dynamic and threshold changeable, which means that it is efficient to implement our schemes according to the actual situation when participants, secrets or the threshold needs to be changed.

The security of digital communication relies on few cryptographic protocols that are used to protect internet traffic, from web sessions to instant messaging. These protocols and the cryptographic primitives they rely on have been extensively studied and are considered secure.Yet, sophisticated attackers are often able to bypass rather than break security mechanisms. Kleptography or algorithm substitution attacks (ASA) describe techniques to place backdoors right into cryptographic primitives. While highly relevant as a building block, we show that the real danger of ASAs is their use in cryptographic protocols. In fact, we show that a highly desirable security property of these protocols - forward secrecy - implies the applicability of ASAs. We then analyze the application of ASAs in three widely used protocols: TLS, WireGuard, and Signal. We show that these protocols can be easily subverted by carefully placing ASAs. Our analysis shows that careful design of ASAs makes detection unlikely while leaking long-term secrets within a few messages in the case of TLS and WireGuard, allowing impersonation attacks. In contrast, Signal's double-ratchet protocol shows high immunity to ASAs, as the leakage requires much more messages. But once Signal's long-term key is leaked, the security of the Signal messenger is completely subverted by our attack due to unfortunate choices in the implementation of Signal's multi-device support.

Secure computation protocols enable mutually distrusting parties to compute a function of their private inputs while revealing nothing but the output. Protocols with {\em full security} (also known as {\em guaranteed output delivery}) in particular protect against denial-of-service attacks, guaranteeing that honest parties receive a correct output. This feature can be realized in the presence of an honest majority, and significant research effort has gone toward attaining full security with good asymptotic and concrete efficiency.

We present an efficient protocol for {\em any constant} number of parties $n$, with {\em full security} against $t<n/2$ corrupted parties, that makes a black-box use of a pseudorandom generator. Our protocol evaluates an arithmetic circuit $C$ over a finite ring $R$ (either a finite field or $R=\Z_{2^k}$) with communication complexity of $\frac{3t}{2t+1}S + o(S)$ $R$-elements per party, where $S$ is the number of multiplication gates in $C$ (namely, $<1.5$ elements per party per gate). This matches the best known protocols for the semi-honest model up to the sublinear additive term. For a small number of parties $n$, this improves over a recent protocol of Goyal {\em et al.} (Crypto 2020) by a constant factor for circuits over large fields, and by at least an $\Omega(\log n)$ factor for Boolean circuits or circuits over rings.

Our protocol provides new methods for applying the sublinear-communication distributed zero-knowledge proofs of Boneh {\em et al.}~(Crypto 2019) for compiling semi-honest protocols into fully secure ones, in the more challenging case of $t>1$ corrupted parties. Our protocol relies on {\em replicated secret sharing} to minimize communication and simplify the mechanism for achieving full security. This results in computational cost that scales exponentially with $n$.

Our main fully secure protocol builds on a new intermediate honest-majority protocol for verifying the correctness of multiplication triples by making a {\em general} use of distributed zero-knowledge proofs. While this intermediate protocol only achieves the weaker notion of {\em security with abort}, it applies to any linear secret-sharing scheme and provides a conceptually simpler, more general, and more efficient alternative to previous protocols from the literature. In particular, it can be combined with the Fiat-Shamir heuristic to simultaneously achieve logarithmic communication complexity and constant round complexity.

Anonymous attestation for secure hardware platforms leverages tailored group signature schemes and assumes the hardware to be trusted. Yet, there is an ever increasing concern on the trustworthiness of hardware components and embedded systems. A subverted hardware may, for example, use its signatures to exfiltrate identifying information or even the signing key.

In this paper we focus on Enhanced Privacy ID (EPID)---a popular anonymous attestation scheme used in commodity secure hardware platforms like Intel SGX. We define and instantiate a \emph{subversion resilient} EPID scheme (or SR-EPID). In a nutshell, SR-EPID provides the same functionality and security guarantees of the original EPID, despite potentially subverted hardware. In our design, a ``sanitizer'' ensures no covert channel between the hardware and the outside world both during enrollment and during attestation (i.e., when signatures are produced). We design a practical SR-EPID scheme secure against adaptive corruptions and based on a novel combination of malleable NIZKs and hash functions modeled as random oracles.

Our approach has a number of advantages over alternative designs. Namely, the sanitizer bears no secret information---hence, a memory leak does not erode security. Further, the role of sanitizer may be distributed in a cascade fashion among several parties so that sanitization becomes effective as long as one of the parties has access to a good source of randomness. Also, we keep the signing protocol non-interactive, thereby minimizing latency during signature generation.

We propose a practical zero-knowledge proof system for proving knowledge of short solutions s, e to linear relations A s + e= u mod q which gives the most efficient solution for two naturally-occurring classes of problems. The first is when A is very ``tall'', which corresponds to a large number of LWE instances that use the same secret s. In this case, we show that the proof size is independent of the height of the matrix (and thus the length of the error vector e) and rather only linearly depends on the length of s. The second case is when A is of the form A' tensor I, which corresponds to proving many LWE instances (with different secrets) that use the same samples A'. The length of this second proof is square root in the length of s, which corresponds to square root of the length of all the secrets. Our constructions combine recent advances in ``purely'' lattice-based zero-knowledge proofs with the Reed-Solomon proximity testing ideas present in some generic zero-knowledge proof systems -- with the main difference is that the latter are applied directly to the lattice instances without going through intermediate problems.

There has been a lot of recent progress in constructing efficient zero-knowledge proofs for showing knowledge of an $\polvec s$ with small coefficients satisfying $\pol A\polvec s=\polvec t$. For typical parameters, the proof sizes have gone down from several megabytes to a bit under $50$KB (Esgin et al., Asiacrypt 2020). These are now within an order of magnitude of the sizes of lattice-based signatures, which themselves constitute proof systems which demonstrate knowledge of something weaker than the aforementioned equation. One can therefore see that this line of research is approaching optimality. In this paper, we modify a key component of these proofs, as well as apply several other tweaks, to achieve a further reduction of around $30\%$ in the proof output size. We also show that this savings propagates itself when these proofs are used in a general framework to construct more complex protocols.

Recently, there has been a great development in communication-efficient zero-knowledge (ZK) protocols for arithmetic circuit relations. Since any relation can be translated into an arithmetic circuit relation, these primitives are extremely powerful and widely applied. However, this translation often comes at the cost of losing conceptual simplicity and modularity in cryptographic protocol design.

For this reason, Lai et al. (CCS 2019), show how Bulletproof's communication-efficient circuit zero-knowledge protocol (Bootle et al., EUROCRYPT 2016 and Bünz et al., S&P 2018) can be generalized to work for bilinear group arithmetic circuits directly, without requiring these circuits to be translated into arithmetic circuits. For many natural relations their approach is actually more efficient than the indirect circuit ZK approach.

We take a different approach and show that the arithmetic circuit model can be generalized to any circuit model in which (a) all wires take values in (possibly different) Zq-modules and (b) all gates have fan-in 2 and are either linear or bilinear mappings. We follow a straightforward generalization of Compressed Sigma-Protocol Theory (CRYPTO 2020). We compress the communication complexity of a basic Sigma-protocol for proving linear statements down to logarithmic. Then, we describe a {\em linearization} strategy to handle non-linearities. Besides its conceptual simplicity our approach also has practical advantages; we reduce the constant of the logarithmic component in the communication complexity of the CCS 2019 approach from 16 down to 6 and that of the linear component from 3 down to 1.

Moreover, the generalized commitment scheme required for bilinear circuit relations is also advantageous to standard arithmetic circuit ZK protocols, since its application immediately results in a square root reduction of public parameters size. The implications of this improvement can be significant, because many application scenarios result in very large sets of public parameters.

As an application of our compressed protocol for proving linear statements we construct the first k-out-of-n threshold signature scheme (TSS) with both transparent setup and threshold signatures of size $O(\kappa \log(n))$ bits for security parameter $\kappa$. Each individual signature is of a so-called BLS type, the threshold signature hides the identities of the $k$ signers and the threshold $k$ can be dynamically chosen at aggregation time. Prior TSSs either result in sub-linear size signatures at the cost of requiring a trusted setup or the cost of the transparent setup amounts to linear (in $k$) size signatures.

We introduce and study a simple kind of proof systems called line-point zero knowledge (LPZK). In an LPZK proof, the prover encodes the witness as an affine line $\mathbf{v}(t) := \mathbf{a}t + \mathbf{b}$ in a vector space $\mathbb{F}^n$, and the verifier queries the line at a single random point $t=\alpha$. LPZK is motivated by recent practical protocols for {\em vector oblivious linear evaluation} (VOLE), which can be used to compile LPZK proof systems into lightweight designated-verifier NIZK protocols.

We construct LPZK systems for proving satisfiability of arithmetic circuits with attractive efficiency features. These give rise to designated-verifier NIZK protocols that require only 2-3 times the computation of evaluating the circuit in the clear (following a ``silent'' preprocessing phase), and where the prover communicates roughly 2 field elements per multiplication gate, or roughly 1 element in the random oracle model with a modestly higher computation cost. On the theoretical side, our LPZK systems give rise to the first linear interactive proofs (Bitansky et al., TCC 2013) that are zero knowledge against a malicious verifier.

We then apply LPZK towards simplifying and improving recent constructions of reusable non-interactive secure computation (NISC) from VOLE (Chase et al., Crypto 2019). As an application, we give concretely efficient and reusable NISC protocols over VOLE for {bounded inner product, where the sender's input vector should have a bounded $L_2$-norm.

This note presents two attacks against COMET, a second-round candidate in the NIST lightweight cryptography standardization process. The first attack uses a long message to detect the use of weak keys, whereas the second attack focuses on the resistance of COMET against slide attacks. These attacks do not invalidate the security claims of the designers.

This work is dedicated to APN and AB functions which are optimal against differential and linear cryptanlysis when used as S-boxes in block ciphers. They also have numerous applications in other branches of mathematics and information theory such as coding theory, sequence design, combinatorics, algebra and projective geometry. In this paper we give an overview of known constructions of APN and AB functions, in particular, those leading to infinite classes of these functions. Among them, the bivariate construction method, the idea first introduced in 2011 by the third author of the present paper, turned out to be one of the most fruitful. It has been known since 2011 that one of the families derived from the bivariate construction contains the infinite families derived by Dillon's hexanomial method. Whether the former family is larger than the ones it contains has stayed an open problem which we solve in this paper. Further we consider the general bivariate construction from 2013 by the third author and study its relation to the recently found infinite families of bivariate APN functions.

Cloud storage is becoming increasingly popular among end users that outsource their personal data to services such as Dropbox or Google Drive. For security, uploaded data should ideally be encrypted under a key that is controlled and only known by the user. Current solutions that support user-centric encryption either require the user to manage strong cryptographic keys, or derive keys from weak passwords. While the former has massive usability issues and requires secure storage by the user, the latter approach is more convenient but offers only little security. The recent concept of password-authenticated secret-sharing (PASS) enables users to securely derive strong keys from weak passwords by leveraging a distributed server setup, and has been considered a promising step towards secure and usable encryption. However, using PASS for encryption is not as suitable as originally thought: it only considers the (re)construction of a \emph{single}, static key -- whereas practical encryption will require the management of \emph{many}, object-specific keys. Using a dedicated PASS instance for every key makes the solution vulnerable against online attacks, inherently leaks access patterns to the servers and poses the risk of permanent data loss when an incorrect password is used at encryption. We therefore propose a new protocol that directly targets the problem of boostrapping encryption from a single password: distributed password-authenticated symmetric key encryption DPASE.

DPASE offers strong security and usability, such as protecting the user's password against online and offline attacks, and ensuring message privacy and ciphertext integrity as long as at least one server is honest. We formally define the desired security properties in the UC framework and propose a provably secure instantiation. The core of our protocol is a new type of OPRF that allows to extend a previous partially-blind-query with a follow-up request and will be used to blindly carry over passwords across evaluations and avoid online attacks. Our (proof-of-concept) implementation of DPASE uses $10$ exponentiations at the user, $4$ exponentiations and $2$ pairings at each server, takes $105.58$ ms to run with $2$ servers and has a server throughput of $40$ encryptions per second.

In this paper, we study the effect of two modifications to multivariate public key encryption schemes: internal perturbation (ip), and Q_+. Focusing on the Dob encryption scheme, a construction utilising these modifications, we accurately predict the number of degree fall polynomials produced in a Gröbner basis attack, up to and including degree five. The predictions remain accurate even when fixing variables. Based on this new theory we design a novel attack on the Dob encryption scheme, which breaks Dob using the parameters suggested by its designers. While our work primarily focuses on the Dob encryption scheme, we also believe that the presented techniques will be of particular interest to the analysis of other big-field schemes.