International Association
for Cryptologic Research

We’re looking for a PhD student (4 years, full position) to work with us on the NWO project EPOCHAL (Extensions of POst-quantum CryptograpHy and ALgorithms). The last years have seen a lot of focus on building encryption systems and signature schemes that are secure against quantum attacks. This involves analyzing them in a security model where the attacker has a quantum computer. While the replacement schemes are not perfect fits in terms of speed or size, the community has reached some workable solutions. However, there is a lot of usage of public-key cryptography that goes beyond these core building blocks – many real-world solutions need to establish related public keys, which involves using the structure of elliptic curves, or to verify the validity of public keys. Currently deployed protocols often inherently use properties of the pre-quantum building blocks. For those, we do not (yet) have matching or sufficiently efficient replacements among systems that can resist attacks with quantum computers. The goal of this project is to develop exactly such solutions and to analyze their security. The PhD position is embedded in the Coding Theory and Cryptology group in the Discrete Mathematics (DM) cluster with Tanja Lange as main supervisor. We work closely with the Applied and Provable Security group (also part of DM) and Kathrin Hövelmanns is part of the project team. Please note that applications must be received via the TU/e application site https://jobs.tue.nl/en/vacancy/phd-on-postquantum-cryptography-1101449.html and the "APPLY NOW" button on that page. The page also has some general information about the employment conditions.

Closing date for applications:

Contact: Tanja Lange

More information: https://jobs.tue.nl/en/vacancy/phd-on-postquantum-cryptography-1101449.html

We are looking for a candidate with proven scientific expertise in the field of Security & Privacy. The following areas are of particular interest:

• AI Safety and Security
• Privacy
• Cryptography
• Formal Methods for Security
• System Security
• Digital Identities
• Usable Security

The successful candidate will cover one of these fields or any other field in Security & Privacy that complements the existing strengths in the department. The professorship will be part of the Institute of Applied Information Processing and Communications, which is an internationally highly visible research environment with more than 60 researchers in information security. It has been active in this field for more than 30 years and performs research in the following four areas: Cryptology & Privacy, Formal Methods, System Security, and Secure Applications.

The new professor will build an internationally visible group, and will be an engaged teacher in the Computer Science programs at the Bachelor’s, Master’s, and PhD level, and will actively participate in academic self-administration. At Graz University of Technology, undergraduate courses are taught in German or English and graduate courses are taught in English.

Closing date for applications:

Contact: Please send your application via this link:

https://jobs.tugraz.at/en/jobs/2ce67149-7069-cc79-2bdc-65b9f66b2c32/apply?preview=true

For further questions, please contact Stefan Mangard (stefan.mangard@iaik.tugraz.at).

More information: https://jobs.tugraz.at/de/jobs/c9dc1465-5885-6706-d049-6650453181d0

We study the linear code equivalence problem (LEP) for linear $[n,k]$-codes over finite fields $\mathbb{F}_q$. Recently, Chou, Persichetti and Santini gave an elegant heuristic algorithm that solves LEP over large finite fields (with $q = \Omega(n)$) in time $2^{\frac{1}{2}\operatorname{H}\left(\frac{k}{n}\right)n}$, where $\operatorname{H}(\cdot)$ denotes the binary entropy function. However, for small finite fields, their algorithm can be significantly slower. In particular, for fields of constant size $q = \mathcal{O}(1)$, its runtime increases by an exponential factor $2^{\Theta(n)}$. We present an improved and provably correct version of their algorithm, which achieves the desired runtime of $2^{\frac{1}{2}\operatorname{H}\left(\frac{k}{n}\right)n}$ for all finite fields of size $q \geq 7$. For a wide range of parameters, this improves over the runtime of all previously known algorithms by an exponential factor.

The recent VOLE-based interactive zero-knowledge (VOLE-ZK) protocols along with non-interactive zero-knowledge (NIZK) proofs based on MPC-in-the-Head (MPCitH) and VOLE-in-the-Head (VOLEitH) extensively utilize the commitment schemes, which adopt a circular correlation robust (CCR) hash function as the core primitive. Nevertheless, the state-of-the-art CCR hash construction by Guo et al. (S&P'20), building from random permutations, can only provide 128-bit security, when it is instantiated from AES. This brings about a gap between AES-based CCR hash function and high security (beyond 128-bit security). In this paper, we fill this gap by constructing a new CCR hash function from AES, supporting three security levels (i.e., 128, 192 and 256). Using the AES-based CCR hash function, we present an all-but-one vector commitment (AVC) scheme, which constitutes a computationally intensive part of the NIZK proofs from MPCitH and VOLEitH, where these NIZK proofs can in turn be transformed into the promising post-quantum signature candidates. Furthermore, we obtain an efficient VOLE-ZK protocol with security levels higher than 128 from the CCR hash function. Our benchmark results show that the AES-based CCR hash function has a comparable performance with CCR hash functions based on Rijndael with larger block sizes, which is not standardized and has a limited application range. In the AVC context, the expensive commitment component instantiated with our AES-based CCR hash function improves the running time by a factor of $7 \sim 30 \times$, compared to the SHA3-based instantiation used in the recent post-quantum signature algorithm FAEST.

\scarf, an ultra low-latency tweakable block cipher, is the first cipher designed for cache randomization. The block cipher design is significantly different from the other common tweakable block ciphers; with a block size of only 10 bits, and yet the input key size is a whopping $240$ bits. Notably, the majority of the round key in its round function is absorbed into the data path through AND operations, rather than the typical XOR operations. In this paper, we present a key-recovery attack on a round-reduced version of SCARF with 4 + 4 rounds under the single-tweak setting. Our attack is essentially a Meet-in-the-Middle (MitM) attack, where the matching phase is represented by a system of linear equations. Unlike the cryptanalysis conducted by the designers, our attack is effective under both security requirements they have outlined. The data complexity of our attack is $2^{10}$ plaintexts, with a time complexity of approximately $2^{60.63}$ 4-round of SCARF encryptions. It is important to note that our attack does not threaten the overall security of SCARF.

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.