Paper 2026/2092
Indifferentiability of the Sum of Two Permutations: Tight 3n/4 Security for the Uniform Simulator and a New Simulator for 4n/5 Security
Abstract
We study the regular indifferentiability of the sum of two n-bit permutations. Previous work proved 2n/3-bit security and gave a 5n/6-bit attack against the uniform simulator. We prove 3n/4-bit se curity for the simulator and give a matching attack. Our proof bounds the KL divergence between response distributions by tracking the bias in unrevealed construction values through their conditional distribution, which was not analysed in detail in previous work. To exceed this thresh old, we introduce the Gyroscope simulator, which adjusts inverse-query acceptance probabilities to compensate for the bias left by earlier re sponses. The Gyroscope simulator achieves 4n/5-bit security.
Metadata
- Available format(s)
-
PDF
- Category
- Secret-key cryptography
- Publication info
- Preprint.
- Keywords
- Indifferentiabilitysum of permutationssimulatordistinguishing attacks
- Contact author(s)
- sunyeopkim @ korea ac kr
- History
- 2026-09-22: revised
- 2026-09-18: received
- See all versions
- Short URL
- https://ia.cr/2026/2092
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2026/2092,
author = {Sunyeop Kim},
title = {Indifferentiability of the Sum of Two Permutations: Tight 3n/4 Security for the Uniform Simulator and a New Simulator for 4n/5 Security},
howpublished = {Cryptology {ePrint} Archive, Paper 2026/2092},
year = {2026},
url = {https://eprint.iacr.org/2026/2092}
}
