We give a new framework for constructing post-quantum protocols based on graded monoidal actions. An essential difference between the graded monoidal action framework and the cryptographic group action framework is that our higher-rank problems give rise to infinite structures, where elements do not admit inverses, while cryptographic group actions are finite by definition. Nevertheless, we show that the hard problems for cryptographic group actions reduces to the corresponding family of...

This paper considers the problem of building blind signatures in pairing-free groups. We provide the first three-move blind signature which is provably one-more unforgeable, in the random-oracle model, under the minimal assumption that the discrete logarithm (DL) problem is hard. Our construction in fact achieves one-more strong unforgeability, and also supports partial blindness. Blindness is statistical, also in the ROM. Our construction makes black-box use of the underlying group and does...

We construct the first (conjectured) post-quantum Time Lock Puzzle (TLP) from isogenies. Our construction avoids setup/preprocessing and achieves non-trivial efficiency, where puzzle generation runs in time $\sqrt{T}$ . We prove security in the quantum random oracle model (QROM) under a new conjecture about the sequentiality of isogeny pushforward computations, for which we provide a thorough justification. The only other (conjectured) post-quantum TLP constructions rely on heavy...

Secure messaging runs on commodity devices that can be subverted by malware or supply-chain attacks. Reverse firewalls address this threat by interposing a user-side device that mediates the communication of a potentially compromised end-point. Recently, Dodis et, al. (CRYPTO 2025) proposed a reverse firewall design for protecting Signal, including its Diffie-Hellman based X3DH handshake, against subversion. With Signal and other platforms now migrating to post-quantum cryptography, however,...

This note reports an attack scenario for CSIDH that does not appear to have been considered in the literature. A subverted device of Alice can leak a shared curve between Alice and Bob through Alice's public curves in later CSIDH sessions. The attack adapts the Young--Yung kleptographic attack from classical Diffie--Hellman to CSIDH using the Goldreich--Levin theorem and rejection sampling. We prove that a CSIDH public curve $[\mathfrak a]\star E_0$ remains computationally indistinguishable...

In a multi-instance problem, the adversary is given $n$ independent problem instances and succeeds if it solves at least $k$ of them. We study the generic hardness of a broad class of multi-instance problems over prime-order groups, including multi-instance Computational Diffie-Hellman (CDH), Square Diffie-Hellman (SDH), Inverse Diffie-Hellman (IDH), and Linear Kernel Diffie-Hellman (LKDH). As expected, we show that, in generic groups, solving multi-instance CDH and SDH is as hard as...

Batch decryption allows an authority to release a short key that enables public decryption of a selected batch of ciphertexts. Motivated by encrypted mempools, we study this capability through two constructions with different authorization semantics and assumptions. First, we provide a simple and compact epochless construction in an RSA group based on Fiat's Batch RSA [CRYPTO'89]. Its batch-decryption hint is just one group element, and its keys and ciphertexts have size independent of...

We construct the first Batched Threshold Encryption scheme with a \emph{transparent} setup where public parameters are \emph{independent} of the batch size. As a result batches of arbitrary sizes can be decrypted, without imposing an a priori fixed bound. We prove security under a constant size assumption -- the decisional bilinear square Diffie--Hellman assumption. Setup is just a distributed key generation protocol to sample secret shares of a random value. Ciphertexts consist of two...

Inspired by the recent polynomial-time adaptive attacks on threshold Schnorr signatures, we contextualize the Low-Dimensional Vector Representation (LDVR) assumption and its impact on relevant threshold Schnorr signature schemes. Our analysis focuses in large part on FROST, a widely deployed threshold Schnorr signature scheme. However, our analysis is applicable to any relevant threshold Schnorr signature scheme, such as Lindell's three-round threshold Schnorr protocol. We show that for...

The Groth16 verification equation has a compact algebraic description, yet garbling its Boolean implementation can require tens of gigabytes. We show how to garble this computation using native elliptic-curve group operations. Motivated by proof verification in trust-minimized Bitcoin bridges, we construct a projective partial garbling scheme for conditional disclosure on invalid Groth16 proofs. For a fixed verification key and public statement, evaluation reveals a garbler-held secret when...

We construct homomorphic secret sharing (HSS) and pseudorandom correlation functions (PCFs) in a general group-theoretic framework, with security based on the subgroup indistinguishability (SgI) assumption introduced by Brakerski and Goldwasser (Crypto 2010). Under certain instantiations of this framework, SgI corresponds to decisional composite residuosity (DCR), but other instantiations are possible as well. Hence, our work expands the set of assumptions that imply HSS and PCFs. Our...

Garbled circuits are fundamental in modern cryptography and secure two- or multi-party computation. For real-world programs that are naturally expressed in the Random-Access Machine (RAM) model, garbled RAM is the RAM counterpart of garbled circuits: they avoid the cost of compiling the entire program into a circuit, with communication complexity serving as the primary efficiency metric. We study the setting in which the RAM program is public, while the input data and memory contents remain...

Are private set intersection (PSI) protocols ready for the post-quantum future? We focus on the PSI protocol of Rosulek \& Trieu (``RT21'', ACM CCS 2021), which is the current state-of-the-art for PSI on small sets (less than a thousand items). The RT21 protocol presents some fundamental barriers to post-quantum security. First, although it is written in terms of an arbitrary KEM, it requires certain properties of Diffie-Hellman KEM that simply are not satisfied by any post-quantum...

The Signal protocol is used by billions of users daily and recognized as the gold standard for end-to-end encrypted messaging. Its initial handshake protocol X3DH uses XEdDSA to sign its semi-static key and allows parties to derive a session key asynchronously. The protocol is implemented over Curve25519, relying on the assumed 128-bit hardness for solving Discrete Logarithms (DL). Previous non-tight reductions incur a large loss in the number of sessions, and the resulting concrete security...

Threshold signatures enable a set of $n$ parties to jointly generate signatures under a single public key such that any subset of at least $t+1$ parties can produce a valid signature, whereas any coalition of at most $t$ parties cannot. They constitute a fundamental primitive for distributed trust and are widely deployed in systems such as certification authorities, blockchains, and multiparty wallets. Modern applications require strong security guarantees under realistic adversarial models,...

We present an efficient attack on a knot-based Diffie--Hellman key exchange proposed by Sconza and Wildi. In the proposal, the two parties exchange oriented knots, combine them under connected sum to obtain a common knot, and derive the shared secret by evaluating a finite type invariant of degree $m$ on it. We show the scheme is insecure for every choice of finite type invariant. The shared secret can be computed from the public transcript at roughly three times the cost of running the...

In recent years, threshold encryption has gained a lot of interest, particularly due to its potential use in encrypted mempools in blockchains. Standard security models allow the adversary to corrupt parties either statically (i.e., fixed at the onset of the game) or adaptively (i.e., via an oracle one-by-one, depending on keys and ciphertexts). In this work, we observe that neither of these models captures the case in which a party decides to become corrupted based on secret...

With the arrival of scalable quantum computers, classical key exchange protocols like RSA, elliptic-curve and finite-field Diffie-Hellman are vulnerable to harvest-now-decrypt-later attacks. Quantum key distribution offers information-theoretic security but is sensitive to channel noise, loss, and distance, while post-quantum cryptography provides quantum resistance on conventional hardware at the cost of larger keys and a dependence on hardware computational strength. Existing hybrid...

A $(k,n)$-robust combiner for a primitive $\mathcal{P}$ combines $n$ candidate instantiations of $\mathcal{P}$ into a single scheme that remains secure as long as at least $k$ of them remain secure. Robust combiners have been extensively studied for primitives such as hash functions, public-key encryption, and oblivious transfer, but much less is known in the setting of cryptographic groups. In this work, we initiate the study of robust combiners for cryptographic groups in Maurer's generic...

The Signal Protocol’s Double Ratchet and X3DH/PQXDH handshakes give in-transit messages forward secrecy and post-compromise security: compromising a session key does not expose past traffic, and the protocol self-heals after a fresh Diffie–Hellman step. Encrypted backups, by contrast, are commonly protected by a single static secret, a “Backup Recovery Key” generated once and held constant until manually rotated. We show, with an explicit attack, that this baseline design provably fails even...

Post-quantum cryptography (PQC) standardisation reached a pivotal milestone in August 2024 with the release of NIST FIPS 203 (ML-KEM) and FIPS 204 (ML-DSA), yet the vast majority of deployed public-key infrastructure continues to rely on RSA-2048 and Elliptic Curve Diffie-Hellman (ECDH), both vulnerable to Shor's algorithm on a cryptographically relevant quantum computer. The Harvest Now, Decrypt Later (HNDL) threat renders this risk operationally present: adversaries may archive ciphertext...

Batched identity-based encryption (batched IBE), introduced by Agarwal, Fernando, and Pinkas (CRYPTO 2025), enables a key authority to issue a single succinct key that decrypts an entire batch of ciphertexts. However, existing batched encryption protocols support only identity-based access control and do not accommodate expressive attribute-based policies. We are the first to introduce Batched Attribute-Based Encryption (B-ABE), a generalization of batched encryption to the attribute-based...

To initiate migration to post-quantum cryptography (PQC), it is necessary to identify whether deployed software uses quantum-vulnerable (QV) public-key cryptographic schemes such as RSA, ECDSA, and Diffie–Hellman (DH). However, many ELF executables are distributed without source code, making it necessary to directly screen executable binaries for QV candidates. A prior tool, Quantum-vulnerable Executable Detection (QED), provides high precision but incurs substantial analysis cost, whereas...

A Password-Authenticated Key Exchange (PAKE) protocol allows two parties to jointly establish a cryptographic session key, in the "password-only" setting where the only information shared in advance is a low-entropy password. In recent years, the One-encryption EKE with 2-round Feistel cipher (OEKE-2F) protocol, a compiler from Key Encapsulation Mechanism (KEM) to PAKE, has received much attention, for the following reasons: (1) When instantiated with the Diffie–Hellman KEM, it is the most...

We initiate the study of multi-authority traitor tracing (MA-TT), a decentralized variant of traitor tracing in which tracing capabilities are distributed across multiple independent authorities rather than concentrated in a single trusted entity. Ciphertexts are associated with tracing policies over a collection of authorities, specifying which subsets of authorities are authorized to jointly accuse a user of contributing to a pirate decoder. This enables fine-grained control over tracing...

Two post-quantum upgrades to TLS 1.3 are being standardized in parallel: a hybrid key exchange (already deployed) that runs an elliptic-curve Diffie-Hellman exchange alongside ML-KEM, and a standalone mode that uses ML-KEM on its own. The Internet-Draft draft-usama-tls-risks-of-mlkem points out that the machine-checked symbolic proofs of TLS 1.3 rely on the commutativity of Diffie-Hellman, which ML-KEM does not share: a key encapsulation mechanism is asymmetric, one endpoint generating a key...

Publicly verifiable secret sharing (PVSS) is a fundamental primitive in threshold cryptography that allows a dealer to share a secret $S$ among a set of $n$ parties via a publicly verifiable transcript. Any subset of $t+1$ parties can then use their individual shares to reconstruct the full secret $S$, whereas $t$ or fewer shares give no information about $S$. As such, the secret $S$ remains hidden from an adversary that corrupts up to $t$ parties. Recently, Bacho and Loss (CCS 2023) gave...

Authenticated Private Information Retrieval (Authenticated PIR) allows the client to retrieve the desired database entry without revealing any information about the query, while safely aborting if malicious behavior by the server is detected (presented in USENIX '23). However, two key challenges remain: existing single-server authenticated PIR schemes with sublinear online communication have not yet been clearly and fully implemented; incremental updates to the digest introduce unnecessary...

Can a relevant cryptographic primitive, when instantiated over the NIST P-256 elliptic curve, achieve a bit-security level exceeding $128$ bits? Yes. We formally prove that the well-known password-authenticated key exchange protocol $\mathsf{EKE}$, introduced by Bellovin and Merritt (S&P 1992), achieves a generic security level of $128+\frac{1}{2}\log_2(N)$ bits, where $N$ denotes the size of the password space. To prove this result, we introduce and develop a new approach for showing that...

Updatable public-key encryption (UPKE) is a cryptographic primitive that was proposed for secure messaging to provide forward secrecy in public-key settings. It extends standard public-key encryption with a key-update mechanism that lets anyone update a receiver’s public key and issue a corresponding token for updating the secret key. Unlike traditional forward secrecy where all past messages should remain secure after a key leakage, UPKEs guarantee security only as long as at least one...

We present PQES-AKE, a novel two-party authenticated key exchange (AKE) protocol built upon the Post-Quantum Encryption and Signcryption Scheme (PQES) introduced by Kara et al. The protocol achieves mutual authentication, session key secrecy, and forward secrecy in a post-quantum adversarial model. The central design principle of PQES-AKE is the concealment of ephemeral Diffie-Hellman (DH) keys within affine masks derived from randomness generated internally by the PQES signcryption...

Although automated symbolic protocol verification has proven valuable and effective, current approaches begin to reach their limits: While small protocols can be analyzed automatically, the most complex case studies often require substantial expert time and resources. There have been many attempts to solve this problem by compositional verification, but they rely on unrealistic protocol assumptions and do not support real-world security properties like Forward Secrecy. In this work, we...

Dwork and Naor (FOCS 2000) showed a generic transformation to construct a ZAP (a two-round public-coin witness-indistinguishable proof) from any non-interactive zero-knowledge (NIZK) proof with statistical soundness in the common random string model. In recent years, a number of works have shown how to construct NIZK arguments in the common random string model from a broad range of assumptions including decisional Diffie-Hellman (DDH), learning with errors (LWE), or combinations of multiple...

Batched threshold encryption allows any $t$-out-of-$N$ parties in a committee to decrypt a batch of $B$ ciphertexts using sub-linear $o(NB)$ communication, while ensuring that any subset of $<t$ colluding parties learns no information about the underlying plaintext. Our first result is a simple batched threshold encryption scheme that is censorship resistant, avoids epoch restrictions, and achieves quasi-linear $O(B\log B)$ decryption complexity in the batch size $B$. Our scheme has the...

Several modern applications, such as Signal or WireGuard, use efficient Noise-like implicit authentication key exchanges that require only a small number of exponentiations and two interactions. These protocols have been proven to be secure under the 'strong Diffie–Hellman' (SDH) assumption in the random oracle model (ROM). At ESORICS 2021, Ramacher, Slamanig and Weninger presented an extension to the implicit authenticated key exchange security model, which enables strong privacy...

Threshold blind signatures (TBS) allow any set of issuers whose size exceeds a predefined threshold to jointly generate a signature without learning the message. Adaptively secure TBS schemes allow the adversary to corrupt issuers at any point during protocol execution, capturing realistic threat models. Adaptive security methods rely on the algebraic group model (AGM) in security proofs to extract the discrete logarithm of the blinded protocol message. However, as a strong idealized...

Basically, public-key searchable encryption schemes require a linear search time with respect to the total number of ciphertexts. Xu, Wu, Wang, Susilo, Domingo-Ferrer, and Jin (IEEE Transactions on Information Forensics and Security, 2015) introduced Searchable Public-Key Ciphertexts with Hidden Structure (SPCHS). In SPCHS, ciphertexts associated with the same keyword are linked through a hidden structure that can be revealed using a trapdoor. This enables efficient extraction of matching...

CSIDH (Commutative Supersingular Isogeny Diffie--Hellman) is a class-group-based key-exchange protocol operated on supersingular elliptic curves, which, at the time of its proposal, exhibited several attractive selling points such as non-interactivity. Unfortunately, CSIDH is vulnerable to the sub-exponentiation attack--Kuperberg's algorithm, thereby requiring large parameters to ensure security. A recent work based on oriented elliptic curves with large discriminants, proposed by Houben,...

(Bi-Directional) Proxy Re-Encryption ($\mathsf{PRE}$) is a public-key encryption scheme that allows a proxy, holding a re-encryption key from $i$ to $j$, to transform a ciphertext intended for $i$ into one intended for $j$. $\mathsf{PRE}$ has numerous applications, including secure data sharing and cloud computing. However, most existing $\mathsf{PRE}$ schemes experience significant security degradation when adversaries are allowed to adaptively corrupt re-encryption or secret keys. Prior to...

This paper presents the first blind signature scheme in a pairing-free group with the following properties: (1) the signing protocol consists of only three moves; (2) the proof of one-more unforgeability relies solely on the Decisional Diffie-Hellman (DDH) assumption in the Random Oracle Model (ROM); and (3) the construction makes only black-box use of the underlying group. This resolves a major open problem in the area, as all prior pairing-free blind signatures either additionally relied...

The rapid progress of quantum computing threatens widely deployed public-key cryptosystems such as RSA and Diffie–Hellman, accelerating the transition toward post-quantum cryptography (PQC). During this migration, hybrid key encapsulation mechanisms (KEMs) that combine classical and post-quantum primitives are strongly recommended by standardization bodies and cybersecurity agencies. However, existing hybrid designs mainly focus on combining post-quantum KEMs with Diffie–Hellman–style...

In this work, we propose Hyperelliptic Gluing Isogeny Diffie– Hellman (HGIDH), a key-exchange protocol built from gluing isogenies between the product of two supersingular elliptic curves and the Jacobian of a genus-2 hyperelliptic curve. The protocol leverages the Frey–Kani correspondence, using maximal isotropic subgroups of (E1 × E2)[N] to construct principally polarized abelian surfaces. Private keys are encoded as four scalars defining a non-cyclic, two-dimensional kernel,...

Graphs $D(n, q)$ and their connected components $CD(n, q)$ were defined 30 years ago. We observe shortly their applications to Extremal Graph Theory, Spectral Graph Theory, Algebraic Graph Theory, Symmetric Cryptography and Theory of Low Density Parity Check Codes. We introduce several new algorithms of Noncommutative Cryptography based on this graphs of large girth, In particular we propose modification of Diffie-Hellman protocol in terms of semigroup of walks of even length on the...

This survey article provides an overview of the Semigroup Action Problem (SAP) as a pivotal generalization of the Discrete Logarithm Problem (DLP), tracing its theoretical evolution from foundational algebraic cryptography in the early 2000s to its application in the National Institute of Standards and Technology (NIST) Post-Quantum Cryptography (PQC) standardization process. We examine the mathematical framework of semigroup actions, contrasting them with classical group-theoretic...

We present two constructions of short signature schemes based on the polynomial hardness of decisional Diffie Hellman. Our simplest scheme guarantees selective security (i.e. the adversary has to commit to the forged message ahead of time) while the second one realizes full fledged existential unforgeability. Remarkably, our schemes can be implemented over standard prime order groups (no pairings needed) and can be proven secure without resorting to the random oracle heuristic.

This paper formally specifies and analyzes the CK hybrid key encapsulation mechanism (KEM) construction from the IRTF CFRG’s recent draft on hybrid (post-quantum/traditional) KEMs CK combines two KEMs using a PRF to produce a hybrid KEM. Unlike the QSF framework of Barbosa et al., which combines an IND-CCA KEM with a nominal group (Diffie-Hellman-style), CK combines a C2PRI-secure post-quantum-secure KEM with an IND-CCA traditionlly-secure KEM constructed from an IND-CCA2 public key...

Motivated by new attack vectors against key encapsulation mechanisms (KEMs), a framework for binding security has recently been introduced and has since been widely used for analyzing post-quantum schemes. While the migration to such post-quantum schemes has already started, classical KEMs remain relevant due to the use of hybrid schemes, which combine post-quantum and classical KEMs. However, KEMs based on classical schemes have not been analyzed with respect to their binding security yet....

A number of recent works propose watermarking the outputs of large language models (LLMs) but fail to describe who is authorized to watermark the text or check for a watermark. To resolve these problems, we propose interactive watermarking schemes. Our technique leverages the fact that, for many of the cases in which detecting synthetic text is useful, the detector is able to control some part of the prompt that is passed to the LLM. In other words, we propose poisoning the prompt,...

An asymmetric Password-Authenticated Key Exchange (aPAKE) protocol allows a client, who holds a raw password, and a server, who holds a one-way mapping of the password, to jointly establish a cryptographically strong session key, without an authenticated channel. The standard security definition for aPAKE is in the Universal Composability (UC) framework. Despite its great potential of being used in practice, existing aPAKE protocols are either not round-optimal, computationally inefficient,...

We introduce an optimization to the Tamarin prover that reduces its search space. The optimization applies to protocol models that use equational theories with cancellative operators, for example, when modelling Diffie-Hellman groups or bilinear pairings. We prove the optimization's soundness and evaluate its performance.

Idealized models such as the Random Oracle Model and the Generic Group Model underpin much of modern provable security. The Algebraic Group Model (AGM) of Fuchsbauer, Kiltz, and Loss (CRYPTO 2018) attempts to bridge the gap to the standard model by forcing adversaries to justify every new group element via a linear representation in its inputs, and it was leveraged in many follow-up works. Lipmaa, Parisella, and Siim (TCC 2023) strengthened this framework to the AGM with Oblivious Sampling...

Post-quantum migration must balance two risks: future quantum breaks of classical cryptography and residual uncertainty in newly standardized post-quantum cryptography (PQC). Hybrid Key Encapsulation Mechanisms (KEMs) hedge by combining a classical and a PQC component. Prior work shows that optimized combiners may omit large public inputs from the final key-derivation step, but only if the derived key remains bound to the ciphertext transcript and, in multi-target settings, to the intended...

This short paper formally specifies and analyzes the UG hybrid KEM construction from the IRTF CFRG’s recent draft on hybrid (post-quantum/traditional) KEMs. The UG construction is an optimized hybrid of a Diffie-Hellman (DH)-based KEM in a nominal group and a generic IND-CCA KEM. The main optimization is that the group elements derived in the DH-based KEM are “inlined” in the key derivation, saving unnecessary hashing. We perform two security analyses of the UG construction: one shows UG is...

The devastating attacks against SIDH (Supersingular Isogeny Diffie-Hellman) have popularised the practical use of isogenies of dimension $2$ and above in cryptography. Though this effort was primarily focused on dimension 2, $4$-dimensional isogenies, have been used in several isogeny-based cryptographic constructions including SQIsignHD, SQIPrime, (qt-)Pegasis and MIKE. These isogenies are also interesting for number theoretic applications related to higher dimensional isogeny graphs. In...

$\textit{Proxy re-encryption}$ (PRE) is an essential cryptographic primitive for managing secure access delegation in outsourced data environments, particularly public cloud systems. PRE is a public key encryption (PKE) with two additional algorithms - (i) re-encryption key generation by which a proxy server generates a re-encryption key; (ii) re-encryption algorithm by which the proxy server can transform the ciphertext under the delegator's public key to a ciphertext under the delegatee's...

Password-Authenticated Public Key Encryption (PAPKE) enables secure encryption using only a shared, human-memorable password—eliminating the need for trusted intermediaries or pre-established infrastructure. It allows a sender to encrypt a message for a recipient, using the recipient's password-authenticated public key and a shared password, while provably resisting man-in-the-middle and offline dictionary attacks. PAPKE's support for reusable password-authenticated public keys makes it...

Subversion-resilient Authenticated key-exchange (AKE) aims to achieve the guarantees of secure AKE even in the presence of an adversary that has tampered with parts of the protocol's implementation. One way to achieve subversion-resilient AKE is the use of Reverse Firewalls (RFs), an untrusted third-party that can restore security. Recent work [18] highlights the challenges of designing RFs for practical secure channel-establishment. This paper extends existing RF-based...

End-to-end encryption (E2EE) is the foundation of modern secure messaging, with the Signal protocol as the de facto standard in applications such as Signal, WhatsApp, Facebook Messenger and Google Messages. At the same time, the deployment of E2EE has led to growing pressure from authorities to decrypt user traffic under law enforcement. This raises a critical question: if an adversary can routinely decrypt Signal messages (for example via a mandated access or a leaked key), can users still...

A message authentication code (MAC) ensures authenticity and integrity in symmetric-key settings. The Carter–Wegman–Shoup (CWS) paradigm establishes that MACs for arbitrary-length messages can be built in a black-box way using a single call to a pseudorandom function (PRF) on a random input. More than a decade ago, Dodis, Kiltz, Pietrzak, and Wichs left open whether weak pseudorandom functions (wPRFs) would suffice in this construction. This work establishes tight upper and lower bounds...

Threshold encryption distributes decryption capability across $n$ parties such that any $t$ of them can jointly decrypt a ciphertext, while smaller coalitions learn nothing. However, once $t$ or more parties collude, traditional threshold schemes provide no accountability: a coalition of $t$ or more parties can pool its keys into a pirate decoder that enables unrestricted decryption, all without any risk of being exposed. To address this, Boneh, Partap, and Rotem [CRYPTO '24] introduced...

Password-based Authenticated Key Exchange (${\sf PAKE}$) is a widely acknowledged, promising security mechanism for establishing secure communication between devices. It enables two parties to mutually authenticate each other over insecure networks and generate a session key using a low-entropy password. However, the existing $\mathsf{PAKE}$ protocols encounter significant challenges concerning both security and efficiency in the context of the \textit{Internet of Things} (IoT). In...

The rapid advancements in quantum computing pose a significant threat to widely used cryptographic standards such as RSA and Elliptic-Curve Diffie-Hellman (ECDH), which are fundamental to securing digital communications and protecting sensitive data worldwide. The increasing feasibility of "harvest now, decrypt later" strategies where adversaries collect encrypted data today with the intent of decrypting it once quantum computing reaches sufficient maturity underscores the urgency of...

Secure communication in the Internet of Things (IoT) requires lightweight protocols that scale across unicast, multicast, and broadcast settings. Existing solutions typically depend on centralized gateways, which introduce single points of failure and scalability limitations. We propose TreeCast, a distributed group key establishment protocol that organizes devices into a binary tree of hashed Diffie–Hellman secrets, which naturally unifies unicast, multicast, and broadcast in a single...

We initiate the study of memory efficiency in proving the security of authenticated key exchange (AKE) protocols: We first revise the security model for AKE protocols in order to prove their security in a memory-efficient manner without compromising its capability of capturing usual attacks. We formally show that security in our model implies {security in} previous ones, and thus our model captures the same security as before. After that we propose a generic construction of AKE from key...

Threshold signatures are an important tool for trust distribution, and preserving the interface of standardized signatures, such as Schnorr signatures, is crucial for their adoption. In practice, latency dominates end-to-end signing time, so minimizing the number of interaction rounds is critical. Ideally, this is achieved under minimal assumptions and with adaptive security, where the adversary can corrupt signers on-the-fly during the protocol. While Schnorr signatures are proven...

The generic group model (GGM) is fundamental for evaluating the feasibility and limitations of group-based cryptosystems. Two prominent versions of the GGM exist in the literature: Shoup's GGM and Maurer's GGM. Zhandry (CRYPTO 2022) points out inherent limitations in Maurer's GGM by demonstrating that several textbook cryptographic primitives, which are provably secure in Shoup's GGM, cannot be proven secure in Maurer's model. In this work, we further investigate Shoup's GGM and identify...

We present Golden, a non-interactive Distributed Key Generation (DKG) protocol. Golden achieves public verifiability in a lightweight, non-interactive manner, outputting Shamir secret shares of a field element $\mathsf{sk} \in \mathbb{Z}_p$ to all participants, and a public key $\mathsf{PK}= g^{\mathsf{sk}}$ that is a discrete-logarithm commitment to sk. Golden avoids the overhead of public-key encryption schemes like ElGamal, Pallier, or class groups by using a novel building block: a...

We study error-detection and error-correction codes for computationally bounded adversarial channels. We consider seeded codes where the polynomial-time encoding and decoding procedures share a public random seed, but are otherwise deterministic. An adversarial channel gets this seed and can perform arbitrary polynomial-time computation to adaptively select both the message to be encoded and a bounded number of errors to be added to the resulting codeword. The goal is to detect or correct...

Privacy Pass is an anonymous authentication protocol which was initially designed by Davidson et al. (PETS’18) to reduce the number of CAPTCHAs that TOR users must solve. It issues single-use authentication tokens with anonymous and unlinkable redemption guarantees. The issuer and verifier of the protocol share a symmetric key, and tokens are privately verifiable. The protocol has sparked interest from both academia and industry, which led to an Internet Engineering Task Force (IETF)...

Signal's handshake protocol non-interactively generates a shared key between two parties for secure communication. The underlying protocol X3DH, on which the post-quantum hybrid successor, PQXDH, builds, computes three to four individual Diffie-Hellman (DH) keys by combining the long-term identity keys and the ephemeral secrets of the two parties. Each of these DH operations serves a different purpose, either to authenticate the derived key or to provide forward secrecy. We present here...

We present Zyga, a pairing-based zero-knowledge proof system optimized for privacy-preserving DeFi applications. Our main contribution is an enhancement of existing zkSNARK constructions that enables dynamic public input substitution during verification while maintaining privacy of witness components through one-sided encoding. The one-sided encoding aspect favors practical deployment constraints on Solana and Ethereum where G2 scalar multiplications are computationally expensive. Zyga...

Blind signatures are a versatile cryptographic primitive with many applications, especially in privacy-preserving technologies. Threshold blind signature schemes (TBS) enhance blind signatures with a signing procedure distributed among up to n signers to reduce the risk attached to the compromise of the secret key. So far, TBS constructions over groups rely on strong assumptions, e.g., the algebraic group model (AGM) or interactive assumptions. In this work, we propose two TBS based on the...

WireGuard is a VPN based on the Noise protocol, known for its high performance, small code base, and unique security features. Recently, Hülsing et al. (IEEE S&P'21) presented post-quantum (PQ) WireGuard, replacing the Diffie-Hellman (DH) key exchange underlying the Noise protocol with key-encapsulation mechanisms (KEMs). Since WireGuard requires the handshake message to fit in one UDP packet of size roughly 1200 B, they combined Classic McEliece and a modified variant of Saber. However, as...

We suggest post quantum secure protocol based on pseudorandom walk on infinite q-regular forest D(q) where q = 2^m, m > 1. Correspondents share positive integer n, pseudorandom tuple from (Fq) ^n and two pseudorandom input words in the alphabet F_q of length O(1). They use the group of cubic multivariate transformations of the vector space of points of D(q) induced by walks on the forest of even length as the platform for the implementation of modified Twisted Diffie-Hellman protocol of ...

In Diffie–Hellman key exchange, the commutativity of power operations is instrumental in the agreement of keys. Viewing commutativity as a law in abelian groups, we propose Diffie–Hellman key exchange in the group action framework (Brassard–Yung, Crypto'90; Ji–Qiao–Song–Yun, TCC'19), for actions of non-abelian groups with laws. The security of this protocol is shown, following Fischlin, Günther, Schmidt, and Warinschi (IEEE S&P'16), based on a pseudorandom group action assumption. A concrete...

Abstract. Designated verifier signature allows a signer to designate a verifier who can verify the signature. A strong designated verifier signature (SDVS) enhances privacy by ensuring that the signature itself does not leak information about the signer’s identity to anyone other than the designated verifier. Non-delegatability is a property, as it prevents the signer’s ability to generate valid signatures from being delegated to others. This property is important for SDVS applications such...

Message authentication (MA) in the Short Authenticated String (SAS) model, defined by Vaudenay, allows for authenticating arbitrary messages sent over an insecure channel as long as the sender can also transmit to the receiver a short authenticated message, e.g. d = 20 bits. The flagship application of SAS-MA is Authenticated Key Exchange (AKE) in the SAS model (SAS-AKE), which allows parties communicating over insecure network to establish a secure channel without prior source of trust...

We revisit decentralized multi‑authority attribute‑based encryption (MA‑ABE) through the lens of fully adaptive security -- the most realistic setting in which an adversary can decide on‑the‑fly which users and which attribute authorities to corrupt. Previous constructions either tolerated only static authority corruption or relied on highly complex “dual system with dual‑subsystems” proof technique that inflated ciphertexts and keys. Our first contribution is a streamlined security...

Currently, the only tightly secure inner-product functional encryption (IPFE) schemes in the multi-user and multi-challenge setting are the IPFE scheme due to Tomida (Asiacrypt 2019) and its derivatives. However, these tightly secure schemes have large ciphertext expansion and are all based on the matrix decisional Diffie-Hellman (DDH) assumption. To improve the efficiency of tightly secure IPFE and enrich the diversity of its underlying assumptions, we construct a set of tightly secure...

We present a practical, non-interactive threshold decryption scheme. It can be proven CCA secure with respect to adaptive corruptions in the random oracle model under the decisional Diffie-Hellman assumption. Our scheme, called TDH2a, is a minor modification on the TDH2 scheme presented by Shoup and Gennaro at Eurocrypt 1998, which was proven secure against static corruptions under the same assumptions. The design and analysis of TDH2a are based on a straightforward extension of the...

Since supersingular isogeny Diffie-Hellman (SIDH) was broken by a polynomial-time attack, several countermeasures were proposed. Among them, terSIDH has been highlighted for its high performance, yet it exposes a side-channel vulnerability. The total isogeny degree depends on the private key, causing variation in isogeny computation times. This dependency makes terSIDH susceptible to timing attacks. The ratio between the worst- and the best-case execution times of terSIDH was about 32.67...

An aggregate signature scheme allows a user to take $N$ signatures from $N$ users and aggregate them into a single short signature. One approach to aggregate signatures uses general-purpose tools like indistinguishability obfuscation or batch arguments for NP. These techniques are general, but lead to schemes with very high concrete overhead. On the practical end, the seminal work of Boneh, Gentry, Lynn, and Shacham (EUROCRYPT 2003) gives a simple and practical scheme, but in the random...

Making 2-party computation scale up to big datasets is a long-cherished dream of our community. More than a decade ago, a line of work has implemented and optimized interactive RAM-model 2-party computation (2PC), achieving somewhat reasonable concrete performance on large datasets, but unfortunately suffering from $\widetilde{O}(T)$ roundtrips for a $T$-time computation. Garbled RAM promises to compress the number of roundtrips to $2$, and encouragingly, a line of recent work has designed...

Threshold decryption schemes allow a group of decryptors, each holding a private key share, to jointly decrypt ciphertexts. Over the years, numerous threshold decryption schemes have been proposed for applications such as secure data storage, internet auctions, and voting, and recently as a tool to protect against miner-extractable value attacks in blockchain. Despite the importance and popularity of threshold decryption, many natural and practical threshold decryption schemes have only been...

Oblivious Pseudorandom Functions (OPRFs) are fundamental cryptographic primitives essential for privacy-enhancing technologies such as private set intersection, oblivious keyword search, and password-based authentication protocols. We present the first fully adaptive, partially oblivious threshold pseudorandom function that supports proactive key refresh and provides composable security under the One-More Gap Diffie-Hellman assumption in the random oracle model. Our construction is secure...

Randomness is a fundamental requirement in cryptographic systems, enabling secure encryption, commitments, and zero-knowledge proofs. However, real-world randomness sources often suffer from weaknesses that adversaries can exploit, leading to significant security vulnerabilities. While deterministic randomness extraction from a single min-entropy source is impossible, two-source extractors provide a robust solution by generating nearly uniform randomness from two independent weak sources....

We introduce the \(Inverse\ Discrete\ Logarithm\ Problem\) (iDLP) framework, which inverts traditional discrete logarithm assumptions by making the exponent public but deliberately non-invertible modulo the group order, while hiding the base. This creates a many-to-one algebraic mapping that is computationally infeasible under both classical and quantum attack models. Within this framework, we define three post-quantum cryptographic primitives: Inverse Discrete Diffie–Hellman (IDDH),...

Cascader, a novel key-exchange protocol based on an iterative multiplicative recurrence over a finite field, is introduced. In contrast to standard methods, e.g., traditional Diffie–Hellman and ECC, it replaces exponentiation and scalar multiplication with layered products, achieving commutativity and deterministic pseudorandom behavior.

Ateniese et al. (CRYPTO 2019/JoC 2021) introduced a cryptographic primitive which they call matchmaking encryption (ME), and Identity-based ME (IB-ME) is its identity-based variant. IB-ME supports an equality matching where a sender (encryptor) indicates a receiver's (decryptor's) identity (rcv) in addition to their own ID ($\sigma$), and a receiver indicates a sender's identity (snd) in addition to the own identity ($\rho$). A ciphertext is decrypted if $(\sigma,\rho)=$(snd,rcv). In this...

We introduce a novel Public Key Encryption with Equality Test supporting Flexible Authorization scheme offering User-Level, Ciphertext-Level, and User-Specific-Ciphertext-Level authorizations. Notably, our construction achieves security under the Decisional Diffie-Hellman assumption with a tight reduction, whereas the existing works are either not tightly secure or rely heavily on the random oracles. By relying solely on the standard DDH assumption, our scheme offers practical implementation...

PQ-WireGuard is a post-quantum variant of WireGuard Virtual Private Network (VPN), where Diffie-Hellman-based key exchange is replaced by post-quantum Key Encapsulation Mechanisms-based key exchange. In this paper, we first conduct a thorough formal analysis of PQ-WireGuard's original design, in which we point out and fix a number of weaknesses. This leads us to an improved construction PQ-WireGuard*. Secondly, we propose and formally analyze a new protocol, based on both WireGuard...

Gao et al. (IEEE Internet of Things Journal 2024) proposed public-key inverted-index keyword search with designated tester as an extension of public key encryption with keyword search (PEKS). In their scheme, a server (a tester) has a secret key and uses the key for running the search algorithm due to the designated tester setting. They proved that no information of keyword is revealed from trapdoors under the decisional Diffie-Hellman (DDH) assumption. However, they also employed a...

We introduce a novel technique for verifying Schnorr signatures using fast endomorphisms. Traditionally, fast endomorphisms over prime field curves are used to decompose a scalar into two scalars of half of the size. This work shows that the context of the verification of signatures allows for the decomposition into three scalars of a third of the size. We apply our technique to three scenarios: verification of a single Schnorr signature, batch verification, and verification of BLS...

An oblivious pseudorandom function (OPRF) is an interactive protocol between a client and server, where the client aims to evaluate a keyed pseudorandom function for a key held by the server, without revealing its input. OPRFs are a versatile tool for enhancing privacy, inciting extensive research and standardization efforts in this area. The round-efficient 2Hash-Diffie-Hellman OPRF is widely deployed, but unfortunately, it is prone to quantum attacks. The search for post-quantum...

A reduction showing that the hardness of the discrete logarithm ($\mathsf{DL}$) assumption implies the hardness of the computational Diffie-Hellman ($\mathsf{CDH}$) assumption in groups of order $p$, where $p - 1$ is smooth, was first presented by den Boer [Crypto, 88].} We also consider groups of prime order $p$, where $p - 1$ is somewhat smooth (say, every prime $q$ that divides $p - 1$ is less than $2^{100}$). Several practically relevant groups satisfy this condition. 1. ...

The Signal protocol is the most widely deployed end-to-end-encrypted messaging protocol. Its initial handshake protocol X3DH allows parties to asynchronously derive a shared session key without the need to be online simultaneously, while providing implicit authentication, forward secrecy, and a form of offline deniability. The X3DH protocol has been extensively studied in the cryptographic literature and is acclaimed for its strong "maximum-exposure" security guarantees, hedging against...

We introduce and analyze a novel class of binary operations on finite-dimensional vector spaces over a field K, defined by second-order multilinear expressions with linear shifts. These operations generate polynomials whose degree increases linearly with each iterated application, while the number of distinct monomials grows combinatorially. We demonstrate that, despite being non-associative and non-commutative in general, these operations exhibit power associativity and internal...

CVRFs are PRFs that unify the properties of verifiable and constrained PRFs. Since they were introduced concurrently by Fuchsbauer and Chandran-Raghuraman-Vinayagamurthy in 2014, it has been an open problem to construct CVRFs without using heavy machinery such as multilinear maps, obfuscation or functional encryption. We solve this problem by constructing a prefix-constrained verifiable PRF that does not rely on the aforementioned assumptions. Essentially, our construction is a verifiable...

Forward-secure public key encryption (FS-PKE) is a key-evolving public-key paradigm that ensures the confidentiality of past encryptions even if the secret key is compromised at some later point in time. However, existing FS-PKE schemes are considerably complex and less efficient compared to standard public-key encryption. Updatable public-key encryption (UPKE), introduced by Jost et al. (Eurocrypt 2019), was designed to achieve forward security in secure group messaging while maintaining...

Threshold signatures are one of the most important cryptographic primitives in distributed systems. Of particular interest is the threshold Schnorr signature, a pairing-free signature with efficient verification, compatible with standardized EdDSA (non-threshold) signature. However, most threshold Schnorr signatures have only been proven secure against a static adversary, which has to declare its corruptions before the protocol execution. Many existing adaptively secure constructions require...