Vadhan, Salil. “
Computational entropy.” In
Providing Sound Foundations for Cryptography: On the Work of Shafi Goldwasser and Silvio Micali (Oded Goldreich, Ed.), 693726. ACM, 2019.
Publisher's VersionAbstract
In this survey, we present several computational analogues of entropy and illustrate how they are useful for constructing cryptographic primitives. Specifically, we focus on constructing pseudorandom generators and statistically hiding commitments from arbitrary oneway functions, and demonstrate that:

The security properties of these (and other) cryptographic primitives can be understood in terms of various computational analogues of entropy, and in particular how these computational measures of entropy can be very different from real, informationtheoretic entropy.

It can be shown that every oneway function directly exhibits some gaps between real entropy and the various computational entropies.

Thus we can construct the desired cryptographic primitives by amplifying and manipulating the entropy gaps in a oneway function, through forms of repetition and hashing.
The constructions we present (which are from the past decade) are much simpler and more efficient than the original ones, and are based entirely on natural manipulations of new notions of computational entropy. The two constructions are "dual" to each other, whereby the construction of pseudorandom generators relies on a form of computational entropy ("pseudoentropy") being larger than the real entropy, while the construction of statistically hiding commitments relies on a form of computational entropy ("accessible entropy") being smaller than the real entropy. Beyond that difference, the two constructions share a common structure, using a very similar sequence of manipulations of real and computational entropy. As a warmup, we also "deconstruct" the classic construction of pseudorandom generators from oneway permutations using the modern language of computational entropy.
This survey is written in honor of Shafi Goldwasser and Silvio Micali.
ACM2019Computational Entropy.pdf Balcer, Victor, and Salil Vadhan. “
Differential privacy on finite computers.”
Journal of Privacy and Confidentiality 9, no. 2 (2019).
Publisher's VersionAbstract
Version History:
Also presented at TPDP 2017; preliminary version posted as arXiv:1709.05396 [cs.DS].
2018: Published in Anna R. Karlin, editor, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018), volume 94 of Leibniz International Proceedings in Informatics (LIPIcs), pp 43:143:21. http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8353
We consider the problem of designing and analyzing differentially private algorithms that can be implemented on discrete models of computation in strict polynomial time, motivated by known attacks on floating point implementations of realarithmetic differentially private algorithms (Mironov, CCS 2012) and the potential for timing attacks on expected polynomialtime algorithms. As a case study, we examine the basic problem of approximating the histogram of a categorical dataset over a possibly large data universe \(X\). The classic Laplace Mechanism (Dwork, McSherry, Nissim, Smith, TCC 2006 and J. Privacy & Confidentiality 2017) does not satisfy our requirements, as it is based on real arithmetic, and natural discrete analogues, such as the Geometric Mechanism (Ghosh, Roughgarden, Sundarajan, STOC 2009 and SICOMP 2012), take time at least linear in \(X\), which can be exponential in the bit length of the input.
In this paper, we provide strict polynomialtime discrete algorithms for approximate histograms whose simultaneous accuracy (the maximum error over all bins) matches that of the Laplace Mechanism up to constant factors, while retaining the same (pure) differential privacy guarantee. One of our algorithms produces a sparse histogram as output. Its “perbin accuracy” (the error on individual bins) is worse than that of the Laplace Mechanism by a factor of \(\log X\), but we prove a lower bound showing that this is necessary for any algorithm that produces a sparse histogram. A second algorithm avoids this lower bound, and matches the perbin accuracy of the Laplace Mechanism, by producing a compact and efficiently computable representation of a dense histogram; it is based on an \((n + 1)\)wise independent implementation of an appropriately clamped version of the Discrete Geometric Mechanism.
JPC2019.pdf ITCS2018.pdf ArXiv2018.pdf Agrawal, Rohit, YiHsiu Chen, Thibaut Horel, and Salil Vadhan. “
Unifying computational entropies via KullbackLeibler divergence.” In
Advances in Cryptology: CRYPTO 2019, A. Boldyreva and D. Micciancio, (Eds), 11693:831858. Springer Verlag, Lecture Notes in Computer Science, 2019.
Publisher's VersionAbstract
Version History:
We introduce hardness in relative entropy, a new notion of hardness for search problems which on the one hand is satisfied by all oneway functions and on the other hand implies both nextblock pseudoentropy and inaccessible entropy, two forms of computational entropy used in recent constructions of pseudorandom generators and statistically hiding commitment schemes, respectively. Thus, hardness in relative entropy unifies the latter two notions of computational entropy and sheds light on the apparent “duality” between them. Additionally, it yields a more modular and illuminating proof that oneway functions imply nextblock inaccessible entropy, similar in structure to the proof that oneway functions imply nextblock pseudoentropy (Vadhan and Zheng, STOC ‘12).
CRYPTO 2019.pdf ArXiv2019.pdf