Bit-Security Preserving Hardness Amplification

Shun Watanabe; Kenji Yasunaga

Paper 2023/795

Bit-Security Preserving Hardness Amplification

Shun Watanabe, Tokyo University of Agriculture and Technology

Kenji Yasunaga, Tokyo Institute of Technology

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 the bit-security loss by the factor 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.
Keywords: bit security hardness amplification XOR lemma hardcore lemma
Contact author(s): shunwata @ cc tuat ac jp
yasunaga @ c titech ac jp
History: 2023-06-06: approved; 2023-05-31: received; See all versions
Short URL: https://ia.cr/2023/795
License: CC BY

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},
      note = {\url{https://eprint.iacr.org/2023/795}},
      url = {https://eprint.iacr.org/2023/795}
}