Segmented hash chains improve secure sequence authentication states
RecHash: Segmented Hash-Entangled Chains for Stateful Sequential Authentication
Cryptography and Security
Summary
Ensuring data records are securely linked and verified over time is a challenge in computer security. The authors introduce RecHash, a new way to organize and authenticate sequences of records using paired hash chains assigned in segments, making it possible to keep track of records reliably without depending on earlier messages. This method allows many records to be authenticated with clear slots and supports renewing security credentials efficiently. While the paper provides detailed design and analysis, some advanced security guarantees, especially against quantum attacks, remain to be addressed.
What this means in practice
- •For blockchain developers: Maintain secure and verifiable transaction histories by using segmented hash chains to authenticate sequences of blockchain records efficiently.
- •For cloud security teams: Support secure audit logs that authenticate sequences of system events with minimal reliance on prior event data, improving integrity guarantees.
Authors
Luis Adrián Lizama-Pérez
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.