International Association
for Cryptologic Research

Homomorphic encryption schemes are an essential ingredient to design protocols where different users interact in order to obtain some information from the others, at the same time that each user keeps private some of his information. When the algebraic structure underlying these protocols is complicated, then standard homomorphic encryption schemes are not enough, because they do not allow to crypto-compute at the same time additions and products of plaintexts. In this work we define a theoretical object, $t$-chained encryption schemes, which can be used to design crypto-computers for the addition and product of $t$ integer values. Previous solutions in the literature worked for the case $t=2$. Our solution is not only theoretical: we show that some existing (pseudo-)homomorphic encryption schemes (some of them based on lattices) can be used to implement in practice the concept of $t$-chained encryption scheme.

A PIR scheme is a scheme that allows an user to get an element of a database without giving any information about what part of the database he is interested in. In this paper we present a lattice-based PIR scheme, using an NTRU-like approach, in which the computational cost is a few thousand bit-operations per bit in the database. This improves the protocol computational performance by two orders of magnitude when compared to existing approaches. Our scheme has worse communication performance than other existing protocols, but we show that practical usability of PIR schemes is not as dependent on communication performance as the literature suggests, and that a trade-off between communication and computation leads to much more versatile schemes.