Paper 2023/795 Original: eprint.iacr.org/2023/795 ↗
Bit-Security Preserving Hardness Amplification
Abstract
Hardness amplification is one of the important reduction techniques in cryptography, and it has been extensively studied in the literature. The standard XOR lemma known in the literature evaluates the hardness in terms of the probability of correct prediction; the hardness is amplified from mildly hard (close to $1$) to very hard $1/2 + \varepsilon$ by inducing $\varepsilon^2$ multiplicative decrease of the circuit size. Translating such a statement in terms of the bit-security framework introduced by Micciancio-Walter (EUROCRYPT 2018) and Watanabe-Yasunaga (ASIACRYPT 2021), it may cause a bit-security loss of $\log(1/\varepsilon)$. To resolve this issue, we derive a new variant of the XOR lemma in terms of the R\'enyi advantage, which directly characterizes the bit security. In the course of proving this result, we prove a new variant of the hardcore lemma in terms of the conditional squared advantage; our proof uses a boosting algorithm that may output the $\bot$ symbol in addition to $0$ and $1$, which may be of independent interest.
Metadata
- Available format(s)
PDF- Category
- Foundations
- Publication info
- Preprint.
- History
- 2024-09-18: last updated
- 2023-05-31: published
- Short URL
- https://ia.cr/2023/795
- License
- https://creativecommons.org/licenses/by/4.0/
BibTeX
@misc{cryptoeprint:2023/795,
author = {Shun Watanabe and Kenji Yasunaga},
title = {Bit-Security Preserving Hardness Amplification},
howpublished = {Cryptology {ePrint} Archive, Paper 2023/795},
year = {2023},
url = {https://eprint.iacr.org/2023/795}
}