Paper 2023/1929

Cryptography from Planted Graphs: Security with Logarithmic-Size Messages

Damiano Abram, Aarhus University
Amos Beimel, Ben-Gurion University of the Negev
Yuval Ishai, Technion – Israel Institute of Technology
Eyal Kushilevitz, Technion – Israel Institute of Technology
Varun Narayanan, University of California, Los Angeles

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 information-theoretic 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 well-studied intractability assumptions: 1) A private simultaneous messages (PSM) protocol for every $f:[n]\times[n]\to\{0, 1\}$ requiring $(1+\epsilon)\log n$-bit messages for most functions and $(2+\epsilon)\log n$-bit messages for the remaining ones. We apply this towards non-interactive secure 3-party computation with similar message size in the preprocessing model, improving over previous 2-round protocols. 2) A secret-sharing scheme for any ``forbidden-graph'' access structure on $n$ nodes with $O(\log n)$ share size. 3) On the negative side, we show that computational threshold secret-sharing schemes with public information require share size $\Omega(\log \log n)$. For arbitrary access structures, we show that computational security does not help with 1-bit 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.

Available format(s)
Publication info
A major revision of an IACR publication in TCC 2023
planted graphsplanted cliquePSMsecret-sharing
Contact author(s)
damiano abram @ cs au dk
amos beimel @ gmail com
yuvali @ cs technion ac il
eyalk @ cs technion ac il
varunnkv @ gmail com
2023-12-21: approved
2023-12-19: received
See all versions
Short URL
No rights reserved


      author = {Damiano Abram and Amos Beimel and Yuval Ishai and Eyal Kushilevitz and Varun Narayanan},
      title = {Cryptography from Planted Graphs: Security with Logarithmic-Size Messages},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1929},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.