Shaomin Chen

Shaomin Chen

Auto-generated profile, based on publicly available information

Shaomin Chen

Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China, University of Chinese Academy of Sciences, Beijing, China

Research Focus & Metrics

Academic Career Length

2Years (2025-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications

30 October 2026 in IACR Transactions on Symmetric Cryptology
Verified
Journal Article
Open access
RDRui Ding
Rui Ding
LTLili Tang
Lili Tang
SCShaomin Chen
Shaomin Chen
XGXiaorui Gong
Xiaorui Gong
Wagner's k-tree algorithm solves the generalized birthday problem and underlies preimage attacks on randomize-then-combine incremental hashes (EUROCRYPT '97) such as iSHAKE, LtHash, and AdHash. In its full-index execution, 2k-1 index entries dominate peak memory at large k, and index trimming narrows each entry but leaves their number intact. Tang et al. (TCHES '26) introduced post-retrieval for the single-chain algorithm and left the 2k exponent of the k-tree setting as an open problem. We resolve it by extending post-retrieval to the k-tree algorithm. This cuts the peak working memory to PklN = O(k2lN), removing the 2k-1 index entries from the forward pass at the cost of a Theta(k) time overhead. Free delta-level caching shrinks this time factor at no memory cost. The trade-off is starkly asymmetric: it removes an exponential number of index entries for only a linear recovery-time overhead. As a practical application, we revisit the list-item-reduction landscape for the k-tree algorithm under the memory-time product metric, MT = M * T. The gain is regime-dependent: for small k the index entries do not yet dominate, so the recovery overhead outweighs the saving. For large k the saving dominates, lowering the optimized log2 MT from 4 sqrt(n) to 2 sqrt(2n) at leading order. For fixed-size iSHAKE preimage attacks, we save approximately 51 and 122 bits over state-of-the-art index trimming for iSHAKE-128 and iSHAKE-256, respectively, in the unlimited-block setting, narrowing to roughly 6 and 8 bits under block-count caps.