RecHash enables 254 sequential authentications per renewal with fixed-size hash openings
The claim
RecHash can authenticate 254 application records before needing a renewal certificate under the described parameters
Published as: “RecHash: Segmented Hash-Entangled Chains for Stateful Sequential Authentication”
So what
RecHash offers a compact, deterministic stateful authentication scheme suitable for applications that can rely on an authenticated-history service and tolerate a limited, pre-computed number of records, but its practical security remains unproven.
The five-minute version
RecHash’s segmented construction deterministically supports 254 application records plus a renewal certificate for a 256-bit digest using 32 chain pairs of length 65535, with each record carrying a 2048-byte opening payload. The paper provides exact capacity formulas and resource counts, but its security claim rests on a conditional adaptive one-step bound and lacks a concrete post-quantum reduction.
What they found 2
- For a 256-bit digest, 32 pairs, and chain length 65535, RecHash provides 254 application records and one renewal certificate with 2048-byte openings per record.
“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.”
- The segmented capacity is given by J = ⌊L/(2⌈l/k⌉+1)⌋ slots for equal-length chains.
“For an l-bit digest divided among k chain pairs of equal length L, balanced partitioning gives ⌊L/(2⌈l/k⌉+ 1)⌋slots.”
What undercuts it the paper’s own results
- The security composition theorem separately assumes a uniform one-step computational guarantee for reachable states and accumulated adversarial views. Neither local incomparability nor the absence of number-theoretic assumptions establishes that guarantee on its own.
- It also does not prove computational unforgeability: equal digests and attacks on the hash functions remain outside the index argument.
Stated limits 3
- The security composition theorem separately assumes a uniform one-step computational guarantee for reachable states and accumulated adversarial views. Neither local incomparability nor the absence of number-theoretic assumptions establishes that guarantee on its own.
- The slot count is exact for this specified fixed-width, strictly interior construction. It is not a universal optimum among arrangements that reuse boundaries, change encodings, or redistribute coordinates.
- Concrete reductions, security across replacement, and measured implementation costs are the remaining steps toward assessing post-quantum deployment.
What’s new here 4
- Deterministic segmented allocation that guarantees a fixed number of slots independent of earlier messages.
- Exact integer normalization showing the underlying relation is a constant-sum antichain.
- Balanced partitioning formula J = ⌊L/(2⌈l/k⌉+1)⌋ that maximizes slot count for given parameters.
- A conditional security composition theorem linking authenticated history and a one-step guarantee.
Artifacts & methods 5
- RecHash Segmented constructionsystem
- hash-chain openingprimitive
- authenticated-history servicesystem
- balanced allocation formulatheory
- constant-sum antichain normalizationtheory