A survey of single-database private information retrieval: techniques and applications <s> Connections: PIR and Function-Hiding PKE <s> We propose a generalisation of Paillier's probabilistic public key system, in which the expansion factor is reduced and which allows to adjust the block length of the scheme even after the public key has been fixed, without losing the homomorphic property. We show that the generalisation is as secure as Paillier's original system. We construct a threshold variant of the generalised scheme as well as zero-knowledge protocols to show that a given ciphertext encrypts one of a set of given plaintexts, and protocols to verify multiplicative relations on plaintexts. We then show how these building blocks can be used for applying the scheme to efficient electronic voting. This reduces dramatically the work needed to compute the final result of an election, compared to the previously best known schemes. We show how the basic scheme for a yes/no vote can be easily adapted to casting a vote for up to t out of L candidates. The same basic building blocks can also be adapted to provide receipt-free elections, under appropriate physical assumptions. The scheme for 1 out of L elections can be optimised such that for a certain range of parameter values, a ballot has size only O(log L) bits. <s> BIB001 </s> A survey of single-database private information retrieval: techniques and applications <s> Connections: PIR and Function-Hiding PKE <s> In this paper we consider the problem of private searching on streaming data, where we can efficiently implement searching for documents that satisfy a secret criteria (such as the presence or absence of a hidden combination of hidden keywords) under various cryptographic assumptions. Our results can be viewed in a variety of ways: as a generalization of the notion of private information retrieval (to more general queries and to a streaming environment); as positive results on privacy-preserving datamining; and as a delegation of hidden program computation to other machines. <s> BIB002
A classic view of a Public-Key Encryption/Decryption paradigm is that of an identity map: it takes a plaintext message m and creates a ciphertext which can be decrypted back to m. However, in many applications, instead of an identity map, there is a need for a Public-Key Encryption to perform some secret computation during encryption. That is, the key-generation algorithm takes as an additional input a function specification f (·) ∈ F from some class F of functions and produces a Public Key. The resulting Public-Key is not much bigger then the description of a typical f ∈ F, yet the publickey should not reveal which f from F have been used during the key-generation phase. The encryption/decryption maps m to f (m). The definition becomes nontrivial (in the sense that one can not push all the work of computing f (·) to the decryption phase) when for all f ∈ F it holds that |f (m)| < |m|, and we insist that the cyphertext size must be smaller than the size of m. Any single-round PIR can be used to achieve this notion for the class of Encryption functions that encrypt a single bit out of the message, hiding which bit they encrypt: simply publish in your public key both the PIR query and an additional Public-Key Encryption (with small ciphertext expansion, compared to the plaintext, such as  BIB001 ). When encrypting the message, first compute PIR answer, and then encrypt the resulting answer with the Public-Key Encryption. (Some specific PIR constructions do not need this additional layer of encryption). What makes the Function-Hiding PKE notion interesting, is that there are many examples of functions beyond PIR-based projection map. For example, as was shown by Ostrovsky and Skeith BIB002 that one can construct an encryption scheme which takes multiple documents, and encrypts only a subset of these documents -only those that contain a set of hidden keywords, where the public-key encryption function does not reveal which keywords are used as selectors of the subset.