International Association
for Cryptologic Research

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.

Decentralized cryptocurrencies still suffer from three interrelated weaknesses: Low transaction rates, high transaction fees, and long confirmation times. Payment Channels promise to be a solution to these issues, and many constructions for real-life cryptocurrencies, such as Bitcoin, are known. Somewhat surprisingly, no such solution is known for Monero, the largest privacy-preserving cryptocurrency, without requiring system-wide changes like a hard-fork of its blockchain.

In this work, we close this gap by presenting \textsc{PayMo}, the first payment channel protocol that is fully compatible with Monero. \textsc{PayMo} does not require any modification of Monero and can be readily used to perform off-chain payments. Notably, transactions in \textsc{PayMo} are identical to standard transactions in Monero, therefore not hampering the coins' fungibility. Using \textsc{PayMo}, we also construct the first fully compatible secure atomic-swap protocol for Monero: One can now securely swap a token of Monero with a token of several major cryptocurrencies such as Bitcoin, Ethereum, Ripple, Cardano, etc. Before our work, it was not known how to implement secure atomic swaps protocols for Monero without forcing a hard fork. Our main technical contribution is a new construction of an efficient verifiable timed linkable ring signature, where signatures can be hidden for a pre-determined amount of time, in a verifiable way. Our scheme is fully compatible with the transaction scheme of Monero and it might be of independent interest. We implemented \textsc{PayMo} and our results show that, even with high network latency and with a single CPU core, two regular users can perform up to 93500 payments over a span of 2 minutes (the block production rate of Monero). This is approximately five orders of magnitude improvement over the current payment rate of Monero.

Nowadays, virtually all products and services offered by financial institutions are backed by technology. While the frontend banking services seem to be simple, the core-banking backend systems and architecture are complex and often based on legacy technologies. Customer-facing applications and services are evolving rapidly, yet they have data dependencies on core banking systems running on ancient technology standards.

While those legacy systems are preferred for their stability, reliability, availability, and security properties, in adapting the frontends and services many security and privacy issues can occur. Clearly, this issues are arising as those systems have been designed decades ago, without considering the enormous amounts of data that they are required to handle and also considering different threat scenarios. Moreover, the trend towards using new technologies such as Distributed Ledger Technologies (DLT) has also emerged in the financial sector. As the nodes in DLT systems are decentralized, additional security threats come to light.

The focus of this work is the security of financial technologies in the FinTech domain. We provide relevant categorization and taxonomies for a better understanding of the main cyber-attack types, and suitable countermeasures. Our findings are supported by using security-by-design principles for some selected critical financial use-cases, and include a detailed discussion of the resulting threats, attack vectors and security recommendations.