Traditional Secure Multi-Party Computation (MPC) requires parties to stay online through the whole computation, which compromises scalability when dealing with large-scale and complex tasks. The notion of fluid MPC, introduced by Choudhuri et al. (Crypto 2021), aims to address this challenge by presenting a dynamic participation model where parties have the flexibility to join and leave as needed. The best-known honest-majority MPC protocol by Bienstock et al. (Crypto 2023) in the fluid setting achieves linear communication complexity, but still incurs a substantially higher communication overhead than MPC in the classical setting. In this paper, we present two concretely efficient fluid MPC protocols in the honest-majority setting. The first, Velora, is an unconditionally secure maximal-fluid MPC protocol, which achieves the lowest communication cost among maximally fluid MPC protocols by introducing a new approach of transferring the output sharings held by the current committee to the next committee. To eliminate the inherent overhead of Velora, we also propose a separation-generation approach for random double sharings and integrate it into the second protocol as Ion. As a trade-off, Ion relaxes the fluidity requirement to the submaximal fluidity, allowing an extra internal communication round for each committee. Both protocols Velora and Ion enable us to extend the ATLAS technique from the classical setting to the fluid setting for further lowering communication overhead. Compared to the best-known fluid MPC protocol, our protocols reduce the communication cost per multiplication gate by a factor of 5.4 ∼ 7.5× (resp., 20.7 ∼ 28×) for semi-honest security (resp., malicious security). Compared to the state-of-the-art ATLAS protocol by Goyal et al. (Crypto 2021) in the classical setting, our semi-honest protocols only introduce a 1 ∼ 1.5× larger communication overhead for securely computing multiplication gates.

In this paper, we specifically review Xu et al.’s quantum blind signature scheme for distributed e-voting systems, which primarily focuses on simulating real-life e-voting. The scheme aims to ensure voter anonymity in an e-voting system. However, we found that it not only suffers from identity impersonation attacks but also lacks the blindness property essential to a blind quantum signature. To address these shortcomings, we propose a new quantum blind signature scheme that leverages quantum mechanical properties and a one-way hash function. Considering that a voting scheme naturally involves an election committee member blindly signing a ballot embedded with the name of the selected candidate, we use our quantum blind signature as the foundation to design a quantum voting system. This system effectively prevents the repudiation and counterfeiting issues present in Xu et al.’s scheme. Additionally, we provide relevant security analyses to support our theoretical framework. The results demonstrate that our scheme outperforms existing literature not only in terms of e-voting security properties—such as undeniability, anonymity, and untraceability—but also in conceptual simplicity and computational efficiency.

Quantum security most commonly encompasses only offline passive quantum attacks, where a quantum computer is used by an adversary to solve some computationally hard problem, e.g. factoring or discrete logarithm. However, we are witnessing major efforts for the development and deployment of quantum communication networks, and in this environment, cryptographic protocols may also be implemented in quantum devices. In this new setting, a wider range of online active attacks may become possible, for example against targets that may, either deliberately or inadvertently, run a cryptographic scheme in superposition. In this work, we demonstrate that authentication protocols whose security is based on the difficulty of learning linear functions subject to errors may be vulnerable to attacks where adversaries can make queries in superposition — that is, under the so-called “Q2” adversarial model. We do so by describing superposition attacks against a family of symmetric-key authentication protocols based on the LPN problem, a post-quantum cryptography assumption. Our attacks against the HB+ and HB# protocols, both of which have classical proofs of security against active attacks, are based on the Bernstein-Vazirani algorithm, and can efficiently recover the secret key. Despite being conceptually simple, we suggest that our attack techniques might be extended and adapted to also allow for superposition attacks against some modern lattice-based identification and post-quantum signature schemes.

The problem of finding a minimal circuit to implement a given function is one of the oldest in electronics. It is known to be NP-hard. Still, many tools exist to find sub-optimal circuits to implement a function. In electronics, such tools are known as synthesisers. However, these synthesisers aim to implement very large functions (a whole electronic chip). In cryptography, the focus is on small functions, hence the necessity for new dedicated tools for small functions. Several tools exist to implement small functions. They differ by their algorithmic approach (some are based on Depth-First-Search as introduced by Ullrich in 2011, some are based on SAT-solvers like the tool desgined by Stoffelen in 2016, some non-generic tools use subfield decomposition) and by their optimisation criteria (some optimise for circuit size, others for circuit depth, and some for side-channel-protected implementations). However, these tools are limited to functions operating on less than 5 bits, sometimes 6 bits for quadratic functions, or to very simple functions. The limitation lies in a high computing time. We propose a new tool to implement quadratic functions up to 9 bits within AND-depth 1, minimising the number of AND gates. This tool is more time-efficient than previous ones, allowing to explore larger implementations than others on 6 bits or less and allows to reach larger sizes, up to 9 bits.

Achieving (at least) a worst-case correctness error is essential for an underlying public-key encryption (PKE) scheme to which the Fujisaki-Okamoto (FO) transformation is applied. There are three average-case to worst-case (ACWC) transformations—denoted as $\mathsf{ACWC}_{0}$, $\mathsf{ACWC}_{1}$ (PKC 2023), and $\mathsf{ACWC}_{2}$ (TIFS 2023)-which generically convert a PKE scheme with an average-case correctness error into one with a worst-case correctness error. However, in these ACWC transformations the $\gamma$-spreadness, a critical factor in determining explicit rejection ($\mathsf{FO}^{\perp}$) or implicit rejection ($\mathsf{FO}^{\not\perp}$), has not been established with rigorous proofs. Existing analyses of $\gamma$-spreadness lack rigorous proofs, include analytical flaws, or fail to achieve the tightest possible bounds. In this work, we reprove the $\gamma$-spreadness of ACWC-transformed PKE schemes by leveraging two key facts: the random oracle is chosen at random and the encoding mechanism used in the ACWC framework is message-hiding. Our new proofs are applied to the previous NTRU-based PKE schemes, called $\mathsf{NTRU}\mbox{-}\mathsf{C}$, $\mathsf{NTRU}\mbox{-}\mathsf{B}$, and $\mathsf{NTRU+}$, giving the corrected $\gamma$-spreadness for those PKE schemes with concrete parameters.

Hashing to elliptic curve groups is a fundamental operation used in many cryptographic applications, including multiset hashing and BLS signatures. With the recent rise of zero-knowledge applications, they are increasingly used in constraint programming settings. For example, multiset hashing enables memory consistency checks in zkVMs, while BLS signatures are used in proof of stake protocols. In such cases, it becomes critical for hash-to-elliptic-curve-group constructions to be constraint-friendly such that one can efficiently generate succinct proofs of correctness. However, existing constructions rely on cryptographic hash functions that are expensive to represent in arithmetic constraint systems, resulting in high proving costs. We propose a constraint-efficient alternative: a map-to-elliptic-curve-group relation that bypasses the need for cryptographic hash functions and can serve as a drop-in replacement for hash-to-curve constructions in practical settings, including the aforementioned applications. Our relation naturally supports non-deterministic map-to-curve choices making them more efficient in constraint programming frameworks and enabling efficient integration into zero-knowledge proofs. We formally analyze the security of our approach in the elliptic curve generic group model (EC-GGM). Our implementation in Noir/Barretenberg demonstrates the efficiency of our construction in constraint programming: it achieves over $23\times$ fewer constraints than the best hash-to-elliptic-curve-group alternatives, and, enables $50$-$100\times$ faster proving times at scale.

Multiple authentication solutions are widely deployed, such as OTP/TOTP/HOTP codes, hardware tokens, PINs, or biometrics. However, in practice, one sometimes needs to authenticate not only the user but also their location. The current state-of-the-art secure localisation schemes are either unreliable or insecure, or require additional hardware to reliably prove the user's location. This paper proposes CARPOOL, a novel, secure, and reliable approach to affirm the location of the user by solely relying on location-bounded interactions with commercial off-the-shelf devices. Our solution does not require any additional hardware, leverages devices already present in a given environment, and can be integrated effortlessly with existing security components, such as identity and access control systems. To demonstrate the feasibility of our work and to show that it can be deployed in a realistic closed environment setting, we implemented a proof of concept realisation of CARPOOL on an Android phone and multiple Raspberry Pi boards and integrated CARPOOL with Amazon Web Services (AWS) Cognito.

We give a public key encryption scheme that is provably secure against poly-size adversaries, assuming $n^{\log^\alpha n}$ hardness of the standard planted clique conjecture, for any $\alpha \in (0,1)$, and a relatively mild hardness conjecture about noisy $k\mbox{-}\mathsf{LIN}$ over expanders that is not known to imply public-key encryption on its own. Both of our conjectures correspond to natural average-case variants of NP-complete problems and have been studied for multiple decades, with unconditional lower bounds supporting them in a variety of restricted models of computation. Our encryption scheme answers an open question in a seminal work by Applebaum, Barak, and Wigderson [STOC'10].

SNARKs enable compact proofs that an NP statement is true and that the prover knows a valid witness. They have become a key building block in modern smart contract applications, including rollups and privacy-focused cryptocurrencies. In the widely used Groth16 framework, however, long statements incur high costs. A common workaround is to pass the statement’s hash to the SNARK and move the statement into the witness. The smart contract then hashes the statement first, and the circuit that is proven additionally checks consistency of the hash and the statement. Unfortunately, virtually any hash function is expensive to call either in a smart contract (in terms of gas) or in the proven circuit (in terms of prover time). We demonstrate a novel solution to this dilemma, which we call hybrid compression. Our method allows us to use two different hash functions—one optimized for the proof circuit, and another optimized for on-chain verification—thereby combining the efficiency advantages of both. We define a clean and simple security property of the two hash functions to which our security reduces in the standard model, namely, joint UHF hardness. We then show the plausibility of this assumption in the random oracle model. Our benchmarks show that it achieves near-optimal performance in both gas usage and prover time. As an example, compressing an 8 KB statement with our approach results in a 10-second prover time and a smart contract spending 270K gas, whereas the existing approaches either need a much longer proof generation (290 seconds for SHA-256 hashing) or a much more expensive contract (5M gas for Poseidon hashing). Along the way, we develop a two-party protocol of independent interest in communication complexity: an efficient deterministic method for checking input equality when the two parties do not share the same hash function.

The threshold secret sharing scheme enables a dealer to distribute the share to every participant such that the secret is correctly recovered from a certain amount of shares. The traditional $(k, n)$ threshold secret sharing scheme requires that the number of participants $n$ is known in advance. In contrast, the evolving secret sharing scheme allows that $n$ can be uncertain and even ever-growing. In this paper, we consider the evolving secret sharing scenario. Based on the prefix codes, we propose a brand-new construction of evolving $k$-threshold secret sharing scheme for an $\ell$-bit secret over a polynomial ring, with correctness and perfect security. The proposed scheme is the first evolving $k$-threshold secret sharing scheme by generalizing Shamir's scheme onto a polynomial ring. Besides, the proposed scheme also establishes the connection between prefix codes and the evolving schemes for $k\geq2$. The analysis shows that the size of the $t$-th share is $(k-1)(\ell_t-1)+\ell$ bits, where $\ell_t$ denotes the length of a binary prefix code of encoding integer $t$. In particular, when $\delta$ code is chosen as the prefix code, the share size is $(k-1)\lfloor\lg t\rfloor+2(k-1)\lfloor\lg ({\lfloor\lg t\rfloor+1}) \rfloor+\ell$, which improves the prior best result $(k-1)\lg t+6k^4\ell\lg{\lg t}\cdot\lg{\lg {\lg t}}+ 7k^4\ell\lg k$, where $\lg$ denotes the binary logarithm. Specifically, when $k=2$, the proposal also provides a unified mathematical decryption for prior evolving $2$-threshold secret sharing schemes and also achieves the minimal share size for a single-bit secret, which is the same as the best-known scheme.

Motivated by LowMC cryptanalysis challenge, research in recent years focuses more on attacking LowMC in \PICNIC application setting, \ie an attacker can see only a single plaintext/ciphertext pair. It can be noted that in the security proof of \PICNIC, LowMC is required to be secure under two plaintexts, it is thus meaningful to investigate the security of LowMC in this direction. Pioneered by Liu, Isobe and Meier at Crypto 2021, they combined algebraic techniques with difference enumeration attack, which could attack all three 4-round LowMC instances adopting full S-Box layers in \PICNIC with only two chosen plaintexts. However, the research on cryptanalysis of LowMC using two plaintext/ciphertext pairs is yet far from complete. Previous works using a single known plaintext are better than those with two plaintexts in terms of attack complexity or attacked rounds when considering a comparable success probability. In this paper, to address such counter-intuitive gaps between existing attacks on LowMC with full S-box layers using a single and two plaintext/ciphertext pairs, we first develop an algebraic key-derived attack framework, where an algebraic property of the key-derived difference is utilized to build an equation system with lower algebraic degree. This directly contributes to less cost for solving equation system and naturally works under known-plaintext setting, which can be further enhanced with chosen-plaintext attack setting. We then present an improved difference enumeration attack framework. Instead of enumerating all possible differences in the second round, variables for part of S-boxes in the second and third rounds are introduced to derive cubic equations, which will lead to fewer variables for the last round. Finally, applying our new attack frameworks to LowMC, we propose \text{8-round} attacks on LowMC for the very first time, which remain under known-plaintext setting. Moreover, we give the first attacks on three LowMC instances, \ie 129-bit block size of 6 rounds and 129-/192-bit block size of 7 rounds, which cannot be obtained using previous attacking methods. Also, previous attacks on LowMC from 4 to 7 rounds could be improved for almost all three LowMC instances in this paper. All these results, we believe, could be a positive answer that given one more pair, more information indeed can be gained to improve attacks on LowMC when compared to those using only a single plaintext. As well as our newly proposed algebraic key-derived attack framework, we hope that, could provide more insights into the cryptanalysis of LowMC with low allowable data complexity.

We consider the question of whether worst-case hardness of the time-bounded Kolmogorov complexity problem, $\KpolyA$---that is, determining whether a string is time-bounded Kolmogorov random ($K^t$-random) or not---suffices to imply the existence of one-way functions (OWF). Roughly speaking, our main result shows that under a natural strengthening of standard-type derandomization assumptions, worst-case hardness of the \emph{boundary} version of this classic problem characterizes OWFs. In more detail, let $\bKtA$ denote the problem of, given an instance $x$, deciding whether (a) $K^{t_2}(x)\geq n-1$, or (b) $K^{t_1}(x) < n-1$ \emph{but} $K^{t_2}> n - \log n$; that is, deciding whether $x$ is $K^t$-random, or just ``near" $K^t$-random. We say that $\bKpolyA \notin \ioBPP$ if $\bKpolyA \notin \ioBPP$ for all polynomials $t_1,t_2$. We show that under a natural strengthening of standard derandomization assumptions (namely, there exists a constant $\varepsilon > 0$ such that $\E \not\subseteq {\sf ioNTIME}[2^{kn}] \slash 2^{\varepsilon n}$ for every $k \in \N$), OWF exist iff $\bKpolyA \notin \ioBPP$. Along the way, we also demonstrate that if we consider the probabilistic version of Kolmogorov complexity (referred to as $pK^t$) instead, then the characterization holds unconditionally. We finally observe that for most standard optimization problems, hardness ``along boundary" is equivalent to ``plain" worst-case hardness, indicating that assuming hardness along the boundary may be WLOG.

Plaintext-checking oracle (PCO) attacks are among the most prominent types of attacks against NIST's recently standardized ML-KEM. Previous works have drastically reduced the number of queries needed to recover the secret key. Although this number is now close to the information-theoretic bound, current attacks have not yet been adapted to settings with increased noise and highly imperfect oracles. In attacks targeting real-world protected implementations, noisy leakage may lead to oracles that only provide a small advantage over guessing. This work shows how to efficiently exploit imperfect oracles arising from highly noisy side channels. We present several soft-analytic techniques that enable highly noise-tolerant parallel PCO attacks. These techniques allow for successful attacks in relatively few traces from information that gives just a slight advantage over guessing. Additionally, we extend the generic framework for side-channel information from Eurocrypt 2025 and thereby relate our techniques to previous work. We then discuss several oracle instantiations that are based on the noisy Hamming weight model. These oracles rely on widely accepted assumptions, are easy to simulate, and allow for fair comparisons between different attacks. Furthermore, they allow taking countermeasures into account, and we evaluate the impact of masking. Our evaluations in these and previous models show that PCO attacks are noise-tolerant on an entirely different scale compared to previous work. These improvements are of an algorithmic nature and orthogonal to the fact that the Fujisaki-Okamoto transform in ML-KEM offers a large attack surface. Finally, we discuss the implications of our findings for protected ML-KEM implementations.

We prove that $4r + 4$ rounds of an AES variant with independent and uniform random round keys are $\varepsilon$-close to pairwise independent with $\varepsilon = 2^{14}\, 2^{-39r}$. This result follows from a near-optimal bound for a two-norm version of pairwise independence for the Shark construction, depending on the third singular value of the difference-distribution table of the S-boxes. Our analysis combines insights from cryptanalysis — in particular, truncated differentials — and linear algebra over the reals.

Symmetric cryptography is confronting threats posed by quantum computing, including Grover's search algorithm and Simon's algorithm. In the fault-tolerant quantum computation, the limited qubit count, connectivity constraints, and error rates of quantum hardware impose stringent requirements on the implementation of cryptographic quantum circuits. Constructing low-resource quantum circuit models forms the foundation for evaluating algorithmic resistance to quantum threats. At CRYPTO 2019, Jaques et al. justified the adoption of depth-times-width cost (DW-cost) as a metric for quantum circuits by incorporating advancements in quantum computation and error correction. In this work, we address the fundamental limitations in in-place implementations of AES quantum circuits by proposing a set of in-place synthesis methods centered on DW-cost optimization. First, we prove that within the composite field arithmetic framework, intermediate circuit states can be utilized to uncompute S-box input states, and introduce a novel design pathway and circuit structure for in-place S-box quantum circuits. Second, we establish the necessary conditions for maximizing parallelization of Toffoli gates under minimal-width constraints in binary field multiplication. Through co-design and optimization of multiple nonlinear components, we construct a compact in-place S-box with a DW-cost of merely 276. Finally, building on this, we achieve quantum circuit implementations for AES-128, AES-192, and AES-256 via co-optimization of key expansion and round functions, reducing their DW-cost values to 65,280, 87,552, and 112,896 respectively. These results indicate a reduction of at least 46%, 45%, and 45% compared to existing state-of-the-art solutions. This study establishes new technical benchmarks for low-resource fault-tolerant implementations of symmetric cryptography in the post-quantum era. (This is a revised version containing Clifford+T resource estimates for both AES-128 Grover oracle and encryption oracle. Key revisions are highlighted in red.)

The efficiency of circuit implementations for cryptographic algorithms is crucial for their practical deployment. The implementation cost of the linear layer can be evaluated by the number of XOR operations, typically measured in generalized XOR (g-\xor) and serial XOR (s-XOR). Finding the minimal sequence of g-XOR operations constitutes the Shortest Linear Program (SLP) problem. Existing approaches generally address this problem through a two-stage framework: generating an initial sequence followed by local optimization, both stages essentially solving the SLP problem. The Boyar-Peralta (BP) algorithm serves as a foundational heuristic for addressing the SLP problem and has been extensively adopted in subsequent research; however, its computational inefficiency presents a significant limitation for practical applications, especially in large-scale problems. This paper proposes a novel implementation framework for the BP algorithm based on linear combinations, significantly enhancing its computational efficiency. We further introduce a new strategy for selecting subsequences during local optimization, replacing the random selection strategy employed in previous works. By analyzing the structural properties of the Advanced Encryption Standard (AES) linear layer matrix and applying our proposed methods, we achieve the first implementation requiring only 89 g-XOR operations, improving upon the previous best result of 91 g-XOR operations reported in prior literature.

We show the key ideas of the above-referenced work for lattice Gaussian sampling are not new; the same ideas have been proposed by Ling et al. in 2014.

A homomorphic secret sharing (HSS) scheme allows a client to delegate a computation to a group of untrusted servers while achieving input privacy as long as at least one server is honest. In recent years, many HSS schemes have been constructed that have, in turn, found numerous applications to cryptography. Prior work on HSS focuses on the setting where the servers are semi-honest. In this work we study HSS in the setting of malicious evaluators. We propose the notion of HSS with verifiable evaluation (ve-HSS) that guarantees correctness of output even when all the servers are corrupted. ve-HSS retains all the attractive features of HSS and adds the new feature of succinct public verification of output. We present black-box constructions of ve-HSS by devising generic transformations for semi-honest HSS schemes (with negligible error). This provides a new non-interactive method for verifiable and private outsourcing of computation.

FALCON is a NIST-selected post-quantum digital signature scheme whose performance bottleneck lies in the SamplerZ subroutine for discrete Gaussian sampling. We present a throughput-optimized, custom hardware implementation of SamplerZ that introduces several architectural and algorithmic innovations to significantly accelerate signature generation. Our design incorporates a datapath-aware floating-point arithmetic pipeline that strategically balances latency and resource utilization. Our novel algorithmic innovations include an Estrin's Scheme-based polynomial evaluator and a constant-latency BerExp routine using floating-point exponentiation IP to eliminate fixed-point decomposition critical paths. Additionally, we optimize rejection handling through parallel sampling loops and propose a speed-optimized flooring circuit. These advancements lower the sampling time by 55%-81% and overall FALCON signature generation time by 36%-53% compared to the state-of-the-art FPGA implementation. In a landmark result, our work is the first to demonstrate a Xilinx FPGA SamplerZ design that outperforms state-of-the-art software (by 15%) and ASIC (by 16%) designs, advancing the practical deployment of post-quantum signatures on reconfigurable hardware.

Rekeying is an effective technique for protecting symmetric ciphers against side-channel and key-search attacks. Since its introduction, numerous rekeying schemes have been developed. We introduce Post-Quantum Stateless Auditable Rekeying (PQ-STAR), a novel post-quantum secure stateless rekeying scheme with audit support. PQ-STAR is presented in three variants of increasing security guarantees: (i) Plain PQ-STAR lets an authorized auditor decrypt and verify selected ciphertexts; (ii) Commitment-based PQ-STAR with the additional binding guarantee from the commitments, preventing a malicious sender from potentially claiming a random or wrong session key. (iii) Zero-knowledge PQ-STAR equips each session key with a signature-based zero-knowledge proof (ZKP), which proves that the session key was derived honestly, without ever revealing the secret preimage. We formally prove that all variants achieve key-uniqueness, index-hiding, and forward-secrecy, even if a probabilistic polynomial-time (PPT) adversary arbitrarily learns many past session keys. PQ-STAR provides a formally verified, stateless, and audit-capable rekeying primitive that can be seamlessly integrated as a post-quantum upgrade for existing symmetric-key infrastructures.

Asynchronous byzantine agreement extension studies the message complexity of $L$-bit multivalued asynchronous byzantine agreement given access to a binary asynchronous Byzantine agreement protocol. We prove that asynchronous byzantine agreement extension can be solved with perfect security and optimal resilience in $O(nL+n^2 \log n)$ total communication (in bits) in addition to a single call to a binary asynchronous Byzantine agreement protocol. For $L = O(n \log n)$, this gives an asymptotically optimal protocol, resolving a question that remained open for nearly two decades. List decoding is a fundamental concept in theoretical computer science and cryptography, enabling error correction beyond the unique decoding radius and playing a critical role in constructing robust codes, hardness amplification, and secure cryptographic protocols. A key novelty of our perfectly secure and optimally resilient asynchronous byzantine agreement extension protocol is that it uses list decoding - making a striking new connection between list decoding and asynchronous Byzantine agreement.

SCALES (Small Clients And Larger Ephemeral Servers) (Acharya et al., TCC 2022, CRYPTO 2024) is a recently proposed model for MPC with several attractive features, including resilience to adaptive corruption. Known SCALES constructions, while offering reasonable asymptotics for large-scale MPC, incur high concrete costs both in computation and communication. As our primary contribution, we dramatically improve both asymptotic and concrete costs of SCALES for permutation branching programs (PBP), a well-motivated practical model of computation. We achieve linear cost in program length, input size, and the security parameter. Our instantiations of the building blocks may be of independent interest. Further, we present generic transformations to extend any semi-honestly secure SCALES protocol to achieve (1) guaranteed output delivery in the presence of mixed adversaries (that corrupt servers maliciously and clients semi-honestly) in the all-but-one corruption setting; and (2) protocols for computing general functionalities where each server's computation scales sub-linearly in the function~size.

Construction of efficient and provably-secure (T)PRPs and (fixed/variable input-length) PRFs has been one of the central open problem in modern symmetric-key cryptography. Many Feistel-based constructions has been proposed and analysed to solve this problem. Inspired by some recent works, in this paper, we revisit the problem of constructing provably secure Feistel constructions using permutations as the round functions. More specifically, following the idea of Naor and Reingold, we try to reduce the number of inner permutations used by replacing them with cheap hash functions, without sacrificing optimal security. We affirmatively show that with the use of a suitable hash function along with a four-round Feistel construction, which uses only three independent permutations, one can achieve optimally secure (T)PRPs and PRFs.

Bitcoin is a decentralized, permissionless network for digital payments. Bitcoin also supports a limited set of smart contracts, which restrict how bitcoin can be spent, through bitcoin script. In order to support more expressive scripting functionality, Robin Linus introduced the BitVM family of protocols. These implement a weaker form of ``optimistic" smart contracts, and for the first time allowed bitcoin to verify arbitrary computation. BitVM allows a challenger to publish a ``fraud proof" that the computation was carried out incorrectly which can be verified on chain, even when the entire computation cannot. Jermey Rubin introduced an alternative optimistic smart contract protocol called Delbrag. This protocol uses Garbled Circuits (GC) to replace the BitVM fraud proof with by simply revealing a secret. He also introduced the Grug technique for malicious security. We introduce a new formalization of GC based optimistic techniques called Garbled Locks or Glocks. Much like Delbrag, we use the GC to leak a secret and produce a signature as a fraud proof. We further propose the first concretely practical construction that does not require Grug. Like BitVM2 and Delbrag, Glock25 reduces verification of arbitrary bounded computation to verification of a SNARK. In Glock25, we use a designated verifier version of a modified of the SNARK Pari with smaller proof size. We make Glock25 maliciously secure using a combination of Cut-and-Choose, Verifiable Secret Sharing (VSS), and Adaptor Signatures. These techniques reduce the communication, computational, and on-chain complexity of the protocol compared to other approaches to construct a Glock, e.g. based on Groth16.

Payment channel networks (PCNs) are a promising technology that alleviates blockchain scalability by shifting the transaction load from the blockchain to the PCN. Nevertheless, the network topology has to be carefully designed to maximise the transaction throughput in PCNs. Additionally, users in PCNs also have to make optimal decisions on which transactions to forward and which to reject to prolong the lifetime of their channels. In this work, we consider an input sequence of transactions over $p$ parties. Each transaction consists of a transaction size, source, and target, and can be either accepted or rejected (entailing a cost). The goal is to design a PCN topology among the $p$ cooperating parties, along with the channel capacities, and then output a decision for each transaction in the sequence to minimise the cost of creating and augmenting channels, as well as the cost of rejecting transactions. Our main contribution is an $\mathcal{O}(p)$ approximation algorithm for the problem with $p$ parties. We further show that with some assumptions on the distribution of transactions, we can reduce the approximation ratio to $\mathcal{O}(\sqrt{p})$. We complement our theoretical analysis with an empirical study of our assumptions and approach in the context of the Lightning Network.

Conventional Byzantine fault-tolerant protocols focus on the workflow within a group of nodes. In recent years, many applications of consensus involve communication across groups. Examples include communication between infrastructures running replicated state machine, sharding-based protocols, and cross-chain bridges. Unfortunately, little efforts have been made to model the properties for communication across groups. In this work, we propose a new primitive called cross-consensus reliable broadcast (XRBC). The XRBC primitive models the security properties of communication between two groups, where at least one group executes a consensus protocol. We provide three constructions of XRBC under different assumptions and present three different applications for our XRBC protocols: a cross-shard coordination protocol via a case study of Reticulum (NDSS 2024), a protocol for cross-shard transactions via a case study of Chainspace (NDSS 2018), and a solution for cross-chain bridge. Our evaluation results show that our protocols are highly efficient and benefit different applications. For example, in our case study on Reticulum, our approach achieves 61.16% lower latency than the vanilla approach.

We discuss how Fully Homomorphic Encryption (FHE), and in particular the TFHE scheme, can be used to define an e-voting scheme for the Alternative Vote (AV) election system. This system has a more complex tallying phase than traditional First-Past-The-Post (FPTP) election variants. Previous work on e-voting schemes that used homomorphic encryption has focused on FPTP systems only, and utilized mainly linearly homomorphic encryption. We show, by using FHE, that more complex electoral systems such as AV can also be supported by homomorphic encryption. We show security of our protocol by considering it as a simple MPC functionality, and we also show practicality by presenting some experimental runtimes using the tfhe-rs library.

A Symmetric Key Encryption scheme using Camera Zooming is pre- sented using a familiar Paper-pencil cipher. The Camera can have a mag- nification/scaling up to some integer. The encrypter and decrypter are two hardware systems that are assumed to have the capability to zoom a given image with text from the resolution of a single character to a page by applying an appropriate scaling factor and an appropriate polynomial time zoom algorithm. Using the symmetric key, the Camera or a zooming algorithm implementation repeatedly zooms on different boxes in an im- age filled with cipher text and spurious redundant non-correlated pseudo- random data. Then, it decrypts the cipher using the Merkle-Hellman Knapsack Cryptosystem (MHKC) trapdoor algorithm or variants for ef- ficient encryption/decryption. As shown, the MHKC algorithm’s crypt- analysis vulnerability using Lattice-based LLL and other density attacks would not affect this scheme—as long as the key is private.

Kleptography was first proposed by Adam Young and Moti Yung in 1996, while algorithm substitution attack was introduced by Mi- hir Bellare et al. as a variation of kleptography in 2014 after the Dual EC incident with the confidential documents revelation by Edward Snowden. These two paradigms share a common goal: to enable attackers to embed covert capabilities into cryptographic implementations while maintaining the appearance of normal functionality. The goal of this paper is to con- solidate existing research on kleptographic attacks, integrate it into a uni- fied definition, and explore future directions for the research in this field. This paper begins by introducing and comparing the two major branches of kleptographic attacks: traditional kleptography and post-Snowden al- gorithm substitution attack, highlighting their theoretical distinctions, threat models, and historical development. Then, it analyzes the spe- cific goals that attackers aim to achieve through such subversions and propose a generalized definition of algorithm substitution attack that in- clude all the goals. The paper also presents practical examples framed within my definition and classify prior research works as either strong or weak attacks based on their structure and undetectability. Finally, it discusses the current landscape of research in kleptographic attacks, and then suggest future directions for the attack and defense perspectives.

Making 2-party computation scale up to big datasets is a long-cherished dream of our community. More than a decade ago, a line of work has implemented and optimized interactive RAM-model 2-party computation (2PC), achieving somewhat reasonable concrete performance on large datasets, but unfortunately suffering from $\widetilde{O}(T)$ roundtrips for a $T$-time computation. Garbled RAM promises to compress the number of roundtrips to $2$, and encouragingly, a line of recent work has designed concretely efficient Garbled RAM schemes whose asymptotic communication and computation costs almost match the best known interactive RAM-model 2PC, but still leaves $({\sf poly})\log\log$ gaps. We present ${\sf PicoGRAM}$, a practical garbled RAM (GRAM) scheme that not only asymptotically matches the prior best RAM-model 2PC, but also achieves an order of magnitude concrete improvement in online time relative to interactive RAM-model 2PC, on a dataset of size $8$GB. Moreover, our work also gives the first Garbled RAM whose total cost (including bandwidth and computation) achieves an optimal dependency on the database size (up to an arbitrarily small super-constant factor). Our work shows that for high-value real-life applications such as Signal, blockchains, and Meta that require oblivious accesses to large datasets, Garbled RAM is a promising direction towards eventually removing the trusted hardware assumption that exist in production implementations today. Our open source code is available at https://github.com/picogramimpl/picogram.

Threshold Schnorr signatures enable $t$-out-of-$n$ parties to collaboratively produce signatures that are indistinguishable from standard Schnorr signatures, ensuring compatibility with existing verification systems. While static-secure constructions are well understood and achieve optimal round complexity, obtaining full adaptive security - withstanding up to $t-1$ dynamic corruptions under standard assumptions has proven elusive: Recent impossibility results (CRYPTO’25) either rule out known proof techniques for widely deployed schemes or require speculative assumptions and idealized models, while positive examples achieving full adaptivity from falsifiable assumptions incur higher round complexity (EUROCRYPT’25, CRYPTO’25). We overcome these barriers with the first round-optimal threshold Schnorr signature scheme that, under a slightly relaxed security model, achieves full adaptive security from DDH in the random oracle model. Our model is relaxed in the sense that the adversary may adaptively corrupt parties at any time, but each signer must refresh part of their public key after a fixed number of signing queries. These updates are executed via lightweight, succinct, stateless tokens, preserving the aggregated signature format. Our construction is enabled by a new proof technique, equivocal deterministic nonce derivation, which may be of independent interest.

Threshold decryption schemes allow a group of decryptors, each holding a private key share, to jointly decrypt ciphertexts. Over the years, numerous threshold decryption schemes have been proposed for applications such as secure data storage, internet auctions, and voting, and recently as a tool to protect against miner-extractable value attacks in blockchain. Despite the importance and popularity of threshold decryption, many natural and practical threshold decryption schemes have only been proven secure against static adversaries. In this paper, we present two threshold decryption schemes that withstand malicious adaptive corruption. Our first scheme is based on the standard ElGamal encryption scheme and is secure against chosen plaintext attack~(CPA). Our second scheme, based on the chosen ciphertext attack~(CCA) secure Shoup-Gennaro encryption scheme, is also CCA secure. Both of our schemes have non-interactive decryption protocols and comparable efficiency to their static secure counterparts. Building on the technique introduced by Das and Ren (CRYPTO 2024), our threshold ElGamal decryption scheme relies on the hardness of Decisional Diffie-Hellman and the random oracle model.

The Regular Syndrome Decoding (RSD) problem, introduced nearly two decades ago, is a regular version of the Syndrome Decoding (SD) problem, where the noise vector is divided into consecutive, equally sized blocks, each containing exactly one noisy coordinate. Recently, RSD has gained renewed attention for its applications in Pseudorandom Correlation Generator (PCG) and more. Very recently, several works presented the improved algebraic approach (AGB for short) and ISD approach (including regular-ISD and regular-RP) to utilize the regular structure of noise vectors and provide a more precise security evaluation for the RSD problem. In this paper, we refine the AGB algorithm from a one-round process to a two-round process, and refer to the new algebraic algorithm as AGB 2.0. For each round, we guess a few noise-free positions, followed by a tailored partial XL algorithm. This interleaving strategy increases the probability of success by reducing the number of guessing noise-free positions and effectively lowers the problem's dimension in each round. By fine-tuning position guesses in each round and optimizing the aggregate running time, our AGB 2.0 algorithm reduces the concrete security of the RSD problem by up to $6$ bits for the parameter sets used in prior works, compared to the best-known attack. In particular, for a specific parameter set in Wolverine, the RSD security is $7$ bits below the $128$-bit target. We analyze the asymptotic complexity of algebraic attacks on the RSD problem over a finite field $\mathbb{F}$ with the field size $|\mathbb{F}|>2$, when the noise rate $\rho$ and code rate $R$ satisfy $\rho + R < 1$. If $n \rho R^2 = O(1)$ where $n$ is the noise length, the RSD problem over $\mathbb{F}$ can be solved in polynomial time, but it does not hold for the SD problem. We show that the ISD and its variants, including regular-ISD and regular-RP, are asymptotically less efficient than AGB for solving RSD problems with $R = o(1/\log(n))$ and $|\mathbb{F}| > e^{n\rho R}$.

The industry is moving away from passwords for authentication and authorization, with hardware devices for storing long-term cryptographic keys emerging as the leading alternative. However, these devices often have limited displays and remain vulnerable to theft, malware, or tricking users into signing malicious payloads. Current systems provide little fallback security in such cases. Any solution must also meet strict requirements: compatibility with industry standards, scalability to handle high request volumes, and high availability. We present a novel design for authentication and authorization that meets these demands. Our approach virtualizes the authenticating/authorizing party via a two-party signing protocol with a helper entity, ensuring that keys remain secure even if a device is compromised and that every signed message conforms to a security policy. We formalize the required properties for such protocols and show how they are met by existing schemes (e.g., FROST for Schnorr, Boneh–Haitner–Lindell-Segev'25 for ECDSA). Motivated by the widespread use of ECDSA (FIDO2/Passkeys, blockchains), we introduce a new, optimized two-party ECDSA protocol that is significantly more efficient than prior work. At its core is a new variant of exponent-VRF, improving on earlier constructions and of independent interest. We validate our design with a proof-of-concept virtual authenticator for the FIDO2 Passkeys framework.

An Authenticated Key Encapsulation Mechanism (AKEM) combines public-key encryption and digital signatures to provide confidentiality and authenticity. AKEMs build the core of Hybrid Public Key Encryption (RFC 9180) and serve as a useful abstraction for messaging applications like the Messaging Layer Security (MLS) protocol (RFC 9420) and Signal's X3DH protocol. To date, most existing AKEM constructions either rely on classical (non post-quantum) assumptions or on unoptimized black-box approaches leading to suboptimal efficiency. In this work, we choose a different abstraction level to combine KEMs and identification schemes more efficiently by leveraging randomness reuse. We construct a generic scheme and identify the necessary security requirements on the underlying KEM and identification scheme when reusing parts of their randomness. This allows for a concrete instantiation from isogenies based on the POKÉ KEM (EUROCRYPT'25) and the SQIsignHD identification scheme (EUROCRYPT'24). To be used in our black-box construction, the identification scheme requires the more advanced security property of response non-malleability. Hence, we further show that a slight modification of SQIsignHD satisfies this notion, which might be of independent interest. Putting everything together, our final scheme yields the most compact AKEM from PQ assumptions with public keys of 366 bytes and ciphertexts of 216 bytes while fulfilling the strongest confidentiality and authenticity notions.

The sumcheck protocol is a fundamental building block in the design of probabilistic proof systems, and has become a key component of recent work on efficient succinct arguments. We study time-space tradeoffs for the prover of the sumcheck protocol in the streaming model, and provide upper and lower bounds that tightly characterize the efficiency achievable by the prover. $\bullet{}$ For sumcheck claims about a single multilinear polynomial we demonstrate an algorithm that runs in time $O(kN)$ and uses space $O(N^{1/k})$ for any $k \geq 1$. For non-adaptive provers (a class which contains all known sumcheck prover algorithms) we show that this tradeoff is optimal. $\bullet{}$ For sumcheck claims about products of multilinear polynomials, we describe a prover algorithm that runs in time $O(N(\log \log N + k))$ and uses space $O(N^{1/k})$ for any $k \geq 1$. We show that, conditioned on the hardness of a natural problem about multiplication of multilinear polynomials, any ``natural'' prover algorithm that uses space $O(N^{1/2 - \varepsilon})$ for some $\varepsilon > 0$ must run in time $\Omega(N(\log \log N + \log \varepsilon))$. We implement and evaluate the prover algorithm for products of multilinear polynomials. We show that our algorithm consumes up to $120\times$ less memory compare to the linear-time prover algorithm, while incurring a time overhead of less than $2\times$. The foregoing algorithms and lower bounds apply in the interactive proof model. We show that in the polynomial interactive oracle proof model one can in fact design a new protocol that achieves a better time-space tradeoff of $O(N^{1/k})$ space and $O(N(\log^* N + k))$ time for any $k \geq 1$.

The Module Learning With Errors (M-LWE) problem has become a fundamental hardness assumption for lattice-based cryptography. It offers an attractive trade-off between strong robustness guarantees, sometimes directly based on worst-case lattice problems, and efficiency of the subsequent cryptographic primitives. Different flavors of M-LWE have then been introduced towards improving performance. Such variants look at different secret-error distributions and might allow for additional hints on the secret-error vector. Existing hardness results however only cover restricted classes of said distributions, or are tailored to specific leakage models. This lack of generality hinders the design of efficient and versatile cryptographic schemes, as each new distribution or leakage model requires a separate and nontrivial hardness evaluation. In this work, we address this limitation by establishing the hardness of MLWE under general distributions. As a first step, we show that MLWE remains hard when the error vector follows an arbitrary bounded distribution with sufficient entropy, with some restriction on the number of samples. Building on this, we then reduce to the Hermite Normal Form (HNF) where the secret-error vector follows said arbitrary distribution. Overall, our result shows the actual shape of the distribution does not matter, as long as it keeps sufficient entropy. To demonstrate the versatility of our framework, we further analyze a range of leakage scenarios. By examining the residual entropy given the leakage, we show that our results of M-LWE with general distributions encompass various types of leakage. More precisely, we cover exact and approximate linear hints which are widely used in recent cryptographic designs, as well as quadratic, and even non-algebraic forms, some of which were not yet covered by any theoretical hardness guarantees. The generality of our results aims at facilitating future cryptographic designs and security analyses.

In this article, we introduce a new post-quantum cryptosystem, NTWR Prime, which is based on the NTRU Prime and Learning With Rounding (LWR) problems. This scheme is inspired by the NTWE construction proposed by Joel Gartner in 2023. Unlike NTWE, our algorithm employs an irreducible, non-cyclotomic polynomial whose Galois group is isomorphic to the symmetric group. Additionally, the LWR problem is used in place of the LWE problem, offering potential advantages for structural security due to its deterministic nature. We conduct a security analysis demonstrating that solving the NTWR Prime problem requires solving both the underlying NTRU Prime and LWR problems. Consequently, given the absence of definitive post-quantum security proofs for these problems, our construction offers redundancy, which may fulfill the requirements of applications with exceptionally high security standards. Importantly, we show that there exists a set of parameters satisfying the hardness assumptions for both contributing problems.

Fuzzy-labeled private set intersection (PSI) outputs the corresponding label if there is a ``fuzzy'' match between two items, for example, when the Hamming distance is low between the two items. Such protocols can be applied in privacy-preserving biometric authentication, proximity testing, and so on. The only fuzzy-labeled PSI protocol designed for practical purposes is by Uzun et al. (USENIX’21), which is based on homomorphic encryption. This design puts constraints on the item size, label size, and communication cost since it is difficult for homomorphic encryption to support large plaintext space and it is well-known that the ciphertext-expansion factor is large. Our construction begins with a new primitive which we call vector ring-oblivious linear evaluation (vector ring-OLE). This primitive does not rely on existing instantiations of ring-OLE over the quotient ring, but leverages the more efficient vector-OLE. It is ideal for building unbalanced threshold-labeled PSI and is also of independent interest. Our main contribution, fuzzy-labeled PSI, is bootstrapped from our threshold-labeled PSI protocol. Through a prototype implementation, we demonstrate our communication cost is up to $4.6\times$ better than the prior state-of-the-art with comparable end-to-end latency while supporting a significantly higher label size.

The $k$LIN problem concerns solving noisy systems of random sparse linear equations mod 2. It gives rise to natural candidate hard CSP distributions and is a cornerstone of local cryptography. Recently, it was used in advanced cryptographic constructions, under the name 'sparse LPN'. For constant sparsity $k$ and inverse polynomial noise rate, both search and decision versions of $k$LIN are statistically possible and conjectured to be computationally hard for $n\ll m\ll n^{k/2}$, where $m$ is the number of $k$-sparse linear equations, and $n$ is the number of variables. We show an algorithm that given access to a distinguisher for $(k-1)$LIN with $m$ samples, solves search $k$LIN with roughly $O(nm)$ samples. Previously, it was only known how to reduce from search $k$LIN with $O(m^3)$ samples, yielding meaningful guarantees for decision $k$LIN only when $m \ll n^{k/6}$. The reduction succeeds even if the distinguisher has sub-constant advantage at a small additive cost in sample complexity. Our technique applies with some restrictions to Goldreich's function and $k$LIN with random coefficients over other finite fields.

We present a real-world deployment of secure multiparty computation to predict political preference from private web browsing data. To estimate aggregate preferences for the 2024 U.S. presidential election candidates, we collect and analyze secret-shared data from nearly 8000 users from August 2024 through February 2025, with over 2000 daily active users sustained throughout the bulk of the survey. The use of MPC allows us to compute over sensitive web browsing data that users would otherwise be more hesitant to provide. We collect data us- ing a custom-built Chrome browser extension and perform our analysis using the CrypTen MPC library. To our knowledge, we provide the first implementation under MPC of a model for the learning from label pro- portions (LLP) problem in machine learning, which allows us to train on unlabeled web browsing data using publicly available polling and elec- tion results as the ground truth. The client code is open source, and the remaining code will be open source in the future.

In this paper, we present an optimized construction of the Homomorphic Polynomial Public Key (HPPK) cryptosystem, a novel framework designed to provide enhanced security and efficiency in the post-quantum era. Our work introduces a layered cryptographic design that combines modular arithmetic permutations with an innovative additive random masking technique. This approach effectively obscures the underlying factorizable structure of the public key, thereby mitigating vulnerabilities to known lattice reduction attacks and other algebraic cryptanalyses. The security of our scheme is formally grounded in the computational hardness of three new problems: the Hidden Modulus Product Problem (HMPP), the HPPK Key Recovery Problem (HKRP), and the HPPK Secret Recovery Problem (HSRP). We demonstrate through rigorous analysis that the optimal attacks on our scheme are computationally infeasible for appropriately chosen parameters. Furthermore, we show that HPPK achieves remarkably compact key, ciphertext, and signature sizes, offering a significant advantage over leading NIST post-quantum finalists such as Kyber, Dilithium, and Falcon, particularly in bandwidth-constrained environments. The HPPK cryptosystem offers a compelling and mathematically-grounded solution for next-generation cryptography, delivering both provable security and practical efficiency.

Most adaptively secure identity-based encryption (IBE) constructions from lattices in the standard model follow the framework proposed by Agrawal et al. (EUROCRYPT 2010). However, this framework has an inherent restriction: the modulus is quadratic in the trapdoor norm. This leads to an unnecessarily large modulus, reducing the efficiency of the IBE scheme. In this paper, we propose a novel framework for adaptively secure lattice-based IBE in the standard model, that removes this quadratic restriction of modulus while keeping the dimensions of the master public key, secret keys, and ciphertexts unchanged. More specifically, our key observation is that the original framework has a \textit{natural} cross-multiplication structure of trapdoor. Building on this observation, we design two novel algorithms with non-spherical Gaussian outputs that fully utilize this structure and thus remove the restriction. Furthermore, we apply our framework to various IBE schemes with different partitioning functions in both integer and ring settings, demonstrating its significant improvements and broad applicability. Besides, compared to a concurrent work by Ji et al. (PKC 2025), our framework is significantly simpler in design, and enjoys a smaller modulus, a more compact master public key and shorter ciphertexts.

If the system of an honest user is corrupted, all of its security may be lost: The system may perform computations using different inputs, report different outputs or perform a different computation altogether, including the leakage of secrets to an adversary. In this paper, we present an approach that complements arbitrary computations to protect against the consequences of malicious systems. Tothis end, we adapt a well-known technique traditionally used to increase fault tolerance, namely redundant executions on different machines that are combined by a majority vote on the results. However, using this conceptually very simple technique for general computations is surprisingly difficult due to non-determinism on the hardware and software level that may cause the executions to deviate. The CoRReCt approach, short for Compute, Record, Replay, Compare, considers two synchronized executions on different machines. Only if both executions lead to the same result, this result is returned. Our realization uses virtual machines (VMs): On one VM, the software is executed and non-deterministic events are recorded. On a second VM, the software is executed in lockstep and non-deterministic events are replayed. The outputs of both VMs, which are hosted on different machines, are compared by a dedicated trusted entity and only allowed if they match. The following security guarantees can be proven: – Integrity: If at most one host is corrupted, then the computation is performed using the correct inputs and returns either the correct result or no result at all. – Privacy: If timing side-channels are not considered and at most one host is corrupted, the additional leakage introduced by our approach can be bounded by $\log_2(n)$ bits, where n is the number of messages sent. If timing side-channels are considered and the recording system is honest, the same leakage bound can be obtained. As VMs can be run on completely different host platforms, e.g. Windows on Intel x86-64 or OpenBSD on ARM, the assumption of at least one system being honest is very plausible. To prove our security guarantees, we provide a proof within a formal model. To demonstrate the viability of our approach, we provide a ready-to-use implementation that allows the execution of arbitrary (networked) x86-64 Linux programs and discuss different real-world applications.

Constructing MPC with ephemeral committees has gained a lot of attention since the seminal works on Fluid MPC and YOSO MPC (CRYPTO'21). However, most protocols in this setting focus on the extreme case of ephemeral committees who can only act for one round (i.e., the maximally fluid case). The Layered MPC model (CRYPTO'23) recasts this notion as a protocol execution against an adaptive rushing adversary over a layered interaction graph, where each committee sits on a layer and can only communicate with the immediate next committee. Although protocols with abort allow for linear communication complexity (CRYPTO'23, CiC'24), Perfect Layered MPC with guaranteed output delivery (GOD) and its statistically secure counterpart (TCC'24) suffer from $O(n^9)$ and $O(\kappa n^{18})$ communication complexity for $n$ parties per committee, respectively. In this work, we investigate communication complexity improvements gained in a relaxed Multi-Layered MPC model that allows for limited interaction among the parties in each committee, while still allowing only one round to communicate towards the immediate next committee. We construct Rumors MPC protocols, where the interaction among each committee's members is constant-round. Our protocols achieve GOD and optimal corruption threshold in the perfect (resp. statistical) security setting with committees acting for $\delta=5$ (resp. $\delta=13$) rounds and $O(n^6)$ (resp. $O(\kappa n^8)$) communication.

In this study, we revisit leakage-resilient circuits (LRCs) against $\mathsf{NC}^1$-leakage and propose new constructions that minimize the reliance on leak-free hardware. Specifically, we first present a stateless LRC scheme that is resilient to $\mathsf{NC}^1$-leakage, and then extend it to a leakage-tolerant circuit with auxiliary input (AI-LTC). By integrating this with a 2-adaptive leakage-resilient encoding scheme, we achieve a stateful LRC scheme that uses a secure hardware component. In comparison to the state-of-the-art constructions against $\mathsf{NC}^1$-leakage by Miles and Viola (STOC 2013), both the encoder during the leak-free phase in our stateless LRC and the secure hardware component in our stateful LRC are typically much smaller, as their sizes are independent of the original circuit size. Additionally, we provide a non-black-box instantiation of stateful LRC, resulting in a smaller compiled circuit. The security of all our constructions is based on the very mild worst-case assumption $\mathsf{NC}^1 \subsetneq \oplus\mathsf{L}/\mathsf{poly}$, which is strictly weaker than the assumption $\mathsf{NC}^1 \subsetneq \mathsf{L}$ used by Miles and Viola. Furthermore, we propose a generic conversion from AI-LTCs to non-interactive zero-knowledge proofs with offline simulation (oNIZK) for all $\mathsf{NP}$ in the fine-grained setting. Our instantiation derived from it has small common reference strings, perfect soundness, zero-knowledge against adversaries in $\mathsf{NC}^1$ under $\mathsf{NC}^1 \subsetneq \oplus\mathsf{L}/\mathsf{poly}$, and minimal verification complexity. Finally, we show that any fine-grained oNIZK cannot simultaneously achieve perfect soundness and verifiable common reference strings, thereby ruling out the possibility of constructing stateful LRCs without secure hardware by eliminating the trusted setup of our AI-LTC.

Finding the largest pair of consecutive $B$-smooth integers for a fixed value of $B$, also called a $B$-smooth twin, is computationally challenging. It has only been provably done for $B \leq 100$ and heuristically for $100 < B \leq 113$. We improve this by detailing a new algorithm to find such smooth twins. The core idea is to solve the shortest vector problem (SVP) in a well-constructed lattice. Using a heuristic about smooth numbers in short intervals, we give an estimate of the size of the largest smooth twin for a given $B$. We are able to significantly increase $B$ and notably report the heuristically largest twin with $B = 751$, which has $196$ bits. By slightly modifying the lattice, we are able to find even larger twins, but the resulting smoothness bound will not always be optimal. This notably includes a $213$-bit twin with $B = 997$, which is the largest twin found in this work.

Let f be an arbitrary positive integer valued function. The goal of this note is to show that one can construct a finitely generated group in which the discrete log problem is polynomially equivalent to computing the function f. In particular, we provide infinite, but finitely generated groups, in which the discrete logarithm problem is arbitrarily hard. As another application, we construct a family of two-generated groups that have polynomial time word problem and NP-complete discrete log problem. Additionally, using our framework, we propose a generic scheme of cryptographic protocols, which might be of independent interest.

Homomorphic encryption (HE) is a promising technique for privacy-preserving data analysis. Several HE schemes have been developed, with the CKKS and TFHE schemes being two of the most advanced. However, due to their differences, it is hard to compare their performance and suitability for a given application. We therefore conducted an empirical study of the performance of the two schemes in a comparable scenario. We benchmarked the commonly used operations addition, multiplication, division, square root, evaluation of a polynomial and a comparison function, each on a common pair of datasets with 65536 32-bit integers. Since the CKKS scheme is an approximate scheme, we set a requirement of at least 32 bits of precision to match that of the input data. Our results show that CKKS outperforms TFHE in most operations. TFHE’s only advantage is its fast bootstrapping. Even though TFHE performs bootstrapping after every operation, while CKKS typically performs bootstrapping only after a certain number of multiplications, CKKS’s bootstrapping still presents a bottleneck. This can be seen specifically with the comparison operation, where TFHE is much faster than CKKS in many settings, as it requires several bootstrapping operations in CKKS due to its multiplicative depth. Generally speaking, CKKS should be preferred in applications which can be parallelized. CKKS’s advantages decreases in applications with a large depth that require many bootstrapping operations.

Distributed social networking services (SNSs) recently received significant attention as an alternative to traditional, centralized SNSs, which have inherent limitations on user privacy and freedom. We provide the first in-depth security analysis of Nostr, an open-source, distributed SNS protocol developed in 2019 with more than 1.1 million registered users. We investigate the specification of Nostr and the client implementations and present a number of practical attacks allowing forgeries on various objects, such as encrypted direct messages (DMs), by a malicious user or a malicious server. Even more, we show a confidentiality attack against encrypted DMs by a malicious user exploiting a flaw in the link preview mechanism and the CBC malleability. Our attacks are due to cryptographic flaws in the protocol specification and client implementation, some of which in combination elevate the forgery attack to a violation of confidentiality. We verify the practicality of our attacks via Proof-of-Concept implementations and discuss how to mitigate them.

POKE (POint-based Key Exchange), proposed by Basso and Maino at Eurocrypt 2025, is currently the fastest known isogeny-based public-key encryption scheme. Although POKE is secure against currently known key-recovery attacks, there is no known reduction from key-recovery security to IND-CPA security. In this work, we propose INKE, a variant of POKE that replaces torsion points in the encryption process with intermediate elliptic curves. This modification enables a quantum reduction from key-recovery security to IND-CPA security in the algebraic isogeny model (AIM), while maintaining the practical performance. Although INKE is overall slower than POKE and has larger public-key and ciphertext sizes, it remains more efficient than other group-action-based key exchange protocols such as CSIDH and CORAL that admit reductions from key-recovery security to shared-secret security in algebraic group action model (AGAM). To illustrate the practical overhead of INKE compared to POKE, we provide an optimized C implementation together with detailed benchmark comparisons at each security level.

This paper presents a novel key-based access control technique for secure outsourcing key-value stores where values correspond to documents that are indexed and accessed using keys. The proposed approach adopts Shamir’s secret-sharing that offers unconditional or information-theoretic security. It supports keyword-based document retrieval while preventing leakage of the data, access rights of users, or the size (i.e., volume of the output that satisfies a query). The proposed approach allows servers to detect (and abort) malicious clients from gaining unauthorized access to data, and prevents malicious servers from altering data undetected while ensuring efficient access – it takes 231.5ms over 5,000 keywords across 500,000 files

A Proof of Work (PoW) is an important construction for spam-mitigation and distributed consensus protocols. Intuitively, a PoW is a short proof that is easy for the verifier to check but moderately expensive for a prover to generate. However, existing proofs of work are not egalitarian in the sense that the amortized cost to generate a PoW proof using customized hardware is often several orders of magnitude lower than the cost for an honest party to generate a proof on a personal computer. Because Memory-Hard Functions (MHFs) appear to be egalitarian, there have been multiple attempts to construct Memory-Hard Proofs of Work (MHPoW) which require memory-hard computation to generate, but are efficient to verify. Biryukov and Khovratovich (Usenix, 2016) developed a MHPoW candidate called Merkkle Tree Proofs using used the Argon2d MHF. However, they did not provide a formal security proof and Dinur and Nadler (Crypto, 2017) found an attack which exploited the data-dependencies of the underlying Argon2d graph. We revisit the security of the MTP framework and formally prove, in the parallel random oracle model, that the MTP framework is sound when instantiated with a suitable {\em data-independent} Memory-Hard function. We generically lower bound the cumulative memory cost (cmc) of any prover for the protocol by the pebbling cost of the ex-post facto graph. We also prove that as long as the underlying graph of the original iMHF is sufficiently depth-robust that, except with negligible probability, the ex-post facto will have high cumulative memory cost (cmc). In particular, if we instantiate the iMHF with DRSample then we obtain a MHPoW with the following properties: (1) An honest prover for the protocol can run in sequential time $O(N)$, (2) The proofs have size $\mathtt{polylog}(N)$ and can be verified in time $\mathtt{polylog}(N)$ (3) Any malicious prover who produces a valid proof must incur high cumulative memory complexity at least $\Omega\left(\frac{N^2}{\log N}\right)$. We also develop general pebbling attacks to which we use to show that (1) any iMHF based MHPoW using the MTP framework has proof size at least $\Omega\left(\log^2 N/\log \log N \right)$, and (2) at least $\tilde{\Omega}(N^{0.32})$ when the iMHF is instantiated with Argon2i, the data-independent version of Argon2.

Proof-of-work allows Bitcoin to boast security amidst arbitrary fluctuations in participation of miners throughout time, so long as, at any point in time, a majority of hash power is honest. In recent years, however, the pendulum has shifted in favor of proof-of-stake-based consensus protocols. There, the sleepy model is the most prominent model for handling fluctuating participation of nodes. However, to date, no protocol in the sleepy model rivals Bitcoin in its robustness to drastic fluctuations in participation levels, with state-of-the-art protocols making various restrictive assumptions. In this work, we present a new adversary model, called external adversary. Intuitively, in our model, corrupt nodes do not divulge information about their secret keys. In this model, we show that protocols in the sleepy model can meaningfully claim to remain secure against fully fluctuating participation, without compromising efficiency or corruption resilience. Our adversary model is quite natural, and arguably naturally captures the process via which malicious behavior arises in protocols, as opposed to traditional worst-case modeling. On top of which, the model is also theoretically appealing, circumventing a barrier established in a recent work of Malkhi, Momose, and Ren.

Designing cryptographic protocols and proving these rigorously secure is an arduous and challenging task. Among the methods commonly used to prove security of cryptographic protocols, formalizing it in Canneti's Universal Composability (UC) Framework offers several benefits: (1) Modular design, (2) demonstrating that security remains under arbitrary composition and concurrent execution, (3) the security against any computationally polynomially bound adversary. However, working within the UC Framework can be cumbersome, requires a long time commitment by the prover, and it is prone to errors. While utilization of proof assistants in Cryptography and IT Security is a prominent research area, proof assistants for UC are still in their infancy. Here we show our ongoing work to utilize model checking for verification of proofs in the UC Framework, which to the best of our knowledge is the first attempt to do so. In this work we (1) formally create a Markov Decision Process (MDP) encoding a given proof in the UC Framework, (2) define and proof notions of soundness and completeness for the constructed MDP, (3) implement a proof of concept and (4) demonstrate practical feasibility through experimental evaluation. In summary, in this work we lay out the formal foundations for model checking UC proofs and create a tool that can not only be used for proof verification but also as an assistant for developing proofs in the UC Framework.

Passwords remain the dominant form of authentication on the Internet. The rise of single sign-on (SSO) services has centralized password storage, increasing the devastating impact of potential attacks and underscoring the need for secure storage mechanisms. A decade ago, Facebook introduced a novel approach to password security, later formalized in Pythia by Everspaugh et al. (USENIX'15), which proposed the concept of password hardening. The primary motivation behind these advances is to achieve provable security against offline brute-force attacks. This work initiated significant follow-on research (CCS'16, USENIX'17), including Password-Hardened Encryption (PHE) (USENIX'18, CCS'20), which was introduced shortly thereafter. Virgil Security commercializes PHE as a software-as-a-service solution and integrates it into its messenger platform to enhance security. In this paper, we revisit PHE and provide both negative and positive contributions. First, we identify a critical weakness in the original design and present a practical cryptographic attack that enables offline brute-force attacks -- the very threat PHE was designed to mitigate. This weakness stems from a flawed security model that fails to account for real-world attack scenarios and the interaction of security properties with key rotation, a mechanism designed to enhance security by periodically updating keys. Our analysis shows how the independent treatment of security properties in the original model leaves PHE vulnerable. We demonstrate the feasibility of the attack by extracting passwords in seconds that were secured by the commercialized but open-source PHE provided by Virgil Security. On the positive side, we propose a novel, highly efficient construction that addresses these shortcomings, resulting in the first practical PHE scheme that achieves security in a realistic setting. We introduce a refined security model that accurately captures the challenges of practical deployments, and prove that our construction meets these requirements. Finally, we provide a comprehensive evaluation of the proposed scheme, demonstrating its robustness and performance.

Multivariate cryptography is one of the challenging candidates for post-quantum cryptography. There exists a huge variety of proposals, most of them have been broken substantially. Multivariate schemes are usually constructed by applying two secret affine invertible transformations $\mathcal S,\mathcal T$ to a set of multivariate polynomials $\mathcal{F}$ (often quadratic). The secret polynomials $\mathcal{F}$ possess a trapdoor that allows the legitimate user to find a solution of the corresponding system, while the public polynomials $\mathcal G=\mathcal S\circ\mathcal F\circ\mathcal T$ look like random polynomials. In [Calderini, M., Caminata, A., Villa, I. A New Multivariate Primitive from CCZ Equivalence. J. Cryptol. 38, 25 (2025)], the authors addressed the above challenge by presenting a promising new way of constructing a multivariate scheme by considering the CCZ equivalence, which has been introduced and studied in the context of vectorial Boolean functions. The resulting proposal is called Pesto with security parameters $s,t,m,n,q$, where $n$ is the number of variables, $s,t,m\leq n$ and $q$ the size of the finite base field $\mathbb{F}_q$. In this paper we present an attack against Pesto by constructing an equivalent secret key from the public key. This attack has a precomputation phase with a complexity of \[\textrm{max}\left\{{\mathcal{O}\left(n^{6}(m-t)\right),\mathcal{O}\left(\frac{(m-t)(n-t)^2(n-t-s)q^s}{\mathcal{P}(q,n-t-s)}\right)}\right\}\] base field operations on average and an online complexity of \[\mathcal{O}(q^s(m-t)(n-t-s) \cdot \min(m-t,n-t-s) + q^st (n-t)^2 + q^st^3)\] base field operations to decipher a message or forge a signature, where $\mathcal{P}(q,k) := \prod_{i=1}^k (1-1/q^i)$. Thus, our attack breaks Pesto for any practical choice of the security parameters $n,m,s,t,q$ and renders the concrete construction underlying Pesto insecure.

Vertical federated learning (VFL) enables a cohort of parties with vertically partitioned data to collaboratively train a machine learning (ML) model without requiring them to centralise their data. Each party feeds its data to its local model, with output fed to a global model. However, this configuration requires parties to share some intermediary results during training, which include the output and the gradients of the local models. These intermediary results can reveal insights into the parties' data, and can be protected by secret sharing them with secure multiparty computation (MPC). However, this increases the total number of communications and makes the VFL training significantly slower. In this work, we introduce MUSE-VFL to accelerate the computation of the local gradients by using homomorphic encryption on top of MPC for parties to directly complete this computation during backpropagation. We show theoretically that MUSE-VFL improves the complexity of the MPC baseline. Our experiments, conducted on four different ML tasks, show that the runtime needed to compute the gradients of the local models significantly outweighs the combined runtime of all other steps. This highlights the significance of MUSE-VFL, with experiments demonstrating a training runtime faster by 30% to 35% for LAN and 32% to 50% for WAN.

This work presents a provably-secure lattice-based multisignature scheme which requires only a single round of communication, whereas the existing works need two or three rounds. The reduction in the number of rounds for the proposed scheme is achieved by utilizing lattice trapdoors. In order to generate multisignatures securely, our scheme however requires an honest centralized server that maintains the trapdoor of a shared matrix used in the scheme.

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

We study the approximate Hermite Shortest Vector Problem (HSVP) in ideal lattices in orders of quaternion algebras. For one- and two-sided ideals respectively, we show that for almost all ideals we may solve HSVP in a sublattice of dimension at most one half (respectively, one quarter) of the original lattice dimension, with only small losses in the approximation factor. For two-sided ideals in a cryptographically-relevant family of maximal orders, we obtain approximation factors independent of the algebraic norm of the ideal. For one-sided ideals, we obtain a similar result for a large and natural family of ideal lattices. Finally, we turn our mathematical results into algorithms, and give an unconditional quantum polynomial time algorithm to solve HSVP in ideals of maximal orders of quaternion algebras, given an oracle for HSVP in ideals of maximal orders of number fields, in lower dimension.

Privacy-preserving decision tree inference is a fundamental primitive in privacy-critical applications such as healthcare and finance, yet existing protocols rely heavily on secure selection, which accounts for more than half of the total cost. We introduce a new paradigm that eliminates this limitation by replacing multiple secure selections with a single permutation, whose cost is comparable to that of a single secure selection. Our scheme significantly reduces both computation and communication overhead compared to SOTA. Comprehensive benchmarks show an 86 % reduction in model evaluation versus the state-of-the-art FSS protocol by Ji et al., and a 99.9 % reduction versus the OT-based protocol of Ma et al. Overall, our benchmark shows that our protocol achieves a performance improvement of 20 tiems over Ma et al.’s scheme and 4.5 times over Ji et al.’s scheme.

The argument size of succinct non-interactive arguments (SNARG) is a crucial metric to minimize, especially when the SNARG is deployed within a bandwidth constrained environment. We present a non-recursive proof compression technique to reduce the size of hash-based succinct arguments. The technique is black-box in the underlying succinct arguments, requires no trusted setup, can be instantiated from standard assumptions (and even when $\mathsf{P} = \mathsf{NP}$!) and is concretely efficient. We implement and extensively benchmark our method on a number of concretely deployed succinct arguments, achieving compression across the board to as much as $60\%$ of the original proof size. We further detail non-black-box analogues of our methods to further reduce the argument size.

In recent years and with the emergence of the industrial revolution, the secure data sharing schemes have been developed in IoT platforms and have been recognized as a hot topic in industry and academia. These schemes enable IoT devices to securely share their sensed data in industrial environments with clients through an appropriate infrastructure and intermediary entities. The research conducted in this field shows the existence of various security challenges and solutions. Data privacy, data authentication, fairness and accountability are some of the most important security features presented. Recently, in paper [Sengupta-Ruj-Bit, TNSM 2023] proposed a secure sharing scheme and claimed that it covers all the mentioned security features even when entities collude with each other. In this paper, we investigate the security analysis of this scheme, and show that it does not cover the claimed fairness property. Therefore, the mentioned scheme is vulnerable and cannot be used as a valid scheme in real-world applications.

Transitioning secure information systems to post-quantum cryptography (PQC) comes with certain risks, such as the potential for switching to PQC schemes with as yet undiscovered vulnerabilities. Such risks can be mitigated by combining multiple schemes in such a way that the resulting hybrid scheme is secure provided at least one of the ingredient schemes is secure. In the case of key-encapsulation mechanisms (KEMs), this approach is already in use in practice, where the PQC scheme ML-KEM is combined with “traditional” X25519 key exchange. Combining multiple KEMs to construct a single hybrid KEM is largely straightforward, except for the crucial choice of how to derive the final shared secret key. A generic method for doing this in a manner that preserves IND-CCA security is to include the keys and ciphertexts of all ingredient KEMs in an appropriate key derivation step. In the specialized X-Wing construction, one instead relies on a special property of ML-KEM to avoid including its ciphertext in key derivation. In this work, we show that this optimization can be done in a more general setting. Specifically, when combining multiple KEMs one need not include the ciphertext of any KEM that satisfies ciphertext second preimage resistance (C2PRI)—provided the key combination step is performed using a split-key pseudorandom function. We also prove that any KEM constructed from a certain set of Fujisaki-Okamoto (FO) transforms satisfies C2PRI in the random oracle model. This applies to KEMs such as BIKE, Classic McEliece, HQC, and ML-KEM.

In Neural Cryptanalysis, a deep neural network is trained as a cryptographic distinguisher between pairs of ciphertexts $(F(X), F(X \oplus \delta))$, where $F$ is either a random permutation or a block cipher, $\delta$ is a fixed difference. The AutoND framework aims to se neural distinguishers that are treated as a generic tool and discourages cipher-specific optimizations. On the other hand, works such as $[\text{LLS}^+24]$ obtain superior distinguishers by adding dedicated features, such as selected parts of the difference in the previous rounds, to the input of the neural distinguishers. In this paper, we study $\text{Generic Partial Decryption}$ as a feature engineering technique and integrate it within a fully automated pipeline, where we evaluate its effect independently of the number of pairs per sample, with which feature engineering is often combined. We show that this technique matches state-of-the-art dedicated approaches on Simon and Simeck. Additionally, we apply it to Aradi, and present a practical neural-assisted key recovery for 5 rounds, as well as a 7-rounds key recovery with $2^{70}$ time complexity. Additionally, we derive useful information from the neural distinguishers and propose a non-neural version of our 5-round key recovery.

The shuffle model is a widely used abstraction for non-interactive anonymous communication. It allows $n$ parties holding private inputs $x_1,\dots,x_n$ to simultaneously send messages to an evaluator, so that the messages are received in a random order. The evaluator can then compute a joint function $f(x_1,\dots,x_n)$, ideally while learning nothing else about the private inputs. The model has become increasingly popular both in cryptography, as an alternative to non-interactive secure computation in trusted setup models, and even more so in differential privacy, as an intermediate between the high-privacy, little-utility local model and the little-privacy, high-utility central curator model. The main open question in this context is which functions $f$ can be computed in the shuffle model with statistical security. While general feasibility results were obtained using public-key cryptography, the question of statistical security has remained elusive. The common conjecture has been that even relatively simple functions cannot be computed with statistical security in the shuffle model. We refute this conjecture, showing that all functions can be computed in the shuffle model with statistical security. In particular, any differentially private mechanism in the central curator model can also be realized in the shuffle model with essentially the same utility, and while the evaluator learns nothing beyond the central model result. This feasibility result is obtained by constructing a statistically secure additive randomized encoding (ARE) for any function. An ARE randomly maps individual inputs to group elements whose sum only reveals the function output. Similarly to other types of randomized encoding of functions, our statistical ARE is efficient for functions in $NC^1$ or $NL$. Alternatively, we get computationally secure ARE for all polynomial-time functions using a one-way function. More generally, we can convert any (information-theoretic or computational) ``garbling scheme'' to an ARE with a constant-factor size overhead.

This paper proposes DIMSEPP, a decentralized identity management system that enhances privacy while preserving blockchain verifiability. The system cryptographically enforces data minimal disclosure principles by storing attribute commitments on-chain and validating them through zero-knowledge proofs, allowing users to demonstrate attribute validity without revealing sensitive values. The architecture maintains full compatibility with existing DID standards through standard document structures and verification methods. Security analysis demonstrates provable guarantees under standard cryptographic assumptions. Practical evaluation confirms the system's efficiency for resource-constrained environments, supporting deployment in applications where both privacy and verifiability are essential.

We design a fully homomorphic encryption for moduli of the form $b^k$ with small $b$. Our construction asymptotically improves upon Kim [TCHES'25]: for fixed $b$, the multiplication latency decreases from $O(k \log k)$ to $O(\log k)$ while preserving amortized latency. Our experiments show that our $64$-bit multiplication achieves $\approx 6 \times$ lower latency than Kim and slightly lower latency than TFHE-rs, while improving amortized latency by three orders of magnitude over TFHE-rs. The performance gap widens for larger precision. For instance, our $512$-bit multiplication achieves $\approx 49 \times$ lower latency and four orders of magnitude lower amortized latency than TFHE-rs. We also outperform Boneh and Kim [Crypto'25] with $4.70 \times$ lower latency and $75.3 \times$ lower amortized latency for $256$-bit multiplication.

The development of cryptographic schemes which remain secure in the post-quantum era is an urgent challenge, particularly in light of the growing ubiquity of low-power devices and the looming threat of quantum computing. Identity-Based Encryption (IBE) offers a compelling alternative to traditional Public Key Infrastructures by simplifying key management, but most classical IBE schemes rely on number-theoretic assumptions that are vulnerable to quantum attacks. In response, Koshiba and Takashima proposed a novel approach based on Isogenous Pairing Groups (IPGs) [ 12 ], claiming partial quantum resistance. In this work, we critically examine their construction and security claims and investigate upon the security in standard security notions. We show that the proposed scheme, despite its theoretical elegance, reduces to the Elliptic Curve Dis- crete Logarithm Problem (ECDLP) on supersingular curves, which can be broken in polynomial time by quantum algorithms in the IND-ID-CPA setting and in subexponential time classically in the authors security models. Our analysis reveals structural weaknesses inherent to the IPG framework, such as the use of explicit group elements in prime-order groups and exploitable isogeny homomorphisms, which undermine the post-quantum security of isogeny based cryptography. These findings suggest that IPG-based constructions, which use more than a single point per pairing group, are unlikely to provide robust post-quantum security. In Koshiba and Takashima’s proposed IBE system, we can directly observe this, when paying regards to not only the IBE’s Master Secret Key but also Users’ Secret Keys.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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