International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Asymptotically Quasi-Optimal Cryptography

Authors:
Leo de Castro , MIT
Carmit Hazay , Bar Ilan
Yuval Ishai , Technion
Vinod Vaikuntanathan , MIT
Muthu Venkitasubramaniam , Georgetown
Download:
Search ePrint
Search Google
Presentation: Slides
Conference: EUROCRYPT 2022
Abstract: The question of minimizing the {\em computational overhead} of cryptography was put forward by the work of Ishai, Kushilevitz, Ostrovsky and Sahai (STOC 2008). The main conclusion was that, under plausible assumptions, most cryptographic primitives can be realized with {\em constant} computational overhead. However, this ignores an additive term that may depend polynomially on the (concrete) computational security parameter λ. In this work, we study the question of obtaining optimal efficiency, up to polylogarithmic factors, for {\em all} choices of n and λ, where n is the size of the given task. In particular, when n=λ, we would like the computational cost to be only O~(λ). We refer to this goal as {\em asymptotically quasi-optimal} (AQO) cryptography. We start by realizing the first AQO semi-honest batch oblivious linear evaluation (BOLE) protocol. Our protocol applies to OLE over small fields and relies on the near-exponential security of the ring learning with errors (RLWE) assumption. Building on the above and on known constructions of AQO PCPs, we design the first AQO zero-knowledge (ZK) argument system for Boolean circuit satisfiability. Our construction combines a new AQO ZK-PCP construction that respects the AQO property of the underlying PCP along with a technique for converting statistical secrecy into soundness via OLE reversal. Finally, combining the above results, we get AQO secure computation protocols for Boolean circuits with security against malicious parties under RLWE.
Video from EUROCRYPT 2022
BibTeX
@inproceedings{eurocrypt-2022-31964,
  title={Asymptotically Quasi-Optimal Cryptography},
  publisher={Springer-Verlag},
  author={Leo de Castro and Carmit Hazay and Yuval Ishai and Vinod Vaikuntanathan and Muthu Venkitasubramaniam},
  year=2022
}