Ordered multi-signatures allow multiple signers to sign a common message sequentially, and anyone to verify the signing order of signers with a public-key list. Recently, Baum et al. (PKC 2025) proposed an ordered multi-signature scheme over a pairing-free group by modifying the multi-signature scheme MuSig2 by Nick et al. (CRYPTO 2021). The security of their ordered multi-signature scheme was proven under the algebraic one-more discrete logarithm (AOMDL) assumption in the random oracle model (ROM). The AOMDL assumption is stronger than the discrete logarithm (DL) assumption. To strengthen the assurance of security, it is desirable either to prove their scheme under the DL assumption or give a construction whose security is proven under the DL assumption. In this paper, we give an ordered multi-signature scheme from linear hash function families. Our scheme is obtained by generalizing Baum et al.’s scheme via linear hash function families. The security of our scheme is proven under the algebraic one-more preimage resistance (AOMPR) property of a linear hash function in the ROM. There is a linear hash function whose AOMPR property can be proven under the DL assumption. Thus, by using this linear hash function, we obtain the first DL- based ordered multi-signature scheme.

As digital transformation accelerates, securing communication through hierarchical Public Key Infrastructures (PKIs) is increasingly critical. Yet, this centralized trust architecture remains inherently vulnerable. As a Systematization of Knowledge (SoK), this paper maps the threat landscape of hierarchical PKIs, demonstrating how a compromise at any single node from a Root CA breach to an operational revocation failure can trigger a cascading loss of global trust. Grounded in the Weakest-Link Principle, our analysis reveals that a PKI ecosystem is only as resilient as its least protected vector. Traditional revocation mechanisms, particularly CRLs and OCSP, exhibit significant operational and privacy flaws, and are often rendered ineffective by client-side "soft-fail" policies. To address these vulnerabilities, we advocate for a shift: replacing unconditional trust in individual entities with decentralized,verifiable protocols. We evaluate Certificate Transparency (CT) as a core mitigation strategy, illustrating how append-only Merkle trees make misissuance publicly visible and cryptographically auditable. Finally, we synthesize essential operational hardening measures such as strict key cryptoperiods and procedural policies to ensure long-term ecosystem resilience.

Ring signatures, a cryptographic primitive introduced by Rivest, Shamir and Tauman (ASIACRYPT 2001), offer signer anonymity within dynamically formed user groups. Recent advancements have focused on lattice-based constructions to improve efficiency, particularly for large signing rings. However, current state-of-the-art solutions suffer from significant overhead, especially for smaller rings. In this work, we present a novel NTRU-based ring signature scheme, Gandalf, tailored towards small rings. Our post-quantum scheme achieves a 50% reduction in signature sizes compared to the linear ring signature scheme Raptor (ACNS 2019). For rings of size two, our signatures are approximately a quarter the size of DualRing (CRYPTO 2021), another linear scheme, and remain more compact for rings up to size seven. Compared to the sublinear scheme Smile (CRYPTO 2021), our signatures are more compact for rings of up to 26. In particular, for rings of size two, our ring signatures are only 1236 bytes. Additionally, we explore the use of ring signatures to obtain deniability in authenticated key exchange mechanisms (AKEMs), the primitive behind the recent HPKE standard used in MLS and TLS. We take a fine-grained approach at formalising sender deniability within AKEM and seek to define the strongest possible notions. Our contributions extend to a black-box construction of a deniable AKEM from a KEM and a ring signature scheme for rings of size two. Our approach attains the highest level of confidentiality and authenticity, while simultaneously preserving the strongest forms of deniability in two orthogonal settings. Finally, we present parameter sets for our schemes, and show that our deniable AKEM, when instantiated with our ring signature scheme, yields ciphertexts of 2004 bytes.

Threshold signatures split the secret key among $n$ parties, where any subset of at least $t$ parties can collaboratively produce a valid signature. They have been widely deployed in applications such as blockchain systems. Lattice-based threshold signatures have also attracted considerable attention due to their post-quantum security guarantees. However, existing lattice-based constructions still face significant efficiency challenges, particularly when the number of parties becomes large. Recent lattice-based threshold signatures such as TRaccoon (Eurocrypt’24) and Ringtail (S\&P’25) support large thresholds, but they either require three interaction rounds or incur heavy communication costs in the two-round setting, limiting their practicality. In this paper, we present $\mathsf{TalonG}$, a novel two-round lattice-based threshold signature that overcomes these limitations via a new trapdoor semi-commitment technique. This variant of commitment relaxes the standard binding requirement to a weaker form, allowing an efficient instantiation from the NTRU assumption and enabling a compact two-round signing protocol with low communication. For $t=1024$ and 128-bit security, $\mathsf{TalonG}$ achieves significant improvements among existing lattice-based threshold signatures: its total communication per party and public key size are both minimal, at 26.9 KB and 2.0 KB, respectively. While the resulting signature size is larger (17.7 KB), it remains practical and highly competitive. $\mathsf{TalonG}$ is thus well-suited for real-world large-scale deployments where both round efficiency and communication load are critical.

The SPHINCS+ framework, recently standardized by NIST as SLH-DSA (FIPS 205), is a leading stateless hash-based signature scheme for the post-quantum era. Concrete-security evaluation of SPHINCS+ faces a trade-off: tight bounds require a conjectural multi-target decisional second-preimage resistance (SM-DSPR), while fully proven bounds incur substantial looseness. In this paper, we refine the concrete security analysis of SPHINCS+ by eliminating this heuristic reliance. In our approach, we analyze the SM-openPRE and SM-PRE properties instead of relying on SM-DSPR. By utilizing a precise probabilistic simulation technique, we restrict the multi-target tightness degradation exclusively to the maximum number of practically revealed targets rather than the total theoretical targets. When applied to the SLH-DSA parameter sets, our conjecture-free approach bridges the theoretical gap, recovering up to 18 bits of classical security and 9 bits of quantum security compared to the NIST loose evaluation. Our results establish a provable bound for the practical security of SLH-DSA without relying on optimistic multi-target assumptions.

Among the schemes in the second round of NIST's additional call for Post-Quantum signatures, PERK builds its security on the intractability of the Permuted Kernel Problem (PKP). In its original formulation, this problem asks, on input three matrices $\mathbf H,\mathbf X,\mathbf Y$, to find a permutation matrix $\mathbf P$ such that $\mathbf H \mathbf P \mathbf X = \mathbf Y$. To achieve better performance and smaller signatures, in its first proposal, the PERK signature modified the security assumption in the following way: given a PKP instance, the matrix $\mathbf P$ does not have to verify the exact previous equation but a relaxed one, taking care of a non-null vector $\mathbf v$ such that $(\mathbf H \mathbf P \mathbf X)\mathbf v = \mathbf Y \mathbf v$. In this work, we rephrase the relaxed problem so that it no longer depends on the PKP instance nor the vector $\mathbf v$. We show that it suffices to find $\mathbf P$ such that $\mathbf H\mathbf P \mathbf X - \mathbf Y$ has rank deficiency. This generalized formulation is easier to model and allows us to design an algebraic attack inspired by those of MinRank and Rank Syndrome Decoding, writing a polynomial system in the entries of $\mathbf P$. Moreover, we can consider it as linear in the minors of $\mathbf P$ and provide some results on them, which may be of independent interest.

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 computational Diffie-Hellman assumption (CDH) in the ROM: – The first TBS over pairing-free groups without the AGM. – The first round-optimal TBS over pairing-based groups that does not rely on interactive assumptions. The starting point for both constructions is the pairing-based signature scheme derived from Boneh-Boyen IBE (Eurocrypt’04), and their recent blind signature variants by Katsumata et al. (Asiacrypt’23) and Klooß et al. (Asiacrypt’24) based on the decisional Diffie-Hellman assumption (DDH). We first remove the reliance on DDH in their schemes, then provide careful adaptations to the threshold setting.

In this paper, we examine the One-time signature scheme using run-length encoding, as proposed by Steinwandt et al., under the scenario where an adversary is allowed to obtain signatures on two messages before attempting to forge a signature on a third message. Our analysis follows the line of security discussion presented by Groot Bruinderink et al. in their paper “Oops, I Did It Again – Security of One-Time Signatures under Two-Message Attacks.” By considering various attack models and different strategies, we estimate both the attack complexity and the probability of forging a signature. Our results indicate that the signature scheme performs well under a two-message attack, making it an interesting candidate for a few-time signature scheme. Few-time signature schemes such as HORS are a fundamental building block of stateless hash-based signature schemes.

Attribute-based encryption can be considered a generalization of public key encryption, enabling fine-grained access control over encrypted data using predetermined access policies. In general, we distinguish between key-policy and ciphertext-policy attribute-based encryption schemes. Our new scheme is built upon the multi-authority attribute-based encryption with an honest-but-curious central authority scheme in a key-policy setting presented earlier by Božović et al., and it can be considered an extension of their scheme. In their paper, trust was shared between the central authority and the participating authorities, who were responsible for issuing attribute-specific secret keys. The central authority was not capable of decrypting any message as long as there exists an honest attribute authority. In our new scheme, we maintain this feature, and add another level of security by allowing users to participate in the key generation process and contribute to the final user-specific attribute secret keys. Users gain more control over their own secret keys, and they will be the only parties with access to the final user-specific secret keys. Furthermore, no secure channels, only authenticated communication channels are needed between users and authorities. After the modifications our scheme will be closer to the registered multi-authority attribute-based encryption. We refer to our scheme as a partially registered type of multi-authority attribute-based encryption scheme. We prove the security of our scheme in the Selective-ID model.

Sampling a non degenerate (that is, invertible) square matrix over a finite field is easy, draw a random square matrix and discard if the determinant is zero. We address the problem in higher dimensions, and sample non degenerate boundary format tensors, which generalise square matrices. Testing degeneracy is conjectured to be hard in more than two dimensions, precluding the "draw a random tensor and discard if degenerate'' recipe. The difficulty is in computing hyperdeterminants, higher dimensional analogues of determinants. Instead, we start with a structured random non degenerate tensor and scramble it by infusing more randomness while still preserving non degeneracy. We propose two kinds of scrambling. The first is multiplication in each dimension by random invertible matrices, which preserves dimension and format. Assuming pseudo randomness of this action, which also underlies tensor isomorphism based cryptography, our samples are computationally indistinguishable from uniform non degenerate tensors. The second scrambling employs tensor convolution (that generalises multiplication by matrices) and can increase dimension. Inspired by hyperdeterminant multiplicativity, we devise a recursive sampler that uses tensor convolution to reduce the problem from arbitrary to three dimensions. Our sampling is a candidate solution for drawing public keys in tensor isomorphism based cryptography, since non degenerate tensors elude recent weak key attacks targeting public key tensors either containing geometric structures such as "triangles" or being deficient in tensor rank. To accommodate our sampling, tensor isomorphism based schemes need to be instantiated in boundary formats such as (2k+1) x (k+1) x (k+1), away from the more familiar k x k x k cubic formats. Our sampling (along with the recent tensor trapdoor one-way functions) makes an enticing case to transition tensor isomorphism cryptography to boundary formats tensors, which are true analogues of square matrices.

Recent MPC-in-the-Head techniques enable the construction of signature schemes with compact signature sizes from various hardness assumptions. These techniques rely on commitments based on GGM trees, which have been optimized to further reduce the signature size with the so-called one-tree or correlated tree optimizations. While the one-tree technique has no incidence on the security of the scheme, this is not obvious for the correlated tree technique, and a formal security analysis of this technique has been missing in the literature. In this work, we fill this gap and provide the first formal security analysis of MPC-in-the-Head signature schemes based on correlated trees. We first exhibit a potential security flaw of this technique which rules out any hope for a security reduction to the underlying hardness assumption. In particular, we show that recovering the first $\lambda$ bits of the secret witness is sufficient to achieve a full key recovery (where $\lambda$ is the security level). The underlying assumption should hence be such that recovering these $\lambda$ bits is as hard as recovering the full witness. Some state-of-the-art schemes do not satisfy this condition, which prevents a direct application of the correlated tree technique. We then provide a formal security proof for signature schemes based on the correlated tree technique under this degraded hardness assumption. Our proof comes in several variants, in the random oracle mode or in the ideal cipher model, depending on the specific correlated tree construction. We also introduce a tweak for the instantiation of the leaf seed expansion in the ideal cipher model, which allows us to achieve a tighter security reduction. Our result shows that MPC-in-the-Head signatures based on correlated trees can achieve strong security guarantees and provides the first formal security proof for the MQOM v2 signature scheme, the on-going candidate in the NIST post-quantum standardization process with the shortest signature size in the MPC-in-the-Head family.

We present HyperFrog, a lattice-based Key Encapsulation Mechanism (KEM) targeting post-quantum security levels. The construction instantiates a variant of the Learning With Errors (LWE) problem in which the secret vector is derived from high-genus topological structures embedded in a three-dimensional grid. Unlike standard LWE schemes that draw secrets from uniform or Gaussian distributions, HyperFrog uses a topology-mining procedure to generate sparse binary secret keys corresponding to connected subgraphs with cyclomatic number (genus) >= 8, introducing geometric constraints while preserving combinatorial hardness. To achieve practical robustness, the scheme applies the Fujisaki-Okamoto (FO) transform, attaining IND-CCA2 security under standard assumptions. The reference implementation, internally codenamed "Topological Obsidian", includes a constant-time decoding routine based on branchless arithmetic to eliminate secret-dependent control flow during decryption and re-encryption. We provide benchmark results on an AMD Ryzen 9 5950X implementation using AVX2 vectorization for polynomial arithmetic, and demonstrate the integration of the KEM into a high-performance AES-256-GCM hybrid encryption pipeline.

Fully homomorphic encryption (FHE) is a cryptographic scheme that can take ciphertexts as inputs and compute a new ciphertext of a function of the underlying messages without decryption. FHE has been attracting attention along with the growing interest in privacy-preserving technologies. In terms of privacy-preserving technology, deniable encryption is also important. Deniable encryption enables a user, who may be forced to reveal the messages corresponding to the user's public ciphertexts, to lie about which messages the user encrypted. Agrawal et al. (CRYPTO 2021) introduced deniable FHE (DFHE) that combines FHE with deniable encryption, and proposed a transformation from an FHE scheme that satisfies specific special requirements, called special FHE, to a DFHE scheme. They also showed a construction of a special FHE scheme based on the BGV (Brakerski--Gentry--Vaikuntanathan) scheme. However, in the construction by Agrawal et al., one must store all the extensive randomness used for encryption in order to lie, and a bootstrapping operation, which takes a long time to execute, is a bottleneck in execution speed. In this paper, we show that by providing a tighter upper bound on deniability, we can reduce the size of the stored randomness and the required number of bootstrapping in the construction by Agrawal et al. In addition, we show that TFHE (Chillotti et al., J. Cryptol., 2020; Joye, CT-RSA 2024), which is known as a FHE scheme with fast bootstrapping, satisfies the requirements of special FHE, and thus can realize a faster DFHE scheme than the BGV-based construction.

Curve5453 and Curve6071 are Montgomery curves over the primes $2^{545}-3$ and $2^{607}-1$, providing 271- and 302-bit classical security, respectively. Their TMVP-based field multiplication in 10-limb representation costs 77 multiplications. We reduce this to 60 for Curve5453 ($22\%$ fewer) using a 9-limb radix-$2^{61}$ representation, and to 54 for Curve6071 ($30\%$ fewer) using a 12-limb radix-$2^{51}$ representation with hierarchical block-level TMVP. Choosing the limb count to produce $3 \times 3$ Toeplitz blocks aligns the structure with the size-3 TMVP formula, computing each block product in 6 multiplications rather than 9. Portable C implementations benchmarked on ARM64 and x86-64 confirm speedups of up to $16\%$ in field multiplication and $13\%$ in scalar multiplication. On ARM64, Curve5453 reaches $90.6\%$ of OpenSSL's assembly-optimized NIST P-521 ECDH throughput with 12 additional bits of classical security, and Curve6071 delivers 302-bit classical security at $80.8\%$ of P-521's throughput.

Updatable (public-key) encryption is a broad concept covering (public-key) encryption schemes whose keys can evolve over time to support secure key rotation and limit the impact of key compromise. The essential feature is that the encryption keys (and possibly also ciphertexts) can be updated from one epoch to the next via so called update tokens. This concept is useful in various applications, among them secure outsourced storage, secure messaging or low-latency forward-secret key-exchange protocols. The term, however, is used with varying meanings across the literature. Some works define key-updatable schemes, where only the public and secret keys evolve. Others extend this idea by also allowing ciphertexts to be updated during key evolution. Variants further differ in how evolution is triggered: in some schemes, the receiver performs key updates locally, while in others, the sender initiates the evolution by embedding update information in ciphertexts. Beyond achieving forward secrecy, many formulations also aim for post-compromise security, ensuring that once a compromised key is updated, future ciphertexts regain confidentiality under the new key. In this paper, we systematize this field with a focus on updatable public-key encryption schemes. Our aim is to first provide a taxonomy that sheds light into the currently fragmented terminology. It then compares their formal definition, syntaxes and formal security models found in the literature, clarifies their interrelations, and identifies common design patterns underlying current schemes. Beyond mapping the definitional landscape we provide a comparative analysis of existing instantiations, focusing on their properties and efficiency, and highlighting their main trade-offs. The paper concludes with open challenges outlining directions for advancing the field.

In this work, we present the first lattice-based construction of batched IBE in the standard model, whose security is proven under the succinct LWE assumption. Prior batched IBE schemes are only known either based on pairing-based assumptions or in the random oracle model. Moreover, our scheme is shown to be highly efficient, as the master public key, decryption key, and ciphertext are independent of the batch size $B$. Technically, we mainly rely on an insightful observation: batched IBE can be obtained solely from Inner-Product Encryption (IPE). To satisfy the efficiency requirements of batched IBE, we require an IPE scheme that owns two important features: decomposable key generation and compact components. Finally, we show how to construct such an IPE scheme from the well-known BGG+14 IPE scheme via careful modification.

The BBS+/BBS signature scheme is a key building block for anonymous credentials and privacy-preserving authentication and is currently being standardized and increasingly deployed in practice. To avoid the problem of single-point-of-failure, many threshold BBS+ protocols have been recently proposed for general $t$-out-of-$n$ settings. In practice, however, a $2$-out-of-$2$ policy between a server and a mobile device is sufficient to distribute trust while keeping the system lightweight. Yet, existing threshold designs still require at least three rounds/passes and multi-kilobyte communication in the two-party setting. In this work, we focus on the two-party setting and show that one can achieve reduced interaction while maintaining low computational and communication overhead. Specifically, we present a two-pass two-party BBS+ signing protocol that requires only 0.85KB of communication per signature, about 27% of the currently most bandwidth-efficient work (S&P'25) in the $2$-out-of-$2$ setting. It achieves competitive signing times (roughly 62ms for one party and 46ms for the other) and remains efficient even for large message vectors (e.g., $\ell = 500$), making it attractive for practical deployments. Overall, our protocol is only slower than the fastest OT-based design (S&P'23) but uses nearly two orders of magnitude less bandwidth. We provide a full simulation-based security proof in the standard real-ideal paradigm. As an extension, our protocol can be generalized to a $2$-out-of-$n$ threshold setting naturally.

We construct compilers that convert any secure signature scheme into a single-round blind signature scheme. An important property of the construction is that the final blind signature has exactly the same format as the underlying signature scheme, making the blind signature scheme backwards compatible with the underlying scheme. Our compilers make use of (two-key) fully homomorphic encryption and zero-knowledge proofs to ensure unforgeability and blindness of the final scheme. We present three compilers where the main differences is which party does the bulk of the work: the client, the signer, or both. Along the way we introduce a new notion of verifiable FHE that we call committed verifiable FHE, where the verifier does not see the circuit in the clear.

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 constructions, while the systematic integration of standardized classical public-key encryption (PKE) schemes with post-quantum KEMs remains largely unexplored. In this work, we introduce two generic hybrid constructions, $\mathsf{HybKEM}$ and $\mathsf{HybKEM}^{*}$, that combine a classical PKE scheme with a post-quantum KEM satisfying ciphertext second-preimage resistance (C2PRI). We prove that both constructions achieve IND-CCA security in the standard model. The refined construction $\mathsf{HybKEM}^{*}$ additionally relies on a new security notion of the classical PKE scheme, termed partial ciphertext second-preimage resistance (PC2PRI), which captures second-preimage resistance when a designated ciphertext component is fixed. This new property enables shared-key derivation from only a designated PKE ciphertext component in $\mathsf{HybKEM}^{*}$, leading to improved efficiency. Finally, we provide a systematic analysis of the PC2PRI property for several standardized classical encryption schemes, including ECIES, PSEC, and SM2.

Steganography studies methods to not only protect the confidentiality of messages but also to conceal the very act of message transmission. Prior provably secure stegosystems are predominantly constructed based on a rejection sampling technique which achieves an encoding rate inversely proportional to the min-entropy of the cover channel. Furthermore, while replayable chosen-covertext attack (RCCA) secure stegosystems for general channels can be constructed based on standard cryptographic assumptions, it is known [Berndt and Liśkiewicz, EUROCRYPT'18] that achieving (standard) CCA-security for channels with memory in the so-called non-look-ahead model is in general impossible and the only known CCA-secure construction crucially relies on the channels being memoryless. In this work, we show that the impossibility on CCA-secure stegosystems can be circumvented, in the random oracle model, by dropping the non-look-ahead restriction and by restricting to a natural class of channels which we call "partially sampleable channels". These capture channels which partly consist of explicitly sampleable distributions, such as Gaussian sensor noise of digital photographs. To achieve a high encoding rate, we extend the formalisation of stegosystems to capture a technique known as "cover-source switching" in the practical steganography literature. This allows us to construct CCA-secure stegosystems for Gaussian channels using Gaussian preimage sampling techniques borrowed from lattice-based cryptography, which can theoretically achieve an embedding rate of $1/\omega(\log \log \lambda)$ regardless of the min-entropy of the channel. Our prototype implementation suggests that our scheme is practical, achieving an embedding rate of 24.7% in 24-megapixel RAW images in around 1 minute per image.

This short note explains how the Tate pairing can be used to efficiently sample torsion points with precise requirements, and other applications. These applications are most clearly explained on Montgomery curves, using the Tate pairing of degree 2, but hold more generally for any degree or abelian variety, or even generalized Tate pairings. This note is explanatory in nature; it does not contain new results, but aims to provide a clear and concise explanation of results in the literature that are somewhat hidden, yet are extremely useful in practical isogeny-based cryptography.

In this work, we present Functional Encryption (FE) schemes for Attribute-Weighted Sums (AWS), introduced by Abdalla, Gong and Wee (Crypto 2020) in the registration-based setting (RFE). In such a setting, users sample their own public/private key pairs $(\mathsf{pk}_i, \mathsf{sk}_i)$; a key curator registers user public keys along with their functions $h_i$; encryption takes as input $N$ attribute-value pairs $\{\vec x_\ell, \vec z_\ell\}_{\ell\in[N]}$ where $\vec x_\ell$ is public and $\vec z_\ell$ is private; and decryption recovers the weighted sum $\sum_{\ell\in[N]}h_i(\vec x_\ell)^\mathsf{T}\vec z_\ell$ while leaking no additional information about $\vec z_\ell$. Recently, Agrawal, Tomida and Yadav (Crypto 2023) studied the attribute-based case of AWS (AB-AWS) providing fine-grained access control, where the function is described by a tuple $(g_i, h_i)$, the input is extended to $(\vec y, \{\vec x_\ell, \vec z_\ell\}_{\ell \in [N]})$ and decryption recovers the weighted sum only if $g_i(\vec y) = 0$. Our main results are the following: - We build the first RFE for (AB-)1AWS functionality, where $N=1$, that achieves adaptive indistinguishability-based security under the (bilateral) $k$-Lin assumption in prime-order pairing groups. Prior works achieve RFE for linear and quadratic functions without access control in the standard model, or for attribute-based linear functions in the generic group model. - We develop the first RFE for AB-AWS functionality, where $N$ is unbounded, that achieves very selective simulation-based security under the bilateral $k$-Lin assumption. Here, “very selective” means that the adversary declares challenge attribute values, all registered functions and corrupted users upfront. Previously, SIM-secure RFEs were only constructed for linear and quadratic functions without access control in the same security model. We devise a novel nested encoding mechanism that facilitates achieving attribute-based access control and unbounded inputs in the registration-based setting for AWS functionalities, proven secure in the standard model. In terms of efficiency, our constructions feature short public parameters, secret keys independent of $N$, and compact ciphertexts unaffected by the length of public inputs. Moreover, as required by RFE properties, all objective sizes and algorithm costs scale poly-logarithmically with the total number of registered users in the system.

This work presents a novel machine-checked tight security proof for $\mathrm{XMSS}$ — a stateful hash-based signature scheme that is (1) standardized in RFC 8391 and NIST SP 800-208, and (2) employed as a primary building block of $\mathrm{SPHINCS}^{+}$, one of the signature schemes recently selected for standardization as a result of NIST’s post-quantum competition. In 2020, Kudinov, Kiktenko, and Fedoro pointed out a flaw affecting the tight security proofs of $\mathrm{SPHINCS}^{+}$ and $\mathrm{XMSS}$. For the case of $\mathrm{SPHINCS}^{+}$, this flaw was fixed in a subsequent tight security proof by Hülsing and Kudinov. Unfortunately, employing the fix from this proof to construct an analogous tight security proof for XMSS would merely demonstrate security with respect to an insufficient notion. At the cost of modeling the message-hashing function as a random oracle, we complete the tight security proof for $\mathrm{XMSS}$ and formally verify it using the EasyCrypt proof assistant. As part of this endeavor, we formally verify the crucial step common to (the security proofs of) $\mathrm{SPHINCS}^{+}$ and $\mathrm{XMSS}$ that was found to be flawed before, thereby confirming that the core of the aforementioned security proof by Hülsing and Kudinov is correct. As this is the first work to formally verify proofs for hash-based signature schemes in EasyCrypt, we develop several novel libraries for the fundamental cryptographic concepts underlying such schemes — e.g., hash functions and digital signature schemes — establishing a common starting point for future formal verification efforts. These libraries will be particularly helpful in formally verifying proofs of other hash-based signature schemes such as $\mathrm{LMS}$ or $\mathrm{SPHINCS}^{+}$.

This self-contained and detailed tutorial covers RSA-based integer commitments and related protocols. It also presents a new, highly efficient setup protocol for sampling commitment parameters.

Fully homomorphic encryption algorithms enable users to perform computation on encrypted data. Since the first candidate scheme was proposed in 2009 by Gentry, schemes have rapidly improved in all metrics, be it computational complexity or memory efficiency. The class of accumulator based schemes which include FHEW and TFHE are designed to operate on small data, usually ranging between 4 and 5 bits. Yet, schemes can be effectively leveraged in practice and enable lifting of small data to larger plaintext domains through the use of so-called programmable bootstrapping, the ability to evaluate arbitrary functions on an encrypted datum with time independent of the function. In this work, we present novel methods for homomorphic digit decomposition, the task of efficiently breaking up a large encrypted datum, vastly exceeding the conventional plaintext domain size, into a radix representation for a chosen basis. Our approach relies on a computationally inexpensive decomposition of a ciphertext into chunks that can be assembled into the original message, without requiring that such chunks correspond to actual digits. Asymptotically, our approach doubles the performance compared to prior work and practically is 90% faster than the state of the art by Liu et al. As a direct consequence of our digit decomposition, we describe how to increase the size of the plaintext domain by a large factor, while only doubling the computational complexity and not causing a super-polynomial slowdown. Although concurrent works on functional bootstrapping reach similar improvements regarding the plaintext domain, our approach shines through its conceptual simplicity and flexibility.

Traceable Receipt-free Encryption (TREnc) has recently been introduced by Devillez, Pereira and Peters (Asiacrypt’22) as a verifiable public-key encryption primitive allowing to randomize ciphertexts in order to remove any subliminal information up to a public trace which prevents the malleability of the underlying plaintexts. This unique feature generically enables the construction of voting systems by allowing voters to encrypt their votes, tracing whether a published ballot takes their choices into account, and preventing them from proving how they voted. While being a very promising primitive, the few existing TREnc mechanisms solely rely on discrete-logarithm related assumptions making them vulnerable to the well-known harvest now, decrypt later attack in the wait of quantum computers. In this article, we address this limitation by building the first TREnc which can be safely used today until the advent of quantum adversaries. More precisely, based on the observation that security must hold at the time the primitive is used while only privacy should withstand in the post-quantum era, our solution relies on a mix of pre-quantum and post-quantum cryptography. As a first contribution, we generalize the original TREnc primitive that is too restrictive to be easily compatible with built-in lattice-based semantically-secure encryption. Our more flexible model keeps all the ingredients generically implying receipt-free voting. Next, we design our construction with the following essential proper- ties for trustworthy elections: (i) it is provably-secure in the standard model; (ii) it relies on standard assumptions, namely Ring Learning With Errors (RLWE) coupled with pairing-based statistical zero-knowledge simulation-sound SXDH-based proofs; and (iii) it further enjoys a public-coin common reference string removing the need of a trusted setup.

Fully Homomorphic Encryption (FHE) allows users to offload large computations to servers without revealing the underlying data. Due to this unique feature, it is applicable to a variety of domains, including privacy-preserving Machine Learning. However, all FHE schemes have two problems- slow encryption/decryption and substantial ciphertext expansion. Thus, despite its significant potential, the practical implementation of FHE faces considerable challenges due to massive computation and communication overhead. In this work we address this gap, and propose a novel \tonetwo approach to optimize client-side homomorphic encryption, leveraging bootstrapping. This technique minimizes ciphertext expansion and reduces the communication overhead on the server as well as the client. We also eliminate the need for encoding and decoding by the client, thereby omitting the floating-point arithmetic requirement for FHE over approximate numbers. The elegance of this technique lies in its ability to utilize the built-in FHE routines and inherently maintain security and precision guarantees. The proposed technique reduces the enc/decryption computation and communication requirements by up to $97\%$. We employ the proposed techniques to develop a framework for FHE client operations that is compatible with both software and hardware platforms. We conduct a comprehensive design analysis and FPGA prototyping, present ASIC synthesis results, and provide microcontroller performance evaluations. The efficient architecture design methodology demonstrates up to $76\times$ speedup compared to prior works on the same platform.

Group signatures (GS) are a well-known cryptographic primitive that provide both anonymity and traceability. Several implication results have been established, mainly focusing on different security levels of anonymity. For example, fully anonymous GS implies public-key encryption (PKE), and selfless anonymous GS can be constructed from one-way functions and non-interactive zero-knowledge proofs, among others. In this paper, we explore a winning condition for full traceability: an adversary must produce a valid group signature whose opening reveals an uncorrupted user. We present a generic construction of GS that is secure in the Bellare-Micciancio-Warinschi (BMW) model, except for the above condition, based solely on PKE. We emphasize that the proposed construction is highly artificial and practically meaningless because the verification algorithm always outputs 1 regardless of the input. This result suggests that the winning condition is essential for full traceability, namely that an uncorrupted user must exist.

The Learning with Errors (LWE) problem has been widely utilized as a foundation for numerous cryptographic tools over the years. In this study, we focus on an algebraic variant of the LWE problem called Group ring LWE (GR-LWE). We select group rings (or their direct summands) that underlie specific families of finite groups constructed by taking the semi-direct product of two cyclic groups. Unlike the Ring-LWE problem described in [LPR10], the multiplication operation in the group rings considered here is non-commutative. As an extension of Ring-LWE, it maintains computational hardness and can be potentially applied in many cryptographic scenarios. In this paper, we present two polynomial-time quantum reductions. Firstly, we provide a quantum reduction from the worst-case shortest independent vectors problem (SIVP) in ideal lattices with polynomial approximate factor to the search version of GR-LWE. This reduction requires that the underlying group ring possesses certain mild properties; Secondly, we present another quantum reduction for two types of group rings, where the worst-case SIVP problem is directly reduced to the (average-case) decision GR-LWE problem. The pseudorandomness of GR-LWE samples guaranteed by this reduction can be consequently leveraged to construct semantically secure public-key cryptosystems.

We introduce a new (amortized) functional bootstrapping framework over the CKKS homomorphic encryption (HE) scheme based on Fourier extension. While approximating the modular reduction function in CKKS bootstrapping through Fourier series is a well-known technique, how such method can be efficiently generalized to functional bootstrapping is less understood. In this work, we show that, by constructing proper Fourier extensions, any function with a bounded domain in the smoothness class $C^{\kappa}$ can be approximated by a degree-$n$ Fourier series with errors of order $O(n^{-\kappa-2})$ (except at the singularities), improving on previous results on a global error bound of $O(n^{-1})$ [AKP2025]. To achieve such bound, we propose a new way of constructing Fourier extensions, such that the extended functions appear as smooth as possible in the sense of a Fourier approximation. By implementing our functional bootstrapping over OpenFHE, we demonstrate that we can improve the data precision by $10$-$27$ bits and reduce the amortized FBS latency by $1.1$-$2\times$ over a variety of benchmarking functions.

Certified deletion ensures that encrypted data can be irreversibly deleted, preventing future recovery even if decryption keys are later exposed. Although existing works have achieved certified deletion across various cryptographic primitives, they rely on central authorities, leading to inherent escrow vulnerabilities. This raises the question of whether certified deletion can be achieved in decentralized frameworks such as Registered Attribute-Based Encryption (RABE) that combines fine-grained access control with user-controlled key registration. This paper presents the first RABE schemes supporting certified deletion and certified everlasting security. Specifically, we obtain the following: - We first design a privately verifiable RABE with Certified Deletion (RABE-CD) scheme by combining our newly proposed shadow registered ABE (Shad-RABE) with one-time symmetric key encryption with certified deletion. - We then construct a publicly verifiable RABE-CD scheme using Shad-RABE, witness encryption, and one-shot signatures, allowing any party to validate deletion certificates without accessing secret keys. - We also extend to privately verifiable RABE with Certified Everlasting Deletion (RABE-CED) scheme, integrating quantum-secure RABE with the certified everlasting lemma. Once a certificate is produced, message privacy becomes information-theoretic even against unbounded adversaries. - We finally realize a publicly verifiable RABE-CED scheme by employing digital signatures for the BB84 states, allowing universal verification while ensuring that deletion irreversibly destroys information relevant to decryption.

SQIsign is an isogeny‑based post‑quantum signature scheme over supersingular elliptic curves that represents isogenies as elements of a quaternion algebra, enabling highly compact signatures and efficient computation. However, because SQIsign performs quaternion arithmetic over $\mathbb{Q}$, no explicit, uniform worst‑case bound is available for the integer coefficients used to represent quaternion algebra elements. Hence, existing implementations require multi-precision integer arithmetic which hinders portability and complicates memory management, disabling constant-time and embedded-friendly implementations. In this work, we perform a complete analysis of all routines in the Round-2 SQIsign specification that manipulate quaternion elements and establish an explicit uniform worst‑case size bound, with a hypothesis to make all intermediate quaternion computations provably bounded. This proof removes the need for multi-precision arithmetic, enabling the first implementation of SQIsign with fixed-precision integer arithmetic, further presenting possibility of constant-time and memory-friendly implementation. We further tighten this bound by introducing a modified ideal multiplication algorithm, which is a subroutine of SQisign. By modifying the ideal multiplication, we derived the improvement of the size of uniform bound compared with the experimental maximum bit of original Round-$2$ SQIsign, as $45\%/44\%/44.5\%$, for NIST-I/III/V security levels, respectively. Relying on the reduced uniform bound, we build a fixed-precision C implementation of SQIsign.

In applications such as secure group communication and broadcasting, it is important to efficiently deliver multiple messages to different recipients at once. To this end, multi-message multi-recipient Public Key Encryption (mmPKE) enables the batch encryption of multiple messages for multiple independent recipients in one go, significantly reducing costs–particularly bandwidth–compared to the trivial solution of encrypting each message individually. This capability is especially desirable in the post-quantum setting, where the ciphertext length is typically significantly larger than the corresponding plaintext. However, almost all prior works on mmPKE are limited to quantum-vulnerable traditional assumptions. In this work, we propose the first CPA-secure mmPKE and Multi-Key Encapsulation Mechanism (mmKEM) from the standard Module Learning with Errors (MLWE) lattice assumption, named mmCipher-PKE and mmCipher-KEM, respectively. Our design proceeds in two steps: (i) We introduce a novel generic construction of mmPKE by proposing a new PKE variant—extended reproducible PKE (XR-PKE)—that enables the reproduction of ciphertexts through additional hints; (ii) We instantiate a lattice-based XR-PKE using a new technique that can precisely estimate the impact of such hints on the ciphertext security while also establishing suitable parameters. We believe both to be of independent interest. As a bonus contribution, we explore generic constructions of adaptively secure mmPKE, resisting adaptive corruption and chosen-ciphertext attacks. We also provide an efficient implementation and thorough evaluation of the practical performance of our mmCipher. The results demonstrate substantial bandwidth and computational savings over the state-of-the-art. For example, for 1024 recipients, our mmCipher-KEM achieves a 23-45× reduction in bandwidth overhead, with ciphertexts only 4-9% larger than the plaintexts (near optimal bandwidth), while also offering a 3-5× reduction in computational cost.

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 assumptions, and detail the generalizations of Diffie-Hellman and ElGamal protocols within this broader context. Finally, the paper investigates the renaissance of group and semigroup actions in the design of next-generation digital signatures, providing a detailed algebraic analysis of candidates in the current NIST competition.

Hamming Quasi-Cyclic (HQC) is a leading code-based key-encapsulation mechanism (KEM), recently selected by NIST for standardization, whose bandwidth and efficiency are balanced with the concrete cost of information-set decoding (ISD) attacks. However, the current balance relies on (1) the decryption-failure-rate (DFR) is directly configured to be less than $2^{-\lambda}$ ($\lambda$ is the security parameter), rather than carefully determined by choosing conservative parameters to resist known attacks as the Kyber team did in the design of NIST FIPS 203; (2) the error distribution in the underlying quasi-cyclic syndrome decoding problem is restricted to be balanced. In this paper, we show how to quantitatively and conservatively evaluate the impact of removing the aforementioned two restrictions on the complexities of known attacks, and thus find a new balance among bandwidth, efficiency, and security for HQC. In detail, we first formalize the best-known decryption-failure attack against HQC, and derive an upper bound on the probability that an adversary triggers a decryption-failure event under realistic query and time limits, enabling an attack-aware upper bound on the secure DFR. Second, we quantify how the weight distribution of $(\mathbf{r}_1, \mathbf{r}_2, \mathbf{e})$ (the random low-weight polynomials used in encryption) affects the concrete cost of ISD attacks and DFR. This yields an \emph{unbalanced} weight strategy that strictly lowers the DFR without sacrificing the targeted bit security, leading to a new variant called \emph{Unbalanced HQC (UHQC)}. By combining these analyses, we provide optimized parameters for UHQC. Across all NIST security levels, UHQC reduces bandwidth by 10-12% and improves runtime by 6-8%.

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 encryption (PKE) scheme, such as RSA-OAEP. We additionally show how to securely promote an IND-CCA2 PKE into an IND-CCA KEM. We perform two complementary security analyses of CK in the standard model: the first shows CK is IND-CCA assuming the traditional KEM is IND-CCA, the post-quantum KEM is C2PRI, and the KDF is a secure PRF; the second shows CK is IND-CCA assuming the post-quantum KEM is IND-CCA and the KDF is a secure PRF, even if the traditional KEM is completely broken. Neither proof requires the random oracle model.

In fully homomorphic encryption, bootstrapping serves as a key component while also remaining the performance bottleneck of the scheme. Specifically, for CKKS bootstrapping, this bottleneck is reflected in significant computational overhead and modulus consumption. In this work, we improve the CKKS bootstrapping with lower time complexity and less modulus consumption. We first propose a novel rescaling operation, called level-conserving rescaling, that acts on CoeffsToSlots for saving moduli. Secondly, we reconstruct the rotation keys and merge the plaintext-ciphertext multiplication and rescaling operations into the key-switching procedure, which reduces the time complexity of matrix-vector multiplication for matrices with $\le$64 non-zero diagonals, albeit with increased space overhead. By combining the two methods in CoeffsToSlots in a non-trivial manner, we not only further accelerate the homomorphic linear transformations and save one level of moduli, but also reduce the total size of rotation keys. Experiments demonstrate the practicability of our techniques. Compared to the state of the art, our approaches save one level of moduli, achieving a $20\%\sim 35\%$ improvement in bootstrapping throughput and an 11.9\% $\sim$ 15.2\% reduction of rotation key size in CoeffsToSlots. Furthermore, with sufficient storage, our technology achieves up to 40\% higher bootstrapping throughput than before, at the cost of doubling the rotation key size in CoeffsToSlots. The bootstrapping precision and failure probability remain identical to the previous method.

The efficiency of Public Key Encryption (PKE) and Key Encapsulation Mechanism (KEM), and in particular their large ciphertext size, is a bottleneck in real-world systems. This worsens in post-quantum secure schemes (e.g., lattice-based ones), whose ciphertexts are an order of magnitude larger than prior ones.%their non-post-quantum counterparts. The work of Kurosawa (PKC'02) introduced multi-message multi-recipient PKE (mmPKE) to reduce the amortized ciphertext size when sending messages to more than one recipient. This notion naturally extends to multi-message multi-recipient KEM (mmKEM). In this work, we first show concrete attacks on existing lattice-based mmPKE schemes: Using maliciously-crafted recipient public keys, these attacks completely break semantic security and key privacy, and are inherently undetectable. We then introduce the first lattice-based mmKEM scheme that maintains full privacy even in the presence of maliciously-generated public keys. Concretely, the ciphertext size of our mmKEM for 100 recipients is ${\sim} 8\times$ smaller than naively using Crystals-Kyber. We also show how to extend our mmKEM to mmPKE, achieving a scheme that outperforms all prior lattice-based mmPKE schemes in terms of both security and efficiency. We additionally show a similar efficiency gain when applied to batched random oblivious transfer, and to group oblivious message retrieval. Our scheme is proven secure under a new Module-LWE variant assumption, Oracle Module-LWE, which can be of its own independent interest. We reduce standard MLWE to this new assumption for some parameter regimes, which also gives intuition on why this assumption holds for the parameter we are interested in (along with additional cryptanalysis). Furthermore, we show an asymptotically efficient compiler that removes the assumption made in prior works that recipients know their position in the list of intended recipients for every ciphertext.

This paper presents the first round-optimal threshold blind signature without random oracles. Our construction achieves security in the algebraic group model (AGM) for asymmetric pairing groups, and tolerates adaptive corruption of up to $t-1$ signers, where $t$ is the threshold. We improve upon the recent threshold blind signatures of Lehmann, Nazarian and Özbay (EUROCRYPT 2025) and Jarecki and Nazarian (ASIACRYPT 2025) in two ways: we eliminate both the reliance on random oracles and the need for $q$-type assumptions in the AGM. As a core building block, we introduce a new pairing-based round-optimal blind signature without random oracles, based on the $2$-DL assumption in the AGM. Both blind signature schemes achieve communication and computation costs only twice that of the celebrated blind BLS signature.

Attribute-based signatures (ABS) allow users to simultaneously sign messages and prove their possession of some attributes while hiding the attributes and revealing only the fact that they satisfy a public policy. In this paper, we propose a generic construction of ABS for circuits of unbounded depth and size, with optimal parameter size—meaning the lengths of public parameters, keys, and signatures are all constant. Our construction can be instantiated from various standard assumptions, including LWE and DLIN. This substantially improves the state-of-the-art ABS scheme by Boyle, Goldwasser, and Ivan (PKC 2014), which, while achieving optimal parameter size, relies on succinct non-interactive arguments of knowledge that can only be constructed from non-standard assumptions. Our generic construction is based on RAM delegations. At a high level, we leverage the fact that the circuit associated with the signature can be made public and compress it using the power of RAM delegation. This allows us to achieve an overall optimal parameter size while simultaneously hiding the user’s attribute.

FuncCPA is a recent security notion in which the CPA game is extended by a functional re-encryption oracle in order to model setups in which a server performing FHE computations is allowed to interactively delegate part of the computation back to the client. In this paper, we study funcCPA-style variants of several CCA security notions, including CCA1 and the more recent vCCA security. Contrary to the CPA case where a strict separation holds between CPA and funcCPA, we show that these new variants are equivalent to their respective originating CCA security notions. Interestingly, funcCPA-style security notions also model setups where, rather than delegating part of the encrypted domain computation all the way back to the client, the server has the ability to perform this delegation towards a honest or semi-honest client proxy it hosts, such as a secure enclave. We then provide a number of blueprints for achieving both FHE-like capabilities and advanced CCA security properties which may then meaningfully be implemented by leveraging on the combination of a partially homormophic scheme and a semi-honest non-colluding enclave hosted within the server performing the encrypted domain calculations itself.

Falcon is a winner of NIST’s six-year post-quantum cryptography standardisation competition. Based on the celebrated full-domain-hash framework of Gentry, Peikert and Vaikuntanathan (GPV) (STOC’08), Falcon leverages NTRU lattices to achieve the most compact signatures among lattice-based schemes. Its security hinges on a Rényi divergence-based argument for Gaussian samplers. However, the GPV proof, which uses statistical distance to argue closeness of distributions, fails when applied naively to Falcon due to parameter choices resulting in statistical distances as large as $2^{−34}$. Additional implementation-driven deviations from the GPV framework further invalidate the original proof, leaving Falcon without a security proof despite its selection for standardisation. In this work, we provide the first formal security proof of Falcon in the random oracle model, achieved through a few conservative modifications, now incorporated into the forthcoming standard. At the heart of our analysis lies an adaptation of the GPV framework to work with the Rényi divergence, along with an optimised method for parameter selection under this measure. We also analyse the FFO Sampler that is used in Falcon. Further, we prove the equivalence of plain unforgeability to a multi-target inhomogeneous SIS problem, and strong unforgeability to a second-preimage version of this problem, providing clear targets for cryptanalysis. Assuming these problems are as hard as standard SIS, we demonstrate that Falcon-512 barely satisfies the claimed 120-bit security target, while Falcon-1024 achieves the claimed security level.

This paper gives the first lattice-based two-round threshold signature scheme that tolerates the adaptive corruption of up to $T -1$ out of $N$ signers. Our construction is based on the MLWE and MSIS assumptions. We substantially improve upon the only existing adaptively secure lattice-based construction, recently given by Katsumata, Reichle, and Takemure (CRYPTO '24), which requires five rounds.

Registered attribute-based encryption (Reg-ABE) is a new variant of attribute-based encryption (ABE) that was introduced to resolve the notorious key escrow problem. In a Reg-ABE system, there is no authority that generates secret keys, and each user joins the system by generating its own public/secret key pair. Because of its public-key infrastructure-like model and versatile access control functionality, Reg-ABE is a promising alternative of ABE. In this work, we present a highly space efficient non-monotone Reg-ABE scheme with strong security. Specifically, the sizes of MPK and ciphertext of our scheme are both about 7.5KB, which could be more than 2000$ \times $ and 5$ \times $ smaller than those of the state-of-the-art scheme by Garg \textit{et al.}~(Crypto'24, GLWW), respectively, in a realistic parameter setting. The sizes of other elements such as helper secret key and a state that the system maintains could also become more than 40$ \times $ smaller. Furthermore, our scheme supports non-monotone policies and CCA-security, neither of which GLWW supports. We implement our scheme together with GLWW and show that encryption of ours outperforms that of GLWW even with the above features, while decryption of ours is a few times less efficient than that of GLWW but still takes less than 0.1 seconds with a laptop. Our scheme is proven secure in the generic group model. We also present a dual system variant of our main scheme, which is CPA-secure under the MDDH assumption in the plain model. The variant is much simpler and more efficient than the only known non-monotone Reg-ABE scheme by Attrapadung \textit{et al.}~(Crypto'24).

Following the announcement of the first winners of the NIST post-quantum cryptography standardization process in 2022, cryptographic protocols are now undergoing migration to the newly standardized schemes. In most cases, this transition is realized through a hybrid approach, in which algorithms based on classical hardness assumptions, such as the discrete logarithm problem, are combined with post-quantum algorithms that rely on quantum-resistant assumptions, such as the Short Integer Solution (SIS) problem. A combiner for signature schemes can be obtained by simply concatenating the signatures of both schemes. This construction preserves unforgeability of the underlying schemes; however, it does not extend to stronger notions, such as strong unforgeability. Several applications, including authenticated key exchange and secure messaging, inherently require strong unforgeability, yet no existing combiner is known to achieve this property. This work introduces three practical combiners that preserve strong unforgeability and all BUFF (beyond unforgeability features) properties. Each combiner is tailored to a specific class of classical signature schemes capturing all broadly used schemes that are strongly unforgeable. Remarkably, all combiners can be instantiated with any post-quantum signature scheme in a black-box way making deployment practical and significantly less error prone. The proposed solutions are further highly efficient and have signatures that are at most the size of the (insecure) concatenation combiner. For instance, our most efficient combiner enables the combination of EdDSA with ML-DSA, yielding a signature size that is smaller than the sum of an individual EdDSA signature and an individual ML-DSA signature. Additionally, we identify a novel signature property that we call random-message validity and show that it can be used to replace the BUFF transform with the more efficient Pornin-Stern transform. The notion may be of independent interest.

The beyond unforgeability features formalize additional security properties for signature schemes. We develop a general framework of binding properties for signature schemes that encompasses existing beyond unforgeability features and reveals new notions. Furthermore, we give new results regarding various transforms: We show that the transform by Cremers et al. (SP’21) achieves all of our security notions; we give a modified definition of so-called weak keys, and show that the Pornin–Stern transform (ACNS’05) also achieves all notions if there are no weak keys. Finally, we connect our framework to unforgeability notions.

Non-interactive blind signatures (NIBS; Eurocrypt '23) allow a signer to asynchronously generate presignatures for a recipient, ensuring that only the intended recipient can extract a "blinded" signature for a random message. We introduce a new generalization called non-interactive batched blind signatures (NIBBS). Our goal is to reduce the computation and communication costs for signers and receivers, by batching multiple blind signature queries. More precisely, we define the property of 'succinct communication' which requires that the communication cost from signer to receiver be independent of the batch size. NIBBS is very suitable for large-scale deployments requiring only minimal signer-side effort. We design a NIBBS scheme and prove its security based on the hardness of lattice assumptions (in the random oracle model). When instantiated with the low-depth PRF candidate "Crypto Dark Matter" (TCC '18) and the succinct lattice-based proof system for rank-1 constraint systems (Crypto '23), our final signature size is 308 KB with <1 KB communication.

Homomorphic encryption (HE) for high-precision integers has been steadily researched through various schemes; however, these approaches incurred severe overhead as the bit-width grew, requiring larger parameters to support integers of several hundred to a thousand bits. A significant breakthrough was recently made by Boneh and kim (Crypto'25). Their scheme constructs a residue number system from the different slots of a single CKKS ciphertext. This enables arithmetic on thousand-bit integers without increasing parameters. However, RNS approach in Boneh et al., which performs approximate reduction, fundamentally cannot support non-arithmetic operations. Alternatively, radix-based approach proposed by Kim (CHES'25) can perform non-arithmetic operations, but they require $O(k)$ bootstraps for a bit-width $k$. This makes them highly inefficient, and thus impractical, for non-arithmetic operations requiring thousand-bit precision. This paper proposes an improved radix-based CKKS scheme, centered on a 2-step algorithm that optimizes the number of bootstraps required for the digit carry operation to $O(\log k)$. The proposed scheme requires only 3-6 bootstraps to restore the result of a 32-2048 bit integer multiplication to its unique representation, which enables the efficient implementation of non-arithmetic operations such as comparison. Furthermore, our scheme extends the radix-based system, previously limited to prime-power moduli, to support an efficient homomorphic reduction algorithm for arbitrary moduli. Furthermore, our experiments demonstrate substantial efficiency gains compared to Boneh et al. For example, for moduli used in homomorphic signatures (Curve25519, P-384, and 2048-bit RSA), our scheme can process up to 4$\times$ more integers in a single ciphertext. Specifically for Curve25519, we also reduce the latency by 1.4$\times$, shortening the amortized time by 5.6$\times$ compared to Boneh et. al. and achieving a final processing time of 1.34 seconds per data point.

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 threshold traitor tracing (TTT), which equips threshold encryption with traceability. Yet, all known TTT schemes either suffer from parameter sizes growing with at least $n^{1/3}$, or rely on indistinguishability obfuscation to achieve optimal parameters. In this paper, we present the first TTT schemes with optimal parameters, where public keys, secret keys, and ciphertexts are all bounded by ${\sf poly}(\lambda,\log n)$, built solely from standard cryptographic tools and assumptions. Our first construction relies on the decisional Bilinear Diffie–Hellman (DBDH) assumption in prime order bilinear groups. Our second scheme is a candidate construction based on the Learning with Errors (LWE) assumption, which relies on the existence of secret sharing schemes with certain properties. This construction is plausibly post-quantum secure, and supports ramp-thresholds where decryption requires a larger coalition than those tolerated by security. Both of our constructions provide traceability against coalitions of arbitrary sizes. To achieve these results, we introduce a new primitive, Attribute-Based Threshold Encryption (ABTE), which generalizes both threshold and attribute-based encryption. We then combine ABTE with Mixed Functional Encryption through a new compiler to obtain our TTT schemes. We believe ABTE is a powerful primitive that may have independent applications beyond optimal TTT.

Post-quantum signature schemes are becoming increasingly important due to the threat of quantum computers to classical cryptographic schemes. Among the approaches considered in the literature, the MPC-in-the-head paradigm introduced by Ishai et al. (STOC'07) provides an innovative solution for constructing zero-knowledge proofs by exploiting Multi-Party Computation (MPC). This technique has proven to be a versatile tool in order to design efficient cryptographic schemes, including post-quantum signatures. Building on the MPC-in-the-head paradigm, we introduce Bittersweet signatures, a new class of signature schemes based on the Learning With Rounding (LWR) assumption. Their main advantage is conceptual simplicity: by exploiting (almost) key-homomorphic pseudorandom functions (PRFs), a cryptographic object that preserves pseudorandomness while allowing linear operations on keys, we obtain a very regular design offering nice opportunities for parallel implementations. Theoretically, analyzing Bittersweet signatures requires addressing significant challenges related to the (carry) leakage that almost key-homomorphic operations lead to. Concretely, Bittersweet signatures natively lead to competitive signature sizes, trading moderate software performance overheads for hardware performance gains when compared to state-of-the-art MPC-in-the-head schemes (e.g., relying on code-based assumptions), while admittedly lagging a bit behind recent algorithms based on the VOLE-in-the-head or Threshold-Computation-in-the-head frameworks. Besides, their scalability and algebraic structure makes them promising candidates for leakage-resilient implementations. The new abstractions we introduce additionally suggest interesting research directions towards further optimization and generalization.

X-Wing (Barbosa et al., CiC Volume 1, Issue 1) is a hybrid key encapsulation mechanism (KEM) currently considered for standardization by IETF and deployed by major companies such as Google to ensure a secure transition to post-quantum cryptography. It combines a classical X25519 KEM with the post-quantum ML-KEM-768. In this paper, we propose the first analysis of the anonymity of X-Wing. We are interested in tight and memory-tight reductions that offer stronger security guarantees. We first establish in the standard model that for any IND-CCA secure KEM, weak anonymity implies full anonymity, and our reduction is tight not only in success probability and time but also in memory consumption. We then prove in the random oracle model that X-Wing achieves weak anonymity if both X25519 and ML-KEM-768 are weakly anonymous. The former can even be proven without a hardness assumption. Our proof on the weak anonymity of X-Wing does not preserve the memory-tightness of the underlying KEMs. To improve it, we propose a slight variant of X-Wing that preserves memory-tightness. Finally, we improve the existing IND-CCA proof of the original X-Wing by Barbosa et al. using our new memory-tight analysis.

This paper investigates the algebraic structure of SNOVA, a NIST PQC Round 2 candidate, with a specific focus on the kernel dimension of the wedge map. We employ lifting techniques to transform the public key from the matrix ring $\mathbb{F}_q^{l \times l}$ to an equivalent representation over the extension field $\mathbb{F}_{q^l}$, establishing that the rank of the wedge map is a structural invariant. A key contribution of this work is the derivation of a generating function that explicitly characterizes the wedge map's kernel dimension. This algebraic analysis provides a rigorous understanding of SNOVA's geometry, verifying the safety of specific parameter sets and enabling future refined adjustments to guarantee structural security.

Distributed monotone-policy encryption augments public-key encryption with fine-grained decryption capabilities in a trustless manner. In this scheme, users independently generate a public/private key-pair and post their public key to a public-key directory. Thereafter, anyone can encrypt a message to a set of public keys together with an access policy. Any set of users that satisfies the access policy can decrypt the ciphertext while the message should remain computationally hidden to any unsatisfying set of users. The primary efficiency requirement is succinctness: namely, the size of the ciphertext should be sublinear (or polylogarithmic) in the description length of the policy. Distributed monotone-policy encryption directly generalizes recent trustless cryptographic notions like threshold encryption with silent setup and distributed broadcast encryption. In this work, we show how to construct distributed monotone-policy encryption for Boolean formulas in disjunctive normal form (DNF formulas) that supports an unbounded number of users. Security relies on the decomposed learning with errors (LWE) assumption, a simple and falsifiable lattice assumption, in the random oracle model. Previously, such a scheme was only known from plain witness encryption in the random oracle model. Our scheme has a transparent setup and the ciphertext size is $\mathsf{poly}(\lambda, \log N)$, where $N$ is the number of variables in the DNF formula.

Distributed cryptography serves as a cornerstone for building trustless systems, yet existing solutions for distributed policy encryption typically require either a trusted dealer or complex interactive setup protocols. Recent advances have introduced the concept of $silent~setup$, where users independently generate keys and a joint public key is derived deterministically. However, all current silent-setup constructions rely on bilinear pairings, leaving them vulnerable to quantum adversaries. In this work, we present the first distributed monotone-policy encryption scheme with silent setup based on lattices. Our construction supports arbitrary monotone policies represented as Disjunctive Normal Forms (DNFs) and provides a robust, post-quantum foundation for decentralized access control.

Multi-signatures enable multiple parties to create a joint signature on the same message. Such schemes aggregate several individual signatures and public keys into a short signature and aggregated public key, and verification is performed on these combined values. Interestingly, all existing notions of unforgeability for multi-signatures are designed with a single honest user in mind, overlooking the multi-user setting that multi-signatures are built for. While multi-user security can be bootstrapped from any single-user secure scheme, the straightforward adoption implies a security loss that is linear in the number of signers n. In this work we therefore start the investigation of multi-signatures with tight multi-user security. We show that none of the existing multi-signatures with tight single-user security seems amendable to the multi-user setting, as all their proofs and design choices exploit the fact that there is only a single honest user. Based on this insight, we then propose two new constructions built from scratch with multi-user security in mind: Skewer-NI, a non-interactive and pairing-based scheme, and Skewer-PF, a pairing-free and two-round construction. We prove both schemes tightly secure under the DDH assumption in the ROM. Both schemes also improve the state-of-the-art in another aspect: they support the feature of key aggregation. Skewer-NI is the first non-interactive tightly secure multi-signature with this feature. In the pairing-free two-round setting, Skewer-PF is the first to combine tight multi-user security with key aggregation where the only prior result, due to Bacho and Wagner (CRYPTO’25), achieved aggregation but only in the single-user case.

In this paper, we revisit the recent Pegasis algorithm that computes an effective group action of the class group of any imaginary quadratic order $R$ on a set of supersingular elliptic curves primitively oriented by $R$. Although Pegasis was the first algorithm showing the practicality of computing unrestricted class group actions at higher security levels, it is complicated and prone to failures, which leads to many rerandomizations. We present a new algorithm, qt-Pegasis, which is much simpler, but at the same time faster and removes the need for rerandomization of the ideal we want to act with, since it never fails. It leverages the main technique of the recent Qlapoti approach. However, Qlapoti solves a norm equation in a quaternion algebra, which corresponds to the full endomorphism ring of a supersingular elliptic curve. We show that the algorithm still applies in the quadratic setting, by embedding the quadratic ideal into a quaternion ideal using a technique similar to the one applied in KLaPoTi. This way, we can reinterpret the output of Qlapoti as four equivalent quadratic ideals, instead of two equivalent quaternion ideals. We then show how to construct a Clapoti-like diagram in dimension $2$, which embeds the action of the ideal in a $4$-dimensional isogeny. We implemented our qt-Pegasis algorithm in SageMath for the CSURF group action, and we achieve a speedup over Pegasis of $1.8\times$ for the 500-bit parameters and $2.6\times$ for the 4000-bit parameters.

In this paper we introduce a rank $2$ lattice over a polynomial ring arising from the public key of the BIKE cryptosystem. The secret key is a sparse vector in this lattice. We study properties of this lattice and generalize the recovery of weak keys from "Weak keys for the quasi-cyclic MDPC public key encryption scheme". In particular, we show that they implicitly solved a shortest vector problem in the lattice we constructed. Rather than finding only a shortest vector, we obtain a reduced basis of the lattice which makes it possible to check for more weak keys.

The two groups $\mathbb{G}_1$ and $\mathbb{G}_2$ on pairing-friendly curves typically have nontrivial cofactors, which may give rise to security vulnerabilities (e.g., small subgroup attacks) in pairing-based protocols. In order to avoid the pitfalls of cofactors, it is necessary to perform subgroup membership testing. Previous testing methods for such curves relied on efficiently computable endomorphisms. In 2023, Koshelev introduced a novel technique of subgroup membership testing for a list of non-pairing-friendly curves, requiring at most two small Tate pairings. In fact, this technique can also be applied to certain pairing-friendly curves, such as those from the BLS and BW13 families. In this paper, we revisit Koshelev's method and propose simplified formulas for computing the two Tate pairings. Compared to the original formulas, ours reduce both the number of Miller's iterations and the storage requirements. Moreover, we provide a high-speed software implementation on a 64-bit processor. Our experimental results show that the new method outperforms the state-of-the-art one by up to $62.0\%$ and $41.2\%$ on for singular $\mathbb{G}_1$ membership testing on the BW13-310 and BLS48-575 curves, respectively. When precomputation is utilized, the improvements increase to $110.6\%$ and $74.4\%$ on the two curves, respectively.

The Shortest Vector problem (SVP) is the most important problem in lattice-based cryptanalysis. There is currently a gap in the understanding of this problem with respect to its worst-case complexity and its average-case behaviour. For instance, SVP on an n-dimensional lattice has worst-case complexity $2^{n+o(n)}$ [ADRS15]. However, in practice, people rely on heuristic (unproven) sieving algorithms of time complexity $2^{0.292n+o(n)}$ [BDGL16] to assess the security of lattice-based cryptography schemes. Those heuristic algorithms are experimentally verified for lattices used in cryptography, which are usually random in some way. In this paper, we try to bridge the gap between worst-case and heuristic algorithms. Using the formalism of random real lattices developed by Siegel, we show a tighter upper bound on an important lattice parameter called the smoothing parameter that applies to almost all random lattices. Using a known discrete Gaussian sampler at the smoothing parameter, we can then directly sample short vectors. This allows us to provably solve an approximation version of the SVP on almost all random lattices with a small constant approximation factor $1.123$, in time $2^{n/2+o(n)}$. With further analysis, we can provably solve the exact SVP in time $2^{0.63269n+o(n)}$ on most random lattices as well. We also provide a smooth time approximation factor tradeoff between these two cases. All our algorithms work in space $2^{n/2+o(n)}$.

Zero-knowledge simulators, initially developed for proving the security of proof systems, turned out to be also useful in constructing advanced protocols from simple three-move interactive proofs. However, in the context of multi-round public-coin protocols, the interfaces of these auxiliary algorithms become more complex, introducing a range of technical challenges that hinder the generalization of these constructions. We introduce a framework to enhance the usability of zero-knowledge simulators in multi-round argument systems for protocol designs. Critical-round zero-knowledge relies on the ability to perform complete zero-knowledge simulations by knowing the challenge of just one specific round in advance. We show that these notions are satisfied by diverse protocols based on MPC-in-the-Head, interactive oracle proofs, and split-and-fold arguments. We demonstrate the usefulness of the critical round framework by constructing proofs of partial knowledge (Cramer, Damgård, and Schoenmakers, CRYPTO’94) and trapdoor commitments (Damgård, CRYPTO’89) from critical-round multi-round proofs.

We present a fully homomorphic encryption scheme which natively supports arithmetic and logical operations over large ``machine words'', namely plaintexts of the form $\mathbb{Z}_{2^n}$ (e.g.\ $n=64$). Our scheme builds on the well-known BGV framework, but deviates in the selection of number field and in the encoding of messages. This allows us to support large message spaces with only modest effect on the noise growth. Arithmetic operations (modulo $2^n$) are supported natively similarly to BGV-style FHE schemes, and we present an efficient bootstrapping procedure for our scheme. Our bootstrapping algorithm has the feature that along the way it decomposes our machine word into bits, so that during bootstrapping it is possible to perform logical operations (essentially addressing each bit in the message independently). This means that during a single bootstrapping cycle we can perform logical operations on $n$ bits. For example, a ``greater than'' operation (if $x> y$ output $1$, otherwise $0$), only requires a single subtraction and a single bootstrapping cycle. Along the way we present a number of new tools and techniques, such as a generalization of the BGV modulus switching technique to a setting where the plaintext and ciphertext moduli are ideals (and not numbers).

This paper studies the concrete security of BBS signatures (Boneh, Boyen, Shacham, CRYPTO '04; Camenisch and Lysyanskaya, CRYPTO '04), a popular algebraic construction of digital signatures which underlies practical privacy-preserving authentication systems and is undergoing standardization by the W3C and IRTF. Sch\"age (Journal of Cryptology '15) gave a tight standard-model security proof under the $q$-SDH assumption for a less efficient variant of the scheme, called BBS+--here, $q$ is the number of issued signatures. In contrast, the security proof for BBS (Tessaro and Zhu, EUROCRYPT '23), also under the $q$-SDH assumption, is \emph{not} tight. Nonetheless, this recent proof shifted both standardization and industry adoption towards the more efficient BBS, instead of BBS+, and for this reason, it is important to understand whether this tightness gap is inherent. Recent cryptanalysis by Chairattana-Apirom and Tessaro (ASIACRYPT '25) also shows that a tight reduction to $q$-SDH is the best we can hope for. This paper closes this gap in two different ways. On the positive end, we show a novel tight reduction for BBS in the case where each message is signed at most once--this case covers in particular the common practical use case which derandomizes signing. On the negative end, we use a meta-reduction argument to prove that if we allow generating multiple signatures for the same message, then {\em no} algebraic reduction to $q$-SDH (and its variants) can be tight.

One-sided linear systems of the form ``$Ax=b$'' are well-known and extensively studied over the tropical (max-plus) semiring and wide classes of related idempotent semirings. The usual approach is to first find the greatest solution to such system in polynomial time and then to solve a much harder problem of finding all minimal solutions. We develop an extension of this approach to the same systems over two well-known extensions of the tropical semiring: symmetrized and supertropical, and discuss the implications of our findings for the tropical cryptography.

In a batched identity-based encryption (IBE) scheme, ciphertexts are associated with a batch label $\mathsf{tg}^\ast$ and an identity $\mathsf{id}^\ast$ while secret keys are associated with a batch label $\mathsf{tg}$ and a set of identities $S$. Decryption is possible whenever $\mathsf{tg} = \mathsf{tg}^\ast$ and $\mathsf{id}^\ast \in S$. The primary efficiency property in a batched IBE scheme is that the size of the decryption key for a set $S$ should be independent of the size of $S$. Batched IBE schemes provide an elegant cryptographic mechanism to support encrypted memory pools in blockchain applications. In this work, we introduce a new algebraic framework for building pairing-based batched IBE. Our framework gives the following: First, we obtain a selectively-secure batched IBE scheme under a $q$-type assumption in the plain model. Both the ciphertext and the secret key consist of a constant number of group elements. This is the first pairing-based batched IBE scheme in the plain model. Previous pairing-based schemes relied on the generic group model and the random oracle model. Next, we show how to extend our base scheme to a threshold batched IBE scheme with silent setup. In this setting, users independently choose their own public and private keys, and there is a non-interactive procedure to derive the master public key (for a threshold batched IBE scheme) for a group of users from their individual public keys. We obtain a statically-secure threshold batched IBE scheme with silent setup from a $q$-type assumption in the plain model. As before, ciphertexts and secret keys in this scheme contain a constant number of group elements. Previous pairing-based constructions of threshold batched IBE with silent setup relied on the generic group model, could only support a polynomial number of identities (where the size of the public parameters scaled linearly with this bound), and ciphertexts contained $O(\lambda / \log \lambda)$ group elements, where $\lambda$ is the security parameter. Finally, we show that if we work in the generic group model, then we obtain a (threshold) batched IBE scheme with shorter ciphertexts (by 1 group element) than all previous pairing-based constructions (and without impacting the size of the secret key). Our constructions rely on classic algebraic techniques underlying pairing-based IBE and do not rely on the signature-based witness encryption viewpoint taken in previous works.

Isogeny-based cryptography is cryptographic schemes whose security is based on the hardness of a mathematical problem called the isogeny problem, and is attracting attention as one of the candidates for post-quantum cryptography. A representative isogeny-based cryptography is the signature scheme called SQIsign, which was submitted to the NIST PQC standardization competition for additional signature. SQIsign has attracted much attention because of its very short signature and key size among candidates for the NIST PQC standardization. Recently, many new signature schemes using high-dimensional isogenies have been proposed, such as: SQIsignHD, SQIsign2D-West, SQIsgn2D-East, and SQIPrime. Last year, SQIsign advanced to Round 2 of the NIST competition and was updated to version 2.0 (we call it SQIsign-v2.0), which is based on SQIsign2D-West. SQIsign-v2.0 achieves smaller signature sizes and faster verification. However, the signing costs are relatively high. In this paper, we propose a new signature scheme `SQIsign2DPush', which has a smaller signing cost than SQIsign-v2.0 while the signature size and the verification cost are almost the same.

Witness Encryption (WE) is a powerful cryptographic primitive, enabling applications that would otherwise appear infeasible. While general-purpose WE requires strong cryptographic assumptions, and is highly inefficient, recent works have demonstrated that it is possible to design special-purpose WE schemes for targeted applications that can be built from weaker assumptions and can also be concretely efficient. Despite the plethora of constructions in the literature that (implicitly) use witness encryption schemes, there has been no systematic study of special purpose witness encryption schemes. In this work we make progress towards this goal by designing a modular and extensible framework, which allows us to better understand existing schemes and further enables us to construct new witness encryption schemes. The framework is designed around simple but powerful building blocks that we refer to as "gadgets". Gadgets can be thought of as witness encryption schemes for small targeted relations (induced by linearly verifiable arguments) but they can be composed with each other to build larger, more expressive relations that are useful in applications. To highlight the power of our framework we methodically recover past results, improve upon them and even provide new feasibility results. The first application of our framework is a Registered Attribute-Based Encryption Scheme [Hohenberger et al. (Eurocrypt 23)] with linear sized common reference string (CRS). Numerous Registered Attribute-Based Encryption (R-ABE) constructions have introduced though a black-box R-ABE construction with a linear--in the number of users--CRS has been a persistent open problem, with the state-of-the-art concretely being N^{1.58} (Garg et al. [GLWW, CRYPTO 24]). Empowered by our Witness Encryption framework we provide the first construction of black-box R-ABE with linear-sized CRS. Our construction is based on a novel realization of encryption for DNF formulas that leverages encryption for set membership. Our second application is a feasibility result for Registered Threshold Encryption (RTE) with succinct ciphertexts. RTE (Branco et al. [ASIACRYPT 2024] is an analogue of the recently introduced Silent Threshold Encryption (Garg et al. [GKPW, CRYPTO 24]) in the Registered Setting. We revisit Registered Threshold Encryption and provide an efficient construction, with constant-sized encryption key and ciphertexts, that makes use of our WE framework.

Threshold cryptography is a standard technique for distributing trust by splitting cryptographic keys into multiple shares held by different parties. The classic model of threshold cryptography assumes either that a trusted dealer distributes the shares to the different parties (and in doing so, also knows the overall secret) or that the users participate in an interactive distributed key-generation protocol to derive their individual shares. In recent years, several works have proposed a new model where users can independently choose a public key, and there is a public and deterministic function that derives the joint public key associated with a group of users from their individual keys. Schemes with this silent (i.e., non-interactive) setup procedure allow us to take advantage of the utility of threshold cryptography without needing to rely on a trusted dealer or an expensive interactive setup phase. Existing works have primarily focused on threshold policies. This includes notions like threshold signatures (resp., encryption) with silent setup (where only quorums with at least $T$ users can sign (resp., decrypt) a message) and distributed broadcast encryption (a special case of threshold encryption where the threshold is 1). Currently, constructions that support general threshold policies either rely on strong tools such as indistinguishability obfuscation and witness encryption, or analyze security in idealized models like the generic bilinear group model. The use of idealized models is due to the reliance on techniques for constructing succinct non-interactive arguments of knowledge (SNARKs). In this work, we introduce a new pairing-based approach for constructing threshold signatures and encryption schemes with silent setup. On the one hand, our techniques directly allow us to support expressive policies like monotone Boolean formulas in addition to thresholds. On the other hand, we only rely on basic algebraic tools (i.e., a simple cross-term cancellation strategy), which yields constructions with shorter signatures and ciphertexts compared to previous pairing-based constructions. As an added bonus, we can also prove (static) security under $q$-type assumptions in the plain model. Concretely, the signature size in our distributed threshold signature scheme is 3 group elements and the ciphertext size in our distributed threshold encryption scheme is 4 group elements (together with a short tag).

Blind rotation is the computational core of GINX, AP, and AP+ bootstrappings, yet its error behavior has not been precisely characterized. Prior analyses rely on heuristic independence assumptions that fail to capture the distinct error accumulation patterns of different algorithmic variants. We prove that no additional assumptions are needed: the (M)LWE assumption guaranteeing ciphertext indistinguishability also implies the independence properties required for an exact second-moment characterization of blind rotation error. We derive the first closed-form formulas covering all four combinations of decomposition type (full vs. approximated) and algorithmic variant (vanilla vs. unrolled). Our analysis reveals three structural phenomena previously overlooked: (i) a message-dependent residual term that halves the effective decomposition variance, (ii) a doubling coefficient inherent to unrolled implementations, and (iii) bounded cross-term correlations whose contribution remains constant in the security parameter. Our formulas match experimental measurements within 1%, whereas prior estimators deviate by up to 50% for unrolled blind rotation. Our results show that the (M)LWE assumption—already required for security— is sufficient to determine the exact error behavior of GINX, AP, and AP+ bootstrapping.

Anamorphic Encryption (Persiano, Phan and Yung, Eurocrypt '22) allows private communication in a challenging setting where encryption is severely controlled by a central authority (henceforth the dictator) who can demand the users to surrender their secret keys. Anamorphic Signatures (AS) (Kutylowski, Persiano, Phan, Yung, Zawada, Crypto '23) face the even more restrictive world where only authentication is allowed but users still want to send secret messages despite the repressive control of the dictator holding their signing key. Several constructions have been proposed so far, but they all come with some limitations. We propose a new flexible setting where digital signatures are used to covertly embed secret shares which $t$ out of $N$ designated receivers can combine to recover a covert secret. We formalize this new primitive called Anamorphic Secret Sharing Signatures (ASSS) together with new robustness, forward secrecy, and private unforgeability notions and we give a construction for Schnorr-like signatures overcoming the limitations of previous constructions. ASSS additionally imply (regular single-receiver) AS, but two signatures (instead of one) are needed to recover the covert message.

Fully Homomorphic encryption allows the evaluation of any circuits over encrypted data while preserving the privacy of the data. However, without any additional properties, no guarantee is provided for the privacy of the circuits which are evaluated. A sanitization algorithm allows to destroy all previous information about how a ciphertext was obtained, ensuring that the circuit which was evaluated remains secret. In this paper, we present two new techniques to randomize RLWE ciphertexts, and show how they can be used to achieve ciphertext sanitization for the TFHE scheme proposed by Chillotti et al. (Asiacrypt 2016), by modifying the bootstrapping procedure internally. Our first technique relies on a generalization of the strategy proposed by Bourse et al. (Crypto 2016) to the ring setting. Using a backward induction over the circuit size, we also improve on their proof technique to avoid randomization at each step of the computation, enabling faster randomization and smaller noise growth. While this first approach adapts well in theory, we show evidence that it fails to provide a practical solution and propose a second solution with more realistic parameters at the cost of using an additional public key. As an additional contribution, we improve on the prohibitive size of the public key by relaxing the circuit privacy property to its computational counterpart, and build an efficient public randomizer composed of an RLWE-based public key encryption with additional properties on the ciphertexts distribution. We show that this randomizer can be used in the soak-and-spin paradigm of Ducas and Stehlé (Eurocrypt 2016) as well, and that it yields a significant improvement, mainly in the size of the public key. As a proof of concept, we provide a C implementation of our sanitization strategy, which shows that a sanitized LWE ciphertext can be obtained almost for free compared to a bootstrapped LWE ciphertext assuming many discrete Gaussian samples at hand.

In this work, we investigate the landscape of emerging lattice-based assumptions tailored for anonymous credentials, focusing on variants of the Short Integer Solution (SIS) problem augmented with auxiliary hints. We provide a tight reduction from the Generalised ISISf (GenISISf) (Dubois et al., PKC 2025) assumption to its interactive variant IntGenISISf, enabling the construction of proof-friendly signature schemes without incurring the significant efficiency loss observed in prior works. In particular, our results directly apply to the anonymous credential scheme proposed by Bootle et al. (CRYPTO 2023), and circumvent the 4X blow-up in the credential size due to their security loss. We also identify families of functions f for which GenISISf is as hard as SIS, leading to the first (strongly) unforgeable standard-model signature scheme from SIS without relying on chameleon hash functions. Moreover, we analyse the “one-more”-type lattice assumptions, showing in particular that Randomised One-More-ISIS (Baldimtsi et al., ASIACRYPT 2024) is at least as hard as standard One-More-ISIS (Agrawal et al., ACM CCS 2022). Further, we inspect different, yet equivalent, variations of Randomised One-More-ISIS which could be of independent interest. Finally, we compare the structural properties of GenISISf and One-More-ISIS, highlighting both shared techniques and fundamental differences. We believe our results contribute to a clearer understanding of the assumptions underpinning efficient, lattice-based anonymous credential systems.

In this paper, we show that tightly secure signature schemes in the multi-user setting with adaptive corruptions can be achieved from various weak assumptions, such as classical discrete logarithm, RSA, factoring, and even the post-quantum group action discrete logarithm assumption, at the cost of signature length. To this end, we introduce a new framework to construct a signature scheme. Our construction is a combination of an identification scheme with multiple secret keys per public key (with additional specific features) and (randomized) Fischlin transformation. From the straight-line extractability of the transformation, intuitively unforgeability can be tightly reduced to the soundness of an identification scheme in the programmable random oracle model (PROM). Our careful security proof succeeds in a tight reduction in the non-programmable random oracle model (NPROM). As a complementary study, we analyze the multi-user security of hash-based signatures. Although hash-based signatures seem to be tightly secure in the multi-user setting with adaptive corruptions (at the cost of signature lengths similar to our construction), their security has not been closely analyzed. We show the tight security based on collision resistance of the underlying hash function by modeling the pseudo-random function for key generation as a (programmable) random oracle. By using a hash function whose security is tightly reduced to other assumptions, such as the discrete logarithm problem, we also obtain a tightly secure signature based on them. However, the concrete signature size is larger than our proposal based on an identification scheme, and the security reduction is in the PROM in contrast to our new framework.

Anonymous Attribute-Based Credentials (ABCs) let users authenticate by proving only the attributes required by a policy. In many applications, single-show ABCs are particularly attractive because they can be instantiated from Blind Signatures with Attributes (BSAs) and showing reduces to a signature check, yielding low overhead. However, most existing Blind Signatures do not allow for attribute embedding. We provide a generic transform that lifts a broad class of two/three-move blind signatures to BSAs. We furthermore identify issues with prior definitions of blindness and secure showing of BSAs, particularly related to the selective reveal of attributes, and we upgrade these definitions. Our transform uses Merkle commitments and a parallel cut-and-choose to enforce attribute consistency and achieves concurrent one-more unforgeability, our stronger secure-showing notion, and the upgraded blindness. Finally, we prove that the well-known construction of Anonymous Credentials Light (ACL) satisfies the stronger notions without modification (in ROM+AGM). Taken together, our results consolidate the definitional landscape for single-show ABCs with attributes and provide a modular route to practical constructions.

In this paper, we construct the first asymptotically efficient two-round $n$-out-of-$n$ and multi-signatures from lattices in the quantum random oracle model (\QROM), using the Fiat-Shamir with Aborts (\FSwA) paradigm. Our protocols can be viewed as the improvements on the two-round protocols by Damg{\aa}rd et al. (JoC 2022). From a technical perspective, the simulation of \QROM~and the efficient reduction from breaking underlying assumption to forging signatures are the essential challenges to achieving efficient $\QROM$ security for the previously related works. In order to conquer the former one, we adopt the quantum-accessible pseudorandom function (\QPRF) to simulate $\QROM$. Particularly, we show that there exists a $\QPRF$ that is both invertible and programmable, which can simulate $\QROM$ with the same properties. Moreover, we use $\QPRF$ as an intermediate tool to successfully simulate $\QROM$ whose output is separable, even against a quantum adversary. For the latter challenge, we tweak and apply the online extractability by Unruh (Eurocrypt 2015).

We construct and implement an efficient post-quantum commutative cryptographic group action based on combining the SCALLOP framework for group actions from isogenies of oriented elliptic curves on one hand with the recent Clapoti method for polynomial-time evaluation of the CM group action on elliptic curves on the other. We take advantage of the very attractive performance of $(2^e,2^e)$-isogenies between products of elliptic curves in the theta coordinate system. To successfully apply Clapoti in dimension $2$, it is required to resolve a particular quadratic diophantine norm equation, for which we employ a slight variant of the KLPT algorithm. Our work marks the first practical instantiation of the CM group action for which both the setup and the online phase can be computed in (heuristic) polynomial time. We also point out that the order of the acting group — equivalently, the size of the set being acted on — is known, and can be chosen (within constraints) during parameter generation, in our construction.

In this paper, we propose an algorithm to efficiently retrieve the value of Euler's totient function of an RSA modulus, consequently voiding the RSA encryption. Furthermore, we show that the proposed algorithm is significantly faster and more effective when the prime factors of an RSA modulus are closer to each other. We conjecture a relation between the difference of two prime factors of the RSA modulus and the required number of steps for the algorithm.

Threshold ECDSA has become a crucial security component in blockchain and decentralized systems, as it mitigates the risk of a single point of failure. Following the multiplicative-to-additive approach, the state-of-the-art threshold ECDSA (Doerner et al. in S&P24) requires only three rounds but has \( O(n) \) outgoing communication complexity. Based on threshold CL encryption, Wong et al. (in NDSS24) proposed the first scheme with constant outgoing communication; however, their scheme requires at least four rounds. We bridge this gap by introducing a three-round threshold ECDSA scheme with constant outgoing communication based on threshold CL encryption. Additionally, we enhance our basic scheme with robustness while maintaining the number of communication rounds, albeit at the cost of non-constant outgoing communication. Our implementation demonstrates that the basic scheme achieves optimal runtime and communication costs, while the robust variant reduces the communication rounds required by Wong et al.'s scheme, incurring only a small additional cost in small-scale settings.

The works of Ananth et al. (ITCS 2022) and Bartusek et al. (Eurocrypt 2023) initiated the study of pre-constrained cryptography which achieves meaningful security even against the system authority, without assuming any trusted setup. In this work we significantly expand this area by defining new primitives and providing constructions from simple, standard assumptions as follows. 1. For general constraints, we sidestep the lower bound by Ananth et al. by defining a weaker static notion of pre-constrained encryption (sPCE), which nevertheless suffices for all known applications. We construct sPCE for general constraints with security against malicious authorities from a variety of assumptions, including DDH, LWE, QR, and DCR. In particular, our LWE-based construction achieves unconditional security against malicious authorities. 2. We also study succinctness in sPCE (laconic sPCE), where the public key is sublinear in the number of function keys. We show that laconic sPCE is impossible to achieve in the strongest malicious model of security against authority and provide the first construction of semi-malicious laconic sPCE for general constraints from LWE in the random oracle model. 3. As an application of our sPCE, we provide the first construction of pre-constrained group signatures supporting general constraints, achieving unconditional anonymity and unlinkability against malicious authorities from the LWE assumption. The only other construction by Bartusek et al. supports the restricted set/database membership constraint, and achieves computational security from the DDH assumption. Along the way, we define and construct the notion of pre-constrained Input Obfuscation which may be of independent interest.

Chameleon hash functions are trapdoor hashes that allow authorized adaptations while preserving security against outsiders. They appear in chameleon signatures, sanitizable and redactable structures, and several ledger mechanisms, yet the literature remains scattered. To our knowledge, no prior work has offered a dedicated survey or SoK on CHFs. This paper provides the first unified account, covering 1998 to 2025. We build a usable overview instead of a taxonomy dump. We collect the published constructions into a compact dataset that records underlying assumptions, trapdoor arrangements, and target security notions, and we place these results on a timeline from 1998 to 2025 to show how definitions and design choices evolved. We then provide simple maps that let the reader pivot between authorization models, trapdoor structure, and functional or algebraic features, keeping comparisons focused and avoiding unnecessary parameter detail. The result is a reference for making informed choices in real deployments. We end with a short set of future roads we believe are worth exploring, drawn from the gaps we observed and aimed at aligning CHF design with practical constraints and follow-up studies.

Sanitizable signatures authorize semi-trusted sanitizers to modify admissible blocks of a signed message. Most works consider only one sanitizer while those considering multiple sanitizers are limited by their capacity to manage admissible blocks which must be the same for all of them. We study the case where different sanitizers with different roles can be trusted to modify different blocks of the message. We define a model for multi-sanitizer sanitizable signatures which allow managing authorization for each sanitizer independently. We also provide formal definitions of its security properties. We propose two secure generic constructions FSV-k-SAN and IUT-k-SAN with different security properties. We implement both constructions and evaluate their performance on a server and a smartphone.

QC-MDPC based schemes feature secret sparse binary vectors in a cyclic polynomial ring. When those vectors are sparse enough, they can be reconstructed from their distance spectrum, that is the set of all distances between the coordinates of the non-zero coefficients. In this work, we revisit the reconstruction algorithms and we explore to what extent a secret sparse vector can be recovered from a partial knowledge of its distance spectrum. In particular, we show how to efficiently use reliability (soft information) in the reconstruction process. Another aspect of this work is to investigate which kind of side-channel leaks information about the distance spectrum and to understand the models that enable us to quantify the reliability on leaking data depending on the amount of side-channel observations (or queries). For instance, we show that for BIKE level 1, assuming that a side-channel leaks information about the syndrome weight, using soft information in the reconstruction process reduces the number of queries by a factor 10. Our technique can also be applied to HQC, which also features sparse secret vector, with similar figures, assuming there exists a side-channel leaking relevant information, the error weight in the case of HQC.

Falcon is a lattice-based signature scheme that has been selected as a standard in NIST post-quantum cryptography standardization project. The trapdoor generation process of Falcon amounts to generating two polynomials, $f$ and $g$, that satisfy certain conditions to achieve a quality parameter $\alpha$ as small as possible, because smaller $\alpha$ usually leads to higher security levels and shorter signatures. The original approach to generate NTRU trapdoors, proposed by Ducas, Lyubashevsky, and Prest (ASIACRYPT 2014), is based on trial-and-repeat, which generates $f$ and $g$ with small Gaussian coefficients and tests whether they satisfy the condition or not. If not, the process is repeated. In practice, $\alpha$ is chosen as 1.17 because it is the smallest value that keeps the number of repetitions relatively small. A recent work by Espitau et al. (ASIACRYPT 2023) proposed a new approach to generate NTRU trapdoors: instead of using trial-and-repeat, sample $f$ and $g$ in the Fourier domain that satisfies the targeted quality and map them back to ring elements. In principle, the idea of Fourier sampling applies to Falcon itself as well, but the sampling region in the Fourier domain for Falcon has a distinct, less elegant geometric shape, which makes sampling more challenging. In this paper, we adopt Markov Chain Monte Carlo (MCMC) methods for sampling. The core idea is to start from an arbitrary point within the target region and perform random walks until the point approximates a random sample from the desired distribution. Specifically, we use Gibbs sampler with Fourier sampling to generate Falcon trapdoors. Our approach allows us to achieve \(\alpha\) values arbitrarily close to 1 efficiently, whereas the original trial-and-repeat method would require impractically many repetitions (far exceeding trillions) to reach even \(\alpha = 1.04\). In particular, Falcon-512 currently falls short of the NIST level one requirement of 128 bits, but our method effectively mitigates this gap. Furthermore, our approach eliminates the need for discrete Gaussian sampling, which is challenging to implement and secure. Instead, our method relies solely on uniform sampling over an interval, simplifying the implementation and improving efficiency.

We propose Curve5453 and Curve6071, two Montgomery curves over the Crandall prime $2^{545}-3$ and Mersenne prime $2^{607}-1$, respectively, providing 271 and 302 bits of classical security. Comprehensive security analysis shows Curve6071 passes all verifiable SafeCurves criteria, while Curve5453 passes all except completeness. We develop TMVP-optimized field multiplication tailored to the arithmetic structure of these primes for 10-limb representations on 64-bit architectures, achieving $12.0\%$ and $20.4\%$ speedups over the closest alternative. ARM64 benchmarks show scalar multiplication completing in 871,898 and 895,028 cycles, respectively, competitive with existing lower-security alternatives such as E-521 (259-bit security) while delivering higher security levels. These curves address a critical gap for hybrid post-quantum constructions requiring classical security commensurate with quantum-resistant components, blockchain systems with decades-long security requirements, and specialized deployments where implementation robustness and enhanced classical security are essential---providing the first SafeCurves-compliant alternatives beyond 260 bits with demonstrated practical performance on modern architectures.

In the past decade and largely in response to the NIST standardization effort for post-quantum cryptography, many new designs for digital signatures have been proposed. Among those, the FAEST digital signature scheme (Baum et al., CRYPTO 2023) stands out due to its interesting security-performance trade-off. It only relies on well-tested symmetric-key cryptographic primitives, as it constructs a digital signature from a zero-knowledge (ZK) proof of knowledge of an AES key. To achieve this, it uses the VOLE-in-the-Head ZK proof system which relies only on pseudorandom generator (PRG) and hash function calls. FAEST simultaneously has relatively small signature size and competitive sign and verify times. In this work, we improve both the security and practical efficiency of FAEST. We improve the main computational bottleneck of the original construction by replacing hash function calls in the underlying vector commitment scheme with calls to an AES-based PRG. At the same time, we also improve the signature size by revisiting the evaluation of the AES block cipher in ZK. We use observations from Galois Theory to compress the size of the witness (and thus signature), due to the algebraic nature of the AES S-Box. We implemented our new construction, and our benchmarks show that its sign and verify times reduce up to $50\%$ over the state-of-the-art while achieving the same security and smaller signatures. Finally, we analyze our resulting signature scheme both in the Quantum Random Oracle Model (QROM) and its classical analogue. To achieve concretely good security bounds, we devise a new classical proof for FAEST based on Renyi divergence techniques. We construct a QROM analogue and present a new Fiat-Shamir transform which is applicable to VOLE-in-the-Head-based signature schemes.

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 IND-CCA even if the generic IND-CCA KEM is broken; the other complementary analysis shows UG is IND-CCA even if the DH assumptions in the nominal group are broken (by, e.g., a cryptographically-relevant quantum computer).

We study the cryptographic properties of sums of commutators of quaternions modulo $q$. We show that for certain parameters, the distribution of the sum of commutators of uniformly random elements with elements sampled from a discrete Gaussian is statistically close to uniform. We also give reductions from worst-case lattice problems such as SIVP to SIS-style problems defined using commutators on structured quaternionic lattices. Together these results indicate one-wayness and collision resistance of the sum-of-commutators function, under worst-case assumptions on lattices. We use this to develop a linearly homomorphic commitment scheme, dubbed `ABBA', which in many cases can be substituted for the widely-used Ajtai commitment scheme. We demonstrate the utility of the properties of commutation by replacing the Ajtai commitments used in Neo (a state-of-the-art folding scheme from lattices) with ABBA commitments, obtaining a 25% commitment size reduction and an almost equally efficient scheme.

We propose a new iterative method to convert a ciphertext from the Generalized BFV (GBFV) to the regular BFV scheme. In particular, our conversion starts from an encrypted plaintext that lives in a large cyclotomic ring modulo a small-norm polynomial $t(x)$, and gradually changes the encoding to a smaller cyclotomic ring modulo a much larger integer $p$. Previously, only a trivial conversion method was known, which did not change the underlying cyclotomic ring. Using our improved conversion algorithm, we can bootstrap the GBFV scheme almost natively, in the sense that only a very small fraction of the operations is computed inside regular BFV. Specifically, we evaluate (an adapted version of) the slot-to-coefficient transformation entirely in the GBFV scheme, whereas the previous best method used the BFV scheme for that transformation. This insight allows us to bootstrap either with less noise growth, or much faster than the state-of-the-art. We implement our new bootstrapping in Microsoft SEAL. Our experiments show that, for the same remaining noise budget, our bootstrapping runs in only 800 ms when working with ciphertexts containing 1024 slots over $\mathbb{F}_p$ with $p = 2^{16}+1$. This is $1.6\times$ faster than the state-of-the-art. Finally, we use our improved GBFV bootstrapping in an application that computes an encrypted edit distance. Compared to the recent TFHE-based Leuvenshtein algorithm, our GBFV version is almost two orders of magnitude faster in the amortized sense.

The primary goal of Anamorphic encryption ($\mathsf{AE}$), introduced at Eurocrypt 2022, is to enable private communication even in highly adversarial settings, such as when an adversarial $\textit {dictator}$ "legally" confiscates a user's secret keys (compromising the receiver's privacy) and/or coerces users into sending specific messages (compromising the sender's privacy). To achieve this, $\mathsf{AE}$ embeds hidden additional messages within seemingly innocuous ciphertexts where the sender and receiver comply with the dictator's demands and, in doing so, $\mathsf{AE}$ uncovers novel structural properties of encryption mechanisms. One methodology that extends the capability of a ciphertext is to embed the hidden anamorphic message in the randomness used in encryption. However, not all schemes reveal this randomness as part of the decryption process! Here, we unveil a conceptually simple yet general new methodology that achieves $\mathsf{AE}$. It is based on the concept of $\textit {Trapdoor-Aided Randomness Recovery}$ by which one can generate special key pairs $(\mathsf{pk},\mathsf{sk})$ that are still indistinguishable from honestly generated key pairs but possess an associated trapdoor $\mathsf{td}$ that first allows for randomness extraction from a ciphertext (and nothing more). Secondly, importantly and differently from prior proposals, the new trapdoor should be different from and computationally independent of "the decryption trapdoor key." Primarily, this new methodology allows for a generic construction of $\textit{public-key}~\mathsf{AE}$ which is a notion introduced at Crypto 24, where, to date, the only known public-key anamorphism relied on a specific CCA encryption scheme. Note that public-key $\mathsf{AE}$ eliminates the need for a preliminary private interaction between the receiver and the sender, thus greatly extending the applicability of anamorphism. In addition to obtaining public-key anamorphism, the new methodology, in turn, generically allows for extended anamorphic properties: Specifically and significantly, the methodology allows protections against a dictator that may ask for the randomness employed by the sender. We then show concrete instantiations of the above methodology based on known lattice-based schemes. Specifically, due to the new methodology, we give efficient anamorphic versions of the Dual Regev scheme and the Lindner-Peikert scheme. Technically, we first define a new problem, called $\textit{randomness finding}~(\mathsf{RFinding})$, which requires that even if the adversary obtains the receiver's secret key, then, while it can decrypt, it cannot fully recover the randomness from the ciphertext. Secondly, we reduce the standard LWE assumptions to the hardness of $\mathsf{RFinding}$ for both schemes. Notably, in both schemes we achieve public-key anamorphism utilizing the "trapdoor techniques for lattices" introduced by Micciancio and Peikert at Eurocrypt 2012.

Homomorphic Signatures (HS) enable the authentication of data that has been processed by an untrusted party, allowing a verifier to check the correctness of a computation without access to the original signed inputs. Since their introduction, HS have evolved from algebraically restricted linear schemes to expressive non-linear and Fully Homomorphic Signature (FHS) constructions, spanning diverse cryptographic assumptions and security models. This paper presents a Systematization of Knowledge (SoK) on homomorphic signatures. We organize existing schemes along key dimensions including functional expressiveness, underlying cryptographic primitives, security notions (selective vs. adaptive, single-key vs. multi-key), and privacy guarantees such as context hiding. This unified perspective highlights a fundamental shift from algebraic constructions toward proof-based and post-quantum designs, as well as the growing importance of Multi-Key Homomorphic Signatures (MKHS) for decentralized settings. We conclude by identifying open problems and emerging directions that must be addressed to bridge the gap between theoretical HS constructions and practical verifiable computation.

We analyzed in depth the Homomorphic Secret Sharing construction applied for Pseudorandom Correlation Function, and we obtained interesting results for various applications. In this paper, we discuss how the PCF can be achieved using the Damgard-Jurik HSS schema by solving the distance function over a ciphertext parametric space of \(\mathbb{Z}^{*}_{n^{\zeta + 1}}\), performing the distributed multiplication protocol as the base building block for our PCF. We created a weak PCF for Vector-OLE via 1-depth HSS circuit, furthermore, via what we called pre-computation with RO-less, we achieved a strong PCF for V-OLE between two parties correct against anhonest-but-curious adversary \(\mathcal{A}_{\mathsf{hbc}}\) and fail-safe secure against an active adversary \(\mathcal{A}_{\mathsf{poly}}\). We also extended our main construction by describing a silent approach in two different ways described as semi-silent by a pre-sampling assumption between the parties and a true-silent protocol execution exploiting the generation of seeds by a PRF. As a last step, we discussed how to build a \(n \times\)OLE generator via our pre-computation session to craft an arbitrary amount of OLE correlation. Our entire paper is further verified by the implementation of a complete and exhaustive library covering all HSS operations, publicly accessible and usable via \(\textit{pip install obliviouspy-HSS}\) and importing \(\textit{import oblivious}\).

We introduce the Algebraic Isogeny Model (AIM): an algebraic model, akin to the Algebraic Group Model in the group setting, for isogenies and supersingular elliptic curves. This model is significantly more general than previous ones, such as the Algebraic Group Action Model: the AIM works with arbitrary isogenies over $\mathbb{F}_{p^2}$, rather than being limited to oriented ones, which gives considerably more power to the adversary. Within this model, we obtain three results. First, we show that any result in the AGAM can be lifted to the AIM, strengthening previous results against more powerful adversaries. Then, we prove that the SQIsign identification protocol is ID-sound: in turn, this implies that SQIsign is EUF-CMA secure in the Quantum Random Oracle Model, resolving (in the AIM) a long-standing open problem. Lastly, we establish the equivalence of the DLOG and CDH problems for all SIDH-derived key exchanges, such as M-SIDH, binSIDH, and terSIDH.

The Functional Decomposition Problem (FDP) involves expressing a given set of multivariate polynomials as a composition of simpler polynomials. Traditional methods, such as Faugère-Perret’s AlgoFDP and its generalized variant MultiComPoly, rely on Gröbner basis computations on ideals generated from derivatives of composed polynomials h = f ◦ g, where f and g are called left-factor and right-factor of h, respectively. The computational cost of these methods increases significantly with both the number of variables and the degrees of the component polynomials in f and g, and their existing complexity estimates are not sufficiently precise. This paper presents two algorithmic improvements to FDP. First, we replace Gröbner basis computation with Gauss–Jordan elimination (GJE) to convert the coefficient matrix into its reduced row-echelon form (RREF), offering a clearer formulation of a key step in MultiComPoly. The resulting algorithm, named RREFComPoly, integrates this change. Additionally, by using exact binomials in place of original binomial approximations and refining the estimation of a critical parameter, we achieve a tighter complexity bound than that of MultiComPoly. Our second and more impactful contribution, PartComPoly, inverts the conventional FDP workflow. Instead of directly recovering the vector space spanned by the component polynomials of g, PartComPoly first uses a localization strategy to recover f and partial information of g with RREFComPoly, and then iteratively reconstructs g by solving a series of linear systems derived from the obtained f and partial information of g. This inversion dramatically reduces computational complexity and expands the solvable domain of FDP, making previously intractable instances – such as those which were claimed to be not computationally exploitable in [1, page 175] – computationally tractable for the first time. Our experiments have confirmed the correctness and validity of both algorithms RREFComPoly and PartComPoly.

The ongoing transition to Post-Quantum Cryptography (PQC) has highlighted the need for cryptographic schemes that offer high security, strong performance, and fine-grained parameter selection. In lattice-based cryptography, particularly for the popular module variants of learning with errors (Module-LWE) and learning with rounding (Module-LWR) schemes based on power-of-two cyclotomics, existing constructions often force parameter choices that either overshoot or undershoot desired security levels due to structural constraints. In this work, we introduce a new class of techniques that are the best of both worlds: structured Module-LWE (or LWR) embeds more algebraic structure than a module such that it significantly improves performance, yet less structure than a power-of-two cyclotomic ring such that it still enables more flexible and efficient parameter selection. We present two concrete instances: a construction based on a radical extension of a two-power cyclotomic field denoted radical Ring-LWE (RR-LWE) or Ring-LWR (RR-LWR), and a cyclotomic block-ring module lattice approach (BRM-LWE or BRM-LWR). These new structured Module-LWE and LWR reduce the required number of uniformly random bytes in its matrix by a factor up to the module rank and allows efficient NTT implementations while enabling more granular security-performance trade-offs. We analyze the security of these constructions, provide practical parameter sets, and present implementation results demonstrating a performance improvement of up to 37% compared to an optimized implementation of ML-KEM. Our techniques apply to both key encapsulation mechanisms and digital signature schemes, offering a pathway to more adaptable and performant PQC standards.

Falcon is a selected signature scheme in the NIST post-quantum standardization. It is an efficient instantiation of the GPV framework over NTRU lattices. While the GPV framework comes with an elegant security proof in theory, Falcon had no formal proof involving concrete parameters for a long time. Until recently, Fouque et al. initiate the concrete security analysis of Falcon-type signatures. They give a formal proof of Falcon+, a minor modification of Falcon, in the random oracle model, whereas they claim that Falcon+-512 barely achieves the claimed 120-bit security for plain unforgeability. % and neither Falcon+-512 nor Falcon+-1024 offer strong unforgeability. Furthermore, they show that standard reductions for strong unforgeability are vacuous for Falcon parameters, necessitating the introduction of a new, non-standard assumption. In this work, we revisit the concrete security analysis of Falcon-type signatures and present positive results. We develop improved analytic tools by leveraging the profile of the NTRU trapdoor bases. This eliminates the security loss for both Falcon+-512 and Falcon+-1024 in the case of plain unforgeability. We also apply our new analysis to the recent weak-smoothness variant Falcon-ws (Zhang et al. Asiacrypt 2025) that admits smaller parameters than Falcon under a non-standard assumption. As a result, we propose new parameters for Falcon-ws allowing for provable security under standard assumptions and signature size 17.8% (resp. 12.8%) smaller than that of Falcon-512 (resp. Falcon-1024) simultaneously. Moreover, we give a refined strong unforgeability security proof by replacing the worst-case analysis with a probabilistic analysis, which leads to a substantial increase in concrete security. Based on this, we show that by using a tighter Gaussian sampler, e.g. the one in Falcon-ws, Falcon-type signatures can achieve concrete security for strong unforgeability closely consistent with the claimed security level while keeping the compact size.

Bitcoin enables decentralized, pseudonymous transactions, but balancing privacy with accountability remains a challenge. This paper introduces a novel dual accountability mechanism that enforces both sender and recipient compliance in Bitcoin transactions. Senders are restricted to spending Unspent Transaction Outputs (UTXOs) that meet specific criteria, while recipients must satisfy legal and ethical requirements before receiving funds. We enhance stealth addresses by integrating compliance attributes, preserving privacy while ensuring policy adherence. Our solution introduces a new cryptographic primitive, Identity-Based Matchmaking Stealth Signatures (IB-MSS), which supports streamlined auditing. Our approach is fully compatible with existing Bitcoin infrastructure and does not require changes to the core protocol, preserving both privacy and decentralization while enabling transaction auditing and compliance.

We present the first practical, round-optimal blind signatures in pairing-free groups. We build on the Fischlin paradigm (EUROCRYPT 2007) where a first signature is computed on a commitment to the message and the final signature is a zero-knowledge proof of the first signature. We use the Nyberg-Rueppel signature scheme as the basis (CCS 1993), it is a well-studied scheme with a verification equation that is sufficiently algebraic to allow efficient proofs, that do not need to make non-black box use of a random oracle. Our construction offers flexibility for trade-offs between underlying assumptions and supports issuance of signatures on vectors of attributes making it suitable for use in anonymous credential systems. As a building block, we show how existing NIZKs can be modified to allow for straight-line extraction. We implement variants of our construction to demonstrate its practicality, varying the choice of elliptic curve and the proof system used to compute the NIZK. With conservative parameters (NIST-P256 and SHA-256) and targeting short proofs, signatures are 1349 bytes long, and on a typical laptop can be generated in under 500ms and verified in under 100ms.

Identity-based signature (IBS) schemes eliminate the need for certificate management, thereby reducing communication and computational overhead. A major challenge, however, is the efficient update or revocation of compromised keys, as existing approaches such as revocation lists or periodic key renewal incur significant network costs in dynamic settings. We address this challenge by introducing a symmetric element that enables key updates in IBS schemes through a single multicast message. Our approach achieves logarithmic network overhead in the number of keys, with constant computation and memory costs. We further propose a general framework that transforms any IBS scheme into a key-updatable IBS scheme ($\mathsf{KUSS}$), and formalize the associated security requirements, including token security, forward security, and post-compromise security. The versatility of our framework is demonstrated through five instantiations based on Schnorr-type, pairing-based, and isogeny-based IBS, and we provide a detailed security analysis.

The NIST lattice-based cryptographic standards are set to be widely adopted, offering solutions to the most common cryptographic needs, namely key establishment and authentication (signature). This shifted the attention to more advanced primitives such as threshold cryptography as well as privacy-enhanced technologies, where the transition is expected to be more complex. This is particularly true in the context of post-quantum anonymous authentication where the existing mechanisms may not match the performance requirements of industrial applications. An important avenue for improvement of said performances is the lattice sampler, which is at the center of these mechanisms. Despite recent progress, prior samplers neglected one component: the tag. The latter is not only necessary for security, but it also impacts the efficiency of the subsequent constructions if not handled properly. In this paper, we introduce a new sampler with an enhanced tag management that yet retain the main features of current samplers, and can thus be used as a plug-in replacement. It offers a sampling quality independent of the tag, allowing for producing preimages that are both smaller and faster to generate than those from the very recent sampler of Jeudy and Sanders (Asiacrypt'25). Far from being anecdotal, plugging it into several advanced authentication mechanisms results in size improvements of up to 30%, while being 35% faster.

Although both blind signatures and adaptor signatures have individually attracted attention, there is little research on combining these primitives so far. To the best of our knowledge, although the only existing scheme is the scheme by Qin et al. (S\&P 2023), it does not consider practical security notions, namely full extractability, unlinkability, and pre-verify soundness, especially against adversaries with rich attack interfaces. In this paper, we propose the first blind adaptor signature scheme that satisfies the above security definitions. We first formalize the security of a blind adaptor signature scheme and prove a relationship between our security definitions and the existing security definitions, as well as showing several gaps in the existing schemes as a technical problem. Our main idea to overcome this problem is to leverage relations that support random self-reducibility instead of additional random numbers for blind signatures. Such a construction can embed relations into the signature components by re-randomizing them with the relations, and hence satisfies all the above security definitions. We then introduce new proof techniques to prove the full extractability by leveraging the unlinkability. We also discuss applications of the proposed scheme.

We introduce a method for efficiently computing $2^a$-isogenies in Legendre form with applications in post-quantum cryptography. An example of a secure application is the Charles-Goren-Lauter (CGL) hash function, which recently saw significant improvement in complexity by Doliskani et al. The majority of work on isogeny computation uses elliptic curves in Montgomery form; this includes the original work on SIDH by Jao, De Feo and Plût and the state of the art implementation of SIKE. Elliptic curves in twisted Edwards form have also been used due to their efficient elliptic curve arithmetic, and complete Edwards curves have been used for their benefit of providing added security against side channel attacks. As far as we know, elliptic curves in Legendre form have not yet been explored for isogeny-based cryptography. Legendre form has the benefit of a very simple defining equation, and the simplest possible representation of the $2$-torsion subgroup. In this work, we develop a new framework for constructing $2^a$-isogenies using elliptic curves in Legendre form, and in doing so optimize Legendre curve arithmetic and $2$-isogeny computations on Legendre curves by avoiding any square root computations.