CryptoDB
Cryptography with Weak Privacy
| Authors: |
|
|---|---|
| Download: | |
| Conference: | TCC 2025 |
| Abstract: | We initiate a systematic study of information-theoretic cryptography with weak privacy, requiring that no secret can be ruled out by the adversary. For a parameter 0 < p <= 1, we say that a primitive has p-weak differential privacy (p-WP) if for every possible view V and inputs x_1, x_2, the ratio between the probabilities of the adversary observing V on x_1 and on x_2 is at least p. This generalizes both perfect privacy, which is p-WDP for p = 1, and a previous "combinatorial" notion of weak privacy (WP), which is p-WDP for some p > 0. We obtain the following main results. - Positive results. We present efficient WDP constructions for generalized secret sharing, decomposable randomized encodings (and the related notions of garbling schemes and PSM protocols), and secure two-party computation with correlated randomness. For secret sharing, we settle a question of Beimel and Franklin (TCC 2007), showing that every n-party access structure admits a WP scheme with per-party share size O(n). When all unauthorized sets have constant size, we get a p-WDP scheme with constant share size and p >= 1 / poly(n). - Negative result. For decomposable randomized encodings, we show that a previous lower bound technique of Ball et al. (ITCS 2020) applies also to the WP notion. Together with our upper bound, this shows that the optimal WP garbling size of the worst-case f : {0, 1}^n -> {0, 1} is \tilde{\Theta}(n^2). - Application. Under the standard LPN assumption, we show that any p-WDP secret sharing scheme with inverse-polynomial p implies a computationally secure secret sharing scheme for a related access structure. Together with our positive results for WDP secret sharing, this implies a super-polynomial improvement in the share size of computational secret sharing for a natural class of access structures. |
BibTeX
@inproceedings{tcc-2025-36280,
title={Cryptography with Weak Privacy},
publisher={Springer-Verlag},
author={Amos Beimel and Yuval Ishai and Eyal Kushilevitz and Hanjun Li},
year=2025
}