עמוס ביימל

We initiate a systematic study of information-theoretic cryptography with weak privacy, only requiring that the adversary cannot rule out any possible secret. For a parameter 0<p≤1, we say that a primitive has p-weak privacy (p-WP) if for every possible view V and inputs x₁,x₂, the ratio between the probabilities of the adversary observing V on x₁ and on x₂ is at least p. This generalizes both perfect privacy, which is p-WP for p=1, and a previous “combinatorial” notion of privacy, which is p-WP for somep>0. We obtain the following main results. Positive results. We present efficient WP constructions for generalized secret sharing, decomposable randomized encodings, and the related notions of garbling schemes and PSM protocols, as well as interactive secure multiparty computation protocols in the plain model and in the OT-hybrid model.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-WP 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}ⁿ→{0,1} is Θ~(n²).Application. While WP may seem like an unrealistically weak security notion, we demonstrate its usefulness towards achieving traditional security guarantees. Concretely, under the standard LPN assumption, we show that any p-WP 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 WP secret sharing, this implies a super-polynomial improvement of the share size for a natural class of access structures. Positive results. We present efficient WP constructions for generalized secret sharing, decomposable randomized encodings, and the related notions of garbling schemes and PSM protocols, as well as interactive secure multiparty computation protocols in the plain model and in the OT-hybrid model. 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-WP 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}ⁿ→{0,1} is Θ~(n²). Application. While WP may seem like an unrealistically weak security notion, we demonstrate its usefulness towards achieving traditional security guarantees. Concretely, under the standard LPN assumption, we show that any p-WP 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 WP secret sharing, this implies a super-polynomial improvement of the share size for a natural class of access structures.