Papers updated in last 365 days (3051 results)
Modular Reduction in CKKS
The Cheon-Kim-Kim-Song (CKKS) scheme is renowned for its efficiency in encrypted computing over real numbers. However, it lacks an important functionality that most exact schemes have, an efficient modular reduction. This derives from the fundamental difference in encoding structure. The CKKS scheme encodes messages to the least significant bits, while the other schemes encode to the most significant bits (or in an equivalent manner). As a result, CKKS could enjoy an efficient rescaling but lost the ability to modular reduce inherently.
Instead of homomorphically approximating the modular reduction function, we suggest to use the inherent modular reduction over $\mathbb{Z}_q[X]/(X^N+1)$. We construct a novel homomorphic modular reduction algorithm using the discrete bootstrapping from Bae et al. [Asiacrypt'24] and a new discretization algorithm from modulus switching. One of the key advantages of our modular reduction is that its computational complexity grows sublinearly ($O(\log k)$) as we increase the input range $[0,k)$, which is asymptotically better than the state-of-the-art with $\geq O(k)$.
We checked our algorithms with concrete experiments. Notably, our modulo 1 function for input range $[0, 2^{20})$ takes only 44.9 seconds with 13.3 bits of (mean) precision, in a single-threaded CPU. Recall that modular reduction over such a large range was almost infeasible in the previous works, as they need to evaluate a polynomial of degree $> 2^{20}$ (or equivalent). As an application of our method, we compared a bit decomposition based on our framework with the state-of-the-art method from Drucker et al. [J.Cryptol'24]. Our method is $7.1 \times$ faster while reducing the failure probability by more than two orders of magnitude.
Efficient Homomorphic Integer Computer from CKKS
As Fully Homomorphic Encryption (FHE) enables computation over encrypted data, it is a natural question of how efficiently it handles standard integer computations like $64$-bit arithmetic. It has long been believed that the CGGI/DM family or the BGV/BFV family are the best options, depending on the size of the parallelism. The discrete variant of CKKS, suggested by Drucker et al. [J.Cryptol.'24], provides an interesting alternative for integer computations. Notably, the modular reduction framework proposed by Kim and Noh [CiC'25] built on top of the CKKS-style functional bootstrapping by Bae et al. [Asiacrypt'24] gives an efficient arithmetic modulo small integers.
In this work, we propose a novel homomorphic computer for unsigned integer computations. We represent a large integer (e.g. $64$-bit) as a vector of smaller chunks (e.g. $4$-bit) and construct arithmetic operations relying on discrete CKKS. The proposed scheme supports many of the operations supported in TFHE-rs while outperforming it in terms of amortized running time. Notably, our homomorphic $64$-bit multiplication takes $8.85$ms per slot, which is more than three orders of magnitude faster than TFHE-rs.
Structured-Seed Local Pseudorandom Generators and their Applications
We introduce structured‑seed local pseudorandom generators (SSL-PRGs), pseudorandom generators whose seed is drawn from an efficiently sampleable, structured distribution rather than uniformly. This seemingly modest relaxation turns out to capture many known applications of local PRGs, yet it can be realized from a broader family of hardness assumptions. Our main technical contribution is a generic template for constructing SSL-PRGs that combines the following two ingredients:
(i) noisy‑$\mathsf{NC}^0$ PRGs, computable by constant‑depth circuits fed with sparse noise, with
(ii) new local compression schemes for sparse vectors derived from combinatorial batch codes.
Instantiating the template under the sparse Learning‑Parity‑with‑Noise (LPN) assumption yields the first SSL-PRGs with polynomial stretch and constant locality from a subquadratic‑sample search hardness assumption; a mild strengthening of sparse‑LPN gives strong SSL-PRGs of arbitrary polynomial stretch. We further show that for all standard noise distributions, noisy‑local PRGs cannot be emulated by ordinary local PRGs, thereby separating the two notions.
Plugging SSL-PRGs into existing frameworks, we revisit the canonical applications of local PRGs and demonstrate that SSL-PRGs suffice for:
(i) indistinguishability obfuscation,
(ii) constant-overhead secure computation,
(iii) compact homomorphic secret sharing, and
(iv) deriving hardness results for PAC‑learning DNFs from sparse‑LPN.
Our work thus broadens the landscape of low‑depth pseudorandomness and anchors several primitives to a common, well‑motivated assumption.
On One-Shot Signatures, Quantum vs Classical Binding, and Obfuscating Permutations
One-shot signatures (OSS) were defined by Amos, Georgiou, Kiayias, and Zhandry (STOC'20). These allow for signing exactly one message, after which the signing key self-destructs, preventing a second message from ever being signed. While such an object is impossible classically, Amos et al observe that OSS may be possible using quantum signing keys by leveraging the no-cloning principle. OSS has since become an important conceptual tool with many applications in decentralized settings and for quantum cryptography with classical communication. OSS are also closely related to separations between classical-binding and collapse-binding for post-quantum hashing and commitments. Unfortunately, the only known OSS construction due to Amos et al. was only justified in a classical oracle model, and moreover their justification was ultimately found to contain a fatal bug. Thus, the existence of OSS, even in a classical idealized model, has remained open.
We give the first standard-model OSS, with provable security assuming (sub-exponential) indistinguishability obfuscation (iO) and LWE. This also gives the first standard-model separation between classical and collapse-binding post-quantum commitments/hashing, solving a decade-old open problem. Along the way, we also give the first construction with unconditional security relative to a classical oracle. To achieve our standard-model construction, we develop a notion of permutable pseudorandom permutations (permutable PRPs), and show how they are useful for translating oracle proofs involving random permutations into obfuscation-based proofs. In particular, obfuscating permutable PRPs gives a trapdoor one-way permutation that is $\textit{full-domain}$, solving another decade-old-problem of constructing this object from (sub-exponential) iO and one-way functions.
Blockcipher-Based Key Commitment for Nonce-Derived Schemes
AES-GCM has seen great adoption for the last 20 years to protect data in various use-cases because of its optimal performance. It has also posed some challenges to modern applications due to its nonce, block size, and lack of key commitment. Nonce-derived schemes address these challenges by deriving a different key from random values and using GCM with the derived key. In this work, we explore efficient key commitment methods for nonce-derived schemes. For concreteness, we focus on expanding XAES-256-GCM, a derived key scheme originally introduced by Filippo Valsorda. We propose an efficient CMAC-based key commitment solution, and prove its security in the ideal-cipher model. This proposal yields a FIPS-compliant mode and offers much better data bounds than GCM. Finally, we benchmark the new mode's performance to demonstrate that the additional cost affects mostly small plaintexts.
A Fast Heuristic for Mapping Boolean Circuits to Functional Bootstrapping
Functional bootstrapping in FHE schemes such as FHEW and TFHE allows the evaluation of arbitrary functions on encrypted data, while simultaneously reducing noise. Implementing programs that directly use functional bootstrapping is challenging and error-prone. In this paper, we propose a heuristic that automatically maps Boolean circuits to functional bootstrapping instructions. Unlike prior approaches, our method does not limit the encrypted data plaintext space to a power-of-two size, allowing the instantiation of functional bootstrapping with smaller parameters. Furthermore, the negacyclic property of functional bootstrapping is exploited to extend the plaintext effective space. Despite the inherently greedy nature of the heuristic, experimental results show that the mapped circuits exhibit a significant reduction in evaluation time. Our heuristic demonstrates a $45\%$ reduction in evaluation time when compared to hand-optimized Trivium and Kreyvium implementations.
Group Signatures with Designated Traceability over Openers' Attributes
We propose a group signature scheme with a function of designated traceability; each opener has attributes, and a signer of a group signature can be traced by only the openers whose attributes satisfy the boolean formula designated by the signer. We describe syntax and security definitions of the scheme. Then we give a generic construction of the scheme by employing a ciphertext-policy attribute-based encryption scheme.
TRIFORS: LINKable Trilinear Forms Ring Signature
We present TRIFORS (TRIlinear FOrms Ring Signature), a logarithmic post-quantum (linkable) ring signature based on a novel assumption regarding the equivalence of alternating trilinear forms. The basis of this work is the construction by Beullens, Katsumata and Pintore from Asiacrypt 2020 to obtain a linkable ring signature from a cryptographic group action. The group action on trilinear forms used here is the same employed in the signature presented by Tang et al. at Eurocrypt 2022. We first define a sigma protocol that, given a set of public keys, the ring, allows us to prove the knowledge of a secret key corresponding to a public one in the ring. Furthermore, some optimisations are used to reduce the size of the signature: among others, we use a novel application of the combinatorial number system to the space of the challenges. Using the Fiat-Shamir transform, and taking into account the attack of Beullens from Crypto 2023, we obtain a (linkable) ring signature of competitive length with the state-of-the-art among post-quantum proposals for security level 128.
Cymric: Short-tailed but Mighty
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.
Solving the Shortest Vector Problem in $2^{0.63269n+o(n)}$ time on Random Lattices
The Shortest Vector problem (SVP) is the most important problem in lattice-based cryptanalysis. There is currently a gap in the understanding of this problem with respect to its worst-case complexity and its average-case behaviour. For instance, SVP on an n-dimensional lattice has worst-case complexity $2^{n+o(n)}$ [ADRS15]. However, in practice, people rely on heuristic (unproven) sieving algorithms of time complexity $2^{0.292n+o(n)}$ [BDGL16] to assess the security of lattice-based cryptography schemes. Those heuristic algorithms are experimentally verified for lattices used in cryptography, which are usually random in some way.
In this paper, we try to bridge the gap between worst-case and heuristic algorithms. Using the formalism of random real lattices developed by Siegel, we show a tighter upper bound on an important lattice parameter called the smoothing parameter that applies to almost all random lattices. Using a known discrete Gaussian sampler at the smoothing parameter, we can then directly sample short vectors. This allows us to provably solve an approximation version of the SVP on almost all random lattices with a small constant approximation factor $1.123$, in time $2^{n/2+o(n)}$. With further analysis, we can provably solve the exact SVP in time $2^{0.63269n+o(n)}$ on almost all random lattices as well. We also provide a smooth time approximation factor tradeoff between these two cases. All our algorithms work in space $2^{n/2+o(n)}$. Our paper is a first step towards better understanding the heuristic behaviour of lattice sieving on random lattices.
AD-MPC: Asynchronous Dynamic MPC with Guaranteed Output Delivery
MPC-as-a-Service (MPCaaS) systems enable clients to outsource privacy-preserving computations to distributed servers, offering flexibility by adapting and configuring MPC protocols to meet diverse security requirements. However, traditional MPC protocols rely on a fixed set of servers for the entire computation process, limiting scalability. Dynamic MPC (DMPC) addresses this limitation by permitting participants to join or leave during the computation. Nevertheless, existing DMPC protocols assume synchronous networks, which can lead to failures under unbounded network delays. In this paper, we present AD-MPC, the first asynchronous dynamic MPC protocol. Our protocol ensures guaranteed output delivery under optimal resilience ($n=3t+1$). To achieve this, we introduce two critical components: an asynchronous dynamic preprocessing protocol that facilitates the on-demand generation of Beaver triples for secure multiplication, and an asynchronous transfer protocol that maintains consistency during party hand-offs. These components collectively ensure computation correctness and transfer consistency across participants. We implement AD-MPC and evaluate its performance across up to 20 geographically distributed nodes. Experimental results demonstrate that the protocol not only offers strong security guarantees in dynamic and asynchronous network environments but also achieves performance comparable to state-of-the-art DMPC protocols.
PassPro: A Secure Password-based Authentication Mechanism using SHF
The password-based authentication system is a widely used authentication mechanism. However, it has several issues, including guessing attacks, dictionary attacks, rainbow table attacks, collision attacks, domino effects, phishing attacks, and database leakage issues. To avoid these attacks, FIDO authentication avoids passwords and uses a public key to implement a challenge-response-based and digital signature-based authentication mechanism. It implements a passwordless authentication mechanism to avoid various attacks that are present in password-based authentication mechanisms. The FIDO authentication mechanism stores the private key in the client's devices. Therefore, FIDO authentication is susceptible to device-specific issues, so cross-platform management becomes a concern. This issue is overcome by passkeys synchronizing with the cloud; however, hardware dependency is still an issue for such a system. The security of such a system is entirely dependent on the security of the hardware.
To address these issues, we present a client-side password hashing method called PassPro. PassPro uses a shuffle and hash function (SHF) to implement PassPro. The SHF is used to create a unique hash value for two publicly known words using a secret context. The SHF is used to create a unique hash value on the client side, preventing the transmission of the raw password to the server. Moreover, PassPro can protect the password database using two different methods: PassPro with encryption (PassProE) and PassPro with SHF (PassProS). PassProE encrypts the password database using mutually reproducible secret keys instead of using hashing, such as Argon2i. PassProS hashes the password database with SHF. In this paper, we exemplify how PassPro can prevent various attacks, including guessing attacks, dictionary attacks, rainbow table attacks, collision attacks, domino effects, phishing attacks, and database leakage issues. Moreover, PassPro users can reuse their password in different or the same domains. Also, PassPro guarantees that adversaries cannot retrieve the user's original password from the leaked password database.
Replication of Quantum Factorisation Records with an 8-bit Home Computer, an Abacus, and a Dog
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.
Reality Check on Side-Channels: Lessons learnt from breaking AES on an ARM Cortex A processor
Side-channel analysis (SCA) has posed a significant threat to systems for nearly three decades. Numerous practical demonstrations have targeted everyday devices, such as smart cards, cryptocurrency wallets, and smartphones. However, much of the research in the public domain has focused on low-end microcontrollers, limiting our understanding of the challenges involved in attacking more complex systems. In this work, we conduct a reality check on SCA by targeting a high-performance ARM Cortex-A72 out-of-order processor, commonly found in smartphones. We evaluate the practical effort required for key recovery attacks, considering various threat models, from basic to advanced. Our results show that while basic approaches fail, advanced approaches like deep learning-based SCA can successfully recover the secret key. This multi-tier evaluation approach is crucial for comprehensive risk assessment and informed decision-making regarding mitigation strategies, balancing security, performance, and area constraints.
Rejected Signatures' Challenges Pose New Challenges: Key Recovery of CRYSTALS-Dilithium via Side-Channel Attacks
Rejection sampling is a crucial security mechanism in lattice-based signature schemes that follow the Fiat-Shamir with aborts paradigm, such as ML-DSA/CRYSTALS-Dilithium. This technique transforms secret-dependent signature samples into ones that are statistically close to a secret-independent distribution (in the random oracle model). While many side-channel attacks have directly targeted sensitive data such as nonces, secret keys, and decomposed commitments, fewer studies have explored the potential leakage associated with rejection sampling. Notably, at HOST 2021, Karabulut \etal showed that leakage from rejected signatures' challenges can undermine, but not entirely break, the security of the Dilithium scheme.
Motivated by the above, we convert the problem of key recovery (from the leakage of rejection sampling) to an integer linear programming problem (ILP), where rejected responses of unique Hamming weights set upper/lower constraints of the product between the challenge and the private key. We formally study the worst-case complexity of the problem as well as empirically confirm the practicality of the rejected signature's challenge attack. For all three security levels of Dilithium-2/3/5, our attack recovers the private key in seconds or minutes with a 100\% Success Rate (SR).
Our attack leverages knowledge of the rejected signature's challenge and response, and thus we propose methods to extract this information by exploiting single-trace side-channel leakage from Number Theoretic Transform (NTT) operations and functions associated with the response generation procedure. We demonstrate the practicality of this rejected signature's challenge attack by using real power consumption on an ARM Cortex-M4 microcontroller. To the best of our knowledge, it is the first practical and efficient side-channel key recovery attack on ML-DSA/Dilithium that targets the rejection sampling procedure. Furthermore, we discuss some countermeasures to mitigate this security issue.
Classical Commitments to Quantum States
We define the notion of a classical commitment scheme to quantum states, which allows a quantum prover to compute a classical commitment to a quantum state, and later open each qubit of the state in either the standard or the Hadamard basis. Our notion is a strengthening of the measurement protocol from Mahadev (STOC 2018). We construct such a commitment scheme from the post-quantum Learning With Errors (LWE) assumption, and more generally from any noisy trapdoor claw-free function family that has the distributional strong adaptive hardcore bit property (a property that we define in this work).
Our scheme is succinct in the sense that the running time of the verifier in the commitment phase depends only on the security parameter (independent of the size of the committed state), and its running time in the opening phase grows only with the number of qubits that are being opened (and the security parameter). As a corollary we obtain a classical succinct argument system for QMA under the post-quantum LWE assumption. Previously, this was only known assuming post-quantum secure indistinguishability obfuscation. As an additional corollary we obtain a generic way of converting any X/Z quantum PCP into a succinct argument system under the quantum hardness of LWE.
Probing Secure Composability Without Fresh Randomness: Theory and Application to Ascon
Side-channel attacks (SCAs) pose a significant threat to the implementations of lightweight ciphers, particularly in resource-constrained environments where masking—the primary countermeasure—is constrained by tight resource limitations. This makes it crucial to reduce the resource and randomness requirements of masking schemes. In this work, we investigate an approach to minimize the randomness
complexity of masking algorithms. Specifically, we explore the theoretical foundations of higher-order masking schemes that eliminate the need for online (fresh) randomness by relying solely on offline randomness present in the initial input shares.
We demonstrate that round-based ciphers with linear diffusion layers can support such deterministic composition, where the diffusion layer acts as a refresh subcircuit. This ensures that, up to a threshold number, probes placed across rounds remain independent. Based on this observation, we propose composition theorems for probing-secure masking. On the practical side, we instantiate our framework using known deterministic first- and second-order masked S-boxes and provide software
implementations of Ascon’s protected permutation.
Last updated: 2025-07-14
On the Complexity and Admissible Parameters of the Crossbred Algorithm in $\mathbb{F}_{q\geq2}$
[IMPORTANT NOTE]
This work was mostly done whilst I as a Master's student at Royal Holloway.
Unfortunately, I do not believe it is of sufficient quality or rigor, and maybe even worse, is very sloppy and at times, confusing.
Hence, I am leaving this note to point readers in the direction of other publications that also concern themselves with the complexity of the Crossbred algorithm.
These works have done a much better job, and I do not believe that I have the profile at the moment to continue working on this particular topic.
[1]
J. Baena, D. Cabarcas, S. K. Tiwari, J. Verbel, and L. Villota, ‘Admissible parameters for the Crossbred algorithm and semi-regular sequences over finite fields’, Designs, Codes and Cryptography, Mar. 2025.
[2]
D. Vidal, C. Delaplace, and S. Ionica, ‘An analysis of the Crossbred Algorithm for the MQ Problem’, IACR Communications in Cryptology, vol. 1, no. 3, 2024.
Let us walk on the 3-isogeny graph: efficient, fast, and simple
Constructing and implementing isogeny-based cryptographic primitives is an active research. In particular, performing length-$n$ isogenies walks over quadratic field extensions of $\mathbb{F}_p$ plays an exciting role in some constructions, including
Hash functions, Verifiable Delay Functions, Key-Encapsulation Mechanisms, and generic proof systems for isogeny knowledge.
Remarkably, many isogeny-based constructions, for efficiency, perform $2$-isogenies through square root calculations.
This work analyzes the idea of using $3$-isogenies instead of $2$-isogenies, which replaces the requirement of calculating square roots with cube roots. Performing length-$m$ $3$-isogenies allows shorter isogeny walks than when employing length-$n$ $2$-isogenies since a cube root calculation costs essentially the same as computing a square root, and we require $3^m \approx 2^n$ to provide the same security level.
We propose an efficient mapping from arbitrary supersingular Montgomery curves defined over $\mathbb{F}_{p^2}$ to the $3$-isogeny curve model from Castryck, Decru, and Vercauteren (Asiacrypt 2020); a deterministic algorithm to compute all order-$3$ points on arbitrary supersingular Montgomery curves, and an efficient algorithm to compute length-$m$ $3$-isogeny chains.
We improve the length-$m$ $3$-isogeny walks required by the KEM from Nakagawa and Onuki (CRYPTO 2024) by using our results and introducing more suitable parameter sets that are friendly with C-code implementations. In particular, our experiments illustrate an improvement between 26.41% and 35.60% in savings when calculating length-$m$ $3$-isogeny chains and using our proposed parameters instead of those proposed by Nakagawa and Onuki (CRYPTO 2024).
Finally, we enhance the key generation of $\mathsf{CTIDH}$-2048 by including radical $3$-isogeny chains over the basefield $\mathbb{F}_p$, reducing the overhead of finding a $3$-torsion basis as required in some instantiations of the $\mathsf{CSIDH}$ protocol. Our experiments illustrate the advantage of radical $3$ isogenies in the key generation of $\mathsf{CTIDH}$-2048, with an improvement up to 4 times faster than the original $\mathsf{CTIDH}$.
Fast AVX-512 Implementation of the Optimal Ate Pairing on BLS12-381
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 (resp., SIMD) extensions of modern 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.
On the Estonian Internet Voting System, IVXV, SoK and Suggestions
The Estonian i-voting experience is probably the richest to analyze; a country that is considered a pioneer in digitizing both the government and private sector since 2001 followed by online internet voting (i-voting) in 2005. However, there are still some complaints submitted, critics and remarks to consider about the IVXV system. In this paper, we introduce a Systemization of Knowledge of the Estonian IVXV i-voting system and propose some added security enhancements. The presented SoK discusses applications implemented by election observers in 2023 & 2024 elections, which, to our knowledge, have never been mentioned and/or analyzed in the academia before. We also point out to unnoticed automated formal verification analysis of IVXV; the researchers discovered a privacy attack that we show extendable to a possible large scale encrypted vote copying. In addition, we identify and analyze recent fixes and improvements in the June 2024 version used in the European Parliament elections connecting them to their academic sources. Finally, we discuss the current system status, propose our own suggestions to some remaining vulnerabilities, then raise the inevitable question of the approaching quantum threat.
Comprehensive Deniability Analysis of Signal Handshake Protocols: X3DH, PQXDH to Fully Post-Quantum with Deniable Ring Signatures
The Signal protocol relies on a handshake protocol, formerly X3DH and now PQXDH, to set up secure conversations. One of its privacy properties, of value to Signal, is $\mathit{deniability}$, allowing users to deny participation in communications. Prior analyses of deniability for these protocols, including post-quantum variants, use models highly tailored to the individual protocols and generally make ad-hoc adaptations to "standard" AKE definitions, obscuring the concrete deniability guarantees and complicating comparisons across protocols.
Building on Hashimoto, Katsumata, and Wigger's abstraction for Signal handshake protocols (USENIX'25), we address this gap by presenting a unified framework for analyzing their deniability. We analyze Signal's classically secure X3DH and harvest-now-decrypt-later-secure PQXDH, and show the settings for which PQXDH is (un)deniable against harvest-now-$\mathit{judge}$-later attacks, where a quantum judge retrospectively assesses the participation of classical users. We further analyze post-quantum alternatives like RingXKEM, whose deniability relies on ring signatures (RS). By introducing a novel metric inspired by differential privacy, we provide relaxed, pragmatic guarantees for deniability.
Lastly, we also use this metric to define $\mathit{deniability}$ for RS, a relaxation of anonymity, allowing us to build an efficient RS from NIST-standardized Falcon (and MAYO), which is not anonymous, but is provably deniable. We believe this relaxation to have independent interest outside of the Signal handshake protocol.
FAEST for Memory-Constrained Devices with Side-Channel Protections
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. Based on the compact implementation, we develop a masked version of FAEST aiming at security against first-order attacks, achieving a performance overhead of 1.26x and a memory overhead of 1.93x. The masked implementation also thwarts horizontal attacks by employing additional shuffling countermeasures. The security of the masked implementation is demonstrated through leakage assessment experiments in the ChipWhisperer platform, both for the main building blocks and the full signature scheme. We conclude the paper by discussing how the side-channel protections can be ported to version 2.0 submitted to NIST.
A Novel Partial Key Exposure Attack on Common Prime RSA
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.
Improving RSA Cryptanalysis: Combining Continued Fractions and Coppersmith's Techniques
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.
mid-pSquare: Leveraging the Strong Side-Channel Security of Prime-Field Masking in Software
Efficiently protecting embedded software implementations of standard symmetric cryptographic primitives against side-channel attacks has been shown to be a considerable challenge in practice. This is, in part, due to the most natural countermeasure for such ciphers, namely Boolean masking, not amplifying security well in the absence of sufficient physical noise in the measurements. So-called prime-field masking has been demonstrated to provide improved theoretical guarantees in this context, and the Feistel for Prime Masking (FPM) family of Tweakable Block Ciphers (TBCs) has been recently introduced by Grassi et al. (Eurocrypt’24) to efficiently leverage these advantages. However, it was so far only instantiated for and empirically evaluated in a hardware implementation context, by using a small (7-bit) prime modulus. In this paper, we build on the theoretical incentive to increase the prime field size to obtain improved side-channel (Faust et al., Eurocrypt’24) and fault (Moos et al., CHES’24) resistance, as well as on the practical incentive to instantiate an FPM instance with optimized performance on 32-bit software platforms. We introduce mid-pSquare for this purpose, a lightweight TBC operating over a 31-bit Mersenne prime field. We first provide an in-depth black-box security analysis with a particular focus on algebraic attacks – which, contrary to the cryptanalysis of instances over smaller primes, are more powerful than statistical ones in our setting.
We also design a strong tweak schedule to account for potential related-tweak algebraic attacks which, so far, are almost unknown in the literature. We then demonstrate that mid-pSquare implementations deliver very competitive performance results on the target platform compared to analogous binary TBCs regardless of masked or unmasked implementation (we use fix-sliced SKINNY for our comparisons). Finally, we experimentally establish the side-channel security improvements that masked mid-pSquare can lead to, reaching unmatched resistance to profiled horizontal attacks on lightweight 32-bit processors (ARM Cortex-M4).
SecFePAS: Secure Facial-Expression-Based Pain Assessment with Deep Learning at the Edge
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.
BitVM with Succinct On-Chain Cost from AB-LFE, HMAC, or Privacy-Free GC
This paper aims to be a systematization of knowledge on how to instantiate BitVM with succinct on-chain cost from attribute-based laconic function evaluation (AB-LFE), homomorphic message authentication codes (HMAC), or privacy-free garbled circuits (GC) with suitable properties, specifically with:
- AB-LFE with unbounded depth and with bounded depth, which implies reusable privacy-free garbled circuits
- HMAC in with unbounded depth, which implies succinct privacy-free garbled circuits
- privacy-free garbled circuits and their succinct garbling as in BitGC
They vary in complexity, concrete overhead, succinctness, reusability, and security mechanisms against a malicious garbler. This paper is a literature review, as instantiating BitVM with them is straightforward.
Randomized vs. Deterministic? Practical Randomized Synchronous BFT in Expected Constant Time
Most practical synchronous Byzantine fault-tolerant (BFT) protocols, such as Sync HotStuff (S&P 2020), follow the convention of partially synchronous BFT and adopt a deterministic design. Indeed, while these protocols achieve O(n) time complexity, they exhibit impressive performance in failure-free scenarios.
This paper challenges this conventional wisdom, showing that a randomized paradigm terminating in expected O(1) time may well outperform prior ones even in the failure-free scenarios. Our framework reduces synchronous BFT to a new primitive called multi-valued Byzantine agreement with strong external validity (MBA-SEV). Inspired by the external validity property of multi-valued validated Byzantine agreement (MVBA), the additional validity properties allow us to build a BFT protocol where replicas agree on the hashes of the blocks. Our instantiation of the paradigm, Sonic, achieves O(n) amortized message complexity per block proposal, expected O(1) time, and enables a fast path of only two communication step.
Our evaluation results using up to 91 instances on Amazon EC2 show that the peak throughput of Sonic and P-Sonic (a pipelining variant of Sonic) is 2.24x-14.52x and 3.08x-24.25x that of Sync HotStuff, respectively.
Early Stopping for Any Number of Corruptions
Minimizing the round complexity of byzantine broadcast is a fundamental question in distributed computing and cryptography. In this work, we present the first early stopping byzantine broadcast protocol that tolerates up to $t=n-1$ malicious corruptions and terminates in $O(\min\{f^2,t+1\})$ rounds for any execution with $f\leq t$ actual corruptions. Our protocol is deterministic, adaptively secure, and works assuming a plain public key infrastructure. Prior early-stopping protocols all either require honest majority or tolerate only up to $t=(1-\epsilon)n$ malicious corruptions while requiring either trusted setup or strong number theoretic hardness assumptions. As our key contribution, we show a novel tool called a polariser that allows us to transfer certificate-based strategies from the honest majority setting to settings with a dishonest majority.
Multi-Authority Registered Attribute-Based Encryption
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).
Polar Lattice Cryptography
Presenting a protocol that builds a cryptographic solution which shifts security responsibility from the cipher designer to the cipher user. The Polar Lattice is a pattern-devoid cryptographic cipher. It is based on a geometric construct -- a polar lattice, on which the letters of a plaintext alphabet A, are presented as two points each letter, so that to transmit a letter the transmitter transmits a randomized pathway, a trail, (ciphertext) that begins at the first point of the transmitted letter and ends at the second point of the transmitted letter; the transmitted pathway is a set of steps on the lattice. Once a letter is transmitted the next bits on the ciphertext mark the beginning of the pathway that points to the next letter. The size and the geometric construction of the polar lattice are randomized and kept secret. The randomized pathways may be long or short, the attacker does not know how to parcel the ciphertext to individual trails pointing to distinct letters in the plaintext alphabet A. The polar lattice may be implemented algebraically, or geometrically; the lattice may be a physical nano-construct. The polar lattice is very power efficient, very fast. It claims all the attributes associated with pattern devoid cryptography: it allows for only brute force cryptanalysis, which in turn can be defeated through increased ciphertext size, unlimited key size and structure complexity.
In the Vault, But Not Safe: Exploring the Threat of Covert Password Manager Providers
Password managers have gained significant popularity and are widely recommended as an effective means of enhancing user security. However, current cloud-based architectures assume that password manager providers are trusted entities. This assumption is never questioned because such password managers are operated by their own designers, which are therefore judge and jury. This exposes users to significant risks, as a malicious provider could perform covert actions without being detected to access or alter users' credentials.
This exposes users to significant risks, as a malicious provider could perform covert actions without being detected to access or alter the credentials of users.
Most password managers rely solely on the strength of a user-chosen master password. As a result, a covert adversary could conceivably perform large-scale offline attacks to recover credentials protected by weak master passwords. Even more concerning, some password managers do not encrypt credentials on users' devices, transmitting them in plaintext before encrypting them server-side, e.g., Google, in its default configuration. On the other hand, key-protected password managers, e.g., KeePassXC, are less commonly used, as they lack functionality for synchronizing credentials across multiple devices.
In this paper, we establish a comprehensive set of security properties that should be guaranteed by any cloud-based password manager. We demonstrate that none of the widely deployed mainstream password managers fulfill these fundamental requirements. Nevertheless, we argue that it is feasible to design a solution that is resilient against covert adversaries while allowing users to synchronize their credentials across devices. To support our claims, we propose a password manager design that fulfills all the required properties.
PIsignHD: A New Structure for the SQIsign Family with Flexible Applicability
In this paper, we propose a new structure for the SQIsign family: Pentagon Isogeny-based Signature in High Dimension (referred to as PIsignHD).
The new structure separates the hash of the commitment and that of the message by employing two cryptographic hash functions. This feature is desirable in reality, particularly for applications based on mobile low-power devices or for those deployed interactively over the Internet or in the cloud computing setting.
This structure can be generally applied to all SQIsign variants. In this work, we focus on the instance based on SQIsignHD.
Compared with SQIsignHD, PIsignHD has the same signature size (even smaller for some application scenarios). For the NIST-I security level, the signature size of PIsignHD can be reduced to 519 bits, while the SQIsignHD signature takes 870 bits. Additionally, PIsignHD has an efficient online signing process and enjoys much desirable application flexibility. In our experiments, the online signing process of PIsignHD runs in 4 ms.
Scalable Accountable Byzantine Agreement and Beyond
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: the ratifier and the 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}$.
On Weak NIZKs, One-way Functions and Amplification
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}$.
Improving the Fault Robustness of Polynomial Masking
Rigorous protection against physical attacks which simultaneously and adaptively combine passive side-channel observations with active fault injections is an active and recent area of research. At CRYPTO 2023, Berndt et al. presented the “LaOla” scheme for protecting arbitrary circuits against said attacks. Their constructions use polynomial masking in an optimal least number of shares and come with security proofs based on formal notions of security.
In this work, we improve the security of this construction significantly by adapting it. We present a new refresh gadget designed specifically for combined attacks. This gadget does not only counteract passive side-channel attacks but additionally randomizes the effect of faults in a detectable but secret-independent manner. We introduce sufficient and attainable security definitions which are stronger than in the work of Berndt et al. to achieve this. Further, we apply the principle to the LaOla construction and prove the stronger
security notions for the adapted multiplication gadget, as well as the original
properties of composability and strong security against adaptive attacks combining side-channel and faults.
On the security of the initial tropical Stickel protocol and its modification based on Linde-de la Puente matrices
Recently, a more efficient attack on the initial tropical Stickel protocol has been proposed, different from the previously known Kotov-Ushakov attack, yet equally guaranteed to succeed. Given that the Stickel protocol can be implemented in various ways, such as utilizing platforms beyond the tropical semiring or employing alternative commutative matrix ``classes'' instead of polynomials, we firstly explore the generalizability of this new attack across different implementations of the Stickel protocol. We then conduct a comprehensive security analysis of the Stickel protocol based on Linde-de la Puente (LdlP) matrices. Additionally, we extend the concept of LdlP matrices beyond the tropical semiring, generalizing it to a broader class of semirings and include a discussion of the centralizer of such matrices over the tropical semiring.
New constructions of pseudorandom codes
Introduced in [CG24], pseudorandom error-correcting codes (PRCs) are a new
cryptographic primitive with applications in watermarking generative AI models.
These are codes where a collection of polynomially many codewords is computationally indistinguishable from random for an adversary that does not have the secret key, but anyone with the secret key is able to efficiently decode corrupted codewords. In this work, we examine the assumptions under which PRCs with
robustness to a constant error rate exist.
1. We show that if both the planted hyperloop assumption introduced in
[BKR23] and security of a version of Goldreich's PRG hold, then there exist
public-key PRCs for which no efficient adversary can distinguish a polynomial
number of codewords from random with better than $o(1)$ advantage.
2. We revisit the construction of [CG24] and show that it can be based on a
wider range of assumptions than presented in [CG24]. To do this, we introduce a
weakened version of the planted XOR assumption which we call the weak planted
XOR assumption and which may be of independent interest.
3. We initiate the study of PRCs which are secure against space-bounded
adversaries. We show how to construct secret-key PRCs of length $O(n)$ which
are $\textit{unconditionally}$ indistinguishable from random by
$\text{poly}(n)$ time, $O(n^{1.5-\varepsilon})$ space adversaries.
Adaptive TDF from any TDF via Pseudorandom Ciphertext PKE
We present a generic construction of adaptive trapdoor function (TDF) from the combination of any TDF and pseudorandom-ciphertext public-key encryption (PKE) scheme. As a direct corollary, we can obtain adaptive TDF from any trapdoor permutation (TDP) whose domain is both recognizable and sufficiently dense. In our construction, we can prove that the function's output is indistinguishable from uniform even when an adversary has access to the inversion oracle.
Formulations and Constructions of Remote State Preparation with Verifiability, with Applications
Remote state preparation with verifiability (RSPV) is an important quantum cryptographic primitive [GV19,Zha22]. In this primitive, a client would like to prepare a quantum state (sampled or chosen from a state family) on the server side, such that ideally the client knows its full description, while the server holds and only holds the state itself. In this work we make several contributions on its formulations, constructions and applications. In more detail:
- We first work on the definitions and abstract properties of the RSPV problem. We select and compare different variants of definitions [GV19,GMP22,Zha22], and study their basic properties (like composability and amplification).
- We also study a closely related question of how to certify the server's operations (instead of solely the states). We introduce a new notion named remote operator application with verifiability (ROAV). We compare this notion with related existing definitions [SW87,MY04,MV21,NZ23], study its abstract properties and leave its concrete constructions for further works.
- Building on the abstract properties and existing results [BGKPV23], we construct a series of new RSPV protocols. Our constructions not only simplify existing results [GV19] but also cover new state families, for example, states in the form of $\frac{1}{\sqrt{2}}(|0\rangle|x_0\rangle+|1\rangle|x_1\rangle)$. All these constructions rely only on the existence of weak NTCF [BKVV,AMR22], without additional requirements like the adaptive hardcore bit property [BCMVV,AMR22].
- As a further application, we show that the classical verification of quantum computations (CVQC) problem [ABEM,Mah18] could be constructed from assumptions on group actions [ADMP20]. This is achieved by combining our results on RSPV with group-action-based instantiation of weak NTCF [AMR22], and then with the quantum-gadget-assisted quantum verification protocol [FKD18].
HADES: Automated Hardware Design Exploration for Cryptographic Primitives
While formal constructions for cryptographic schemes have steadily evolved and emerged over the past decades, the design and implementation of efficient and secure hardware instances are still mostly manual, tedious, and intuition-driven processes. With the increasing complexity of modern cryptography, e.g., Post-Quantum Cryptography (PQC) schemes, and consideration of physical implementation attacks, e.g., Side-Channel Analysis (SCA), the design space often grows exorbitantly without developers being able to weigh all design options.
This emphasizes the evident necessity for tool-assisted Design Space Exploration (DSE) for efficient and secure cryptographic hardware. To address this demand, we present the HADES framework. This tool systematically traverses the design space driven by security requirements, rapidly predicts user-defined performance metrics, e.g., area footprint or cycle-accurate latency, and instantiates the most suitable candidate in a synthesizable Hardware Description Language (HDL).
We demonstrate the capabilities of our framework by applying our proof-of-concept implementation to a wide-ranging selection of symmetric and PQC schemes, including the ChaCha20 stream cipher and the PQC standard Kyber. Notably, for these schemes, we present the first hardware implementations featuring arbitrary-order masking.
Improved Matrix Inversion with Packed Ciphertexts using Fully Homomorphic Encryption
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.
HyperPianist: Pianist with Linear-Time Prover and Logarithmic Communication Cost
Recent years have seen great improvements in zero-knowledge proofs (ZKPs). Among them, zero-knowledge SNARKs are notable for their compact and efficiently-verifiable proofs, but suffer from high prover costs. Wu et al. (Usenix Security 2018) proposed to distribute the proving task across multiple machines, and achieved significant improvements in proving time. However, existing distributed ZKP systems still have quasi-linear prover cost, and may incur a communication cost that is linear in circuit size.
In this paper, we introduce $\mathsf{HyperPianist}$. Inspired by the state-of-the-art distributed ZKP system Pianist (Liu et al., S&P 2024) and the multivariate proof system HyperPlonk (Chen et al., EUROCRYPT 2023), we design a distributed multivariate polynomial interactive oracle proof (PIOP) system with a linear-time prover cost and logarithmic communication cost. Unlike Pianist, $\mathsf{HyperPianist}$ incurs no extra overhead in prover time or communication when applied to general (non-data-parallel) circuits. To instantiate the PIOP system, we adapt two additively-homomorphic multivariate polynomial commitment schemes, multivariate KZG (Papamanthou et al., TCC 2013) and Dory (Lee et al., TCC 2021), into the distributed setting, and get $\mathsf{HyperPianist^K}$ and $\mathsf{HyperPianist^D}$ respectively. Both systems have linear prover complexity and logarithmic communication cost; furthermore, $\mathsf{HyperPianist^D}$ requires no trusted setup. We also propose $\mathsf{HyperPianist+}$, incorporating an optimized lookup argument based on Lasso (Setty et al., EUROCRYPT 2024) with lower prover cost.
Experiments demonstrate $\mathsf{HyperPianist^K}$ and $\mathsf{HyperPianist^D}$ achieve speedups of $63.1\times$ and $40.2\times$ over HyperPlonk with 32 distributed machines. Compared to Pianist, $\mathsf{HyperPianist^K}$ can be $2.9\times$ and $4.6\times$ as fast and $\mathsf{HyperPianist^D}$ can be $2.4\times$ and $3.8\times$ as fast, on vanilla gates and custom gates respectively. With layered circuits, $\mathsf{HyperPianist^K}$ is up to $5.9\times$ as fast on custom gates, and $\mathsf{HyperPianist^D}$ achieves a $4.7\times$ speedup.
Grafting: Decoupled Scale Factors and Modulus in RNS-CKKS
The CKKS Fully Homomorphic Encryption (FHE) scheme enables approximate arithmetic on encrypted complex numbers for a desired precision. Most implementations use RNS with carefully chosen parameters to balance precision, efficiency, and security. However, a key limitation in RNS-CKKS is the rigid coupling between the scale factor, which determines numerical precision, and the modulus, which ensures security. Since these parameters serve distinct roles—one governing arithmetic correctness and the other defining cryptographic structure—this dependency imposes design constraints, such as a lack of suitable NTT primes and limited precision flexibility, ultimately leading to inefficiencies.
We propose Grafting, a novel approach to decouple scale factors from the modulus by introducing (universal) sprouts, reusable modulus factors that optimize word-sized packing while allowing flexible rescaling. With the universal property, sprouts allow rescaling by arbitrary bit-lengths and key-switching at any modulus bit-length without requiring additional key-switching keys. Decoupling the scale factor from the modulus in Grafting yields significant efficiency gains: (1) Optimized RNS packing by decomposing the modulus into machine word-sized components, accelerating computations and reducing the ciphertext and encryption/evaluation key sizes; and (2) A freely adjustable scale factor independent of the modulus, unifying the ring structure across applications and reducing modulus consumption through adaptive scalings.
Our experiments demonstrate that Grafting improves performance across standard SHE/FHE parameter sets for ring dimensions $2^{14}$-$2^{16}$ by up to $1.83\times$ and $2.01\times$ for key-switchings and multiplications, respectively, and up to $1.92\times$ for bootstrapping. Grafting also reduces public key and ciphertext sizes by up to $62\%$ without compressions, maintaining the same number of public keys as before. As an application, we showcase the CKKS gate bootstrapping for bits (Bae et al.; Eurocrypt'24), achieving $1.89\times$ speed-up due to the reduced number of RNS factors. Finally, we revisit the homomorphic comparison (Cheon et al.; Asiacrypt'20), evaluating it with carefully chosen scale factors for each iteration, reporting up to $204$-bit fewer modulus consumption ($27\%$ reduction) in the standard parameter set, without precision loss.
zkMarket: Ensuring Fairness and Privacy in Decentralized Data Exchange
Ensuring fairness in blockchain-based data trading presents significant challenges, as the transparency of blockchain can expose sensitive details and compromise fairness. Fairness ensures that the seller receives payment only if they provide the correct data, and the buyer gains access to the data only after making the payment. Existing approaches face limitations in efficiency, particularly when applied to large-scale data. Moreover, preserving privacy has also been a significant challenge in blockchain.
In this paper, we introduce zkMarket, a privacy-preserving fair trade system on the blockchain. We ensure fairness by integrating encryption with zk-SNARKs, enabling verifiable proofs for fair trading. However, applying zk-SNARKs directly can be computationally expensive for the prover. To address this, we improve efficiency by leveraging our novel matrix-formed PRG (MatPRG) and commit-and-prove SNARK (CP-SNARK), making the data registration process more concise and significantly reducing the seller's proving time. To ensure transaction privacy, zkMarket is built upon an anonymous transfer protocol.
Experimental results demonstrate that zkMarket significantly reduces the computational overhead associated with traditional blockchain solutions while maintaining robust security and privacy. Specifically, our evaluation quantifies this high efficiency: the seller can register 1MB of data in 2.8 seconds, the buyer can generate the trade transaction in 0.2 seconds, and the seller can finalize the trade within 0.4 seconds.
Threshold Structure-Preserving Signatures with Randomizable Key
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.
EinHops: Einsum Notation for Expressive Homomorphic Operations on RNS-CKKS Tensors
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.
Applications Of Zero-Knowledge Proofs On Bitcoin
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.
Key Recovery from Side-Channel Power Analysis Attacks on Non-SIMD HQC Decryption
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.
Linear Prover IOPs in Log Star Rounds
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.
Weave: Efficient and Expressive Oblivious Analytics at Scale
Many distributed analytics applications that are offloaded to the cloud operate on sensitive data. Even when the computations for such analytics workloads are confined to trusted hardware enclaves and all stored data and network communications are encrypted, several studies have shown that they are still vulnerable to access pattern attacks. Prior efforts towards preventing access pattern leakage often incur network and compute overheads that are logarithmic in dataset size, while also limiting the functionality of supported analytics jobs.
We present Weave, an efficient, expressive, and secure analytics platform that scales to large datasets. Weaveemploys a combination of noise injection and hardware memory isolation via enclave page caches to reduce the network and compute overheads for oblivious analytics to a constant factor. Weave also employs several optimizations and extensions that exploit dataset and workload-specific properties to ensure performance at scale without compromising on functionality. Our evaluations show that Weave reduces the end-to-end execution time for a wide range of analytics jobs on large real-world datasets by $4$--$10\times$ compared to prior state-of-the-art while providing strong obliviousness guarantees.
What’s the Matter? An In-Depth Security Analysis of the Matter Protocol
The Matter protocol has emerged as a leading standard for secure IoT interoperability, backed by major vendors such as Apple, Google, Amazon, Samsung, and others. With millions of Matter-certified devices already deployed, its security assurances are critical to the safety of global IoT ecosystems. This paper presents the first in-depth security evaluation and formal analysis of Matter’s core protocols, focusing on its Passcode-Authenticated Session Establishment (PASE) and Certificate Authenticated Session Establishment (CASE) mechanisms. While these are based on the well-studied SPAKE2+ and SIGMA respectively, Matter introduces modifications that compromise the original security guarantees. Our analysis reveals multiple cryptographic design flaws, including low-entropy passcodes, static salts, and weak PBKDF2 parameters – all of which contradict Matter’s own threat model and stated security goals. We highlight cases where Matter delegates critical security decisions to vendors, rather than enforcing robust cryptographic practices in the specification, thereby making the system more fragile and susceptible to exploitation. We formally model both standard and Matter-adapted variants of these protocols in ProVerif, confirming several of Matter’s security goals, but disproving others. Our findings go as far as rendering some of Matter’s own mitigations insufficient, exposing all Matter-certified devices to threats classified as “High Risk” in their own documentation. As part of our study, we also discovered previously unknown vulnerabilities in Matter’s public codebase, which we responsibly disclosed to the developers, leading to updates in the codebase.
Efficient CPA Attack on Hardware Implementation of ML-DSA in Post-Quantum Root of Trust
Side-channel attacks (SCA) pose a significant threat to cryptographic implementations, including those designed to withstand the computational power of quantum computers.
This paper introduces the first side-channel attack on an industry-grade post-quantum cryptography implementation.
Specifically, we present a Correlation Power Analysis (CPA) attack targeting the open-source hardware implementation of ML-DSA within a Silicon Root of Trust framework developed through a multi-party collaboration involving leading technology companies.
Our attack focuses on the modular reduction process that follows the Number Theoretic Transform-based polynomial pointwise multiplication.
By exploiting side-channel leakage from a distinctive unique reduction algorithm and leveraging the zeroization mechanism used to securely erase sensitive information by clearing internal registers, we significantly enhance the attack's efficacy.
Our findings reveal that an adversary can extract the secret keys using only 10,000 power traces.
With access to these keys, an attacker could forge signatures for certificate generation, thereby compromising the integrity of the root of trust.
This work highlights the vulnerabilities of industry-standard root-of-trust systems to side-channel attacks. It underscores the urgent need for robust countermeasures to secure commercially deployed systems against such threats.
That’s AmorE: Amortized Efficiency for Pairing Delegation
Over two decades since their introduction in 2005, all major verifiable pairing delegation protocols for public inputs have been designed to ensure unconditional security. However, we note that a delegation protocol involving only ephemeral secret keys in the public view can achieve everlasting security, provided the server is unable to produce a pairing forgery within the protocol's execution time. Thus, computationally bounding the adversary's capabilities during the protocol's execution may be more reasonable when the goal is to achieve significant efficiency gains for the delegating party. This consideration is particularly relevant given the continuously evolving computational costs associated with pairing computations and their ancillary blocks, which creates an ever-changing landscape for what constitutes efficiency in pairing delegation protocols. With the goal of fulfilling both efficiency and everlasting security, we present AmorE, a protocol equipped with an adjustable security and efficiency parameter for sequential pairing delegation, which achieves state-of-the-art Amortized Efficiency in terms of the number of pairing computations. For example, delegating batches of 10 pairings on the BLS48-575 elliptic curve via our protocol costs to the client, on average, less than a single scalar multiplication in $G_2$ per delegated pairing, while still ensuring at least 40 bits of statistical security.
On Knowledge-Soundness of Plonk in ROM from Falsifiable Assumptions
Lipmaa, Parisella, and Siim [Eurocrypt, 2024] proved the extractability of the KZG polynomial commitment scheme under the falsifiable assumption ARSDH. They also showed that variants of real-world zk-SNARKs like Plonk can be made knowledge-sound in the random oracle model (ROM) under the ARSDH assumption. However, their approach did not consider various batching optimizations, resulting in their variant of Plonk having approximately $3.5$ times longer argument. Our contributions are: (1) We prove that several batch-opening protocols for KZG, used in modern zk-SNARKs, have computational special-soundness under the ARSDH assumption. (2) We prove that interactive Plonk has computational special-soundness under the ARSDH assumption and a new falsifiable assumption SplitRSDH. We also prove that two minor modifications of the interactive Plonk have computational special-soundness under only the ARSDH and a simpler variant of SplitRSDH. We define a new type-safe oracle framework of the AGMOS (AGM with oblivious sampling) and prove SplitRSDH is secure in it. The Fiat-Shamir transform can be applied to obtain non-interactive versions, which are secure in the ROM under the same assumptions.
Delegated PSI from Homomorphic Encryptions
This paper presents an efficient protocol for private set intersection in a setting with multiple set owners and a semi-honest cloud server. The core idea is to reduce the intersection computation to secure operations over Bloom filters, enabling both scalability and efficiency. By leveraging this transformation, our protocols achieve strong privacy guarantees while minimizing computation and communication overhead.
SMOOTHIE: (Multi-)Scalar Multiplication Optimizations On TFHE
The (Multi-)Scalar multiplication is a crucial operation during FHE-related
AI applications, and its performance has a significant impact on the overall efficiency of these applications. In this paper we introduce SMOOTHIE: (Multi-)Scalar Multiplication Optimizations On TFHE, introducing new techniques to improve the performance of single- and multi-scalar multiplications in TFHE. We show that by taking the bucket method, known from the Elliptic Curve field, significant improvements can be made. However, as the characteristics between TFHE and Elliptic Curves differ, we need to adapt this method and introduce novel optimizations. We propose a new negation with offset technique that eliminates direct carry propagation after ciphertext negation. Additionally, we introduce powershift aggregation and bucket merging techniques for the bucket aggregation step, which exploit TFHE properties to substantially 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 ×2.05 speedup for single-scalar multiplication compared to the current state-of-the-art, with multi-scalar multiplication improvements up to ×7.51, depending on the problem size.
Revisiting Honest Re-Encryption Attack for Proxy Re-Encryption Schemes
Proxy re-encryption (PRE) schemes allow a delegator to designate a proxy to re-encrypt its ciphertext into a ciphertext that the delegatee can decrypt. In contrast, the proxy gains nothing helpful from this transformation. This decryption-power transfer is proper in applications of encrypted email forwarding, key escrow, and publish/subscribe systems. The security notions for PRE are inherited from the standard public key encryption (PKE) schemes, i.e., indistinguishability under chosen-plaintext attacks (CPA) and under chosen-ciphertext attacks (CCA). A recently popular notion, indistinguishability under honest re-encryption attacks (HRA), was proposed by Cohen in 2019, indicating that CPA security is insufficient for PRE because some CPA-secure PRE provides no security against the adversarial delegatee. Many post-quantum secure PRE schemes have recently been designed under the HRA security model. However, HRA security differs from traditional CCA security, and there is no known reduction between them. The existing results show they appear to be incompatible. This paper aims to bridge those two security notions via reductions. We find that if the re-encryption is single-hop, CCA security actually implies HRA. In addition, we extract a weaker security notion to capture the unlearnability of re-encryption key (RKUL), which is implied by both CCA and HRA security. RKUL promises that, given input and output ciphertexts of the re-encryption algorithm, the adversary cannot learn the re-encryption key. Next, we show that many proved HRA-secure schemes have no RKUL; therefore, those schemes are not HRA-secure.
Hydrangea: Optimistic Two-Round Partial Synchrony
We introduce Hydrangea, a partially synchronous Byzantine fault-tolerant state machine replication protocol that offers strong fault tolerance and achieves a fast, two-round commit in optimistic scenarios. Specifically, for a system of $n = 3f + 2c + k + 1$ parties, Hydrangea achieves an optimistic good-case latency of two rounds when the number of faulty parties (Byzantine or crash) is at most $p = \lfloor \frac{c+k}{2} \rfloor$ for a parameter $k \geq 0$. In more adversarial settings with up to $f$ Byzantine faults and $c$ crash faults, Hydrangea obtains a good-case latency of three rounds. Furthermore, we prove a matching lower bound: no protocol can achieve two-round optimistic commit under this fault model if $p > \lfloor \frac{c+k+2}{2} \rfloor$.
Willow: Secure Aggregation with One-Shot Clients
A common drawback of secure vector summation protocols in the single-server model is that they impose at least one synchronization point between all clients contributing to the aggregation. This results in clients waiting on each other to advance through the rounds of the protocol, leading to large latency (or failures due to too many dropouts) even if the protocol is computationally efficient. In this paper we propose protocols in the single-server model where clients contributing data to the aggregation (i) send a single message to the server and (ii) can join aggregation sessions dynamically whenever they have resources, i.e., without the need for synchronizing their reporting time with any other clients. Our approach is based on a committee of parties that aid in the computation by running a setup phase before data collection starts, and a verification/decryption phase once it ends. Unlike existing committee-based protocols such as Flamingo (S&P 2023), the cost for committee members can be made sub-linear in the number of clients, and does not depend on the size of the input client vectors. Our experimental evaluation shows that our protocol, even while allowing dynamic client participation, is competitive with the state of the art protocols that do not have that feature in both computation and communication.
A Fiat–Shamir Transformation From Duplex Sponges
We analyze a variant of the Fiat–Shamir transformation based on an ideal permutation. The transformation relies on the popular duplex sponge paradigm, and minimizes the number of calls to the permutation (given the information to absorb/squeeze). This closely models deployed variants of the Fiat–Shamir transformation, and our analysis provides concrete security bounds to guide security parameters in practice. Our results contribute to the ongoing community-wide effort to achieve rigorous, and ultimately formally verified, security proofs for deployed cryptographic proofs. Along the way, we find that indifferentiability (a property proven for many modes of operation, including the duplex sponge) is ill-suited for establishing the knowledge soundness and zero knowledge of a non-interactive argument.
We additionally contribute spongefish, an open-source Rust library implementing our Fiat–Shamir transformation. The library is interoperable across multiple cryptographic frameworks, and works with any choice of permutation. The library comes equipped with Keccak and Poseidon permutations, as well as several "codecs" for re-mapping prover and verifier messages to the permutation's domain.
Efficiently parsing existing eID documents for zero-knowledge proofs
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.
A note on a recent attack against SPEEDY-7-192
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}$.
Copy Protecting Cryptographic Functionalities over Entropic Inputs
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.
Multi-Party Homomorphic Encryption with Dynamicity and Ciphertext Reusability
Homomorphic Encryption (HE) is a cryptographic primitive that enables computation on encrypted data while preserving user privacy. We explore its application in the multi-party setting, where data is stored in the cloud encrypted under several distinct keys.
A straightforward approach is to use Multi-Key Homomorphic Encryption (MKHE), which supports computation over ciphertexts encrypted under different keys. However, MKHE incurs space and computational overhead of $O(n)$ with respect to the number of users $n$, making it impractical for large-scale scenarios. In contrast, Multi-Party Homomorphic Encryption (MPHE) achieves constant overhead $O(1)$, but suffers from significant limitations: ciphertexts are tied to a fixed group of parties. They cannot be reused across different contexts, and new parties cannot join dynamically.
To address these limitations, we consider a relaxed model where secret key owners perform limited communication before the computation phase. Consequently, the ciphertext sizes and evaluation complexities are reduced from $O(n)$ to $O(1)$, matching the efficiency of a single‑key HE setting during computation. Building on this idea, we propose Reusable Dynamic Multi-Party Homomorphic Encryption (rdMPHE), a primitive better suited for real-world deployments. Within this framework, the pre-computation phase requires just a few rounds of communication, and both evaluation and space complexities remain independent of the number of users.
We construct and implement a rdMPHE scheme based on the Ring Learning with Errors (RLWE) assumption. Our asymptotic and experimental analyses demonstrate that rdMPHE attains efficiency comparable to MKHE while overcoming its scalability limitations. Additionally, our experiments verify support for the dynamic participation of new parties and the reusability of ciphertexts.
OasisDB: An Oblivious and Scalable System for Relational Data
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.
Public-Key Quantum Money From Standard Assumptions (In The Generic Model)
Our main result is a quantum polynomial-time reduction from the group action discrete logarithm (DLP) problem to a specific cloning problem. A consequence of this result is that the public-key quantum money scheme proposed by Zhandry (2024), which is based on abelian group actions, is secure in the generic group action model. Specifically, our result shows that breaking the quantum money scheme is equivalent, under quantum polynomial-time reductions, to solving the group action DLP. An immediate implication of our result concerns the relationship between cloning and preparing Fourier states: our main theorem shows that the problem of cloning group action Fourier states is equivalent to the problem of preparing them.
HiAE Remains Secure in Its Intended Model: A Clarification of Claimed Attacks
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.
The Concrete Security of Two-Party Computation: Simple Definitions, and Tight Proofs for PSI and OPRFs
This paper initiates a concrete-security treatment of two-party secure computation. The first step is to propose, as target, a simple, indistinguishability-based definition that we call InI. This could be considered a poor choice if it were weaker than standard simulation-based definitions, but it is not; we show that for functionalities satisfying a condition called invertibility, that we define and show is met by functionalities of practical interest like PSI and its variants, the two definitions are equivalent. Based on this, we move forward to study the concrete security of a canonical OPRF-based construction of PSI, giving a tight proof of InI security of the constructed PSI protocol based on the security of the OPRF. This leads us to the concrete security of OPRFs, where we show how different DH-style assumptions on the underlying group yield proofs of different degrees of tightness, including some that are tight, for the well-known and efficient 2H-DH OPRF, and thus for the corresponding DH PSI protocol. We then give a new PSI protocol, called salted-DH PSI, that is as efficient as DH-PSI, yet enjoys tighter proofs.
Circular Insecure Encryption: from Long Cycles to Short Cycles
A length $n$ encryption cycle consists of a sequence of $n$ keys, each encrypting the next, forming a cycle, and an encryption scheme is $n$-circular secure if a length $n$ encryption cycle is computationally indistinguishable from encryptions of zeros. An interesting problem is whether CPA security implies circular security. This is shown to be not true. Using standard cryptographic assumptions and LWE, it was shown that within the class of CPA secure encryption schemes, for any $n$, there exists an $n$-circular insecure encryption scheme. Furthermore, there exists a particular encryption scheme that is $\ell$-circular insecure for all $\ell$. Following these results, it is natural to ask whether a circular insecurity of a particular length implies circular insecurity of different lengths and of multiple lengths. We answer this problem with an affirmative in this paper. We constructively prove that a CPA secure encryption scheme that is insecure in the presence of encryption cycles of length $(n+1)$ implies the existence of such a scheme for encryption cycles of any length less than $(n+1)$. The constructed $(\le n)$-circular insecure construction may have the same message space as the $(n+1)$-circular insecure encryption scheme, and our results apply to both public key and symmetric key settings.
Vectorised Hashing Based on Bernstein-Rabin-Winograd Polynomials over Prime Order Fields
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.
Solve Approximate CVP via Variants of Nearest-Colattice
The approximate Closest Vector Problem (CVP) is a core computational problem underlying many post-quantum lattice-based signature schemes, including Dilithium, one-more-ISIS, and HuFu. While the security of these schemes is typically expressed in terms of the Inhomogeneous Short Integer Solution (ISIS) problem, it is well-known that ISIS can be efficiently reduced to approximate CVP. Despite its foundational role, approximate CVP with non-negligible approximation factors remains far less explored than other lattice problems such as SVP or LWE, creating a critical gap in both theory and practice.
In this work, we bridge this gap by advancing the Colattice framework for solving approximate CVP with large approximation factors. More concretely, (1) We define a practical version of the Colattice algorithm and propose a randomized Nearest Colattice for generating more than one approximate closest vector. (2) Define a formal strategy space for blockwise approximate CVP. (3) Propose a polynomial-time strategy selection algorithm and prove its correctness under standard lattice heuristics. (4) Building on this, we design an efficient security estimator for approximate CVP in both Euclidean and Infinity norms, and extend it to approximate batch-CVP attack settings. (5) By applying this estimator, we perform concrete security evaluations of Dilithium, HuFu, and one-more-ISIS. Our results reveal that almost none of the evaluated schemes withstand approximate batch-CVP attacks with $2^{32}$ queries. (6) We integrate a slicer and Colattice into G6K-CPU, leveraging the Locality-Sensitive Hashing (LSH) technqiue for nearest neighbors search (NNS). This is the first practical implementation of an NNS-accelerated slicer. Our results demonstrate the practical efficiency of approximate CVP and batch-CVP attacks, highlighting the need for more accurate security estimation.
These findings underscore the practical importance of accurate approximate CVP modeling and call for a reassessment of current parameter sets in post-quantum signature schemes.
Improving the Masked Division for the FALCON Signature
FALCON is a post-quantum signature selected by the National Institute of Standards and Technology (NIST). Although its side-channel resilience has been studied and a masking countermeasure proposed, the division is a major performance bottleneck. This work proposes a different approach to the masked FALCON division. We use the Newton-Raphson method and a convergent sequence to approximate this operation. The first term of the sequence is evaluated using pre-calculated second-order minimax polynomials. As a consequence, computing the inverse only requires 5 masked additions and 8 masked multiplications, compared to the roughly 55 masked additions required by the previous state-of-the-art. Formal security proofs using the MIMO-SNI criteria are also provided.
Baloo: Nearly Optimal Lookup Arguments
We present Baloo, a protocol for lookup tables where the prover work is linear on the number of lookups and independent of the table size. Baloo is built over previous lookup arguments, and the framework for SNARKs from Ràfols and Zapico (CRYPTO 21).
Our protocol supports commit-and-prove expansions: the prover selects the subtable containing the elements used in the lookup, that is unknown to the verifier, commits to it and later proves its relation with the committed elements. This feature makes Baloo especially suitable for proving input-output relations on hash functions, and in particular to instantiate the Ethereum Virtual Machine (EVM).
Opossum Attack: Application Layer Desynchronization using Opportunistic TLS
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.
One-Step Schnorr Threshold Identification
Threshold zero-knowledge protocols have not been widely adopted,
presumably due to the relevant network overhead,
complicated certification processes
and thus limited interoperability chances.
In this work, we propose $\mathsf{OSST}$,
a Schnorr-based threshold identification scheme
that is both non-interactive and non-reliant on the public shares.
Given a $(n, t)$-shared secret $x$,
the proposed protocol allows
any $t^* \ge t$ (but no less) shareholders to collectively prove
that their secret keys combine to $x$ in the sense of interpolation
without revealing any information beyond that.
On the one side, the provers do not need to engage in
multi-party computations,
sending their packets to the verifier asynchronously.
On the other side, the verification operation
involves the combined public key $y \equiv g ^ x$ alone,
meaning that the verifier does not need to
have validated and registered the individual member identities.
The protocol
can be cheaply adopted in permissionless and dynamic environments,
where no certification processes or infrastructure support
are available, and be easily integrated
with existing verifiers by means of pure software extension.
No publicly trusted setup is required beyond
the assumption that $x$ has been
distributed by means of Shamir's secret sharing
(or equivalent distribution scheme)
and that the public counterpart has been advertised correctly;
in particular, the protocol is intended to be
secure against impersonation attacks
in the plain public-key model.
We provide evidence that this has good chances to
hold true by giving a formal security proof
in the random oracle model under the
one-more discrete-logarithm hardness
($\mathsf{OMDL}$) assumption.
Preimage-type Attacks for Reduced Ascon-Hash: Application to Ed25519
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.
Multi-Source Randomness Extraction and Generation in the Random-Oracle Model
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.
Non-Profiled Higher-Order Side-Channel Attacks against Lattice-Based Post-Quantum Cryptography
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.
Lattice-based Multi-key Homomorphic Signatures Forward-unforgeable against Signing Key Leakage
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.
Efficient Full Domain Functional Bootstrapping from Recursive LUT Decomposition
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.
UTRA: Universe Token Reusability Attack and Verifiable Delegatable Order-Revealing Encryption
As datasets grow, users increasingly rely on \modi{ cloud services for data storage and processing. Consequently, concerns regarding data protection and the practical use of encrypted data have emerged as significant challenges. One promising solution is} order-revealing encryption (ORE), which enables efficient operations on encrypted numerical data. \modi{To support distributed environments with different users, delegatable ORE (DORE) extends this functionality to multi-client settings, enabling order comparisons between ciphertexts encrypted under different secret keys. However, Hahn et al. proposed a token forgery attack against DORE with a threat model and introduced the secure DORE (SEDORE) scheme as a countermeasure. Despite this enhancement, we claim that SEDORE remains vulnerable under the same threat model.}
In this paper, we present a novel Universal Token Reusability Attack, which exposes a critical vulnerability in SEDORE with the identical threat model. To mitigate this, we introduce the concept of verifiable delegatable order-revealing encryption (VDORE), along with a formal definition of token unforgeability. Building on this, we design a new scheme, Token Unforgeable DORE ($\mathsf{TUDORE}$), which ensures token unforgeability.
Moreover, $\mathsf{TUDORE}$ achieves 1.5× faster token generation than SEDORE with enhanced security.
Batch Decryption without Epochs and its Application to Encrypted Mempools
Suppose Alice holds a secret key $\mathsf{sk}$ in a public key encryption scheme. For a given set of ciphertexts, Alice wants to create a short pre-decryption key that lets anyone decrypt this exact set of ciphertexts and nothing else. This problem is called batch decryption. When the secret key $\mathsf{sk}$ is shared among a number of decryption parties the problem is called batch threshold decryption. 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 threshold decryption with some limitations.
In this work, we construct three new batch decryption and batch threshold decryption schemes. We first observe that a key-policy ABE (KP-ABE) scheme directly gives a batch decryption scheme. However, the best KP-ABE schemes, which happen to be lattice-based, lead to relatively long public keys and ciphertexts. We then use very different techniques to construct a new lattice-based batch decryption scheme with shorter parameters. Our construction employs a recent preimage sampler due to Waters, Wee, and Wu. Finally, for completeness, we show that a trilinear map leads to a highly efficient threshold batch decryption scheme.
QuickPool: Privacy-Preserving Ride-Sharing Service
Online ride-sharing services (RSS) have become very popular owing to increased awareness of environmental concerns and also as a response to increased traffic congestion. To request a ride, users submit their locations and route information for ride matching to a service provider (SP), leading to possible privacy concerns caused by leakage of users' location data. We propose QuickPool, an efficient SP-aided RSS solution for oblivious rider-driver matching, without involving any auxiliary server. Our solution provides simultaneous multiple matching which, to the best of our knowledge, is the first one to do so. End-users, namely, riders and drivers share their route information with SP as encryptions of the ordered set of points-of-interest (PoI) of their route from their start to end locations. SP performs a zone based oblivious matching of drivers and riders, based on partial route overlap as well as proximity of start and end points. QuickPool is in the semi-honest setting, and makes use of secure multi-party computation. We provide security proof of our protocol, perform extensive testing of our implementation and show that our protocol simultaneously matches multiple drivers and riders very efficiently. We compare the performance of QuickPool with state-of-the-art works and observe a run time improvement of 1.7 - 2.2x, and communication improvement of at least 8x.
Tree PCPs
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 the 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 $poly(s,\log(t))$ bits, and the number of queries made by the verifier to the overall proof is $poly(s) \cdot t^\epsilon$, for an arbitrary constant $\epsilon > 0$.
Tree PCPs are well-suited to proving correctness of ongoing computation that unfolds over time. They may be thought of as an information-theoretic analog of the cryptographic notion of incrementally verifiable computation (Valiant, TCC'08). In the random oracle model, tree PCPs can be compiled to realize a variant of incrementally verifiable computation where the prover is allowed a small number of queries to a large evolving state. This yields the first construction of (a natural variant of) IVC in the random oracle model.
Dynamic-FROST: Schnorr Threshold Signatures with a Flexible Committee
Threshold signatures enable any subgroup of predefined cardinality $t$ out of a committee of $n$ participants to generate a valid, aggregated signature.
Although several $(t,n)$-threshold signature schemes exist, most of them assume that the threshold $t$ and the set of participants do not change over time.
Practical applications of threshold signatures might benefit from the possibility of updating the threshold or the committee of participants. Examples of such applications are consensus algorithms and blockchain wallets.
In this paper, we present Dynamic-FROST (D-FROST, for short) that combines FROST, a Schnorr threshold signature scheme, with CHURP, a dynamic proactive secret sharing scheme. The resulting protocol is the first Schnorr threshold signature scheme that accommodates changes in both the committee and the threshold value without relying on a trusted third party.
Besides detailing the protocol, we present a proof of its security: as the original signing scheme, D-FROST preserves the property of Existential Unforgeability under Chosen-Message Attack.
Black Box to Blueprint: Visualizing Leakage Propagation in Deep Learning Models for SCA
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.
UNIDLE: A Unified Framework for Deep Learning-based Side-channel Analysis
Side-channel analysis (SCA) exploits the dependency of a cryptographic device's power consumption or electromagnetic (EM) emissions on the data being processed to extract secret keys. While deep learning (DL) has advanced SCA, most existing models struggle to scale to long traces and tend to be effective only against specific countermeasures. Therefore, their applicability is limited in implementations that employ multiple countermeasures simultaneously.
This paper introduces UNIDLE, a UNIfied framework for Deep LEarning-based SCA, for building scalable and robust models for long traces. UNIDLE employs a hierarchical divide-and-conquer strategy: it segments each trace into smaller parts, which are independently processed by base models, and then aggregates their outputs using a top-level model. This approach enables efficient information extraction from long traces while making the model robust against combinations of masking and desynchronization-based countermeasures. UNIDLE also naturally supports multi-task learning, a useful DL approach for attacking countermeasures such as shuffling, while being less susceptible to the capacity bottlenecks observed in existing multi-task models.
Leveraging this framework, we develop HierNet, a novel DL model that integrates a shift-invariant base model and a transformer-based top-level model. HierNet demonstrates strong empirical performance across three datasets of masked implementations, reaching the guessing entropy 1 with fewer than 50 attack traces--where several state-of-the-art benchmark models fail even with up to 5K attack traces. Experiments on traces protected by shuffling show that HierNet can reach the guessing entropy 1 using 95% fewer attack traces than a state-of-the-art multi-task benchmark while requiring only one-tenth of the model size.
The Weighted Sum Correlation Analysis
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.
An Automated Model to Search For Differential Meet-In-The-Middle Attack: Applications to AndRX Ciphers
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.
Beyond Side-Channels: Evaluating Inner Product Masking Against SIFA
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.
Security of Fixed-Weight Repetitions of Special-Sound Multi-Round Interactive Proofs
Interactive proofs are a cornerstone of modern cryptography and, as such, used in many areas, from digital signatures to multi-party computation. Often the knowledge error $\kappa$ of an interactive proof is not small enough and thus needs to be reduced. This is usually achieved by repeating the interactive proof in parallel $t$ times.
Recently, it was shown that the $t$-fold parallel repetition of any $(k_1,\ldots,k_{\mu})$-special-sound multi-round public-coin interactive proof reduces the knowledge error from $\kappa$ to $\kappa^t$, which is optimal.
However, parallel repetitions lead to an increase in transcript size. A common technique to mitigate this drawback, which is often employed in digital signatures obtained by using the Fiat-Shamir transform, is to use fixed-weight challenges, i.e. vectors of challenges having a constant number of entries (for which the last component is) equal to a fixed value.
While widely used, this method has not been fully assessed from a security standpoint. In particular, the effect of the technique on the knowledge error of repeated interactive proofs has remained unstudied.
In this work, we fill the gap and prove that a fixed-weight repetition of a $(k_1,\ldots,k_{\mu})$-special-sound multi-round public-coin interactive proof
is still knowledge sound. We provide an explicit bound for the knowledge error of the protocol, proving that it matches the maximum cheating probability of a dishonest prover.
Our results apply to some recently-proposed digital signatures which are supposed to be quantum resistant, for example the code-based signature CROSS.
Fully Secure Searchable Encryption from PRFs, Pairings, and Lattices
Searchable encryption is a cryptographic primitive that allows us to perform searches on encrypted data. Searchable encryption schemes require that ciphertexts do not leak information about keywords. However, most of the existing schemes do not achieve the security notion that trapdoors do not leak information. Shen et al. (TCC 2009) proposed a security notion called full security, which includes both ciphertext privacy and trapdoor privacy, but there are few fully secure constructions. Full security is defined for the secret key settings since it is known that public key schemes cannot achieve the trapdoor privacy in principle.
In this paper, we construct a query-bounded fully secure scheme from pseudorandom functions. In addition, we propose three types of efficient (unbounded) fully secure schemes. One of them is based on bilinear groups, and the others are besed on lattices. We then analyze the existing constructions. We then analyze the existing constructions. First, we simplify the Cheng et al. scheme (Information Sciences 2023) and prove its security. This scheme had not been proved to be secure. Second, we show that the Li-Boyen pairing-based scheme (IACR CiC 2024) does not achieve the trapdoor privacy, not as claimed.
Field-Tested Authentication for Quantum Key Distribution and DoS Attacks
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.
A Generalized Approach to Root-based Attacks against PLWE
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.
Multi-Key Fully Homomorphic Encryption: removing noise flooding in distributed decryption via the smudging lemma on discrete Gaussian distribution
The current Multi-key Fully Homomorphic Encryption (MKFHE) needs to add exponential noise in the distributed decryption phase to ensure the simulatability of partial decryption. Such a large noise causes the ciphertext modulus of the scheme to increase exponentially compared to the Single-key Fully Homomorphic Encryption (FHE), further reducing the efficiency of the scheme and making the hardness problem on the lattice on which the scheme relies have a sub-exponential approximation factor $\widetilde{O}(n\cdot2^{\sqrt{nL}})$ (which means that the security of the scheme is reduced). To address this problem, this paper analyzes in detail the noise in partial decryption of the MKFHE based on the LWE problem. It points out that this part of the noise is composed of private key and the noise in initial ciphertext. Therefore, as long as the encryption scheme is leak-resistant and the noise in partial decryption is independent of the noise in the initial ciphertext, the semantic security of the ciphertext can be guaranteed. In order to make the noise in the initial ciphertext independent of the noise in the partial decryption, this paper proves the smudging lemma on discrete Gaussian distribution and achieves this goal by multiplying the initial ciphertext by a ``dummy" ciphertext with a plaintext of 1. Based on the above method, this paper removes the exponential noise in the distributed decryption phase for the first time and reduces the ciphertext modulus of MKFHE from $2^{\omega(\lambda L \log \lambda)}$ to $2^{O(\lambda+L)}$ as the same level as the FHE.
Foundations of Single-Decryptor Encryption
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.
SoK: Signatures With Randomizable Keys
Digital signature schemes with specific properties have recently seen various real-world applications with a strong emphasis on privacy-enhancing technologies. They have been extensively used to develop anonymous credentials schemes and to achieve an even more comprehensive range of functionalities in the decentralized web.
Substantial work has been done to formalize different types of signatures where an allowable set of transformations can be applied to message-signature pairs to obtain new related pairs. Most of the previous work focused on transformations with respect to the message being signed, but little has been done to study what happens when transformations apply to the signing keys. A first attempt to thoroughly formalize such aspects was carried by Derler and Slamanig (ePrint'16, Designs, Codes and Cryptography'19), followed by the more recent efforts by Backes et al. (ASIACRYPT'18) and Eaton et al. (ePrint'23). However, the literature on the topic is vast and different terminology is used across contributions, which makes it difficult to compare related works and understand the range of applications covered by a given construction.
In this work, we present a unified view of signatures with randomizable keys and revisit their security properties. We focus on state-of-the-art constructions and related applications,identifying existing challenges. Our systematization allows us to highlight gaps, open questions and directions for future research on signatures with randomizable keys.
On Round-Optimal Computational VSS
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.