International Association
for Cryptologic Research

The celebrated result by Gentry and Wichs established a theoretical barrier for succinct non-interactive arguments (SNARGs), showing that for (expressive enough) hard-on-average languages we must assume non-falsifiable assumptions. We further investigate those barriers by showing new negative and positive results related to extractability and to the preprocessing model. 1. We first ask the question “are there further barriers to SNARGs that are knowledge-sound (SNARKs) and with a black-box extractor?”. We show it is impossible to have such SNARKs in the standard model. This separates SNARKs in the random oracle model (which can have black-box extraction) and those in the standard model. 2. We find positive results regarding the same question in the non-adaptive setting. Under the existence of SNARGs (without extractability) and from standard assumptions, it is possible to build SNARKs with black-box extractability for a non-trivial subset of NP. 3. On the other hand, we show that (under some mild assumptions) all NP languages cannot have SNARKs with black-box extractability even in the non-adaptive setting. 4. The Gentry-Wichs result does not account for the preprocessing model, under which fall several efficient constructions. We show that also in the preprocessing model it is impossible to construct SNARGs that rely on falsifiable assumptions in a black-box way. Along the way, we identify a class of non-trivial languages, which we dub “trapdoor languages”, that bypass some of these impossibility results.

In attribute-based proxy re-encryption (AB-PRE) and attribute-based conditional proxy re-encryption (AB-CPRE) systems, the proxy transforms a ciphertext associated with policy $f$ to a ciphertext associated with policy $g$ or transforms a ciphertext for delegator satisfying a fine-grained condition to a ciphertext for delegatee. However, such PRE schemes have found many practical applications requiring fine-grained access control while keeping flexible delegation. Unfortunately, the existing PRE schemes are impossible to handle simultaneously with the above scenarios. In this work, we introduce the notion of conditional attribute-based proxy re-encryption (CAB-PRE), which enables a proxy only to transform a ciphertext associated with policy $f$ meeting the special delegation requirements by delegator to a ciphertext associated with policy $g$. We formalize its honestly re-encryption attacks (HRA) security model that implies CPA-secure, giving a concrete CAB-PRE scheme based on learning with errors (LWE) assumption. Finally, we show that CAB-PRE implies AB-PRE and AB-CPRE notions, and propose their constructions.

Code-based cryptography received attention after the NIST started the post-quantum cryptography standardization process in 2016. A central NP-hard problem is the binary syndrome decoding problem, on which the security of many code-based cryptosystems lies. The best known methods to solve this problem all stem from the information-set decoding strategy, first introduced by Prange in 1962. A recent line of work considers augmented versions of this strategy, with hints typically provided by side-channel information. In this work, we consider the integer syndrome decoding problem, where the integer syndrome is available but might be noisy. We study how the performance of the decoder is affected by the noise. We provide experimental results on cryptographic parameters for the BIKE and Classic McEliece cryptosystems, which are finalist and alternate candidates for the third round of the NIST standardization process, respectively.

The ability to trust a system to act safely and securely strongly relies on the integrity of the software that it runs. To guarantee authenticity of the software one can include cryptographic data such as digital signatures on application images that can only be generated by trusted parties. These are typically based on cryptographic primitives such as Rivest-Shamir-Adleman (RSA) or Elliptic-Curve Cryptography (ECC), whose security will be lost whenever a large enough quantum computer is built. For that reason, migration towards Post-Quantum Cryptography (PQC) is necessary. This paper investigates the practical impact of migrating the secure boot flow on a Vehicle Network Processor (S32G274A) towards PQC. We create a low-memory fault-attack- resistant implementation of the Dilithium signature verification algorithm and evaluate its impact on the boot flow.

Threshold signature schemes enable distribution of the signature issuing capability to multiple users, to mitigate the threat of signing key compromise. Though a classic primitive, these signatures have witnessed a surge of interest in recent times due to relevance to modern applications like blockchains and cryptocurrencies. In this work, we study round-optimal threshold signatures in the post- quantum regime and improve the only known lattice-based construction by Boneh et al [CRYPTO’18] as follows:

• Efficiency. We reduce the amount of noise flooding used in the construction from $2^{\Omega(\lambda)}$ down to $\sqrt{Q}$, where $Q$ is the bound on the number of generated signatures and $\lambda$ is the security parameter. By using lattice hardness assumptions over polynomial rings, this allows to decrease the signature bit-lengths from $\widetilde{O}(\lambda^3)$ to~$\widetilde{O}(\lambda)$, bringing them significantly closer to practice. Our improvement relies on a careful analysis using Rényi divergence rather than statistical distance in the security proof.

• Instantiation. The construction of Boneh et al requires a standard signature scheme to be evaluated homomorphically. To instantiate this, we provide a homomorphism-friendly variant of Lyubashevsky’s signature [EUROCRYPT ’12] which achieves low circuit depth by being “rejection-free” and uses an optimal, moderate noise flooding of $\sqrt{Q}$, matching the above.

• Towards Adaptive Security. The construction of Boneh et al satisfies only selective security, where all the corrupted parties must be announced before any signing query is made. We improve this in two ways: in the Random Oracle Model, we obtain partial adaptivity where signing queries can be made before the corrupted parties are announced but the set of corrupted parties must be announced all at once. In the standard model, we obtain full adaptivity, where parties can be corrupted at any time but this construction is in a weaker pre-processing model where signers must be provided correlated randomness of length proportional to the number of signatures, in an offline preprocessing phase.

Homomorphic encryption (HE), which allows computation over encrypted data, has often been used to preserve privacy. However, the computationally heavy nature and complexity of network topologies make the deployment of HE schemes in the Internet of Things (IoT) scenario difficult. In this work, we propose CARM, the first optimized GPU implementation that covers BGV, BFV and CKKS, targeting for accelerating homomorphic multiplication using GPU in heterogeneous IoT systems. We offer constant-time low-level arithmetic with minimum instructions and memory usage, as well as performance- and memory-prior configurations, and exploit a parametric and generic design, and offer various trade-offs between resource and efficiency, yielding a solution suitable for accelerating RNS homomorphic multiplication on both high-performance and embedded GPUs. Through this, we can offer more real-time evaluation results and relieve the computational pressure on cloud devices. We deploy our implementations on two GPUs and achieve up to 378.4×, 234.5×, and 287.2× speedup for homomorphic multiplication of BGV, BFV, and CKKS on Tesla V100S, and 8.8×, 9.2×, and 10.3× on Jetson AGX Xavier, respectively.

Rainbow, a multivariate digital signature scheme and third round finalist in NIST's PQC standardization process, is a layered version of the unbalanced oil and vinegar (UOV) scheme. We introduce two fault attacks, each focusing on one of the secret linear transformations $T$ and $S$ used to hide the structure of the central map in Rainbow. The first fault attack reveals a part of $T$ and we prove that this is enough to achieve a full key recovery with negligible computational effort for all parameter sets of Rainbow. The second one unveils $S$, which can be extended to a full key recovery by the Kipnis-Shamir attack. Our work exposes the secret transformations used in multivariate signature schemes as an important attack vector for physical attacks, which need further protection. Our attacks target the optimized Cortex-M4 implementation and require only first-order instruction skips and a moderate amount of faulted signatures.

We initiate the study of software watermarking against quantum adversaries. A quantum adversary generates a quantum state as a pirate software that potentially removes an embedded message from a classical marked software. Extracting an embedded message from quantum pirate software is difficult since measurement could irreversibly alter the quantum state. In software watermarking against classical adversaries, a message extraction algorithm crucially uses the (input-output) behavior of a classical pirate software to extract an embedded message. Even if we instantiate existing watermarking PRFs with quantum-safe building blocks, it is not clear whether they are secure against quantum adversaries due to the quantum-specific property above. Thus, we need entirely new techniques to achieve software watermarking against quantum adversaries.

In this work, we define secure watermarking PRFs for quantum adversaries (unremovability against quantum adversaries). We also present two watermarking PRFs as follows.

- We construct a privately extractable watermarking PRF against quantum adversaries from the quantum hardness of the learning with errors (LWE) problem. The marking and extraction algorithms use a public parameter and a private extraction key, respectively. The watermarking PRF is unremovable even if adversaries have (the public parameter and) access to the extraction oracle, which returns a result of extraction for a queried quantum circuit.

- We construct a publicly extractable watermarking PRF against quantum adversaries from indistinguishability obfuscation (IO) and the quantum hardness of the LWE problem. The marking and extraction algorithms use a public parameter and a public extraction key, respectively. The watermarking PRF is unremovable even if adversaries have the extraction key (and the public parameter).

We develop a quantum extraction technique to extract information (a classical string) from a quantum state without destroying the state too much. We also introduce the notion of extraction-less watermarking PRFs as a crucial building block to achieve the results above by combining the tool with our quantum extraction technique.

Cryptographic constant-time (CT) is a popular programming disci- pline used by cryptographic libraries to protect themselves against timing attacks. The CT discipline aims to enforce that program ex- ecution does not leak secrets, where leakage is defined by a formal leakage model. In practice, different leakage models coexist, some- times even within a single library, both to reflect different architec- tures and to accommodate different security-efficiency trade-offs. Constant-timeness is popular and can be checked automatically by many tools. However, most sound tools are focused on a baseline (BL) leakage model. In contrast, (sound) verification methods for other leakage models are less developed, in part because these mod- els require modular arithmetic reasoning. In this paper, we develop a systematic, sound, approach for enforcing fine-grained constant- time policies beyond the BL model. Our approach combines two main ingredients: a verification infrastructure, which proves that source programs are constant-time, and a compiler infrastructure, which provably preserves constant-timeness for these fine-grained policies. By making these infrastructures parametric in the leakage model, we achieve the first approach that supports fine-grained constant-time policies. We implement the approach in the Jasmin framework for high-assurance cryptography, and we evaluate our approach with examples from the literature: OpenSSL and wolfSSL. We found a bug in OpenSSL and provided a formally verified fix.

Functional Encryption (FE) allows users who hold a specific decryption key, to learn a specific function of encrypted data while the actual plaintexts remain private. While FE is still in its infancy, it is our strong belief that in the years to come, this remarkable cryptographic primitive will have matured to the degree that will make it an integral part of access control systems, especially cloud-based ones. To this end, we believe it is of great importance to provide not only theoretical and generic constructions but also concrete instantiations of FE schemes from well-studied cryptographic assumptions. Therefore, in this paper, we undertake the task of presenting two instantiations of the generic work presented in [8] from the Decisional Die-Hellman (DDH) problem that also satisfies the property of verifiable decryption. Moreover, we present a novel multi-input FE (MIFE) scheme, that can be instantiated from Regev's cryptosystem, and thus remains secure even against quantum adversaries. Finally, we provide a multi-party computation (MPC) protocol that allows our MIFE construction to be deployed in the multi-client mode

Along the rapid development in building large-scale quantum computers, post-quantum cryptography (PQC) has drawn significant attention from research community recently as it is proven that the existing public-key cryptosystems are vulnerable to the quantum attacks. Following this direction, this paper presents a novel implementation of high-performance polynomial multiplication hardware accelerators for key encapsulation mechanism (KEM) Saber and NTRU, two PQC algorithms that are currently under the consideration by the National Institute of Standards and Technology (NIST) PQC standardization process. In total, we have carried out three layers of efforts to obtain the proposed work. First of all, we have proposed a new Dual Cyclic-Row Oriented Processing (Dual-CROP) technique to build a high-performance polynomial multiplication hardware accelerator for KEM Saber. Then, we have extended this hardware accelerator to NTRU with proper innovation and adjustment. Finally, through a series of complexity analysis and implementation based comparison, we have shown that the proposed hardware accelerators obtain better area-time complexities than known existing ones. It is expected that the outcome of this work can impact the ongoing NIST PQC standardization process and can be deployed further to construct efficient cryptoprocessors.

Over the past decade, cryptocurrency has been undergoing a rapid development. Digital wallet, as the tool to store and manage the cryptographic keys, is the primary entrance for the public to access cryptocurrency assets. Hierarchical Deterministic Wallet (HDW), proposed in Bitcoin Improvement Proposal 32 (BIP32), has attracted much attention and been widely used in the community, due to its virtues such as easy backup/recovery, convenient cold-address management, and supporting trust-less audits and applications in hierarchical organizations. While HDW allows the wallet owner to generate and manage his keys conveniently, Stealth Address (SA) allows a payer to generate fresh address (i.e., public key) for the receiver without any interaction, so that users can achieve ``one coin each address" in a very convenient manner, which is widely regarded as a simple but effective way to protect user privacy. Consequently, SA has also attracted much attention and been widely used in the community. However, as so far, there is not a secure wallet algorithm that provides the virtues of both HDW and SA. Actually, even for standalone HDW, to the best of our knowledge, there is no strict definition of syntax and models that captures the functionality and security (i.e., safety of coins and privacy of users) requirements that practical scenarios in cryptocurrency impose on wallet. As a result, the existing wallet algorithms either have (potential) security flaws or lack crucial functionality features.

In this work, we formally define the syntax and security models of Hierarchical Deterministic Wallet supporting Stealth Address (HDWSA), capturing the functionality and security (including safety and privacy) requirements imposed by the practice in cryptocurrency, which include all the versatile functionalities that lead to the popularity of HDW and SA as well as all the security guarantees that underlie these functionalities. We propose a concrete HDWSA construction and prove its security in the random oracle model. We implement our scheme and the experimental results show that the efficiency is suitable for typical cryptocurrency settings.

As the first generic method for finding the optimal differential and linear characteristics, Matsui's branch and bound search algorithm has played an important role in evaluating the security of symmetric ciphers. By combining the Matsui's bounding conditions with automatic search models, the search efficiency can be improved. All the previous methods realize the bounding conditions by adding a set of constraints. This may increase the searching complexity of models. In this paper, by using Information Theory to quantify the effect of bounding conditions, we give the general form of bounding conditions that can use all the information provided by Matsui's bounding conditions. Then, a new method of combining bounding conditions with sequential encoding method is proposed. Different from all the previous methods, our new method can realize the bounding conditions by removing the variables and clauses from Satisfiability Problem (SAT) models based on the original sequential encoding method. With the help of some small size Mixed Integer Linear Programming (MILP) models, we build the simplest SAT model of combining Matsui's bounding conditions with sequential encoding method. Then, we apply our new method to search the optimal differential and linear characteristics of some SPN, Feistel, and ARX block ciphers. The number of variables, clauses and the solving time of the SAT models are decreased significantly. And we find some new differential and linear characteristics covering more rounds. For example, the optimal differential probability of the full rounds GIFT128 is obtained for the first time.

State-of-the-art Byzantine fault-tolerant (BFT) protocols assuming partial synchrony such as SBFT and HotStuff use regular certificates obtained from $2f+1$ (partial) signatures. We show in this paper that one can use weak certificates obtained from only $f+1$ signatures to design more robust and much more efficient BFT protocols. We devise Dashing (a family of three HotStuff-style BFT protocols) and Star (a parallel BFT framework).

We begin with Dashing1 that targets both efficiency and robustness using weak certificates. Dashing1 is partition-tolerant and network-adaptive, and does not rely on fallback asynchronous BFT protocols. Dashing2 is a variant of Dashing1 and focuses on performance only. Then we show in Dashing3 how to further enable a fast path by using strong certificates obtained from $3f+1$ signatures, a challenging task we tackled in the paper.

We then leverage weak certificates to build a highly efficient BFT framework (Star) that delivers transactions from $n-f$ replicas using only a single consensus instance in the standard BFT model. Star completely separates bulk data transmission from consensus. Moreover, its data transmission process uses $O(n^2)$ messages only and can be effectively pipelined.

We demonstrate that the Dashing protocols achieve 10.7%-29.9% higher peak throughput than HotStuff. Meanwhile, Star, when being instantiated using PBFT, is an order of magnitude faster than HotStuff. Furthermore, unlike the Dashing protocols and HotStuff whose performance degrades as $f$ grows, the peak throughput of Star increases as $f$ grows. When deployed in a WAN with 91 replicas across five continents, Star achieves 243 ktx/sec, 15.8x the throughput of HotStuff.

We investigate the security assumptions behind three public-key quantum money schemes. Aaronson and Christiano proposed a scheme based on hidden subspaces of the vector space $\mathbb{F}_2^n$ in 2012. It was conjectured by Pena et al in 2015 that the hard problem underlying the scheme can be solved in quasi-polynomial time. We confirm this conjecture by giving a polynomial time quantum algorithm for the underlying problem. Our algorithm is based on computing the Zariski tangent space of a random point in the hidden subspace. Zhandry proposed a scheme based on multivariate hash functions in 2017. We give a polynomial time quantum algorithm for cloning a money state with high probability. Our algorithm uses the verification circuit of the scheme to produce a banknote from a given serial number. Kane proposed a scheme based on modular forms in 2018. The underlying hard problem in Kane's scheme is cloning a quantum state that represents an eigenvector of a set of Hecke operators. We give a polynomial time quantum reduction from this hard problem to a linear algebra problem. The latter problem is much easier to understand, and we hope that our reduction opens new avenues to future cryptanalyses of this scheme.

We introduce a new MPC protocol to securely compute any functionality over an arbitrary black-box finite ring (which may not be commutative), tolerating $t
Furthermore, the amortized communication complexity of our protocol is not only constant, but very small: only $1 + \frac{t-1}{n}<1\frac{1}{3}$ ring elements per party, per multiplication gate over two rounds of interaction. This improves over the state-of-the art protocol in the same setting by Furukawa and Lindell (CCS 2019), which has a communication complexity of $2\frac{2}{3}$ \emph{field} elements per party, per multiplication gate and while achieving fairness only. As an alternative, we also describe a variant of our protocol which has only one round of interaction per multiplication gate on average, and amortized communication cost of $\le 1\frac{1}{2}$ ring elements per party on average for any natural circuit.

Motivated by the fact that efficiency of distributed protocols are much more penalized by high communication complexity than local computation/storage, we perform a detailed analysis together with experiments in order to explore how large the number of parties can be, before the storage and computation overhead becomes prohibitive. Our results show that our techniques are viable even for a moderate number of parties (e.g., $n>10$).

We design and implement a new efficient and accurate Fully homomorphic argmin/min or argmax/max comparison operator, which finds its application in numerous real-world use cases as a classifier. In particular we propose two versions of our algorithms using different tools from TFHE's functional bootstrapping toolkit. Our algorithm scales to any number of input data points with linear time complexity and logarithmic noise-propagation. Our algorithm is the fastest on the market for non-parallel comparisons with a high degree of accuracy and precision. For MNIST and SVHN datasets, which work under the PATE framework, using our algorithm, we achieve an accuracy of around 99.95 % for both.

We present position-hiding linkability for vector commitment schemes: one can prove in zero knowledge that one or $m$ values that comprise commitment cm all belong to the vector of size $N$ committed to in C. Our construction Caulk can be used for membership proofs and lookup arguments and outperforms all existing alternatives in prover time by orders of magnitude. For both single- and multi-membership proofs Caulk beats SNARKed Merkle proofs by the factor of 100 even if the latter instantiated with Poseidon hash. Asymptotically our prover needs $O(m^2 + m\log N)$ time to prove a batch of $m$ openings, whereas proof size is $O(1)$ and verifier time is $O(\log(\log N))$. As a lookup argument, Caulk is the first scheme with prover time sublinear in the table size, assuming $O(N\log N)$ preprocessing time and $O(N)$ storage. It can be used as a subprimitive in verifiable computation schemes in order to drastically decrease the lookup overhead. Our scheme comes with a reference implementation and benchmarks.

The significant progress in the development of quantum computers has made the study of cryptanalysis based on quantum computing an active topic. To accurately estimate the resources required to carry out quantum attacks, the involved quantum algorithms have to be synthesized into quantum circuits with basic quantum gates. In this work, we present several generic synthesis and optimization techniques for circuits implementing the quantum oracles of iterative symmetric-key ciphers that are commonly employed in quantum attacks based on Grover and Simon’s algorithms. Firstly, a general structure for implementing the round functions of block ciphers in-place is proposed. Then, we present some novel techniques for synthesizing efficient quantum circuits of linear and non-linear cryptographic building blocks. We apply these techniques to AES and systematically investigate the strategies for depth-width trade-offs. Along the way, we derive a quantum circuit for the AES S-box with provably minimal T-depth based on some new observations on its classical circuit. As a result, the T-depth and width (number of qubits) required for implementing the quantum circuits of AES are significantly reduced. Compared with the circuit proposed in EUROCRYPT 2020, the T-depth is reduced from 60 to 40 without increasing the width or 30 with a slight increase in width. These circuits are fully implemented in Microsoft Q# and the source code is publicly available. Compared with the circuit proposed in ASIACRYPT 2020, the width of one of our circuits is reduced from 512 to 371, and the Toffoli-depth is reduced from 2016 to 1558 at the same time. Actually, we can reduce the width to 270 at the cost of increased depth. Moreover, a full spectrum of depth-width trade-offs is provided, setting new records for the synthesis and optimization of quantum circuits of AES.

We present the first proactive secret sharing under honest majority which is purely over pairwise asynchronous channels. Moreover: - it has robust reconstruction. In addition, provided a single broadcast in the sharing phase, then it commits the dealer to a value; - it operates under a bare PKI and enables dynamic membership; - the standard version carries over the model known as \cst{receiver-anonymous (Yoso)} in which participants speak only once then erase their memories. Each refresh of a secret takes $2$ actual message delays and a total of $O(n^4)$ bits sent by the honest \players; - it allows an optimization in $O(n^3)$ bits sent and latency of $5$ messages.