International Association
for Cryptologic Research

Isogeny-based cryptography is one of the candidates for post-quantum cryptography. Recently, many isogeny-based cryptosystems using isogenies between Kummer surfaces were proposed. Most of those cryptosystems use $(2,2)$-isogenies. However, to enhance the possibility of cryptosystems, higher degree isogenies, say $(\ell,\ell)$-isogenies for an odd $\ell$, is also crucial. For an odd $\ell$, the Lubicz-Robert gave a formula to compute $(\ell)^g$-isogenies in general dimension $g$. In this paper, we propose explicit and efficient algorithms to compute $(\ell,\ell)$-isogenies between Kummer surfaces, based on the Lubicz-Robert formula.In particular, we propose two algorithms for computing the codomain of the isogeny and two algorithms for evaluating the image of a point under the isogeny. Then, we count the number of arithmetic operations required for each of our proposed algorithms, and determine the most efficient algorithm in terms of the number of arithmetic operations from each of two types of algorithms for each $\ell$. As an application, using the most efficient one, we implemented the SIDH attack on B-SIDH in SageMath.In setting that originally claimed 128-bit security, our implementation was able to recover that secret key in about 11 hours.

To date, the strongest notions of security achievable for two-round publicly-verifiable cryptographic proofs for $\mathsf{NP}$ are witness indistinguishability (Dwork-Naor 2000, Groth-Ostrovsky-Sahai 2006), witness hiding (Bitansky-Khurana-Paneth 2019, Kuykendall-Zhandry 2020), and super-polynomial simulation (Pass 2003, Khurana-Sahai 2017). On the other hand, zero-knowledge and even weak zero-knowledge (Dwork-Naor-Reingold-Stockmeyer 1999) are impossible in the two-round publicly-verifiable setting (Goldreich-Oren 1994). This leaves an enormous gap in our theoretical understanding of known achievable security and the impossibility results for two-round publicly-verifiable cryptographic proofs for $\mathsf{NP}$.

Towards filling this gap, we propose a new and natural notion of security, called witness semantic security, that captures the natural and strong notion that an adversary should not be able to learn any partial information about the prover's witness beyond what it could learn given only the statement $x$. Not only does our notion of witness semantic security subsume both witness indistinguishability and witness hiding, but it also has an easily appreciable interpretation.

Moreover, we show that assuming the subexponential hardness of LWE, there exists a two-round public-coin publicly-verifiable witness semantic secure argument. To our knowledge, this is the strongest form of security known for this setting.

As a key application of our work, we show that non-interactive zero-knowledge (NIZK) arguments in the common reference string (CRS) model can additionally maintain witness semantic security even when the CRS is maliciously generated. Our work gives the first construction from (subexponential) standard assumptions that achieves a notion stronger than witness-indistinguishability against a malicious CRS authority.

In order to achieve our results, we give the first construction of a ZAP from subexponential LWE that is adaptively sound. Additionally, we propose a notion of simulation using non-uniform advice about a malicious CRS, which we also believe will be of independent interest.

SNOVA is one of the submissions in the NIST Round 1 Additional Signature of the Post-Quantum Signature Competition. SNOVA is a UOV variant that uses the noncommutative-ring technique to educe the size of the public key. SNOVA's public key size and signature size are well-balanced and have good performance. Recently, Beullens proposed a forgery attack against SNOVA, pointing out that the parameters of SNOVA can be attacked. Beullens also argued that with some slight adjustments his attacks can be prevented. In this note, we explain Beullens' forgery attack and show that the attack can be invalid by two different approaches. Finally, we show that these two approaches do not increase the sizes of the public keys or signatures and the current parameters satisfy the security requirement of NIST.

An important consideration with the growth of the DeFi ecosystem is the protection of clients who submit transactions to the system. As it currently stands, the public visibility of these transactions in the memory pool (mempool) makes them susceptible to market manipulations such as frontrunning and backrunning. More broadly, for various reasons—ranging from avoiding market manipulation to including time-sensitive information in their transactions—clients may want the contents of their transactions to remain private until they are executed, i.e. they have *pending transaction privacy*. Therefore, *mempool privacy* is becoming an increasingly important feature as DeFi applications continue to spread.

We construct the first *practical* mempool privacy scheme that uses a *one-time* DKG setup for $n$ decryption servers. Our scheme ensures the strong privacy requirement by not only hiding the transactions until they are decrypted but also guaranteeing privacy for transactions that were not selected in the epoch (*pending transaction privacy*). For each epoch (or block), clients can encrypt their transactions so that, once $B$ (encrypted) transactions are selected for the epoch, they can be decrypted by each decryption server while communicating only $O(1)$ information.

Our result improves upon the best-known prior works, which either: (i) require an expensive initial setup involving a (special purpose) multiparty computation protocol executed by the $n$ decryption servers, along with an additional *per-epoch* setup; (ii) require each decryption server to communicate $O(B)$ information; or (iii) do not guarantee pending transaction privacy.

We implement our scheme and find that transactions can be encrypted in approximately 8.5 ms, independent of committee size, and the communication required to decrypt an entire batch of transactions is 48 bytes per party, independent of the number of transactions. If deployed on Ethereum, which processes close to 500 transactions per block, it takes close to 3.2 s for each committee member to compute a partial decryption and 3.0 s to decrypt all transactions for a block in single-threaded mode. Compared to prior work, which had an expensive setup phase per epoch, we incur $<2\times$ overhead in the worst case. On some metrics such as partial decryptions size, we actually fare better.

With the standardization of NIST post-quantum cryptographic (PQC) schemes, optimizing these PQC schemes across various platforms presents significant research value. While most existing software implementation efforts have concentrated on ARM platforms, research on PQC implementations utilizing various RISC-V instruction set architectures (ISAs) remains limited. In light of this gap, this paper proposes comprehensive and efficient optimizations of Keccak, Kyber, and Dilithium on RV{32,64}IM{B}{V}. We thoroughly optimize these implementations for dual-issue CPUs, believing that our work on various RISC-V ISAs will provide valuable insights for future PQC deployments.

Specifically, for Keccak, we revisit a range of optimization techniques, including bit interleaving, lane complementing, in-place processing, and hybrid vector/scalar implementations. We construct an optimal combination of methods aimed at achieving peak performance on dual-issue CPUs for various RISC-V ISAs. For the NTT implementations of Kyber and Dilithium, we deliver optimized solutions based on Plantard and Montgomery arithmetic for diverse RISC-V ISAs, incorporating extensive dual-issue enhancements. Additionally, we improve the signed Plantard multiplication algorithm proposed by Akoi et al. Ultimately, our testing demonstrates that our implementations of Keccak and NTT across various ISAs achieve new performance records. More importantly, they significantly enrich the PQC software ecosystem for RISC-V.

We present a new approach for constructing non-interactive zero-knowledge (NIZK) proof systems from vector trapdoor hashing (VTDH) -- a generalization of trapdoor hashing [Döttling et al., Crypto'19]. Unlike prior applications of trapdoor hash to NIZKs, we use VTDH to realize the hidden bits model [Feige-Lapidot-Shamir, FOCS'90] leading to black-box constructions of NIZKs. This approach gives us the following new results: - A statistically-sound NIZK proof system based on the hardness of decisional Diffie-Hellman (DDH) and learning parity with noise (LPN) over finite fields with inverse polynomial noise rate. This gives the first statistically sound NIZK proof system that is not based on either LWE, or bilinear maps, or factoring. - A dual-mode NIZK satisfying statistical zero-knowledge in the common random string mode and statistical soundness in the common reference string mode assuming the hardness of learning with errors (LWE) with polynomial modulus-to-noise ratio. This gives the first black-box construction of such a dual-mode NIZK under LWE. This improves the recent work of Waters (STOC'24) which relied on LWE with super-polynomial modulus-to-noise ratio and required a setup phase with private coins.

The above constructions are black-box and satisfy single-theorem zero-knowledge property. Building on the works of Feige et al.(FOCS'90) and Fishclin and Rohrback (PKC'21), we upgrade these constructions (under the same assumptions) to satisfy multi-theorem zero-knowledge property at the expense of making non-black-box use of cryptography.

Homomorphic encryption has long been used to build voting schemes. Additively homomorphic encryption only allows simple count- ing functions. Lattice-based fully (or somewhat) homomorphic encryp- tion allows more general counting functions, but the required parameters quickly become impractical if used naively. It is safe to leak information during the counting function evaluation, as long as the information could be derived from the public result. To exploit this observation, we de- sign a flexible framework for using somewhat homomorphic encryption for voting that incorporates random input and allows controlled leakage of information. We instantiate the framework using novel circuits with low but significant multiplicative depth exploiting the fact that, in the context of voting, leakage of certain information during homomorphic evaluation can be permitted. We also instantiate the framework with a circuit that uses random input to shuffle without the use of mixnets.

We enhance the provable soundness of FRI, an interactive oracle proof of proximity (IOPP) for Reed-Solomon codes introduced by Ben-Sasson et al. in ICALP 2018. More precisely, we prove the soundness error of FRI is less than $\max\left\{O\left(\frac{1}{\eta}\cdot \frac{n}{|\mathbb{F}_q|}\right), (1-\delta)^{t}\right\}$, where $\delta\le 1-\sqrt{\rho}-\eta$ is within the Johnson bound and $\mathbb{F}_q$ is a finite field with characteristic greater than $2$. Previously, the best-known provable soundness error for FRI was $\max\left\{O\left(\frac{\rho^2}{\eta^7}\cdot \frac{n^2}{|\mathbb{F}_q|}\right), (1-\delta)^{t}\right\}$, as established by Ben-Sasson et al. in FOCS 2020.

We prove the number of \emph{bad} folding points in FRI is linear in the length $n$ of codeword when it is $\delta$-far from the Reed-Solomon code. This implies the linear proximity gaps for Reed-Solomon codes and improves the provable soundness of batched FRI. Our results indicate that the FRI protocol can be implemented over a smaller field, thereby enhancing its efficiency. Furthermore, for a fixed finite field $\mathbb{F}_q$, we prove that FRI can achieve improved security.

It is well known that estimating a sharp lower bound on the second-order nonlinearity of a general class of cubic Booleanfunction is a difficult task. In this paper for a given integer $n \geq 4$, some values of $s$ and $t$ are determined for which cubic monomial Boolean functions of the form $h_{\mu}(x)=Tr( \mu x^{2^s+2^t+1})$ $(n>s>t \geq 1)$ possess good lower bounds on their second-order nonlinearity. The obtained functions are worth considering for securing symmetric cryptosystems against various quadratic approximation attacks and fast algebraic attacks.

Cryptographic group actions have gained significant attention in recent years for their application on post-quantum Sigma protocols and digital signatures. In NIST's recent additional call for post-quantum signatures, three relevant proposals are based on group actions: LESS, MEDS, and ALTEQ. This work explores signature optimisations leveraging a group's factorisation. We show that if the group admits a factorisation as a semidirect product of subgroups, the group action can be restricted on a quotient space under the equivalence relation induced by the factorisation. If the relation is efficiently decidable, we show that it is possible to construct an equivalent Sigma protocol for a relationship that depends only on one of the subgroups. Moreover, if a special class of representative of the quotient space is efficiently computable via a canonical form, the restricted action is effective and does not incur in security loss. Finally, we apply these techniques to the group actions underlying LESS and MEDS, showing how they will affect the length of signatures and public keys.

Lookup arguments enable a prover to convince a verifier that a committed vector of lookup elements $\vec{f} \in \mathbb{F}^m$ is contained within a predefined table $T \in \mathbb{F}^N$. These arguments are particularly beneficial for enhancing the performance of SNARKs in handling non-arithmetic operations, such as batched range checks or bitwise operations. While existing works have achieved efficient and succinct lookup arguments, challenges remain, particularly when dealing with large vectors of lookup elements in privacy-sensitive applications.

In this paper, we introduce $\duplex$, a scalable zero-knowledge lookup argument scheme that offers significant improvements over previous approaches. Notably, we present the first lookup argument designed to operate over the RSA group. Our core technique allows for the transformation of elements into prime numbers to ensure compatibility with the RSA group, all without imposing substantial computational costs on the prover. Given $m$ lookup elements, $\duplex$ achieves an asymptotic proving time of $O(m \log m)$, with constant-sized proofs, constant-time verification, and a public parameter size independent of the table size $N$. Additionally, $\duplex$ ensures the privacy of lookup elements and is robust against dynamic table updates, making it highly suitable for scalable verifiable computation in real-world applications.

We implemented and empirically evaluated $\duplex$, comparing it with the state-of-the-art zero-knowledge lookup argument Caulk [CCS'22]. Our experimental results demonstrate that $\duplex$ significantly outperforms Caulk in proving time for both single and batched lookup arguments, while maintaining practical proof size and verification time.

In this paper, we explore a new type of key collisions called target-plaintext key collisions of AES, which emerge as an open problem in the key committing security and are directly converted into single-block collision attacks on Davies-Meyer (DM) hashing mode. For this key collision, a ciphertext collision is uniquely observed when a specific plaintext is encrypted under two distinct keys. We introduce an efficient automatic search tool designed to find target-plaintext key collisions. This tool exploits bit-wise behaviors of differential characteristics and dependencies among operations and internal variables of both data processing and key scheduling parts. This allows us to hierarchically perform rebound-type attacks to identify key collisions. As a result, we demonstrate single-block collision attacks on 2/5/6-round AES-128/192/256-DM and semi-free-start collision attacks on 5/7/9-round AES-128/192/256-DM, respectively. To validate our attacks, we provide an example of fixed-target-plaintext key collision/semi-free-start collisions on 9-round AES-256-DM. Furthermore, by exploiting a specific class of free-start collisions with our tool, we present two-block collision attacks on 3/9-round AES-128/256-DM, respectively.

We introduce new lattice-based techniques for building ABE for circuits with unbounded attribute length based on the LWE assumption, improving upon the previous constructions of Brakerski and Vaikuntanathan (CRYPTO 16) and Goyal, Koppula, and Waters (TCC 16). Our main result is a simple and more efficient unbounded ABE scheme for circuits where only the circuit depth is fixed at set-up; this is the first unbounded ABE scheme for circuits that rely only on black-box access to cryptographic and lattice algorithms. The scheme achieves semi-adaptive security against unbounded collusions under the LWE assumption. The encryption time and ciphertext size are roughly $3 \times$ larger than the prior bounded ABE of Boneh et al. (EUROCRYPT 2014), substantially improving upon the encryption times in prior works. As a secondary contribution, we present an analogous result for unbounded inner product predicate encryption that satisfies weak attribute-hiding.

We investigate the notion of bit-security for decisional cryptographic properties, as originally proposed in (Micciancio & Walter, Eurocrypt 2018), and its main variants and extensions, with the goal clarifying the relation between different definitions, and facilitating their use. Specific contributions of this paper include: (1) identifying the optimal adversaries achieving the highest possible MW advantage, showing that they are deterministic and have a very simple threshold structure; (2) giving a simple proof that a competing definition proposed by (Watanabe & Yasunaga, Asiacrypt 2021) is actually equivalent to the original MW definition; and (3) developing tools for the use of the extended notion of computational-statistical bit-security introduced in (Li, Micciancio, Schultz & Sorrell, Crypto 2022), showing that it fully supports common cryptographic proof techniques like hybrid arguments and probability replacement theorems. On the technical side, our results are obtained by introducing a new notion of "fuzzy" distinguisher (which we prove equivalent to the "aborting" distinguishers of Micciancio and Walter), and a tight connection between the MW advantage and the Le Cam metric, a standard quantity used in statistics.

Multi-key fully homomorphic encryption (MKFHE), a generalization of fully homomorphic encryption (FHE), enables a computation over encrypted data under multiple keys. The first MKFHE schemes were based on the NTRU primitive, however these early NTRU based FHE schemes were found to be insecure due to the problem of over-stretched parameters. Recently, in the case of standard (non-multi key) FHE a secure version, called FINAL, of NTRU has been found. In this work we extend FINAL to an MKFHE scheme, this allows us to benefit from some of the performance advantages provided by NTRU based primitives. Thus, our scheme provides competitive performance against current state-of-the-art multi-key TFHE, in particular reducing the computational complexity from quadratic to linear in the number of keys.

In August 2021, Liu et al. (IEEE TIFS'21) proposed a privacy-enhanced framework named PEFL to efficiently detect poisoning behaviours in Federated Learning (FL) using homomorphic encryption. In this article, we show that PEFL does not preserve privacy. In particular, we illustrate that PEFL reveals the entire gradient vector of all users in clear to one of the participating entities, thereby violating privacy. Furthermore, we clearly show that an immediate fix for this issue is still insufficient to achieve privacy by pointing out multiple flaws in the proposed system.

A mix network, or mixnet, is a cryptographic tool for anonymous routing, taking messages from multiple (identifiable) senders and delivering them in a randomly permuted order. Traditional mixnets employ encryption and proofs of correct shuffle to cut the link between each sender and their input.

Hébant et al. (PKC '20) introduced a novel approach to scalable mixnets based on linearly homomorphic signatures. Unfortunately, their security model is too weak to support voting applications. Building upon their work, we leverage recent advances in equivalence class signatures, replacing linearly homomorphic signatures to obtain more efficient mixnets with security in a more robust model. More concretely, we introduce the notion of mercurial signatures on randomizable ciphertexts along with an efficient construction, which we use to build a scalable mixnet protocol suitable for voting. We compare our approach to other (scalable) mixnet approaches, implement our protocols, and provide concrete performance benchmarks. Our findings show our mixnet significantly outperforms existing alternatives in efficiency and scalability. Verifying the mixing process for 50k ciphertexts takes 135 seconds on a commodity laptop (without parallelization) when employing ten mixers.

The SPDZ protocol family is a popular choice for secure multi-party computation (MPC) in a dishonest majority setting with active adversaries. Over the past decade, a series of studies have focused on improving its offline phase, where special additive shares, called authenticated triples, are generated. However, to accommodate recent demands for matrix operations in secure machine learning and big integer arithmetic in distributed RSA key generation, updates to the offline phase are required.

In this work, we propose a new protocol for the SPDZ offline phase, TopGear 2.0, which improves upon the previous state-of-the-art construction, TopGear (Baum et al., SAC'19), and its variant for matrix triples (Chen et al., Asiacrypt'20). Our protocol aims to achieve a speedup in matrix triple generation and support for larger prime fields, up to 4096 bits in size. To achieve this, we employ a variant of the BFV scheme and a homomorphic matrix multiplication algorithm optimized for our purpose.

As a result, our protocol achieves about 3.6x speedup for generating scalar triples in a 1024-bit prime field and about 34x speedup for generating 128x128 matrix triples. In addition, we reduce the size of evaluation keys from 27.4 GB to 0.22 GB and the communication cost for MAC key generation from 816 MB to 16.6 MB.

In the rapidly evolving Web3 ecosystem, transparent auditing has emerged as a critical component for both applications and users. However, there is a significant gap in understanding how users perceive this new form of auditing and its implications for Web3 security. Utilizing a mixed-methods approach that incorporates a case study, user interviews, and social media data analysis, our study leverages a risk perception model to comprehensively explore Web3 users' perceptions regarding information accessibility, the role of auditing, and its influence on user behavior. Based on these extensive findings, we discuss how this open form of auditing is shaping the security of the Web3 ecosystem, identifying current challenges, and providing design implications.

Although one-way functions are well-established as the minimal primitive for classical cryptography, a minimal primitive for quantum cryptography is still unclear. Universal extrapolation, first considered by Impagliazzo and Levin (1990), is hard if and only if one-way functions exist. Towards better understanding minimal assumptions for quantum cryptography, we study the quantum analogues of the universal extrapolation task. Specifically, we put forth the classical$\rightarrow$quantum extrapolation task, where we ask to extrapolate the rest of a bipartite pure state given the first register measured in the computational basis. We then use it as a key component to establish new connections in quantum cryptography: (a) quantum commitments exist if classical$\rightarrow$quantum extrapolation is hard; and (b) classical$\rightarrow$quantum extrapolation is hard if any of the following cryptographic primitives exists: quantum public-key cryptography (such as quantum money and signatures) with a classical public key or 2-message quantum key distribution protocols.

For future work, we further generalize the extrapolation task and propose a fully quantum analogue. We observe that it is hard if quantum commitments exist, and it is easy for quantum polynomial space.