Paper 2017/722

A Simpler Rate-Optimal CPIR Protocol

Helger Lipmaa and Kateryna Pavlyk

Abstract

In PETS 2015, Kiayias, Leonardos, Lipmaa, Pavlyk, and Tang proposed the first $(n, 1)$-CPIR protocol with rate $1 - o (1)$. They use advanced techniques from multivariable calculus (like the Newton-Puiseux algorithm) to establish optimal rate among a large family of different CPIR protocols. It is only natural to ask whether one can achieve similar rate but with a much simpler analysis. We propose parameters to the earlier $(n, 1)$-CPIR protocol of Lipmaa (ISC 2005), obtaining a CPIR protocol that is asymptotically almost as communication-efficient as the protocol of Kiayias et al. However, for many relevant parameter choices, it is slightly more communication-efficient, due to the cumulative rounding errors present in the protocol of Kiayias et al. Moreover, the new CPIR protocol is simpler to understand, implement, and analyze. The new CPIR protocol can be used to implement (computationally inefficient) FHE with rate $1 - o (1)$.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Keywords
Communication complexitycryptographic protocolsoptimal rate
Contact author(s)
helger lipmaa @ gmail com
History
2017-07-27: received
Short URL
https://ia.cr/2017/722
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/722,
      author = {Helger Lipmaa and Kateryna Pavlyk},
      title = {A Simpler Rate-Optimal CPIR Protocol},
      howpublished = {Cryptology ePrint Archive, Paper 2017/722},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/722}},
      url = {https://eprint.iacr.org/2017/722}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.