International Association
for Cryptologic Research

The Byzantine Fault Tolerance (BFT) protocol is a long-standing topic. Recently, a lot of efforts have been made in the research of asynchronous BFT. However, the existing solutions cannot adapt well to the flexible network environment, and suffer from problems such as high communication complexity or long latency. To improve the efficiency of BFT consensus in flexible networks, we propose FaBFT. FaBFT's clients can make their own assumptions about the network conditions, and make the most of their networks based on different network assumptions. We also use the BlockDAG structure and an efficient consistent broadcast protocol to improve the concurrency and reduce the number of steps in FaBFT. The comparison with other asynchronous BFT protocols shows that FaBFT has lower complexity and cancels the dependency on the view change. We prove that FaBFT is an atomic broadcast protocol in the flexible networks.

The partial sums cryptanalytic technique was introduced in 2000 by Ferguson et al., who used it to break 6-round AES with time complexity of $2^{52}$ S-box computations -- a record that has not been beaten ever since. In 2014, Todo and Aoki showed that for 6-round AES, partial sums can be replaced by a technique based on the Fast Fourier Transform (FFT), leading to an attack with a comparable complexity.

In this paper we show that the partial sums technique can be combined with an FFT-based technique, to get the best of the two worlds. Using our combined technique, we obtain an attack on 6-round AES with complexity of about $2^{46.4}$ additions. We fully implemented the attack experimentally, along with the partial sums attack and the Todo-Aoki attack, and confirmed that our attack improves the best known attack on 6-round AES by a factor of more than 32.

We expect that our technique can be used to significantly enhance numerous attacks that exploit the partial sums technique. To demonstrate this, we use our technique to improve the best known attack on 7-round Kuznyechik by a factor of more than 80, and to reduce the complexity of the best known attack on the full MISTY1 from $2^{69.5}$ to $2^{67}$.

In TCHES’22, Shen et al. proposed Triplex, a single-pass leakage-resistant authenticated encryption scheme based on Tweakable Block Ciphers (TBCs) with 2n-bit tweaks. Triplex enjoys beyond-birthday-bound ciphertext integrity in the CIML2 setting and birthday-bound confidentiality in the CCAmL1 notion. Despite its strengths, Triplex’s operational efficiency was hindered by its sequential nature, coupled with a rate limit of 2/3. In an endeavor to surmount these efficiency challenges, Peters et al. proposed Multiplex, a variant of Triplex with increased parallelism and a flexible rate of d/(d+1) that retains similar security guarantees. However, the innovation came at the price of requiring TBCs with dn-bit tweaks, which are unusual and potentially costly for d > 3. In this paper, we investigate the limits of generalized Triplex- and Multiplex-type constructions for single-pass leakage-resilient authenticated encryption. Our contributions are threefold. First, we show that such constructions cannot provide CIML2 integrity for any tweak lengths below dn/2 bits. Second, we provide a birthday-bound attack for constructions with TBCs of tweak lengths between dn/2 and (d − 1)n + n/2 bits. Finally, on the constructive side, we propose a family of single-pass leakage-resilient authenticated ciphers, dubbed Tweplex, that uses tweaks of dn/2 bits and provides a rate of d/(d + 1) while providing n/2-bit CIML2 integrity and CCAmL1 confidentiality.

In recent years, the elliptic curve Qu-Vanstone (ECQV) implicit certificate scheme has found application in security credential management systems (SCMS) and secure vehicle-to-everything (V2X) communication to issue pseudonymous certificates. However, the vulnerability of elliptic-curve cryptography (ECC) to polynomial-time attacks posed by quantum computing raises concerns. In order to enhance resistance against quantum computing threats, various post-quantum cryptography methods have been adopted as standard (e.g. Dilithium) or candidate standard methods (e.g. McEliece cryptography), but state of the art has proven to be challenging to implement implicit certificates using lattice-based cryptography methods. Therefore, this study proposes a post-quantum cryptography McEliece-Chen (PQCMC) based on an efficient random invertible matrix generation method to issue pseudonymous certificates with less computation time. The study provides mathematical models to validate the key expansion process for implicit certificates. Furthermore, comprehensive security evaluations and discussions are conducted to demonstrate that distinct implicit certificates can be linked to the same end entity. In experiments, a comparison is conducted between the certificate length and computation time to evaluate the performance of the proposed PQCMC. This study demonstrates the viability of the implicit certificate scheme based on PQC as a means of countering quantum computing threats.

The global lockdown imposed during the Covid-19 pandemic has resulted in significant social and economic challenges. In an effort to reopen economies and simultaneously control the spread of the disease, the implementation of contact tracing and digital vaccine passport technologies has been introduced. While contact tracing methods have been extensively studied and scrutinized for security concerns through numerous publications, vaccine passports have not received the same level of attention in terms of defining the problems they address, establishing security requirements, or developing efficient systems. Many of the existing methods employed currently suffer from privacy issues. This work introduces PPass, an advanced digital vaccine passport system that prioritizes user privacy. We begin by outlining the essential security requirements for an ideal vaccine passport system. To address these requirements, we present two efficient constructions that enable PPass to function effectively across various environments while upholding user privacy. By estimating its performance, we demonstrate the practical feasibility of PPass. Our findings suggest that PPass can efficiently verify a passenger’s vaccine passport in just 7 milliseconds, with a modest bandwidth requirement of 480KB.

Suppose a prover, in possession of a large body of valuable evidence, wants to quickly convince a verifier by presenting only a small portion of the evidence.

We define an Approximate Lower Bound Argument, or ALBA, which allows the prover to do just that: to succinctly prove knowledge of a large number of elements satisfying a predicate (or, more generally, elements of a sufficient total weight when a predicate is generalized to a weight function). The argument is approximate because there is a small gap between what the prover actually knows and what the verifier is convinced the prover knows. This gap enables very efficient schemes.

We present noninteractive constructions of ALBA in the random oracle and uniform reference string models and show that our proof sizes are nearly optimal. We also show how our constructions can be made particularly communication-efficient when the evidence is distributed among multiple provers, which is of practical importance when ALBA is applied to a decentralized setting.

We demonstrate two very different applications of ALBAs: for large-scale decentralized signatures and for proving universal composability of succinct proofs.

We present a general framework for polynomial-time lattice Gaussian sampling. It revolves around a systematic study of the discrete Gaussian measure and its samplers under extensions of lattices; we first show that given lattices $\Lambda'\subset \Lambda$ we can sample efficiently in $\Lambda$ if we know how to do so in $\Lambda'$ and the quotient $\Lambda/\Lambda'$, \emph{regardless} of the primitivity of $\Lambda'$. As a direct application, we tackle the problem of domain extension and restriction for sampling and propose a sampler tailored for lattice \emph{filtrations}, which can be seen as a broad generalization of the celebrated Klein's sampler. Then, we demonstrate how to sample using a change of bases, or even switching the ambient space, even when the target lattice is not represented as full-rank in the ambient space. We show how to correct the induced distortion with the ``convolution-like'' technique of Peikert (Crypto 2010) (which we encompass as a byproduct). Since our framework aims at modularity and leverage the combinations of smaller samplers to build new ones, we also propose ad-hoc samplers for the so-called \emph{root lattices} $\mathsf{A}_n, \mathsf{D}_n, \mathsf{E}_n$ as base cases, extending the state-of-the-art for root lattice sampling, which was limited to $\mathbb{Z}^n$. We also show how our framework blends with the so-called $k$ing construction and provides a sampler for the remarkable Leech and Barnes-Wall lattices.

As a by-product, we obtain novel, quasi-linear samplers for prime and smooth conductor (as $2^\ell 3^k$) cyclotomic rings, achieving essentially optimal Gaussian width. In a practice-oriented application, we showcase the impact of our work on hash-and-sign signatures over \textsc{ntru} lattices. In the best case, we can gain around 200 bytes (which corresponds to an improvement greater than 20\%) on the signature size. We also improve the new gadget-based constructions (Yu, Jia, Wang, Crypto 2023) and gain up to 110 bytes for the resulting signatures.

Lastly, we sprinkle our exposition with several new estimates for the smoothing parameter of lattices, stemming from our algorithmic constructions and by novel methods based on series reversion.

QCB is a proposal for a post-quantum secure, rate-one authenticated encryption with associated data scheme (AEAD) based on classical OCB3 and \(\Theta\)CB, which are vulnerable against a quantum adversary in the Q2 setting. The authors of QCB prove integrity under plus-one unforgeability, whereas the proof of the stronger definition of blind unforgeability has been left as an open problem. After a short overview of QCB and the current state of security definitions for authentication, this work proves blind unforgeability of QCB. Finally, the strategy of using tweakable block ciphers in authenticated encryption is generalised to a generic blindly unforgeable AEAD model.

$\Sigma$-protocols are a widely utilized, relatively simple and well understood type of zero-knowledge proofs. However, the well known Schnorr $\Sigma$-protocol for proving knowledge of discrete logarithm in a cyclic group of known prime order, and similar protocols working over this type of groups, are hard to generalize to dealing with other groups. In particular with hidden order groups, due to the inability of the knowledge extractor to invert elements modulo the order.

In this paper, we introduce a universal construction of $\Sigma$-protocols designed to prove knowledge of preimages of group homomorphisms for any abelian finite group. In order to do this, we first establish a general construction of a $\Sigma$-protocol for $\mathfrak{R}$-module homomorphism given only a linear secret sharing scheme over the ring $\mathfrak{R}$, where zero knowledge and special soundness can be related to the privacy and reconstruction properties of the secret sharing scheme. Then, we introduce a new construction of 2-out-of-$n$ packed black-box secret sharing scheme capable of sharing $k$ elements of an arbitrary (abelian, finite) group where each share consists of $k+\log n-3$ group elements. From these two elements we obtain a generic ``batch'' $\Sigma$-protocol for proving knowledge of $k$ preimages of elements via the same group homomorphism, which communicates $k+\lambda-3$ elements of the group to achieve $2^{-\lambda}$ knowledge error.

For the case of class groups, we show that our $\Sigma$-protocol improves in several aspects on existing proofs for knowledge of discrete logarithm and other related statements that have been used in a number of works.

Finally, we extend our constructions from group homomorphisms to the case of ZK-ready functions, introduced by Cramer and Damg\aa rd in Crypto 09, which in particular include the case of proofs of knowledge of plaintext (and randomness) for some linearly homomorphic encryption schemes such as Joye-Libert encryption. However, in the case of Joye-Libert, we show an even better alternative, using Shamir secret sharing over Galois rings, which achieves $2^{-k}$ knowledge soundness by communicating $k$ ciphertexts to prove $k$ statements.

Publicly Verifiable Secret Sharing (PVSS) allows a dealer to publish encrypted shares of a secret so that parties holding the corresponding decryption keys may later reconstruct it. Both dealing and reconstruction are non-interactive and any verifier can check their validity. PVSS finds applications in randomness beacons, distributed key generation (DKG) and in YOSO MPC (Gentry et al. CRYPTO'21), when endowed with suitable publicly verifiable re-sharing as in YOLO YOSO (Cascudo et al. ASIACRYPT'22).

We introduce a PVSS scheme over class groups that achieves similar efficiency to state-of-the art schemes that only allow for reconstructing a function of the secret, while our scheme allows the reconstruction of the original secret. Our construction generalizes the DDH-based scheme of YOLO YOSO to operate over class groups, which poses technical challenges in adapting the necessary NIZKs in face of the unknown group order and the fact that efficient NIZKs of knowledge are not as simple to construct in this setting.

Building on our PVSS scheme's ability to recover the original secret, we propose two DKG protocols for discrete logarithm key pairs: a biasable 1-round protocol, which improves on the concrete communication/computational complexities of previous works; and a 2-round unbiasable protocol, which improves on the round complexity of previous works. We also add publicly verifiable resharing towards anonymous committees to our PVSS, so that it can be used to efficiently transfer state among committees in the YOSO setting. Together with a recent construction of MPC in the YOSO model based on class groups (Braun et al. CRYPTO'23), this results in the most efficient full realization (i.e without assuming receiver anonymous channels) of YOSO MPC based on the CDN framework with transparent setup.

The security of multivariate polynomial cryptography depends on the computational complexity of solving a multivariate quadratic polynomial system (MQ problem). One of the fastest algorithms for solving the MQ problem is F4, which computes a Groebner basis but requires numerous calculations of zero reduction that do not affect the output.The Hilbert-driven algorithm evaluates the number of generators in the Groebner basis of degree $d$ using Hilbert series, then it reduces the number of zero reduction computations. In this paper, we propose a high-speed algorithm designed for randomly generated semi-regular MQ problems. Although the Hilbert-driven algorithm is limited to computing homogeneous ideals, we demonstrate its applicability to semi-regular non-homogeneous ideals in this work. Furthermore, when using the Hilbert-driven algorithm to solve non-homogeneous MQ problems with F4, we demonstrate the efficient achievement of reducing zero reduction for F4. We implemented the proposed algorithm in C++ and report successful decryption of a new record $m=21$ Type VI equations. This was achieved using an AMD EPYC 7742 processor and 2TB RAM, and the decryption process was completed within approximately 9 h.

Homomorphic Encryption (HE) is one of the mainstream cryptographic tools used to enable secure outsourced computation. A typical task is secure matrix computation. Popular HE schemes are all based on the problem of Ring Learning with Errors (RLWE), where the messages are encrypted in a ring. In general, the ring dimension should be large to ensure security, which is often larger than the matrix size. Hence, exploiting the ring structure to make fast homomorphic matrix computation has been an important topic in HE. In this paper, we present a new framework for encoding a matrix and performing multiplication on encrypted matrices. The new framework requires fewer basic homomorphic operations for matrix multiplication. Suppose that the ring dimension is $n$ and the matrix size is $d\times d$ with $d= n^{\rho}$. (1) In the compact case where $\rho \leq \frac{1}{3}$, the multiplication of two encrypted matrices requires $\tilde{O}(1)$ basic homomorphic operations, which include plaintext-ciphertext multiplications, ciphertext-ciphertext multiplications, and homomorphic Galois automorphisms. (2) In the large sized case where $\rho> \frac{1}{3}$, our new method requires $O\big(d^{(1 - \frac{1}{3\rho})\cdot \log_2 7 }\big)$ basic homomorphic operations, which is better than all existing methods. In addition, the new framework reduces the communication cost, since it requires fewer key-switching keys. The number of key-switching keys is reduced from $O(d)$ to $O(\log d)$.

When Satoshi Nakamoto introduced Bitcoin, a central tenet was that the blockchain functions as a timestamping server. In the Ethereum era, smart contracts widely assume on-chain timestamps are mostly accurate. In this paper, we prove this is indeed the case, namely that recorded timestamps do not wildly deviate from real-world time, a property we call timeliness. Assuming a global clock, we prove that all popular mechanisms for constructing blockchains (proof-of-work, longest chain proof-of-stake, and quorum-based proof-of-stake) are timely under honest majority, but a synchronous network is a necessary condition. Next we show that all timely blockchains can be suitably modified, in a black-box fashion, such that all honest parties output exactly the same ledgers at the same round, achieving a property we call supersafety, which may be of independent interest. Conversely, we also show that supersafety implies (perfect) timeliness, completing the circle.

Over the last decades, fault injection attacks have been demonstrated to be an effective method for breaking the security of electronic devices. Some types of fault injection attacks, like clock and voltage glitching, require very few resources by the attacker and are practical and simple to execute. A cost-effective countermeasure against these attacks is the use of a detector circuit which detects timing violations - the underlying effect that glitch attacks rely on. In this paper, we take a closer look at three examples of such detectors that have been presented in the literature. We demonstrate four high-speed clock glitching attacks, which successfully inject faults in systems, where detectors have been implemented to protect. The attacks remain unnoticed by the glitch detectors. We verify our attacks with practical experiments on an FPGA.

Proof-carrying data (PCD) is a powerful cryptographic primitive that allows mutually distrustful parties to perform distributed computation in an efficiently verifiable manner. Applications of PCD have sparked keen interest within the applied community and industry.

Known constructions of PCD are obtained by recursively-composing SNARKs or related primitives. Unfortunately, these constructions do not come with security analyses that yield useful concrete security bounds, leaving practitioners in the dark about how to securely instantiate PCD constructions.

In this work we study the concrete security of recursive composition, with the goal of enabling practitioners to set efficient parameters for certain PCD constructions of practical interest. Our main result is that PCD obtained from SNARKs with \emph{straightline knowledge soundness} has essentially the same security as the underlying SNARK. In this setting, recursive composition incurs no security loss.

We describe how straightline knowledge soundness is achieved by SNARKs in several oracle models, including SNARKs that are deployed in practice. Crucially, SNARKs in these settings can be \emph{relativized}, allowing us to construct PCD without instantiating the SNARK's oracle explicitly. This results in a highly efficient security analysis of PCD that makes black-box use of the SNARK's oracle.

As a notable application, our work offers an idealized model that provides useful, albeit heuristic, guidance for setting the security parameters of \emph{recursive STARKs} currently used in blockchain systems.

In 2019, Wan, Liao, Yan and Tsai proposed an article ``Discrete Sliding Mode Control for Chaos Synchronization and Its Application to an Improved ElGamal Cryptosystem''. However, Wan et al. just renamed the variable names without modified the core algorithm. Their paper passed review phase and then published. For this case, it is difficult to detect this situation by computer/digital forensics techniques. In this paper the authors would like to point out this dilemmas.

Domain Generation Algorithms (DGAs) are used by malware to generate pseudorandom domain names to establish communication between infected bots and Command and Control servers. While DGAs can be detected by machine learning (ML) models with great accuracy, offering DGA detection as a service raises privacy concerns when requiring network administrators to disclose their DNS traffic to the service provider. We propose the first end-to-end framework for privacy-preserving classification as a service of domain names into DGA (malicious) or non-DGA (benign) domains. We achieve this through a combination of two privacy-enhancing technologies (PETs), namely secure multi-party computation (MPC) and differential privacy (DP). Through MPC, our framework enables an enterprise network administrator to outsource the problem of classifying a DNS domain as DGA or non-DGA to an external organization without revealing any information about the domain name. Moreover, the service provider's ML model used for DGA detection is never revealed to the network administrator. Furthermore, by using DP, we also ensure that the classification result cannot be used to learn information about individual entries of the training data. Finally, we leverage the benefits of quantization of deep learning models in the context of MPC to achieve efficient, secure DGA detection. We demonstrate that we achieve a significant speed-up resulting in a 15% reduction in detection runtime without reducing accuracy.

In the ever-evolving landscape of Information Technologies, private decentralized computing on an honest yet curious server has emerged as a prominent paradigm. While numerous schemes exist to safeguard data during computation, the focus has primarily been on protecting the confidentiality of the data itself, often overlooking the potential information leakage arising from the function evaluated by the server. Recognizing this gap, this article aims to address the issue by presenting and implementing an innovative solution for ensuring the privacy of both the data and the program. We introduce a novel approach that combines the power of Fully Homomorphic Encryption with the concept of the Turing Machine model, resulting in the first fully secure practical, non-interactive oblivious Turing Machine. Our Oblivious Turing Machine construction is based on only three hypothesis, the hardness of the Ring Learning With Error problem, the ability to homomorphically evaluate non-linear functions and the capacity to blindly rotate elements of a data structure. Only based on those three assumptions, we propose an implementation of an Oblivious Turing Machine relying on the TFHE cryptosystem and present some implementation results.

Fully homomorphic encryption is a promising solution for privacy-preserving computation. For BFV, BGV, and CKKS, three state-of-the-art fully homomorphic encryption schemes, the so-called key switching is one of the primary bottlenecks when evaluating homomorphic circuits. While a large body of work explores optimal selection for scheme parameters such as the polynomial degree or the ciphertext modulus, the realm of key switching parameters is relatively unexplored.

This work closes this gap, formally exploring the parameter space for BGV-like key switching. We introduce a new asymptotic bound for key switching complexity, thereby providing a new perspective on this crucial operation. We also explore the parameter space for the recently proposed double-decomposition technique by Kim et al. [24], which outperforms current state-of-the-art only in very specific circumstances. Furthermore, we revisit an idea by Gentry, Halevi, and Smart [19] switching primes in and out of the ciphertext and find novel opportunities for constant folding, speeding up key switching by up to 50% and up to 11.6%, respectively.

Symmetric Private Information Retrieval (SPIR) is a protocol that protects privacy during data transmission. However, the existing SPIR focuses only on the privacy of the data to be requested on the server, without considering practical factors such as the payload that may be present during data transmission. This could seriously prevent SPIR from being applied to many complex data scenarios and hinder its further expansion. To solve such problems, we propose a primitive (PSKPIR) for symmetric private keyword information retrieval based on private set intersection (PSI) that supports payload transmission and batch keyword search. Specifically, we combine probe-and-XOR of strings (PaXoS) and Oblivious Programmable PRF (OPPRF) to construct PSI with payload (PSI-Payload) not only satisfies client privacy and server privacy, but also facilitates efficient payload transmission. The client can efficiently generate symmetric keys locally using keywords in the intersection, and receive payloads with matching labels in batches. In addition, we provide security definitions for PSKPIR and use the framework of universal composability (UC) to prove security. Finally, we implement PSKPIR with sublinear communication costs in both LAN and WAN settings. Experimental results show that our payload transfer speed is 10× faster than previous work on sufficiently large data sets.