Cryptology ePrint Archive

In secret-key private information retrieval (SK-PIR), the client in an offline phase processes the database using a short secret key. In the online phase the client could then use the secret key to make queries to the server, without revealing the entries accessed, and using only sublinear communication $o(N)$ in the database size $N$. While (non-SK) PIR requires public-key cryptography, recent w…

Hash-based SNARKs are arguably the most prominent and widely deployed class of transparent SNARKs, owing to desirable properties such as plausible post-quantum security and the avoidance of public-key cryptography. The key ingredients in the construction of hash-based SNARKs are an error-correcting code and an Interactive Oracle Proof of Proximity (IOPP) for that code. A particularly desirab…

The Recording Standard Oracle with Errors (RstOE) technique is an important tool for quantum security proofs in symmetric-key cryptography. However, against adaptive quantum chosen-plaintext adversaries, traditional RstOE-based proofs may suffer from the ``trivialization of norm” problem. This issue arises from three main causes: the delayed evaluation of bad events, the presence of unrecorded ex…

Broadcast encryption (BE) allows a sender to succinctly encrypt a message to any dynamically chosen subset of recipients. The gold-standard for BE is optimal succinctness (parameters independent of the number of users) and adaptive security, and attaining both from falsifiable post-quantum assumptions has been a central open problem. Recently, Goyal and Yadugiri (GY) gave the first adaptively-sec…

We give the first rigorous $O(1)/|F|$ FRI commit-phase soundness bound for plain Reed–Solomon above the Johnson radius — the central open question in the proximity-gap line, made urgent by the late-2025 disproof of the up-to-capacity conjecture (Crites–Stewart; BCHKS; Diamond–Gruen). The bound is proved via a structural mechanism new to the proximity-gap literature: the action–orbit symmetry …

Permissionless Proof-of-Stake (PoS) economic security is predicated on the high cost of violating consensus safety or liveness. We show that liquid staking introduces additional risks that are not captured by standard PoS economic security arguments. Through an empirical study of Ethereum data, we find that the operational performance of liquid staking pools is positively associated with subseque…

We propose a plausibly post-quantum additively homomorphic PKE scheme, SoliloQuat, based on the short generator principal ideal problem (SG-PIP) in orders of quaternion algebras. SoliloQuat is inspired by Soliloquy, a KEM that was both introduced and broken by Campbell-Groves-Shepherd in 2014. However, it is not known if their attack can be generalised to the non-commutative setting, despite havi…

We prove the first unconditional soundness theorem above the Johnson bound for FRI, STIR, and WHIR — the proximity-testing protocols underlying every deployed STARK, zkVM, and FRI-based system on Ethereum's roadmap. For $\mathrm{RS}[F, L, k]$ with $k = 2^m$ and $L$ admitting a fixed-point-free involution (standard for deployed FRI, in either characteristic), for every $\delta \in (\delta_J,\, 1-\…

Verifiable Computation on Encrypted Data (VCoED) addresses the computational integrity gap in Fully Homomorphic Encryption (FHE). While recent protocols have made significant strides in making VCoED feasible, server-side proof generation remains computationally intensive, often requiring hours for a modest $2^{20}$-gate payload circuit (e.g., 2.27 hours for Phalanx, 9.26 hours for Blind Fractal).…

We introduce MERIDIAN, a 128-bit block cipher designed for resource-constrained environments as a lightweight alternative to AES-128. MERIDIAN retains the AES-128 interface, including a 128-bit block, 128-bit key, and 4×4 byte state, while reusing the standard AES S-box. This enables compatibility with existing AES-128 modes such as ECB, CBC, CFB, OFB, CTR, XTS, CMAC, CCM, and GCM, and allows imp…

Nearly all succinct proof systems express computations as algebraic constraints over a finite field. Operations not native to this field, such as bitwise manipulation, modular arithmetic, and lattice-ring operations, require an arithmetization step that can inflate the witness size by one or more orders of magnitude. We introduce Universal Constraint Systems (UCS) and Zinc$+$. The first is a rel…

The *random oracle model* (ROM) allows us to optimistically reason about security properties of cryptographic hash functions, and has been hugely influential in designing practical cryptosystems. But it is overly optimistic against non-uniform adversaries, and often suggests security properties and security levels unachievable by any real hash function. To reconcile with this discrepancy, Unruh…

Fully homomorphic encryption is a promising cryptographic primitive for privacy-preserving computation, yet bootstrapping remains the primary bottleneck for its practical deployment. For the CKKS scheme, the dominant cost of bootstrapping arises from the homomorphic evaluation of the Discrete Fourier Transform (DFT) and its inverse. Existing approaches realize these operations as matrix-vector pr…

Isogeny-based cryptography is a kind of cryptography whose security relies on the computational hardness of the isogeny problem. This field is gaining attention as a promising candidate for post-quantum cryptography. Among the notable schemes within this category is SQIsign, a signature schemes that has been submitted to the NIST Post-Quantum Cryptography Standardization competition. In this pape…

Identity-Based Encryption (IBE) schemes were introduced to simplify public-key infrastructure by using any arbitrary strings as public keys. However, a longstanding criticism of IBE is the trade-off inherent in the ``key escrow'' problem: the design of IBE ensures that the authority possesses a master secret key that allows it to generate secret keys for any identity and, consequently, decrypt an…

Fungible tokens on public blockchains expose all balances and transfer amounts in the clear, which is incompatible with the financial privacy required by many real-world applications. We present Merces a confidential token contract that hides user balances and transaction amounts while preserving on-chain verifiability. The core idea is to store secret shares of balances within a decentralized MP…

Naively multiplying two $2 \times 2$ matri- ces requires eight multiplications and four additions. Strassen showed how to perform the same computation using seven multiplications and 18 additions. By chang- ing basis, Karstadt and Schwartz lowered the number of additions to 12, which they showed to be optimal within this generalized Karstadt-Schwartz (KS) framework. We present improved methods f…

With the expansion of Machine Learning as a Service (MLaaS), Secure Multi-Party Computation (MPC) is widely used to protect the privacy of both proprietary models and client data during inference. To achieve practical performance, these protocols typically rely on fixed-point arithmetic over finite rings. However, this design choice introduces a unique arithmetic vulnerability: silent modular wra…

Group signatures are one of the central privacy-preserving authentication mechanisms, offering an interesting trade-off between accountability and anonymity. Their versatility has led to many applications and even standardization at ISO/IEC. Unfortunately, they lack so far efficient quantum-safe constructions, despite several works implementing the seminal framework by Bellare, Micciancio and War…

It is obviously necessary that the security of post-quantum cryptographic schemes is based on computational problems that are hard to solve even with a quantum computer (unlike, e.g., factoring). Examples of such computational problems appear in the theory of lattices or in coding theory. However, this is not sufficient: also the security proof, which comes in the form of an algorithmic reduction…