Welcome to the resource topic for 2023/795
Title:
Bit-Security Preserving Hardness Amplification
Authors: Shun Watanabe, Kenji Yasunaga
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.
ePrint: https://eprint.iacr.org/2023/795
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .