MarriageTheoremのこと

_ IACR ePrint 2013/429まで確認済み、ECCC 2000年分まで確認済み

_ 気になった論文：Private Database Queries Using Somewhat Homomorphic Encryption, Dan Boneh and Craig Gentry and Shai Halevi and Frank Wang and David J. Wu, http://eprint.iacr.org/2013/422

In a private database query system, a client issues queries to a database and obtains the results without learning anything else about the database and without the server learning the query. While previous work has yielded systems that can efficiently support disjunction queries, performing conjunction queries privately remains an open problem. In this work, we show that using a polynomial encoding of the database enables efficient implementations of conjunction queries using somewhat homomorphic encryption. We describe a three-party protocol that supports efficient evaluation of conjunction queries. Then, we present two implementations of our protocol using Paillier's additively homomorphic system as well as Brakerski's somewhat homomorphic cryptosystem. Finally, we show that the additional homomorphic properties of the Brakerski cryptosystem allow us to handle queries involving several thousand elements over a million-record database in just a few minutes, far outperforming the implementation using the additively homomorphic system.

_ 気になった論文２：Instantiating Random Oracles via UCEs, Mihir Bellare and Viet Tung Hoang and Sriram Keelveedhi, http://eprint.iacr.org/2013/424

This paper provides a (standard-model) notion of security for (keyed) hash functions, called UCE, that we show enables instantiation of random oracles (ROs) in a fairly broad and systematic way. Goals and schemes we consider include deterministic PKE; message-locked encryption; hardcore functions; point-function obfuscation; OAEP; encryption secure for key-dependent messages; encryption secure under related-key attack; proofs of storage; and adaptively-secure garbled circuits with short tokens. We can take existing, natural and efficient ROM schemes and show that the instantiated scheme resulting from replacing the RO with a UCE function is secure in the standard model. In several cases this results in the first standard-model schemes for these goals. The definition of UCE-security itself is quite simple, asking that outputs of the function look random given some 'leakage', even if the adversary knows the key, as long as the leakage does not permit the adversary to compute the inputs.