Welcome to the resource topic for 2023/1929
Title:
Cryptography from Planted Graphs: Security with LogarithmicSize Messages
Authors: Damiano Abram, Amos Beimel, Yuval Ishai, Eyal Kushilevitz, Varun Narayanan
Abstract:We study the following broad question about cryptographic primitives: is it possible to achieve security against an arbitrary \mathsf{poly}(n)time adversary with O(\log n)size messages? It is common knowledge that the answer is ``no’’ unless informationtheoretic security is possible. In this work, we revisit this question by considering the setting of cryptography with public information and computational security.
We obtain the following results, assuming variants of wellstudied intractability assumptions:

A private simultaneous messages (PSM) protocol for every f:[n]\times[n]\to\{0, 1\} requiring (1+\epsilon)\log nbit messages for most functions and (2+\epsilon)\log nbit messages for the remaining ones. We apply this towards noninteractive secure 3party computation with similar message size in the preprocessing model, improving over previous 2round protocols.

A secretsharing scheme for any ``forbiddengraph’’ access structure on n nodes with O(\log n) share size.

On the negative side, we show that computational threshold secretsharing schemes with public information require share size \Omega(\log \log n). For arbitrary access structures, we show that computational security does not help with 1bit shares.
The above positive results guarantee that any adversary of size n^{o(\log n)} achieves an n^{\Omega(1)} distinguishing advantage. We show how to make the advantage negligible by slightly increasing the asymptotic message size, still improving over all known constructions.
The security of our constructions is based on the conjectured hardness of variants of the planted clique problem, which was extensively studied in the algorithms, statistical inference, and complexity theory communities. Our work provides the first applications of such assumptions improving the efficiency of mainstream cryptographic primitives, gives evidence for the necessity of such assumptions, and suggests new questions in this domain that may be of independent interest.
ePrint: https://eprint.iacr.org/2023/1929
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .