This paper addresses the challenge of best arm identification in stochastic multi-armed bandit (MAB) models under privacy-preserving constraints, such as in dynamic spectrum access networks where secondary users must privately detect underutilized channels. While previous network security research has explored securing MAB algorithms through techniques such as homomorphic encryption or differential privacy, these methods often suffer from high computational overhead or introduce noise that strictly decreases accuracy. In contrast, this work focuses on lightweight solutions that ensure data confidentiality without compromising the accuracy of best arm identification. We introduce two secure protocols that leverage additive secret sharing and threshold secret sharing. The proposed model, employing aggregation nodes and a comparator node, securely distributes computations to prevent any entity from accessing complete reward or ranking data. Furthermore, the protocol ensures resistance to collusion and fault tolerance, while maintaining computational efficiency. These contributions establish a scalable and robust framework for privacy-preserving best arm identification, offering practical and secure solutions that use MAB methods for network security.

Continuous Group Key Agreement (CGKA) is a primitive with which members of a group can continuously establish shared keys. With every interaction, these members also update their individual, local secrets such that temporary corruptions of these secrets only affect the security of shared keys established shortly before (Forward Security; FS) and after the corruption (Post-Compromise Security; PCS). Due to these interactive updates–possibly enriched by dynamic group membership changes–, CGKA is a very powerful but also very complex primitive. In this work, we limit the power of CGKA to identify and analyze its core components. More concretely, we consider the case that all members of a group are always either senders or receivers. Thus, the interaction is strictly unidirectional from the former to the latter: a group of senders Alice establishes shared keys with a group of receivers Bob. With every shared key, Alice updates her local state to achieve FS and PCS; when receiving an established key, each Bob also updates their local state to achieve FS. This notion naturally lifts the so called Unidirectional Ratcheted Key Exchange concept (Bellare et al., Crypto 2017; Poettering and Rösler, Crypto 2018) to the group setting and, thereby, captures and generalizes Signal's Sender Key Mechanism, which is the core of WhatsApp and Signal's group chat protocols. We modularize this concept of Group Unidirectional RKE (GURKE) by considering either single or multiple senders, single or multiple receivers, and static or dynamic membership on each of both sides of the group. To instantiate these new primitives, we develop a building block called Updatable Broadcast KEM (UB-KEM). Using UB-KEM, our GURKE constructions for static groups only use standard Key Encapsulation Mechanisms (KEMs) and induce only a constant communication overhead. Our GURKE constructions for dynamic groups are based on general Non-Interactive Key Exchange (NIKE) and offer a constant communication overhead as long as the set of members is unchanged; only for adding and removing users, a communication overhead logarithmic in the group size is induced. We discuss the benefits of replacing the Sender Key Mechanism in Signal and WhatsApp with our constructions, and demonstrate their practicality with a performance evaluation of our proof of concept UB-KEM implementation.

The Vector Oblivious Linear Evaluation in the Head (VOLEitH) paradigm has proven to be a versatile tool to design zero-knowledge proofs and signatures in post-quantum cryptography. In this paper, we propose three VOLE-friendly modellings for Proofs of Knowledge (PoK) of a solution of an instance of the Linear Code Equivalence Problem (LEP). For the first two schemes, we propose two new reductions from LEP to the Multivariate Quadratic (MQ) problem, that may be of independent interest for the cryptanalysis of LEP. Instead, the last model is obtained by generalizing a recent work by Bettaieb et al. to the context of monomial matrices instead of permutation matrices. While our proposed schemes exhibit larger signature sizes compared to LESS, they improve the computational efficiency, reducing the overall complexity from $O(n^3)$ to $O(n^2\log n )$ and $O(n^2\log^2 n )$, where $n$ is the length of the code.

In this work we analyze a problem strictly linked with the Rational Reconstruction, which forms the foundation of some post-quantum Quasi-Cyclic Moderate-Density Parity-Check and Quasi-Cyclic Low-Density Parity-Check code-based schemes such as LEDAkem and BIKE. Given a polynomial in a cyclic ring as input, our aim is to recover two polynomials, with specific properties, whose ratio is the input one. The starting point of this work is the paper of Bardet, Dragoi, Luque, and Otmani, which describes some approaches, based on the Extended Euclidean Algorithm, that solves this problem in some specific cases. In comparison to previous work, we define an additional setting in which the problem can be solved. We also provide an alternative approach to estimate the probability of success, by taking into account a requirement that was not considered in the original paper, thus getting a more precise estimation. Finally, we present a key-recovery attack on BIKE, evaluate its computational cost, and compare it with that of the most efficient known attacks. Although this last step is performed specifically on BIKE, the methodology can be extended to other schemes as well.

Transport Layer Security (TLS) is the backbone of the web, allowing clients to establish secure and private channels with servers. DECO (CCS'20) and follow-up works proposed protocols that enable proving the provenance of a TLS response, i.e., that a payload came from a particular server, without needing server-side modifications. Unfortunately, these works are limited to proving Boolean statements over the payload (e.g., age $\ge$ 18) and cannot combine payloads from multiple clients. We introduce TLShare, a framework that extracts authenticated data from a TLS connection and imports it into secure multiparty computation (MPC) or fully homomorphic encryption (FHE), without requiring server-side changes or exposing client credentials. Unlike prior work, TLShare allows the payload itself, not just a predicate about it, to serve as private input to secure downstream computation. TLShare supports combining verifiable inputs across multiple clients and servers, enabling new applications such as privacy-preserving financial risk assessment and collaborative analytics. We design three protocols for TLShare: one for MPC using verifiable secret sharing, and two for FHE using interactive and non-interactive zero-knowledge proofs, each ensuring input authenticity, integrity, and end-to-end privacy. We evaluate all three protocols of TLShare over both LAN and WAN settings, comparing their trade-offs and demonstrating their practicality.

Oblivious Pseudorandom Functions (OPRFs) are fundamental cryptographic primitives essential for privacy-enhancing technologies such as private set intersection, oblivious keyword search, and password-based authentication protocols. We present the first fully adaptive, partially oblivious threshold pseudorandom function that supports proactive key refresh and provides composable security under the One-More Gap Diffie-Hellman assumption in the random oracle model. Our construction is secure with respect to a new ideal functionality for OPRFs that addresses three critical shortcomings of previous models–specifically, key refresh and non-verifiability issues that rendered them unrealizable. In addition, we identify a gap in a prior work's proof of partial obliviousness and develop a novel proof technique to salvage their scheme.

We show that Brauer and a certain class of Hansen chains satisfy the requirements for an addition chain to be closed. This puts these types of addition chain as a subfamily of the so-called closed addition chains.

Artificial Intelligence (AI) has had a profound impact on our contemporary society, and it is indisputable that it will continue to play a significant role in the future. To further enhance AI experience and performance, a transition from large-scale server applications towards AI-powered edge devices is inevitable. In fact, current projections indicate that the market for Smart Edge Processors (SEPs) will grow beyond 70 Billion USD by 2026 [1]. Such a shift comes with major challenges, as these devices have limited computing and energy resources yet need to be highly performant. Additionally, security mechanisms need to be implemented to protect against diverse attack vectors as attackers now have physical access to the device. Besides cryptographic keys, Intellectual Property (IP), including neural network weights, may also be potential targets. The CONVOLVE [2] project (currently in its intermediate stage) follows a holistic approach to address these challenges and establish the EU in a leading position in embedded, ultra-low- power and secure processors for edge computing. It encompasses novel hardware technologies, end-to-end integrated workflows, and a security-by-design approach. This paper highlights the security aspects of future edge-AI processors by illustrating challenges encountered in CONVOLVE, the solutions we pursue including some early results, and directions for future research.

\xoodyak is a finalist of the NIST lightweight cryptography competition, offering both keyed and hash modes. After several years of cryptanalysis, the largest number of \xoodyak hash rounds for which actual collisions was still in vacancy. To the best of our knowledge, one of the most powerful collision attacks on hash functions based on sponge construction is the differential-based attacks using the S-box linearization technique proposed by Qiao \etal (EUROCRYPT 2017). However, the linearization technique requires a large number of degrees of freedom, making it challenging to apply to \xoodyak with a small outer part. On the other hand, the constraint-input and constraint-output imposed on the differential trail of \xoodoo permutation make the exhaustive search for relatively high-probability differential trails in collision attacks extremely costly. In this paper, we present critical observations regarding \xoodoo round function, particularly focusing on its unique $\theta$ and $\chi$ operation. These properties can be leveraged to manually design specific differential trails, referred to as \textit{loop} trails. To efficiently find practical collisions for up to 3 rounds, we develop a SAT model based on these \textit{loop} trails. Finally, we present the first practical collision on 2 rounds and a practical semi-free-start collision on 3 rounds of \xoodyak hash mode. Besides, we improve Dong \etal's (CRYPTO 2024) collision attack on 3-round \xoodyak-\hash from $2^{125.23}$ to $2^{100.93}$ using several linearization strategies. Since we focus on the analysis on collisions during the message absorbing phase of the hash modes, our results are applicable to both \xoodyak-\hash and \xoodyak-\xof.

The hardness of the learning with errors (LWE) problem increases as its noise rate grows. However, all existing LWE-based public-key encryption schemes require the noise rate to be no greater than $o(1/(\sqrt{n}\log n))$. Breaking through this limitation presents an intriguing challenge. In this paper, we construct public-key encryption (PKE) schemes based on the sub-exponential hardness of decisional LWE with polynomial modulus and noise rate ranging from $O(1/\sqrt{n})$ to $o(1/\log n)$. More concretely, we demonstrate the existence of CPA-secure PKE schemes as long as one of the following three assumptions holds. (i) $(n^{\omega(1)},n^{-\omega(1)})-$hardness of decisional LWE with noise rate $O(1/\sqrt{n})$. (ii) $(2^{\omega(n^{1/c_1})},2^{-\omega(n^{1/c_1})})$-hardness of decisional LWE with noise rate $O(1/\sqrt{n^{1-1/c_1}\log n})$ for some constant $c_1>1$. (iii) $(2^{\omega(n/\log^{c_2}n)},2^{-\omega(n/\log^{c_2}n)})$-hardness of decisional LWE with noise rate $O(1/\sqrt{\log^{c_2+1} n})$ for some constant $c_2>0$. \end{itemize} We also construct injective trapdoor function (iTDF) families based on the same hardness assumption as our PKE. To achieve this, we give a generalization of Babai's nearest plane algorithm, which finds a ``common closest lattice point'' for a set of vectors. In addition, we propose a PKE based on the $(2^{\omega(n^{1/2})},2^{-\omega(n^{1/2})})$-hardness of constant noise learning parity with noise (LPN) problem. Our construction is simpler than the construction of Yu and Zhang [CRYPTO 2016] while achieving the same security.

The security of blockchain systems relies on the honest majority assumption. However, strategic mining threatens this assumption, because selfish miners can gain more block rewards than honest miners by attacks such as withholding blocks. Due to its significant implication, blockchain mining games have been studied in PoW and PoS under various settings using different methods. Nonetheless, this paper argues that the practical limitation of random beacons has not been exploited in strategic mining in PoS blockchains. Current PoS blockchains use random beacons to randomly select validators for each slot. However, the randomness is usually fixed for multiple slots, due to the latency of distributed random beacon protocols. This means that validators actually know the exact election results for future slots within an epoch, which contrasts with the Markov process models in previous analysis. In this paper, we formalize this ”Lookahead Property” and present Lookahead-Aware Mining (LAM), a deterministic optimal strategy that exploits the predictability of epoch-based leader schedules. By mapping the mining process to a Weighted Interval Scheduling problem on the difference of prefix sums, we derive an $O(T \log T )$ algorithm that allows adversaries to compute the exact optimal attack strategy in real-time. Our simulations demonstrate that LAM enables miners with as little as 5% stake to outperform honest mining, significantly lowering the security threshold compared to probabilistic MDP-based models which require >30% stake to be profitable.

With the advancement of deep learning techniques, Deep Learning-based Non-profiled Side-Channel Analysis (DL-NSCA) can automatically learn and combine features, making it a promising method that can skip the manual and precise selection of Points of Interest (PoIs). Existing DL-NSCA methods assume that the attacker can identify a short leakage interval (usually less than 5000 points) containing PoIs from raw traces (more than 100,000 points) and then feed the leakage interval into the neural network to recover the key. However, in practice, the attacker often faces a black-box scenario with unknown underlying implementations, making locating the short interval from raw traces challenging, especially when masking countermeasures exist. To address this issue, we propose a lightweight end-to-end DL-NSCA model called convWIN-MCR, which consists of a performance-optimizing component, convWIN, and an accelerator component, MCR. It can efficiently process raw traces without the need to manually identify the short leakage interval. On the public dataset ASCADv1, while the state-of-the-art model Multi-Output Regression (MOR) requires 28,000 traces and 24 minutes to recover the key from the leakage interval with 1,400 feature points, our framework only requires 6,000 traces in 13 minutes to directly analyze raw traces with 250,000 feature points. To further validate the practical applicability of our framework, we successfully crack a commercial USIM card by analyzing its raw traces and recovering its 128-bit AES key.

A growing body of work addresses the security of cryptographic systems in the presence of mass surveillance, a threat made concrete by Snowden’s revelations and the widespread use of spyware against journalists and activists. In this paper, we investigate the security of symmetric encryption faced with simultaneous algorithm substitution attacks (ASAs) and key exfiltration (KE). The security of symmetric encryption in presence of ASAs or KE alone was established but no result deals with their coordinated deployment. Yet, that is a necessary step to be made if we are to achieve actual security against mass surveillance. We formalize this setting, and prove that no scheme alone stands chance against coordinated ASA and KE, by describing a realistic attack. We then describe a new kind of schemes, which make use of externally supplied randomness. We formalize their security and give a construction which provably resists simultaneous ASAs and KE when paired with a verifiable source of randomness, with security bounds in the concrete security spirit.

Encrypted matrix-vector multiplication is a fundamental component of a variety of applications that involve data privacy concerns. Current algorithms utilizing fully homomorphic encryption (FHE) generally use batching to enhance computational efficiency while neglecting the sparsity of the matrices, a characteristic that exists naturally in many practical situations. Alternatively, porting plaintext algorithms that address sparsity may fail to utilize batching and introduce additional privacy concerns. We propose Lodia, an efficient outsourced SpMV algorithm for batched FHE schemes without sacrificing privacy. It only requires $\Theta((n+m)\log(n+m)/s)$ FHE operations, where $n$ is the number of rows/columns, $m$ is the number of non-zero elements of the matrix, and $s$ is the batch size of the FHE scheme. This is optimal for $m=\Omega(n)$ and $m=O(n^\rho)$ for some $\rho<2$ (i.e., $an \le m \le bn^\rho$ asymptotically), covering most practical cases. To our knowledge, no method has been published with better than $\Theta(n^2/s)$ FHE operations, suitable for any sparse matrix, and without privacy concerns. Lodia utilizes a novel low-diagonal decomposition, which decomposes a sparse matrix into a series of special matrices named low-diagonal matrices. Based on a conventional method encoding the matrix in diagonal order, each low-diagonal matrix can be efficiently multiplied by a vector. This results in an efficient SpMV method suitable for any sparse matrix. Experiments show that Lodia practically achieves a speedup of up to $96\times$ compared to baselines that ignore matrix sparsity, and up to $3.6\times$ compared to implementations even with fewer security guarantees. This is the first SpMV solution on encrypted data that can process a substantial matrix with over 8 million rows/columns and 125 million non-zero elements.

LESS is a signature scheme based on the code equivalence problem that has advanced to the second round of the NIST PQC standardization process. While promising, the scheme suffers from relatively large signatures and moderate to slow signing and verification times. Chou, Santini, and Persichetti recently introduced a variant of LESS relying on canonical forms to significantly reduce signature sizes. However, the overall performance impact of this approach remained largely unclear. In this work, we provide the first implementation of the new LESS variant and show that, in its original form, it performs poorly due to the overhead of computing canonical forms in a naïve way. We then introduce a series of algorithmic and implementation-level optimizations that reduce this overhead to about 10%, showing that the signature size reduction comes at minor cost. In addition, we present further improvements to the signature scheme as a whole, as well as a re-parameterization. The resulting scheme achieves speedups of 2.5× to 10× over the Round 1 NIST submission, while maintaining the reduced signature sizes.

Proxy re-encryption is a cryptographic scheme enabling a delegator (user $i$) to delegate its decryption right to a valid delegatee (user $j$) through a proxy, who cannot extract any information about the message during the procedure. An important security notion is the security against collusion between the proxy and the delegatee. In this case, the adversary has the secret key of the delegatee, $\mathsf{sk}_j$, and the re-encryption key, $\mathsf{rk}_{i\to j}$. The master secret security is first formalised by Ateniese et al. (NDSS'05) to capture the secrecy of $i$'s secret key during collusion. This notion was further formalised by Zhou et al. (ASIACRYPT'23) as the indistinguishability of re-encrypted ciphertext against chosen-message attacks, called collusion safety, which implies the master secret security. In this paper, we find that a PRE scheme is not master secret secure as they claimed, and many other schemes were not master secret secure. Then, we propose a generic construction to achieve collusion safety at the cost of doubling the key size from the IND-CPA secure PRE, enjoying a much better generality and efficiency than the existing technique by secret sharing.

This article presents the architectural design of Zero Knowledge Non-Repudiation (ZK-NR), a layered cryptographic protocol enabling post-quantum secure, legally interpretable, and verifiably non-repudiable attestations. Built upon STARK-based zero-knowledge proofs, hybrid post-quantum signatures, and entropy-accumulating ledger anchoring, ZK-NR satisfies the structural properties of both the Q2CSI framework and the NIZK-E model. The protocol achieves semantic interpretability by structurally separating contextual proofs from bounded explanations, while maintaining cryptographic soundness under the Universal Composability framework. Formal UC proofs are deferred to Article A.2 in this series. This article constitutes the first entry in the ZK-NR series, focused specifically on the protocol's architectural and functional design. Subsequent articles will cover its mathematical foundations, implementation strategies, and operational validation using formal verification environments.

Randomness is a fundamental requirement in cryptographic systems, enabling secure encryption, commitments, and zero-knowledge proofs. However, real-world randomness sources often suffer from weaknesses that adversaries can exploit, leading to significant security vulnerabilities. While deterministic randomness extraction from a single min-entropy source is impossible, two-source extractors provide a robust solution by generating nearly uniform randomness from two independent weak sources. Moreover, cryptographic systems must also be resilient to leakage and tampering attacks, necessitating the development of non-malleable two-source extractors. In this work, we construct a two-source non-malleable extractor in the Common Reference String (CRS) model, where a random low-degree polynomial is sampled once and made accessible to independent random sources, the distinguisher, and the tamperer. Our extractor requires only linear min-entropy in both sources and doesn't rely on strong computational assumptions, in contrast to prior constructions requiring computational assumptions such as sub-exponential hardness of the Decisional Diffie-Hellman (DDH) problem. Notably, our construction builds upon and relies on the recent breakthrough proof of the polynomial Freiman-Ruzsa conjecture. A connection of the Freiman-Ruzsa conjecture with two-source extractors was considered in prior work [ZBS11],[AGMR24], but their construction did not achieve non-malleability. Our results advance the state of non-malleable cryptographic primitives, with applications in secure storage, leakage-resilient cryptography, and privacy amplification. By eliminating the need for strong computational hardness assumptions, our techniques provide a more foundational and widely applicable method for randomness extraction. We also show, that the requirements on CRS for our application are so mild that the CRS can be sampled with $2$ party computation even when one of the parties is malicious (setting in which establishing unbiased coins is impossible).

We introduce Coral, a system for proving in zero- knowledge that a committed byte stream corresponds to a structured object in accordance to a Context Free Grammar. Once a prover establishes the validity of the parsed object with Coral, they can selectively prove facts about the object—such as fields in Web API responses or in JSON Web Tokens—–to third parties or blockchains. Coral reduces the problem of correct parsing to a few simple checks over a left-child right-sibling tree and introduces a novel segmented memory abstraction that unifies and extends prior constructions for RAM in zkSNARKs. Our implementation of Coral runs on a standard laptop, and non-interactively proves the parsing of real Web responses (JSON) and files (TOML and C) in seconds. The resulting proofs are small and cheap to verify.

Threshold encrypted mempools protect the privacy of transactions up until the point their inclusion on chain is confirmed. They are a promising approach to protection against front-running attacks on decentralized blockchains. Recent works have introduced two key properties that an encryption scheme must satisfy in order to scale to large scale decentralized blockchains such as Ethereum: Silent Setup [Garg-Kolonelos-Policharla-Wang, CRYPTO'24], demands that a threshold encryption scheme does not require any interaction during the setup phase and only relies on the existence of Public Key Infrastructure. Batched Decryption [Choudhuri-Garg-Piet-Policharla, USENIX'24], demands that an entire block containing $B$ encrypted transactions can be decrypted using communication that is independent of (or sublinear in) $B$, without compromising the privacy of transactions that have not yet been confirmed. While existing constructions achieve either Silent Setup or Batched Decryption independently, a truly decentralized and scalable encrypted mempool requires both properties to be satisfied simultaneously. In this work, we present the first ``Batched Threshold Encryption scheme with Silent Setup'' built using bilinear pairings. We provide formal definitions for the primitive, and prove security in the Generic Group Model. We provide several optimizations and implement our scheme to evaluate its performance. Our experiments demonstrate its efficiency for deployment in blockchain systems.

Cascader has been introduced as a new key exchange protocol based on iterative multiplicative recurrence. This short note presents a practical shared key recovery attack on the Cascader key exchange protocol. This note also shows that Cascader as a hash function is not collision resistant, presents a new upper bound on the output space of Cascader and shows that a Cascader-based KDF is not secure against an Adaptive Chosen Public Inputs Attack (CPM).

In Submission 2025/1391 to the IACR Cryptology ePrint Archive, the Inverse Discrete Logarithm Problem (IDLP) is introduced and used to build a key exchange protocol and a KEM. The author claims both classical and post-quantum security for IDLP and therefore for the proposed protocols. It is the purpose of this note to give an efficient quantum algorithm for IDLP, based on the algorithm of Shor. We give an implementation of our algorithm, replacing the use of Shor's algorithm with an oracle.

In this work we analyze the various binding properties of combiners for KEMs. We show that several binding properties follow easily for the most general combiner—assuming a collision-resistant hash function—while more performance-oriented combiners require the respective property from one or both of the underlying KEMs. Other binding properties are not obtained as directly and require either more properties of one underlying KEM or the respective property from both KEMs. Additionally, we provide an overview of the binding properties for several combinations of real-world KEMs.

As quantum computing technology rapidly advances, threats to existing symmetric-key and public-key cryptosystems are becoming increasingly real. In this study, we implement a SHA-1 quantum circuit that operates efficiently in a quantum computing environment. We optimize the quantum circuit, focusing on minimizing total circuit depth, a key performance indicator of quantum algorithms. The SHA-1 quantum circuit implementation used 985 qubits, resulting in a measured circuit depth of 9,026. Furthermore, by integrating this optimized circuit with the Grover algorithm, we establish the foundation for an efficient quantum attack on the SHA-1 algorithm. This research is significant not only because it presents a resource-efficient SHA-1 quantum implementation but also because it enables accelerated attacks in a quantum computing environment.

Data availability sampling (DAS) is an important technique to horizontally scale consensus protocols without compromising on the number of adversarial nodes that can be tolerated. DAS is on the technical roadmap of major blockchains such as Ethereum. A major challenge for DAS schemes, that has not been formally studied in the literature, is how incomplete shares can be repaired. The need for repairing data shares motivates key aspects of Ethereum's DAS-based sharding vision called "Danksharding". In this work, we make two contributions. First, we provide a new definitional framework that formalizes the notion of local repair, along with the security guarantees that a DAS scheme must provide. Second, we propose a new DAS scheme designed with efficient local repair in mind, based on locally-correctable multiplicity codes. To facilitate using these codes, we introduce a new multivariate polynomial commitment scheme that (i) supports efficient openings of partial derivatives of a committed polynomial, (ii) supports fast batch opening proof generation at many points, and (iii) has an algorithm to recompute (repair) opening proofs at a point from only a few other proofs. The proposed scheme improves upon the state-of-the-art Ethereum PeerDAS scheme, deployed in December 2025, in storage overhead, local repair bandwidth and coordination, while only slightly increasing dispersal cost and sampling bandwidth. As an additional benefit, our construction also supports efficient partial reconstruction, i.e., retrieving parts of the stored data. All of our techniques readily carry over to data availability schemes based on verifiable information dispersal (VID) as well.

Incrementally Verifiable Computation (IVC) allows one to prove the correctness of a computation of potentially unbounded length (or, depth) in an incremental way, while a computationally weak client can efficiently check its correctness in time sublinear in the computation's length. IVC are of practical relevance; yet, most existing IVC schemes are only provably secure for constant-depth computations. Arguing their security for computations of polynomial depth relies on heuristic assumptions, raising both theoretical and practical concerns. More generally, it remains unclear whether these schemes are genuinely insecure at superconstant depths or whether our current proof techniques are simply insufficient. In this work, we delve into the security foundations of incremental proof systems, while at the same time looking for new approaches to prove security at superconstant depths. To this end, we study the relation between the depth of the target computation and IVC security as a question in its own right. Specifically, we ask: - Can we prove an IVC secure at depth $d =\omega(1)$ if it satisfies a "weak" security property at some "larger" depth $D$? We uncover a surprising connection between infinitely-often soundness (guaranteed to hold only for some infinite set of parameters) and standard soundness in IVC: a scheme that is infinitely-often sound at $D$ depth achieves standard soundness at some "smaller" depth $d=o(D)$. - How does a proof system's security degrade with depth? More precisely, if a scheme loses negligible soundness beyond (e.g.) $O(1)$ depth---the current provable frontier of most practical schemes---can we at least achieve \textit{noticeable} (but arbitrarily low) soundness for \textit{some} superconstant depth? We show the answer is negative. - Depth boosting: If there exists an IVC scheme secure at depth $d$, does there exist one secure at a "greater" depth? We show a simple and black-box boosting technique: given an IVC secure at depth $d$, we can construct one secure at depth $D = d^\rho$ for any function $\rho$ such that $d^\rho$ is polynomially bounded ($\rho$ can even be superconstant). This allows us to systematically amplify security from modest depths to much greater ones (e.g., constant to polynomial depth, with only a logarithmic overhead). Our results uncover a nuanced landscape of depth, efficiency, and security in IVC, and new strategies to prove security beyond $O(1)$ depth. They also apply to non-deterministic computations and other soundness notions, including incremental functional commitments (IFC), a streaming variant of functional commitments that we introduce.

The World Wide Web Consortium (W3C) has established standards for decentralized identities (DIDs) and verifiable credentials (VCs). A DID serves as a unique identifier for an entity, while a VC validates specific attributes associated with the DID holder. To prove ownership of credentials, users generate verifiable presentations (VPs). To enhance privacy, the W3C standards advocate for randomizable signatures in VC creation and zero-knowledge proofs for VP generation. However, these standards face a significant limitation: they cannot effectively verify cross-domain credentials while maintaining anonymity. In this paper, we present Anonymous Verifiable Presentations with Extended Usability (AVPEU), a novel framework that addresses this limitation through the introduction of a notary system. At the technical core of AVPEU lies our proposed randomizable message-hiding signature scheme. We provide both a generic construction of AVPEU and specific implementations based on Boneh-Boyen-Shacham (BBS), Camenisch-Lysyanskaya (CL), and Pointcheval-Sanders (PS) signature. Our experimental results demonstrate the feasibility of these schemes.

All-but-one Vector Commitments (AVCs) allow a committed vector to be verified by randomly opening all but one of the committed values. Typically, AVCs are instantiated using Goldwasser-Goldreich-Micali (GGM) trees. Generating these trees comprises a significant computational cost for AVCs due to a large number of hash function calls. Recently, correlated GGM (cGGM) trees were proposed to halve the number of hash calls and Batched AVCs (BAVCs) using one large GGM tree were integrated to FAEST to form the FAEST version 2 signature scheme, which improves efficiency and reduces the signature size. However, further optimizations on BAVC schemes remain possible. Inspired by the large-GGM based BAVC and the cGGM tree, this paper proposes BACON, a BAVC with aborts scheme by leveraging a large cGGM tree. BACON executes multiple instances of AVC in a single batch and enables an abort mechanism to probabilistically reduce the commitment size. We prove that BACON is secure under the ideal cipher model and the random oracle model. We also discuss the possible application of the proposed BACON, i.e., FAEST version 2. Furthermore, because the number of hash calls in a large cGGM tree is halved compared with that used in a large GGM tree, theoretically, our BACON is more efficient than the state-of-the-art BAVC scheme.

The blocks in the Bitcoin blockchain record the amount of work W that went into creating them through proofs of work. When honest parties control a majority of the work, consensus is achieved by picking the chain with the highest recorded weight. Resources other than work have been considered to secure such longest-chain blockchains. In Chia, blocks record the amount of disk-space S (via a proof of space) and sequential computational steps V (through a VDF). In this paper, we ask what weight functions Γ(S,V,W) (that assign a weight to a block as a function of the recorded space, speed, and work) are secure in the sense that whenever the weight of the resources controlled by honest parties is larger than the weight of adversarial parties, the blockchain is secure against private double-spending attacks. We completely classify such functions in an idealized “continuous” model: Γ(S,V,W) is secure against private double-spending attacks if and only if it is homogeneous of degree one in the timed resources V and W, i.e., αΓ(S,V,W)=Γ(S,α V, α W). This includes the Bitcoin rule Γ(S,V,W)=W and the Chia rule Γ(S,V,W) = S · V. In a more realistic model where blocks are created at discrete time-points, one additionally needs some mild assumptions on the dependency on S (basically, the weight should not grow too much if S is slightly increased, say linear as in Chia). Our classification is more general and allows various instantiations of the same resource. It provides a powerful tool for designing new longest-chain blockchains. E.g., consider combining different PoWs to counter centralization, say the Bitcoin PoW W_1 and a memory-hard PoW W_2. Previous work suggested to use W_1+W_2 as weight. Our results show that using e.g., √(W_1)·√(W_2) or min{W_1,W_2} are also secure, and we argue that in practice these are much better choices.

Recent regulations such as the GDPR have given the right to be forgotten to users, which requires that they can ask for the deletion of their data. Yet, enforcing such deletions for machine learning (ML) models remains challenging, especially when servers are untrusted or may ignore requests. To address this issue, we present the first ML model to support oblivious exact unlearning, in which the deletion is computationally indistinguishable from regular training or inference. This ensures that unlearning can be enforced without revealing its occurrence to the server. Our construction is based on Extremely Randomized Trees (ERTs), which are well-suited for encrypted training and efficient unlearning. More precisely, their randomized data-independent structure enables exact sample removal without retraining. We instantiate our protocol within the TFHE framework by designing a non-interactive procedure for encrypted updates, traversals and inference. Our implementation shows that encrypted ERTs train up to 2.4× faster than prior encrypted random forests while maintaining a comparable accuracy.

Verifiable Databases (VDBs) allow clients to outsource data storage without trusting the provider: a client holding only a short digest can verify any query response using a compact server-provided proof. Given the ubiquity of both databases and outsourced storage, VDBs address a fundamental need. Our work advances the state of the art in VDB design. Our main contribution is $\mathsf{qedb}$, a simple and performant construction for SQL queries based on bilinear pairings. Like some prior VDB schemes, $\mathsf{qedb}$ leverages features specific to the database setting; however, it differs from such approaches in its technical blueprint, the breadth of supported queries, and performance. Notably, it is the first scheme of its kind with proof size independent of database size and without quadratic scaling for storage or preprocessing. Compared to VDB solutions based on general-purpose proofs, $\mathsf{qedb}$ offers stronger tradeoffs in at least one of the following: provable security, proof size and verification time, or system complexity and maintainability (over an order of magnitude fewer lines of code). As additional contributions, we provide both an implementation of $\mathsf{qedb}$ and new theoretical foundations for VDB design—a new framework modeling $\textit{idealized}$ protocols for verifiable databases, which future works can use in a plug-and-play manner. Through our modular approach we can get more provably secure instantiations of $\mathsf{qedb}$ $\textit{for free}$, including a post-quantum one from lattices.

Fully Homomorphic Encryption (FHE) and Post-Quantum Cryptography (PQC) involve polynomial multiplications, which are a common performance bottleneck. To resolve this bottleneck, polynomial multiplications are often accelerated in hardware using the Number-Theoretic Transformation (NTT) or the Fast Fourier Transformation (FFT). In particular, NTT operates over modular rings while FFT operates over complex numbers. NTT and FFT are widely deployed in applications with diverse parameter sets, leading to long design times for hardware accelerators. Existing hardware generation tools have limited functionality since they do not support generic on-the-fly twiddle factor generation or different memory-related optimizations. This paper improves the hardware design process and presents a generic and flexible tool to generate FFT and NTT architectures. In contrast to prior work, we combine on-the-fly twiddle factor generation and stall-free memory accesses. Moreover, we enhance hardware design flexibility through memory-optimized or routing-optimized design strategies. While our memory-optimized strategy minimizes twiddle factors in ROM, our routing-optimized strategy allows significantly higher clock frequencies on FPGAs. These optimization strategies allow effective customization of NTT/FFT architectures, spanning from low-end PQC to high-end FHE accelerators. Compared to existing works, we reach up to 15.9x lower latency and up to 7.4x improved ATP for FFT applications such as the Falcon signature scheme. Considering other NTT tools, we decrease latency by up to 1.8x and 2x for PQC and FHE parameter sets, respectively.

In this work, we study the communication complexity of MPC achieving perfect security with optimal resilience ($t<n/3$). We ask the question: ``Is it possible to build a perfectly secure MPC for arithmetic circuits of size $|C|$ with optimal resilience with communication of $o(|C|\cdot n)$ field elements?'' On the positive side, we construct a perfectly secure MPC protocol for general arithmetic circuits with communication complexity of $O(|C|)$ elements assuming preprocessing data of size $O(|C|)$, where the preprocessing data consists of packed Beaver triples over bivariate polynomials. Furthermore, we show that packed Beaver triples over bivariate polynomials can be prepared at an amortized cost of $O(1)$ elements plus $O(1)$ three-party Beaver triples per secret. On the negative side, we establish a communication lower bound proving that preparing packed Beaver triples over bivariate polynomials requires at least $\Omega(n)$ elements of communication per secret. This lower bound is derived by first proving a communication lower bound for verifying the correctness of packed Beaver triples with perfect security with abort, and then efficiently reducing the task of verifying packed Beaver triples to preparing packed Beaver triples over bivariate polynomials. To match this bound, we give a concrete construction for preparing packed Beaver triples over bivariate polynomials with $O(n)$ elements per secret, demonstrating the tightness of our lower bound. Our proof technique also extends to show that for the task of computing the inner-product of two length-$|C|$ vectors, any MPC protocol that achieves perfect security with abort requires either $\Omega(|C|\cdot n)$ elements of communication or $\Omega(|C|)$ elements of preprocessing data.

Common blockchain protocols are monolithic, i.e., their security relies on a single assumption, e.g., honest majority of hashing power (Bitcoin) or stake (Cardano, Algorand, Ethereum). In contrast, so-called optimistic approaches (Thunderella, Meshcash) rely on a combination of assumptions to achieve faster transaction liveness. We revisit, redesign, and augment the optimistic paradigm to a tiered approach. Our design assumes a primary (Tier 1) and a secondary (Tier 2, also referred to as fallback) blockchain, and achieves full security also in a tiered fashion: If the assumption underpinning the primary chain holds, then we guarantee safety, liveness and censorship resistance, irrespectively of the status of the fallback chain. And even if the primary assumption fails, all security properties are still satisfied (albeit with a temporary slow down) provided the fallback assumption holds. To our knowledge, no existing optimistic or tiered approach preserves both safety and liveness when any one of its underlying blockchain (assumptions) fails. The above is achieved by a new detection-and-recovery mechanism that links the two blockchains, so that any violation of safety, liveness, or censorship resistance on the (faster) primary blockchain is temporary—it is swiftly detected and recovered on the secondary chain—and thus cannot result in a persistent fork or halt of the blockchain ledger. We instantiate the above paradigm using a primary chain based on proof of reputation (PoR) and a fallback chain based on proof of stake (PoS). Our construction uses the PoR and PoS blockchains in a mostly black-box manner—where rather than assuming a concrete construction we distill abstract properties on the two blockchains that are sufficient for applying our tiered methodology. In fact, choosing reputation as the resource of the primary chain opens the door to an incentive mechanism—which we devise and analyze—that tokenizes reputation in order to deter cheating and boost participation (on both the primary/PoR and the fallback/PoS blockchain). As we demonstrate, such tokenization in combination with interpreting reputation as a built-in system-wide credit score, allows for embedding in our two-tiered methodology a novel mechanism which provides collateral-free, multi-use payment-channel-like functionality where payments can be instantly confirmed.

Message dissemination is a fundamental building block in distributed systems and guarantees that any message sent eventually reaches all parties. State of the art provably secure protocols for disseminating messages have a per-party communication complexity that is linear in the inverse of the fraction of parties that are guaranteed to be honest in the worst case. Unfortunately, this per-party communication complexity arises even in cases where the actual fraction of parties that behave honestly is close to 1. In this paper, we propose an optimistic message dissemination protocol that adopts to the actual conditions in which it is deployed, with optimal worst-case per-party communication complexity. Our protocol cuts the complexity of prior provably secure protocols for 49% worst-case corruption almost in half under optimistic conditions and allows practitioners to combine efficient heuristics with secure fallback mechanisms.

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 Syndrome Decoding Problem (SDP) underpins the security of most code-based cryptographic schemes, and Information Set Decoding (ISD) algorithms are the fastest known solvers for most parameter sets. While ISD is well developed in the binary setting, the landscape for non-binary ISD is less mature. Most $q$-ary methods are straightforward generalizations of their binary counterparts, with the recent projective Stern algorithm being the only exception. However, no existing algorithm is designed to leverage the specific algebraic properties of extension fields. This research gap -- highlighted by the first-round NIST PQC proposal SDitH -- motivates our central question: is decoding over an extension field fundamentally easier than over a prime field of similar size? This work explores whether the algebraic structure of extension fields can accelerate ISD. We analyze several techniques for translating the SDP to the base field, including the expansion map, subfield subcodes, and the trace map. We also develop new BJMM variants that restrict base list vectors to “small” field elements, aiming to counter the performance loss of advanced ISD when $q$ is large. Contrary to our initial intuition, our results provide no evidence of an asymptotic speedup, suggesting that decoding over extension fields is not easier than over prime fields. Additionally, we make two contributions of independent interest: we show that a three-level BJMM algorithm gives a slight improvement over the two-level version for small fields, and we extend Meurer’s proof to show that the complexity of advanced ISD algorithms converges to Prange’s, even when parameters grow simultaneously.

In this paper, we present a simple meet-in-the-middle attack that requires low data and memory resources. To evaluate the complexity of the attack, we also propose an automated tool that calculates the time, data, and memory complexities based on the suggested matching points. Our method operates at the bit level and employs a known-plaintext attack, with no constraints on the attacker's choice of data. We apply our tool on various lightweight block ciphers, including CRAFT, Midori, WARP, PRESENT, and ARADI. For CRAFT, our tool successfully identified an attack targeting 15 rounds using 3 known plaintexts. In the case of Midori64 and Midori128, the tool proposed attacks on 5 rounds with 16 known plaintexts and 7 rounds with 3 known plaintexts, respectively. For WARP, the tool discovered an attack on 18 rounds utilizing 7 known plaintexts. Additionally, for PRESENT80, the tool identified an attack on 6 rounds with 18 known plaintexts, and for ARADI, an attack on 5 rounds with 28 known plaintexts was determined.

The paper defines a novel type of consensus for a distributed smart contract system, named RGB, which is based on the concept of client-side validation, separating the contract state and operations from the blockchain. With this approach, contracts are sharded (each contract is a standalone shard), kept, and validated only by contract participants, providing native scalability and privacy mechanisms, exceeding all existing blockchain-based smart contract systems while not compromising on security or decentralization. The system is designed to operate on top of compatible layers 1, such as an UTXO-based blockchain (e.g., Bitcoin) without relying on it for transaction ordering or state replication. Instead, RGB keeps the state client-side, operating as partially replicated state machines (PRiSM). It employs a novel SONIC (State machine with Ownership Notation Involving Capabilities) architecture, which provides capability-based access control to the contract state, individually owned and operated by a well-defined contract parties via novel single-use seal mechanism. RGB does state validation using zk-AluVM virtual machine, designed to support zk-STARK provers. It has a single security assumption of the collision-resistance hash function and, thus, is quantum-secure. The proposed RGB consensus is distinct from traditional blockchain-based smart contract systems; it is scalable, provably-secure, and formally verifiable.

KEM-to-PAKE compilers have been recently proposed to leverage post-quantum KEM standardization efforts. These typically follow the Encrypted Key Exchange (EKE) paradigm, where the KEM public key is encrypted under a password. While KEM implementations generally aim to execute all secret-dependent computations in constant time, such guarantees do not always extend to computations that depend only on the public key, as public keys are generally assumed to be public. A notable example is ML-KEM, where public keys include a short seed from which a large matrix is expanded prior to algebraic computations. This expansion procedure relies on rejection sampling which is, typically, implemented as a variable-time algorithm. However, compilers that follow the EKE paradigm must treat the public key as secret, since knowledge of the public key hidden in a ciphertext enables an offline dictionary attack on the password; therefore, instantiating these compilers with off-the-shelf implementations of ML-KEM or encrypting the public key under a password using variable-time methods (e.g., cycle walking or rejection sampling, as proposed in related PAKE literature) can be problematic. In this paper we show two approaches which yield ML-KEM-based PAKEs resilient to timing attacks. First, we explore constant-time alternatives to ML-KEM rejection sampling, but as one might expect, such methods impose a performance penalty on ML-KEM. Our second approach introduces a new ML-KEM-to-PAKE compiler that mitigates this issue by design: our proposal transmits the seed in the clear, decoupling password-dependent computations from the seed expansion step. This means that off-the-shelf implementations of ML-KEM can be used. Our new protocol Tempo builds on an idea from CHIC (Asiacrypt'24), which considered splitting the KEM public key, and extends the NoIC protocol and proof (ePrint:2025/231) to show protocol simulation in the UC framework, assuming ML-KEM security under adversarially chosen seeds. We justify this assumption via a new hardness assumption, which we call Oracle-MLWE, and show that it is asymptotically equivalent to the MLWE problem in the Random Oracle Model.

The advent of quantum computing threatens the security assumptions underpinning classical public-key cryptographic algorithms such as RSA and ECC. As a response, the cryptographic community has focused on developing quantum-resistant alternatives, with hash-based signature schemes emerging as a compelling option due to their reliance on well-understood hash functions rather than number-theoretic hard- ness assumptions. This paper presents a comprehensive review of hash- based signature schemes, including Lamport, WOTS, XMSS, XMSSMT , and SPHINCS+, examining their structural design, key generation, sign- ing, and verification processes. Emphasis is placed on their classification as stateful and stateless schemes, as well as their practical integration us- ing Merkle trees and address structures. Furthermore, the paper analyzes several notable cryptanalytic attacks-such as intermediate value guess- ing, Antonov’s attack, multi-target attacks, and fault injection strate- gies-that pose risks to these constructions. By discussing both their strengths and vulnerabilities, this work highlights the viability of hash- based signatures as secure and efficient candidates for post-quantum digital signatures.

In this work, we present a comprehensive analysis of QSF, the KEM combiner used by X-Wing (Communications in Cryptology 1(1), 2024). While the X-Wing paper focuses on the application of QSF to ML-KEM-768 and X25519, we discuss the combiner’s applicability to other post-quantum KEMs and ECDH instantiations. Particularly, we establish the compatibility of QSF to KEMs based on variants of the Fujisaki-Okamoto transform by proving ciphertext second-preimage resistance (C2PRI) for these variants. Building on these results, we show that QSF is compatible with, to the best of our knowledge, all post-quantum KEMs currently standardized or considered for standardization—including ML-KEM, (e)FrodoKEM, HQC, Classic McEliece, and various NTRU variants. Notably, this means these schemes can be used with QSF to construct PQ/T hybrid KEMs. In addition, we introduce QSI, a variant of QSF that combines two KEMs by hashing their shared keys, yielding a KEM that is IND-CCA-secure as long as one constituent KEM is IND-CCA-secure and the other is C2PRI-secure. We establish the same compatibility results for QSI as for QSF. Finally, we analyze both QSF and QSI regarding (their preservation of) the recently introduced family of binding properties for KEMs.

Let $N = pq$ be the product of two balanced prime numbers $p$ and $q$. In 2023, Cotan and Te\c seleanu introduced a family of RSA-like cryptosystems based on the key equation $ed - k(p^n - 1)(q^n - 1) = 1$, where $n \geq 1$. Note that when $n = 1$, we obtain the classical RSA system, while $n = 2$ yields the variant proposed by Elkamchouchi, Elshenawy, and Shaban. In this paper, we present a novel attack that combines continued fractions with lattice-based methods for the case $n = 6$. This represents a natural continuation of previous research, which successfully applied similar techniques for $n = 1, 2, 4$.

In smart grid (SG), key agreement protocols (KAPs) are used as one of the most prevalent means to establish secure data transmission channels between smart meters (SMs) and service providers (SPs). Quite recently, Wu et al. have indicated the vulnerability of Hu et al.'s KAP to key compromise impersonation (KCI) attack and proposed a security-enhanced one for secure communications of SMs and SPs in SG. Not to undermine the noteworthy contributions of their work, this comment demonstrates that their own KAP, i.e., Wu et al.'s scheme is still vulnerable to KCI attack. Accordingly, we suggest a simple modification to fix the KCI attack issue. Our attack procedure gives some delicate hints to scholars to protect their schemes against the KCI attack in future researches.

An important requirement in synchronous protocols is that, even when a party receives all its messages for a given round ahead of time, it must wait until the round officially concludes before sending its messages for the next round. In practice, however, implementations often overlook this waiting requirement. This leads to a mismatch between the security analysis and real-world deployments, giving adversaries a new, unaccounted-for capability: the ability to ``peek into the future.'' Specifically, an adversary can force certain honest parties to advance to round $r+1$, observe their round $r+1$ messages, and then use this information to determine its remaining round $r$ messages. We refer to adversaries with this capability as ``super-rushing" adversaries. We initiate a study of secure computation in the presence of super-rushing adversaries. We focus on understanding the conditions under which existing synchronous protocols remain secure in the presence of super-rushing adversaries. We show that not all protocols remain secure in this model, highlighting a critical gap between theoretical security guarantees and practical implementations. Even worse, we show that security against super-rushing adversaries is not necessarily maintained under sequential composition. Despite those limitations, we present a general positive result: secret-sharing based protocols in the perfect setting, such as BGW, or those that are based on multiplication triplets, remain secure against super-rushing adversaries. This general theorem effectively enhances the security of such protocols ``for free.'' It shows that these protocols do not require parties to wait for the end of a round, enabling potential optimizations and faster executions without compromising security. Moreover, it shows that there is no need to spend efforts to achieve perfect synchronization when establishing the communication networks for such protocols.

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.

This paper presents FLEX (Fraud proofs with Lightweight Escrows for eXits), a garbled circuit-based protocol designed to facilitate two-party disputes on Bitcoin without requiring permanent security bonds. FLEX enables conditional security deposits that are only activated in the event of a dispute, reducing the financial overhead for both parties. The main goal of FLEX is to improve the capital efficiency of BitVM-based bridges in a permissioned challenge setting but can also be used to improve the security of any other fraud proof-based protocol such as payment channels. The paper also introduces enhancements that allow faster reimbursements in scenarios where one party's node is unavailable, while preserving security and minimizing race conditions.

We introduce the \(Inverse\ Discrete\ Logarithm\ Problem\) (iDLP) framework, which inverts traditional discrete logarithm assumptions by making the exponent public but deliberately non-invertible modulo the group order, while hiding the base. This creates a many-to-one algebraic mapping that is computationally infeasible under both classical and quantum attack models. Within this framework, we define three post-quantum cryptographic primitives: Inverse Discrete Diffie–Hellman (IDDH), Inverse Discrete Key Encapsulation (IDKE), and Inverse Discrete Data Encapsulation (IDDE). Using a 512-bit modulus (prime or semiprime), a random generator \( g \), and a public exponent \( y \) with \(\gcd(y, \varphi(m)) = d\), the masking function \[ \mathsf{Mask}_{g,y}(x) := g^{x y} \bmod m \] induces a many-to-one mapping that renders discrete logarithm inversion infeasible. Our security analysis shows that known quantum algorithms yield only multiple candidates, requiring exhaustive search among equivalence classes, which remains intractable at 512-bit parameters. We demonstrate efficient prototype implementations with sub-millisecond key operations and AES-GCM-level data throughput. Full source code and parameters are publicly available at \url{https://github.com/AdamaSoftware/InverseDiscrete/}.

Zero-knowledge rollups represent a critical scaling solution for Ethereum, yet their practical deployment faces significant challenges in on-chain verification costs. This paper presents a comprehensive implementation of the Tokamak zkEVM verifier, specifically optimized for the BLS12-381 elliptic curve operations introduced by EIP-2537. We detail the complete verification architecture, from EVM compatible data formatting for pairing checks, multi-scalar multiplication (MSM), and elliptic curve addition, to the non-interactive protocol design between prover and verifier. Our key contribution lies in novel optimization techniques that substantially reduce on-chain verification costs. Through strategic polynomial aggregation and scalar factorization, we minimize G1 exponentiations from 40 to 31, achieving gas savings of 108,000 units per verification. Additionally, we introduce a dynamic barycentric interpolation method that replaces computationally intensive FFT operations, resulting in 92-95% gas reduction for sparse polynomial evaluations. We further present proof aggregation strategies that minimize precompile calls while maintaining the 128-bit security guarantees of BLS12-381. Our implementation demonstrates that careful protocol design and mathematical optimizations can make zk-rollup verification economically viable on Ethereum. The techniques presented are compatible with the upcoming Pectra upgrade and provide a blueprint for efficient on-chain verification of complex zero-knowledge proofs. Experimental results show total gas costs reduced from 857,200 to 748,450 units for complete proof verification, making our approach practical for high-throughput rollup deployments.

Human verification under adversarial information flow operates as a cost-bounded decision procedure constrained by working memory limits and cognitive biases. We introduce the Verification Cost Asymmetry (VCA) coefficient, formalizing it as the ratio of expected verification work between populations under identical claim distributions. Drawing on probabilistically checkable proofs (PCP) and parameterized complexity theory, we construct dissemination protocols that reduce verification for trusted audiences to constant human effort while imposing superlinear costs on adversarial populations lacking cryptographic infrastructure. We prove theoretical guarantees for this asymmetry, validate the framework through controlled user studies measuring verification effort with and without spot-checkable provenance, and demonstrate practical encoding of real-world information campaigns. The results establish complexity-theoretic foundations for engineering democratic advantage in cognitive warfare, with immediate applications to content authentication, platform governance, and information operations doctrine. We are concerned not with verifying ground truth, but with verifying provenance—the integrity of the chain of custody from source to receiver. Our protocols allow a user to efficiently check that a bundle of information is authentic and has not been tampered with, even though the underlying claims may still be right or wrong in substance.

Collaborative zkSNARKs, proposed by Ozdemir and Boneh in 2022, allow a prover to delegate the generation of zkSNARK proofs to multiple servers, without compromising the confidentiality of the secret witness. They enable the use of zkSNARK techniques on computational limited devices in critical applications such as blockchains. However, the running time of each server is at least as slow as computing the proof on a single server. Garg et al. attempted to improve the efficiency in their scheme named zkSaaS using packed secret sharing, but the scheme still requires a powerful central server with linear computation, communication and memory usage. In this paper, we propose a new collaborative zkSNARK scheme with $O(\frac{C}{n}\log\frac{C}{n})$ prover time and $O(1)$ proof size with $n$ servers for a circuit of size $C$. An adversary compromising less than $\frac{n}{4}$ servers cannot learn any information about the witness. The core of our technique lies in a new zkSNARK scheme for the Plonkish constraint system that is friendly to packed secret sharing. We utilize bivariate polynomials to avoid a large Fast Fourier Transform on the entire witness, which was the major bottleneck in prior work. We also construct permutation constraints based on logarithmic derivatives and univariate sumcheck to avoid the computation of prefix products. Finally, we build a bivariate polynomial commitment scheme that can be computed directly on packed secret shares. Experimental results show that for a circuit of size $2^{20}$, with 128 servers, our scheme can accelerate the proof generation by 36.2$\times$ compared to running the zkSNARK on a single server. The prover time of our system is 25.9$\times$ faster than the prior work of zkSaaS. The proof size of our scheme is only 960 Bytes.

The final exponentiation is a crucial step in pairing computations, ensuring cor- rectness and uniqueness of results in pairing-based cryptographic protocols. In this work, we propose an efficient method for computing the hard part of the final exponentiation on BW10-511, BW14-351 and BLS12 curves at 128 bits security level. Our approach reduces the computation cost by optimizing the exponenti- ation sequence and minimizing the number of required multiplications through an improved addition chain strategy. The computation cost of our method for the final exponentiation on these curves is about 25.6%, 33.2% and 10% faster than the previously fastest result on BW10-511, BW14-351 and BLS12 curves respectively. The correctness of our formulas has been verified by a Magma code.

Strong asymmetric password-authenticated key exchange (saPAKE) is the gold standard for password-based authentication. When authenticating using saPAKE, the client holds a cleartext password, and the server holds only a "digest" of the password. The two parties obtain a shared session key if and only if the client password matches the password encoded in the digest. In this work we initiate the study of strong asymmetric fuzzy PAKE (safPAKE), which allows the client and server to obtain a shared session key if the client's password is "close enough" to the password encoded in the digest, according to some policy. safPAKE can be used to tolerate incidental password typos in the PAKE setting, which is becoming a standard industry practice outside the PAKE setting. Our safPAKE functionality supports any "typo policy", and our protocol is practical when there are a small number of permissible mistypings of a password.

Protection of biometric templates is a critical and urgent area of focus. \textbf{IronMask} demonstrates superior recognition performance while protecting facial templates against existing known attacks. In high-level, IronMask can be conceptualized as a fuzzy commitment scheme building on the hypersphere directly. We devise an attack on IronMask targeting on the security notion of renewability. Our attack, termed as \textbf{Probabilistic Linear Regression Attack}, utilizes the linearity of underlying used error correcting code. This attack is the first algorithm to successfully recover the original template when getting multiple protected templates in acceptable time and requirement of storage. We implement experiments on \textbf{IronMask} applied to protect \textbf{ArcFace} that well verify the validity of our attacks. Furthermore, we carry out experiments in noisy environments and confirm that our attacks are still applicable. Finally, we discuss two strategies to mitigate this type of attacks.

Threshold encryption enables a sender to encrypt a message towards $n$ recipients, such that any $t+1$ parties can decrypt the message, whereas any subset of size $t$ cannot. Silent threshold encryption additionally requires that all recipients can generate their public keys independently of each other, without engaging in an interactive distributed key generation protocol. In this work, we consider a relaxed notion of silent threshold encryption with \emph{soft} thresholds. In this setting, we choose parameters $c \in (0,1)$ and $\epsilon >0$, and we only require that $(c - \epsilon)n$ parties cannot, while $(c + \epsilon)n$ parties can decrypt the message. We present a simple blueprint for constructing efficient silent threshold encryption schemes for soft thresholds. Our construction has ciphertexts and recipient public keys, whose sizes are independent of $n$. As an exemplary data point, tolerating $t < n/3$ corruptions and encrypting $1$ MB results in a ciphertext of size $1.072$ MB. When instantiating our construction for the same parameters in a plausibly post-quantum secure manner, we have a ciphertext size of $1.431$ MB. Our construction is proven secure in the presence of \emph{one-shot adaptive corruptions}, a novel notion introduced in this work that conceptually lays between static and fully adaptive corruptions. We believe that the notion itself and our associated proof techniques are of independent interest. In comparison to prior works for the exact threshold setting, we have smaller recipient public keys, we do not rely on strong assumptions, such as indistinguishability obfuscation, or the generic group model, we are plausibly post-quantum secure, and we prove security for a non-trivial notion of adaptive corruptions.

Optimizing Boolean circuits presents a considerable challenge, especially when aiming to construct circuits amenable to Fully Homomorphic Encryption (FHE) schemes. FHE enables arbitrary computations on encrypted data but incorporates a computationally intensive operation called bootstrapping, necessary for reducing noise in ciphertexts to facilitate computations on circuits of arbitrary depth. This operation can consume a substantial amount of time, depending on the size of the circuits. To address this issue, we propose a technique for efficiently synthesizing circuits specific to FHE by utilizing multi-input homogeneous and composite Boolean gates. Following this we develop an automated framework for designing efficient circuits compatible with FHE schemes. In this work, we use Torus-FHE (TFHE) (JoC 2019), a widely used FHE scheme for Boolean circuits due to its fast bootstrapping operation per bit. Existing techniques typically employ either multi-input homogeneous gates or, multi-bit Look-Up tables during circuit synthesis, which often limits their ability to produce highly optimized circuits for FHE. Our approach addresses this limitation by proposing viable multi-input composite gates alongwith the homogeneous gates during circuit synthesis. Additionally, we propose an efficient and lightweight circuit synthesis approach based on graph optimization. Our approach identifies convex sub-graphs in a Directed Acyclic Graph (DAG) representing the input circuit and replaces them with a more compact structure. This results in a reduction of the number of nodes in the DAG and so as the number of Boolean gates in the input circuit. Our proposed framework provides the most efficient Boolean circuits for TFHE till date, achieving up to a 20% improvement in homomorphic evaluation time compared to the state-of-the-art general compiler optimization techniques for TFHE, and it also demonstrates a 4-6× improvement over prior work on FHEW-like schemes.

The Learning with Rounding (LWR) problem, introduced as a deterministic variant of Learning with Errors (LWE), has become a promising foundation for post-quantum cryptography. This Systematization of Knowledge (SoK) paper presents a comprehensive survey of the theoretical foundations, algorithmic developments, and practical implementations of LWR-based cryptographic schemes. We introduce LWR within the broader landscape of lattice-based cryptography and post-quantum security, highlighting its advantages such as reduced randomness, improved efficiency, and enhanced side-channel resistance. We explore the evolution of security reductions from LWR to LWE, including recent advances that support practical parameter regimes and address challenges in both bounded and unbounded sample settings. This paper systematically reviews existing LWR-based schemes --- including Saber, Lizard, Florete, Espada, Sable, and SMAUG --- analyzing their design choices, parameter sets, and performance trade-offs. Furthermore, we examine the impact of LWR on side-channel resistance, failure probabilities, and masking efficiency, demonstrating its suitability for secure and efficient implementations. By consolidating the research spanning theory and practice, this SoK aims to guide future cryptographic design and standardization efforts leveraging LWR.

The current Domain Name System (DNS) infrastructure faces critical vulnerabilities including poisoning attacks, censorship mechanisms, and centralized points of failure that compromise internet freedom and security. Recent incidents such as DNS poisoning attacks on ISP customers highlight the urgent need for resilient alternatives. This paper presents a novel blockchain-based Decentralized Domain Name System (DDNS). We designed a specialized Proof-of-Work blockchain to maximize support for DNS-related protocols and achieve node decentralization. The system integrates our blockchain with IPFS for distributed storage, implements cryptographic primitives for end-to-end trust signatures, and achieves Never Trust, Always Verify zero-trust verification. Our implementation achieves 15-second domain record propagation times, supports 20 standard DNS record types, and provides perpetual free .ddns domains. The system has been deployed across distributed infrastructure in San Jose, Los Angeles, and Orange County, demonstrating practical scalability and resistance to traditional DNS manipulation techniques. Performance evaluation shows the system can handle up to Max Theor. TPS 1,111.1 tx/s (minimal transactions) and Max Theor. TPS 266.7 tx/s (regular transactions) for domain operations while maintaining sub-second query resolution through intelligent caching mechanisms.

The fundamental incompatibility between confidentiality, reliability, and le gal opposability, formalized as the CRO trilemma, imposes an entropic bound Γ_CRO on cryptographic security in contextual adversarial settings. This pa per introduces Q2CSI (Quantum Composable Contextual Security Infras tructure), a layered framework resolving this trilemma through dialectical separation. Q2CSI decomposes security guarantees into three isolated yet composable layers: Iron (reliability: temporal/logging integrity), Gold (con f identiality: semantic entropy preservation), and Clay (opposability: insti tutional interpretability). By embedding entropic constraints into an ex tended Universal Composability (UC) model, Q2CSI achieves Γ_CRO < 0.4, surpassing monolithic designs, while maintaining post-quantum resilience. The architecture is abstractly instantiated with minimal primitives (IND CCA2 encryption, EUF-CMA signatures) and validated via a symbolic UC framework. Proofs demonstrate strict dialectical isolation, bounded contex tual leakage, and compatibility with quantum adversaries. Q2CSI establishes a foundation for legally verifiable post-quantum protocols, with applications in zero-knowledge attestations and regulatory-compliant signatures.

Deep learning-based side-channel analysis (DLSCA) has demonstrated remarkable performance over the past few years. Even with limited preprocessing and feature engineering, DLSCA is capable of breaking protected targets, sometimes requiring only a single attack trace. In the DLSCA context, the commonly investigated countermeasures are Boolean masking and desynchronization. While the exact mechanisms of how DLSCA breaks masking are less understood, the core idea behind handling desynchronization is simple. Convolutional neural networks (CNNs) are shift invariant, allowing them to overcome desynchronization. However, considering the importance and practicality of desynchronization countermeasures, we know remarkably little about the limits of CNNs or how to enhance their capabilities when dealing with desynchronization. In this work, we begin with the theoretical foundations of shift and temporal scale equivariance. Afterward, we build a neural network model allowing such equivariance and test it against several commonly considered targets. Our results demonstrate that equivariant CNNs are robust, easy to design, and achieve excellent attack performance. More precisely, we showcase how such a simple model can even outperform recent transformer-based neural networks. Finally, we demonstrate the practical relevance of scale equivariance by showing how an equivariant CNN can learn leakage from a device operating at one clock frequency and generalize to a device with a different clock frequency, a result not previously demonstrated in DLSCA.

We study additive positive accumulators, which maintain a short digest of a growing set such that each value in the set can prove membership via a generated witness. Due to the compactness of the digest, previously added values may require updated witnesses as the set grows. In this paper, we establish a trade-off between the bit-length of the accumulator value and the number of witness updates. Specifically, we show that if the accumulator value has bit-length \( \mathsf{poly}(\log n) \), where \( n \) is the number of accumulated values, then some values must incur \( \Omega(\log n / \log \log n) \) witness updates. This improves upon the recent \( \omega(1) \) lower bound of [BCCK25] and matches the upper bound in [MQ23]. Building on the framework of [MQR22], we introduce a new combinatorial structure that removes the fixed-update-time assumption. Our approach also applies to Registration-based Encryption [GHMR18], thereby resolving the open problem left in [MQR22]: it shows that the tight lower bound on decryption-update frequency continues to hold even without any fixed-update-time assumption.

Searchable symmetric encryption allows clients to outsource their databases to a semi-trusted cloud server while enabling private searches. The Oblivious Cross-Tag (OXT) protocol is a fundamental approach to conjunctive keyword search, ensuring that search performance scales with the least frequent keyword while introducing keyword pair result pattern (KPRP) and intersection result pattern (IP) leakages. However, recent studies show that the KPRP leakage in OXT can be exploited, allowing the cloud server to infer information about the client database. Several works have aimed to mitigate this issue, with Doris being the first non-interactive OXT-based scheme to hide KPRP and IP leakages. However, this comes at the cost of increased storage overhead. In this work, we propose a Doris-based conjunctive SSE scheme with improved storage efficiency. We replace the XOR filter in Doris with our XEBFF filter, which formalizes XOR filters and Binary Fuse Filters. Additionally, we introduce a frequency estimation approach using Count-Min Sketch to efficiently determine the least frequent keyword, which all previous OXT-based schemes overlook. Our scheme reduces storage overhead by 8% compared to Doris while maintaining search performance. With our s-term selection protocol, we ensure that search operations typically scale with the least frequent keyword.

The Lattice Isomorphism Problem (LIP) is a relatively recent cryptographic assumption whose precise hardness remains not fully understood. Certain weak instances have been identified through hull attacks on $p$-ary lattices constructed via Construction A using linear codes with trivial hulls. In this work, we generalize the notion of the hull by introducing ideal-based hulls for Hermitian lattices. We propose a new hull attack targeting lattices derived from Generalized Construction A over number fields, under specific structural conditions. Furthermore, we show that modular lattices offer intrinsic resistance to hull attacks: the hull introduces only a limited variation in the lattice gap, bounded by a factor depending on the root discriminant of the number field. In particular, for modular $\mathbb{Z}$-lattices, the hull gap coincides exactly with the original lattice gap. As a concrete example, we show that the family of Barnes-Wall lattices, which are alternatively unimodular and 2-modular over $\mathbb{Z}$, are resistant to hull attacks.

Ring Signatures allow a user to sign on behalf of an ad-hoc set of public keys, while hiding their identity inside that set. Linkable Ring Signatures (LRS) add the functionality of detecting signatures originating from the same signer. They have found many applications in anonymous transactions and e-voting. The LLRing family of linkable ring signature schemes by Hui and Chau (ESORICS 2024) is one of the more efficient LRS schemes. However, we show that it has an unlinkability vulnerability, meaning an adversary can create more unlinkable signatures than the number of secret keys they own. The vulnerability is caused by the introduction of unwanted structure to base elements used in proofs. We also find a similar attack against the Threshold Ring Referral (TRR) scheme of Ta, Hui, and Chau (Security and Privacy 2025), rendering it unsound. We show how to achieve strong linkability with logarithmic verification complexity in the pairing based setting by first reverting the unsafe construction of base elements, and by also adjusting the arguments of knowledge used in order to maintain efficiency. Concretely, by modifying the Dory argument to fit our scheme we are able to match the performance of LLRing-P. We separate the design and analysis of the scheme from the instantiation of the knowledge arguments, which helps prevent unwanted interactions between the two, and can provide easier upgrades to more efficient proof systems.

In this work, we explore the possibility of unconditionally secure universally composable (UC) commitments, a very relevant cryptographic primitive in the context of secure multi-party computation. To this end, we assume the existence of Physically Uncloneable Functions (PUFs), a hardware security assumption that has been proven useful for securely achieving diverse tasks. In prior work [ASIACRYPT 2013, LNCS, vol. 8270, pp. 100–119] it was shown that a protocol for unconditional UC-secure commitments can be constructed even when the PUFs are malicious. Here, we report an attack to this protocol, as well as a few more issues that we identified in its construction. To address them, first we revise some of the previous PUF properties, and introduce new properties and tools that allow us to rigorously develop and present the security proofs. Second, we propose two different ways for making the commitment scheme secure against the attack we found. The first involves considering a new model where the creator of a PUF is notified whenever the PUF is queried and the second involves restricting adversaries to only being able to create stateless malicious PUFs. Finally, we analyze the efficiency of our schemes and show that our constructions are advantageous in this respect compared to the original proposal.

The syndrome decoding problem is one of the NP-complete problems lying at the foundation of code-based cryptography. The variant thereof where the distance between vectors is measured with respect to the Lee metric, rather than the more commonly used Hamming metric, has been analyzed recently in several works due to its potential relevance for building more efficient code-based cryptosystems. The purpose of this article is to present a zero-knowledge proof of knowledge for this variant of the problem.

This paper introduces Gluon W, a novel stablecoin protocol inspired by nuclear physics and named after the particle responsible for the stability of matter in the universe. The key idea in Gluon W is to split (as in nuclear fission) an existing volatile asset into its stable and unstable components. These components can be merged back (as in nuclear fusion) into the original asset or transmuted into each other (as in nuclear beta decays). Various stability theorems are proven and their proofs are formally verified using the interactive proof assistant Rocq.

Credentials are used to verify a user’s identity and attributes and form the basis of securing user access to the system resources. Users obtain credentials and store them on their (mobile) devices, and present them when needed. Anonymous credentials protect the user’s identity, and ensure unlinkability of multiple showing of the credential. In this paper, we consider a setting where a user is issued multiple credentials in sequence (e.g., for completing courses), and credential subsequences must be presented in order of issuance. We focus on the anonymous credential system where information such as the time of issuing is hidden for anonymity, or settings where there is no global clock and issuing time information is not recorded. We propose a novel order-preserving Proof-of-Credential-Subsequence (PoCS) system called KROM that allows a user that is potentially untrusted, to present a subsequence of their locally stored credentials to a verifier, while the relative chronological order of issuance is preserved. We formalize the security and privacy of KROM and present two constructions: a basic one that is based on Merkle trees and one with batched verification that significantly improves the efficiency of the system. We use KROM to construct an anonymous order-preserving proof-of-location-subsequence system and prove its security. The system enables users to selectively present a subsequence of their visited locations to a verifier or an auditor. The main challenge that is addressed is to ensure that the location information that must be in plaintext, does not breach privacy when used in sequence.

We establish the randomized distributed function computation (RDFC) framework, in which a sender transmits just enough information for a receiver to generate a randomized function of the input data. Describing RDFC as a form of semantic communication, which can be essentially seen as a generalized remote‑source‑coding problem, we show that security and privacy constraints naturally fit this model, as they generally require a randomization step. Using strong coordination metrics, we ensure (local differential) privacy for every input sequence and prove that such guarantees can be met even when no common randomness is shared between the transmitter and receiver. This work provides lower bounds on Wyner's common information (WCI), which is the communication cost when common randomness is absent, and proposes numerical techniques to evaluate the other corner point of the RDFC rate region for continuous‑alphabet random variables with unlimited shared randomness. Experiments illustrate that a sufficient amount of common randomness can reduce the semantic communication rate by up to two orders of magnitude compared to the WCI point, while RDFC without any shared randomness still outperforms lossless transmission by a large margin. A finite blocklength analysis further confirms that the privacy parameter gap between the asymptotic and non-asymptotic RDFC methods closes exponentially fast with input length. Our results position RDFC as an energy-efficient semantic communication strategy for privacy‑aware distributed computation systems.

This paper presents an enhancement to cube-attack-like cryptanalysis by minimizing output-bit dependency on related key bits, thereby improving attack complexity. We construct two distinct initial states differing exclusively in predetermined bit positions. Through independent cube summation and state difference analysis, we observed reduced related key bits dependency for specific output bits. We validate our approach by targeting three Keccak keyed variants Ketje Minor, Keccak-MAC-512 and Keccak-MAC-384, developing a dedicated tool to recover all output-bit superpolies. Using our computational resources, we successfully attacked 4-round of Ketje Minor and 5-round of other variants, confirming both the method's validity and practical applicability. While the best known attacks on these structures reach 7-round, our results improve upon the 5-round. We construct our initial state configurations based on the automated method proposed by Bi et al.\ in \textit{Design, Codes and Cryptography} (2019), and compare our results with theirs. For the 4-round Ketje Minor, we reduce the time complexity from \(2^{20}\) to \(2^{16.8}\); for 5 round Keccak-MAC-512, from \(2^{34}\) to \(2^{31.2}\); and for 5 round Keccak-MAC-384, from \(2^{27.6}\) to \(2^{26.5}\).

Quantum computers pose a critical threat to blockchains that rely on ECDSA, such as Bitcoin and Ethereum, due to public key exposure and lack of post-quantum protections. Existing proposals for migrating to quantum-secure signatures, including hybrid constructions and zero knowledge key updates, often require address changes or fail to secure inactive accounts. In this work, we show that EdDSA-based blockchains like Sui, Solana, Near, and others offer a structural advantage: their keys are deterministically derived from a seed according to RFC 8032, allowing users to prove ownership through zero knowledge without revealing elliptic curve secrets or changing addresses. Our core contribution is a post-quantum secure protocol that uses the EdDSA seed as a witness in a zero knowledge proof to authorize new quantum-safe signatures. This construction supports seamless migration, even for users with publicly exposed keys, and preserves backward compatibility. We formalize a security model for post quantum ready signatures defined to support dual-mode security and backward compatibility and then we prove the security of our core construction via a game-based argument. Finally, we provide an implementation to validate the feasibility of our approach. Our proof of concept implementation shows a practical system and enables a seamless transition, with current benchmarks showing a proving time of $6.2$ seconds, a verification time of $2.3$ seconds, and a proof size of $5.4$ MB using the Ligetron zkVM.

Fully homomorphic encryption (FHE) enables computations over encrypted data without the need for decryption. Recently there has been an increased interest in developing FHE based algorithms to facilitate encrypted matrix multiplication (EMM) due to rising data security concerns surrounding cyber-physical systems, sensor processing, blockchain, and machine learning. Presently, FHE operations have a high computational overhead, resulting in an increased need for low operational complexity algorithms to compensate. We present a novel matrix encoding and EMM algorithm for power-of-2 cyclotomic based rings, utilizing three-dimensional rotations which offer improvements over the one-dimensional rotations used in previous work. We encode each $d \times d$ matrix as a single, batch-encoded, ciphertext, with minimum ciphertext size $d^3$. The proposed algorithm improves the number of plaintext-ciphertext multiplications from $O(d)$ to $O(1)$ and the number of rotations from $O(d)$ to $O(\log_2{d})$. In addition, our work supports rectangular matrix multiplication and matrix packing without incurring additional operations per execution. Benchmarks were obtained with a Microsoft SEAL implementation and compared against leading EMM algorithm, with our work performing $4$ times faster for $16 \times 16$ matrices on consumer hardware. Our algorithm is compatible with existing encrypted machine learning frameworks and can be a drop-in replacement for existing matrix multiplication algorithms for increased speed. The favorable time complexity is well suited for time sensitive encrypted algorithms such as computer vision, controls, and patient health monitoring.

Server authentication assures users that they are communicating with a server that genuinely represents a claimed domain. Today, server authentication relies on certification authorities (CAs), third parties who sign statements binding public keys to domains. CAs remain a weak spot in Internet security, as any faulty CA can issue a certificate for any domain. This paper describes the design, implementation, and experimental evaluation of NOPE, a new mechanism for server authentication that uses succinct proofs (for example, zero-knowledge proofs) to prove that a DNSSEC chain exists that links a public key to a specified domain. The use of DNSSEC dramatically reduces reliance on CAs, and the small size of the proofs enables compatibility with legacy infrastructure, including TLS servers, certificate formats, and certificate transparency. NOPE proofs add minimal performance overhead to clients, increasing the size of a typical certificate chain by about 10% and requiring just over 1 ms to verify. NOPE’s core technical contributions (which generalize beyond NOPE) include efficient techniques for representing parsing and cryptographic operations within succinct proofs, which reduce proof generation time and memory requirements by nearly an order of magnitude.

Privacy-preserving machine learning (PPML) based on cryptographic protocols has emerged as a promising paradigm to protect user data privacy in cloud-based machine learning services. While it achieves formal privacy protection, PPML often incurs significant efficiency and scalability costs due to orders of magnitude overhead compared to the plaintext counterpart. Therefore, there has been a considerable focus on mitigating the efficiency gap for PPML. In this survey, we provide a comprehensive and systematic review of recent PPML studies with a focus on cross-level optimizations. Specifically, we categorize existing papers into protocol level, model level, and system level, and review progress at each level. We also provide qualitative and quantitative comparisons of existing works with technical insights, based on which we discuss future research directions and highlight the necessity of integrating optimizations across protocol, model, and system levels. We hope this survey can provide an overarching understanding of existing approaches and potentially inspire future breakthroughs in the PPML field. As the field is evolving fast, we also provide a public GitHub repository to continuously track the developments, which is available at https://github.com/PKU-SEC-Lab/Awesome-PPML-Papers.

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.

Adaptor signatures extend the functionality of digital signatures by enabling the computation of pre-signatures on messages relative to statements in NP relations. Pre-signatures are publicly verifiable objects that simultaneously hide and commit to a standard signature on the same message. Anyone possessing a valid witness for the statement can adapt the pre-signature into a full signature under the underlying signature scheme. Since adaptor signatures are commonly used as building blocks in larger systems, in particular blockchain protocols, it is natural to seek a security definition in the Universal Composability (UC) framework. Tairi et al. (CCS'23) recently took a first step in this direction by proposing a UC functionality for adaptor signatures. This paper investigates UC-secure adaptor signatures as a primitive, making both negative and positive contributions. On the negative side, we show that the functionality proposed by Tairi et al. suffers from critical limitations: - The functionality fails to guarantee extractability and adaptability, which are core security properties of adaptor signatures, to higher-level protocols. - No adaptor signature scheme can realize the functionality. On the positive side, we propose a new UC functionality that faithfully captures the latest security guarantees of adaptor signatures as formalized via game-based notions by Gerhart et al. (EUROCRYPT'24). - Our functionality guarantees extractability and pre-signature adaptability in a way that is composable and meaningful for higher-level protocols. - We show that it is realizable by an enhanced Schnorr-based adaptor signature scheme that we construct. Our construction maintains compatibility with existing infrastructure and is efficient enough for practical deployment, particularly in Bitcoin-like environments.

In the last few years, the old idea of internal perturbation for multivariate schemes has been resurrected. A form of this method was proposed with application to HFE and UOV and independently by another team for application to Rainbow. Most recently, a newer and more efficient version of internal perturbation was proposed as an enhanced measure for securing HFE for encryption. This efficient method, known as the LL' construction, is designed to add little complexity to HFE decryption while increasing the rank of the resulting map to resist the now very effective cryptanalyses powered by MinRank. The basic idea of the construction is to have two small lists of binary linear forms which when multiplied produce rank $1$ quadratic forms. Random linear combinations of these products are then added to each of the HFE equations, resulting in a masked HFE. The main trick to make the scheme usable is to encrypt an send many random messages so that statistically it is likely that the legitimate user can find a ciphertext that is not perturbed by the construction and which may be decrypted as a plain HFE ciphertext. We show that this approach is not secure. In particular, we present a method to recover the noise support, a collection of quadratic forms spanning the set of LL' quadratic forms. We then are able to filter out the effect of these maps to recover a compatible HFE map. Finally, we are able to complete the key recovery, achieving efficiently an equivalent private key.

We strengthen Kaneko's bound to prove that, away from the $j$-invariant $0$, edges of multiplicity at least three can occur in the supersingular $\ell$-isogeny graph $\mathcal{G}_\ell(p)$ only if the base field's characteristic satisfies $p < 4\ell^3$. Further we prove a diameter bound for $\mathcal{G}_\ell(p)$, while also showing that most vertex pairs have a substantially smaller distance, in the directed case; this bound is then used in conjunction with Kaneko's bound to deduce that the distance of $0$ and $1728$ in $\mathcal{G}_\ell(p)$ is at least one fourth of the graph's diameter if $p \equiv 11 \mathrel{\operatorname{mod}} 12$. We also study other phenomena in $\mathcal{G}_\ell(p)$ with Kaneko's bound and provide data to demonstrate that the resulting bounds are optimal; for one of these bounds we investigate the connection between loop multiplicities in isogeny graphs and the factorization of the `diagonal' classical modular polynomial $\Phi_\ell(X,X)$ in positive characteristic.

A private set operation (PSO) scheme [Rafiee, Comput. J. 2020] is a cryptographic primitive that enables a user to securely outsource their dataset to cloud storage, and then when needed, securely issue common set operation queries to the server and receive the results. In [Rafiee, Comput. J. 2020], the only security notion of the PSO schemes, named naSIM, is proposed. This security notion models a weak attacker who is far from the threats of practical environments, and providing stronger security notions has been raised as an open problem. In this paper, we propose a new security notion for the PSO schemes, called aIND, and show that this concept is stronger than naSIM. Furthermore, we propose a new PSO construction that satisfies the security notion aIND. We also show that our construction does not increase the computational and storage overheads compared to other existing constructions, despite covering a much higher level of security.

One of the main guidelines to prevent timing side-channel attacks against cryptographic implementations is to avoid array accesses indexed by secret data. However, alternatives and countermeasures often incur significant performance losses. We propose a novel methodology for secure, constant-time implementation of algorithms that read and write to small arrays with secret-dependent indices, with a constant-factor performance impact compared to timing-unprotected accesses. It is specifically suitable for simple in-order CPUs like those in embedded systems, e.g., the ARM Cortex-M4 core. Although our methodology is general, we illustrate it with secure implementation of permutation operations, such as composition, inversion, and sampling, the latter using the Fisher-Yates shuffle. We apply this methodology to the post-quantum cryptosystems PERK and NTRU, bridging most of the performance gap to unprotected implementations that employ secret-dependent array accesses.

Recent years have witnessed significant progress in composable masked AES designs based on Hardware Private Circuits (HPCs) under the Probe-Isolating Non-Interference (PINI) framework. However, these designs still suffer from substantial randomness requirements and area overhead at higher protection orders. In this work, we revisit Domain-Oriented Masking (DOM), originally proposed by Gross et. al. in 2016, and leverage the DOM-$dep$ and DOM-$indep$ multipliers to construct efficient AES implementations based on the Strong Non-Interference (SNI) framework. Our contributions include: 1. a comprehensive security analysis of DOM-$dep$ and DOM-$indep$, including their compositional security under the SNI framework; 2. more efficient masked AES implementations for arbitrary protection orders, reducing randomness and area overhead while maintaining latency comparable to state-of-the-art HPC3-based designs. Specifically, our masked AES implementations maintain a latency of 41 clock cycles by using the Hadzic's decomposition for $F_2^8$ inverter. When $d <= 4$, they save at least 13% in area (RNG included) and reduce latency by 19.6% compared to the smallest $d$-PINI round-based masked AES implementations provided by Cassiers et.al. (The current version focuses on the core construction and its initial evaluation. Source code has been made publicly available to facilitate verification. Further performance optimizations and theoretical generalizations are underway and will appear in an upcoming revision.)

A quantum copy-protection scheme (Aaronson, CCC’09) encodes a functionality into a quantum state such that given this state, no efficient adversary can create two (possibly entangled) quantum states that are both capable of running the functionality. There has been a recent line of works on constructing provably-secure copy-protection schemes for general classes of schemes in the plain model, and most recently the recent work of Çakan and Goyal (IACR Eprint, 2025) showed how to copy-protect all cryptographically puncturable schemes with pseudorandom puncturing points. In this work, we show how to copy-protect even a larger class of schemes. We define a class of cryptographic schemes called malleable-puncturable schemes where the only requirement is that one can create a circuit that is capable of answering inputs at points that are unrelated to the challenge in the security game but does not help the adversary answer inputs related to the challenge. This is a flexible generalization of puncturable schemes, and can capture a wide range of primitives that was not known how to copy-protect prior to our work. Going further, we show that our scheme is secure against arbitrary high min-entropy challenge distributions whereas previous work has only considered schemes that are punctured at pseudorandom points.

Group signatures (GS, Chaum and van Heyst, EUROCRYPT 1991) are digital signatures that allow a signer to anonymously prove the membership and also allow the special authority called the opener can identify the signer. Group signatures with message-dependent opening (GS-MDO, Sakai et al., Pairing 2012) weakened the power of the opener by introducing another authority called the admitter who issues a message-dependent token. It would be a natural research topic to clarify whether cryptographic primitives that are required to construct GS-MDO are stronger than those of GS or not, according to the enhanced functionality of GS-MDO. In this paper, we propose a generic construction of timed-release encryption (TRE) from GS-MDO. Note that Sakai et al. have shown that GS-MDO implies identity-based encryption (IBE), and Nakai et al. (IWSEC 2009) and Matsuda et al. (Pairing 2010) demonstrated generic constructions of TRE from IBE. Thus, we do not show any new result from the viewpoint of feasibility. We show that (1) GS-MDO directly implies TRE without employing the generic constructions of TRE from IBE, and (2) the proposed TRE construction provides public verifiability, that is not usually supported by TRE, because a TRE ciphertext is a group signature in our construction. We also introduce a new security notion which we call token unforgeability where no adversary can forge a token even the adversary has the opener's secret key, and prove that token unforgeability is implied by opener anonymity which is a fundamental security notion of GS-MDO. Our result implies that GS-MDO is a very strong cryptographic primitive.

Quantum computational pseudorandomness has emerged as a fundamental notion that spans connections to complexity theory, cryptography, and fundamental physics. However, all known constructions of efficient quantum-secure pseudorandom objects rely on complexity-theoretic assumptions. In this work, we establish the first unconditionally secure efficient pseudorandom constructions against shallow-depth quantum circuit classes. We prove the following: (1) Any quantum state $2$-design yields unconditional pseudorandomness against both $\mathsf{QNC}^0$ circuits with arbitrarily many ancillae and $\mathsf{AC}^0 \circ \mathsf{QNC}^0$ circuits with nearly linear ancillae. (2) Random phased subspace states, where the phases are picked using a $4$-wise independent function, are unconditionally pseudoentangled against the above circuit classes. (3) Any unitary $2$-design yields unconditionally secure parallel-query pseudorandom unitaries against geometrically local $\mathsf{QNC}^0$ adversaries, even with limited $\mathsf{AC}^0$ postprocessing. Our indistinguishability results for $2$-designs stand in stark contrast to the standard setting of quantum pseudorandomness against $\mathsf{BQP}$ circuits, wherein they can be distinguishable from Haar random ensembles using more than two copies or queries. Our work demonstrates that quantum computational pseudorandomness can be achieved unconditionally for natural classes of restricted adversaries, opening new directions in quantum complexity theory.

Succinct non-interactive arguments of knowledge (SNARKs) rely on polynomial commitment schemes (PCSs) to verify polynomial evaluations succinctly. High-performance multilinear PCSs (MLPCSs) from linear codes reduce prover cost, and distributed MLPCSs reduce it further by parallelizing commitment and opening across provers. Employing a fast Reed--Solomon interactive oracle proof of proximity (FRI), we propose PIPFRI, an MLPCS that combines the linear-time proving of linear-time-encodable-code PCSs with the compact proofs and fast verification of Reed--Solomon (RS) PCSs. Reducing fast Fourier transform and hash overhead, PIPFRI is 10× faster to prove than the RS-based DeepFold (USENIX Security '25) while keeping competitive proof size and verifier time. Measured against Orion (CRYPTO '22) from linear-time-encodable codes, PIPFRI proves 3.5× faster and reduce proof size and verifier time by 15×. As a linearly scalable distributed variant, we propose DEPIPFRI, which adds accountability and distributes a single polynomial across provers, enabling the first code-based distributed SNARK for general circuits. Notably, compared with DeVirgo (CCS '22), which lacks accountability and supports only multiple independent polynomials, DEPIPFRI improves prover time by 25× and inter-prover communication by 7×. We identify shred-to-shine as the key insight: partitioning a polynomial into independently handled fragments while maintaining proof size and verifier time. Hitting the pairing regime, this insight yields a group-based MLPCS with a 16× shorter structured reference string (SRS) and a 10× faster opening time than a multilinear variant of Kate--Zaverucha--Goldberg (TCC '13).

In 2023, Barreto and Zanon proposed a three-round Schnorr-like blind signature scheme, leveraging zero-knowledge proofs to produce one-time signatures as an intermediate step of the protocol. The resulting scheme, called BZ, is proven secure in the discrete-logarithm setting under the one-more discrete logarithm assumption with (allegedly) resistance to the Random inhomogeneities in a Overdetermined Solvable system of linear equations modulo a prime number $p$ attack, commonly referred to as ROS attack. The authors argue that the scheme is resistant against a ROS-based attack by building an adversary whose success depends on extracting the discrete logarithm of the intermediate signing key. In this paper, however, we describe a distinct ROS attack on the BZ scheme, in which a probabilistic polynomial-time attacker can bypass the zero-knowledge proof step to break the one-more unforgeability of the scheme. We also built a BZ variant that, by using one secure hash function instead of two, can prevent this particular attack. Unfortunately, though, we show yet another ROS attack that leverages the BZ scheme's structure to break the one-more unforgeability principle again, thus revealing that this variant is also vulnerable. These results indicate that, like other Schnorr-based strategies, it is hard to build a secure blind signature scheme using BZ's underlying structure.

We present InsPIRe that is the first private information retrieval (PIR) construction simultaneously obtaining both high-throughput and low query communication while using silent preprocessing (meaning no offline communication). Prior PIR schemes with both high-throughput and low query communication required substantial offline communication of either downloading a database hint that is 10-100x larger than the communication cost of a single query (such as SimplePIR and DoublePIR [Henzinger et al., USENIX Security 2023]) or streaming the entire database (such as Piano [Zhou et al., S&P 2024]). In contrast, recent works such as YPIR [Menon and Wu, USENIX Security 2024] avoid offline communication at the cost of increasing the query size by 1.8-2x, up to 1-2 MB per query. Our new PIR protocol, InsPIRe, obtains the best of both worlds by obtaining high-throughput and low communication without requiring any offline communication. Compared to YPIR, InsPIRe requires 5x smaller cryptographic keys, requires up to 50% less online query communication while obtaining up to 25% higher throughput. We show that InsPIRe enables improvements across a wide range of applications and database shapes including the InterPlanetary File System and private device enrollment. At the core of InsPIRe, we develop a novel ring packing algorithm, InspiRING, for transforming LWE ciphertexts into RLWE ciphertexts. InspiRING is more amenable to the silent preprocessing setting that allows moving the majority of the necessary operations to offline preprocessing. InspiRING only requires two key-switching matrices whereas prior approaches needed logarithmic key-switching matrices. We also show that InspiRING has smaller noise growth and faster packing times than prior works in the setting when the total key-switching material sizes must be small. To further reduce communication costs in the PIR protocol, InsPIRe performs the second level of PIR using homomorphic polynomial evaluation, which only requires one additional ciphertext from the client.

The Generalized Birthday Problem ($\textsf{GBP}$), which seeks $k$ hash values from $k$ lists whose XOR is zero, is a fundamental problem across multiple cryptographic domains. While the $k$-list $\textsf{GBP}$ has been extensively studied, many schemes including $\textsf{Equihash}$ (NDSS'16) utilize a single-list variant (selecting hash values from a single list) without clear theoretical grounding. Our work reveals that the $k$-list $\textsf{GBP}$ implicitly exhibits a regularity property, a block-wise structure that has been thoroughly studied by Esser and Santini (Crypto'24) in the context of the Syndrome Decoding Problem. Such structured regularity can often be leveraged to design efficient protocols and enable new functionalities. In this work, we revisit these two long-conflated $\textsf{GBP}$s and initiate a systematic study of the regularity in the realm of $\textsf{GBP}$. $\textbf{Complexity.}$ In the worst-case setting, we develop a novel ISD-based framework for $\textsf{GBP}$. When $k/n > 0.188$ and $k/n > 0.11$ for the regular and non-regular cases, respectively, the proposed algorithms surpass the worst-case complexity of $2^{n/2}$. Through numerical optimization, we heuristically demonstrate that for any constant $k/n > 0$, the advanced ISD algorithms such as BJMM achieve an asymptotic complexity superior to the birthday bound when applied to density-one $\textsf{GBP}$ instances. Our results disprove the average-case-to-worst-case $k$-$\textsf{XOR}$ conjecture when $k$ is non-constant (e.g., linear in $n$). In the average-case regime, we fill in theoretical gaps in solving the single-list $\textsf{GBP}$ and show that the regular variant exhibits a $\sqrt{2}$-factor difference in the exponent, which extends naturally to the $k$-$\textsf{SUM}$ problem and offers new insights into its complexity. $\textbf{Implications for Cryptography.}$ We analyze the impact of regularity on incremental hash and propose a new collision attack against the ID-based incremental hash (Eurocrypt'97). Our attack achieves an asymptotic time complexity of $\mathcal{O}(\sqrt{n} \cdot 2^{\sqrt{2n}})$, significantly improving upon Wagner's previous bound of $\mathcal{O}(2^{\sqrt{4n}})$ (Crypto'02). Applying our attack to $\textsf{iSHAKE256}$, we reduce its security lower bound from $2^{256}$ to $2^{189}$. In the realm of $\textsf{Equihash}$, the index-pointer technique has significantly weakened its ASIC-resistance. To address this, we propose $\textsf{Requihash}$, a PoW with enhanced ASIC-resistance and a smaller solution size, rigorously aligned with the regular $k$-list $\textsf{GBP}$.

In this paper, we propose a new postquantum lattice-based digital signature named Rhyme. The scheme is based on the Fiat-Shamir structure and does not rely on flooding, rejection sampling, or Gaussian convolution as previous methods. Instead, its security is based on a variant of LWE combined with a new sampling method (3C sampling). We prove its security in ROM/QROM and provide concrete parameters as well as reference implementation to show that our scheme enjoys high efficiency and very compact signature size compared with former results.

Recent years have witnessed the surge of academic researches and industrial implementations of succinct non-interactive arguments of knowledge (SNARKs). However, proving time remains a bottleneck for applying SNARKs to large-scale circuits. To accelerate the proof generation process, a promising way is to distribute the workload to several machines running in parallel, the SNARKs with which feature are called \textit{distributed SNARKs}. Nevertheless, most existing works either require a trusted setup, or rely on quantum-insecure assumptions, or suffer from linear communication costs. In this paper, we introduce $\mathsf{HyperFond}$, the first distributed SNARK that enjoys a transparent setup, post-quantum security and polylogarithmic communication cost, as well as field-agnosticity (no reliance on specific choices of fields). To this end, we first propose a distributed proof system based on HyperPlonk (by Chen et al. in EUROCRYPT 2023). To instantiate the system, we then put forward a novel approach to distribute the multilinear polynomial commitment scheme in BaseFold (by Zeilberger et al. in CRYPTO 2024), and present a trade-off between communication cost and proof size. In $\mathsf{HyperFond}$, after committing to polynomial coefficients with quasilinear complexity, each sub-prover generates proofs with time linear in subcircuit size. We implement $\mathsf{HyperFond}$ using up to 16 machines. Experimental results demonstrate that the proving time of $\mathsf{HyperFond}$ is 15.6 $\times$ faster than HyperPlonk instantiated with BaseFold. We also compare to deVirgo (by Xie et al. in CCS 2022), so far the only post-quantum distributed SNARK, and achieve a 1.45 $\times$ speedup.

This work establishes the CRO Trilemma: no post-quantum proof system can simultaneously satisfy the following three properties beyond negligible failure probability: (i) Confidentiality, quantified by Priv > 1 - negl(lambda); (ii) Reliability, with Rel > 1 - negl(lambda); and (iii) Legal Opposability, measured by contextual entropy H_Opp ≈ log |V_J|, where V_J denotes the validation space of a polynomial-time institutional verifier J. The result formalizes the Invisible Authenticity Paradox through contextual entropy H(C) and quantum interpretability loss eta_q(C). Under standard quantum assumptions, we prove the following impossibility bound against QPT adversaries: H_Opp <= (Priv * Rel) / (epsilon_eff * 2^H(C)) + eta_q(C) + negl(lambda) A composable framework is introduced, including a composable model with verifier J (Algorithm 1), and an optimal entropy decomposition theorem (Theorem 2.3). Theoretical predictions are supported by empirical evidence indicating consistent violation of the bound (Gamma_CRO > 0.8) across NIST PQC finalists (e.g., Dilithium) and structured ZKPs (e.g., STARKs, Groth16).

Tracing techniques have been used to identify users who have leaked their decryption keys in a secure multi-receiver encryption system. Very recently, in the field of distributed cryptography, where trust is distributed, Boneh et al. extended traitor tracing to the framework of threshold decryption, where a single user doesn't hold the whole secret to decrypt but needs to collaborate with others. However, the tracing capacity in their collusion-secure codes-based schemes is still centralized: only the authority holding the secret tracing key can perform tracing. We continue in the direction of not relying on a single entity and propose decentralizing tracing in this context so that the tracing procedure does not need to rely on any secret key and can be done by anyone. Technically, as binary collusion-secure codes only support secret tracing, we switch to robust $q$-ary IPP codes supporting public tracing. This requires us to generalize the bipartite threshold KEM for two users in Boneh et al.'s paper to $q$-partite KEM for q users. In terms of security, their static one-sided security in the binary case is not appropriate, which requires us to define an adaptive one-sided security notion for $q$-partite KEM to be compatible with $q$-ary IPP codes. Finally, we generalize the Boneh et al. construction to achieve this security notion and achieve public traceability for threshold decryption without degrading efficiency.

FRAST is a TFHE-friendly stream cipher that was published at FSE 2025. The cipher is defined over $\mathbb{Z}_{16}$, and makes extensive use of negacyclic S-boxes over $\mathbb Z_{16}$ as they are less costly in TFHE. Like many FHE-friendly ciphers, FRAST randomizes some of its components to increase its security against statistical attacks. In the case of FRAST, some S-boxes are randomized using an XOF that takes a nonce as input. In this work, we point out a strong structural property of the full FRAST permutation, which leads to a much simpler alternative representation of the primitive. We study the consequences of this representation and find a weak key space of non-negligible size (i.e., much larger than $2^{128}$) on which every ciphertext leaks one bit of plaintext. This corresponds to a distinguishing attack on the full FRAST in the weak-key setting. In particular, we emphasize that, apart from the structural property, the usage of negacyclic S-boxes further leads to a much larger weak-key space for our attack. Finally, we provide a general framework to mount a linear attack on FRAST in the average key setting. We briefly describe our approach in the end of the paper, and observe that standard assumptions expected to work in the context of linear cryptanalysis do not hold in the case of FRAST: our experiment indicate that a linear attack in the average key setting does not work as expected.

Eagen introduced a framework for proof-of-computation over elliptic curves, replacing costly group operations with efficient computations over a function field. This work lacks clear protocol descriptions, formal security proofs, and a thorough efficiency analysis; we improve upon the literature, present a detailed protocol description, then analyze completeness, soundness, and complexity. We apply our construction to the Schnorr and Bulletproofs protocols, highlighting how this reduces verifier costs significantly compared to the original proposals. This tradeoff most clearly benefits privacy-centered constructions like blockchain cryptocurrencies and Tor routing - where proofs must be verified repeatedly - but more generally may be used to improve verification time in generic curve-based zero-knowledge proof systems.

Hamming Quasi-Cyclic (HQC) has recently been officially selected for standardization by NIST as a post-quantum KEM alternative to ML-KEM. This milestone raises new requirements, in particular the need to design and deploy secure implementations of the scheme. This paper presents two major contributions to secure HQC against Side-Channel Attacks (SCAs). First, we present a detailed sensitivity analysis of HQC, highlighting the critical variables and critical internal functions that need to be protected. Second and main contribution, we propose the first fully masked HQC implementation at any order. It is also the first PQC masked implementation that is formally proved to be secure in the MIMO-SNI security model. This security, introduced by Cassiers and Standaert in 2020, ensures the security of gadgets composition against propagating probes. In this paper, we provide benchmarks of our implementation, showing that our masked implementation is competitive in the state-of-the-art masked PQC implementations.

Symmetric encryption allows us to establish a secure channel based on a shared, strong key. However, users cannot remember or cannot store such keys securely. Password-Authenticated Key Exchange (PAKE) protocols address this by using low-entropy, human-memorizable passwords to establish secure channels. PAKEs are widely used and are foundational in practical cryptographic protocols, but while cryptographic tools like Key Encapsulation Mechanism (KEM) and Signatures have been implemented to resist attacks from quantum computers, PAKEs have gained quantum security only recently. To hedge against any potential vulnerabilities in recent quantum-secure PAKEs and in their implementations, we primarily focus on hybrid PAKE constructions that compose CPace, a classically-secure PAKE, with a variant of a recently proposed quantum-secure PAKE, which we call OQUAKE. Specifically we introduce and analyze two new hybrid PAKEs designed to be efficient, easy to implement, and utilize a minimized set of standard building blocks. The first, called CPaceOQUAKE, is a hybrid symmetric PAKE that remains secure as long as either a classical or post-quantum assumption holds. The second, called CPaceOQUAKE+, is a hybrid asymmetric PAKE (aPAKE) where the server party holds a verifier that obscures the password, instead of holding the password itself. In our analysis we present the necessary security proofs in the Universal Composability framework. In particular, we prove that OQUAKE, the underlying KEM-based PAKE in our hybrid constructions, realizes a relaxed UC PAKE variant that exposes password equality to passive observers, an observation available anyway in typical applications of PAKEs where the network interactions which follow the PAKE depend on authentication success. Moreover, we prove that our variant of the PAKE(+KEM)-to-aPAKE compiler is a similarly relaxed UC aPAKE.

Discrete Gaussian Sampling (DGS) over the integers—also known as integer Gaussian sampling— is used to generate integer values that statistically follow the discrete Gaussian distribution and plays a central role in lattice-based cryptography. Among existing approaches for integer DGS, the cumulative distribution table (CDT) method is widely adopted. However, CDT sampling typically incurs substantial storage costs due to the need to store high-precision fixed-point probability tables, where a precision of $k$ bits is required to achieve a statistical distance of $2^{-k}$ from the ideal distribution. In this work, we propose a more compact representation of CDT based on Simultaneous Diophantine Approximation (SDA). Instead of storing fixed-point values, our method expresses the probabilities in the CDT as a sequence of rational numbers with a common denominator. With parameter selection guided by SDA, this compact fractional representation enables reducing data width while maintaining the same level of statistical accuracy. Our SDA-CDT construction offers clear advantages in both computation speed and storage compared to classical CDT implementations. For example, in Frodo-1344, our sampler achieves a 19.97% increase in speed (from 12.10 million to 14.51 million samples per second) and a 3.85% reduction in memory usage (from 104 bits to 100 bits). Similarly, in Frodo-976, we observe a 10.88% speedup and a 21.60% decrease in memory cost. In addition, our design eliminates floating-point arithmetic and supports a fully constant-time online sampling procedure, which ensures resistance to timing side-channel attacks without compromising performance.

HPPC is a multivariate signature scheme submitted to the NIST PQC standardization process in response to the recent call for additional signature schemes. We show that, despite some non-standard notational choices in the submission document, HPPC can be viewed as a special case of the well-studied, but broken for all practical parameters, HFE signature scheme. We further show that the HPPC construction introduces additional structure that further weakens the scheme. For instance, the central map has $Q$-rank $2$ independently from the degree $D$ of the central polynomial that is used. Using these observations, we show that HPPC is weaker against the direct attack than claimed in the submission document and more crucially that all parameter sets can be practically broken using MinRank techniques. For instance, with a very naive implementation, we have been able to recover an equivalent key in approximately 8 minutes for security level 2, an hour and a half for security level 4, and slightly more than 7 hours for security level 5.

Private Information Retreival (PIR) schemes without preprocessing are known to incur linear server computation per client query. Several recent works have shown that by relying on a one-time preprocessing phase, we can get around this barrier, and achieve sublinear computation per query without relying on any cryptographic assumptions. Beimel et al. (CRYPTO'00) first showed a family of schemes whose bandwidth and computation per query scale as fast as $n^{O(1/S)}$ where $S$ denotes the number of servers and $n$ denotes the database size. Unfortunately, their schemes are not practical partly because the servers must each store an encoded version of the database, and the encoding length grows sharply as we increase $S$. The recent work of Singh et al. (TCC'24) showed how to achieve similar bandwidth scaling but without the server space blowup. To get this, they rely on a different type of preprocessing called client-specific preprocessing, where the stateful client stores some hints and the servers store only the original database. Unfortunately, Singh et al.'s result is completely impractical due to the reliance on Dvir and Gopi's PIR as a building block. We propose Zelda (short for ZEro-Leakage Data Access), the first concretely efficient, information-theoretic multi-server PIR scheme with sublinear computation. Our work makes both theoretical and practical contributions. On the theoretical front, we devise a unified framework for constructing multi-server PIR with client-specific preprocessing. This gives us a parametrizable family of schemes that asymptotically outperform all prior constructions in the same setting, including Singh et al. (TCC'24) and Ishai et al. (CRYPTO'24). On the practical front, Zelda is conceptually simple, self-contained, and does not rely on any underlying PIR as a building block. We implemented Zelda and open sourced our code. We compared the concrete performance of Zelda with a state-of-the-art PIR scheme called QuarterPIR (Eurocrypt'24), which relies on pseudorandom functions for security. Experimental results show that Zelda outperforms QuarterPIR in terms of online response time and client space (assuming typical fiber optical links), at the price of increased costs for offline maintenance operations.

This paper studies the Twinkle family of low-latency symmetric key schemes designed by Wang et al. (CiC 2024). In particular, it presents cryptanalysis of both the mode and the underlying primitive. Twinkle is a PRF-based design, and an authenticated encryption scheme Twinkle-AE is specified based on a dedicated PRF called Twinkle-PRF. To achieve low latency, Twinkle-PRF uses a large key and state to produce sufficient randomness in a single step. Twinkle-AE uses a 1024- or 512-bit key for authentication and generates a $t$-bit tag, where $t \in \{64, 128\}$. It claims to provide $t$ bits of integrity. Several Twinkle-AE parameter sets claim higher confidentiality than integrity. In this setup, for any ciphertext, an adversary can obtain the message after $O(2^t)$ decryption attempts by guessing the tag, allowing attacks in the chosen-ciphertext setting. We show that a 1024- or 512-bit authentication key can be recovered using only $O(2^t)$ queries. The recovered authentication key enables the generation of valid ciphertexts for arbitrary plaintexts, thus achieving universal forgery. In the second part of the paper, we perform cryptanalysis on reduced-round variants of the 1280-bit public permutation Twinkle-P, which serves as a core component of Twinkle-PRF. We investigate impossible differential, zero-correlation linear, integral, and differential-linear distinguishers by developing automated analytic tools. We provide practical distinguishers for up to 5 rounds, and the longest distinguisher reaches 6 rounds with a complexity of $2^{74.32}$. This surpasses the round bounds evaluated by the designers. We stress that our attacks on mode exploits the gap between the claimed confidentiality and integrity levels, thus have no impact on the parameter sets having the same security level. Our attacks on the permutation do not have any significant impact on the whole specifications. Moreover, we note that Twinkle-AE-512b/Twinkle-AE-1024b and Twinkle-PA remain secure, and the versions we attacked would also be secure if the claimed confidentiality level matched the integrity level.