Cryptology ePrint Archive: Report 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)$.

Category / Keywords: cryptographic protocols / Communication complexity, computationally-private information retrieval, cryptographic protocols, optimal rate

Date: received 15 Jul 2017, last revised 26 Jul 2017

Contact author: helger lipmaa at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20170727:182354 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]