[cryptography] Fwd: [ECCC] New Paper published

Noon Silk noonslists at gmail.com
Tue Aug 9 20:07:50 EDT 2011

---------- Forwarded message ----------
From:  <eccc at eccc.hpi-web.de>
Date: Wed, Aug 10, 2011 at 3:13 AM
Subject: [ECCC] New Paper published
To: noonslists at gmail.com

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

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

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

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

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."

More information about the cryptography mailing list