International Association
for Cryptologic Research

Zero-knowledge proof systems are becoming increasingly prevalent and being widely used to secure decentralized financial systems and protect the privacy of users. Given the sensitivity of these applications, zero-knowledge proof systems are a natural target for formal verification methods. We describe methods for checking one such proof system: Halo2. We use abstract interpretation and an SMT solver to check various properties of Halo2 circuits. Using abstract interpretation, we can detect unused gates, unconstrained cells, and unused columns. Using an SMT solver, we can detect under-constrained (in the sense that for the same public input they have two efficiently computable satisfying assignments) circuits. This is the first work we are aware of that applies lightweight formal methods to PLONKish arithmetization and Halo2 circuits.

We construct a succinct non-interactive argument ($\mathsf{SNARG}$) for the class of monotone policy batch $\mathsf{NP}$ languages under the Learning with Errors ($\mathsf{LWE}$) assumption. This class is a subclass of $\mathsf{NP}$ that is associated with a monotone function~$f:\{0,1\}^k\rightarrow\{0,1\}$ and an $\mathsf{NP}$ language $\mathcal L$, and contains instances $(x_1,\ldots,x_k)$ such that $f(b_1,\ldots,b_k)=1$ where $b_j=1$ if and only if $x_j\in \mathcal L$. Our $\mathsf{SNARG}$s are arguments of knowledge in the non-adaptive setting, and satisfy a new notion of somewhere extractability against adaptive adversaries.

This is the first $\mathsf{SNARG}$ under standard hardness assumptions for a sub-class of $\mathsf{NP}$ that is not known to have a (computational) non-signaling $\mathsf{PCP}$ with small locality. Indeed, our approach necessarily departs from the known framework of constructing $\mathsf{SNARG}$s dating back to [Kalai-Raz-Rothblum, STOC '13]

Our construction combines existing quasi-arguments for $\mathsf{NP}$ (based on batch arguments for $\mathsf{NP}$) with a novel ingredient which we call a predicate-extractable hash ($\mathsf{PEH}$) family. This notion generalizes the notion of a somewhere extractable hash. Whereas a somewhere extractable hash allows to extract a single input coordinate, our $\mathsf{PEH}$ extracts a global property of the input. We view this primitive to be of independent interest, and believe that it will find other applications.

The low-degree method postulates that no efficient algorithm outperforms low-degree polynomials in certain hypothesis-testing tasks. It has been used to understand computational indistinguishability in high-dimensional statistics.

We explore the use of the low-degree method in the context of cryptography. To this end, we apply it in the design and analysis of a new public-key encryption scheme whose security is based on Goldreich's pseudorandom generator. The scheme is a combination of two proposals of Applebaum, Barak, and Wigderson, and inherits desirable features from both.

Topological Data Analysis (TDA) offers a suite of computational tools that provide quantified shape features in high dimensional data that can be used by modern statistical and predictive machine learning (ML) models. In particular, persistent homology (PH) takes in data (e.g., point clouds, images, time series) and derives compact representations of latent topological structures, known as persistence diagrams (PDs). Because PDs enjoy inherent noise tolerance, are interpretable and provide a solid basis for data analysis, and can be made compatible with the expansive set of well-established ML model architectures, PH has been widely adopted for model development including on sensitive data, such as genomic, cancer, sensor network, and financial data. Thus, TDA should be incorporated into secure end-to-end data analysis pipelines. In this paper, we take the first step to address this challenge and develop a version of the fundamental algorithm to compute PH on encrypted data using homomorphic encryption (HE).

We construct the first tight verifiable delay function (VDF) where the evaluation algorithm only evaluates sequentially the function and hence outputs and empty proof, verification is independent of time parameter $T$ and setup has constant size parameters. Our VDF is based on repeated squaring in hidden order groups, but it requires that coins used to sample a random instance must be kept secret in order to guarantee sequentiality. We denote such a VDF as a private coin verifiable delay function and show that it can be used to obtain multiplicatively homomorphic non-interactive timed commitment with efficient publicly verifiable force decommitment algorithm.

Lattice-based cryptographic schemes such as Crystals-Kyber and Dilithium are post-quantum algorithms selected to be standardized by NIST as they are considered to be secure against quantum computing attacks. The multiplication in polynomial rings is the most time-consuming operation in many lattice-based cryptographic schemes, which is also subject to side-channel attacks. While NTT-based polynomial multiplication is almost a norm in a wide range of implementations, a relatively new method, incomplete-NTT is preferred to accelerate lattice-based cryptography, especially on some computing platforms that feature special instructions. In this paper, we present a novel, efficient and non-profiled power/EM side-channel attack targeting polynomial multiplication based on the incomplete NTT algorithm. We apply the attack on the Crystals-Dilithium signature algorithm and demonstrate that the method accelerates attack run-time when compared to conventional correlation power attacks (CPA). While a conventional CPA tests much larger hypothesis set due to the fact that it needs to predict two coefficients of secret polynomials together, we propose a much faster zero-value filtering attack (ZV-FA), which reduces the size of the hypothesis set by targeting the coefficients individually. We also propose an effective and efficient validation and correction technique to estimate and modify the mis-predicted coefficients. Our experimental results show that we can achieve a speed-up of 128.1× over conventional CPA using a total of 13K traces.

Zero-Knowledge proof systems are widely used as building blocks of different protocols, e.g., such as those supporting blockchains. A core element in Zero-Knowledge proof systems is the underlying PRF, usually modeled as a hash function that needs to be efficient over finite fields of prime order. Such hash functions are part of a newly developed paradigm known as Arithmetization-Oriented designs.

In this paper, we propose two new AO hash functions, XHash8 and XHash12 which are designed based on improving the bottlenecks in RPO [ePrint 2022/1577]. Based on our experiments, XHash8 performs $\approx2.75$ times faster than RPO, and XHash12 performs $\approx2$ times faster than RPO, while at the same time inheriting the security and robustness of the battle-tested Marvellous design strategy.

The problem of designing authenticated key establishment protocols has a rich history. Since 1976 more than a hundred different protocols have been proposed. But the task of comparing and classifying existing protocols is usually complicated by the fact that they are described in different terms and with different levels of detail. This paper contains intermediate results on enumeration and uniform description of AKE protocols. We publish it in order to get feedback on the description principles used. Here we describe 100 AKE protocols (there are much more such protocols, but we found these earlier) in identical terms and the same level of detail. The proposed descriptions are not structured (chronologically only) but classifying of these protocols is future work direction.

In recent years, personal and medical data collected through mobile apps has become a useful data source for researchers. Platforms like Apple ResearchKit try to make it as easy as possible for non-experts to set up such data collection campaigns. However, since the collected data is sensitive, it must be well protected. Methods that provide technical privacy guarantees often limit the usefulness of the data and results. In this paper, we model and analyze mobile data donation to better understand the requirements that must be fulfilled by privacy-preserving approaches. To this end, we give an overview of the functionalities researchers require from data donation apps by analyzing existing apps. We also create a model of the current practice and analyze it using the LINDDUN privacy framework to identify privacy threats.

In response to side-channel attacks on masked implementations of post-quantum cryptographic algorithms, a new bitsliced higher-order masked implementation of CRYSTALS-Kyber has been presented at CHES'2022. The bitsliced implementations are typically more difficult to break by side-channel analysis because they execute a single instruction across multiple bits in parallel. However, in this paper, we reveal new vulnerabilities in the masked Boolean to arithmetic conversion procedure of this implementation that make the shared and secret key recovery possible. We also present a new chosen ciphertext construction method which maximizes secret key recovery probability for a given message bit recovery probability. We demonstrate practical shared and secret key recovery attacks on the first-, second- and third-order masked implementations of Kyber-768 in ARM Cortex-M4 using profiled deep learning-based power analysis.

Suppose two parties have hash functions $h_1$ and $h_2$ respectively, but each only trusts the security of their own. We wish to build a hash combiner $C^{h_1, h_2}$ which is secure so long as either one of the underlying hash functions is. This question has been well-studied in the regime of collision resistance. In this case, concatenating the two hash outputs clearly works. Unfortunately, a long series of works (Boneh and Boyen, CRYPTO'06; Pietrzak, Eurocrypt'07; Pietrzak, CRYPTO'08) showed no (noticeably) shorter combiner for collision resistance is possible.

We revisit this pessimistic state of affairs, motivated by the observation that collision-resistance is insufficient for many applications of cryptographic hash functions anyway. We argue the right formulation of the "hash combiner" is what we call random oracle (RO) combiners.

Indeed, we circumvent the previous lower bounds for collision resistance by constructing a simple length-preserving RO combiner $$\widetilde{C}_{\mathcal{Z}_1,\mathcal{Z}_2}^{h_1,h_2}(M) = h_1(M, \mathcal{Z}_1) \oplus h_2(M, \mathcal{Z}_2),$$ where $\mathcal{Z}_1, \mathcal{Z}_2$ are random salts of appropriate length. We show that this extra randomness is necessary for RO combiners, and indeed our construction is somewhat tight with this lower bound.

On the negative side, we show that one cannot generically apply the composition theorem to further replace "monolithic" hashes $h_1$ and $h_2$ by some simpler indifferentiable construction (such as the Merkle-Damgård transformation) from smaller components, such as fixed-length compression functions. Despite this issue, we directly prove collision resistance of the Merkle-Damgård variant of our combiner, where $h_1$ and $h_2$ are replaced by iterative Merkle-Damgård hashes applied to fixed-length compression functions. Thus, we can still subvert the concatenation barrier for collision-resistance combiners using practically small components.

Homomorphic encryption (HE) enables computation delegation to untrusted third-party while maintaining data confidentiality. Hybrid encryption (a.k.a Transciphering) allows a reduction in the number of ciphertexts and storage size, which makes HE solutions practical for a variety of modern applications. Still, modern transciphering has two main drawbacks: 1) lack of standardization or bad performance of symmetric decryption under FHE; 2) lack of input data integrity. In this paper, we discuss the concept of Authenticated Transciphering (AT), which like Authenticated Encryption (AE) provides some integrity guarantees for the transciphered data. For that, we report on the first implementations of AES-GCM decryption and Ascon decryption under CKKS. Moreover, we report and demonstrate the first end-to-end process that uses transciphering for real-world applications i.e., running deep neural network inference (ResNet50 over ImageNet) under encryption.

Modern security systems depend fundamentally on the ability of users to authenticate their communications to other parties in a network. Unfortunately, cryptographic authentication can substantially undermine the privacy of users. One possible solution to this problem is to use privacy-preserving cryptographic authentication. These protocols allow users to authenticate their communications without revealing their identity to the verifier. In the non-interactive setting, the most common protocols include blind, ring, and group signatures, each of which has been the subject of enormous research in the security and cryptography literature. These primitives are now being deployed at scale in major applications, including Intel's SGX software attestation framework. The depth of the research literature and the prospect of large-scale deployment motivate us to systematize our understanding of the research in this area. This work provides an overview of these techniques, focusing on applications and efficiency.

The advent of quantum computers poses a serious challenge to the security of cloud infrastructures and services, as they can potentially break the existing public-key cryptosystems, such as Rivest–Shamir–Adleman (RSA) and Elliptic Curve Cryptography (ECC). Even though the gap between today’s quantum computers and the threats they pose to current public-key cryptography is large, the cloud landscape should act proactively and initiate the transition to the post-quantum era as early as possible. To comply with that, the U.S. government issued a National Security Memorandum in May 2022 that mandated federal agencies to migrate to post-quantum cryptosystems (PQC) by 2035. To ensure the long-term security of cloud computing, it is imperative to develop and deploy PQC resistant to quantum attacks. A promising class of post-quantum cryptosystems is based on lattice problems, which require polynomial arithmetic. In this paper, we propose and implement a scalable number-theoretic transform (NTT) architecture that significantly enhances the performance of polynomial multiplication. Our proposed design exploits multi-levels of parallelism to accelerate the NTT computation on reconfigurable hardware. We use the high-level synthesis (HLS) method to implement our design, which allows us to describe the NTT algorithm in a high-level language and automatically generate optimized hardware code. HLS facilitates rapid prototyping and enables us to explore different design spaces and trade-offs on the hardware platforms. Our experimental results show that our design achieves 11$\times$ speedup compared to the state-of-the-art requiring only 14 clock cycles for an NTT computation over a polynomial of degree 256. To demonstrate the applicability of our design, we also present a coprocessor architecture for Kyber, a key encapsulation mechanism (KEM) chosen by the NIST post-quantum standardization process, that utilizes our scalable NTT core.

Modern system-on-chip (SoC) designs are becoming prone to numerous security threats due to their critical applications and ever-growing complexity and size. Therefore, the early stage of the design flow requires comprehensive security verification. The control flow of an SoC, generally implemented using finite state machines (FSMs), is not an exception to this requirement. Any deviations from the desired flow of FSMs can cause serious security issues. On the other hand, the control FSMs may be prone to fault-injection and denial-of-service (DoS) attacks or have inherent information leakage and access control issues at the gate-level netlist abstraction. Therefore, defining a set of security rules (guidelines) for obtaining FSM implementations free from particular security vulnerabilities after performing logic synthesis is crucial. Unfortunately, as of today, no solution exists in the state-of-the-art domain to verify the security of control FSMs. In this paper, we propose a set of such security rules for control FSM design and a verification framework called ARC-FSM-G to check for those security rule violations at pre-silicon to prevent any security vulnerabilities of FSM against fault-injection, access control, and information leakage threats. Experimental results on several benchmarks varying in size and complexity illustrate that ARC-FSM-G can effectively check for violations of all the proposed rules within a few seconds.

Perfect ciphers have been a very attractive cryptographic tool ever since C. Shannon described them. Note that, by definition, if a perfect cipher is used, no one can get any information about the encrypted message without knowing the secret key. We consider the problem of reducing the key length of perfect ciphers, because in many applications the length of the secret key is a crucial parameter. This paper describes a simple method of key length reduction. This method gives a perfect cipher and is based on the use of data compression and randomisation, and the average key length can be made close to Shannon entropy (which is the key length limit). It should be noted that the method can effectively use readily available data compressors (archivers).

We introduce a new candidate post-quantum digital signature scheme from the regular syndrome decoding (RSD) assumption, an established variant of the syndrome decoding assumption which asserts that it is hard to find $w$-regular solutions to systems of linear equations over $\mathbb{F}_2$ (a vector is regular if it is a concatenation of $w$ unit vectors). Our signature is obtained by introducing and compiling a new 5-round zero-knowledge proof system constructed using the MPC-in-the-head paradigm. At the heart of our result is an efficient MPC protocol in the preprocessing model that checks the correctness of a regular syndrome decoding instance by using a share ring-conversion mechanism.

The analysis of our construction is non-trivial and forms a core technical contribution of our work. It requires careful combinatorial analysis and combines several new ideas, such as analyzing soundness in a relaxed setting where a cheating prover is allowed to use any witness sufficiently close to a regular vector. We complement our analysis with an in-depth overview of existing attacks against RSD.

Our signatures are competitive with the best-known code-based signatures, ranging from $12.52$ KB (fast setting, with a signing time of the order of a few milliseconds on a single core of a standard laptop) to about $9$ KB (short setting, with estimated signing time of the order of 15ms).

With the growing number of decentralized finance applications, transaction fairness in blockchains has gained intensive research interest. As a broad concept in the distributed systems and blockchain literature, fairness has been used in different contexts, varying from ones related to the system's liveness to ones that focus on the received order of transactions. In this work, we revisit the fairness definitions known so far and provide a more generic fairness definition called verifiable fairness. Our definition relaxes the ordering rules that are inherently embedded in prior definitions to a predicate defined by concrete applications. Our notion thus gains flexibility and generality, capturing all existing fairness definitions. We provide a solution that achieves our new fairness definition, leveraging trusted hardware. Unlike prior works that usually design a dedicated consensus protocol to achieve fairness goals, our solution is modular and can be integrated with any blockchain system. We implement a prototype using Go Ethereum (Geth) as the blockchain and OpenSGX as the trusted hardware. Evaluation results reveal that our construction imposes only minimal overhead on existing blockchain systems.

Our research focuses on achieving perfect provable encryption by drawing inspiration from the principles of a one-time pad. We explore the potential of leveraging the unique properties of the one-time pad to design effective one-way functions. Our methodology involves the application of the exclusive-or (xor) operation to two randomly chosen strings. To address concerns related to preimage mappings, we incorporate error detection codes. Additionally, we utilize permutations to overcome linearity issues in the computation process.

In order to enhance the security of our approach, we propose the integration of a secret-sharing scheme based on a linear polynomial. This helps mitigate collisions and adds an additional layer of perfect security. We thoroughly investigate the interactions between different aspects of one-way functions to strengthen the reliability of commitments. Lastly, we explore the possibility of nesting one-way functions as a countermeasure against potential backdoors.

Through our study, we aim to contribute to the advancement of secure encryption techniques by leveraging the inherent strengths of the one-time pad and carefully considering the interplay of various components in the design of one-way functions.

This paper's primary purpose is to provide a source of introductory information into building a zero knowledge proof system for general computation. We review how to build such a system with a polynomial commitment scheme, and how to implement a fully functional command set in terms of zero knowledge primitives.