[Cryptography] Advances in homomorphic encryption

[Landon Hurley]

-----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—in 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
=TMIB
-----END PGP SIGNATURE-----