International Association
for Cryptologic Research

Event date: 10 September to 14 September 2023

Event date: 29 November to 2 December 2023

In this paper, we present the Webb Protocol, a system for building and governing cross-chain applications that can support shared anonymity set functionality across a set of identical bridged systems on compatible blockchains. The Webb Protocol is composed of two major protocols that deal with storing, updating, and validating of data and state changes that occur on a bridge and that are relevant to replicate on each connected chain. State is efficiently verifiable through the use of merkle trees and privacy is provided using zero-knowledge proofs of membership. Together, one can create applications leveraging distributed state with private property testing capabilities. Both financial and non-financial applications are described as motivating examples within the paper.

Differential-linear (DL) cryptanalysis has undergone remarkable advancements since it was first proposed by Langford and Hellman \cite{langford1994differential} in 1994. At CRYPTO 2022, Niu et al. studied the (rotational) DL cryptanalysis of $n$-bit modulo additions with 2 inputs, i.e., $\boxplus_2$, and presented a technique for evaluating the (rotational) DL correlation of ARX ciphers. However, the problem of how to automatically search for good DL trails on ARX with solvers was left open, which is the focus of this work.

In this paper, we solve this open problem through some techniques to reduce complexity and a transformation technique from matrix multiplication chain to Mixed Integer Quadratically-Constrained Programs (MIQCP). First, the computational complexity of the DL correlation of $\boxplus_2$ is reduced to approximately one-eighth of the state of art, which can be computed by a $2\times2$ matrix multiplication chain of the same length as before. Some methods to further reduce complexity in special cases have been studied. Additionally, we present how to compute the extended (rotational) DL correlations of $\boxplus_k$ for $k\ge 2$, where two output linear masks of the cipher pairs can be different. Second, to ensure that the existing solver Gurobi\footnote{The solver used in this paper is Gurobi, and some ready-made functions in Gurobi are also used, such as LOG\_2 and ABS. The source code is available at \url{https://}. } can compute DL correlations of $\boxplus_2$, we propose a method to transform an arbitrary matrix multiplication chain into a MIQCP, which forms the foundation of our automatic search of DL trails in ARX ciphers. Third, in ARX ciphers, we use a single DL trail under some explicit conditions to give a good estimate of the correlation, which avoids the exhaustion of intermediate differences. We then derive an automatic method for evaluating the DL correlations of ARX, which we apply to Alzette and some versions of SPECK. Experimentally verified results confirm the validity of our method, with the predicted correlations being close to the experimental ones. To the best of our knowledge, this method finds the best DL distinguishers for these ARX primitives currently. Furthermore, we presented the lowest time-complexity attacks against 12-14 rounds of SPECK32 to date.

Privacy enhancing technologies (PETs) have been proposed as a way to protect the privacy of data while still allowing for data analysis. In this work, we focus on Fully Homomorphic Encryption (FHE), a powerful tool that allows for arbitrary computations to be performed on encrypted data. FHE has received lots of attention in the past few years and has reached realistic execution times and correctness.

More precisely, we explain in this paper how we apply FHE to tree-based models and get state-of-the-art solutions over encrypted tabular data. We show that our method is applicable to a wide range of tree-based models, including decision trees, random forests, and gradient boosted trees, and has been implemented within the Concrete-ML library, which is open-source at https://github.com/zama-ai/concrete-ml. With a selected set of use-cases, we demonstrate that our FHE version is very close to the unprotected version in terms of accuracy.

Fully homomorphic encryption (FHE) is an encryption method that allows to perform computation on encrypted data, without decryption. FHE preserves the privacy of the users of online services that handle sensitive data, such as health data, biometrics, credit scores and other personal information. A common way to provide a valuable service on such data is through machine learning and, at this time, Neural Networks are the dominant machine learning model for unstructured data.

In this work we show how to construct Deep Neural Networks (DNN) that are compatible with the constraints of TFHE, an FHE scheme that allows arbitrary depth computation circuits. We discuss the constraints and show the architecture of DNNs for two computer vision tasks. We benchmark the architectures using the Concrete stack, an open-source implementation of TFHE.

We present a pairing-based traitor tracing scheme for $N$ users with$$ |\mathsf{pk}| = |\mathsf{ct}| = O(N^{1/3}), \quad |\mathsf{sk}| = O(1). $$This is the first pairing-based scheme to achieve ${|\mathsf{pk}|\cdot|\mathsf{sk}|\cdot|\mathsf{ct}|=o(N)}$. Our construction relies on the (bilateral) $k$-Lin assumption, and achieves private tracing and full collusion resistance. Our result simultaneously improves upon the sizes of $\mathsf{pk},\mathsf{ct}$ in Boneh–Sahai–Waters [Eurocrypt '06] and the size of $\mathsf{sk}$ in Zhandry [Crypto '20], while further eliminating the reliance on the generic group model in the latter work.

The Demirci-Sel{\c{c}}uk meet-in-the-middle (DS-MITM) attack is a sophisticated variant of differential attacks. Due to its sophistication, it is hard to efficiently find the best DS-MITM attacks on most ciphers \emph{except} for AES. Moreover, the current automatic tools only capture the most basic version of DS-MITM attacks, and the critical techniques developed for enhancing the attacks (e.g., differential enumeration and key-dependent-sieve) still rely on manual work. In this paper, we develop a full-fledged automatic framework integrating all known techniques (differential enumeration, key-dependent-sieve, and key bridging, etc) for the DS-MITM attack that can produce key-recovery attacks directly rather than only search for distinguishers. Moreover, we develop a new technique that is able to exploit partial key additions to generate more linear relations beneficial to the attacks. We apply the framework to the SKINNY family of block ciphers and significantly improved results are obtained. In particular, all known DS-MITM attacks on the respective versions of SKINNY are improved by at least 2 rounds, and the data, memory, or time complexities of some attacks are reduced even compared to previous best attacks penetrating less rounds.

Liquidations in DeFi are both a blessing and a curse — whereas liquidations prevent lenders from capital loss, they simultaneously lead to liquidation spirals and system-wide failures. Since most lending and borrowing protocols assume liquidations are indispensable, there is an increased interest in alternative constructions that prevent immediate systemic-failure under uncertain circumstances.

In this work, we introduce reversible call options, a novel financial primitive that enables the seller of a call option to terminate it before maturity. We apply reversible call options to lending in DeFi and devise Miqado, a protocol for lending platforms to replace the liquidation mechanisms. To the best of our knowledge, Miqado is the first protocol that actively mitigates liquidations to reduce the risk of liquidation spirals. Instead of selling collateral, Miqado incentivizes external entities, so-called supporters, to top-up a borrowing position and grant the borrower additional time to rescue the debt. Our simulation shows that Miqado reduces the amount of liquidated collateral by 89.82% in a worst-case scenario.

We present a new block cipher mode of operation for authenticated encryption (AE), dubbed XOCB, that has the following features: (1) beyond-birthday-bound (BBB) security based on the standard pseudorandom assumption of the internal block cipher if the maximum block length is sufficiently smaller than the birthday bound, (2) rate-1 computation, and (3) supporting any block cipher with any key length. Namely, XOCB has effectively the same efficiency as the seminal OCB while having stronger quantitative security without any change in the security model or the required primitive in OCB. Although numerous studies have been conducted in the past, our XOCB is the first mode of operation to achieve these multiple goals simultaneously.

We show how to obfuscate pseudo-deterministic quantum circuits, assuming the quantum hardness of learning with errors (QLWE) and post-quantum virtual black-box (VBB) obfuscation for classical circuits. Given the classical description of a quantum circuit $Q$, our obfuscator outputs a quantum state $\ket{\widetilde{Q}}$ that can be used to evaluate $Q$ repeatedly on arbitrary inputs.

Instantiating the VBB obfuscator for classical circuits with any candidate post-quantum indistinguishability obfuscator gives us the first candidate construction of indistinguishability obfuscation for all polynomial-size pseudo-deterministic quantum circuits. In particular, our scheme is the first candidate obfuscator for a class of circuits that is powerful enough to implement Shor's algorithm (SICOMP 1997).

Our approach follows Bartusek and Malavolta (ITCS 2022), who obfuscate null quantum circuits by obfuscating the verifier of an appropriate classical verification of quantum computation (CVQC) scheme. We go beyond null circuits by constructing a publicly-verifiable CVQC scheme for quantum partitioning circuits, which can be used to verify the evaluation procedure of Mahadev's quantum fully-homomorphic encryption scheme (FOCS 2018). We achieve this by upgrading the one-time secure scheme of Bartusek (TCC 2021) to a fully reusable scheme, via a publicly-decodable Pauli functional commitment, which we formally define and construct in this work. This commitment scheme, which satisfies a notion of binding against committers that can access the receiver's standard and Hadamard basis decoding functionalities, is constructed by building on techniques of Amos, Georgiou, Kiayias, and Zhandry (STOC 2020) introduced in the context of equivocal but collision-resistant hash functions.

Hardware-based Root of Trust (HRT) is considered the gold standard for bootstrapping trust in secure computing. This paper analyzes HRT implementations across state-of-the-art TEEs and differentiates HRT implementation across two dimensions: 1) Security Properties & Threats and 2) Hardware Capabilities. Later, this work analyzes and compares 1) Intel SGX, 2) ARM TrustZone, 3) NXP Trust Architecture, 4) AMD SEV, 5) Microsoft Pluton, and 6) Apple T2 HRTs in terms of threats, security properties, and capabilities.

We give the first black box lower bound for signature protocols that can be described as group actions, which include many based on isogenies. We show that, for a large class of signature schemes making black box use of a (potentially non-abelian) group action, the signature length must be $\Omega(\lambda^2/\log\lambda)$. Our class of signatures generalizes all known signatures that derive security exclusively from the group action, and our lower bound matches the state of the art, showing that the signature length cannot be improved without deviating from the group action framework.

Anamorphic Encryption, recently introduced by Persiano, Phan, and Yung (EUROCRYPT 2022) is a new cryptographic paradigm challenging the conventional notion of an adversary. In particular they consider the receiver-anamorphic setting, where a dictator is able to obtain the receiver's secret key of a well-established public-key encryption (PKE) scheme, and they ask the question whether the sender can still embed covert messages in a way which the dictator is completely oblivious to, if sender and receiver share an anamorphic key.

In this work, we identify two definitional limitations of Persiano et al.'s original model. First, they require anamorphic keys and key-pairs to be generated together, so a first modification we propose is to decouple the two processes. We allow for the extension of a regular PKE scheme to an anamorphic one to be possible on the fly, even after the public key of the regular scheme is already in use. Second, in their model the receiver cannot distinguish whether or not a ciphertext contains a covert message, so we propose a natural robustness notion which states that when anamorphically decrypting a regularly encrypted message, the receiver explicitly sees that no covert message is contained. This also eliminates certain attacks possible for the original definition.

Regarding new constructions, we first propose a generic anamorphic extension that achieves robustness for any PKE scheme, but requires synchronization of sender and receiver. We then define a natural property of a PKE scheme, selective randomness recoverability, which allows for a robust anamorphic extension even for unsynchronized parties. We show that the well-established schemes of ElGamal and Cramer-Shoup satisfy this condition. Finally, we propose a generic transformation of any non-robust anamorphic extension into a robust one, and apply it to a synchronized anamorphic extension for RSA-OAEP.

Hierarchical Identity Based Encryption (HIBE) is a well studied, versatile tool used in many cryptographic protocols. Yet, since the performance of all known HIBE constructions is broadly considered prohibitive, some real-world applications avoid relying on HIBE at the expense of security. A prominent example for this is secure messaging: Strongly secure messaging protocols are provably equivalent to Key-Updatable Key Encapsulation Mechanisms (KU-KEMs; Balli et al., Asiacrypt 2020); so far, all KU-KEM constructions rely on adaptive unbounded-depth HIBE (Poettering and Rösler, Jaeger and Stepanovs, both CRYPTO 2018). By weakening security requirements for better efficiency, many messaging protocols dispense with using HIBE.

In this work, we aim to gain better efficiency without sacrificing security. For this, we observe that applications like messaging only need a restricted variant of HIBE for strong security. This variant, that we call Unique-Path Identity Based Encryption (UPIBE), restricts HIBE by requiring that each secret key can delegate at most one subordinate secret key. However, in contrast to fixed secret key delegation in Forward-Secure Public Key Encryption, the delegation in UPIBE, as in HIBE, is uniquely determined by variable identity strings from an exponentially large space. We investigate this mild but surprisingly effective restriction and show that it offers substantial complexity and performance advantages.

More concretely, we generically build bounded-depth UPIBE from only bounded-collusion IBE in the standard model; and we generically build adaptive unbounded-depth UPIBE from only selective bounded-depth HIBE in the random oracle model. These results significantly extend the range of underlying assumptions and efficient instantiations. We conclude with a rigorous performance evaluation of our UPIBE design. Beyond solving challenging open problems by reducing complexity and improving efficiency of KU-KEM and strongly secure messaging protocols, we offer a new definitional perspective on the bounded-collusion setting.

The problem of decoding random codes is a fundamental problem for code-based cryptography, including recent code-based candidates in the NIST post-quantum standardization process. In this paper, we present a novel sieving-style information-set decoding (ISD) algorithm for solving the syndrome decoding problem. The essential idea is to keep a list of weight-$2p$ solution vectors to a partial syndrome decoding problem and then create new vectors by finding pairs of vectors that collide in $p$ positions. By increasing the parity-check condition by one position and then iteratively repeating this process, we find the final solution(s). We show that while being competitive in terms of performance, our novel algorithm requires significantly less memory compared to other ISD variants. Also, in the case of problems with very low relative weight, it seems to outperform all previous algorithms. In particular, for code-based candidates BIKE and HQC, the algorithm has lower bit complexity than the previous best results.

We extend and consolidate the security justification for the Dilithium signature scheme. In particular, we identify a subtle but crucial gap that appears in several ROM and QROM security proofs for signature schemes that are based on the Fiat-Shamir with aborts paradigm, including Dilithium. The gap lies in the CMA-to-NMA reduction and was uncovered when trying to formalize a variant of the QROM security proof by Kiltz, Lyubashevsky, and Schaffner (Eurocrypt 2018). The gap was confirmed by the authors, and there seems to be no simple patch for it. We provide new, fixed proofs for the affected CMA-to-NMA reduction, both for the ROM and the QROM, and we perform a concrete security analysis for the case of Dilithium to show that the claimed security level is still valid after addressing the gap. Furthermore, we offer a fully mechanized ROM proof for the CMA-security of Dilithium in the EasyCrypt proof assistant. Our formalization includes several new tools and techniques of independent interest for future formal verification results.

Lyubashevky's signatures are based on the Fiat-Shamir with Aborts paradigm. It transforms an interactive identification protocol that has a non-negligible probability of aborting into a signature by repeating executions until a loop iteration does not trigger an abort. Interaction is removed by replacing the challenge of the verifier by the evaluation of a hash function, modeled as a random oracle in the analysis. The access to the random oracle is classical (ROM), resp. quantum (QROM), if one is interested in security against classical, resp. quantum, adversaries. Most analyses in the literature consider a setting with a bounded number of aborts (i.e., signing fails if no signature is output within a prescribed number of loop iterations), while practical instantiations (e.g., Dilithium) run until a signature is output (i.e., loop iterations are unbounded).

In this work, we emphasize that combining random oracles with loop iterations induces numerous technicalities for analyzing correctness, run-time, and security of the resulting schemes, both in the bounded and unbounded case. As a first contribution, we put light on errors in all existing analyses. We then provide two detailed analyses in the QROM for the bounded case, adapted from Kiltz et al. [EUROCRYPT'18] and Grilo et al. [ASIACRYPT'21]. In the process, we prove the underlying $\Sigma$-protocol to achieve a stronger zero-knowledge property than usually considered for $\Sigma$-protocols with aborts, which enables a corrected analysis. A further contribution is a detailed analysis in the case of unbounded aborts, the latter inducing several additional subtleties.

Properties of quantum mechanics have enabled the emergence of quantum cryptographic protocols achieving important goals which are proven to be impossible classically. Unfortunately, this usually comes at the cost of needing quantum power from every party in the protocol, while arguably a more realistic scenario would be a network of classical clients, classically interacting with a quantum server. In this paper, we focus on copy-protection, which is a quantum primitive that allows a program to be evaluated, but not copied, and has shown interest especially due to its links to other unclonable cryptographic primitives. Our main contribution is to show how to dequantize existing quantum copy-protection from hidden coset states, by giving a construction for classically-instructed remote state preparation for coset states. We also present the first secure copy-protection scheme for point-functions in the plain model, to which our dequantizer can be applied.

The LWE problem is one of the prime candidates for building the most efficient post-quantum secure public key cryptosystems. Many of those schemes, like Kyber, Dilithium or those belonging to the NTRU-family, such as NTRU-HPS, -HRSS, BLISS or GLP, make use of small max norm keys to enhance efficiency. The best attack on these schemes is a hybrid attack, which combines combinatorial techniques and lattice reduction. While lattice reduction is not known to be able to exploit the small max norm choices, May recently showed (Crypto 2021) that such choices allow for more efficient combinatorial attacks.

However, these combinatorial attacks suffer enormous memory requirements, which render them inefficient in realistic attack scenarios and, hence, make their general consideration when assessing security questionable. Therefore, more memory-efficient substitutes for these algorithms are needed. In this work, we provide new combinatorial algorithms for recovering small max norm LWE secrets using only a polynomial amount of memory. We provide analyses of our algorithms for secret key distributions of current NTRU, Kyber and Dilithium variants, showing that our new approach outperforms previous memory-efficient algorithms. For instance, considering uniformly random ternary secrets of length $n$ we improve the best known time complexity for polynomial memory algorithms from $2^{1.063n}$ down-to $2^{0.926n}$. We obtain even larger gains for LWE secrets in $\{-m,\ldots,m\}^n$ with $m=2,3$ as found in Kyber and Dilithium. For example, for uniformly random keys in $\{-2,\ldots,2\}^n$ as is the case for Dilithium we improve the previously best time from $2^{1.742n}$ down-to $2^{1.282n}$.

Our fastest algorithm incorporates various different algorithmic techniques, but at its heart lies a nested collision search procedure inspired by the Nested-Rho technique from Dinur, Dunkelman, Keller and Shamir (Crypto 2016). Additionally, we heavily exploit the representation technique originally introduced in the subset sum context to make our nested approach efficient.