pseudoentropy

Unifying Leakage Classes

Posted on by

Benjamin Fuller and Ariel Hamlin. Unifying Leakage Classes: Simulatable Leakage and Pseudoentropy. ICITS 2015.

Abstract

Leakage-resilient cryptography builds systems that withstand partial adversary knowledge of secret state. Ideally, leakage-resilient systems withstand current and future attacks; restoring confidence in the security of implemented cryptographic systems. Understanding the relation between classes of leakage functions is an important aspect.

In this work, we consider the memory leakage model, where the leakage class contains functions over the system’s entire secret state. Standard classes include functions with bounded output length, functions that retain (pseudo)~entropy in the secret, and functions that leave the secret computationally unpredictable.

Standaert, Pereira, and Yu (Crypto, 2013) introduced a new class of leakage functions they call simulatable leakage. A leakage function is simulatable if a simulator can produce indistinguishable leakage without access to the true secret state. We extend their notion to general applications and consider two versions. For weak simulatability: the simulated leakage must be indistinguishable from the true leakage in the presence of public information. For strong simulatability, this requirement must also hold when the distinguisher has access to the true secret state. We show the following: * Weakly simulatable functions retain computational unpredictability. * Strongly simulatability functions retain pseudoentropy. * There are bounded length functions that are not weakly simulatable. * There are weakly simulatable functions that remove pseudoentropy. * There are leakage functions that retain computational unpredictability are not weakly simulatable.

A Unified Approach to Deterministic Encryption

Posted on by

Benjamin Fuller, Adam O’Neill, and Leonid Reyzin.  A Unified Approach to Deterministic Encryption: New Constructions and a Connection to Computational Entropy.  Theory of Cryptography 2012.

Abstract

This paper addresses deterministic public-key encryption schemes (DE), which are designed to provide meaningful security when only source of randomness in the encryption process comes from the message itself. We propose a general construction of DE that unifies prior work and gives novel schemes. Specifically, its instantiations include:

  • The first construction from any trapdoor function that has sufficiently many hardcore bits.
  • The first construction that provides “bounded” multi-message security (assuming lossy trapdoor functions).

The security proofs for these schemes are enabled by three tools that are of broader interest:

  • A weaker and more precise sufficient condition for semantic security on a high-entropy message distribution. Namely, we show that to establish semantic security on a distribution M of messages, it suffices to establish indistinguishability for all conditional distribution M|E, where E is an event of probability at least 1/4. (Prior work required indistinguishability on all distributions of a given entropy.)
  • A result about computational entropy of conditional distributions. Namely, we show that conditioning on an event E of probability p reduces the quality of computational entropy by a factor of p and its quantity by log_2 1/p.
  • A generalization of leftover hash lemma to correlated distributions.

We also extend our result about computational entropy to the average case, which is useful in reasoning about leakage-resilient cryptography: leaking \lambda bits of information reduces the quality of computational entropy by a factor of 2^\lambda and its quantity by \lambda.