Cryptology ePrint Archive
Not a member yet
24907 research outputs found
Sort by
SNARGs for NP from LWE
Full text linkWe construct the first succinct non-interactive argument (SNARG) for NP in the common reference string model based solely on the sub-exponential hardness of the learning with errors (LWE) assumption. Our scheme achieves non-adaptive security, partial succinctness with an argument size of , and is plausibly post-quantum secure. Previous constructions of SNARGs from falsifiable assumptions either relied on indistinguishability obfuscation or were restricted to idealized models (e.g., the random oracle model or generic group model).
Our construction is also the first to instantiate the Micali transformation (Fiat-Shamir applied to Kilian\u27s protocol) in the standard model with concrete hash functions. We achieve this by developing a new mechanism to securely instantiate the Fiat-Shamir hash function for interactive arguments, overcoming the known barriers that limit standard techniques to interactive proofs. As a result, our scheme refutes universal attacks on the Micali framework by demonstrating that there exist concrete instantiations of the underlying components for which the transformation is sound.
Our construction relies on two primitives of independent interest: a PCP with a new property which we term shadow soundness , and a lattice-based vector commitment that provides statistical binding with respect to a hidden function
TSM+ and OTSM - Correct Application of Time Sharing Masking in Round-Based Designs
Full text linkoai:eprint.iacr.org:2026/004Among the countermeasures against side-channel analysis attacks, masking offers formal security guarantees and composability, yet remains challenging to implement efficiently in hardware due to physical defaults like glitches and transitions. Low-latency masking techniques aim to mitigate the performance penalties but can inadvertently compromise security in certain architectural contexts. In particular, the recently proposed Time Sharing Masking (TSM) technique enables single-cycle masked implementations with composability under the SNI and PINI notions but fails to satisfy stronger composability guarantees required in iterative designs, i.e., OPINI. In this work, we show that TSM-based constructions can exhibit first-order leakage when used in single-register feedback architecture, such as round-based implementations of ciphers. To address this, we propose two new masking schemes: TSM+, a more efficient variant of TSM satisfying only PINI (but not SNI), and OTSM, a construction satisfying OPINI, enabling secure round-based designs.
Our improved round-based masked implementations of PRINCE and AES ensure security in latency-critical applications under both glitch- and transition-extended probing model while demanding for slightly more area consumption
SoK: Privacy-Preserving Transactions in Blockchains
Full text linkEnsuring transaction privacy in blockchain systems is essential to safeguard user data and financial activity from exposure on public ledgers. This paper conducts a systematization of knowledge (SoK) on privacy-preserving techniques in cryptocurrencies with native privacy features. We define and compare privacy notions such as confidentiality, k-anonymity, full anonymity, and sender-receiver unlinkability, and categorize the cryptographic techniques employed to achieve these guarantees. Our analysis highlights the trade-offs between privacy guarantees, scalability, and regulatory compliance. Finally, we evaluate the usability of the most popular private cryptocurrencies providing insights into their practical deployment and user interaction.
Through this analysis, we identify key gaps and challenges in current privacy solutions, highlighting areas where further research and development are needed to enhance privacy while maintaining scalability and security
How to Prove Post-Quantum Security for Succinct Non-Interactive Reductions
Full text linkHash-based succinct non-interactive arguments (SNARGs) are widely used in practice, owing to their ease of deployment, notable efficiency, and post-quantum properties. They are constructed via the BCS transformation, which combines an interactive oracle proof (IOP) and a hash-based vector commitment. This success has motivated the study of hash-based succinct non-interactive reductions (SNRDXs), used for recursively ensuring the correctness of distributed computations, by extending the BCS transformation to work with an interactive oracle reduction (IOR) rather than an IOP.
We prove that hash-based SNRDXs constructed from IORs are secure in the quantum random oracle model (QROM), provided the IOR satisfies a natural post-quantum analogue of state-restoration security; moreover, we show that (classical) round-by-round security implies post-quantum state-restoration security. Our results thus achieve a post-quantum analogue of the classical security of SNRDXs in the ROM, and generalize a prior result about SNARGs in the QROM to cover recent SNRDXs constructions.
Moreover, for SNRDXs we propose and achieve an adaptively-secure straightline quantum extraction property in the QROM, while prior work obtains non-adaptive security for SNARGs in the QROM. Along the way, we develop a modular framework for proving the security of the (extended) BCS transformation based on a new quantum extraction property for vector commitments (which we prove is achieved by Merkle commitments), mirroring classical security analyses and departing from prior monolithic post-quantum analyses. This demands a new commutator bound that shows the almost-commutativity between quantum extraction and quantum oracle queries, by bounding a natural classical extraction property
LatORAM: ORAMs from Lateral Stashes and Delayed Shuffling
Full text linkWe study the design of Oblivious RAMs (ORAMs) that allow a client to access memory outsourced to a remote, untrusted server without revealing the client’s data access pattern. We are interested in concretely efficient constructions and prior works have yielded different ORAM frameworks with various trade-offs. Tree-based constructions such as RingORAM [Ren et al., USENIX’15] obtain low communication overhead, but require client storage of linear position maps and two roundtrip queries. Hierarchical schemes such as FutORAMa [Asharov et al., CCS’23] further reduce communication at the cost of more roundtrips during queries. Finally, SQRT-ORAM [Goldreich, STOC ’87] enables fast queries of one roundtrip and one block of communication at the cost of larger amortized communication costs.
We present two new constructions, LatORAM and Lat 2 ORAM, that simultaneously obtain the positive traits of all three types of ORAM constructions. Online queries are blazing fast with one roundtrip and a single block of communication like SQRT-ORAM. Fixing the client memory sizes for comparison, the online communication cost of our constructions are 5-8x smaller than RingORAM and 5-10x smaller than
FutORAMa even though both RingORAM and FutORAM a require multiple roundtrips per online query. Furthermore, our total amortized communication is also up to 50% smaller. To obtain our constructions, we present a new lazy approach of lateral stash growth that delays large shuffles.
Of independent interest, we present improved oblivious merging schemes for specific settings important for our ORAMs. Our constructions solely rely on symmetric cryptography
TOOP: A transfer of ownership protocol over Bitcoin
Full text linkWe present the Transfer of Ownership Protocol (TOOP). TOOP solves a limitation of all existing BitVM-like protocols (and UTxO blockchains at large) that restricts the unlocking transfers to addresses known and preregistered during lock and setup. Accordingly, our protocol avoids the financially costly, regulatory problematic, and congestion-prone front-and-reimburse paradigm.
Furthermore, we note that one of the main applications of TOOP is as an enabler of secure transfer of assets between UTxO blockchains, and back. We showcase this via sketching a committee-based validation protocol that requires only 1-out-of-n honest security. This protocol operates in distinct phases: the lock phase, where the initial setup and individual assets are locked on Bitcoin, and the unlocking with the ownership transfer phase, where the asset is transferred to a possibly different legitimate owner.
This cross-chain bridge protocol, where TOOP plays a key role, is being formalized in concurrent work, and has been implemented for the first time in Cardinal, a protocol for wrapping Bitcoin Unspent Transaction Outputs (UTxOs) onto the Cardano blockchain, with Bitcoin Ordinals represented as Cardano Non-Fungible Tokens (NFTs)
The Cokernel Pairing
Full text linkWe study a new pairing, beyond the Weil and Tate pairing. The Weil pairing is a non-degenerate pairing , which operates on the kernel of . Similarly, when , the Tate pairing is a non-degenerate pairing , which connects the kernel and the rational cokernel of . We define a pairing on the rational cokernels of , filling the gap left by the Weil and Tate pairing. When , this pairing is non-degenerate, and can be computed using three Tate pairings, and two discrete logarithms in , assuming a basis for . For prime, this pairing allows us to study directly and to simplify the computation for a basis of , and more generally the Sylow -torsion. This finds natural applications in isogeny-based cryptography when computing -isogenies
Tight Lower Bound on Witness Update Frequency in Additive Positive Accumulators
Full text linkWe study additive positive accumulators, which maintain a short digest of a growing set such that each value in the set can prove membership via a generated witness. Due to the compactness of the digest, previously added values may require updated witnesses as the set grows.
In this paper, we establish a trade-off between the bit-length of the accumulator value and the number of witness updates. Specifically, we show that if the accumulator value has bit-length , where is the number of accumulated values, then some values must incur witness updates. This improves upon the recent lower bound of [BCCK25] and matches the upper bound in [MQ23].
Building on the framework of [MQR22], we introduce a new combinatorial structure that removes the fixed-update-time assumption. Our approach also applies to Registration-based Encryption [GHMR18], thereby resolving the open problem left in [MQR22]: it shows that the tight lower bound on decryption-update frequency continues to hold even without any fixed-update-time assumption
Batch Arguments with Optimal Communication
Full text linkBatch arguments (BARGs) are non-interactive arguments for conjunctions of NP statements, with proof size that is sublinear in the number of statements.
Several previous works studied the communication complexity of BARGs, focusing both on the CRS size and on the additive overhead of the proof, defined as the difference between the proof size and the size of a single NP witness:
- Devadas et al.~[FOCS 22] constructed BARGs with additive overhead that is independent of , however, their CRS size is polynomial in .
- Paneth and Pass [FOCS 22] constructed BARGs where the CRS size is independent of , but with higher additive overhead .
Under the hardness of LWE, we construct BARGs where both the CRS size the additive overhead of the proof are independent of .
Such BARGs can be recursively composed an unbounded polynomial number of times without losing succinctness.
Along the way, we also considerably simplify the construction of fully local somewhere extractable hash functions used in the construction of Devadas et al
Multi-Holder Anonymous Credentials from BBS Signatures
Full text linkThe eIDAS 2.0 regulation aims to develop interoperable digital identities for European citizens, and it has recently become law. One of its requirements is that credentials be unlinkable. Anonymous credentials (AC) allow holders to prove statements about their identity in a way that does not require to reveal their identity and does not enable linking different usages of the same credential. As a result, they are likely to become the technology that provides digital identity for Europeans.
Any digital credential system, including anonymous credentials, needs to be secured against identity theft and fraud. In this work, we introduce the notion of a multi-holder anonymous credential scheme that allows issuing shares of credentials to different authentication factors (or holders ). To present the credential, the user\u27s authentication factors jointly run a threshold presentation protocol. Our definition of security requires that the scheme provide unforgeability: the adversary cannot succeed in presenting a credential with identity attributes that do not correspond to an identity for which the adversary controls at least shares; this is true even if the adversary can obtain credentials of its choice and cause concurrent executions of the presentation protocol. Further, our definition requires that the presentation protocol provide security with identifiable abort. Finally, presentations generated by all honest holders must be unlinkable and must not reveal the user\u27s secret identity attributes even to an adversary that controls some of the user\u27s authentication factors.
We design and prove the (concurrent) security of a multi-holder version of the BBS anonymous credential scheme. In our construction, each holder is issued a secret share of a BBS credential. Using these shares, the holders jointly compute a credential presentation that is identical to (and therefore compatible with) the traditional, single-holder variant (due to Tessaro and Zhu, Eurocrypt\u2723) of a BBS credential presentation