International Association
for Cryptologic Research

Finite field multiplication is widely used for masking countermeasures against side-channel attacks. The execution time of finite field multiplication implementation is critical as it greatly impacts the overhead of the countermeasure. In this context, the use of exp-log tables is popular for the implementation of finite field multiplication. Yet, its performance is affected by the need for particular code to handle the case where one of the operands equals zero, as log is undefined for zero. As noticed by two recent papers, the zero case can be managed without any extra code by extending the exp table and setting $log[0]$ to a large-enough value. The multiplication of $a$ and $b$ then becomes as simple as: $exp[log[a]+log[b]]$. In this paper, we compare this approach with other implementations of finite field multiplication and show that it provides a good trade-off between memory use and execution time.

The block cipher GOST 28147-89 was the Russian Federation encryption standard for over 20 years, and is still one of its two standard block ciphers. GOST is a 32-round Feistel construction, whose security benefits from the fact that the S-boxes used in the design are kept secret. In the last 10 years, several attacks on the full 32-round GOST were presented. However, they all assume that the S-boxes are known. When the S-boxes are secret, all published attacks either target a small number of rounds, or apply for small sets of weak keys. In this paper we present the first practical-time attack on GOST with secret S-boxes. The attack works in the related-key model and is faster than all previous attacks in this model which assume that the S-boxes are known. The complexity of the attack is less than $2^{27}$ encryptions. It was fully verified, and runs in a few seconds on a PC. The attack is based on a novel type of related-key differentials of GOST, inspired by local collisions. Our new technique may be applicable to certain GOST-based hash functions as well. To demonstrate this, we show how to find a collision on a Davies-Meyer construction based on GOST with an arbitrary initial value, in less than $2^{10}$ hash function evaluations.

Blockchain consensus algorithms for cryptocurrency consist of the proof of work and proof of stake. However, current algorithms have problems, such as huge power consumption and equality issues. We propose a new consensus algorithm that uses transaction history. This algorithm ensures equality by randomly assigning approval votes based on past transaction records. We also incorporate a mechanism for adjusting issuance volume to measure the stability of the currency's value.

We conduct a systematic study of solving the learning parity with noise problem (LPN) using neural networks. Our main contribution is designing families of two-layer neural networks that practically outperform classical algorithms in high-noise, low-dimension regimes. We consider three settings where the numbers of LPN samples are abundant, very limited, and in between. In each setting we provide neural network models that solve LPN as fast as possible. For some settings we are also able to provide theories that explain the rationale of the design of our models.

Comparing with the previous experiments of Esser, Kübler, and May (CRYPTO 2017), for dimension $n=26$, noise rate $\tau = 0.498$, the "Guess-then-Gaussian-elimination'' algorithm takes 3.12 days on 64 CPU cores, whereas our neural network algorithm takes 66 minutes on 8 GPUs. Our algorithm can also be plugged into the hybrid algorithms for solving middle or large dimension LPN instances.

To be useful and widely accepted, automated contact tracing / expo- sure notification schemes need to solve two problems at the same time: they need to protect the privacy of users while also protecting the users’ from the behavior of a malicious adversary who may potentially cause a false alarm. In this paper, we provide, for the first time, an exposure notification construction that guarantees the same levels of privacy as ex- isting schemes (notably, the same as CleverParrot of [CKL+20]), which also provides the following integrity guarantees: no malicious user can cause exposure warnings in two locations at the same time; and any up- loaded exposure notifications must be recent, and not previously used. We provide these integrity guarantees while staying efficient by only re- quiring a single broadcast message to complete multiple contacts. Also, a user’s upload remains linear in the number of contacts, similar to other schemes. Linear upload complexity is achieved with a new primitive: zero knowledge subset proofs over commitments. Our integrity guarantees are achieved with a new primitive as well: set commitments on equivalence classes. Both of which are of independent interest.

We build quantum cryptosystems that support publicly-verifiable deletion from standard cryptographic assumptions. We introduce target-collapsing as a weakening of collapsing for hash functions, analogous to how second preimage resistance weakens collision resistance; that is, target-collapsing requires indistinguishability between superpositions and mixtures of preimages of an honestly sampled image. We show that target-collapsing hashes enable publicly-verifiable deletion (PVD), proving conjectures from [Poremba, ITCS'23] and demonstrating that the Dual-Regev encryption (and corresponding fully homomorphic encryption) schemes support PVD under the LWE assumption. We further build on this framework to obtain a variety of primitives supporting publicly-verifiable deletion from weak cryptographic assumptions, including: - Commitments with PVD assuming the existence of injective one-way functions, or more generally, almost-regular one-way functions. Along the way, we demonstrate that (variants of) target-collapsing hashes can be built from almost-regular one-way functions. - Public-key encryption with PVD assuming trapdoored variants of injective (or almost-regular) one-way functions. We also demonstrate that the encryption scheme of [Hhan, Morimae, and Yamakawa, Eurocrypt'23] based on pseudorandom group actions has PVD. - $X$ with PVD for $X \in \{$attribute-based encryption, quantum fully-homomorphic encryption, witness encryption, time-revocable encryption$\}$, assuming $X$ and trapdoored variants of injective (or almost-regular) one-way functions.

We introduce Lurk, a new LISP-based programming language for zk-SNARKs. Traditional approaches to programming over zero-knowledge proofs require compiling the desired computation into a flat circuit, imposing serious constraints on the size and complexity of computations that can be achieved in practice. Lurk programs are instead provided as data to the universal Lurk interpreter circuit, allowing the resulting language to be Turing-complete without compromising the size of the resulting proof artifacts. Our work describes the design and theory behind Lurk, along with detailing how its implementation of content addressing can be used to sidestep many of the usual concerns of programming zero-knowledge proofs.

During the last decade, there has been a stunning progress in the domain of AI with adoption in both safety-critical and security-critical applications. A key requirement for this is highly trained Machine Learning (ML) models, which are valuable Intellectual Property (IP) of the respective organizations. Naturally, these models have become targets for model recovery attacks through side-channel leakage. However, majority of the attacks reported in literature are either on simple embedded devices or assume a custom Vivado HLS based FPGA accelerator. On the other hand, for commercial neural network accelerators, such as Google TPU, Intel Compute Stick and NVDLA, there are relatively fewer successful attacks. Focussing on that direction, in this work, we study the vulnerabilities of commercial open-source accelerator NVDLA and present the first successful model recovery attack. For this purpose, we use power and timing side-channel leakage information from Convolutional Neural Network (CNN) models to train CNN based attack models. Utilizing these attack models, we demonstrate that even with a highly pipelined architecture, multiple parallel execution in the accelerator along with Linux OS running tasks in the background, recovery of number of layers, kernel sizes, output neurons and distinguishing different layers, is possible with very high accuracy. Our solution is fully automated, and portable to other hardware neural networks, thus presenting a greater threat towards IP protection.

As a typical representative of the public key cryptosystem, RSA has attracted a great deal of cryptanalysis since its invention, among which a famous attack is the small private exponent attack. It is well-known that the best theoretical upper bound for the private exponent d that can be attacked is d ≤ N^0.292 , where N is a RSA modulus. However, this bound may not be achieved in practical attacks since the lattice constructed by Coppersmith method may have a large enough dimension and the lattice-based reduction algorithms cannot work so well in both efficiency and quality. In this paper, we propose a new practical attack based on the binary search for the most significant bits (MSBs) of prime divisors of N and the Herrmann-May’s attack in 2010. The idea of binary search is inspired by the discovery of phenomena called “multivalued-continuous phenomena”, which can significantly accelerate our attack. Together with several carefully selected parameters according to our exact and effective numerical estimations, we can improve the upper bound of d that can be practically achieved. We believe our method can provide some inspiration to practical attacks on RSA with mainstream-size moduli.

We propose how to homomorphically evaluate arbitrary univariate and bivariate integer functions such as division. A prior work proposed by Okada et al. (WISTP'18) uses polynomial evaluations such that the scheme is still compatible with the SIMD operations in BFV and BGV, and is implemented with the input domain size $\mathbb{Z}_{257}$. However, the scheme of Okada et al. requires the quadratic number of plaintext-ciphertext multiplications and ciphertext-ciphertext additions in the input domain size, and although these operations are more lightweight than the ciphertext-ciphertext multiplication, the quadratic complexity makes handling larger inputs quite inefficient. In this work, first we improve the prior work and also propose a new approach that exploits the packing method to handle the larger input domain size instead of enabling the SIMD operation, thus making it possible to work with the larger input domain size, e.g., $\mathbb{Z}_{2^{15}}$ in a reasonably efficient way. In addition, we show how to slightly extend the input domain size to $\mathbb{Z}_{2^{16}}$ with a relatively moderate overhead. Further we show another approach to handling the larger input domain size by using two ciphertexts to encrypt one integer plaintext and applying our techniques for uni/bivariate function evaluation. We implement the prior work of Okada et al., our improved scheme of Okada et al., and our new scheme in PALISADE with the input domain size $\mathbb{Z}_{2^{15}}$, and confirm that the estimated run-times of the prior work and our improved scheme of the prior work are still about 117 days and 59 days respectively while our new scheme can be computed in 307 seconds.

This article presents the application of homomorphic authenticators, replication encodings to be precise, to multigroup fully homomorphic encryption schemes. Following the works of Gennaro and Wichs on homomorphic authenticators in combination with the work of multigroup schemes by Kwak et al. we present a verifiable solution for a fully homomorphic primitive that includes the multikey, multiparty and single user cases. Furthermore, we propose a line of research for the future with constrained-resource scenarios.

This work investigates zero-knowledge protocols in subverted RSA groups where the prover can choose the modulus and where the verifier does not know the group order. We introduce a novel technique for extracting the witness from a general homomorphism over a group of unknown order that does not require parallel repetitions. We present a NIZK range proof for general homomorphisms such as Paillier encryptions in the designated verifier model that works under a subverted setup. The key ingredient of our proof is a constant sized NIZK proof of knowledge for a plaintext. Security is proven in the ROM assuming an IND-CPA additively homomorphic encryption scheme. The verifier's public key is reusable, can be maliciously generated and is linear in the number of proofs to be verified.

Long-term security, a variant of Universally Composable (UC) security introduced by Müller-Quade and Unruh (JoC ’10), allows to analyze the security of protocols in a setting where all hardness assumptions no longer hold after the protocol execution has finished. Such a strict notion is highly desirable when properties such as input privacy need to be guaranteed for a long time, e.g. zero-knowledge proofs for secure electronic voting. Strong impossibility results rule out so-called long-term-revealing setups, e.g. a common reference string (CRS), to achieve long-term security, with known constructions for long-term security requiring hardware assumptions, e.g. signature cards. We circumvent these impossibility results by making use of new techniques, allowing rewinding-based simulation in a way that universal composability is possible. The new techniques allow us to construct a long-term-secure composable commitment scheme in the CRS-hybrid model, which is provably impossible in the notion of Müller-Quade and Unruh. We base our construction on a statistically hiding commitment scheme in the CRS-hybrid model with CCA-like properties. To provide a CCA oracle, we cannot rely on superpolynomial extraction techniques, as statistically hiding commitments do not define a unique value. Thus, we extract the value committed to via rewinding. However, even a CCA “rewinding oracle” without additional properties may be useless, as extracting a malicious committer could require to rewind other protocols the committer participates in. If this is e.g. a reduction, this clearly is forbidden. Fortunately, we can establish the well-known and important property of k-robust extractability, which guarantees that extraction is possible without rewinding k-round protocols the malicious committer participates in. While establishing this property for statistically binding commitment schemes is already non-trivial, it is even more complicated for statistically hiding ones. We then incorporate rewinding-based commitment extraction into the UC framework via a helper in analogy to Canetti, Lin and Pass (FOCS 2010), allowing both adversary and environment to extract statistically hiding commitments. Despite the rewinding, our variant of long-term security is universally composable. Our new framework provides the first setting in which a commitment scheme that is both statistically hiding and composable can be constructed from standard polynomial-time hardness assumptions and a CRS only. Unfortunately, we can prove that our setting does not admit long-term-secure oblivious transfer (and thus general two-party computations). Still, our long-term-secure commitment scheme suffices for natural applications, such as long-term secure and composable (commit-and-prove) zero-knowledge arguments of knowledge.

Current solutions to quantum vulnerabilities of widely used cryptographic schemes involve migrating users to post-quantum schemes before quantum attacks become feasible. This work deals with protecting quantum procrastinators: users that failed to migrate to post-quantum cryptography in time. To address this problem in the context of digital signatures, we introduce a technique called signature lifting, that allows us to lift a deployed pre-quantum signature scheme satisfying a certain property to a post-quantum signature scheme that uses the same keys. Informally, the said property is that a post-quantum one-way function is used "somewhere along the way" to derive the public-key from the secret-key. Our constructions of signature lifting relies heavily on the post-quantum digital signature scheme Picnic (Chase et al., CCS'17). Our main case-study is cryptocurrencies, where this property holds in two scenarios: when the public-key is generated via a key-derivation function or when the public-key hash is posted instead of the public-key itself. We propose a modification, based on signature lifting, that can be applied in many cryptocurrencies for securely spending pre-quantum coins in presence of quantum adversaries. Our construction improves upon existing constructions in two major ways: it is not limited to pre-quantum coins whose ECDSA public-key has been kept secret (and in particular, it handles all coins that are stored in addresses generated by HD wallets), and it does not require access to post-quantum coins or using side payments to pay for posting the transaction.

We study authenticated encryption (AE) modes dedicated to very short messages, which are crucial for Internet-of-things applications. Since the existing general-purpose AE modes need at least three block cipher calls for non-empty messages, we explore the design space for AE modes that use at most two calls. We proposed a family of AE modes, dubbed Manx, that work when the total input length is less than $2n$ bits, using an $n$-bit block cipher. Notably, the second construction of Manx can encrypt almost n-bit plaintext and saves one or two block cipher calls from the standard modes, such as GCM or OCB, keeping the comparable provable security. We also present benchmarks on popular 8/32-bit microprocessors using AES. Our results show the clear advantage of Manx over the previous modes for such short messages.

Digital signatures ensure legitimate access through identity authentication. It is also used to build blocks in blockchains and to authenticate transactions. The Courtois-Finiasz-Sendrier (CFS) digital signature is a well-known code-based digital signature scheme based on the Niederreiter cryptosystem. The CFS signature, however, is not widely used due to the long processing time required by its signing algorithm. Most code-based digital signature schemes are based on Niederreiter. The present paper proposes a new code-based digital signature based on the McEliece cryptosystem. The proposed McEliece code-based scheme also gives less complexity and a higher success rate. The scheme provides an efficient code-based algorithm to sign a document in a shorter processing time. The scheme is also secure against public key structural attacks. Key generation, signing, and verification algorithms are presented. The key generation algorithm constructs three-tuple public keys using a dual inverse matrix. The proposed signing scheme is the first code-based digital signature based on McEliece with the lower processing time required to construct a valid digital signature. The proposed signing algorithm also constructs smaller signatures. In addition, the verification algorithm checks the integrity value to avoid any forgery before final verification.

Machine learning (ML) has seen a strong rise in popularity in recent years and has become an essential tool for research and industrial applications. Given the large amount of high quality data needed and the often sensitive nature of ML data, privacy-preserving collaborative ML is of increasing importance. In this paper, we introduce new actively secure multiparty computation (MPC) protocols which are specially optimized for privacy-preserving machine learning applications. We concentrate on the optimization of (tensor) convolutions which belong to the most commonly used components in ML architectures, especially in convolutional neural networks but also in recurrent neural networks or transformers, and therefore have a major impact on the overall performance. Our approach is based on a generalized form of structured randomness that speeds up convolutions in a fast online phase. The structured randomness is generated with homomorphic encryption using adapted and newly constructed packing methods for convolutions, which might be of independent interest. Overall our protocols extend the state-of-the-art Overdrive family of protocols (Keller et al., EUROCRYPT 2018). We implemented our protocols on-top of MP-SPDZ (Keller, CCS 2020) resulting in a full-featured implementation with support for faster convolutions. Our evaluation shows that our protocols outperform state-of-the-art actively secure MPC protocols on ML tasks like evaluating ResNet50 by a factor of 3 or more. Benchmarks for depthwise convolutions show order-of-magnitude speed-ups compared to existing approaches.

The security of cryptographic primitives is an important issue. The Shor algorithm illustrates how quantum attacks threaten the security of these widely used primitives. Code-based cryptography is one of several approaches resistant to quantum attacks. To date, no attack has been able to break a code-based cryptosystem in polynomial time. Despite this level of security, these cryptosystems have not been considered for practical applications such as e-commerce, medical and industrial IoT, finance, blockchain, mobile services, and online banking. The main reason is the large public and private key sizes. This paper presents a new code-based cryptosystem based on inverse parity check matrices. The dual matrix provides both a parity check matrix transpose and a parity check matrix inverse. These are employed in the key generation, encryption, and decryption algorithms. The proposed scheme provides public and private key sizes smaller than the McEliece cryptosystem and has a higher level of security.

Fully homomorphic encryption FHE has been one of the most promising cryptographic tools for secure two-party computation and secure outsourcing computation in recent years. However, the complex bootstrapping procedure in FHE schemes is the main bottleneck of it practical usage, and the TFHE scheme is the state-of-the-art for efficient bootstrapping. To further improve the efficiency of bootstrapping in TFHE, the number of fast Fourier transforms (FFT) should be reduced since bootstrapping in TFHE is mainly composed of vast FFTs. In this paper, we focus on a novel method of decomposing-in-Fourier (DIF) to reduce the number of FFTs in bootstrapping of TFHE, from $2(\ell+1)n$ to $4n$. As a result, our method would reduce the number of FFTs required by each external product in bootstrapping to a constant number rather than varying with decomposing parameters, which leads to a scale-invariant bootstrapping structure.

IACR is soliciting for affiliated events to be held in conjunction with Crypto 2023 Saturday, August 19th, and/or Sunday, August 20th, 2023.

The call for proposals is now out at: https://crypto.iacr.org/2023/affiliated.php