Cryptography from Planted Graphs: Security with Logarithmic-Size Messages

ePrint Report: Cryptography from Planted Graphs: Security with Logarithmic-Size Messages

Damiano Abram, Amos Beimel, Yuval Ishai, Eyal Kushilevitz, Varun Narayanan

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 …

adversary amos cryptographic cryptography eprint report graphs knowledge log messages poly question report security size study