Lower-Bounds on Public-Key Operations in PIR

Jesko Dujmovic, Mohammad Hajiabadi

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Private information retrieval (PIR) is a fundamental cryptographic primitive that allows a user to fetch a database entry without revealing to the server which database entry it learns. PIR becomes non-trivial if the server communication is less than the database size. We show that building (even) very weak forms of PIR protocols requires that the amount of public-key operations scale linearly in the database size. We then use this bound to examine the related problem of communication efficient oblivious transfer (OT) extension. Oblivious transfer is a crucial building block in secure multi-party computation (MPC). In most MPC protocols, OT invocations are the main bottleneck in terms of computation and communication. OT extension techniques allow one to minimize the number of public-key operations in MPC protocols. One drawback of all existing OT extension protocols is their communication overhead. In particular, the sender’s communication is roughly double what is information-theoretically optimal. We show that OT extension with close to optimal sender communication is impossible, illustrating that the communication overhead is inherent. Our techniques go much further; we can show many lower bounds on communication-efficient MPC. E.g. we prove that to build high-rate string OT with generic groups, the sender needs to do linearly many group operations.

Original languageEnglish (US)
Title of host publicationAdvances in Cryptology – EUROCRYPT 2024 - 43rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, 2024, Proceedings
EditorsMarc Joye, Gregor Leander
PublisherSpringer Science and Business Media Deutschland GmbH
Pages65-87
Number of pages23
ISBN (Print)9783031587504
DOIs
StatePublished - 2024
Event43rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2024 - Zurich, Switzerland
Duration: May 26 2024May 30 2024

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume14656 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference43rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2024
Country/TerritorySwitzerland
CityZurich
Period5/26/245/30/24

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science

Cite this