International Association
for Cryptologic Research

A significant effort in designing and engineering post-quantum cryptosystems is currently ongoing, also as a result of the National Institute of Standards and Technology (NIST) Post-quantum Cryptography (PQC) standardization process that started in 2016 and recently completed selecting two Key Encapsulation Mechanisms (KEMs), CRYSTALS-Kyber and HQC, and three digital signatures CRYSTALS-Dilithium, Falcon, and SPHINCS+ for standardization. In 2022, NIST launched another standardization effort for additional post-quantum digital signatures, preferably not based on the security assumptions of structured lattices, and with performance better than or equal to that of already standardized schemes (e.g., SPHINCS+ ). This initiative has narrowed down the initial 40 candidates to 14 in October 2024, eliciting public scrutiny of their algorithms and technical evaluation of their performance figures. Among the schemes admitted to the second round of evaluation, the code-based CROSS signature scheme was praised for its speed and the noticeably smaller signature sizes over the standardized version of SPHINCS+ . In this work, we present the first RTL hardware design of CROSS tailored for FPGA devices, delineating efficient implementation strategies for the critical components of the cryptographic scheme. Depending on the chosen security level, our design generates a key pair in 9 to 152 µs, signs a message in 404 µs to 5.89 ms, and verifies a signature in 322 µs to 4.38 ms on the NIST reference FPGA, a Xilinx Artix-7 device, proving competitive when compared with other candidates in the on-ramp standardization effort, namely LESS, MEDS, MAYO, Raccoon and SDitH, and comparable to current standard-selected ML-DSA, FN-DSA, and SLH-DSA in terms of efficiency.

Authenticated dictionaries (ADs) enable secure lookups to a dictionary hosted by an untrusted server and are a key component of various real-world applications, including transparency systems and cryptocurrencies. Despite significant overlap in techniques for building ADs and related primitives, such as memory checkers and accumulators (i.e., authenticated sets), these relationships have yet to be formalized.

In this work, we give a rigorous treatment of ADs and prove their precise connection to the latter two cornerstone primitives. We start by laying out the minimal algorithms and security properties needed in practice and introduce a new security notion for ADs called write-committing, which requires update proofs to guarantee an exact count of changes.

We prove that any AD built from a black-box authenticated set (AS) makes at least $\Omega(\log n)$ AS calls per lookup and obeys a trade-off between lookups and updates. With optimal lookups, such a scheme requires at least $\Omega(\log n/\log\log n)$ AS calls per update. We also resolve the open question of constructing a secure AD from only black-box access to an AS and present two schemes adhering to the trade-off: one with optimal lookup overhead and the other with higher lookup complexity, but which only requires two AS calls for an update.

Finally, we make strides towards unifying memory checkers and ADs. To this end, we present two constructions for memory checkers with black-box access to an AD: one that incurs constant overhead (but needs write-committing) and a second that only requires the AD to be lookup-secure but incurs logarithmic overhead. We then give a simple AD construction using a memory checker as a black-box, with $\mathcal{O}(1)$ overhead.

Our results demonstrate the inherent limitations of ADs built from accumulators but lay the foundation for extending existing results on memory checkers and other primitives, such as vector commitments, to ADs.

Let $p$ be a prime and consider a committed vector $\vec{v} = (v_1, \ldots, v_m) \in \mathbb{F}_p^m$. We develop new techniques for succinctly proving in zero-knowledge that all the elements of $\vec{v}$ are in the range $\{0,1,\ldots,n\}$ for some $n

A holy grail in blockchain infrastructure is a trustless bridge between Bitcoin and its second layers or other chains. We make progress toward this vision by introducing the first light-client based Bitcoin bridge. At the heart of its design lies BitVM2-core, a novel paradigm that enables arbitrary program execution on Bitcoin, combining Turing-complete expressiveness with the security of Bitcoin consensus. BitVM2-bridge advances prior approaches by reducing the trust assumption from an honest majority (t-of-n) to existential honesty (1-of-n) during setup. Liveness is guaranteed with only one rational operator, and any user can act as a challenger, enabling permissionless verification. A production-level implementation of BitVM2 has been developed and a full challenge verification has been executed on the Bitcoin mainnet.

Based on a sharpening of Carmichael’s theorem and Euler’s theorem we generalize RSA and CRT-RSA to arbitrary integer moduli $n > 1$, while restricting messages to integers $m$ which are regular modulo $n$, meaning that they have a John-von-Neumann pseudoinverse modulo $n$. We prove the correctness and completeness of our encryption and decryption method for this class of messages, and show that the restriction to regular integers is negligible, since under reasonable assumptions almost all integers are regular modulo $n$.

Randomness extractors are algorithms that distill weak random sources into near-perfect random numbers. Two-source extractors enable this distillation process by combining two independent weak random sources. Raz’s extractor (STOC '05) was the first to achieve this in a setting where one source has linear min-entropy (i.e., proportional to its length), while the other has only logarithmic min-entropy in its length. However, Raz's original construction is impractical due to a polynomial computation time of at least degree 4. Our work solves this problem by presenting an improved version of Raz's extractor with quasi-linear computation time, as well as a new analytic theorem with reduced entropy requirements. We provide comprehensive analytical and numerical comparisons of our construction with others in the literature, and we derive strong and quantum-proof versions of our efficient Raz extractor. Additionally, we offer an easy-to-use, open-source code implementation of the extractor and a numerical parameter calculation module.

We propose a dimension-reducing transformation on Group Ring Learning with Errors (GRLWE) samples. We exhibit an efficiently computable isomorphism which takes samples defined over the group rings used in the construction of GRLWE to twice as many samples defined over matrix rings, in half the dimension. This is done by composing two maps: the first map is a transformation showing that the group rings used are orders in central simple algebras, and the second map takes the obtained central simple algebra to a matrix ring. When combined with lattice reduction on the resulting matrix samples, this gives an attack on the GRLWE problem. We extend this attack to other groups proposed for cryptographic use by the creators of GRLWE, and display some numerical results quantifying the effects of the transformation, using the `Lattice Estimator'. We then give a family of groups from which GRLWE-style group rings can be constructed which are immune to our attack, namely the generalized quaternion groups. Finally, we discuss the merits and vulnerabilities of a number of different forms of structured LWE.

We present several new algorithms to evaluate modular polynomials of level $\ell$ modulo a prime $p$ on an input $j$. More precisely, we introduce two new generic algorithms, sharing the following similarities: they are based on a CRT approach; they make use of supersingular curves and the Deuring correspondence; and, their memory requirements are optimal.

The first algorithm combines the ideas behind a hybrid algorithm of Sutherland in 2013 with a recent algorithm to compute modular polynomials using supersingular curves introduced in 2023 by Leroux. The complexity (holding around several plausible heuristic assumptions) of the resulting algorithm matches the $O(\ell^3 \log^{3} \ell + \ell \log p)$ time complexity of the best known algorithm by Sutherland, but has an optimal memory requirement. Our second algorithm is based on a sub-algorithm that can evaluate modular polynomials efficiently on supersingular $j$-invariants defined over $\mathbb{F}_p$, and achieves heuristic complexity quadratic in both $\ell$ and $\log j$, and linear in $\log p$. In particular, it is the first generic algorithm with optimal memory requirement to obtain a quadratic complexity in~$\ell$. Additionally, we show how to adapt our method to the computation of other types of modular polynomials such as the one stemming from Weber's function. Finally, we provide an optimised implementation of the two algorithms detailed in this paper, though we emphasise that various modules in our codebase may find applications outside their use in this paper.

In many areas of cybersecurity, we require access to Personally Identifiable Information (PII), such as names, postal addresses and email addresses. Unfortunately, this can lead to data breaches, especially in relation to data compliance regulations such as GDPR. An Internet Protocol (IP) address is an identifier that is assigned to a networked device to enable it to communicate over networks that use IP. Thus, in applications which are privacy-aware, we may aim to hide the IP address while aiming to determine if the address comes from a blacklist. One solution to this is to use homomorphic encryption to match an encrypted version of an IP address to a blacklisted network list. This matching allows us to encrypt the IP address and match it to an encrypted version of a blacklist. In this paper, we use the OpenFHE library \cite{OpenFHE} to encrypt network addresses with the BFV homomorphic encryption scheme. In order to assess the performance overhead of BFV, we implement a matching method using the OpenFHE library and compare it against partial homomorphic schemes, including Paillier, Damgard-Jurik, Okamoto-Uchiyama, Naccache-Stern and Benaloh. The main findings are that the BFV method compares favourably against the partial homomorphic methods in most cases.

Program verification ensures software correctness through formal methods but incurs substantial computational overhead. It typically encodes program execution into formulas that are verified using a SAT solver and its extensions. However, this process exposes sensitive program details and requires redundant computations when multiple parties need to verify correctness. To overcome these limitations, zero-knowledge proofs (ZKPs) generate compact, reusable proofs with fast verification times, while provably hiding the program’s internal logic. We propose a two-phase zero-knowledge protocol that hides program implementation details throughout verification. Phase I uses a zero-knowledge virtual machine (zkVM) to encode programs into SAT formulas without revealing their semantics. Phase II employs the encoding of resolution proofs for UNSAT instances and circuits for satisfying assignment verification for SAT instances through PLONKish circuits. Evaluation on the Boolector benchmark demonstrates that our method achieves verification time that is efficient and is independent of clause width for UNSAT instances and formula size for SAT instances. The resulting ZKPs enable efficient verification of program properties while providing strong end-to-end privacy guarantees.

We introduce a novel technique for verifying Schnorr signatures using fast endomorphisms. Traditionally, fast endomorphisms over prime field curves are used to decompose a scalar into two scalars of half of the size. This work shows that the context of the verification of signatures allows for the decomposition into three scalars of a third of the size. We apply our technique to three scenarios: verification of a single Schnorr signature, batch verification, and verification of BLS signatures within the Blind Diffie-Hellman key exchange protocol. Our experiments on AMD x86 and ARM Cortex-M4 platforms show performance improvements of approximately 20%, 13%, and 27%, respectively. The technique can also be used to accelerate the verification of ECDSA signatures, provided that one additional bit of information is appended to the signature.

As part of our work, we analyze the performance of 3-dimensional lattice reduction algorithms, which are critical for multi-scalar decompositions. To identify the most efficient approach, we experimentally compare Semaev’s algorithm --- known for its best asymptotic complexity --- with the simpler Lagrange’s algorithm. Our results reveal that, despite its simplicity, Lagrange’s algorithm is nearly twice as fast as Semaev’s in practice.

Sorting encrypted values is an open research problem that plays a crucial role in the broader objective of providing efficient and practical privacy-preserving online services. The current state of the art work by Mazzone, Everts, Hahn and Peter (USENIX Security '25) proposes efficient algorithms for ranking, indexing and sorting based on the CKKS scheme, which deviates from the compare-and-swap paradigm, typically used by sorting networks, using a permutation-based approach. This allows to build shallow sorting circuits in a very simple way. In this work, we follow up their work and explore different approaches to approximate the nonlinear functions required by the encrypted circuit (where only additions and multiplications can be evaluated), and we propose simpler solutions that allow for faster computations and smaller memory requirements.

In particular, we drastically reduce the upper bound on the depth of the circuits from 65 to 20, making our circuits usable in relatively small rings such as $N=2^{16}$, even for sorting values while preserving up to three decimal places. As an example, our circuit sorts 128 values with duplicates in roughly 20 seconds on a laptop, using roughly 1 GB of memory, maintaining a precision of 0.01. Furthermore, we propose an implementation of a swap-based bitonic network that is not based on approximations of the sgn$(x)$ function, which scales linearly with the number of values, useful when the number of available slots is small.

In this paper, we propose an improvement to the McEliece encryption scheme by replacing the Goppa code with a $(U+V,U+W)$ code. Specifically, we embed the generator matrices of a split Reed-Solomon code into the generator matrix of the $(U+V,U+W)$ code. This approach disrupts the algebraic structure of Reed-Solomon codes, thereby enhancing resistance against structural attacks targeting such codes, while simultaneously preserving their excellent error-correcting capabilities. As a result, the proposed scheme achieves a significant reduction in public key size. Under the hardness assumptions of the decoding problem and the code distinguishing problem for $(U+V,U+W)$ codes, we prove that the scheme achieves indistinguishability under chosen-plaintext attacks (IND-CPA security). Finally, we provide recommended parameters for various security levels and compare the proposed scheme with other code-based public key encryption schemes.

Observing the growing popularity of random permutation (RP)-based designs (e.g, Sponge), Bart Mennink in CRYPTO 2019 has initiated an interesting research in the direction of RP-based pseudorandom functions (PRFs). Both are claimed to achieve beyond-the-birthday-bound (BBB) security of $2n/3$ bits ($n$ being the input block size in bits) but require two instances of RPs and can handle only one-block inputs. In this work, we extend research in this direction by providing two new BBB-secure constructions by composing the tweakable Even-Mansour appropriately. Our first construction requires only one instance of an RP and requires only one key. Our second construction extends the first to a nonce-based Message Authentication Code (MAC) using a universal hash to deal with multi-block inputs. We show that the hash key can be derived from the original key when the underlying hash is the Polyhash. We provide matching attacks for both constructions to demonstrate the tightness of the proven security bounds.

Privacy is a growing concern for smart contracts on public ledgers. In recent years, we have seen several practical systems for privacy-preserving smart contracts, but they only target privacy of on-chain data, and rely on trusted off-chain parties with user data -- for instance, a decentralized finance application (e.g. exchange) relies on an off-chain matching engine to process client orders that get settled on-chain, where privacy only applies to the on-chain data. Privacy conscious users demand stronger notions of privacy, for their identity and their data, from all other parties in the ecosystem.

We propose a novel framework for smart contracts that ensures {\em doubly private} execution, addressing {both on-chain and off-chain privacy} requirements. In our framework, clients submit their requests in a privacy-preserving manner to a group of (potentially mutually untrusting) servers. These servers collaboratively match client requests without learning any information about the data or identities of the clients.

We then present {\em Jigsaw}, an efficient cryptographic realization of our proposed framework. {\em Jigsaw} builds on the ZEXE architecture (Bowe et al., S\&P 2020), which leverages zkSNARKs, and extends Collaborative zkSNARKs (Ozdemir and Boneh, USENIX 2022) to enable proof generation by a group of servers.

In Jigsaw, we introduce a novel collaborative zkSNARK construction that achieves low latency and reduced proving time, and showcase these advantages over sample applications ranging from trading in a decentralized exchange to auctions and voting. Our experiments demonstrate that {\em Jigsaw} is roughly $40-50$x faster in proof generation and uses orders-of-magnitude less bandwidth than the naive approach of using off-the-shelf Collaborative zkSNARKs.

Decentralized e-voting enables secure and transparent elections without relying on trusted authorities, with blockchain emerging as a popular platform. It has compelling applications in Decentralized Autonomous Organizations (DAOs), where governance relies on voting with blockchain-issued tokens. Quadratic voting (QV), a mechanism that mitigates the dominance of large token holders, has been adopted by many DAO elections to enhance fairness. However, current QV systems deployed in practice publish voters' choices in plaintext with digital signatures. The open nature of all ballots comprises voter privacy, potentially affecting voters' honest participation. Prior research proposes using cryptographic techniques to encrypt QV ballots, but they work in a centralized setting, relying on a trusted group of tallying authorities to administrate an election. However, in DAO voting, there is no trusted third party.

In this paper, we propose QV Network (QV-net), the first decentralized quadratic voting scheme, in which voters do not need to trust any third party other than themselves for ballot secrecy. QV-net is self-tallying with maximal ballot secrecy. Self-tallying allows anyone to compute election results once all ballots are cast. Maximal ballot secrecy ensures that what each voter learns from QV-net is nothing more than the tally and their own ballot. We provide an open-source implementation of QV-net to demonstrate its practicality based on real-world DAO voting settings, reporting only a few milliseconds for voting and a maximum of 255 milliseconds for tallying.

The exceptional efficiency of QV-net is attributed to the design of two new Zero-Knowledge Argument of Knowledge (ZKAoK) protocols for QV ballot secrecy and integrity. Previous works generally rely on pairing-friendly curves to prove the well-formedness of an encrypted QV ballot. But they incur heavy computation and large data sizes. We tackle the challenges of appropriately formalizing and proving ZKAoK relations for QV without using these curves. Specifically, we develop a succinct ZKAoK to prove a new relation: the sum of squares of a private vector's components equals a private scalar. We also introduce the first aggregated range proof to prove that values committed under different keys fall within their respective ranges. Together, these two new zero-knowledge protocols enable us to build an efficient decentralized QV scheme and are of independent interest.

Group Signatures are fundamental cryptographic primitives that allow users to sign a message on behalf of a predefined set of users, curated by the group manager. The security properties ensure that members of the group can sign anonymously and without fear of being framed. In dynamic group signatures, the group manager has finer-grained control over group updates while ensuring membership privacy (i.e., hiding when users join and leave). The only known scheme that achieves standard security properties and membership privacy has been proposed by Backes et al. CCS 2019. However, they rely on an inefficient revocation mechanism that re-issues credentials to all active members during every group update, and users have to rely on a secure and private channel to join the group. In this paper, we introduce a dynamic group signature that supports verifier-local revocation, while achieving strong security properties, including membership privacy for users joining over a public channel. Moreover, when our scheme is paired with structure-preserving signatures over equivalence class it enjoys a smaller signature size compared to Backes et al. Finally, as a stand-alone contribution we extend the primitive Asynchronous Remote Key Generation (Frymann et al. CCS 2020) with trapdoors and introduce new security properties to capture this new functionality, which is fundamental to the design of our revocation mechanism

Fully Homomorphic Encryption (FHE) is a key technology to enable privacy-preserving computation. While optimized FHE implementations already exist, the inner workings of FHE are technically complex. This makes it challenging, especially for non-experts, to develop highly-efficient FHE programs that can exploit the advanced hardware of today. Although several compilers have emerged to help in this process, due to design choices, they are limited in terms of application support and the efficiency levels they can achieve.

In this work, we showcase how to make FHE accessible to non-expert developers while retaining the performance provided by an expert-level implementation. We introduce Parasol, a novel end-to-end compiler encompassing a virtual processor with a custom Instruction Set Architecture (ISA) and a low-level library that implements FHE operations. Our processor integrates with existing compiler toolchains, thereby providing mainstream language support. We extract parallelism at multiple levels via our processor design and its computing paradigm. Specifically, we champion a Circuit Bootstrapping (CBS)-based paradigm, enabling efficient FHE circuit composition with multiplexers. Furthermore, Parasol’s underlying design highlights the benefits of expressing FHE computations at a higher level—producing highly compact program representations. Our experiments demonstrate the superiority of Parasol, in terms of runtime (up to 17x faster), program size (up to 22x smaller), and compile time (up to 32x shorter) compared to the current state-of-the-art. We expect the FHE computing paradigm underlying Parasol to attract future interest since it exposes added parallelism for FHE accelerators to exploit.

The Unbalanced Oil and Vinegar construction (UOV) has been the backbone of multivariate cryptography since the fall of HFE-based schemes. In fact, 7 UOV-based schemes have been submitted to the NIST additional call for signatures, and 4 of these made it to the second round. For efficiency considerations, most of these schemes are defined over a field of characteristic 2. This has as a side effect that the polar forms of the UOV public maps are not only symmetric, but also alternating.

In this work, we propose a new key-recovery attack on UOV in characteristic 2 that makes use of this property. We consider the polar forms of the UOV public maps as elements of the exterior algebra. We show that these are contained in a certain subspace of the second exterior power that is dependent on the oil space. This allows us to define relations between the polar forms and the image of the dual of the oil space under the Plücker embedding. With this, we can recover the secret oil space using sparse linear algebra.

This new attack has an improved complexity over previous methods and reduces the security by 4, 11, and 20 bits for uov-Ip, uov-III, and uov-V, respectively. Furthermore, the attack is applicable to MAYO$_2$ and improves on the best attack by 28 bits.

This paper presents OnionPIRv2, an efficient implementation of OnionPIR incorporating standard orthogonal techniques and engineering improvements. OnionPIR is a single-server PIR scheme that improves response size and computation cost by utilizing recent advances in somewhat homomorphic encryption (SHE) and carefully composing two lattice-based SHE schemes to control the noise growth of SHE. OnionPIRv2 achieves $2.5$x-$3.6$x response overhead for databases with moderately large entries (around $4$ KB or above) and up to $1600$ MB/s server computation throughput.