International Association
for Cryptologic Research

Learning with Errors (LWE) is a hard math problem used in post-quantum cryptography. Homomorphic Encryption (HE) schemes rely on the hardness of the LWE problem for their security, and two LWE-based cryptosystems were recently standardized by NIST for digital signatures and key exchange (KEM). Thus, it is critical to continue assessing the security of LWE and specific parameter choices. For example, HE uses small secrets, and the HE community has considered standardizing small sparse secrets to improve efficiency and functionality. However, prior work, SALSA and PICANTE, showed that machine learning (ML) attacks can recover sparse binary secrets. Building on these, we propose VERDE, an improved ML attack that can recover sparse binary, ternary, and small Gaussian secrets. Using improved preprocessing and secret recovery techniques, VERDE can attack LWE with larger dimensions ($n=512$) and smaller moduli ($\log_2 q=12$ for $n=256$), using less time and power. We propose novel architectures for scaling. Finally, we develop a theory that explains the success of ML LWE attacks.

Society appears to be on the verge of recognizing the need for control over sensitive data in modern web applications. Recently, many systems claim to give control to individuals, promising the preeminent goal of data sovereignty. However, despite recent attention, research and industry efforts are fragmented and lack a holistic system overview. In this paper, we provide the first transecting systematization of data sovereignty by drawing from a dispersed body of knowledge. We clarify the field by identifying its three main areas: (i) decentralized identity, (ii) decentralized access control and (iii) policy-compliant decentralized computation. We find that literature lacks a cohesive set of formal definitions. Each area is considered in isolation, and priorities in industry and academia are not aligned due to a lack of clarity regarding user control. To solve this issue, we propose formal definitions for each sub-area. By highlighting that data sovereignty transcends the domain of decentralized identity, we aim to guide future works to embrace a broader perspective on user control. In each section, we augment our definition with security and privacy properties, discuss the state of the art and proceed to identify open challenges. We conclude by highlighting synergies between areas, emphasizing the real-world benefit obtained by further developing data sovereign systems.

Even given a state-of-the-art masking scheme, masked software implementation of some cryptography functionality can pose significant challenges stemming, e.g., from simultaneous requirements for efficiency and security. In this paper we design an Instruction Set Extension (ISE) to address a specific element of said challenge, namely the elimination of micro-architectural leakage. Conceptually, the ISE allows a leakage-focused behavioural hint to be communicated from software to the micro-architecture: using it informs how computation is realised when applied to masking-specific data, allowing associated micro-architectural leakage to be eliminated. We develop prototype, latency- and area-optimised implementations of the ISE design based on the RISC-V Ibex core; using them, we demonstrate that use of the ISE can close the gap between assumptions about and actual behaviour of a device and thereby deliver an improved security guarantee.

With the announcement of the first winners of the NIST Post-Quantum Cryptography (PQC) competition in 2022, the industry has now a confirmed foundation to revisit established cryptographic algorithms applied in automotive use cases and replace them with quantum-safe alternatives. In this paper, we investigate the application of the NIST competition winner CRYSTALS-Dilithium to protect the integrity and authenticity of over-the-air update packages. We show how this post-quantum secure digital signature algorithm can be integrated in AUTOSAR Adaptive Platform Update and Configuration Management framework and evaluate our approach practically using the NXP S32G vehicle network processor. We discuss two implementation variants with respect to performance and resilience against relevant attacks, and conclude that PQC has little impact on the update process as a whole.

Transport Layer Security (TLS) establishes an authenticated and confidential channel to deliver data for almost all Internet applications. A recent work (Zhang et al., CCS'20) proposed a protocol to prove the TLS payload to a third party, without any modification of TLS servers, while ensuring the privacy and originality of the data in the presence of malicious adversaries. However, it required maliciously secure two-party computation (2PC) for generic circuits, leading to significant computational and communication overhead.

This paper proposes the garble-then-prove technique to achieve the same security requirement without using any heavy mechanism like generic malicious 2PC. Our end-to-end implementation shows 14$\times$ improvement in communication and an order of magnitude improvement in computation over the state-of-the-art protocol; we also show worldwide performance when using our protocol to authenticate payload data from Coinbase and Twitter APIs. Finally, we propose an efficient gadget to privately convert the above authenticated TLS payload to Pedersen commitments so that the properties of the payload can be proven efficiently using zkSNARKs.

This note shows that there exists a nontrivial invariant for the unkeyed round function of QARMAv2-64. It is invariant under translation by a set of $2^{32}$ constants. The invariant does not extend over all rounds of QARMAv2-64 and probably does not lead to full-round attacks. Nevertheless, it might be of interest as it can be expected to give meaningful weak-key attacks on round-reduced instances when combined with other techniques such as integral cryptanalysis.

In this paper we consider multipartite access structures obtained from polymatroids with extreme rank function. They are proved to be ideal and partially hierarchical. It turns out that the family of structures induced by polymatroids with minimal rank function is a natural generalization of the class of disjunctive access structure considered by Simmons and the class of conjunctive access structures introduced by Tassa. The results are based on the connections between multipartite access structures and polymatroids discovered by Farràs, Martí-Farré and Padró.

We present $\mathsf{Testudo}$, a new FFT-less SNARK with a near linear-time prover, constant-time verifier, constant-size proofs and a square-root-size universal setup. $\mathsf{Testudo}$ is based on a variant of Spartan~\cite{C:Setty20}—and hence does not require FFTs—as well as a new, fast multivariate polynomial commitment scheme (PCS) with a square-root-sized trusted setup that is derived from PST (TCC 2013) and IPPs (Asiacrypt 2021). To achieve constant-size SNARK proofs in $\mathsf{Testudo}$ we then combine our PCS openings proofs recursively with a Groth16 SNARK. We also evaluate our construction and its building blocks: to compute a PCS opening proof for a polynomial of size $2^{25}$, our new scheme opening procedure achieves a 110x speed-up compared to PST and 3x compared to Gemini (Eurocrypt 2022), since opening computations are heavily parallelizable and operate on smaller polynomials. Furthermore, a $\mathsf{Testudo}$ proof for a witness of size $2^{30} (\approx 1\,GB)$ requires a setup of size only $2^{15}$ ($\approx$ tens of kilobytes). Finally, we show that a $\mathsf{Testudo}$ variant for proving data-parallel computations is almost 10x faster at verifying $2^{10}$ Poseidon-based Merkle tree opening proofs than the regular version.

TinyJAMBU is one of the ten finalists of the NIST lightweight cryptography competition, announced in March 2021. It proposes a lightweight authenticated encryption scheme based on a lightweight 128-bit keyed permutation. TinyJAMBU supports three key lengths 128, 192, and 256 denoted by TinyJambu-128, TinyJambu192, and TinyJambu-256, respectively. The scheme as well as the permutation is well studied by the designers and third parties. The most relevant work to ours is the full-round zero-sum distinguisher under the known-key setting assumption published at Indocrypt 2022. In this work, we show that even without the known-key setting assumption, there are integral distinguishers not only for full-round versions of the permutations of TinyJambu-128 and TinyJambu-192 but also for round-increased versions of them up to 1273 rounds.

It is well-known that randomness is essential for secure cryptography. The randomness used in cryptographic primitives is not necessarily recoverable even by the party who can, e.g., decrypt or recover the underlying secret/message. Several cryptographic primitives that support randomness recovery have turned out useful in various applications. In this paper, we study randomness recoverable secret sharing schemes (RR-SSS), in both information-theoretic and computational settings and provide two results. First, we show that while every access structure admits a perfect RR-SSS, there are very simple access structures (e.g., in monotone $\mathsf{AC}^0$) that do not admit efficient perfect (or even statistical) RR-SSS. Second, we show that the existence of efficient computational RR-SSS for certain access structures in monotone $\mathsf{AC}^0$ implies the existence of one-way functions. This stands in sharp contrast to (non-RR) SSS schemes for which no such results are known. RR-SSS plays a key role in making advanced attributed-based encryption schemes randomness recoverable, which in turn have applications in the context of designated-verifier non-interactive zero knowledge.

Fully Homomorphic Encryption over the Torus (TFHE) is a homomorphic encryption scheme which supports efficient Boolean operations over encrypted bits. TFHE has a unique feature in that the evaluation of each binary gate is followed by a bootstrapping procedure to refresh the noise of a ciphertext. In particular, this gate bootstrapping involves two algorithms called the blind rotation and key-switching.

In this work, we introduce several optimization techniques for the TFHE bootstrapping. We first define a new key distribution, called the block binary distribution, where the secret key can be expressed as a concatenation of several vectors of Hamming weight at most one. We analyze the hardness of (Ring) LWE with a block binary secret and provide candidate parameter sets which are secure against the best-known attacks. Then, we use the block key structure to simplify the inner working of blind rotation and reduce its complexity. We also modify the RLWE key generation and the gadget decomposition method to improve the performance of the key-switching algorithm in terms of complexity and noise growth.

Finally, we use the TFHE library to implement our algorithms and demonstrate their benchmarks. Our experimentation shows that the execution time of TFHE bootstrapping is reduced from 10.5ms down to 6.4ms under the same security level, and the size of the bootstrapping key decreases from 109MB to 60MB.

We offer a digital signature scheme using Boolean automorphisms of a multivariate polynomial algebra over integers. Verification part of this scheme is based on the approximation of the number of zeros of a multivariate Boolean function.

The expressiveness of Turing-complete blockchains implies that verifying a transaction's validity requires executing it on the current blockchain state. Transaction fees are designed to compensate actors for resources expended on transactions, but can only be charged from transactions included in blocks.

In this work, we show that adversaries can craft malicious transactions that decouple the work imposed on blockchain actors from the compensation offered in return. We introduce three attacks: (i) ConditionalExhaust, the first conditional Resource Exhaustion Attack (REA) against blockchain actors. (ii) MemPurge, an attack for evicting transactions from victims' mempools. (iii) These attack are augmented by GhostTX, the first attack on the reputation system used in Ethereum's Proposer-Builder Separation ecosystem.

We empirically evaluate the attacks on an Ethereum testnet. The worst-case result we find is that by combining ConditionalExhaust and MemPurge, an adversary can simultaneously burden victims' computational resources and clog their mempools, to the point where victims are unable to include transactions in their blocks. Thus, victims create empty blocks, thereby hurting the system's liveness. The expected cost of a one-shot combined attack is $376, but becomes much cheaper if the adversary is a validator. For other attackers, costs decrease if censorship is prevalent in the network.

ConditionalExhaust and MemPurge are made possible by inherent features of Turing-complete blockchains. Potential mitigations may result in reducing a ledger's scalability, an undesirable outcome likely harming its competitiveness.

A secret-sharing scheme enables a dealer to share a secret $s$ among $n$ parties such that only authorized subsets of parties, specified by a monotone access structure $f:\{0,1\}^n\to\{0,1\}$, can reconstruct $s$ from their shares. Other subsets of parties learn nothing about $s$.

The question of minimizing the (largest) share size for a given $f$ has been the subject of a large body of work. However, in most existing constructions for general access structures $f$, the share size is not much smaller than the size of some natural computational representation of $f$, a fact that has often been referred to as the ``representation size barrier'' in secret sharing.

In this work, we initiate a systematic study of succinct computational secret sharing (SCSS), where the secrecy requirement is computational and the goal is to substantially beat the representation size barrier. We obtain the following main results.

(1) SCSS via Projective PRGs. We introduce the notion of a *projective PRG*, a pseudorandom generator for which any subset of the output bits can be revealed while keeping the other output bits hidden, using a *short* projective seed. We construct projective PRGs with different levels of succinctness under a variety of computational assumptions, and apply them towards constructing SCSS for graph access structures, monotone CNF formulas, and (less succinctly) useful subclasses of monotone circuits and branching programs. Most notably, under the sub-exponential RSA assumption, we obtain a SCSS scheme that, given an arbitrary access structure $f$, represented by a truth table of size $N=2^n$, produces shares of size polylog(N)=\poly(n) in time $\tilde O(N)$. For comparison, the share size of the best known information-theoretic schemes is $O(N^{0.58})$.

(2) SCSS via One-way Functions. Under the (minimal) assumption that one-way functions exist, we obtain a near-quadratic separation between the total share size of computational and information-theoretic secret sharing. This is the strongest separation one can hope for, given the state of the art in secret sharing lower bounds. We also construct SCSS schemes from one-way functions for useful classes of access structures, including forbidden graphs and monotone DNF formulas. This leads to constructions of fully-decomposable conditional disclosure of secrets (also known as privacy-free garbled circuits) for general functions, represented by a truth table of size $N=2^n$, with share size polylog(N) and computation time $\tilde O(N)$, assuming sub-exponentially secure one-way functions.

Studying the feasibility of Byzantine Agreement (BA) in realistic fault models is an important question in the area of distributed computing and cryptography. In this work, we revisit the mixed fault model with Byzantine (malicious) faults and omission faults put forth by Hauser, Maurer, and Zikas (TCC 2009), who showed that BA (and MPC) is possible with $t$ Byzantine faults, $s$ send faults (whose outgoing messages may be dropped) and $r$ receive faults (whose incoming messages may be lost) if $n>3t+r+s$. We generalize their techniques and results by showing that BA is possible if $n>2t+r+s$, given the availability of a cryptographic setup. Our protocol is the first to match the recent lower bound of Eldefrawy, Loss, and Terner (ACNS 2022) for this setting.

In MPC, we usually represent programs as circuits. This is a poor fit for programs that use complex control flow, as it is costly to compile control flow to circuits. This motivated prior work to emulate CPUs inside MPC. Emulated CPUs can run complex programs, but they introduce high overhead due to the need to evaluate not just the program, but also the machinery of the CPU, including fetching, decoding, and executing instructions, accessing RAM, etc.

Thus, both circuits and CPU emulation seem a poor fit for general MPC. The former cannot scale to arbitrary programs; the latter incurs high per-operation overhead.

We propose variable instruction set architectures (VISAs), an approach that inherits the best features of both circuits and CPU emulation. Unlike a CPU, a VISA machine repeatedly executes entire program fragments, not individual instructions. By considering larger building blocks, we avoid most of the machinery associated with CPU emulation: we directly handle each fragment as a circuit.

We instantiated a VISA machine via garbled circuits (GC), yielding constant-round 2PC for arbitrary assembly programs. We use improved branching (Stacked Garbling, Heath and Kolesnikov, Crypto 2020) and recent Garbled RAM (GRAM) (Heath et al., Eurocrypt 2022). Composing these securely and efficiently is intricate, and is one of our main contributions.

We implemented our approach and ran it on common programs, including Dijkstra's and Knuth-Morris-Pratt. Our 2PC VISA machine executes assembly instructions at $300$Hz to $4000$Hz, depending on the target program. We significantly outperform the state-of-the-art CPU-based approach (Wang et al., ESORICS 2016, whose tool we re-benchmarked on our setup). We run in constant rounds, use $6\times$ less bandwidth, and run more than $40\times$ faster on a low-latency network. With $50$ms (resp. $100$ms) latency, we are $898\times$ (resp. $1585\times$) faster on the same setup.

While our focus is MPC, the VISA model also benefits CPU-emulation-based Zero-Knowledge proof compilers, such as ZEE and EZEE (Heath et al., Oakland'21 and Yang et al., EuroS&P'22).

This work addresses the long quest for proving full (adaptive) security for attribute-based encryption (ABE). We show that in order to prove full security in a black-box manner, the scheme must be ``irregular'' in the sense that it is impossible to ``validate'' secret keys to ascertain consistent decryption of ciphertexts. This extends a result of Lewko and Waters (Eurocrypt 2014) that was only applicable to straight-line proofs (without rewinding). Our work, therefore, establishes that it is impossible to circumvent the irregularity property using creative proof techniques, so long as the adversary is used in a black-box manner.

As a consequence, our work provides an explanation as to why some lattice-based ABE schemes cannot be proven fully secure, even though no known adaptive attacks exist.

Blockchain systems can become overwhelmed by a large number of transactions, leading to increased latency. As a consequence, latency-sensitive users must bid against each other and pay higher fees to ensure that their transactions are processed in priority. However, most of the time of a blockchain system (78% in Ethereum), there is still a lot of unused computational power, with few users sending transactions. To address this issue and reduce latency for users, we propose the latency-first smart contract model in this paper, which optimistically accepts committed transactions. This allows users to submit a commitment during times of high demand, and then complete the rest of the work at a lower priority. From the perspective of the blockchain, this temporarily “overclocks” the system. We have developed a programming tool for our model, and our experiments show that the proposed latency-first smart contract model can greatly reduce latency during the periods of high demand.

We bring in here a novel algebraic approach for attacking the McEliece cryptosystem which is right now at the $4$-th round of the NIST competition. It consists in introducing a subspace of matrices representing quadratic forms. Those are associated with quadratic relationships for the component-wise product in the dual of the Goppa (or alternant) code of the cryptosystem. Depending on the characteristic of the field over which the code is defined, this space of matrices consists only of symmetric matrices (odd characteristic) or skew-symmetric matrices (characteristic $2$). It turns out that this matrix space contains unusually low-rank matrices (rank $3$ matrices in odd characteristic, rank $2$ matrices for characteristic $2$) which reveal the secret polynomial structure of the code. Finding such matrices can then be used to recover the secret key of the scheme. We devise a dedicated approach in characteristic $2$ consisting in using a Gröbner basis modeling that a skew-symmetric matrix is of rank $2$. This allows to analyze the complexity of solving the corresponding algebraic system with Gröbner bases techniques. This computation behaves differently when applied to the skew-symmetric matrix space associated with a random code rather than with a Goppa or an alternant code. This gives a distinguisher of the latter code family. We give a bound on its complexity which turns out to interpolate nicely between polynomial and exponential depending on the code parameters. A distinguisher for alternant/Goppa codes was already known [FGOPT11]. It is of polynomial complexity but works only in a narrow parameter regime. This new distinguisher is also polynomial for the parameter regime necessary for [FGOPT11] but contrarily to the previous one is able to operate for virtually all code parameters relevant to cryptography. Moreover, we use this matrix space to find a polynomial time attack of the McEliece cryptosystem provided that the Goppa code is distinguishable by the method of [FGOPT11] and its degree is less than $q-1$, where $q$ is the alphabet size of the code.

The word-oriented feedback shift registers (WFSRs) possess very attractive properties as they take advantage of modern word-based processors and thus increase the throughput. We provide a generalized form of the feedback function of WFSR along with some special cases. Then, a necessary and sufficient condition for nonsingular WFSR is discussed. We study different word-based cascade systems and the period of sequences produced by these cascade systems is derived. We provide experimental results on avalanche property on states of cascade systems and statistical results of sequences produced by them. Finally, we present a crypt-analytic attack on cascade systems and suggest its countermeasure.