---------- Forwarded message ---------- From: <[email protected]> Date: Wed, Aug 10, 2011 at 3:13 AM Subject: [ECCC] New Paper published To: [email protected]
Hello, a new Paper has been published at http://eccc.hpi-web.de: TR11-109 | Efficient Fully Homomorphic Encryption from (Standard) LWE Authors: Zvika Brakerski, Vinod Vaikuntanathan Abstract: We present a fully homomorphic encryption scheme that is based solely on the (standard) learning with errors (LWE) assumption. Applying known results on LWE, the security of our scheme is based on the worst-case hardness of ``short vector problems'' on arbitrary lattices. Our construction improves on previous works in two aspects: 1. We show that ``somewhat homomorphic'' encryption can be based on LWE, using a new {\em re-linearization} technique. In contrast, all previous schemes relied on complexity assumptions related to ideals in various rings. 2. We deviate from the ``squashing paradigm'' used in all previous works. We introduce a new {\em dimension-modulus reduction} technique, which shortens the ciphertexts and reduces the decryption complexity of our scheme, {\em without introducing additional assumptions}. Our scheme has very short ciphertexts and we therefore use it to construct an asymptotically efficient LWE-based single-server private information retrieval (PIR) protocol. The communication complexity of our protocol (in the public-key model) is $k \cdot polylog(k)+\log |DB|$ bits per single-bit query (here, $k$ is a security parameter). Keywords: learning with errors, public key encryption, fully homomorphic encryption Visit http://eccc.hpi-web.de/report/2011/109 for details and download. ---------------------------------- You are receiving this email because your are subscribed to the ECCC-Newsletter. To unsubscribe visit http://eccc.hpi-web.de/newsletter/9bbe4a2c267ee4a1b4290639726cfc04. -- Noon Silk Fancy a quantum lunch? http://groups.google.com/group/quantum-lunch?hl=en "Every morning when I wake up, I experience an exquisite joy — the joy of being this signature." _______________________________________________ cryptography mailing list [email protected] http://lists.randombit.net/mailman/listinfo/cryptography
