International Association
for Cryptologic Research

A privately constrained pseudorandom function (pCPRF) is a PRF with the additional property that one can derive a constrained key that allows evaluating the PRF only on inputs satisfying a constraint predicate $C$, without revealing $C$ itself or leaking information about the PRF’s output on inputs that do not satisfy the constraint.

Existing privately constrained PRFs face significant limitations: either (1) they rely on assumptions known to imply fully-homomorphic encryption or indistinguishability obfuscation, (2) they support only highly restricted classes of constraints—for instance, no known group-based pCPRF even supports the simple class of puncturing constraints (where the constrained key permits evaluation on all but one point while hiding the punctured point), or (3) they are limited to polynomial-size input domains. A long-standing open question has been whether one can construct a privately constrained PRF from group-based assumptions for more expressive classes of constraints. In this work, we present a pCPRF based on the decisional composite residuosity (DCR) assumption that supports a highly expressive class of predicates, namely constraints with polynomially bounded Waring rank, which notably includes puncturing.

From a technical perspective, our work follows the general template of Couteau, Meyer, Passelègue, and Riahinia (Eurocrypt'23), who constructed a pCPRF from group-based homomorphic secret-sharing but were limited to inner-product constraints in the constraint-hiding setting. Leveraging novel techniques for computing with distributed discrete logarithms (DDLog), we enable the non-interactive authentication of powers of linear combinations of shares of some value. This, in turn, allows us to express constraints with polynomially bounded Waring rank.

Our construction is single-key, selectively secure, and supports an exponential-size domain.

The Messaging Layer Security protocol MLS is standardized in IETF’s RFC 9420 and allows a group of parties to securely establish and evolve group keys even if the servers are malicious. Its core mechanism is based on the TreeKEM protocol, but has gained many additional features and modifications during the development of the MLS standard. Over the last years, several partial security analyses have appeared of incomplete drafts of the protocol. One of the major additions to the TreeKEM design in MLS RFC 9420 (the final version of the standard) are the external operations, i.e., external commits and proposals, which interact deeply with the core TreeKEM protocol. These operations have not been considered in any previous security analysis, leaving their impact on the protocol’s overall security unclear.

In this work, we formalize ETK: External-Operations TreeKEM that includes external commits and proposals. We develop a corresponding ideal functionality $F_\mathit{ECGKA}$ and prove that ETK indeed realizes $F_\mathit{ECGKA}$.

Our work is the first cryptographic analysis that considers both the final changes to the standard’s version of TreeKEM as well as external proposals and external commits. Compared to previous works that considered MLS draft versions, our ETK protocol is by far the closest to the final MLS RFC 9420 standard. Our analysis implies that the core of MLS’s TreeKEM variant as defined in RFC 9420 is an ETK protocol that realizes $F_\mathit{ECGKA}$, when used with an SUF-CMA secure signature scheme, such as the IETF variant of Ed25519. We show that contrary to previous claims, MLS does not realize $F_\mathit{ECGKA}$ [Crypto2022] when used with signature schemes that only guarantee EUF-CMA, such as ECDSA.

Moreover, we show that the security of the protocol could be further strengthened by adding a functionality to insert PSKs, allowing another form of healing, and give a corresponding construction ETK-PSK and ideal functionality $F_{\mathit{ECGKA}^\mathit{PSK}}$ .

Network agnostic protocols (Blum, Katz, Loss TCC `19) are consensus or MPC protocols that strike a balance between purely synchronous and asynchronous protocols. Given thresholds $t_a,t_s$ that satisfy $t_a
In this work, we introduce a new paradigm to construct network agnostic consensus (and MPC) that, for the first time overcome this barrier. Using this new design pattern we first present simple protocols for reliable broadcast (RB) and binary agreement (BA) that are responsive when no more than $t_a$ parties are corrupted and run in expected constant time regardless of the network conditions. We then extend our results to asynchronous common subset (ACS) and MPC. Notably, our approach reverses the order of the synchronous and asynchronous path by designing protocols that are first and foremost asynchronous and only fall back to the synchronous execution path when more than $t_a$ parties are corrupted.

The Linear Code Equivalence ($\mathsf{LCE}$) problem asks, for two given linear codes $\mathcal{C}, \mathcal{C}'$, to find a monomial $\mathbf{Q}$ mapping $\mathcal{C}$ into $\mathcal{C}'$. Algorithms solving $\mathsf{LCE}$ crucially rely on a (heuristic) subroutine, which recovers the secret monomial from $\Omega(\log n)$ pairs of codewords $(\mathbf{v}_i, \mathbf{w}_i)\in \mathcal{C} \times \mathcal{C}'$ satisfying $\mathbf{w}_i = \mathbf{v}_i\mathbf{Q}$. We greatly improve on this known bound by giving a constructive (heuristic) algorithm that recovers the secret monomial from any \emph{two} pairs of such codewords for any $q\geq 23$. We then show that this reduction in the number of required pairs enables the design of a more efficient algorithm for solving the $\mathsf{LCE}$ problem. Our asymptotic analysis shows that this algorithm outperforms previous approaches for a wide range of parameters, including all parameters proposed across the literature. Furthermore, our concrete analysis reveals significant bit security reductions for suggested parameters. Most notably, in the context of the LESS signature scheme, a second-round contender in the ongoing NIST standardization effort for post-quantum secure digital signatures, we obtain bit security reductions of up to 24 bits.

Isogeny-based cryptography relies its security on the hardness of the supersingular isogeny problem: finding an isogeny between two supersingular curves defined over a quadratic field.

The Delfs-Galbraith algorithm is the most efficient procedure for solving the supersingular isogeny problem with a time complexity of $\tilde{\mathcal{O}}(p^{1/2})$ operations. The bottleneck of the Delfs-Galbraith algorithm is the so-called subfield curve search (i.e., finding an isogenous supersingular elliptic curve defined over the base field), which determines the time complexity.

Given that, for efficiency, most recent isogeny-based constructions propose using finite fields with field characteristics equal to $p = 2^a \cdot f - 1$ for some positive integers $a$ and $f$. This work focuses on primes of that particular form, and it presents two new algorithms for finding subfield curves with a time complexity of $\mathcal{O}(p^{1/2})$ operations and a memory complexity polynomial in $\log_2{p}$. Such algorithms exploit the existence of large torsion-$2^a$ points and extend the subfield root detection algorithm of Santos, Costello, and Shi (Crypto 2022) to our case study. In addition, it is worth highlighting that these algorithms easily extend to primes of the form $p =2^a \cdot f + 1$ and $p = \ell^a \cdot f - 1$ with $\ell$ being a small integer.

This study also examines the usage of radical $3$-isogenies with the proposed extended subfield root detection algorithm. In this context, the results indicate that the radical $3$-isogeny approach is competitive compared with the state-of-the-art algorithms.

Time-lock puzzles are cryptographic primitives that guarantee to the generator that the puzzle cannot be solved in less than $\mathcal{T}$ sequential computation steps. They have recently found numerous applications, e.g., in fair contract signing and seal-bid auctions. However, solvers have no a priori guarantee about the solution they will reveal, e.g., about its ``usefulness'' within a certain application scenario. In this work, we propose verifiable time-lock puzzles (VTLPs) that address this by having the generator publish a succinct proof that the solution satisfies certain properties (without revealing anything else about it). Hence solvers are now motivated to ``commit'' resources into solving the puzzle. We propose VTLPs that support proving arbitrary NP relations $\mathcal{R}$ about the puzzle solution. At a technical level, to overcome the performance hurdles of the ``naive'' approach of simply solving the puzzle within a SNARK that also checks $\mathcal{R}$, our scheme combines the ``classic'' RSA time-lock puzzle of Rivest, Shamir, and Wagner, with novel building blocks for ``offloading'' expensive modular group exponentiations and multiplications from the SNARK circuit. We then propose a second VTLP specifically for checking RSA-based signatures and verifiable random functions (VRFs). Our second scheme does not rely on a SNARK and can have several applications, e.g., in the context of distributed randomness generation. Along the road, we propose new constant-size proofs for modular exponent relations over hidden-order groups that may be of independent interest. Finally, we experimentally evaluate the performance of our schemes and report the findings and comparisons with prior approaches.

It is well-known that any single-server PIR scheme with sublinear communication necessitates public-key cryptography. Several recent studies, which we collectively refer to as lightweight PIR, demonstrate that this limitation can be circumvented to some extent. However, all such schemes require at least $O(n^{1/2})$ communication per-query, where $n$ is the size of the database. Indeed, the celebrated result provided by Ishai et al. (Crypto '24) implies that, with solely symmetric-key cryptography, achieving per-query communication below $O(n^{1/2})$ necessitates more than $O(n^{1/2})$ client storage. Whether this barrier can be overcome with limited use of public-key cryptography remains an open question. In this paper, we tackle this question by presenting the first lightweight single-server PIR scheme with $O_\lambda(n^{1/3})$ communication while allowing arbitrary (non-zero) client storage.

The School of Mathematical and Statistical Sciences is recruiting for one Post Doctoral Scholar position. This is a 12 month research position. The appointment is initially for one year August 15, 2025 - August 14, 2026 and may be renewed for one additional year, contingent upon funding and performance. The start date may be deferred until January 1, 2026. The targeted research area is Post-Quantum Cryptography. The postdoctoral scholar will collaborate closely with the Savannah River National Laboratory SRNL to address critical security and cryptographic challenges. Candidates with strong potential for collaboration with faculty in the Division of Mathematics will receive the highest consideration.

Closing date for applications:

Contact: Ryann Cartor, rcartor@clemson.edu

More information: https://apply.interfolio.com/163536

The School of Computer Science and Electronic Engineering is seeking to recruit a full-time Senior Lecturer in Cyber Security to expand our team of dynamic and highly skilled security researchers. It is part of a strategic investment in cyber security, alongside a Lecturer position in cyber security.

The Surrey Centre for Cyber Security (SCCS), within the School, has an international reputation in cyber security and resilience research excellence in applied and post-quantum cryptography, security verification and analysis, security and privacy, distributed systems, and networked systems. SCCS is recognised by the National Cyber Security Centre as an Academic Centre of Excellence for Cyber Security Research and Education. Its research was also a core contributor to Surrey’s 7th position in the UK for REF2021 outputs within Computer Science. Surrey was recognised as Cyber University of the Year 2023 at the National Cyber Awards.

Surrey has an internationally leading track record in security and communications research and runs the newly formed Doctoral Training centre in Future Open Secure and Resilient Communications in collaboration with Queens University Belfast with funding for 50 PhD students.

This post sits within SCCS and this role encourages applications in the areas of systems security, web security, cyber-physical systems, cyber resilience, ethical hacking, machine learning for security, with application in various domains with preference in communications, space, banking, and autonomous systems. Candidates with practical security experience and skills will complement our strengths in cryptography and formal verification.

This post will support the growing cohort of students across all undergraduate Computer Science programmes and support students in the highly successful MSc in Cyber Security.

Closing date for applications:

Contact: Professor Steve Schneider (s.schneider@surrey.ac.uk)

More information: https://jobs.surrey.ac.uk/vacancy.aspx?ref=009325

The School of Computer Science and Electronic Engineering is seeking to recruit a full-time Lecturer in Cyber Security to expand our team of dynamic and highly skilled security researchers. It is part of a strategic investment in cyber security alongside a Senior Lecturer position in cyber security.

The Surrey Centre for Cyber Security (SCCS), within the School, has an international reputation in cyber security and resilience research excellence in applied and post-quantum cryptography, security verification and analysis, security and privacy, distributed systems, and networked systems. SCCS is recognised by the National Cyber Security Centre as an Academic Centre of Excellence for Cyber Security Research and Education. Its research was also a core contributor to Surrey’s 7th position in the UK for REF2021 outputs within Computer Science. Surrey was recognised as Cyber University of the Year 2023 at the National Cyber Awards.

Surrey has an international leading track record in security and communications research and runs the newly formed Doctoral Training centre in Future Open Secure and Resilient Communications in collaboration with Queens University Belfast with funding for 50 PhD students.

This post sits within SCCS and this role encourages applications in the areas of systems security, web security, cyber-physical systems, cyber resilience, ethical hacking, machine learning for security, with application in various domains with preference in communications, space, banking, and autonomous systems. Candidates with practical security experience and skills will complement our strengths in cryptography and formal verification.

This post will support the growing cohort of students across all undergraduate Computer Science programmes and support students in the highly successful MSc in Cyber Security.

Closing date for applications:

Contact: Professor Steve Schneider

More information: https://jobs.surrey.ac.uk/vacancy.aspx?ref=009425

Adva Network Security is a German-based company and was funded by leading security experts to help operators of critical infrastructure, government agencies and enterprises security-harden their networks. We are currently looking for a highly motivated Cryptography/Security Engineer (PhD track) (M/F/D) to join our Advanced Technology team in Munich. The position will allow to focus on research and innovation in cryptography with a high relevance for our cryptographic products. In cooperation with a University, we’ll support to pursue a PhD degree in the field.

Responsibilities
• Research and develop innovative and secure solutions for key-exchange, encryption and authentication in optical networks.
• Analyze the security of cryptographic algorithms and protocols.
• Collaborate with the research community in national and international projects.
• Demonstrate technical excellence at conferences or workshops.

Requirements
• Master’s degree in Electrical Engineering, Computer Science, Mathematics or a related field.
• Good knowledge of cryptographic concepts and information security principles.
• Solid programming skills in (C and Python preferred).
• Good presentation, communication, and scientific writing skills.
• Fluent in oral and written English, fluency in German is a plus.

Apply here: https://adtran.wd3.myworkdayjobs.com/en-US/ANS/job/Berlin-ANS-Germany/Engineer-Advanced-Technology--M-F-D----PhD_R003928

Closing date for applications:

Contact: Dr. Helmut Griesser [Helmut'Griesser(a)advasecurity'com]

More information: https://adtran.wd3.myworkdayjobs.com/en-US/ANS/job/Berlin-ANS-Germany/Engineer-Advanced-Technology--M-F-D----PhD_R003928

We establish the following theorem: Let $\mathsf{O}_0, \mathsf{O}_1, \mathsf{R}$ be random functions from $\{0,1\}^n$ to $\{0,1\}^n$, $n \in \mathbb{N}$. For all polynomial-query-bounded distinguishers $\mathsf{D}$ making at most $q=\mathsf{poly}(n)$ queries to each oracle, there exists a poly-time oracle simulator $\mathsf{Sim}^{(\cdot)}$ and a constant $c>0$ such that the probability is negligible, that is $$\left|\Pr\left[{\mathsf{D}^{(\mathsf{O}_0+\mathsf{O}_1),(\mathsf{O}_0,\mathsf{O}_1,\mathsf{O}_0^{-1},\mathsf{O}_1^{-1})}(1^n)=1}\right]-\Pr\left[{\mathsf{D}^{\mathsf{R},\mathsf{Sim}^\mathsf{R}}(1^n)=1}\right]\right| = negl(n).$$

The ChaCha20-Poly1305 AEAD scheme is widely used as an alternative for AES-GCM on platforms without AES hardware instructions. Although recent analysis by Degabriele et al. shows that ChaCha20-Poly1305 provides adequate security in the conventional multiuser model, the construction is totally broken when a single nonce is repeated – a real-word scenario that can occur due to faulty implementations or the desire to use random nonces.

We present a new nonce-misuse resistant and key-committing authenticated encryption scheme, called ChaCha20-Poly1305-PSIV, that is based on carefully combining the ChaCha20-Poly1305 building blocks into the NSIV paradigm proposed by Peyrin and Seurin (CRYPTO 2016) without performance loss. We analyze the security of the underlying mode PSIV in the multi-user faulty-nonce model assuming that the underlying permutation is ideal, and prove its key-committing security in the cmt-1 model. Rust and C implementations are provided, and benchmarks confirm that performance is comparable to the ChaCha20-Poly1305 implementation in libsodium.

In terms of security and efficiency (without hardware support), our proposal compares favorably to AES-GCM-SIV. Since we reuse the ChaCha20-Poly1305 building blocks, we expect ChaCha20-Poly1305-PSIV to benefit from existing analysis and to be easy to deploy in practice.

We introduce a general, low-cost, low-power statistical test for transactions in transaction protocols with small anonymity set authentication (TPSASAs), such as Monero. The test classifies transactions as ad hoc (spontaneously constructed to spend a deterministically selected key) or self-churned (constructed from a probability distribution very close to that of the default wallet software, and with the same sender and receiver). The test is a uniformly most powerful (UMP) likelihood ratio tests (LRT) from the Neyman-Pearson Lemma, and makes no assumptions about user behavior. We extend these tests to expoit prior information about user behavior. We discuss test parameterization, as well as how anonymity set cardinality and user behavior impact test performance. We also describe a maximum-likelihood de-anonymization attack on Monero based on our test.

Quantum cryptography allows to achieve security goals which are unobtainable using classical cryptography alone: it offers the promise of everlasting privacy. Thatis, an adversary trying to attack a protocol must succeed during the run of the protocol. After the protocol has terminated, security holds unconditionally. In this work, we initiate the study of a new model which we call the quantum decoherence model (QDM). In a nutshell, this model captures adversaries that are computationally bounded during the run of a protocol (and some time after), but become computationally unbounded long after the protocol terminates. Importantly, once the adversary becomes computationally unbounded, he can only remember a bounded number of qubits from before the computational bound was lifted. We provide a variant of the Universal Composability framework which captures the new notion of quantum decoherence and augment it with quantum random oracles. As our main contribution, we construct a non-interactive commitment scheme achieving unconditional and statistical security against malicious senders and everlasting security against malicious receivers under our new security notion. Such commitments imply general secure multiparty computation with everlasting security. Finally, we show that our core technique can be applied to a broader spectrum of problems. We show that it gives rise to everlasting public key encryption and OT in the QDM. Finally, we also consider the weaker notion of incompressible encryption in the setting of quantum decoherence, and show that post-quantum IND-CPA secure public key encryption is sufficient to realize this notion without resorting to random oracles. At the technical core of our constructions is a new, conceptually simple yet powerful reverse entropic uncertainty relation.

In this paper, we demonstrate that Ethereum's current proof-of-stake (PoS) consensus mechanism poses a significant threat to decentralisation. Our research focuses on the manipulability of distributed randomness beacons (DRBs) in leader selection. Specifically, we show that RANDAO - Ethereum's DRB - is seriously vulnerable to manipulations in its current form. For example, if a lucrative slot is foreseen, there is a risk that staking entities may temporarily collude to control $33\%$ of the validators, enabling them to execute a series of RANDAO manipulation attacks that secure the target slot with a $99.5\%$ success rate. The effectiveness of our method stems from the fact that we work with a significantly richer model of the possible attacks compared to previous works. Our manipulative strategies work by missing blocks from the canonical chain - either by withholding blocks in the adversary's own slots or by forking out blocks proposed by others. We argue that while PoS can pave the path in the future for blockchains, Ethereum's current DRB implementation has to be replaced with a more secure mechanism.

The Log Structured Merge (LSM) Tree is a popular choice for key-value stores that focus on optimized write throughput while maintaining performant, production-ready read latencies. To optimize read performance, LSM stores rely on a probabilistic data structure called the Bloom Filter (BF). In this paper, we focus on adversarial workloads that lead to a sharp degradation in read performance by impacting the accuracy of BFs used within the LSM store. Our evaluation shows up to $800\%$ increase in the read latency of lookups for popular LSM stores. We define adversarial models and security definitions for LSM stores. We implement adversary resilience into two popular LSM stores, LevelDB and RocksDB. We use our implementations to demonstrate how performance degradation under adversarial workloads can be mitigated.

We present the first protocol for efficient Fuzzy Private Set Intersection (PSI) that achieves linear communication complexity, does not depend on restrictive assumptions on the distribution of party inputs, and abstains from inefficient fully homomorphic encryption. Specifically, our protocol enables two parties to compute all pairs of elements from their respective sets that are within a given Hamming distance, without constraints on how these sets are structured.

Our key insight is that securely computing the (threshold) Hamming distance between two inputs can be reduced to securely computing their inner product. Leveraging this reduction, we construct a Fuzzy PSI protocol using recent techniques for inner-product predicate encryption. To enable the use of predicate encryption in our setting, we establish that these predicate encryption schemes satisfy a weak notion of simulation security and demonstrate how their internal key derivation can be efficiently distributed without a trusted third party.

As a result, our Fuzzy PSI on top of predicate encryption features not only asymptotically optimal linear communication complexity but is also concretely practical.

Fully homomorphic encryption (FHE) enables the computation of arbitrary circuits over encrypted data. A widespread application of FHE is a simple two-party computation (2PC) protocol, where the server evaluates a circuit over the client's encrypted data and its private inputs. However, while the security of FHE guarantees that the client's data is protected from the server, there is no inherent support for the privacy of the server's input and the circuit.

One effective solution to this problem is an additional algorithm for FHE called sanitization, introduced by Ducas and Stehlé (Eurocrypt 2016). Roughly speaking, a sanitization algorithm removes any meaningful information contained in the ciphertext, including previous evaluations of circuits. Following their definition, several constructions for sanitization have been proposed, particularly for TFHE. However, all of these methods were impractical, requiring several bootstrappings or an excessive amount of randomized evaluations.

In this work, we construct a novel sanitization algorithm for TFHE that overcomes these issues. Our method only adds two lightweight randomization steps to the original TFHE bootstrapping, without any modifications to the core algorithms. As a result, our algorithm achieves sanitization with a single bootstrapping and minimal randomization, bringing sanitization closer to practicality.

To empirically evaluate the efficiency of our method, we provide concrete benchmark results based on our proof-of-concept implementation. Our algorithm sanitizes a single TFHE ciphertext in 35.88 ms, which is only 3.4% (1.18 ms) slower than the original TFHE bootstrapping with the same parameters. When directly compared to previous works, our method achieves a speedup by a factor of 4.82 to 209.03.

The cryptographic scheme and NIST candidate HAWK makes use of a particular module lattice and relies for its security on the assumption that finding module lattice isomorphisms (module LIP) is hard. To support this assumption, we compute the mass of the HAWK lattice, which gives a lower bound on the number of isometry classes of module lattices which cannot be distinguished from the HAWK lattice by an easily computed invariant called the genus. This number turns out to be so large that an attack based on the genus alone seems infeasible.