[148981] in cryptography@c2.net mail archive
Re: [Cryptography] Advances in homomorphic encryption
daemon@ATHENA.MIT.EDU (Landon Hurley)
Thu Jan 9 17:30:22 2014
X-Original-To: cryptography@metzdowd.com
Date: Thu, 09 Jan 2014 17:20:11 -0500
From: Landon Hurley <ljrhurley@gmail.com>
To: Eric Mill <eric@konklone.com>
In-Reply-To: <CANBOYLXdkW=Y6ag41gTes-V8u1tKgyv4+g2Uzch=MZrW1gmzPQ@mail.gmail.com>
Cc: "cryptography@metzdowd.com List" <cryptography@metzdowd.com>
Errors-To: cryptography-bounces+crypto.discuss=bloom-picayune.mit.edu@metzdowd.com
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA512
On 01/09/2014 04:40 PM, Eric Mill wrote:
> That's really cool. The homepage for cryptdb, for anyone who wants
> to follow it, is http://css.csail.mit.edu/cryptdb/, and they have
> a little -announce list you can sign up for.
> =
> It's true that SQL is not at the vanguard of database practices =
> anymore, though one of the things I'm wondering is if homomorphic =
> encryption has enough versatility to cover small enough operations
> that be built up into arbitrarily complex ones.
Using the original implementation by Gentry, the system has to
do the equivalent of a clean-up operation after performing the
operation, before another operation can be performed. This:
> It is limited because each ciphertext is noisy in some sense, and =
> this noise grows as one adds and multiplies ciphertexts, until =
> ultimately the noise makes the resulting ciphertext =
> indecipherable.) He then shows how to modify this scheme to make it
> bootstrappable=97in particular, he shows that by modifying the =
> somewhat homomorphic scheme slightly, it can actually evaluate its
> own decryption circuit, a self-referential property. Finally, he =
> shows that any bootstrappable somewhat homomorphic encryption =
> scheme can be converted into a fully homomorphic encryption through
> a recursive self-embedding. In the particular case of Gentry's
> ideal-lattice-based somewhat homomorphic scheme, this bootstrapping
> procedure effectively "refreshes" the ciphertext by reducing its
> associated noise so that it can be used thereafter in more
> additions and multiplications without resulting in an =
> indecipherable ciphertext.
refers to the clean-up (I believe, stolen from wikipedia, but it seems
to confirm what I recall). There's a niggling thought that there's some
latitude (maybe 3 or 4) in number of operations, obviously depending on
how much noise is introduced with each operation and the power of the
noise removal. So while plausible to chain this into a complex machine
(like something to completely compute your taxes), I presume the
overhead would start to really hit efficiency if you were trying to do
something like keeping the books of a large company. That said, I know
Paillier's public key system used homomorphic encryption, so I suppose
it all depends on what the desired end state is. Other than reading
Gentry's thesis a couple of years ago though, I haven't really kept pace
with this area.
landon
- -- =
Violence is the last refuge of the incompetent.
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.11 (GNU/Linux)
iQIcBAEBCgAGBQJSzyCbAAoJEDeph/0fVJWsHigP/RZO8E9JSeOJ4Q0nbLvWu3/6
e3GywR0hwRf8yb5PkQTxPdyFnxDV+yqFN3IBS0IfL3ela18FXP1zafZYbF3BXDRj
JwGl5uPOMZN/XCz8atZIPZ7TYLZUklrrFAM6aOIKW6Fr7N6Qy1zRRAKktf6rznU5
xSTDXyjEyHUuilxOurlrfCGd/XZJacjpoHDlE2EsvV8wTP+4M3C9W4QdkThlkUdD
x2bw5nttI2oJzday7V8KAKCeyvWKr03+RzsClnGxD9zSd5BTAukn+k24LXYBlVem
fOxDpdSkTsnZQG7oqtwdI/JOKLSwS9zpEU2KlkeYZJOrzASWd696SkKZ6rVVIAF8
bTTRxLr4rzMYtrPmtYNJr+zpxykz6+dJZijluSB45N0nnBlkMi1iAa2vOXCAvKkT
SXgHe6mGDkpkY4Av3thyKteBkWBsTaU4Kr0MghorezAFDOfTQxqgx8vQ6QgpeoeT
PjE+S2OQ1hItMvZLZBgaeOKPjXRUw/RTuj49Bs9CcFYnQXD2z/eWEYekklcZWriC
XvWuWRg2y3WQpLS9pqBCW72SlLUEQeIGtKxuQofNyhf8pSKoXmr5XUOQFdH6Z2Ve
Eg4N/UgrFEiW+3sN1HvpDWWUUu0tChzcUipaJpwm27XpN3K1tladklz3VSNx+Rwa
naW0GN8k1MjEz4KiTu6p
=3DTMIB
-----END PGP SIGNATURE-----
_______________________________________________
The cryptography mailing list
cryptography@metzdowd.com
http://www.metzdowd.com/mailman/listinfo/cryptography
