1. A Simpler Rate-Optimal CPIR Protocol 2017 FinancialCryptography PIR
    Helger Lipmaa, Kateryna Pavlyk
    [View PDF on fc17.ifca.ai]
    [Show BibTex Citation]

    Address = {Cham},
    Author = {Lipmaa, Helger and Pavlyk, Kateryna},
    Booktitle = {Financial Cryptography and Data Security},
    Editor = {Kiayias, Aggelos},
    Isbn = {978-3-319-70972-7},
    Pages = {621--638},
    Publisher = {Springer International Publishing},
    Title = {A Simpler Rate-Optimal CPIR Protocol},
    Year = {2017}}

In PETS 2015, Kiayias, Leonardos, Lipmaa, Pavlyk, and Tang proposed the first (n, 1)-CPIR protocol with rate 1−𝑜(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−𝑜(1).