International Association
for Cryptologic Research

Discrete Gaussian Sampling (DGS) over the integers—also known as integer Gaussian sampling— is used to generate integer values that statistically follow the discrete Gaussian distribution and plays a central role in lattice-based cryptography. Among existing approaches for integer DGS, the cumulative distribution table (CDT) method is widely adopted. However, CDT sampling typically incurs substantial storage costs due to the need to store high-precision fixed-point probability tables, where a precision of $k$ bits is required to achieve a statistical distance of $2^{-k}$ from the ideal distribution. In this work, we propose a more compact representation of CDT based on Simultaneous Diophantine Approximation (SDA). Instead of storing fixed-point values, our method expresses the probabilities in the CDT as a sequence of rational numbers with a common denominator. With parameter selection guided by SDA, this compact fractional representation enables reducing data width while maintaining the same level of statistical accuracy. Our SDA-CDT construction offers clear advantages in both computation speed and storage compared to classical CDT implementations. For example, in Frodo-1344, our sampler achieves a 19.97% increase in speed (from 12.10 million to 14.51 million samples per second) and a 3.85% reduction in memory usage (from 104 bits to 100 bits). Similarly, in Frodo-976, we observe a 10.88% speedup and a 21.60% decrease in memory cost. In addition, our design eliminates floating-point arithmetic and supports a fully constant-time online sampling procedure, which ensures resistance to timing side-channel attacks without compromising performance.

HPPC is a multivariate signature scheme submitted to the NIST PQC standardization process in response to the recent call for additional signature schemes. We show that, despite some non-standard notational choices in the submission document, HPPC can be viewed as a special case of the well-studied, but broken for all practical parameters, HFE signature scheme. We further show that the HPPC construction introduces additional structure that further weakens the scheme. For instance, the central map has $Q$-rank $2$ independently from the degree $D$ of the central polynomial that is used.

Using these observations, we show that HPPC is weaker against the direct attack than claimed in the submission document and more crucially that all parameter sets can be practically broken using MinRank techniques. For instance, with a very naive implementation, we have been able to recover an equivalent key in approximately 8 minutes for security level 2, an hour and a half for security level 4, and slightly more than 7 hours for security level 5.

Private Information Retreival (PIR) schemes without preprocessing are known to incur linear server computation per client query. Several recent works have shown that by relying on a one-time preprocessing phase, we can get around this barrier, and achieve sublinear computation per query without relying on any cryptographic assumptions. Beimel et al. (CRYPTO'00) first showed a family of schemes whose bandwidth and computation per query scale as fast as $n^{O(1/S)}$ where $S$ denotes the number of servers and $n$ denotes the database size. Unfortunately, their schemes are not practical partly because the servers must each store an encoded version of the database, and the encoding length grows sharply as we increase $S$. The recent work of Singh et al. (TCC'24) showed how to achieve similar bandwidth scaling but without the server space blowup. To get this, they rely on a different type of preprocessing called client-specific preprocessing, where the stateful client stores some hints and the servers store only the original database. Unfortunately, Singh et al.'s result is completely impractical due to the reliance on Dvir and Gopi's PIR as a building block.

We propose Zelda (short for ZEro-Leakage Data Access), the first concretely efficient, information-theoretic multi-server PIR scheme with sublinear computation. Our work makes both theoretical and practical contributions. On the theoretical front, we devise a unified framework for constructing multi-server PIR with client-specific preprocessing. This gives us a parametrizable family of schemes that asymptotically outperform all prior constructions in the same setting, including Singh et al. (TCC'24) and Ishai et al. (CRYPTO'24). On the practical front, Zelda is conceptually simple, self-contained, and does not rely on any underlying PIR as a building block. We implemented Zelda and open sourced our code. We compared the concrete performance of Zelda with a state-of-the-art PIR scheme called QuarterPIR (Eurocrypt'24), which relies on pseudorandom functions for security. Experimental results show that Zelda outperforms QuarterPIR in terms of online response time and client space (assuming typical fiber optical links), at the price of increased costs for offline maintenance operations.

This paper studies the Twinkle family of low-latency symmetric key schemes designed by Wang et al. (CiC 2024). In particular, it presents cryptanalysis of both the mode and the underlying primitive. Twinkle is a PRF-based design, and an authenticated encryption scheme Twinkle-AE is specified based on a dedicated PRF called Twinkle-PRF. To achieve low latency, Twinkle-PRF uses a large key and state to produce sufficient randomness in a single step. Twinkle-AE uses a 1024- or 512-bit key for authentication and generates a $t$-bit tag, where $t \in \{64, 128\}$. It claims to provide $t$ bits of integrity. Several Twinkle-AE parameter sets claim higher confidentiality than integrity. In this setup, for any ciphertext, an adversary can obtain the message after $O(2^t)$ decryption attempts by guessing the tag, allowing attacks in the chosen-ciphertext setting. We show that a 1024- or 512-bit authentication key can be recovered using only $O(2^t)$ queries. The recovered authentication key enables the generation of valid ciphertexts for arbitrary plaintexts, thus achieving universal forgery.

In the second part of the paper, we perform cryptanalysis on reduced-round variants of the 1280-bit public permutation Twinkle-P, which serves as a core component of Twinkle-PRF. We investigate impossible differential, zero-correlation linear, integral, and differential-linear distinguishers by developing automated analytic tools. We provide practical distinguishers for up to 5 rounds, and the longest distinguisher reaches 6 rounds with a complexity of $2^{74.32}$. This surpasses the round bounds evaluated by the designers. We stress that our attacks on mode exploits the gap between the claimed confidentiality and integrity levels, thus have no impact on the parameter sets having the same security level.

Our attacks on the permutation do not have any significant impact on the whole specifications. Moreover, we note that Twinkle-AE-512b/Twinkle-AE-1024b and Twinkle-PA remain secure, and the versions we attacked would also be secure if the claimed confidentiality level matched the integrity level.

Constrained PRFs are PRFs that allow the generation of constrained keys, which can be used to evaluate the PRF on a subset of the inputs. The PRF is still pseudorandom for an adversary how obtains multiple of these constrained keys on all inputs where none of the constrained keys allow it to evaluate the PRF. Constrained PRFs are known for some simple constraint classes (such as puncturing or intervals) from one-way functions, but for more powerful constraint classes such as bitfixing the only known constructions need heavy machinery, like indistinguishability obfuscation or multilinear maps.

In this work we show that constrained PRFs (for any constraint class) do not imply key agreement in a black-box way with an oracle separation. The result also applies to delegatable constrained PRFs, where constrained keys can be used to generate other, more restrictive constrained keys.

We show that this result has interesting applications for identity-based cryptography, where users obtain secret keys from a trusted, central authority. Namely, it shows that primitives that allow key agreement in this setting, like identity-based non-interactive key exchange and a weaker variant of identity-based encryption that we introduce in this work, do not imply key agreement and thus can exist even in a world where traditional key agreement and public-key encryption is impossible.

As a side result, we obtain a very simple proof of the classic result by Impagliazzo and Rudich (STOC 89) that separates key agreement from one-way functions. The proof is similar to a proof by Brakerski, Katz, Segev, and Yerukhimovich (TCC 2011), but more general because it applies to key agreement with non-perfect correctness. The proof also shows that Merkle puzzles are optimal, which Barak and Mahmoody (Crypto 2009) have shown before, but our proof is much simpler (and has tighter constants).

Migration to quantum-safe cryptography represents a significant technological shift, addressing the vulnerabilities of traditional cryptographic primitives, such as KEMs and digital signatures. Yet, a number of challenges remain, especially in the development of secure solutions for sophisticated cryptographic applications. One of them is Smart-ID, European server-supported (threshold) signing service.

To address this issue, we present $\textsf{Electrum}$, a fail-stop server-supported signature scheme designed to enhance security of existing Smart-ID service. $\textsf{Electrum}$ combines multiprime RSA-based signatures with fail-stop features: providing not only unforgeability against classical adversaries but also allowing to prove that a given signature is a forgery made by classical and/or quantum adversaries. Proposed protocol can be seen as a temporary remedy against the quantum threat until standardised threshold signature schemes become a common practice. To prove security of $\textsf{Electrum}$, we introduce a new ideal functionality $\mathcal{F}^{\textsf{SplFS}}$ for a fail-stop server-supported signing in the Universal Composability model. We show that $\textsf{Electrum}$ protocol securely realizes the proposed functionality $\mathcal{F}^{\textsf{SplFS}}$.

This paper presents a family of representations of elementary vectors, which covers existing representations as special cases. We make use of the family of representations to reduce signature size of existing signature schemes based on the VOLE-in-the-head framework. In particular, we use new representations to build modelings for the regular syndrome decoding problem in $\mathbb{F}_2$, which is used in the post-quantum signature scheme SDith, and for the permuted kernel problem in characteristic-2 fields, which is used in a post-quantum signature scheme recently proposed by Bettaieb, Bidoux, Gaborit, and Kulkarni. For the “short” parameter sets of SDith, which are designed for minimiz- ing signature size, we achieve a size reduction of 3.6% to 4.2%. For parameter sets of the Bettaieb-Bidoux-Gaborit-Kulkarni signature scheme, we achieve a size reduction of 9% to 12%.

Digital signatures are essential cryptographic tools that provide authentication and integrity in digital communications. However, privacy-sensitive applications—such as e-voting and digital cash—require more restrictive verification models to ensure confidentiality and control. Strong Designated Verifier Signature (SDVS) schemes address this need by enabling the signer to designate a specific verifier, ensuring that only this party can validate the signature. Existing SDVS constructions are primarily based on number-theoretic assumptions and are therefore vulnerable to quantum attacks. Although post-quantum alternatives—particularly those based on lattices—have been proposed, they often entail large key and signature sizes. In this work, we introduce $\mathsf{CSI\text{-}SDVS}$, a novel isogeny-based SDVS scheme that offers a compact, quantum-resistant alternative. Our construction builds on the ideal class group action framework of CSIDH and the signature techniques of CSI-FiSh, and relies on the hardness of the Multi-Target Group Action Inverse Problem (MT-GAIP). $\mathsf{CSI\text{-}SDVS}$ achieves strong security guarantees—namely, Strong Unforgeability under Chosen-Message Attacks (SUF-CMA), Non-Transferability (NT), and Privacy of Signer’s Identity (PSI)—in the random oracle model. Remarkably, both the keys and signatures in $\mathsf{CSI\text{-}SDVS}$ are of size $\mathcal{O}(\lambda)$, representing a significant improvement over the typical $\mathcal{O}(\lambda^2)$ bounds in existing post-quantum SDVS schemes, thereby making it among the most compact PQC-based SDVS schemes and the only post-quantum secure construction based on isogenies.

In 2009, Galindo and Garcia proposed the usage of concatenated Schnorr signatures for the hierarchical delegation of public keys, creating a quite efficient identity-based signature scheme (IBS). Essentially, the scheme builds upon the Schnorr signature scheme to generate a primary signature, part of which is then used as a secret key to produce signatures on subsequent messages. The resulting IBS is proven secure against existential forgery on adaptive chosen-message and adaptive identity attacks using variants of the Forking Lemma. In this paper, our goal is to answer the following question: would it be feasible to build upon the widely used elliptic curve digital signature algorithm (ECDSA) scheme to obtain a similarly secure and efficient IBS? We answer this affirmatively, opening interesting possibilities not only for identity-based signatures with ECDSA but also for applications such as secure credential delegation. This latter application is of particular interest considering the wide support for ECDSA in web- and cloud-oriented authentication systems (e.g., based on JSON Web Tokens). The resulting scheme is proven secure, combining the Bijective Random Oracle model and the existential unforgeability game in an identity-based setup. Our results show that even considering ECDSA's non-linear characteristic and more convoluted verification process when compared to Schnorr signatures, it is possible to obtain shorter signatures than Galindo-Garcia's scheme.

A redactable set signature scheme is a signature scheme that allows a redactor, without possessing the signing key, to convert a signature on set $S$ to a signature on set $S'$ if $S' \subset S$. This paper introduces a new form of redactable set signature scheme called a policy-based redactable set signature scheme. These redactable set signatures allow for a signer to provide a redaction policy at signing time that limits the possible redactions that can be made by a redactor. In particular, a signature on set $S$ can only be redacted to a signature on $S'$ if $S' \subset S$ and $P\left(S'\right) = 1$.

In this note, we present a new instantiation of the hash-based multi-signature framework introduced by Drake, Khovratovich, Kudinov, and Wagner (CiC Vol 2 Issue 1, eprint 2025/055) for Ethereum’s consensus layer. Inspired by a recent work of Khovratovich, Kudinov, and Wagner (Crypto 2025, eprint 2025/889), we instantiate the framework with a novel incomparable encoding that improves the tradeoff between signature size and verification hashing. The purpose of this document is to make explicit how to use the ideas of the latter work within the framework of Drake, Khovratovich, Kudinov, and Wagner.

The efficient implementation of Boolean masking with minimal overhead in terms of latency has become a critical topic due to the increasing demand for physically secure yet high-performance cryptographic primitives. However, achieving low latency in masked circuits while ensuring that glitches and transitions do not compromise their security remains a significant challenge. State-of-the-art multiplication gadgets, such as the recently introduced HPC4 (CHES 2024), offer composable security against glitches and transitions, as proven under the robust d-probing model. However, these gadgets require at least one clock cycle per computation, resulting in a latency overhead that increases with the algebraic degree. In contrast, LMDPL gadgets (CHES 2014 & CHES 2020) can achieve fixed latency independent of the algebraic degree, effectively addressing this issue. However, they are limited to two shares, and extending them to guarantee composable security at order d with d+1 shares is considered an open challenge. In this work, we introduce CCHPC, a novel hardware masking scheme built on the concept of LMDPL. Specifically, CCHPC achieves a fixed latency of d clock cycles by masking a Boolean function of arbitrary algebraic degree with d+1 shares. CCHPC gadgets are secure and trivially composable, as formally proven under the RR d-probing model (CHES 2024). Using CCHPC gadgets, we design a masked AES encryption core which can be instantiated for an arbitrary number of d+1 shares with a total latency of 11 + d clock cycles.

The cube attack is one of the most powerful attacks on stream ciphers, with recovering the superpoly as its key step. The core monomial prediction is the state-of-the-art technique for superpoly recovery, which can reach 851 rounds for Trivium thus far (EUROCRYPT 2024). The core monomial prediction heavily relies on the trail enumeration which is the bottleneck for its efficiency.

This paper further explores the potential of the core monomial prediction for Trivium by constructing a composite representation for the superpoly. This representation allows us to detect the algebraic structure of the superpoly under specific conditions on the intermediate variables, without the computational burden of trail enumerations. Leveraging these discovered conditions, we successfully recovered weak-key superpolies for 852-round Trivium, establishing the first cryptanalytic result against 852-round Trivium in the literature to date.

We consider the multivariate scheme $\texttt{Pesto}$, which was introduced by Calderini, Caminata, and Villa. In this scheme, the public polynomials are obtained by applying a CCZ transformation to a set of quadratic secret polynomials. As a consequence, the public key consists of polynomials of degree $4$. In this work, we show that the public degree $4$ polynomial system can be efficiently reduced to a system of quadratic polynomials. This seems to suggest that the CCZ transformation may not offer a significant increase in security, contrary to what was initially believed.

We present a collection of protocols to perform privacy-preserving set operations in the third-party private set intersection (PSI) setting. This includes several protocols for multi-party third party PSI. In this model, there are multiple input parties (or clients) each holding a private set of elements and the receiver is an external party (termed as third-party) with no inputs. Multi-party third party PSI enables the receiver to learn only the intersection result of all input clients' private sets while revealing nothing else to the clients and the receiver. Our solutions include constructions that are provably secure against an arbitrary number of colluding parties in the semi-honest model. Additionally, we present protocols for third-party private set difference and private symmetric difference, whereby the learned output by the inputless third-party is the set difference and symmetric difference respectively of two other input parties, while preserving the same privacy guarantees. The motivation in the design of these protocols stems from their utilities in numerous real-world applications. We implemented our protocols and conducted experiments across various input and output set sizes.

Granular Synchrony (Giridharan et al. DISC 2024) is a new network model that unifies the classic timing models of synchrony and asynchrony. The network is viewed as a graph consisting of a mixture of synchronous, eventually synchronous, and asynchronous communication links. It has been shown that Granular Synchrony allows deterministic Byzantine agreement protocols to achieve a corruption threshold in between complete synchrony and complete asynchrony if and only if the network graph satisfies the right condition, namely, that no two groups of honest parties of size $n-2t$ can be partitioned from each other.

In this work, we show that the same network condition is also tight for Agreement on a Common Subset (ACS), Verifiable Secret Sharing (VSS), and secure Multi-Party Computation (MPC) with guaranteed output delivery, when the corruption threshold is between one-third and one-half. Our protocols are randomized and assume that all links are either synchronous or asynchronous. %(no partially synchronous links are needed). Our ACS protocol incurs an amortized communication cost of $O(n^3\lambda)$ bits per input, and our VSS and MPC protocols incur amortized communication costs of $O(n^3)$ and $O(n^4)$ field elements per secret and per multiplication gate, respectively. To design our protocols, we also construct protocols for Reliable Broadcast and Externally Valid Byzantine Agreement (EVBA), which are of independent interest.

Differential cryptanalysis is one of the most powerful attacks on modern block ciphers. After many year of research, we have very good techniques for showing that the probability that an input difference leads to an output difference (i.e., the probability of a differential) is either significantly higher, or lower than expected, and such large deviations lead to attacks.

On the other hand, modern techniques cannot estimate with high accuracy the probability of a differential that spans many rounds of the cipher. Therefore, these techniques are sufficient to argue only limited resistance against differential cryptanalysis.

In particular, for the AES, Keliher and Sui proved in 2005 that any 4-round differential has probability at most (about) $2^{-114}$, under the assumption that the round-keys are chosen independently. This establishes limited security arguments against classical differential cryptanalysis. Stronger bounds are only known when considering thousands of AES rounds, whereas at most 14 rounds are used in practice by AES-256.

In this paper, we propose new techniques for estimating the probability of a differential under the assumption that the round-keys of the cipher are chosen independently. We apply our techniques to AES, and show that the probability of every differential in 8-round AES is within an additive factor of $2^{-128} \cdot \frac{1}{50}$ from the expected value of $\frac{1}{2^{128} - 1}$.

We further apply our techniques to prove that 8-round AES is at most $2^{-18}$-close to a pairwise independent permutation, while 40-round AES is at most $2^{-135}$-close. The latter result improves upon the work of Liu, Tessaro and Vaikuntanathan [CRYPTO 2021], who proved a similar bound for 9000-round AES.

To obtain our results, we develop and adapt a variety of techniques for analyzing differentials using functional analysis. We expect these techniques to be useful for analyzing differentials in additional block ciphers besides the AES.

Inner Product Arguments (IPA) [BCC+16,BBB+17] are a family of proof systems with $O(\log n)$ sized proofs, $O(n)$ time verifiers, and transparent setup. Bootle, Chiesa and Sotiraki [BCS21] observed that an IPA can be viewed as a sumcheck protocol [LFKN92] where the summed polynomial is allowed to have coefficients in a group rather than a field. We leverage this viewpoint to improve the performance of multi-linear polynomial commitments based on IPA. Specifically, - We introduce a simplified variant of Halo-style accumulation that works for multilinear evaluation claims, rather than only univariate ones as in [BGH19,BCMS20]. - We show that the size $n$ MSM the IPA verifier performs can be replaced by a ``group variant'' of $\mathsf{basefold}$[ZCF23]. This reduces the verifier complexity from $O(n)$ to $O_{\lambda}(\log^2 n)$ time at the expense of an additional $4n$ scalar multiplications for the IPA prover.

One of the main layers in the Advanced Encryption Standard (AES) is the substitution layer, where an $8 \times 8$ S-Box is used $16$ times. The substitution layer provides confusion and makes the algorithm resistant to cryptanalysis techniques. Therefore, the security of the algorithm is also highly dependent on this layer. However, the cost of implementing $8 \times 8$ S-Box on FPGA platforms is considerably higher than other layers of the algorithm. Since S-Boxes are repeatedly used in the algorithm, the cost of the algorithm highly comes from the substitution layer. In 2005, Canright used different extension fields to represent AES S-Box to get FPGA-friendly compact designs. The best optimization proposed by Canright reduced the gate-area of the AES S-Box implementation by $20\%$.

In this study, we use the same optimization methods that Canright used to optimize AES S-Box on hardware platforms. Our purpose is not to optimize AES S-Box; we aim to create another $8 \times 8$ S-Box which is strong and compact enough for FPGA platforms. We create an $8 \times 8$ S-Box using the inverse field operation as in the case of AES S-Box. We use another irreducible polynomial to represent the finite field and get an FPGA-friendly compact and efficient $8 \times 8$ S-Box. The finite field we propose provides the same level of security against cryptanalysis techniques with a $3.125\%$ less gate-area on Virtex-7 and Artix-7 FPGAs compared to Canright’s results. Moreover, our proposed S-Box requires $11.76\%$ less gate on Virtex-4 FPGAs. These gate-area improvements are beneficial for resource-constraint IoT devices and allow more copies of the S-Box for algorithm parallelism. Therefore, we claim that our proposed S-Box is more compact and efficient than AES S-Box. Cryptographers who need an $8 \times 8$ S-Box can use our proposed S-Box in their designs instead of AES S-Box with the same level of security but better efficiency.

Non-interactive batch arguments (BARGs) for NP allow a prover to prove $\ell$ NP statements with a proof whose size scales sublinearly with $\ell$. In this work, we construct a pairing-based BARG where the size of the common reference string (CRS) scales linearly with the number of instances and the prover's computational overhead is quasi-linear in the number of instances. Our construction is fully black box in the use of the group. Security relies on a $q$-type assumption in composite-order pairing groups.

The best black-box pairing-based BARG prior to this work has a nearly-linear size CRS (i.e., a CRS of size $\ell^{1 + o(1)}$) and the prover overhead is quadratic in the number of instances. All previous pairing-based BARGs with a sublinear-size CRS relied on some type of recursive composition and correspondingly, non-black-box use of the group. The main technical insight underlying our construction is to substitute the vector commitment in previous pairing-based BARGs with a polynomial commitment. This yields a scheme that does not rely on cross terms in the common reference string. In previous black-box pairing-based schemes, the super-linear-size CRS and quadratic prover complexity was due to the need for cross terms.