CS Paper Radar

RecHash: Segmented Hash-Entangled Chains for Stateful Sequential Authentication

Luis Adrián Lizama-Pérez

cs.CR ·submitted 2026-10-29 17:23 UTC · v1
theory

Abstract

RecHash is a stateful sequential authentication construction based on paired hash-chain openings and an authenticated record history. It develops the decreasing position relation of the 2019 hash-entangled construction, whose exact integer normalization yields a two-coordinate constant-sum antichain. Direct proportional reuse is constrained by integer capacity and multiplicative contraction. The main construction instead assigns each record to a predetermined chain segment, with complementary positions encoding each digest block. All digests fit every scheduled slot, independently of preceding messages. For an $\ell$-bit digest distributed over $k$ equal-length chain pairs, balanced allocation gives $\lfloor L/(2^{\lceil\ell/k\rceil}+1)\rfloor$ slots. A 256-bit digest, 32 pairs, and length 65535 provide 254 application records followed by a renewal certificate, with 2048 bytes of openings per record for 256-bit chain outputs. We give a complete segmented state transition, a worked trace, exact allocation and resource results, and a renewal-free security-composition theorem conditional on authenticated history and an adaptive one-step guarantee. The analysis relates the construction to constant-sum encodings and standardized hash-based signatures; a concrete post-quantum reduction and security across renewal remain open.

Comment
23 pages, 3 figures, 4 tables

Closest papers

Nearest neighbours by meaning across the whole index.

A BUD You Can Count On: Efficient, Verifiable Membership Proofs

cs.CR cs.DBcs.DC ·2026-09-10 ·Alejandro Ranchal-Pedrosa, Cody Littley, Ben Marsh
theorycode/data similarity 0.60
Abstract

A block typically changes only a small fraction of blockchain state, yet producing a state root makes validators update an authenticated tree spanning it all. We show how to support verifiable reads from the writes alone. We introduce Block Update Digests (BUDs), that commit to a block's writes and link each key touched in that block to its previous modification. An optional prior-value record lets one successor BUD authenticate the value between modifications, replacing the baseline's two BUD openings. SuperBUDs summarize those writes over longer intervals, letting a reader verify that a value remained unchanged without checking every intervening block. Thanks to BUDs and SuperBUDs, validators can just keep ordinary flat state while still serving proofs of current and historical values, including deletion. We prove soundness and completeness for reads at or after a key's first logged modification when the required proof data is available. In experiments with the baseline format, a 50x increase in state size raises the measured base-BUD cost by just 1.24x. In paired QMDB experiments, lowering its garbage-collection activation threshold raises process CPU time by 1.3-2.7x and device bytes written by 1.6-2.4x relative to its dormant configuration. BUD authentication requires no corresponding relocation of live entries. In the evaluated baseline, two-digest read-layer payloads stay below 800 bytes, and warm hash-path verification takes at most 146 μs at p99. Authenticated reads need not make validators maintain an authenticated tree over the entire state.

0.20

Guppy: Efficient Light Clients via Recursive Zero-Knowledge Proofs

cs.CR ·2026-09-07 ·George Danezis, Deepak Maram, Arnab Roy, Alberto Sonnino, Karl Wüst
similarity 0.60
Abstract

Traditional light clients rely on validators committing to the entire blockchain state at every block via a state commitment such as a Merkle tree, allowing clients to verify facts using short proofs. However, maintaining large and ever-growing state trees imposes a significant burden on validators and lies on the critical path of block production. As a result, many modern high-throughput chains avoid this approach altogether. This work asks whether efficient inclusion proofs can be supported without requiring validators to maintain full state commitments. We present Guppy, a protocol that achieves this by having validators commit to just the state updates. An off-chain, untrusted service, secured by recursive Zero-Knowledge Proofs (ZKPs), then maintains a verifiable Merkle tree over the full state. This design keeps validator overhead negligible and does not increase the asymptotic complexity of block construction. Our design rests on two key technical ideas. First, a hash-chain commitment moves validator signature verification out of the ZK circuit, keeping the proving circuit efficient. Second, we design a parallel recursive proving pipeline that leverages cheap recursion in modern ZKPs to ensure latency grows only logarithmically with throughput. Our Plonky2-based implementation demonstrates that Guppy can maintain a Merkle tree of size 2^30 while processing thousands of updates per second, adding only 2-4 s of latency.

0.42

PQ-Vault: Provably Quantum-Safe Asset Custody for Unmodified Ethereum

cs.CR quant-phcs.DCcs.IT ·2026-10-21 ·Hassan Khodaiemehr, Khadijeh Bagheri, Chen Feng
theory similarity 0.57
Abstract · 14 pages + 11 pages of appendices

A quantum computer could recover the key of any Ethereum account whose public key appears on chain. We prove that no sidechain or bridge that leaves Ethereum's rules unchanged can protect such accounts: their funds must move into a contract whose release condition relies only on quantum-safe primitives. We design \emph{PQ-Vault}, a custody system for unmodified Ethereum combining this vault, a quantum-safe proof-of-stake sidechain whose checkpoints carry compact certificates, and an optimistic dispute protocol. We give the first security proof of compact certificates against quantum attackers and a matching attack: with classically chosen parameters, the guarantee falls from 128 to about 60 bits, and a simple rule restores it. We show that a common seed-update rule in hash-chain proof of stake lets an attacker steer chosen slots and profit from splitting its stake, and give an election whose steering gain and inclusion delay are provably bounded against quantum attackers. Since compressing certificates with a pairing-based SNARK breaks quantum security, we use fraud proofs that need a single signature check. For 65,536 validators, a certificate is 0.8 MB, 260 times smaller than all signatures, and verifies in about 20 ms; the vault accepts a checkpoint for about 420,000 gas.

0.17

Authenticated Data Structures for Dynamic Workloads

cs.CR ·2026-08-25 ·Ziheng Shangguan, Aviv Yaish, Dahlia Malkhi
publishedhot direction similarity 0.57
Abstract · 40 pages, 18 figures, 2 tables. Appendix A-G included

We introduce the Huffman-Merkle Tree (HMT), an authenticated data structure (ADS) for dynamic workloads where items may differ in access frequencies, and access frequencies can change over time. An ADS allows proving item membership against a short commitment to a large mutable state, with applications including verifiable storage, Internet transparency services, and blockchains. Optimizing ADS performance under continuously changing access frequencies has not been fully addressed before, neither in theory nor in practice. HMT addresses dynamically changing access skew through two complementary mechanisms. The first is a Huffman-coding-based Merkle-tree layout, with a novel extension to support evolving access frequencies. The second is an elastic tiering regime that partitions items across separate trees, such as hot and cold tiers, with adaptive migration between them. The key insight in this approach is to place frequently accessed items closer to the root, while assigning less frequently accessed items to progressively larger and deeper trees. This reduces the overall frequency-weighted access cost. Our scheme is designed to scale to gigabytes of data spanning millions of items. To handle dynamism efficiently, layout updates are applied in batches, access frequencies are tracked using a count-min sketch, and the system employs a tier-promotion cache while exploring multiple tier-migration policies. We implement HMT and compare it on real-world data with Ethereum's Merkle Patricia Trie (MPT) ADS and its proposed replacement, the Unified Binary Tree (UBT). Our evaluation considers two metrics: the amount of hashing per update and access-weighted membership-proof size. The latter captures both item access cost and frequency. We find that the best HMT policy uses about 2.4x and 0.34x less average hash operations than MPT and UBT respectively, and has 0.18x and 0.55x shorter proofs.

0.49

BenX: Resource-Sharing Permutations for Computational Integrity

cs.CR ·2026-09-25 ·Luca Campa, Thomas De Cnudde, Al Kindi, Arnab Roy, Fabian Schmid +2 more
similarity 0.55
Abstract

Cryptographic hash functions over integers modulo a prime play a decisive role in the efficiency and security of proof systems for computational integrity. Early designs focused on compact arithmetic circuits and efficient software execution, primarily targeting general-purpose CPUs rather than hardware accelerators. This work focuses on enabling efficient resource sharing and hardware acceleration alongside efficient software execution. We propose BenX, a permutation-based hash function designed for hardware acceleration, fast CPU execution, and low circuit complexity in proof systems. To construct the underlying permutation, we turn the Benes network into an invertible function over $\mathbb{F}_p^2$ using a Dickson polynomial. Its structure yields a permutation particularly suited to hardware resource sharing and acceleration. Fully pipelined on FPGA, BenX matches the throughput of Poseidon2, with 1.36x and 2.15x lower latency for Goldilocks and BabyBear, respectively. Although larger as a standalone core, it makes more effective use of shared hardware: in our dual-mode architecture, where the NTT and hash share field multipliers, BenX keeps 100% of them busy, compared with 6.25-20.3% for the partial rounds of Poseidon and Poseidon2. In software, BenX outperforms Poseidon in all tested 31- and 64-bit configurations, but is slower than Poseidon2, except for the 16-element BabyBear instance. In zero-knowledge proofs, BenX proves Goldilocks permutations 6-10x faster than Monolith. Its compact arithmetization uses about 36% fewer trace cells than Poseidon and Poseidon2 over BabyBear, while its fast variant requires 1.3-2.6x the prover time of Poseidon2.

0.22

A New Upper Bound on the Binary Deletion Channel Capacity

cs.IT ·2026-09-11 ·Özgür Soysal
theory similarity 0.54
Abstract

We prove that the capacity of the binary deletion channel satisfies $C(d)\le (1-d)/4$ for every $13/20\le d<1$. The proof describes the output from right to left, using a six-bit context to assign a description length. We bound the increase in expected description length minus output entropy when one input bit is added. A relative-entropy identity reduces this bound to finitely many linear inequalities. A potential on input windows of length 26 makes the inequalities telescope, giving a bound for every input word. Deletion composition extends the result from $d=13/20$ to all larger deletion probabilities. We also obtain finite-block bounds on mutual information and decoding error, with explicit $O(\log n/n)$ corrections. The finite certificate is checked using exact integer arithmetic, and the proof is formalized end to end in Lean.

0.34

QUASI: Post-Quantum Quorum Attestation of Pre-Validated Statements

cs.CR ·2026-11-07 ·Maksym Ioffe, Dahlia Malkhi
similarity 0.54
Abstract

We present QUASI, a newly conceived class of protocols that enable a group of parties to produce a publicly verifiable attestation about a pre-validated statement. Designed for quorum-based systems, QUASI enables parties to attest to external entities that the statement is valid. Surprisingly, each party need not sign the entire statement: authenticating only a small subset of symbols suffices for the quorum to attest to the whole. A simple deterministic construction illustrates this possibility. Built purely from hashing and error correction, QUASI achieves small per-party contributions and low attestation generation and verification costs, without relying on SNARKs for aggregation. Our main contribution is a randomized construction achieving reductions of more than $10\times$ in per-party contribution size and hash computations for generation and verification, compared with full hash-based signatures. QUASI is a generic primitive supporting diverse applications. Two principal use cases are external attestation for signature-free consensus, enabling clients to verify statements about committed state; and preprocessing for SNARK-based aggregation, compounding QUASI's savings with succinct-proof compression.

0.23

Finality Before Disclosure for Ledger Authenticators in the Quantum Random Oracle Model

cs.CR ·2026-08-19 ·Maja Lie, Benjamin Marsh
theoryhot direction similarity 0.54
Abstract

Public ledgers increasingly authorize state transitions using prior transactions, finalized state, timing, and ordering rather than only a public key, message, and portable signature. We introduce ledger authenticators and $\LAEUF$, an unforgeability experiment for reactive authorization protocols whose public judgment algorithm reads a finalized transcript. The model separates authentication safety from ledger liveness and captures canonical transition freshness, adaptive corruption, exposure before inclusion, censorship, and adversarial ordering. We identify two conditional resource boundaries. An authenticator satisfying our single event conditions yields a contextual one-time signature. Within our rebindable reveal class, safety requires computational post-disclosure non-admissibility. When precursor admission uses only public computation and ledger scheduling, this condition is enforced by closing the evidence eligible to use a disclosed credential. If newly constructed evidence remains admissible after disclosure, censoring the honest reveal gives a forgery. We then define a joint ledger and quantum random oracle execution model in which quantum state persists across classical finalization cuts and oracle evaluations made through the ledger are charged. For a closed finalized target set of size at most $K$, we prove the bound $3β_{\mathsf{cut}}^2+3c_{\mathsf{co}}KQ^2/2^λ+6\ell/2^λ$, where $β_{\mathsf{cut}}$ accounts for fresh openings already present at the cut. A commit, close, reveal authenticator instantiates the framework and obtains a multi-user lifetime QROM bound.

0.31