RecHash：用于有状态顺序认证的分段哈希纠缠链
RecHash: Segmented Hash-Entangled Chains for Stateful Sequential Authentication
Luis Adrián Lizama-Pérez
AI 速览：提出一种基于配对哈希链开链与认证记录历史的有状态顺序认证构造，用分段分配解决整数容量与乘法收缩带来的复用限制。
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.