### Unprovability of Leakage-Resilient Cryptography Beyond the Information-Theoretic Limit

Rafael Pass

##### Abstract

In recent years, leakage-resilient cryptography---the design of cryptographic protocols resilient to bounded leakage of honest players' secrets---has received significant attention. A major limitation of known provably-secure constructions (based on polynomial hardness assumptions) is that they require the secrets to have sufficient actual (i.e., information-theoretic), as opposed to computational, min-entropy even after the leakage. In this work, we present barriers to provably-secure constructions beyond the information-theoretic barrier'': Assume the existence of collision-resistant hash functions. Then, no NP search problem with $(2^{n^{\epsilon}})$-bounded number of witnesses can be proven (even worst-case) hard in the presence of $O(n^{\epsilon})$ bits of computationally-efficient leakage of the witness, using a black-box reduction to any $O(1)$-round assumption. In particular, this implies that $O(n^{\epsilon})$-leakage resilient injective one-way functions, and more generally, one-way functions with at most $2^{n^{\epsilon}}$ pre-images, cannot be based on any standard'' complexity assumption using a black-box reduction.

Available format(s)
Category
Foundations
Publication info
Published elsewhere. MINOR revision.SCN'20
Keywords
meta-reductionsleakage-resilience
Contact author(s)
rafael @ cs cornell edu
History
Short URL
https://ia.cr/2021/614

CC BY

BibTeX

@misc{cryptoeprint:2021/614,
author = {Rafael Pass},
title = {Unprovability of Leakage-Resilient Cryptography Beyond the Information-Theoretic Limit},
howpublished = {Cryptology ePrint Archive, Paper 2021/614},
year = {2021},
note = {\url{https://eprint.iacr.org/2021/614}},
url = {https://eprint.iacr.org/2021/614}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.