FrodoKEM is a conservative lattice-based KEM based on the Learning With Errors problem. While it was not selected for NIST standardization, it remains a strong candidate for high-security applications and is recommended by several national agencies, including BSI, ANSSI, and the EUCC. Its reliance on CDT-based Gaussian sampling presents a significant challenge for side-channel secure implementations. While recent work by Gérard and Guerreau [GG25] has shown that masking FrodoKEM is feasible, the Gaussian sampler remains a major bottleneck, accounting for between 34% and 65% of the execution time. In this work, we introduce a new high-order masking gadget for CDT sampling, provably secure in the ISW probing model and significantly more efficient than previous approaches. We instantiate and evaluate our design on a real-world setup to assess its side-channel resistance in the context of FrodoKEM, using a complete first-order masked implementation on Cortex-M3, which reflects the most relevant practical threat model. Compared with [GG25] at first order, the cost of the sampler is reduced by at least 82% and the number of random generations by at least 69%. Higher-order security is also fully supported through a generic C implementation, with some selected gadgets hand-optimized in assembly to improve efficiency.

As of November 2021, Bitcoin supports “Taproot” spending policies whose on-chain format is a single elliptic curve point. A transaction spending the funds associated with a Taproot policy can be authorized by interpreting the curve point either (a) as a public key of the Schnorr signature scheme and providing a suitable signature, or (b) as a commitment to alternative spending conditions and satisfying those. Since a sufficiently powerful quantum adversary would be able to forge Schnorr signatures, an upgrade to Bitcoin may, at some point in the future, disable the ability to spend existing funds via Schnorr signatures in order to prevent the havoc created by leaving a large fraction of the currency supply prone to theft. However, to avoid irrevocably losing all funds not migrated in time to (yet to be added) post-quantum signature schemes, it will be desirable for an upgrade disabling Schnorr signatures to retain the ability to spend funds by interpreting the curve point in a Taproot policy as a commitment to alternative spending conditions. This paper justifies such an upgrade strategy by demonstrating the post-quantum security of Taproot as a commitment scheme. Specifically, it provides concrete upper bounds on the probability that a quantum adversary making some number of queries to a quantum random oracle can break the binding or hiding property. Since the bounds follow from powerful existing results, which enable reasoning as if dealing with a classical adversary, the proofs are accessible without a background in quantum computing.

The success of deep learning in cryptanalysis has been largely demonstrated empirically, yet it lacks a foundational theoretical framework to explain its performance. We bridge this gap by establishing a formal learning-theoretic framework for symmetric cryptanalysis. Specifically, we introduce the Coin-Tossing (CoTo) model to abstract the process of constructing distinguishers and propose a unified algebraic representation, the Conjunctive Parity Form (CPF), to capture a broad class of traditional distinguishers without needing domain-specific details. Within this framework, we prove that any concept in the CPF class is learnable in sub-exponential time in the setting of symmetric cryptanalysis. Guided by insights from our complexity analysis, we demonstrate preprocessing the data with a flexible output generating function can simplify the learning task for neural networks. This approach leads to a state-of-the-art practical result: the first improvement on the deep learning-based distinguisher for $S{\scriptsize PECK}32/64$ since 2019, where we enhance accuracy and extend the attack from 8 to a record 9 rounds.

A Private Information Retrieval (PIR) scheme allows a client to retrieve data from a database hosted on a remote server without revealing which location is being accessed. In Doubly-Efficient PIR (DEPIR), the server preprocesses the database offline into a data structure that enables it to answer any client query in sublinear time with respect to the database size $N$. The breakthrough work of Lin-Mook-Wichs (STOC’23) presented the first DEPIR construction from the Ring-LWE assumption. This remains essentially the only known construction to date, and realizing DEPIR from alternative foundations, particularly from plain LWE, has remained elusive. In this work, we present a simple LWE-based construction of DEPIR in the CRS model. Our construction is inspired by SimplePIR (USENIX’23) and leverages the matrix–vector multiplication preprocessing of Williams (SODA’07). While our construction is only barely doubly-efficient, with server computation of $o(N / \log{N})$, it was previously unknown whether even such modest sublinear efficiency could be achieved from unstructured, plain LWE.

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

The seminal work of [Bardet et al., 2020] has shown the potential of algebraic modelings to solve the Rank Syndrome Decoding Problem (R-SDP). For most parameter ranges, their algorithm first needs to perform a guessing step, making it a hybrid approach between combinatorial and algebraic solvers. In this paper, we present a novel guessing technique, which, when applied to [Bardet et al., 2020], is able to attack the proposed parameters of RYDE, a second-round candidate for the additional NIST standardization process. In particular, we show that all of the proposed RYDE parameters have to be updated: We can reduce the security of RYDE-1 to 104 bits, RYDE-3 to 153 bits, and RYDE-5 to 210 bits.

Fully Homomorphic Encryption (FHE) enables computation over encrypted data and is considered a fundamental tool for privacy-preserving systems. Despite significant theoretical progress, its practical adoption remains limited. One contributing factor is the absence of reusable, application-level components suitable for integration into real-world systems. This work introduces a library of FHE components developed through a competition- based framework. The components are outcomes of a series of formalized challenges published on the FHERMA platform, each targeting a specific challenge—such as comparison, sorting, or matrix operations—under concrete cryptographic and performance constraints. This initial release includes contributions from independent researchers and reflects a variety of approaches across different FHE schemes. The library is intended to expand over time as new challenges are introduced and solved, forming a foundation for building and evaluating privacy-preserving applications.

The Cheon-Kim-Kim-Song (CKKS) scheme is a fully homomorphic encryption scheme that traditionally supports only the evaluation of smooth functions. Recent works have enabled the evaluation of arbitrary (discontinuous) integer functions represented as lookup tables (LUT) on small inputs using the method of functional bootstrapping (FBT). Although well-suited for small integers (up to around 10 bits), the efficiency of FBT quickly declines for large LUTs, and a considerable increase in both runtime and memory requirements is observed. Building on CKKS functional bootstrapping, we propose in this paper two functional bootstrapping algorithms, specifically designed to target larger LUTs (up to 20 bits). For a 16-bit LUT, our implementation in OpenFHE achieves a speed-up of 47.5 in amortized time and 95.1 in latency for single-threaded execution, compared to the state-of-the-art CKKS-based functional bootstrapping method of Alexandru et al. (CRYPTO'25).

Despite the growing popularity of blockchains, their scalability remains a significant challenge. Layer-2s (L2s) aim to address this by introducing an operator to process transactions off-chain and post compact summaries to the Layer-1 (L1). However, existing L2 designs struggle with unsatisfactory throughput improvements, complex exit games, limited data availability, stringent synchronization requirements or high computational overhead for users. This paper introduces PlasmaFold, a novel L2 designed to overcome each of those limitations. PlasmaFold utilizes a hybrid architecture: an operator (aggregator) generates proofs on server side for the honest construction of blocks, while users maintain balance proofs on their own devices. This separation of concerns enables instant, non-interactive exits via balance proofs, while block proofs handle most of the validations, minimizing users’ costs. By leveraging Incrementally Verifiable Computation (IVC), PlasmaFold achieves both instant synchronization and concrete efficiency. Using PlasmaFold proving routines, users can update their balance proofs within a browser in under 1 second per transaction using less than 1 GB of RAM. Our construction does not impact scaling, we show that it remains possible to leverage recent verifiable plasma research designed to keep a minimal on-chain footprint, thereby enabling PlasmaFold to reach a theoretical throughput of over 14000 transactions per second.

Many post-quantum cryptosystems require generating an $n$-bit binary vector with a prescribed Hamming weight $\omega$, a process known as \emph{fixed-weight sampling}. When $\omega = O(n)$, we call this \emph{dense} fixed-weight sampling, which commonly appears in lattice-based cryptosystems, like those in the NTRU family. In contrast, code-based cryptosystems typically use \emph{sparse} fixed-weight sampling with $\omega = o(n)$ (e.g., $O(\sqrt{n}$). Sparse fixed-weight sampling generally involves three constant-time steps to keep the sampled vector secret: 1. sample $\omega$ nearly uniform random integers from a series of decreasing intervals; 2. map these integers into a set of $\omega$ distinct indices in $[0, n)$, called the \emph{support}; 3. generate a binary $n$-bit vector with bits set only at the support indices. Remarkably, some of the core algorithms employed in fixed-weight sampling date back to nearly a century, yet developing efficient and secure techniques remains essential for modern post-quantum cryptographic applications. In this paper, we present novel algorithms for steps two and three of the fixed-weight sampling process. We demonstrate their practical applicability by replacing the current fixed-weight sampling routine in the HQC post-quantum key exchange mechanism, recently selected for NIST standardization. We rigorously prove that our procedures are sound, secure, and introduce little to no bias. Our implementation of the proposed algorithms accelerates step 2 by up to $2.9\times$ and step 3 by up to $5.8\times$ compared to an optimized version of the fixed-weight sampler currently used in HQC. Since fixed-weight sampling constitutes a significant portion of HQC’s execution time, these speedups translate into protocol-level improvements of up to $1.37\times$, $1.28\times$ and $1.21\times$ for key generation, encapsulation and decapsulation, respectively.

The Cheon-Kim-Kim-Song (CKKS) homomorphic encryption scheme is widely adopted for securely evaluating circuits over real numbers, such as those arising in privacy-preserving machine learning (PPML), because it efficiently supports approximate floating-point arithmetic of messages. A CKKS ciphertext has a finite level, which corresponds to the budget for how many multiplicative operations can be applied. Once these levels are consumed, the ciphertext must be refreshed through a bootstrapping procedure to restore its capacity for further computation. The CKKS bootstrapping procedure consists of four main steps: 1) ModRaise, which raises the ciphertext coefficient modulus; 2) C2S, which homomorphically evaluates the inverse-DFT (iDFT) to enable further operations on the ciphertext coefficients; 3) EvalMod, which homomorphically removes the unintended coefficients introduced by ModRaise and shifted to the message side by C2S; and 4) S2C, which homomorphically evaluates the DFT to map the ciphertext back from the iDFT domain. However, these bootstrapping procedures also consume a significant number of levels, leaving fewer levels after each bootstrapping. In this work, we introduce three techniques—OverModRaise1, OverModRaise2, and Tuple-C2S/S2C—that target reductions in the modulus consumption of C2S/S2C among the CKKS bootstrapping procedures, without introducing substantial overhead or compromising security. By combining these techniques, our implementation demonstrates at most 41% throughput improvement compared to the state-of-the-art bootstrapping.

Ateniese et al. (CRYPTO 2019/JoC 2021) introduced a cryptographic primitive which they call matchmaking encryption (ME), and Identity-based ME (IB-ME) is its identity-based variant. IB-ME supports an equality matching where a sender (encryptor) indicates a receiver's (decryptor's) identity (rcv) in addition to their own ID ($\sigma$), and a receiver indicates a sender's identity (snd) in addition to the own identity ($\rho$). A ciphertext is decrypted if $(\sigma,\rho)=$(snd,rcv). In this paper, we pay attention to the search condition of public key authenticated encryption with keyword search (PAEKS) (Huang-Li, Information Sciences 2017) is reminiscent of the equality matching. We introduce a public key variant of ME which we call PK-ME, and propose a generic construction of PK-ME from PAEKS. As a conceptual contribution, our work lies in revealing a connection between ME and public key searchable encryption, which were independently researched so far. Due to the generic construction of PAEKS (Li-Boyen, IACR CiC 2024), we can instantiate the proposed generic construction from pairings or lattices. We also introduce a weaker version of authenticity and show that it can be instantiated from several complexity assumptions. Finally, we discuss the advantage/disadvantage of PK-ME compared to IB-ME.

A zero-knowledge proof demonstrates that a fact (like that a Sudoku puzzle has a solution) is true while, counterintuitively, revealing nothing else (like what the solution actually is). This remarkable guarantee is extremely useful in cryptographic applications, but it comes at a cost. A classical impossibility result by Goldreich and Oren [J. Cryptol. '94] shows that zero-knowledge proofs must necessarily sacrifice basic properties of traditional mathematical proofs --- namely perfect soundness (that no proof of a false statement exists) and non-interactivity (that a proof can be transmitted in a single message). Contrary to this impossibility, we show that zero-knowledge with perfect soundness and no interaction is effectively possible. We do so by defining and constructing a powerful new relaxation of zero-knowledge. Intuitively, while the classical zero-knowledge definition requires that an object called a simulator actually exists, our new definition only requires that one cannot rule out that a simulator exists (in a particular logical sense). Using this, we show that **every falsifiable security property of (classical) zero-knowledge can be achieved with no interaction, no setup, and perfect soundness.** This enables us to remove interaction and setup from (classical) zero-knowledge in essentially all of its applications in the literature, at the relatively mild cost that such applications now have security that is "game-based" instead of "simulation-based." Our construction builds on the work of Kuykendall and Zhandry [TCC '20] and relies on two central, longstanding, and well-studied assumptions that we show are also necessary. The first is the existence of non-interactive witness indistinguishable proofs, which follows from standard assumptions in cryptography. The second is Krajícek and Pudlák's 1989 conjecture that no optimal proof system exists. This is one of the main conjectures in the field of proof complexity and is the natural finitistic analogue of the impossibility of Hilbert's second problem (and, hence, also Gödel's incompleteness theorem). Our high-level idea is to use these assumptions to construct a prover and verifier where no simulator exists, but the non-existence of a simulator is independent (in the logical sense of unprovability) of an arbitrarily strong logical system. One such logical system is the standard axioms of mathematics: ZFC.

In this paper, we discuss refined Humbert invariants, introduced by Kani in 1994. We show that in the contexts of SQISign and CSIDH, under GRH, the computational isogeny problem is polynomially equivalent to the computational refined Humbert invariant problem. This includes an algorithm to compute the basis of a maximal order of a quaternion algebra given its norm form. Finally, we also review what is known in the literature about computing refined Humbert invariants.

In this paper, we present Interstellar, a novel folding and IVC framework built on a technique we call circuit interpolation, tailored for circuit satisfiability. By incorporating the GKR protocol, our approach avoids commitments to full computation traces and cross-term vectors, requiring instead only commitments to the actual circuit witness and optionally a small subset of intermediate gate values. This substantially reduces the size of the vectors to be committed to in each folding round, which is highly advantageous compared to existing schemes, as vector commitments involve expensive multi-scalar multiplications. We evaluate Interstellar using two representative workloads: product of matrices which models highly parallel computation, and MiMC hash chains which captures highly serialized computation. Our analysis shows that Interstellar achieves 1.59x to 6.74x prover speedup per folding round for matrix multiplication and up to 2.93x speedups for MiMC chains compared to alternative methods. Beyond efficiency, Interstellar is highly flexible. It can be extended to support high-degree and lookup gates, multi-instance folding, and non-uniform IVC, making it well-suited for practical applications such as zkML and zkVM. Finally, we formalize, for the first time, a new notion called collaborative folding/IVC, which allows folding/IVC proof generation with multiple provers holding disjoint private witnesses for the same public statement. This new primitive enables distributed IVC proof generation while preserving witness privacy across folding rounds, making Interstellar a compelling fit for distributed and privacy-sensitive applications.

Developers implementing elliptic curve cryptography (ECC) face a wide range of implementation choices created by decades of research into elliptic curves. The literature on elliptic curves offers a plethora of curve models, scalar multipliers, and addition formulas, but this comes with the price of enabling attacks to also use the rich structure of these techniques. Navigating through this area is not an easy task and developers often obscure their choices, especially in black-box hardware implementations. Since side-channel attackers rely on the knowledge of the implementation details, reverse engineering becomes a crucial part of attacks. This work presents ECTester -- a tool for testing black-box ECC implementations. Through various test suites, ECTester observes the behavior of the target implementation against known attacks but also non-standard inputs and elliptic curve parameters. We analyze popular ECC libraries and smartcards and show that some libraries and most smartcards do not check the order of the input points and improperly handle the infinity point. Based on these observations, we design new techniques for reverse engineering scalar randomization countermeasures that are able to distinguish between group scalar randomization, additive, multiplicative or Euclidean splitting. Our techniques do not require side-channel measurements; they only require the ability to set custom domain parameters, and are able to extract not only the size but also the exact value of the random mask used. Using the techniques, we successfully reverse-engineered the countermeasures on 13 cryptographic smartcards from 5 major manufacturers -- all but one we tested on. Finally, we discuss what mitigations can be applied to prevent such reverse engineering, and whether it is possible at all.

We present an exponential-time key recovery attack on the public-key encryption scheme using matrix codes proposed by Aragon et al. at Asiacrypt 2024. The secret key is a Gabidulin code expanded using an $\mathbb{F}_q$-basis of $\mathbb{F}_{q^m}$ to obtain a matrix code, which is then hidden by appending random rows and columns and by left- and right-multiplication with invertible matrices. Our attack does not rely on the Gabidulin structure and hence applies to most $\mathbb{F}_{q^m}$-linear codes hidden by their transform. Its complexity is better than the previously best-known distinguisher and significantly better than the naive key recovery algorithm. Our attack breaks some of their proposed parameters. For example, a parameter set targeting 192-bit security is reduced to about 161 bits, and a 256-bit set to about 223 bits.

We provide minimal counterexamples for the security of the BitVM3 garbling scheme: our attack allows the evaluator to forge input and output wires. Then we use the same idea to exhibit an attack on the forward label propagation garbling scheme proposed in a more recent paper. In both cases, the authenticity property of the garbling scheme is broken.

Remote power analysis is a novel threat to information systems. Under this attack model, the adversary does not require direct physical access to the platform or specialized sensing equipment. Most of the literature in this field deals with advanced acquisition methods and adversarial models. In contrast, side-channel analysis techniques for remote attacks have not been sufficiently explored. We bridge this gap by taking a look at the characteristics of the data recovered from remote power analysis. We use these insights to propose a novel selection rule for correlation-based attacks that boosts success confidence. This improvement comes from the observation that the samples in a power trace are not independent. We show that adjacent samples can also provide useful information by proposing a post-processing step that capitalizes on these additional leakages. In contrast to previous work, the proposed technique does not rely on the selection of points of interest within the power traces. We further investigate the characteristics of "remote" power traces and their effect on the proposed selection rule through experiments with real (TDC, ChipWhisperer) and synthetic data sets. To assess the advantage of the proposed improvement, we also introduce novel performance metrics that divert from known-key evaluation techniques.

Federated learning (FL) proposes to train a global machine learning model across distributed datasets. However, the aggregation protocol as the core component in FL is vulnerable to well-studied attacks, such as inference attacks, poisoning attacks [71] and malicious participants who try to deviate from the protocol [24]. Therefore, it is crucial to achieve both malicious security and poisoning resilience from cryptographic and FL perspectives, respectively. Prior works either achieve incomplete malicious security [76], address issues by using expensive cryptographic tools [22, 59] or assume the availability of a clean dataset on the server side [32]. In this work, we propose AlphaFL, a two-server secure aggregation protocol achieving both malicious security in the universal composability (UC) framework [19] and poisoning resilience in FL (thus malicious$^2$) against a dishonest majority. We design maliciously secure multi-party computation (MPC) protocols [24, 26, 48] and introduce an efficient input commitment protocol tolerating server-client collusion (dishonest majority). We also propose an efficient input commitment protocol for the non-collusion case (honest majority), which triples the efficiency in time and quadruples that in communication, compared to the state-of-the-art solution in MP-SPDZ [46]. To achieve poisoning resilience, we carry out $L_\infty$ and $L_2$-Norm checks with a dynamic $L_2$-Norm bound by introducing a novel silent select protocol, which improves the runtime by at least two times compared to the classic select protocol. Combining these, AlphaFL achieves malicious$^2$ security at a cost of 25% − 79% more runtime overhead than the state-of-the-art semi-malicious counterpart Elsa [76], with even less communication cost.

During NIST's post-quantum cryptography standardization process, two generic transforms, Fujisaki-Okamoto (FO) and OAEP, are widely used to achieve the IND-CCA security. For instance, the final winner Kyber has utilized FO, and a variant of the 3rd-round finalist NTRU has utilized OAEP. The FO and OAEP are both constructed in the random oracle model (ROM), so to evaluate their post-quantum security, a security proof in the quantum random oracle model (QROM) is required. So far, the QROM security proof of FO has been given and improved by a sequence of works, however, the QROM security proof of OAEP has not been fully explored: current proofs either introduced an extra plaintext-confirming hash to the ciphertext (TCC 2016), or required parameter restrictions and a quantum collision-resistant term (PKC 2022). In this paper, by reorganizing the proof route, we give a new QROM security proof of plain OAEP. The key techniques used in our proof are the compressed oracle technique proposed by Zhandry (CRYPTO 2019) and the Fixed Permutation One-Way to Hiding recently proposed by Jaeger (Eprint 2024/797), and our proof has the following three advantages: \begin{itemize} \item Similar to Ebrahimi’s proof (PKC 2022), our proof also achieves the stronger IND-qCCA security, where the decryption oracle can be accessed in superposition. \item The parameter restrictions "$n+k_1\geq k_0$" and "$k_0-n=\mathcal{O}(n)$" introduced in Ebrahimi’s proof (PKC 2022) are removed. \item The reliance on the collision resistance of quantum random oracles required in Ebrahimi’s proof (PKC 2022) is avoided, and hence our security bound does not introduce the quantum collision-resistant term "$\mathcal{O}(q^3/2^{n+k_1})$". \end{itemize}

A critical aspect of securing cryptographic hardware is their resistance to FI attacks, which involve the successful injection of faults into the system in operation. Specifically, a hardware design must be resilient to well-established fault injection techniques, including voltage or clock glitching, laser fault injections, and the more recently introduced EMFI. Ideally, the protection level must be verified before the chip is fabricated. Although initial efforts to verify the resistance of hardware designs against fault injection have been made, analyzing the security of practical designs with realistic gate counts under fault injections that affect multiple gates or the entire circuit state remains a significant challenge. This scenario, however, is considered more realistic than assessing resistance to a fixed, relatively small number of faults. In this work, we introduce FIESTA, a versatile automated framework for analyzing the resistance of hardware circuits under the general random fault model. By leveraging a non-exhaustive approach, FIESTA is capable of evaluating larger designs compared to state-of-the-art tools, while maintaining a reasonable level of confidence. FIESTA supports various adversary models, allowing customized resistance analysis against specific adversaries. In particular, we present a concrete procedure for evaluating more realistic precise adversaries, based on practical observations. Using FIESTA, we assessed the resistance of several (protected) AES cores.

Classical Shadow Tomography (Huang, Kueng and Preskill, Nature Physics 2020) is a method for creating a classical snapshot of an unknown quantum state, which can later be used to predict the value of an a-priori unknown observable on that state. In the short time since their introduction, classical shadows received a lot of attention from the physics, quantum information, and quantum computing (including cryptography) communities. In particular there has been a major effort focused on improving the efficiency, and in particular depth, of generating the classical snapshot. Existing constructions rely on a distribution of unitaries as a central building block, and research is devoted to simplifying this family as much as possible. We diverge from this paradigm and show that suitable distributions over \emph{states} can be used as the building block instead. Concretely, we create the snapshot by entangling the unknown input state with an independently prepared auxiliary state, and measuring the resulting entangled state. This state-based approach allows us to consider a building block with arguably weaker properties that has not been studied so far in the context of classical shadows. Notably, our cryptographically-inspired analysis shows that for \emph{efficiently computable} observables, it suffices to use \emph{pseudorandom} families of states. To the best of our knowledge, \emph{computational} classical shadow tomography was not considered in the literature prior to our work. Finally, in terms of efficiency, the online part of our method (i.e.\ the part that depends on the input) is simply performing a measurement in the Bell basis, which can be done in constant depth using elementary gates.

We present the first horizontally scalable polynomial commitment scheme (PCS) that is both transparent and plausibly post-quantum (PQ) secure. This PCS can be combined with the distributed polynomial interactive oracle proof (PIOP) introduced in Pianist (IEEE S&P 2024), which achieves linear scalability by encoding witnesses using bivariate polynomials. While Pianist and other scalable SNARK systems offer strong performance profiles, they rely on trusted setup ceremonies and cryptographic assumptions that are not PQ secure, e.g., pairing-based primitives. In contrast, we present a bivariate PCS based on FRI, which, when used to compile the Pianist PIOP, achieves a transparent and plausibly PQ alternative. Distributed FRI has a high communication cost. Therefore, we introduce Fold-and-Batch, a customizable technique that applies partial folding locally before performing batched FRI centrally. We formally prove the security of our constructions and provide an implementation for three variants of distributed FRI, accompanied by thorough performance evaluations. Our results show that Fold-and-Batch reduces communication overhead compared to existing distributed FRI approaches, while preserving scalability and maintaining moderate proof sizes. To our knowledge, this is the first horizontally scalable PCS that simultaneously achieves transparency, plausible PQ security, and a tunable tradeoff between efficiency, verifier cost, and communication.

Regular Syndrome Decoding (RSD) is a variant of the traditional Syndrome Decoding (SD) problem, where the error vector is divided into consecutive, equal-length blocks, each containing exactly one nonzero element. Recently, RSD has gained significant attention due to its extensive applications in cryptographic constructions, including MPC, ZK protocols, and more. The computational complexity of RSD has primarily been analyzed using two methods: Information Set Decoding (ISD) approach and algebraic approach. In this paper, we introduce a new hybrid algorithm for solving the RSD problem. This algorithm can be viewed as replacing the meet-in-the-middle enumeration in ISD with a process that solves quadratic equations. Our new algorithm demonstrates superior performance across a wide range of concrete parameters compared to previous methods, including both ISD and algebraic approaches, for parameter sets over both large fields (q = 2^128) and binary fields (q = 2). For parameter sets used in prior works, our algorithm reduces the concrete security of RSD by up to 20 bits compared to the state-of-the-art algorithms. We also provide an asymptotic analysis, identifying a broader parameter region where RSD is solvable in polynomial time compared to ISD and algebraic methods over binary fields. Additionally, we apply our algorithm to evaluate the security of the ZK protocol Wolverine (IEEE S&P 2021) and the OT protocol Ferret (ACM CCS 2020). Our results reduce the security level of Wolverine, which targets a 128-bit security level, to about 111 bits, and also marginally lowers the security of Ferret below the targeted 128-bit level for the first time.

Non-degenerate bilinear maps on elliptic curves, commonly referred to as pairings, have many applications including short signature schemes, zero-knowledge proofs and remote attestation protocols. Computing a state-of-the-art pairing at the $128$-bit security level, such as the optimal ate pairing over the curve BLS12-381, is very costly due to the high complexity of some of its sub-operations: most notable are the Miller loop and final exponentiation. In the past ten years, a few optimized pairing implementations have been introduced in the literature, but none of those took advantage of the vector (SIMD) extensions of state-of-the-art Intel and AMD CPUs, especially AVX-512; this is surprising, because doing so offers the potential to reach significant speed-ups. Consequently, the questions of 1) how computation of the optimal ate pairing can be effectively vectorized, and 2) what execution time such a vectorized implementation can achieve are still open. This paper addresses said questions by introducing a carefully-optimized AVX-512 implementation of the optimal ate pairing on BLS12-381. A central feature of the implementation is the use of $8$-way Integer Fused Multiply-Add (IFMA) instructions, which are capable to execute eight $52 \times 52$-bit multiplications in a SIMD-parallel fashion. We introduce new vectorization strategies and describe optimizations of existing ones to speed up arithmetic operations in the extension fields $\mathbb{F}_{p^4}$, $\mathbb{F}_{p^6}$, and $\mathbb{F}_{p^{12}}$ as well as certain higher-level functions. Furthermore, we discuss some parallelization bottlenecks and how they impact execution time. We benchmarked our pairing software, which we call avxbls, on an Intel Core i3-1005G1 ("Ice Lake") CPU and found that it needs $1,265,314$ clock cycles (resp. $1,195,236$ clock cycles) for the full pairing, with the Granger-Scott cyclotomic squaring (resp. compressed cyclotomic squaring) being used in the final exponentiation. For comparison, the non-vectorized (i.e., scalar) x64 assembly implementation from the widely-used blst library has an execution time of $2,351,615$ cycles, which is $1.86$ times (resp. $1.97$ times) slower. avxbls also outperforms Longa's implementation (CHES 2023) by almost the same factor. The practical importance of these results is amplified by Intel's recent announcement to support AVX10, which includes IFMA instructions, in all future CPUs.

We propose a novel partial key exposure attack on common prime RSA by leveraging lattice-based techniques. In common prime RSA, the primes $p$ and $q$ are defined as $p=2ga+1$ and $q=2gb+1$ for a common prime $g$. Recently, Zheng introduced the first partial key exposure attack on this scheme; however, it is limited to instances where $g > N^{1/4}$. In contrast, our work investigates deeper into partial key exposure attacks by presenting a unified generic case that targets one consecutive unknown block of the private key. By employing a lattice-based solving strategy for trivariate integer polynomials, we can effectively identify additional weak private keys that are vulnerable to partial exposure. Extensive numerical experiments validate the correctness and practicality of our proposed attack on common prime RSA.

In this paper, we present a new small private exponent attack on RSA by combining continued fractions and Coppersmith's techniques. Our results improve upon previous bounds, including Herrmann-May's attack, by leveraging a crucial relation derived from continued fraction. Additionally, we extend the range of vulnerable small private exponents by considering the partial leakage of prime factors or their sum. Our main result establishes an improved attack bound $ d < N^{1-\alpha/3-\gamma/2} $, where $ \alpha := \log_{N} e $ and $ \gamma := \log_{N} |p+q-S| $, with $ S $ being an approximation of the prime sum $ p+q $. Furthermore, we explore more applications of our main attack in scenarios where the primes share some most or least significant bits. The validity of our proposed main attack is confirmed through numerical experiments, demonstrating its improved performance over existing attacks.

Patient monitoring in hospitals, nursing centers, and home care can be largely automated using cameras and machine-learning-based video analytics, thus considerably increasing the efficiency of patient care. In particular, Facial-expression-based Pain Assessment Systems (FePAS) can automatically detect pain and notify medical personnel. However, current FePAS solutions using cloud-based video analytics offer very limited security and privacy protection. This is problematic, as video feeds of patients constitute highly sensitive information. To address this problem, we introduce SecFePAS, the first FePAS solution with strong security and privacy guarantees. SecFePAS uses advanced cryptographic protocols to perform neural network inference in a privacy-preserving way. To counteract the significant overhead of the used cryptographic protocols, SecFePAS uses multiple optimizations. First, instead of a cloud-based setup, we use edge computing with a 5G connection to benefit from lower network latency. Second, we use a combination of transfer learning and quantization to devise neural networks with high accuracy and optimized inference time. Third, SecFePAS quickly filters out unessential frames of the video to focus the in-depth analysis on key frames. We tested SecFePAS with the SqueezeNet and ResNet50 neural networks on a real pain estimation benchmark. SecFePAS outperforms state-of-the-art FePAS systems in accuracy and optimizes secure processing time.

Registered attribute-based encryption (ABE) enables fine-grained access control to encrypted data without a trusted authority. In this model, users generate their own public keys and register their public key along with a set of attributes with a key curator. The key curator aggregates the public keys into a short master public key that functions as the public key for an ABE scheme. A limitation of ABE (registered or centralized) is the assumption that a single entity manages all of the attributes in a system. In many settings, the attributes belong to different organizations, making it unrealistic to expect that a single entity manage all of them. In the centralized setting, this motivated the notion of multi-authority ABE, where multiple independent authorities control their individual set of attributes. Access policies are then defined over attributes across multiple authorities. In this work, we introduce multi-authority registered ABE, where multiple (independent) key curators each manage their individual sets of attributes. Users can register their public keys with any key curator, and access policies can be defined over attributes from multiple key curators. Multi-authority registered ABE combines the trustless nature of registered ABE with the decentralized nature of multi-authority ABE. We start by constructing a multi-authority registered ABE scheme from composite-order pairing groups. This scheme supports an a priori bounded number of users and access policies that can be represented by a linear secret sharing scheme (which includes monotone Boolean formulas). Our construction relies on a careful integration of ideas from pairing-based registered ABE and multi-authority ABE schemes. We also construct a multi-authority registered ABE scheme that supports an unbounded number of users and arbitrary monotone policies using indistinguishability obfuscation (and function-binding hash functions).

Password managers have become widely adopted and are commonly recommended to improve user security. However, current cloud-based solutions rely on the implicit assumption that password manager providers are fully trusted. This assumption is never questioned, as password managers are typically operated by their own designers, who are therefore judge and jury. Users are thus exposed to significant risks: a malicious provider could perform covert actions to access or alter credentials without being detected. Most password managers rely solely on the strength of a user-chosen master password. This design enables a covert adversary to mount large-scale offline attacks to crack weak master passwords. Even more concerning, some popular password managers do not encrypt credentials on users' devices, transmitting them in plaintext prior to server-side encryption, as is the case with Google default configuration. On the other hand, key-protected password managers such as KeePassXC offer stronger protection but lack native support for multi-device synchronization, limiting their adoption. Motivated by these observations, we define a comprehensive set of security properties that any cloud-based password manager should satisfy. We demonstrate that none of the widely deployed mainstream solutions fulfill these fundamental requirements. Nevertheless, we argue that it is feasible to design a password manager that is resilient to covert adversaries while supporting secure cross-device synchronization. To support our claims, we propose a provably secure design that meets all identified properties.

No $t$-resilient Byzantine Agreement (or Reliable Broadcast) protocol can guarantee agreement among $n$ correct processes in a non-synchronous network if the actual number of faulty processes $f$ is $\geq n - 2t$. This limitation highlights the need to augment such fragile protocols with mechanisms that detect safety violations, such as forensic support and accountability. This paper introduces simple and efficient techniques to address this challenge by proposing a new generic transformation, $\mathcal{ABC}^{++}$. The transformation leverages two key primitives: $\textit{ratifier}$ and the $\textit{propagator}$. By sequentially composing these primitives with any closed-box Byzantine Agreement (or Reliable Broadcast) protocol, $\mathcal{ABC}^{++}$ produces a robust counterpart that provides both (adaptively-secure) forensic support and ($1$-delayed adaptively-secure) accountability. The transformation incurs a subquadratic additive communication overhead, with only $1$ round of overhead for decision and forensic support, and $2$ additional rounds for detection in case of a safety violation (or $O\big(\log n \big)$ additional rounds with optimized communication). The generality of $\mathcal{ABC}^{++}$ offers a compelling general alternative to the subquadratic forensic support solution by Sheng et al. (FC'23) tailored to HotStuff-like protocols, while being more efficient than the (strongly-adaptively-secure) quadratic $\mathcal{ABC}$ accountable transformation (IPDPS'22, JPDC'23). Moreover, it provides the first subquadratic accountable Byzantine Agreement (or Reliable Broadcast) protocols against a ($1$-delayed) adaptive adversary. Finally, any subquadratic accountable Reliable Broadcast protocol can be integrated into the $\tau_{scr}$ transformation (ICDCS'22) to produce an improved variant, $\tau_{scr}^{++}$. This new version compiles any deterministic (and even beyond) protocol into its accountable counterpart with subquadratic multiplicative communication overhead, significantly improving upon the original quadratic overhead in $\tau_{scr}$.

An $(\epsilon_\mathsf{s},\epsilon_{\mathsf{zk}})$-weak non-interactive zero knowledge (NIZK) argument has soundness error at most $\epsilon_\mathsf{s}$ and zero-knowledge error at most $\epsilon_{\mathsf{zk}}$. We show that as long as $\mathsf{NP}$ is hard in the worst case, the existence of an $(\epsilon_\mathsf{s}, \epsilon_{\mathsf{zk}})$-weak NIZK proof or argument for $\mathsf{NP}$ with $\epsilon_{\mathsf{zk}} + \sqrt{\epsilon_\mathsf{s}} < 1$ implies the existence of one-way functions. To obtain this result, we introduce and analyze a strong version of universal approximation that may be of independent interest. As an application, we obtain NIZK amplification theorems based on very mild worst-case complexity assumptions. Specifically, [Bitansky-Geier, CRYPTO'24] showed that $(\epsilon_\mathsf{s}, \epsilon_{\mathsf{zk}})$-weak NIZK proofs (with $\epsilon_\mathsf{s}$ and $\epsilon_{\mathsf{zk}}$ constants such that $\epsilon_\mathsf{s} + \epsilon_{\mathsf{zk}} < 1$) can be amplified to make their errors negligible, but needed to assume the existence of one-way functions. Our results can be used to remove the additional one-way function assumption and obtain NIZK amplification theorems that are (almost) unconditional; only requiring the mild worst-case assumption that if $\mathsf{NP} \subseteq \mathsf{ioP/poly}$, then $\mathsf{NP} \subseteq \mathsf{BPP}$.

Ensuring rigorous protection against physical attacks that simultaneously combine passive side-channel observations with active fault injections is a recent and rapidly evolving research area. Polynomial masking is a promising countermeasure, as it provides both privacy against leakage and redundancy against faults. At CRYPTO 2023, Berndt et al. introduced the ``LaOla’’ scheme, which protects arbitrary circuits against such attacks. However, their model tolerates only a global threshold of e faults across the entire circuit, which fundamentally limits scalability. In this work, we overcome this restriction by extending fault robustness to the region fault model, where an adversary can inject up to \(e\) faults in each gadget. We present the first gadgets secure against combined leakage and fault attacks in this stronger model. This improvement allows us to tolerate up to \(x \cdot {e}\) faults across a circuit with \(x\) gadgets instead of just a total of \(e\) as in previous works. Consequently, the protection order \(e\) can remain constant. To achieve this, we introduce sufficient and practically attainable security definitions that are strictly stronger than those of Berndt et al. We further apply this principle to the LaOla construction, proving our stronger security notions for the adapted multiplication gadget.

Matrix inversion is a fundamental operation, but performing it over encrypted matrices remains a significant challenge. This is mainly due to the fact that conventional inversion algorithms—such as Gaussian elimination—depend heavily on comparison and division operations, which are computationally expensive to perform under homomorphic encryption. To mitigate this, Ahn et al. (ESORICS 2023) introduced an inversion method based on iterative matrix multiplications. However, their approach encrypts matrices entry-wise, leading to poor scalability. A key limitation of prior work stems from the absence of an efficient matrix multiplication technique for matrix-packed ciphertexts, particularly one with low multiplicative depth. In this paper, we present a novel homomorphic matrix multiplication algorithm optimized for matrix-packed ciphertexts, requiring only a multiplicative depth of two. Building on this foundation, we propose an efficient algorithm for homomorphic matrix inversion. Experimental results show that our method outperforms the state-of-the-art: for $8\times 8$ matrices, it achieves a $6.8\times$ speedup over the method by Ahn et al., and enables inversion of larger matrices that were previously infeasible. We further compare our homomorphic matrix multiplication technique against existing matrix-packed homomorphic matrix multiplication algorithms. When used for iterative inversion, our method consistently outperforms prior approaches. In particular, for $16\times 16$ and $32\times 32$ matrices, it achieves $1.88\times$ and $1.43\times$ speedups, respectively, over the algorithm by Aikata and Roy. Finally, we demonstrate the practical benefits of our method by applying it to privacy-preserving linear regression. For a dataset of $64$ samples with $8$ features, our approach achieves a $1.13\times$ speedup in training time compared to the state-of-the-art homomorphic matrix inversion solution.

While digital signatures serve to confirm message integrity and the identity of the signer, the inherent link between the public key and the signer’s identity can pose challenges in anonymized networks or applications focused on preserving privacy. Signatures with randomiz- able keys aim to disentangle the signer’s identity from their public key, thus preserving the signature’s validity. This approach ensures that the signature, even with a randomized key, maintains its verifiability without linking it to the signer’s identity. Although signatures with randomizable keys effectively maintain privacy, additional structural improvements are necessary in specialized signature schemes for complex cryptographic frameworks. Threshold structure- preserving signatures offer a way to construct modular protocols while retaining the benefits of structure-preserving properties. Thus, the ran- domizable key version of it is essential for a wide range of applications, making it the foundation of this work. In this study, signatures with ran- domizable key principles combined with threshold structure-preserving signatures to build a strong cryptographic base for privacy-preserving applications. This foundation makes sure that signatures are valid while also being modular and unlinkable. An earlier version of this work appeared in the 22nd International Con- ference on Security and Cryptography(SECRYPT 2025) [6]; the present article extends that study by adding the formal security proofs of the introduced protocols.

Fully Homomorphic Encryption (FHE) is an encryption scheme that allows for computation to be performed directly on encrypted data. FHE effectively closes the loop on secure and outsourced computing; data is encrypted not only during rest and transit, but also during processing. Moreover, modern FHE schemes such as RNS-CKKS (with the canonical slot encoding) encrypt one-dimensional floating-point vectors, which makes such a scheme an ideal candidate for building private machine learning systems. However, RNS-CKKS provides a limited instruction set: SIMD addition, SIMD multiplication, and cyclic rotation of these encrypted vectors. This restriction makes performing multi-dimensional tensor operations (such as those used in machine learning) challenging. Practitioners must pack multi-dimensional tensors into 1-D vectors and map tensor operations onto this one-dimensional layout rather than their traditional nested structure. And while prior systems have made significant strides in automating this process, they often hide critical packing decisions behind layers of abstraction, making debugging, optimizing, and building on top of these systems difficult. In this work we ask: can we build an FHE tensor system with a straightforward and transparent packing strategy regardless of the tensor operation? We answer affirmatively and develop a packing strategy based on Einstein summation (einsum) notation. We find einsum notation to be ideal for our approach since the notation itself explicitly encodes the dimensional structure and operation directly into its syntax, naturally exposing how tensors should be packed and manipulated in FHE. We make use of einsum's explicit language to decompose einsum expressions into a fixed set of FHE-friendly operations: dimension expanding and broadcasting, element-wise multiplication, and a reduction along the contraction dimensions. We implement our design and present EinHops, which stands for Einsum Notation for Homomorphic Tensor Operations. EinHops is a minimalist system that factors einsum expressions into a fixed sequence of FHE operations, enabling developers to perform complex tensor operations using RNS-CKKS while maintaining full visibility into the underlying packing strategy. We evaluate EinHops on a range of tensor operations from a simple transpose to complex multi-dimensional contractions. We show that the explicit nature of einsum notation allows us to build an FHE tensor system that is simple, general, and interpretable. We open-source EinHops at the following repository: https://github.com/baahl-nyu/einhops.

This paper explores how zero-knowledge proofs can enhance Bitcoin's functionality and privacy. First, we consider Proof-of-Reserve schemes: by using zk-STARKs, a custodian can prove its Bitcoin holdings are more than a predefined threshold X, without revealing addresses or actual balances. We outline a STARK-based protocol for Bitcoin UTXOs and discuss its efficiency. Second, we examine ZK Light Clients, where a mobile or lightweight device verifies Bitcoin's proof-of-work chain using succinct proofs. We propose a protocol for generating and verifying a STARK-based proof of a chain of block headers, enabling trust-minimized client operation. Third, we explore Privacy-Preserving Rollups via BitVM: leveraging BitVM, we design a conceptual rollup that keeps transaction data confidential using zero-knowledge proofs. In each case, we analyze security, compare with existing approaches, and discuss implementation considerations. Our contributions include the design of concrete protocols adapted to Bitcoin's UTXO model and an assessment of their practicality. The results suggest that while ZK proofs can bring powerful features (e.g., on-chain reserve audits, trustless light clients, and private layer-2 execution) to Bitcoin, each application requires careful trade-offs in efficiency and trust assumptions.

HQC is a code-based cryptosystem that has recently been announced for standardization after the fourth round of the NIST post-quantum cryptography standardization process. During this process, the NIST specifically required submitters to provide two kinds of implementation: a reference one, meant to serve lisibility and compliance with the specifications; and an optimized one, aimed at showing the performance of the scheme alongside other desirable properties such as resilience against implementation misuse or side-channel analysis. While most side-channel attacks regarding PQC candidates running in this process were mounted over reference implementations, very few consider the optimized, allegedly side-channel resistant (at least, constant-time), implementations. Unfortunately, HQC optimized version only targets x86-64 with Single Instruction Multiple Data (SIMD) support, which reduces the code portability, especially for non-generalist computers. In this work, we present two power side-channel attacks on the optimized HQC implementation with just the SIMD support deactivated. We show that the power leaks enough information to recover the private key, assuming the adversary can ask the target to replay a legitimate decryption with the same inputs. Under this assumption, we first present a key-recovery attack targeting standard Instruction Set Architectures (ARM T32, RISC-V, x86-64) and compiler optimization levels. It is based on the well known Hamming Distance model of power consumption leakage, and exposes the key from a single oracle call. During execution on a real target, we show that a different leakage, stemming from to the micro-architecture, simplifies the recovery of the private key. This more direct second attack, succeeds with a 99% chance from 83 executions of the same legitimate decryption. While the weakness leveraged in this work seems quite devastating, we discuss simple yet effective and efficient countermeasures to prevent such a key-recovery.

Interactive Oracle Proofs (IOPs) form the backbone of some of the most efficient general-purpose cryptographic proof-systems. In an IOP, the prover can interact with the verifier over multiple rounds, where in each round the prover sends a long message, from which the verifier only queries a few symbols. State-of-the-art IOPs achieve a linear-size prover and a poly-logarithmic verifier but require a relatively large, logarithmic, number of rounds. While the Fiat-Shamir heuristic can be used to eliminate the need for actual interaction, in modern highly-parallelizable computer architectures such as GPUs, the large number of rounds still translates into a major bottleneck for the prover, since it needs to alternate between computing the IOP messages and the Fiat-Shamir hashes. Motivated by this fact, in this work we study the round complexity of linear-prover IOPs. Our main result is an IOP for a large class of Boolean circuits, with only $O(\log^*(S))$ rounds, where $\log^*$ denotes the iterated logarithm function (and $S$ is the circuit size). The prover has linear size $O(S)$ and the verifier runs in time $\mathrm{polylog}(S)$ and has query complexity $O(\log^*(S))$. The protocol is both conceptually simpler, and strictly more efficient, than prior linear prover IOPs for Boolean circuits.

The Matter protocol has emerged as the leading standard for secure IoT interoperability, backed by major vendors such as Apple, Google, Amazon, Samsung, and others. With millions of Matter devices already deployed, its security guarantees are critical to the safety of modern IoT ecosystems. This paper presents the first in-depth analysis of Matter's key establishment protocols: Passcode-Authenticated Session Establishment (PASE) and Certificate-Authenticated Session Establishment (CASE), which are based on the well-studied SPAKE2+ and SIGMA, respectively. We first perform a specification-level security analysis of PASE and CASE, comparing Matter's design choices against the original SPAKE2+ and SIGMA protocols. This reveals weaknesses such as low-entropy setup passcodes, static per-device salts, and weak PBKDF2 parameters. Next, to assess how such weaknesses manifest in practice, we analyse a certified Matter codebase and find that critical safeguards such as limiting failed pairing attempts are not enforced. All identified vulnerabilities were responsibly disclosed and have been patched. We then complement our analysis by formally verifying PASE, CASE, CASE Resumption, and the original SPAKE2+ and SIGMA protocols. In particular, we show in the symbolic model that the security of Matter's lightweight session re-establishment mechanism (CASE Resumption), used for the vast majority of Matter sessions, rests entirely on the secrecy of an ephemeral key generated by an IoT device. Building on all three stages, we construct proof-of-concept attacks and evaluate their feasibility under Matter's own threat model. Our results invalidate several countermeasures specified in Matter's threat model, including protections for threats classified as ``High Risk''. Overall, our work shows that strong cryptographic building blocks alone are insufficient unless the surrounding protocol and deployment rules are equally rigorously specified and tested at the standard level.

The (Multi-)Scalar multiplication is a crucial operation in numerous FHE-related applications, and its performance has a significant impact on their overall efficiency. This paper presents SMOOTHIE: (Multi-)Scalar Multiplication Optimisations On TFHE, introducing new techniques to improve the performance of single- and multi-scalar multiplications in TFHE. We show that the bucket/Pippenger method, rooted in the elliptic curve field, can be successfully adapted to TFHE when combined with new optimisations that address their inherent differences. We propose a new negation with offset technique that eliminates direct carry propagation after ciphertext negation. Additionally, we introduce a bucket merging technique for the bucket aggregation step, which exploits TFHE properties to reduce bootstrap operations. Specifically, in the multi-scalar multiplication case, we implement a bucket doubling method that eliminates the need for precomputation on each input ciphertext. Our implementation is integrated in the TFHE-rs library and achieves up to $\times2.05$ speedup for single-scalar multiplication compared to the current state-of-the-art, with multi-scalar multiplication improvements up to $\times6.43$, depending on the vector sizes.

Online services increasingly require users to verify their identity or parts of it, often by law. This verification is usually performed by processing data from official identity documents, like national identity cards. However, these documents often contain significantly more information than the verifying party needs to know, including information that should stay private. Disclosing this information is a significant privacy and security risk for the user. Traditional work has designed selective disclosure and zero-knowledge proof protocols for such use cases. However, because these require a complete reimplementation, recall and redistribution of existing identity documents, they have never been adopted on a large scale. More recent work has focused on creating zero-knowledge proofs from existing identity documents like the US passport or specific US driver licenses. In this article, we propose an R1CS protocol to efficiently parse and extract fields from existing European National Identity Cards, with an implementation for the Belgian BeID. The protocol is able to prove correct extraction of a date-of-birth field in 22 seconds on a consumer device, with verification taking 230 milliseconds. With this, we aim to provide EU citizens with a practical solution to the privacy and security risks that arise when one has to prove their authenticity or authority to a third party.

Recently, two independent differential attacks on SPEEDY-7-192 were proposed by Boura et al. and by Beyne and Neyt. Both works present, for the first time, a valid differential attack on SPEEDY-7-192 with time complexities of $2^{186.36}$ and $2^{185}$ respectively. In this note, by extending the search space for 1-round trails, we propose a new differential attack on SPEEDY-7-192 with both data and time complexity of $2^{174.80}$. This improves upon both previous attacks by more than a factor of $2^{10}$.

We present improved definitions and constructions for copy-protected digital signatures and pseudorandom functions (PRFs). Our new security definitions support challenge messages or inputs chosen from arbitrary high min-entropy distributions and allow signing or evaluation queries. This extends prior definitions, which assumed uniformly random challenges and did not consider oracle access. We construct schemes that satisfy these stronger definitions using only polynomially secure indistinguishability obfuscation (iO) and one-way functions (OWFs), avoiding the subexponential assumptions and the Learning with Errors (LWE) assumption used in previous constructions, even in the uniform-challenge and query-free setting. Moreover, our constructions and security proofs are arguably simpler than existing ones. We also propose a new security notion for unclonable puncturable obfuscation (UPO), which primarily extends prior definitions to support challenge inputs drawn from arbitrary high min-entropy distributions, along with some additional refinements. We construct a UPO satisfying this notion from polynomially secure iO and the LWE assumption, thereby avoiding the subexponential assumptions and unproven conjectures required in previous constructions, even in the uniform-challenge setting. In fact, in the uniform-challenge case, we show that iO and OWFs alone suffice, further removing the need for LWE. Again, our constructions and security proofs are arguably simpler than existing ones. As applications, we show that a UPO satisfying this notion is sufficient to copy-protect a variety of puncturable functionalities beyond those studied in the prior work.

We present OasisDB, an oblivious and scalable RBDMS framework designed to securely manage relational data while protecting against access and volume pattern attacks. Inspired by plaintext RDBMSs, OasisDB leverages existing oblivious key value stores (KV-stores) as storage engines and securely scales them to enhance per-formance. Its novel multi-tier architecture allows for independent scaling of each tier while supporting multi-user environments without compromising privacy. We demonstrate OasisDB’s flexibility by deploying it with two distinct oblivious KV-stores, PathORAM and Waffle, and show its capability to execute a variety of SQL queries, including point and range queries, joins, aggregations, and limited updates. Experimental evaluations on the Epinions dataset show that OasisDB scales linearly with the number of machines. When deployed with a plaintext KV-store, OasisDB introduces negligible overhead in its multi-tier architecture compared to a plaintext database, CockroachDB. We also compare OasisDB with ObliDB, an oblivious RDBMS, highlighting its advantages with scalability and multi-user support.

We introduce the new AXU hash function decBRWHash, which is parameterised by the positive integer $c$ and is based on Bernstein-Rabin-Winograd (BRW) polynomials. Choosing $c>1$ gives a hash function which can be implemented using $c$-way single instruction multiple data (SIMD) instructions. We report a set of very comprehensive hand optimised assembly implementations of 4-decBRWHash using avx2 SIMD instructions available on modern Intel processors. For comparison, we also report similar carefully optimised avx2 assembly implementations of polyHash, an AXU hash function based on usual polynomials. Our implementations are over prime order fields, specifically the primes $2^{127}-1$ and $2^{130}-5$. For the prime $2^{130}-5$, for avx2 implementations, compared to the famous Poly1305 hash function, 4-decBRWHash is faster for messages which are a few hundred bytes long and achieves a speed-up of about 16% for message lengths in a few kilobytes range and improves to a speed-up of about 23% for message lengths in a few megabytes range.

We introduce a new compact and constant-time implementation of the FAEST v1.1 signature scheme that allows it to run in resource-constrained Arm Cortex-M4 microcontrollers under 190M cycles for signing or verifying at level 1 security. The main technique for reducing the memory footprint is a new abstraction to reuse or recompute VOLEs on demand, which reduces memory consumption by at least an order of magnitude.

Many protocols, like HTTP, FTP, POP3, and SMTP, were origi- nally designed as synchronous plaintext protocols – commands and data are sent in the clear, and the client waits for the response to a pending request before sending the next one. Later, two main solutions were introduced to retrofit these protocols with TLS protection. (1) Implicit TLS: Designate a new, well-known TCP port for each protocol-over-TLS, and start with TLS immediately. (2) Opportunistic TLS: Keep the original well-known port and start with the plaintext protocol, then switch to TLS in response to a command like STARTTLS. In this work, we present a novel weakness in the way TLS is integrated into popular application layer protocols through implicit and opportunistic TLS. This weakness breaks authentication, even in modern TLS implementations if both implicit TLS and oppor- tunistic TLS are supported at the same time. This authentication flaw can then be utilized to influence the exchanged messages after the TLS handshake from a pure MitM position.In contrast to previ- ous attacks on opportunistic TLS, this attack class does not rely on bugs in the implementations and only requires one of the peers to support opportunistic TLS. We analyze popular application layer protocols that support opportunistic TLS regarding their vulnerability to the attack. To demonstrate the practical impact of the attack, we analyze exploita- tion techniques for HTTP (RFC 2817) in detail, and show four different exploit directions. To estimate the impact of the attack on deployed servers, we conducted a series of IPv4-wide scans over multiple protocols and ports to check for support of opportunistic TLS. We found that support for opportunistic TLS is still widespread for many application protocols, with over 3 million servers support- ing both, implicit and opportunistic TLS at the same time. In the case of HTTP, we found 20,121 servers that support opportunistic HTTP across 35 ports, with 2,268 of these servers also supporting HTTPS and 539 using the same domain names for implicit HTTPS, presenting an exploitable scenario.

Hash functions and extendable output functions are some of the most fundamental building blocks in cryptography. They are often used to build commitment schemes where a committer binds themselves to some value that is also hidden from the verifier until the opening is sent. Such commitment schemes are commonly used to build signature schemes, e.g., Ed25519 via Schnorr signatures, or non-interactive zero-knowledge proofs. We specifically analyze the binding security when Ascon-Hash256 or Ascon-XOF128 is used inside of Ed25519, which is closely related to finding second preimages. While there is ample prior work on Ascon-XOF128 and Ascon-Hash256, none of it applies in this setting either because it analyzes short outputs of 64 or 128 bits or because the complexity is above the security claim and generic attack of 128 bits. We show how to exploit the setting of finding a forgery for Ed25519. We find that this setting is quite challenging due to the large 320-bit internal state combined with the 128-bit security level. We propose a second-preimage attack for 1-round Ascon-Hash256 with a complexity of $2^{64}$ Gaussian eliminations and a random-prefix-preimage attack (also known as Nostradamus attack) for 1-round Ascon-Hash256, for the Ed25519 setting, with complexity $2^{29.7}$ Gaussian eliminations.

We study the multi-source randomness extraction and generation properties of the monolithic random oracle (RO), whereby one is tasked with extracting or generating uniform random bits from multiple arbitrary unpredictable sources. We formalize this problem according to the query complexities of the involved parties—sources, distinguishers, and predictors, where the latter are used to define unpredictability. We show both positive and negative results. On the negative side, we rule out definitions where the predictor is not at least as powerful as the source or the distinguisher. On the positive side, we show that the RO is a multi-source extractor when the query complexity of the distinguisher is bounded. Our main positive result in this setting is with respect to arbitrary unpredictable sources, which we establish via a combination of a compression argument (Dodis, Guo, and Katz, EUROCRYPT'17) and the decomposition of high min-entropy sources into flat sources. Our work opens up a rich set of problems, ranging from statistical multi-source extraction with respect to unbounded distinguishers to novel decomposition techniques (Unruh, CRYPTO'07; Coretti et al., EUROCRYPT'18) and multi-source extraction for non-monolithic constructions.

In this work, we present methods for conducting higher-order non-profiled side-channel attacks on Lattice-Based Cryptography (LBC). Our analysis covers two scenarios: one where the device leakage is known and follows Hamming weight model, and another where the leakage model is not Hamming weight based and unknown to the attacker. We focus on the Post-Quantum Cryptography (PQC) standards, the Dilithium digital signature (i.e. ML-DSA) and the Kyber key encapsulation (i.e. ML-KEM) algorithms. For Hamming weight leakage, we develop efficient higher-order Correlation Power Analysis (HOCPA) attacks in which the attacker must compute a function known as the optimal prediction function. We revisit the definition of optimal prediction function and introduce a recursive method for computing it efficiently. Our approach is particularly useful when a closed-form formula is unavailable, as in LBC. Then, we introduce sin and cos prediction functions, which prove optimal for HOCPA attacks against second and higher-order masking protection. We validate our methods through simulations and real-device experiments on open-source masked implementations of Dilithium and Kyber on an Arm Cortex-M4. we achieve full secret-key recovery using only 700 and 2400 traces for second and third-order masked implementations of Dilithium, and 2200 and 14500 traces for second and third-order masked implementations of Kyber, respectively. For the unknown leakage scenarios, we leverage generic Side-Channel Analysis (SCA) distinguishers. A key challenge here is the injectivity of modular multiplications in NTT based polynomial multiplication, typically addressed by bit-dropping in the literature. However, we experimentally show that bit-dropping is largely inefficient against protected implementations of LBC. To overcome this limitation, we present a novel two-step attack to Kyber, combining generic distinguishers and lattice reduction techniques. Our approach decreases the number of predictions from q^2 to q and does not rely on bit-dropping. Our experimental results demonstrate a speed-up of up to 23490x in attack run-time over the baseline along with improved success rate.

Homomorphic signature (HS) schemes enable an untrusted server to run some computation over the data signed under the same key and derive a short signature for authenticating the computation result. Fiore et al. (Asiacrypt’16) introduced novel lattice-based multi-key homomorphic signatures (MKHS) to support an evaluation of signatures under multiple/different keys, and anyone can verify the resultant signature by using corresponding public verification keys. However, a limitation of their scheme is that even if only one signing key is leaked, a malicious server can forge a signature on a fake computation result involving the inputs of uncorrupted signers. To address this issue, we propose a new scheme built upon the work of Fiore et al., aiming to achieve a stronger security guarantee, which we call forward unforgeability, against signing key leakage. Our MKHS scheme is constructed based on the short integer solution (SIS) problem as Fiore et al., and can be forward-unforgeable even if an adversary obtains all the signing keys. Furthermore, we propose a variant by introducing a helper entity to amortize the overhead of signature verifications.

Fully Homomorphic Encryption over the Torus (TFHE) enables efficient evaluation of arbitrary lookup tables (LUT) over encrypted data, allowing complex functions to be computed without decryption. However, in TFHE, only lookup tables with a negacyclic structure can be homomorphically evaluated, which limits the range of functions that can be supported. To overcome this limitation and enable the evaluation of arbitrary functions, the notion of full-domain functional bootstrapping (FDFB) was introduced. However, existing FDFB methods require at least two consecutive bootstrapping operations to evaluate a single function, resulting in significant latency and overhead. In this work, we present a novel FDFB scheme that supports arbitrary lookup tables by decomposing them into multiple small negacyclic LUTs and one compact full-domain LUT. This structure allows most computations to be handled by fast negacyclic bootstrapping, significantly reducing the computational cost. To address the need for maintaining distinct evaluation keys for each LUT length, we apply Extended Bootstrapping (PKC 2021), which enables all operations to run within a fixed ring dimension. Combined with Extended Bootstrapping, our method nearly halves the bootstrapping cost compared to prior FDFB approaches while maintaining a constant key size, negligible parameter overhead, and strong scalability. Finally, we implement our algorithm using the TFHE-go library and evaluate its performance across various settings. Our method achieves up to a 3.41× speedup over previous FDFB schemes without increasing key size, and retains up to a 1.91× advantage even when Extended Bootstrapping is applied to both.

Suppose Alice holds a master secret key $\mathsf{sk}$ in an identity-based encryption scheme. For a given set of identities $\mathcal{I}$, Alice wants to create a short pre-decryption key that lets anyone decrypt the ciphertexts encrypted under any identity in $\mathcal{I}$ and nothing else. This problem is called batch identity-based encryption (batch IBE). When the secret key $\mathsf{sk}$ is shared among a number of decryption parties, the problem is called threshold batch identity-based encryption. This question comes up in the context of an encrypted mempool where the goal is to publish a short pre-decryption key that can be used to decrypt all ciphertexts in a block. Prior work constructed batch IBE schemes with some limitations. In this work, we construct new batch IBE and threshold batch IBE schemes. We first observe that a key-policy ABE (KP-ABE) scheme directly gives a batch IBE scheme. However, the best KP-ABE schemes happen to be lattice-based, and do not thresholdize efficiently. We then use very different techniques to construct a new lattice-based batch IBE scheme. Our construction employs a recent preimage sampler due to Waters, Wee, and Wu. Along the way, we develop a two-round protocol for preimage lattice sampling when the lattice trapdoor is secret shared among the participants.

This is a systematization of knowledge (SoK) on BitVM with succinct on-chain cost. 1. from different cryptographic primitives: - Minicrypt privacy-free garbled circuits (PFGC) - homomorphic message authentication codes (HMAC), which implies succinct PFGC - attribute-based laconic function evaluation (AB-LFE), which implies reusable PFGC 2. using different malicious security compilers: - cut-and-choose (C&C) - non-interactive zero-knowledge proofs (NIZK) - fraud proofs on Bitcoin 3. with different proof systems: - publicly verifiable SNARK - designated-verifiable SNARK (DV-SNARK) 4. in different protocol directions: - standard BitVM (operator = garbler, challengers = evaluators) - reverse BitVM (operator = evaluator, challengers = garblers) 5. given different operator liveness setup: - existential honesty - honest majority

Probabilistically checkable proofs (PCPs) allow encoding a computation so that it can be quickly verified by only reading a few symbols. Inspired by tree codes (Schulman, STOC'93), we propose tree PCPs; these are PCPs that evolve as the computation progresses so that a proof for time $t$ is obtained by appending a short string to the end of an accepting proof for time $t-1$. At any given time, the tree PCP can be locally queried to verify the entire computation so far. We construct tree PCPs for non-deterministic space-$s$ computation, where at time step $t$, the proof only grows by an additional $\textnormal{poly}(s)\cdot t^\varepsilon$ bits, and the number of queries made by the verifier to the overall proof is $\textnormal{poly}(s)\cdot t^\varepsilon$, for an arbitrary constant $\varepsilon>0$. Tree PCPs are well-suited to proving correctness of ongoing computation that unfolds over time, in particular in a distributed setting where the computation is carried by mutually untrusting generations. They may be thought of as an information-theoretic analog of the cryptographic notion of incrementally verifiable computation (Valiant, TCC'08). To obtain tree PCPs, we present the first results establishing strong local testability and local correctability for tree codes, and construct a tree code that achieves both properties simultaneously.

Deep learning (DL)-based side-channel analysis (SCA) has emerged as a powerful approach for extracting secret information from cryptographic devices. However, its performance often deteriorates when targeting implementations protected by masking and desynchronization-based countermeasures, or when analyzing long side-channel traces. In earlier work, we proposed EstraNet, a Transformer Network (TN)-based model designed to address these challenges by capturing long-distance dependencies and incorporating shift-invariant attention mechanisms. In this work, we perform an in-depth analysis of the internal behavior of EstraNet and propose methods to further enhance its effectiveness. First, we introduce {\bf DL-ProVe} (Deep Learning Leakage Propagation Vector Visualization), a novel technique for visualizing how leakage from secret shares in a masked implementation propagates and recombines into the unmasked secret through the layers of a DL model trained for SCA. We then apply DL-ProVe to EstraNet, providing the first detailed explanation of how leakage is accumulated and combined within such an architecture. Our analysis reveals a critical limitation in EstraNet’s multi-head GaussiP attention mechanism when applied to long traces. Based on this insights, we identify a new architectural hyperparameter which enables fine-grained control over the initialization of the attention heads. Our experimental results demonstrate that tuning this hyperparameter significantly improves EstraNet’s performance on long traces (with upto 250K features), allowing it to reach the guessing entropy 1 using only 3 attack traces while the original EstraNet model fails to do so even with 5K traces. These findings not only deepen our understanding of EstraNet’s internal workings but also introduce a robust methodology for interpreting, diagnosing, and improving DL models for SCA.

This paper introduces the weighted sum correlation analysis method, a profiled higher-order side-channel attack that quantifies the significance of time-domain samples based on a chosen leakage model. We also demonstrate the utility of the Hilbert transform in side-channel analysis, showing how its phase-shifting property can be exploited to construct an effective fused score that combines multiple correlation coefficients into a single metric. We validate the presented method on the challenging case of the AES-CCM accelerator in a commercial Bluetooth chip, leveraging RF signals captured via a software-defined radio as a side channel. Compared to the correlation analysis methods presented at RWC'25 and CHES'25, the weighted sum approach achieves at least a threefold reduction in the number of traces required for key recovery. Remarkably, it also outperforms deep learning-based analysis.

Differential meet-in-the-middle (MITM) cryptanalysis, recently introduced by Boura et al., has emerged as a powerful and versatile technique for assessing the security of modern block cipher designs. Since its introduction, this method has been effectively applied to a variety of block ciphers, including different variants of SKINNY, CRAFT, and AES. However, identifying such attacks manually–especially on bit-oriented ciphers with large block sizes–can be a complex and error-prone process, which underscores the growing importance of automated solutions in this domain. In this work, we present, for the first time to the best of our knowledge, a novel and efficient automated tool for constructing optimized differential MITM attacks on bit-oriented block ciphers, with a particular focus on AndRX designs. Our framework begins by modeling an efficient constraint programming (CP) model to search for single-key optimal differential trails in AndRX ciphers. Building on this, we propose a unified bitwise CP model to automatically construct optimized differential MITM attacks within the same design framework. Furthermore, we incorporate two dedicated optimization strategies–namely, the equivalent subkey technique and the selective key guessing technique–both of which are tailored to the structural properties of AndRX ciphers and significantly enhance key recovery efficiency. Additionally, we also apply two additional optimization techniques: the parallel partitioning technique and the reducing data with imposed conditions techniques to further enhance the differential MITM attack on AndRX ciphers. To demonstrate the practical effectiveness of our tool, we apply it to all versions of SIMON and Simeck, two widely studied representatives of the AndRX family, and report improved cryptanalytic results. Specifically, we present differential MITM attacks on SIMON-32-64, SIMON-48-96, SIMON-64-128, and SIMON-96-144, covering 23, 25, 32, and 38 rounds, respectively. All of these results represent improvements in the number of attacked rounds compared to the best known differential attacks, classical meet-in-the-middle (MITM), and Demirci-Selçuk MITM (DS-MITM) attacks on the corresponding versions of SIMON. For instance, we present a 37-round differential MITM attack on SIMON-96-144, which extends the best known differential, classical MITM, and DS-MITM attacks by 1, 17, and 18 rounds, respectively. In the case of Simeck, we report a 29-round differential MITM attack on Simeck-48-96, improving the previous best differential attack by one round. These results demonstrate the strength and versatility of our automated tool. Importantly, our automated method for constructing differential MITM attacks operates at the bit level and is generic in nature, making it applicable to a broad class of bit-oriented block ciphers beyond the AndRX family.

Statistical Ineffective Fault Attack (SIFA) presents a critical threat to cryptographic implementations by circumventing conventional detection-based countermeasures effective against traditional fault attacks. Particularly, SIFA operates via two mechanisms: SIFA-1 exploits fault effectiveness dependency on target values, while SIFA-2 leverages conditional propagation of faulted values based on sensitive intermediates. Recent studies suggest that, masking, mainly a side-channel protection, also exhibits promising resistance to SIFA-1, such as prime masking. In this paper, we systematically evaluate the resilience of Inner Product Masking (IPM) against SIFA, which has been established in prior works as a powerful side-channel-resistant alternative to Boolean masking. Specifically, with regard to SIFA-1, our theoretical analysis demonstrates that Inner Product (IP) encoding provides stronger SIFA-1 resistance than both Boolean and prime masking under generic multi-bit fault models using various fault types. More interestingly, an equivalence between Side-channel and SIFA-1 security has been theoretically established for IP encoding, indicating that optimal IP encoding exists that simultaneously provides the highest side-channel resistance and maximizes the complexity of effective SIFA-1 attacks. For SIFA-2, our analysis reveals that IPM’s protection remains fundamentally bounded by the computational field size, consistent with previous results in this regard, e.g., for prime field masking. However, some vulnerabilities to persistent faults are anticipated for the most recently proposed IPM multiplication gadget. Given the compatibility with existing ciphers and demonstrated superior resistance against SIFA-1, IPM emerges as a more promising fault-resistant encoding technique compared to prime masking.

Authentication is a crucial requirement for the security of Quantum Key Distribution (QKD). Yet, the integration of suitable methods in QKD systems tends to receive little attention from the research community. As a result, Wegman-Carter message authentication established itself as the go-to solution, leading to serious inefficiencies and additional trust assumptions, making it hard to recover from denial-of-service attacks. Another method is to use the lattice-based signature scheme Dilithium, as proposed by Wang et al. (npj quantum information; 2021). This method avoids the drawbacks of Wegman-Carter but, unfortunately, introduces new disadvantages. In this work, we implement and test several authentication methods on an actual QKD system. We compare and analyze three authentication variants, i.e., Wegman-Carter, Dilithium, and the established message-authentication code Chaskey, as a new method for authentication in QKD, which uses fewer quantum keys. We focus on the key consumptions, runtimes, and practicality in a field test of the QKD system. Lastly, we take a broader look at authentication for QKD in the context of Denial-of-Service attacks and propose a solution by combining several authentication methods to achieve their individual advantages while simultaneously avoiding several drawbacks.

In ASIACRYPT 2011, Backes, Kate, and Patra (BKP) introduced two computationally secure round-optimal (2-round) Verifiable Secret Sharing (VSS) schemes in the honest-majority setting, one based on non-homomorphic commitments and the other on homomorphic ones. Their scheme based on non-homomorphic commitments has $O(n^2)$ computational complexity and necessitates $O(n^2\lambda)$ public and private communication for the dealer, where $n$ denotes the number of parties and $\lambda$ is the security parameter. They showed that these costs are $n$ times higher compared to their round-optimal VSS scheme employing homomorphic commitments and posed a research question regarding the inevitability of this gap. In this paper, we fill this gap by introducing a new variant of the recently proposed unified framework $\mathbf{\Pi}$ by Baghery at PKC 2025, designed to enable the construction of more efficient round-optimal VSS schemes in the honest-majority setting. Compared to the original framework, our variant reduces the required rounds by one while maintaining compatibility with any commitments and achieving comparable efficiency. Leveraging this new general construction, we develop several round-optimal VSS schemes that surpass state-of-the-art alternatives. Particularly noteworthy is the new round-optimal VSS scheme based on non-homomorphic commitments, which improves the BKP scheme by a factor of $n$ across all efficiency metrics. Compared to their schemes based on homomorphic commitments, our schemes demonstrate significantly expedited verification and reconstruction. Implementation results further validate the practicality of these new VSS schemes. For example, for $(n, t)=(256, 127)$, where $t$ represents the threshold, compared to the hash-based BKP VSS scheme, our proposed scheme showcases speed-ups exceeding $120,000\times$ (and $50\times$) for the dealer (and parties, respectively), while also requiring $365\times$ (and $512\times$) less communication.

This paper reports on the implementation and performance evaluation of Korean Post-Quantum Cryptography standards within existing TLS/X.509 infrastructure. We integrated HAETAE, AIMer, SMAUG-T, and NTRU+—the four KpqC standard algorithms—into the OpenSSL ecosystem via a modified liboqs framework. Then, we measured static overhead (certificate size) and dynamic overhead (TLS handshake latency) under both computational-bound (localhost) and network-bound (LAN) settings. Our results indicate that, focusing on the Korean standards, KpqC certificates are 11.5–48 times larger than the classical ECC baseline. In performance, the tested KpqC KEMs increase handshake latency by over 750\% in computation-bound tests (localhost) and by up to 35\% in network-bound tests (LAN). To our knowledge, this study constitutes the first practical evaluation of KpqC standards in real-world TLS environments, providing concrete performance data to guide post-quantum migration strategies.

Pairing functions uniquely encode pairs of natural numbers into single values, a fundamental operation in mathematics and computer science. This paper presents an alternative approach inspired by geometric visualization—viewing pairs as arrangements of square blocks with missing tiles. Our method achieves packing efficiency comparable to the classical Cantor pairing function and matches the time complexity of both Cantor and Szudzik functions. Encoding is performed in constant time using simple arithmetic operations, while decoding requires square root computations, resulting in efficient inversion. By combining algebraic rigor with intuitive geometric insight, this approach offers a practical and accessible alternative for applications involving data encoding, spatial structures, and combinatorial problems.

Given two elliptic curves over F_q, computing an isogeny mapping one to the other is conjectured to be classically and quantumly hard. This problem plays an important role in the security of elliptic curve cryptography. In 2024, Galbraith applied recently developed techniques for isogenies to improve the state-of-the-art for this problem. In this work, we focus on computing ascending isogenies with respect to an orientation. Our results apply to both ordinary and supersingular curves. We give a simplified framework for computing self-pairings, and show how they can be used to improve upon the approach from Galbraith to recover these ascending isogenies and eliminate a heuristic assumption from his work. We show that this new approach gives an improvement to the overall isogeny recovery when the curves have a small crater (super-polynomial in size). We also study how these self-pairings affect the security of the (PEARL)SCALLOP group action, gaining an improvement over the state-of-the-art for some very particular parameter choices. The current SCALLOP parameters remain unaffected.

In this note we study the proposed cipher Synergy and describe a full round differential with probability $2^{-21.29}$. The claims have been experimentally verified.

With the advancing standardization of post-quantum cryptographic schemes, the need for preparing the IT security infrastructure for integrating post-quantum schemes increases. The focus of this work is a specific part of the IT security infrastructure, namely public key infrastructures. For public certification authorities, it is crucial to guarantee the quality of public keys certified by them. To this end, linting is deployed, which describes the process of analyzing the content of a certificate with respect to predefined rules, the so-called lints. In this work, we initiate the study of lints for post-quantum cryptography. As a starting point, we choose lattice-based schemes and analyze the public keys of the NIST standards ML-KEM and ML-DSA. We base our analyses on the NIST FIPS standards and IETF documents. We formally describe the identified lints and classify them with respect to the property of the public key that the lint checks. We implement the lints for a common X.509 certificate linter and provide an open-source tool.

Attribute-based encryption (ABE) is a versatile primitive that has been considered in many applications to enforce access control cryptographically. To actually benefit from ABE in practice, we require implementations of schemes that satisfy all the properties that are needed. Many theoretical advancements have been made to attain such properties, ultimately resulting in powerful abstractions such as pair encodings. To build an ABE scheme, we use a compiler (in the theoretical sense), which transforms a provably secure pair encoding scheme into a provably secure ABE scheme. Although several such compilers have been introduced, they all abstract away many details that are relevant for engineers, which can hinder the implementation of schemes in practice. To address this problem, we propose pracy, which is a tool that automatically implements an ABE scheme from an input pair encoding scheme. To achieve this, we first note that we need to overcome a general issue in any automation efforts – including automated optimization and security analysis – in the field of pairing-based cryptography. In particular, there exist no parsers that properly model the interaction between the predicate and the pair encodings. Therefore, we devise a new formal model and type system, which capture this interaction in a way that is compatible with automated implementation efforts. To illustrate the feasibility of our model and system, we construct pracy, which is a (practical) compiler in Python that can implement ABE schemes in multiple target programming languages such as Python and C/C++. With pracy, we not only make the implementation of ABE schemes from pair encodings more accessible to practitioners, we realize the potential that pair encodings have to simplify implementation efforts.

In this short note, we describe some further improvements to the key pair generation process for the Falcon and Hawk lattice-based signature schemes, and for the BAT key encapsulation scheme, in a fully constant-time way and without any use of floating-point operations. Our new code is slightly faster than our previous implementation, and, more importantly for small embedded systems, uses less RAM space.

This paper introduces {\em truncated inner $c$-differential cryptanalysis}, a novel technique that for the first time enables the practical application of $c$-differential uniformity to block ciphers. While Ellingsen et al. (IEEE Trans. Inf. Theory, 2020) established the notion of $c$-differential uniformity by analyzing the equation $F(x\oplus a) \oplus cF(x) = b$, a key challenge remained: the outer multiplication by $c$ disrupts the structural properties essential for block cipher analysis, particularly key addition. We resolve this challenge by developing an \emph{inner} $c$-differential approach where multiplication by $c$ affects the input: $(F(cx\oplus a), F(x))$, thereby going back to the original idea of Borisov et al. (FSE, 2002). We prove that the inner $c$-differential uniformity of a function $F$ equals the outer $c$-differential uniformity of $F^{-1}$, establishing a fundamental duality. This modification preserves cipher structure while enabling practical cryptanalytic applications. Our main contribution is a comprehensive multi-faceted statistical-computational methodology, implementing truncated $c$-differential analysis against a 9-round Kuznyechik variant without initial key whitening (which preserves the essential $(cx \oplus a, x)$ differential structure required for our analysis). Through extensive computational analysis involving millions of differential pairs, we demonstrate statistically significant non-randomness across all tested round counts. For the full 9-round cipher, we identify multiple configurations triggering critical security alerts, with bias ratios reaching $1.7\times$ and corrected p-values as low as $1.85 \times 10^{-3}$, suggesting insufficient security margin against this new attack vector. The data complexity of our attack is about $2^{33}$ chosen plaintext pairs, time complexity $2^{34}$ and (negligible) memory complexity $2^{16}$. This represents the first practical distinguisher against a full 9-round (and reduced rounds) Kuznyechik variant.

This paper presents implementations that match and, where possible, exceed current quantum factorisation records using a VIC-20 8-bit home computer from 1981, an abacus, and a dog. We hope that this work will inspire future efforts to match any further quantum factorisation records, should they arise.

In 2000, Pliam showed that there does not exist an upper or lower bound in terms of Shannon entropy alone for the number of guesses required in order to guess some randomly sampled element $s$ with certainty $0<q<1$, denoted as marginal guesswork. In comparison, it was shown by Arikan in 1996 that, if the distribution is defined over finite support, the expected guesswork, that is the expected amount of trials it takes to guess some random element $s$ with certainty, is bound in terms of R\'enyi entropy $\operatorname{H}_{1/2}$. In this paper, we utilize the Theorem of Berry-Ess\'een to amend Pliams result. We show that there exists some asymptotic expression for the marginal guesswork in terms of Shannon entropy, variance in information and the probit function, provided $q$ is fixed.

HiAE is a recently proposed high-throughput authenticated encryption algorithm that achieves exceptional performance on both x86 and ARM architectures. Following its publication, several cryptanalysis papers have claimed that HiAE’s 256-bit encryption security is broken under the nonce-respecting model. In this note, we clarify that the claimed attacks rely critically on submitting forged-tag decryption queries — a type of behavior explicitly excluded by HiAE’s original security model. HiAE was designed under a standard nonce-based AEAD setting without decryption oracle access, offering 256-bit security against key and state recovery, and 128-bit security against forgery. This design approach follows the same principle as well-known schemes such as AEGIS and MORUS. The conclusion that HiAE is broken is based on a misinterpretation of its security model, as the attacks rely on conditions that the design explicitly excludes.

Transparency logs are critical for a wide range of applications, from web certificates to end-to-end encrypted messaging. Today, many transparency log designs exist for various applications and workloads, and developers must fully understand the design space to find the best design for their needs. Worse, if a developer needs a transparency log for an application and workload without an existing transparency log, the developer (who might not be an expert) must design a new log. To address these challenges, we introduce the paradigm of a configurable transparency log, which takes as input a description of the application work- load and constraints of different entities and automatically outputs a transparency log uniquely suited to the application. We present the first configurable transparency log design, LegoLog, which we implement and empirically evaluate end- to-end for three specialized transparency logs. We also show that LegoLog can express six different applications, and we compare the asymptotic complexity of LegoLog and existing transparency logs tailored to individual applications. We find that configurability does not come at the cost of performance: LegoLog can capture a variety of applications while performing comparably to existing, special-purpose transparency logs.

Argument systems are a fundamental ingredient in many cryptographic constructions. The best-performing argument systems to date largely rely on a trusted setup, which is undesirable in trust-minimized applications. While transparent argument systems avoid this trust assumption, they have historically been inefficient, typically exhibiting polylogarithmic proof sizes compared to their trusted counterparts. In 2023, Arun et al. (PKC 2023) constructed the first transparent constant-sized polynomial commitment scheme (PCS), leading to transparent constant-sized arguments. However, the evaluation proof still comprises 66 group elements in a group of unknown order (GUO), rendering it rather impractical. In this work, we address this challenge by presenting a set of novel batching and aggregation techniques tailored for proofs of knowledge of ranges in GUOs. These techniques may also be of independent interest and are readily applicable to enhance and shorten other existing schemes in GUOs. Consequently, by applying these techniques, we immediately achieve an improved PCS with an evaluation proof consisting of only 10 group elements---an impressive 85% reduction. To our knowledge, this represents the shortest PCS in the transparent setting. Thus compiling known information-theoretic proof systems using our improved PCS yields highly compact transparent argument systems when instantiated in a class group, which is more practical than prior constant-sized schemes.

In electronic voting systems, guaranteeing voter anonymity is essential. One primary method to ensure this is the use of a mix-net, in which a set of mix-servers sequentially shuffle a set of encrypted votes, and generate proofs that a correct permutation has been applied. Whilst mix-nets offer advantages over alternative approaches, their traditional use during the tallying phase introduces a significant robustness bottleneck: the process is inherently sequential and critically depends on trusted authorities to perform shuffling and decryption. Any disruption can prevent the final result from being revealed. In this work, we propose offline mixing OMIX, the first voting framework to support a mix-net-based system in which trustees never handle encrypted votes, while also ensuring that each voter's cost is independent of the total number of voters. In particular, the contributions of permutations by mix-servers and decryption shares by trustees are completed and publicly verified before any vote is cast. This eliminates the need for their participation during tallying and enables the first scalable, mix-net-based, and self-tallying voting protocol in the sense of Kiayias and Yung (PKC'02). At the core of OMIX is a distributed key-generation mechanism: each voter locally generates a private voting key and registers a constant-size set of basis public keys. These are permuted and partially decrypted in an offline phase, resulting in a final public decryption key that reveals votes in shuffled order. Our construction leverages the homomorphic and structure-preserving properties of function-hiding inner-product functional encryption, combined with standard primitives, to achieve self-tallying, client scalability, ballot privacy and other voting properties. To support the new mixing structure introduced by OMIX, we also develop a compact and verifiable offline mix-net, based on an enhanced linearly homomorphic signature scheme. This latter primitive may be of independent interest.

Steganography is the practice of concealing messages or information within other non-secret text or media to avoid detection. A central challenge in steganography is balancing payload size with detectability and media constraints—larger payloads increase the risk of detection and require proportionally larger or higher-capacity carriers. In this paper, we introduce a novel approach that combines Huffman coding, suitable dictionary identification, and large language models (LLMs) rephrasing techniques to significantly reduce payload size. This enables more efficient use of limited-capacity carriers, such as images, while minimizing the visual or statistical footprint. Our method allows for the embedding of larger payloads into fixed-size media, addressing a key bottleneck in traditional steganographic systems. By optimizing payload compression prior to encoding, we improve both the stealth and scalability of steganographic communication.

Since attribute-based encryption (ABE) was proposed in 2005, it has established itself as a valuable tool in the enforcement of access control. For practice, it is important that ABE satisfies many desirable properties such as multi-authority and negations support. Nowadays, we can attain these properties simultaneously, but none of these schemes have been implemented. Furthermore, although simpler schemes have been optimized extensively on a structural level, there is still much room for improvement for these more advanced schemes. However, even if we had schemes with such structural improvements, we would not have a way to benchmark and compare them fairly to measure the effect of such improvements. The only framework that aims to achieve this goal, ABE Squared (TCHES '22), was designed with simpler schemes in mind. In this work, we propose the ABE Cubed framework, which provides advanced benchmarking extensions for ABE Squared. To motivate our framework, we first apply structural improvements to the decentralized ciphertext-policy ABE scheme supporting negations presented by Riepel, Venema and Verma (ACM CCS '24), which results in five new schemes with the same properties. We use these schemes to uncover and bridge the gaps in the ABE Squared framework. In particular, we observe that advanced schemes depend on more "variables" that affect the schemes' efficiency in different dimensions. Whereas ABE Squared only considered one dimension (as was sufficient for the schemes considered there), we devise a benchmarking strategy that allows us to analyze the schemes in multiple dimensions. As a result, we obtain a more complete overview on the computational efficiency of the schemes, and ultimately, this allows us to make better-founded choices about which schemes provide the best efficiency trade-offs for practice.

Post-quantum cryptography has become pivotal for ensuring communication security in the quantum era. NTRU-based signature schemes have gained attention due to their computational efficiency and compact public keys and signatures, which reduce communication overheads. However, the algebraic structure of NTRU lattices introduces vulnerabilities in physical attack scenarios, where partial secret key leakage can severely undermine system security. In this paper, we propose the Dimension-and-Sample Reduced NTRU Attack (DSRNA). The core principle of DSRNA is to apply a dimension-reduction strategy that transforms the NTRU instance into a lower-dimensional NTRU instance with fewer samples, which is efficiently solvable via lattice basis reduction. Furthermore, we design a unified hint-embedding technique that jointly exploits side information from both secret keys $f$ and $g$, thereby improving both attack efficiency and success rates. We evaluate the residual security of Falcon and its variants Mitaka and Hawk, under perfect, modular and approximate leakage models. Experimental results demonstrate security degradation. Compared to the method of May et al. at Asiacrypt 2023, DSRNA achieves speedups of $5.8\times$ for Falcon-512 with 400 leaked coefficients and over $29.4\times$ for Falcon-1024 with 905 coefficients. This study reveals the potential vulnerability of NTRU-based signature schemes to partial secret key leakage.

Authenticated Key Exchange (AKE) between any two entities is one of the most important security protocols available for securing our digital networks and infrastructures. In PQCrypto 2023, Bruckner, Ramacher and Striecks proposed a novel hybrid AKE (HAKE) protocol dubbed Muckle+ that is particularly useful in large quantum-safe networks consisting of a large number of nodes. Their protocol is hybrid in the sense that it allows key material from conventional, post-quantum, and quantum cryptography primitives to be incorporated into a single end-to-end authenticated shared key. To achieve the desired authentication properties, Muckle+ utilizes post-quantum digital signatures. However, available instantiations of such signatures schemes are not yet efficient enough compared to their post-quantum key-encapsulation mechanism (KEM) counterparts, particularly in large networks with potentially several connections in a short period of time. To mitigate this gap, we propose Muckle# that pushes the efficiency boundaries of currently known HAKE constructions. Muckle# uses post-quantum key-encapsulating mechanisms for implicit authentication inspired by recent works done in the area of Transport Layer Security (TLS) protocols, particularly, in KEMTLS (CCS'20). We port those ideas to the HAKE framework and develop novel proof techniques on the way. Due to our KEM-based approach, the resulting protocol has a slightly different message flow compared to prior work that we carefully align with the HAKE framework and which makes our changes to Muckle+ non-trivial. Lastly, we evaluate the approach by a prototypical implementation and a direct comparison with Muckle+ to highlight the efficiency gains.

ARADI is a low-latency block cipher introduced by the U.S. National Security Agency (NSA), targeting secure and efficient memory encryption. However, unlike most academic cipher proposals, the design rationale behind ARADI has not been made public, leaving its security to be only assessed through independent analysis. In this work, we present improved key-recovery attacks on up to 12 out of 16 rounds of ARADI in the single-key setting — advancing the best known attacks by two rounds. Our techniques build upon the ZeroSum distinguisher framework and leverage the Fast Hadamard Transform (FHT). A central insight in our attacks is that the linear layer of ARADI exhibits weak diffusion. This structural property allows partial decryption with only a subset of the round keys, significantly reducing the key-guessing space.

Censorship resilience is a fundamental assumption underlying the security of blockchain protocols. Additionally, the analysis of blockchain security from an economic and game theoretic perspective has been growing in popularity in recent years. In this work, we present a surprising rational censorship attack on blockchain censorship resilience when we adopt the analysis of blockchain security from a game theoretic lens and assume all users are rational. In our attack, a colluding group with sufficient voting power censors the remainder nodes such that the group alone can gain all the rewards from maintaining the blockchain. We show that if nodes are rational, coordinating this attack just requires a public read and write blackboard and we formally model the attack using a game theoretic framework. Furthermore, we note that to ensure the success of the attack, nodes need to know the total true voting power held by the colluding group. We prove that the strategy to join the rational censorship attack and also for nodes to honestly declare their power is a subgame perfect equilibrium in the corresponding extensive form game induced by our attack. Finally, we discuss the implications of the attack on blockchain users and protocol designers as well as some potential countermeasures.

Enhanced Privacy Identification (EPID) is one of the anonymous authentication mechanisms that found their way into the industry, being deployed in billions of chips and standardized at ISO. The linchpin of EPID lies in its decentralized revocation procedure that allows to revoke a signer by simply placing one of its signatures on a signature revocation list SRL. Each new signature must then include a proof that it has been generated with a key different from those used to produce the signatures on the SRL. This proof of non-revocation in current post-quantum schemes either relies on general-purpose NIZKs or on regular zero-knowledge proofs (ZKP) but with a witness dimension linear in the size of the SRL, which leads to large size and/or computational complexity. In this paper, we rethink the standard approach of non-revocation so as to avoid its heavy reliance on ZKP. Our construction indeed combines features from different tools (such as Falcon signatures) that are unusual in this context to pull most elements out of the ZKP, leading to significant performance improvements. Providing all these elements unconcealed creates many security challenges for our construction but we yet manage to address all of them and prove security under well-understood lattice assumptions, and in the strong model of Sanders-Traoré (CT-RSA'21) allowing malicious SRLs.

New state-of-the-art assembly implementations show that BRWHash is consistently faster than polyHash and both t-BRWHash and d-2LHash for all message lengths and for both the primes $2^{127}-1$ and $2^{130}-5$.

Modern efficient secure multi-party computation (MPC) protocols typically follow an offline-online design, where offline protocols produce a sufficient amount of correlated randomness that would be consumed during the online phases. The past decades have witnessed maturing of efficient online protocols, for computing circuits over either arbitrary finite fields or rings $\mathbb{Z}_{p^k}$. In particular, protocols tailored for $\mathbb{Z}_{2^k}$ arithmetic have achieved better concrete efficiency in most real-life applications, as it naturally captures modern CPU architectures. On the other hand, a recent paradigm of {\em pseudorandom correlation generator} (PCG) initiated by Boyle et al. (CCS'18, Crypto'19) opens a door to efficient preprocessing with sublinear communication. Since then, PCGs have been extensively studied and developed to produce various types of correlations required from online protocols. Although Li et al. (EuroCrypt'25) recently put a significant step forward and propose efficient PCGs for arbitrary finite fields, the current state of PCGs for rings is not satisfying at all. Towards the great demand for efficiently generating correlations over rings, we investigate PCGs for general Galois rings, which simultaneously unify finite fields and integer rings modulo $p^k$. In summary, we establish the following results: (i) We generalize the state-of-the-art PCG constructions for oblivious linear evaluations (OLE) over Galois fields to {\em arbitrary Galois rings}, basing on Galois theory and the Hensel lift. Moreover, our PCGs for Galois rings are as efficient as PCGs for fields. Concretely, for $mN$ OLE correlations over $\mathbb{Z}_{2^k}$, we require $O(m\log{N})$ communication and $O(m^2N\log{N})$ computation, where $m$ is an arbitrary integer $\geq 2$. In comparison, to our best knowledge, previous approaches incur communication at least linear in $N$. (ii) We extend the above OLE construction to provide various types of correlations over any Galois ring. One of the fascinating applications is an efficient PCG for two-party SPD$\mathbb{Z}_{2^k}$ authenticated multiplication triples (Crypto'18). For $mN$ SPD$\mathbb{Z}_{2^k}$ triples, our approach requires only $O(m\log{N})$ communication and $O(m^2N\log{N})$ computation. Concrete evaluations show that our method significantly outperforms existing schemes based on homomorphic encryption. (iii) In addition, our PCGs for Galois rings also enable multi-party multiplication triple generation, yielding the first efficient MPC protocol for arithmetic circuits over $\mathbb{Z}_{2^k}$ with \emph{silent} and \emph{sublinear} preprocessing. Additional applications include circuit-dependent preprocessing and matrix multiplication triples, etc, which are of independent interest.

Post-Quantum Cryptography (PQC) algorithms should remain secure even in the presence of quantum computers. Although the security of such schemes is guaranteed at the algorithmic level, real-world implementations often suffer from other vulnerabilities like Side-Channel Attacks (SCA). This Systematization of Knowledge (SoK) paper investigates side-channel attacks targeting implementations of PQC algorithms. This work categorizes attacks from an adversarial perspective to identify the most vulnerable components of the algorithms' implementations and highlights unexplored parts in current implementations. In addition, it reviews and analyzes the efficiency and efficacy of existing countermeasures to SCA in current hardware implementations. This approach helps identify countermeasures that provide broader protection and highlights characteristics needed for future secure implementations. Our findings offer guidance in strengthening existing systems and developing more efficient defenses against side-channel attacks.

We propose the first updatable white-box secure cipher, EWEMrl (Extended WEM with longevity against non-adaptive read-only adversaries), and its natural extension, EWEMxl (Extended WEM with longevity against executable adversaries), both based on WEM (White-box Even-Mansour), and both achieving longevity against non-adaptive read-only malware. The notion of longevity, introduced by Koike et al., addresses continuous code leakage and is stronger than incompressibility. While Yoroi claimed longevity, but was broken by Isobe and Todo. Given the prevalence of continuous leakage, developing such ciphers is crucial in white-box cryptography. Precisely, we have the following. • We first present EWEMr (Extended WEM against non-adaptive read-only adver- saries), a generalization of WEM (White-box Even-Mansour). WEM is the first (and possibly only) white-box cipher based on Even-Mansour (EM), replacing its key addition layer with a secret Sbox. EWEMr achieves a high space-hardness bound in the non-adaptive model, with a new generic proof strategy, but does not provide longevity. Instead, it serves as the base for EWEMrl. • We also present EWEMx (Extended WEM against executable adversaries), which uses EWEMr as subroutines and achieves a high space-hardness bound in the stronger adaptive model. While EWEMx does not achieve longevity, it is the base design for EWEMxl. • We next propose EWEMrl, that achieves longevity against non-adaptive read-only malware. None of the existing ciphers, such as SPNbox and SPACE, are designed for longevity. We show that EWEMrl ensures (against non-adaptive read-only adversaries) (1) longevity, (2) high space-hardness in both known-space and chosen-space settings, and (3) security against hybrid code-lifting attacks. • Finally, we introduce EWEMxl, a natural extension of EWEMrl with a structure similar to EWEMx. EWEMxl achieves (2) and (3) in the stronger adaptive model while maintaining (1) in the same non-adaptive and read-only setting. In summary, our proposals EWEMrl and EWEMxl provide longevity against non- adaptive read-only malware while ensuring security confidence in the black-box setting.

Succinct non-interactive arguments of knowledge (SNARKs) based on lattice assumptions offer a promising post-quantum alternative to pairing-based systems, but have until now suffered from inherently quadratic proof sizes in the security parameter. We introduce RoK and Roll, the first lattice-based SNARK that breaks the quadratic barrier, achieving communication complexity of $\tilde{O}(\lambda)$ together with a succinct verification time. The protocol significantly improves upon the state of the art of fully-succinct argument systems established by ``RoK, Paper, SISsors'' (RPS) [ASIACRYPT'24] and hinges on two key innovations, presented as reductions of knowledge (RoKs): - Structured random projections: We introduce a new technique for structured random projections that allows us to reduce the witness dimensions while approximately preserving its $\ell_2$ norm and maintaining the desired tensor structure. In order to maintain succinct communication and verification, the projected image is further committed and adjoined to the original relation. This procedure is recursively repeated until dimension of the intermediate witness becomes $\mathsf{poly}(\lambda)$, i.e. independent of the original witness length. - Unstructured random projection: When the witness is sufficiently small, we let the unstructured projection (over coefficients $\mathbb{Z}_q$) be sent in plain, as in LaBRADOR [CRYPTO'23]. We observe, however, that the strategy from prior works to immediately lift the projection claim to $\mathcal{R}_q$, and into our relation, would impose a quadratic communication cost. Instead, we gradually batch-and-lift the projection a the tower of intermediate ring extensions. This reduces the communication cost to $\tilde{O}(\lambda)$ while maintaining a succinct verification time. These two techniques, combined with existing RoKs from RPS, yield a succinct argument system with communication complexity $\tilde{O}(\lambda)$ and succinct verification for structured linear relations.

Single decryptor encryption (SDE) is public key encryption (PKE) where the decryption key is an unclonable quantum state. Coladangelo, Liu, Liu, and Zhandry (CRYPTO 2021) realized the first SDE assuming subexponentially secure indistinguishability obfuscation (iO) and one-way functions (OWFs), along with the polynomial hardness of the learning with errors (LWE) assumption. Since then, SDE has played a pivotal role in recent advances in quantum cryptography. However, despite its central importance in unclonable cryptography, many fundamental questions about SDE remain unanswered. For example, a line of works has proposed various security notions for SDE, but their relationships have hardly been discussed. Moreover, while many subsequent works have adopted the construction methodology of Coladangelo et al., none have explored its improvement, leaving the possibility of a more efficient approach to SDE. In this work, we address these fundamental questions concerning SDE. Our contributions are threefold. New security notion: We introduce a strengthened indistinguishability-based security notion for SDE, which we call CPA+ anti-piracy security. We show that CPA+ security unifies the existing security notions for SDE, as detailed in the third item. New construction: We present an SDE scheme that satisfies CPA+ anti-piracy security, based solely on polynomially secure iO and OWFs. In addition to relying on weaker and more general assumptions, our SDE scheme offers a significant advantage over the scheme of Coladangelo et al., as both the construction and its security proof are much simpler. Relationships among security notions: We demonstrate that CPA+ anti-piracy security implies all existing security notions for SDE, with the sole exception of identical challenge ciphertext security proposed by Georgiou and Zhandry (EPRINT 2020). Although we do not establish a direct implication from CPA+ anti-piracy security to identical challenge ciphertext security, we provide a generic transformation from an SDE scheme satisfying the former to one achieving the latter in the quantum random oracle model. Additionally, we establish various relationships among different security notions for SDE. By combining these results with our SDE construction, we derive several new feasibility results. We further show that our CPA+ anti-piracy security enjoys additional robustness properties. In particular, it is preserved under parallel composition, yielding a way to expand the message space of SDE while maintaining security. We also show that it is robust to arbitrary correlations between the challenge bits for the second-stage adversaries. To capture this setting, we introduce correlated-challenge-bits CPA anti-piracy security, parameterized by an arbitrary joint distribution on the challenge bits, and show that CPA+ anti-piracy security implies this notion.

Homomorphic encryption (HE) schemes have gained significant popularity in modern privacy-preserving applications across various domains. While research on HE constructions based on learning with errors (LWE) and ring-LWE has received major attention from both cryptographers and software-hardware designers alike, their module-LWE-based counterpart has remained comparatively under-explored in the literature. A recent work provides a module-LWE-based instantiation (MLWE-HE) of the Cheon-Kim-Kim-Song (CKKS) scheme and showcases several of its advantages such as parameter flexibility and improved parallelism. However, a primary limitation of this construction is the quadratic growth in the size of the relinearization keys. Our contribution is two-pronged: first, we present a new relinearization key-generation technique that addresses the issue of quadratic key size expansion by reducing it to linear growth. Second, we extend the application of MLWE-HE in a multi-group homomorphic encryption (MGHE) framework, thereby generalizing the favorable properties of the single-keyed HE to a multi-keyed setting as well as investigating additional flexibility attributes of the MGHE framework.

Authenticated encryption (AE) is a fundamental tool in today's secure communication. Numerous designs have been proposed, including well-known standards such as GCM. While their performance for long inputs is excellent, that for short inputs is often problematic due to high overhead in computation, showing a gap between the real need for IoT-like protocols where packets are often very short. Existing dedicated short-input AEs are very scarce, the classical Encode-then-encipher (Bellare and Rogaway, Asiacrypt 2000) and Manx (Adomnic\u{a}i et al., CT-RSA 2023), using up to two block cipher calls. They have superior performance for (very) short inputs, however, security is up to $n/2$ bits, where $n$ is the block size of the underlying block cipher. This paper proposes a new family of short-input AEs, dubbed Cymric, which ensures beyond-birthday-bound (BBB) security. It supports a wider range of input space than EtE and Manx with the help of one additional block cipher call (thus three calls). In terms of the number of block cipher calls, Cymric is the known minimum construction of BBB-secure AEs, and we also prove this is indeed minimal by presenting an impossibility result on BBB-secure AE with two calls. Finally, we show a comprehensive benchmark on microcontrollers to show performance advantage over existing schemes.

Prior research on ensuring trust in delegated computation through lattice-based zero-knowledge proofs mostly rely on Learning-With-Errors (LWE) assumption. In this work, we propose a zero-knowledge proof of knowledge using the Ring Learning with Rounding (RLWR) assumption for an interesting and useful class of statements: linear relations on polynomials. We begin by proposing, to the best of our knowledge, the first efficient commitment scheme in literature based on the hardness of RLWR assumption. We establish two properties on RLWR that aid in the construction of our commitments: (i) closure under addition with double rounding, and (ii) closure under multiplication with a short polynomial. Building upon our RLWR commitment scheme, we consequently design a RLWR based $\Sigma_2$ protocol for proving knowledge of a single committed message under linear relations with public polynomials. As an use-case of our proposed $\Sigma_2$ protocol, we showcase a construction of a quantum-safe Searchable Symmetric Encryption (SSE) scheme by plugging a prior LWR based SSE scheme from (EuroS&P 2023) with our $\Sigma_2$ protocol. Concretely, using our $\Sigma_2$ protocol for linear relations, we prove the correctness of an encrypted search result in a zero-knowledge manner. We implement our verifiable SSE framework and show that the overhead of an extra verification round is negligible ($0.0023$ seconds) and retains the asymptotic query execution time complexity of the original SSE scheme. Our work establishes results on zero-knowledge proof systems that can be of independent interest. By shifting the setting from RLWE to RLWR, we gain significant (i) efficiency improvements in terms of communication complexity by $O(M)$ (since some prior works on RLWE require rejection sampling by a factor of $M$), as well as (ii) very short proof size ($8.4$ KB) and tighter parameters (since RLWR does not explicitly manipulate error polynomials like RLWE).

Searchable symmetric encryption (SSE) enables query execution directly over sym- metrically encrypted databases. To support realistic query executions over encrypted document collections, one needs SSE schemes capable of supporting both conjunctive and disjunctive keyword queries. Unfortunately, existing solutions are either practi- cally inefficient (incur large storage overheads and/or high query processing latency) or are quantum-unsafe. In this paper, we present the first practically efficient SSE scheme with fast con- junctive and disjunctive keyword searches, compact storage, and security based on the (plausible) quantum-hardness of well-studied lattice-based assumptions. We present NTRU-OQXT – a highly compact NTRU lattice-based conjunctive SSE scheme that outperforms all existing conjunctive SSE schemes in terms of search latency. We then present an extension of NTRU-OQXT that additionally supports disjunctive queries, we call it NTRU-TWINSSE. Technically, both schemes rely on a novel oblivious search protocol based on highly optimized Fast-Fourier trapdoor sampling algorithms over NTRU lattices. While such techniques have been used to design other cryptographic primitives (such as digital signatures), they have not been applied before in the context of SSE. We present prototype implementations of both schemes, and experimentally val- idate their practical performance over a large real-world dataset. Our experiments demonstrate that NTRU-OQXT achieves 2× faster conjunctive keyword searches as compared to all other conjunctive SSE schemes (including the best quantum-unsafe conjunctive SSE schemes), and substantially outperforms many of these schemes in terms of storage requirements. These efficiency benefits also translate to NTRU- TWINSSE, which is practically competitive with the best quantum-unsafe SSE schemes capable of supporting both conjunctive and disjunctive queries.

Zero-knowledge succinct non-interactive arguments (zkSNARKs) are notorious for their large prover space requirements, which almost prohibits their use for really large instances. Space-efficient zkSNARKs aim to address this by limiting the prover space usage, without critical sacrifices to its runtime. In this work, we introduce Hobbit, the only existing space-efficient zkSNARK that achieves optimal prover time $O(|C|)$ for an arithmetic circuit $C$. At the same time, Hobbit is the first transparent and plausibly post-quantum secure construction of its kind. Moreover, our experimental evaluation shows that Hobbit outperforms all prior general-purpose space-efficient zkSNARKs in the literature across four different applications (arbitrary arithmetic circuits, inference of pruned Multi-Layer Perceptron, batch AES128 evaluation, and select-and-aggregate SQL query) by $\times$8-$\times$$56$ in terms or prover time while requiring up to $\times$23 less total space. At a technical level, we introduce two new building blocks that may be of independent interest: (i) the first sumcheck protocol for products of polynomials with optimal prover time in the streaming setting, and (ii) a novel multi-linear plausibly post-quantum polynomial commitment that outperforms all prior works in prover time (and can be tuned to work in a space-efficient manner). We build Hobbit by combining the above with a modified version of HyperPlonk, providing an explicit routine to stream access to the circuit evaluation.

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

Speedrunning is a competition that emerged from communities of early video games such as Doom (1993). Speedrunners try to finish a game in minimal time. Provably verifying the authenticity of submitted speedruns is an open problem. Traditionally, best-effort speedrun verification is conducted by on-site human observers, forensic audio analysis, or a rigorous mathematical analysis of the game mechanics1. Such methods are tedious, fallible, and, perhaps worst of all, not cryptographic. Motivated by naivety and the Dunning-Kruger effect, we attempt to build a system that cryptographically proves the authenticity of speedruns. This paper describes our attempted solutions and ways to circumvent them. Through a narration of our failures, we attempt to demonstrate the difficulty of authenticating live and interactive human input in untrusted environments, as well as the limits of signature schemes, game integrity, and provable play.

The use of biometric-based security protocols is on the steep rise. As biometrics become more popular, we witness more attacks. For example, recent BrutePrint/InfinityGauntlet attacks showed how to brute-force fingerprints stored on an Android phone in about 40 minutes. The attacks are possible because biometrics, like passwords, do not have high entropy. But unlike passwords, brute-force attacks are much more damaging for biometrics, because one cannot easily change biometrics in case of compromise. In this work, we propose a novel provably secure Brute-Force Resistant Biometrics (BFRB) protocol for biometric-based authentication and key reconstruction that protects against brute-force attacks even when the server storing biometric-related data is compromised. Our protocol utilizes a verifiable partially oblivious pseudorandom function, an authenticated encryption scheme, a pseudorandom function, and a hash. We formally define security for a BFRB protocol and reduce the security of our protocol to the security of the building blocks. We implement the protocol and study its performance for the ND-0405 iris dataset.

In the present work we address the robustness of the Polynomial Learning With Errors problem extending previous results in Blanco-Chacón et al. and in Elias et al. In particular, we produce two kinds of new distinguishing attacks: a) we generalize Blanco-Chacón et al. to the case where the defining polynomial has a root of degree up to 4, and b) we widen and refine the most general attack in Elias et al. to the non-split case and determine further dangerous instances previously not detected. Finally, we exploit our results in order to show vulnerabilities of some cryptographically relevant polynomials.

Collaborative graph processing refers to the joint analysis of inter-connected graphs held by multiple graph owners. To honor data privacy and support various graph processing algorithms, existing approaches employ secure multi-party computation (MPC) protocols to express the vertex-centric abstraction. Yet, due to certain computation-intensive cryptography constructions, state-of-the-art (SOTA) approaches are asymptotically suboptimal, imposing significant overheads in terms of computation and communication. In this paper, we present RingSG, the first system to attain optimal communication/computation complexity within the MPC-based vertex-centric abstraction for collaborative graph processing. This optimal complexity is attributed to Ring-ScatterGather, a novel computation paradigm that can avoid exceedingly expensive cryptography operations (e.g., oblivious sort), and simultaneously ensure the overall workload can be optimally decomposed into parallelizable and mutually exclusive MPC tasks. Within Ring-ScatterGather, RingSG improves the concrete runtime efficiency by incorporating 3-party secure computation via share conversion, and optimizing the most cost-heavy part using a novel oblivious group aggregation protocol. Finally, unlike prior approaches, we instantiate RingSG into two end-to-end applications to effectively obtain application-specific results from the protocol outputs in a privacy-preserving manner. We developed a prototype of RingSG and extensively evaluated it across various graph collaboration settings, including different graph sizes, numbers of parties, and average vertex degrees. The results show RingSG reduces the system running time of SOTA approaches by up to 15.34× and per-party communication by up to 10.36×. Notably, RingSG excels in processing sparse global graphs collectively held by more parties, consistent with our theoretical cost analysis.