conference paper
Condensed unpredictability
LNCS
published
yes
Maciej
Skórski
author
Alexander
Golovnev
author
Krzysztof Z
Pietrzak
author 3E04A7AA-F248-11E8-B48F-1D18A9856A870000-0002-9139-1654
KrPi
department
ICALP: Automata, Languages and Programming
Provable Security for Physical Cryptography
project
We consider the task of deriving a key with high HILL entropy (i.e., being computationally indistinguishable from a key with high min-entropy) from an unpredictable source.
Previous to this work, the only known way to transform unpredictability into a key that was ϵ indistinguishable from having min-entropy was via pseudorandomness, for example by Goldreich-Levin (GL) hardcore bits. This approach has the inherent limitation that from a source with k bits of unpredictability entropy one can derive a key of length (and thus HILL entropy) at most k−2log(1/ϵ) bits. In many settings, e.g. when dealing with biometric data, such a 2log(1/ϵ) bit entropy loss in not an option. Our main technical contribution is a theorem that states that in the high entropy regime, unpredictability implies HILL entropy. Concretely, any variable K with |K|−d bits of unpredictability entropy has the same amount of so called metric entropy (against real-valued, deterministic distinguishers), which is known to imply the same amount of HILL entropy. The loss in circuit size in this argument is exponential in the entropy gap d, and thus this result only applies for small d (i.e., where the size of distinguishers considered is exponential in d).
To overcome the above restriction, we investigate if it’s possible to first “condense” unpredictability entropy and make the entropy gap small. We show that any source with k bits of unpredictability can be condensed into a source of length k with k−3 bits of unpredictability entropy. Our condenser simply “abuses" the GL construction and derives a k bit key from a source with k bits of unpredicatibily. The original GL theorem implies nothing when extracting that many bits, but we show that in this regime, GL still behaves like a “condenser" for unpredictability. This result comes with two caveats (1) the loss in circuit size is exponential in k and (2) we require that the source we start with has no HILL entropy (equivalently, one can efficiently check if a guess is correct). We leave it as an intriguing open problem to overcome these restrictions or to prove they’re inherent.
https://research-explorer.app.ist.ac.at/download/1650/4693/IST-2016-675-v1+1_384.pdf
application/pdfno
Springer2015Kyoto, Japan
eng
10.1007/978-3-662-47672-7_85
91341046 - 1057
Skórski, Maciej, et al. <i>Condensed Unpredictability </i>. Vol. 9134, Springer, 2015, pp. 1046–57, doi:<a href="https://doi.org/10.1007/978-3-662-47672-7_85">10.1007/978-3-662-47672-7_85</a>.
Skórski M, Golovnev A, Pietrzak KZ. Condensed unpredictability . In: Vol 9134. Springer; 2015:1046-1057. doi:<a href="https://doi.org/10.1007/978-3-662-47672-7_85">10.1007/978-3-662-47672-7_85</a>
M. Skórski, A. Golovnev, K.Z. Pietrzak, in:, Springer, 2015, pp. 1046–1057.
Skórski, Maciej, Alexander Golovnev, and Krzysztof Z Pietrzak. “Condensed Unpredictability ,” 9134:1046–57. Springer, 2015. <a href="https://doi.org/10.1007/978-3-662-47672-7_85">https://doi.org/10.1007/978-3-662-47672-7_85</a>.
Skórski M, Golovnev A, Pietrzak KZ. 2015. Condensed unpredictability . ICALP: Automata, Languages and Programming, LNCS, vol. 9134, 1046–1057.
Skórski, M., Golovnev, A., & Pietrzak, K. Z. (2015). Condensed unpredictability (Vol. 9134, pp. 1046–1057). Presented at the ICALP: Automata, Languages and Programming, Kyoto, Japan: Springer. <a href="https://doi.org/10.1007/978-3-662-47672-7_85">https://doi.org/10.1007/978-3-662-47672-7_85</a>
M. Skórski, A. Golovnev, and K. Z. Pietrzak, “Condensed unpredictability ,” presented at the ICALP: Automata, Languages and Programming, Kyoto, Japan, 2015, vol. 9134, pp. 1046–1057.
16502018-12-11T11:53:15Z2021-01-12T06:52:15Z