International Association
for Cryptologic Research

This study addresses the challenge of strengthening cryptographic security measures in the face of evolving cyber threats. The aim is to apply Kleene's Theorem and automata theory to improve the modeling and analysis of cybersecurity scenarios, focusing on the CyberMoraba game. Representing the game's strategic moves as regular expressions and mapping them onto finite automata provides a solid framework for understanding the interactions between attackers and defenders. This approach helps in identifying optimal strategies and predicting potential outcomes, which contributes to the development of stronger cryptographic security protocols. The research advances the theoretical use of automata theory in cybersecurity while offering practical insights into enhancing defense mechanisms against complex cyber attacks. This work connects theoretical computer science with practical cybersecurity, demonstrating the importance of automata theory in cryptology.

We study the problem of generating public unbiased randomness in a distributed manner within the recent You Only Speak Once (YOSO) framework for stateless multiparty computation, introduced by Gentry et al. in CRYPTO 2021.

Such protocols are resilient to adaptive denial-of-service attacks and are, by their stateless nature, especially attractive in permissionless environments.

While most works in the YOSO setting focus on independent random corruptions, we consider YOSO protocols with worst-case corruptions, a model introduced by Nielsen et al. in CRYPTO 2022.

Prior work on YOSO public randomness generation with worst-case corruptions designed information-theoretic protocols for $t$ corruptions with either $n=6t+1$ or $n=5t$ roles, depending on the adversarial network model.

However, a major drawback of these protocols is that their communication and computational complexities scale exponentially with $t$.

In this work, we complement prior inefficient results by presenting and analyzing simple and efficient protocols for YOSO public randomness generation secure against worst-case corruptions in the computational setting.

Our first protocol is based on publicly verifiable secret sharing and uses $n=3t+2$ roles.

Since this first protocol requires setup and somewhat heavy cryptographic machinery, we also provide a second lighter protocol based on ElGamal commitments and verifiable secret sharing which uses $n=5t+4$ or $n=4t+4$ roles depending on the underlying network model. We demonstrate the practicality of our second protocol by showing experimental evaluations, significantly improving over prior proposed solutions for worst-case corruptions, especially in terms of transmitted data size.

The formal verification of architectural strength in terms of computational complexity is achieved through reduction of the Non-Commutative Grothendieck problem in the form of a quadratic lattice. This multivariate form relies on equivalences derived from a k-clique problem within a multigraph. The proposed scheme reduces the k-clique problem as an input function, resulting in the generation of a quadratic used as parameters for the lattice. By Grothendieck’s inequality, the satisfiability of lattice constraints in terms of NP-Hard and NP-Complete bounds is provably congruent to a closest vector problem in the lattice. The base vectors of the resulting lattice are treated as a holomorphic vector bundle. From the resulting bilinear matrices, the tight hardness reduction of the closest vector problem as the shortest vector problem is introduced within the system. The derivation of the closest vector problem requires that the lattice is necessarily generated by a <0|1>-Matrix expressed as a quadratic. This vector bundle is denoted as the unit ball with congruent topology to the Riemann sphere, symbolized as ?. For the Grothendieck constraints, the relative vector norms necessarily result in satisfaction of NP-Hard requirements for shortest vector problems in the lattice.

Topology-hiding broadcast (THB) enables parties communicating over an incomplete network to broadcast messages while hiding the network topology from within a given class of graphs. Although broadcast is a privacy-free task, it is known that THB for certain graph classes necessitates computational assumptions, even against "honest but curious" adversaries, and even given a single corrupted party. Recent works have tried to understand when THB can be obtained with information-theoretic (IT) security (without cryptography or setup assumptions) as a function of properties of the corresponding graph class.

We revisit this question through a case study of the class of wheel graphs and their subgraphs. The $n$'th wheel graph is established by connecting $n$ nodes who form a cycle with another "center" node, thus providing a natural extension that captures and enriches previously studied graph classes in the setting of IT-THB.

We present a series of new findings in this line. We fully characterize feasibility of IT-THB for any class of subgraphs of the wheel, each possessing an embedded star (i.e., a well-defined center connected to all other nodes). Our characterization provides evidence that IT-THB feasibility may correlate with a more fine-grained degree structure---as opposed to pure connectivity---of the corresponding graphs. We provide positive results achieving perfect IT-THB for new graph classes, including ones where the number of nodes is unknown. Further, we provide the first feasibility of IT-THB on non-degenerate graph-classes with $t>1$ corruptions, for the class of friendship graphs (Erdos, Renyi, Sos '66).

This paper surveys interactions between choices of elliptic curves and the security of elliptic-curve cryptography. Attacks considered include not just discrete-logarithm computations but also attacks exploiting common implementation pitfalls.

Lookup arguments have recently attracted a lot of developments due to their applications in the constructions of succinct non-interactive arguments of knowledge (SNARKs). A closely related topic is subsequence arguments in which one can prove that string $\mathbf{s}$ is a subsequence of another string $\mathbf{t}$, i.e., deleting some characters in $\mathbf{t}$ can achieve $\mathbf{s}$. A dual notion, namely, non-subsequence arguments, is to prove that $\mathbf{s}$ is not a subsequence of $\mathbf{t}$. These problems have a lot of important applications in DNA sequence analysis, internet of things, blockchains, natural language processing, speech recognition, etc. However, despite their applications, they are not well-studied in cryptography, especially succinct arguments for non-subsequences with efficient proving time and sublinear verification time.

In this work, we propose the first succinct non-subsequence argument. Our solution applies the sumcheck protocol and is instantiable by any multivariate polynomial commitment schemes (PCSs). We achieve an efficient prover whose running time is linear in the size of sequences $\mathbf{s}$, $\mathbf{t}$ and their respective alphabet $\Sigma$. Our proof is succinct and the verifier time is sublinear assuming the employed PCS has succinct commitments and sublinear verification time. When instantiating with Sona PCS (EUROCRYPT'24), we achieve proof size $\mathcal{O}(\log_2|\mathbf{s}| + \log_2|\mathbf{t}|+\log_2|\Sigma|)$, prover time $\mathcal{O}(|\mathbf{s}|+|\mathbf{t}|+|\Sigma|)$ and verifier time $\mathcal{O}(\sqrt{|\mathbf{s}|}+\sqrt{|\mathbf{t}|}+\sqrt{|\Sigma|})$.

Extending our technique, we can achieve a batch subsequence argument for proving in batch $k$ interleaving subsequence and non-subsequence arguments without proof size suffering a linear blow-up in $k$.

Let $N=pq$ be the product of two balanced prime numbers $p$ and $q$. In 2002, Elkamchouchi, Elshenawy and Shaban introduced an RSA-like cryptosystem that uses the key equation $ed - k (p^2-1)(q^2-1) = 1$, instead of the classical RSA key equation $ed - k (p-1)(q-1) = 1$. Another variant of RSA, presented in 2017 by Murru and Saettone, uses the key equation $ed - k (p^2+p+1)(q^2+q+1) = 1$. Despite the authors' claims of enhanced security, both schemes remain vulnerable to adaptations of common RSA attacks. Let $n$ be an integer. This paper proposes two families of RSA-like encryption schemes: one employs the key equation $ed - k (p^n-1)(q^n-1) = 1$ for $n > 0$, while the other uses $ed - k [(p^n-1)(q^n-1)]/[(p-1)(q-1)] = 1$ for $n > 1$. Note that we remove the conventional assumption of primes having equal bit sizes. In this scenario, we show that regardless of the choice of $n$, continued fraction-based attacks can still recover the secret exponent. Additionally, this work fills a gap in the literature by establishing an equivalent of Wiener's attack when the primes do not have the same bit size.

Verifiable Timed Signatures (VTS) are cryptographic constructs that enable obtaining a signature at a specific time in the future and provide evidence that the signature is legitimate. This framework particularly finds utility in applications such as payment channel networks, multiparty signing operations, or multiparty computation, especially within blockchain architectures. Currently, VTS schemes are based on signature algorithms such as BLS signature, Schnorr signature, and ECDSA. These signature algorithms are considered insecure against quantum attacks due to the effect of Shor's Algorithm on the discrete logarithm problem. We present a new VTS scheme called VT-Dilithium based on CRYSTALS-Dilithium Digital Signature Algorithm that has been selected as NIST's quantum-resistant digital signature standard and is considered secure against both classical and quantum attacks. Integrating Dilithium into the VTS scheme is more challenging problem due to its complex mathematical operations (i.e. polynomial multiplications, rounding operations) and large module parameters such as polynomials, polynomial vectors, and matrices. This work aims to provide a comprehensive exposition of the VT-Dilithium scheme.

We present a key-recovery attack on a variant of the Seasign signature scheme presented by [Kim24], which attempts to avoid rejection sampling by presampling vectors $\mathbf{f}$ such that the $\mathbf{f}-\mathbf{e}$ is contained in an acceptable bound, where $\mathbf{e}$ is the secret key. We show that this choice leads to a bias of these vectors such that, in a small number of signatures, the secret key can either be completely recovered or its keyspace substantially reduced. In particular, on average, given $20$ signatures, with parameter set II of their paper, the attack reduces the private key to 128 possibilities

Privacy preserving systems often need to allow anonymity while requiring accountability. For anonymous clients, depending on application, this may mean banning/revoking their accounts, docking their reputation, or updating their state in some complex access control scheme. Frequently, these operations happen asynchronously when some violation, e.g., a forum post, is found well after the offending action occurred. Malicious clients, naturally, wish to evade this asynchronous negative feedback. Considering privacy-preserving analogues of modern access control and reputation schemes raises a more fundamental technical challenge with far broader applications: how do we allow multiple parties to interact with private state stored by an anonymous client while ensuring state integrity and supporting oblivious updates?

We propose zk-promises, a framework which supports Turing-complete state machines with arbitrary asynchronous callbacks. In zk-promises, client state is stored in a zk-object. Updates to the zk-object, represented as a cryptographic commitment to the new, modified object, require a zkSNARK that ensures integrity and atomicity while providing confidentiality. Clients can modify and prove their state by calling valid methods (e.g, to show they are authorized to post) and can give callbacks to third parties (e.g., to later hold them accountable). Through careful protocol design, we ensure clients who advance their state-machine are forced to ingest callbacks that are called by a third party.

zk-promises allows us to build a privacy-preserving account model. State that would normally be stored on a trusted server can be privately outsourced to the client while preserving the server's ability to update the account. To demonstrate the feasibility of our approach, we build an anonymous reputation system with better than state-of-the-art performance and features, supporting asynchronous reputation updates, banning, and reputation-dependent rate limiting to better protect against Sybil attacks.

Many applications rely on accumulators and authenticated dictionaries, from timestamping certificate transparency and memory checking to blockchains and privacy-preserving decentralized electronic money, while Merkle tree and its variants are efficient for arbitrary element membership proofs, non-membership proofs, i.e., universal accumulators, and key-based membership proofs may require trees up to 256 levels for 128 bits of security, assuming binary tree, which makes it inefficient in practice, particularly in the context of zero-knowledge proofs.

Building on the hardness of multi-collision we introduce a novel (non-)membership, optionally key-value, accumulator with up to 2x smaller tree depth while preserving the same security level, as well as multiple application-specific versions with even shallower trees, up to 6x smaller depth, that rely on the low-entropy source. Moreover, solving for special case of adversarial attacks we introduce key index variants which might be a stepping stone for an entropy-free accumulator.

Notably, unlike other constructions, this work, although may, doesn't depend on the dynamic depth of the tree which is simpler and more suitable for constant-size ZKP circuits, while ensuring a substantially smaller upper bound on depth.

Efficient in practice construction in the adversarial context, e.g. blockchain, where the tree manager doesn't need to be trusted, i.e., operations can be carried out by an untrusted party and verified by anyone, is the primary goal. Example instantiations are considered, where special treatment is given to the application of representing serial numbers, aka nullifiers. Nevertheless, the constructions are self-sufficient and can be used in other contexts, without blockchain and/or zero-knowledge proofs, including non-adversarial contexts.

Furthermore, our findings might be of independent interest for other use cases, such as hash tables, databases and other data structures.

In the multi-user with corruptions (muc) setting there are $n\geq 1$ users, and the goal is to prove that, even in the face of an adversary that adaptively corrupts users to expose their keys, un-corrupted users retain security. This can be considered for many primitives including signatures and encryption. Proofs of muc security, while possible, generally suffer a factor n loss in tightness, which can be large. This paper gives new proofs where this factor is reduced to the number c of corruptions, which in practice is much smaller than n. We refer to this as corruption-parametrized muc (cp-muc) security. We give a general result showing it for a class of games that we call local. We apply this to get cp-muc security for signature schemes (including ones in standards and in TLS 1.3) and some forms of public-key and symmetric encryption. Then we give dedicated cp-muc security proofs for some important schemes whose underlying games are not local, including the Hashed ElGamal and Fujisaki-Okamoto KEMs and authenticated key exchange. Finally, we give negative results to show optimality of our bounds.

We propose a new wide encryption (WE) mode of operation that satisfies robust authenticated encryption (RAE) and committing security with minimum ciphertext expansion. WE is attracting much attention in the last few years, and its advantage includes RAE security that provides robustness against wide range of misuses, combined with the encode-then-encipher (EtE) construction. Unfortunately, WE-based EtE does not provide good committing security, and there is a recent constant-time CMT-4 attack (Chen et al., ToSC 2023(4)). Improving CMT-4 security requires considerable ciphertext expansion, and the state-of-the-art scheme expands the ciphertext by s_rae + 2 s_cmt bits from an original message to achieve s_rae-bit RAE and s_cmt-bit CMT-4 security. Our new WE mode FFF addresses the issue by achieving s_rae-bit RAE and s_cmt-bit CMT-4 security only with max{s_cmt, s_rae} bits of ciphertext expansion. Our design is based on the committing concealer proposed by Bellare et al., and its extension to WE (cf. tag-based AE) while satisfying RAE security is the main technical innovation.

Lyubashevsky’s signature can be viewed as a lattice-based adapation of the Schnorr signature, with the core difference being the use of aborts during signature generation process. Since the proposal of Lyubashevsky’s signature, a number of other variants of Schnorr-type signatures with aborts have been proposed, both in lattice-based and code-based setting. In this paper, we examine the security of Schnorr-type signature schemes with aborts. We give a detailed analysis of when the expected value of the signature is correlated to the secret key, and when it is not. Our analysis shows that even when abort condition is employed, it is crucial to set the parameters carefully in order to defend against statistical attack. In particular, we recommend to set δ ≥ β (where δ, β are public parameters) as in this case we prove that the signature does not reveal any information about the secret key. On the other hand, if this condition is not satisfied, then some information about the secret key are leaked, making the scheme susceptible to statistical attacks. For completeness, we also analyze the security of Schnorr-type signatures without aborts. In particular, we present a detailed key recovery attack via statistical method on the EagleSign signature, which is one of the submission to the NIST call for Additional PQC Signature. Moreover, we give a formula for determining the number of required signatures to successfully launch the statistical attack.

We introduce Compass, a semantic search system over encrypted data that offers high accuracy, comparable to state-of-the-art plaintext search algorithms while protecting data, queries and search results from a fully compromised server. Compass also enables privacy-preserving RAG where both the RAG database and the query are protected. Compass's search index contributes a novel way to traverse the search graph in Hierarchical Navigable Small Worlds (HNSW), a top performing vector nearest neighbor search, using Oblivious RAM, a cryptographic primitive with strong security guarantees. Our techniques, Directional Neighbor Filtering, Speculative Greedy Search and HNSW-tailored Path ORAM ensure that Compass achieves user-perceived latencies of few seconds and is orders of magnitude faster than a baseline for encrypted embeddings search.

We give the first construction of non-interactive zero-knowledge (NIZK) arguments from post-quantum assumptions other than Learning with Errors. In particular, we achieve NIZK under the polynomial hardness of the Learning Parity with Noise (LPN) assumption, and the exponential hardness of solving random under-determined multivariate quadratic equations (MQ). We also construct NIZK satisfying statistical zero-knowledge assuming a new variant of LPN, Dense-Sparse LPN, introduced by Dao and Jain (CRYPTO 2024), together with exponentially-hard MQ.

The main technical ingredient of our construction is an extremely natural (but only in hindsight!) construction of correlation-intractable (CI) hash functions from MQ, for a NIZK-friendly sub-class of constant-degree polynomials that we call concatenated constant-degree polynomials. Under exponential security, this hash function also satisfies the stronger notion of approximate CI for concatenated constant-degree polynomials. The NIZK construction then follows from a prior blueprint of Brakerski-Koppula-Mour (CRYPTO 2020). In addition, we show how to construct (approximate) CI hashing for degree-$d$ functions from the (exponential) hardness of solving random degree-$d$ equations, a natural generalization of MQ. To realize NIZK with statistical zero-knowledge, we design a lossy public-key encryption scheme with approximate linear decryption and inverse-polynomial decryption error from Dense-Sparse LPN. These constructions may be of independent interest.

Our work therefore gives a new way to leverage MQ with uniformly random equations, which has found little cryptographic applications to date. Indeed, most applications in the context of encryption and signature schemes make use of structured variants of MQ, where the polynomials are not truly random but posses a hidden planted structure. We believe that the MQ assumption may plausibly find future use in the designing other advanced proof systems.

The Extended Greatest Common Divisor (XGCD) computation is a critical component in various cryptographic applications and algorithms, including both pre- and post-quantum cryptosystems. In addition to computing the greatest common divisor (GCD) of two integers, the XGCD also produces Bezout coefficients $b_a$ and $b_b$ which satisfy $\mathrm{GCD}(a,b) = a\times b_a + b\times b_b$. In particular, computing the XGCD for large integers is of significant interest. Most recently, XGCD computation between 6,479-bit integers is required for solving $N$-th degree Truncated polynomial Ring Unit (NTRU) trapdoors in Falcon, a National Institute of Standards and Technology (NIST)-selected Post-Quantum digital signature scheme. To this point, existing literature has primarily focused on exploring software-based implementations for XGCD. The few existing high-performance hardware architectures require significant hardware resources and may not be desirable for practical usage, and the lightweight architectures suffer from poor performance. To fill the research gap, this work proposes a novel FPGA-based scalablE and Lightweight accelerator for large Integer XGCD (FELIX). First, a new algorithm suitable for scalable and lightweight computation of XGCD is proposed. Next, a hardware accelerator (FELIX) is presented, including both constant- and variable-time versions. Finally, a thorough evaluation is carried out to showcase the efficiency of the proposed FELIX. In certain configurations, FELIX involves 81% less equivalent area-time product (eATP) than the state-of-the-art design for 1,024-bit integers, and achieves a 95% reduction in latency over the software for 6,479-bit integers (Falcon parameter set) with reasonable resource usage. Overall, the proposed FELIX is highly efficient, scalable, lightweight, and suitable for very large integer computation, making it the first such XGCD accelerator in the literature (to the best of our knowledge).

The Legendre sequence of an integer $x$ modulo a prime $p$ with respect to offsets $\vec a = (a_1, \dots, a_\ell)$ is the string of Legendre symbols $(\frac{x+a_1}{p}), \dots, (\frac{x+a_\ell}{p})$. Under the quadratic-residuosity assumption, we show that the function that maps the pair $(x,p)$ to the Legendre sequence of $x$ modulo $p$, with respect to public random offsets $\vec a$, is a pseudorandom generator. This answers an open question of Damgård (CRYPTO 1988), up to the choice of the offsets $\vec a$.

Considering side-channel analysis (SCA) security for cryptographic devices, the mitigation of electromagnetic leakage and electromagnetic interference (EMI) between modules poses significant challenges. This paper presents a comprehensive review and deep analysis of the utilization of EMI shielding materials, devised for reliability purposes and standards such as EMI/EMC, as a countermeasure to enhance EM-SCA security. We survey the current landscape of EMI-shields materials, including conductive polymers, metal-foams, carbon-based materials, and meta-materials, evaluating their effectiveness in attenuating emissions and preventing information-leakage, a task done with security-centric metrics for such materials for the first time. Through a systematic examination of existing literature, experimental studies and a construction of fully-simulatable EM environment in ANSYS-solver, we identify key factors influencing the performance of EMI-shield materials, such as shielding-effectiveness (SE), bandwidth, thickness, and material properties, on security characteristics. We devise a connection between SE and cryptographic-SNR, and we demonstrate from real hardware measurements how and in what conditions can such materials provide very high security levels. By synthesizing insights from multidisciplinary research domains, this paper aims to provide valuable two-way benefit and guidance for researchers, engineers, and practitioners in the design and deployment of robust side-channel security measures leveraging EMI-shields, already in utilization devised by reliability standards.

Recently, an emerging branch of research in the field of fully homomorphic encryption (FHE) attracts growing attention, where optimizations are carried out in developing fast and efficient homomorphic logic circuits. While existing works have pointed out that compound homomorphic gates can be constructed without incurring significant computational overheads, the exact theory and mechanism of homomorphic gate design have not yet been explored. In this work, we propose AutoHoG, an automated procedure for the generation of compound gates over FHE. We show that by formalizing the gate generation procedure, we can adopt a match-and-replace strategy to significantly improve the evaluation speed of logic circuits over FHE. In the experiment, we first show the effectiveness of AutoHoG through a set of benchmark gates. We then apply AutoHoG to optimize common Boolean tasks, including adders, multipliers, the ISCAS’85 benchmark circuits, and the ISCAS’89 benchmark circuits. We show that for various circuit benchmarks, we can achieve up to 5.7x reduction in computational latency when compared to the state-of-the-art implementations of logic circuits using conventional gates.