1
$\begingroup$

I've been reading Brakerski and Vaikuntanathan's Efficient Fully Homomorphic Encryption from (Standard) LWE.

When the authors discuss a small modulus p used for the transition from (n, log q) to (k, log p), how 'small' are they talking about?

If a database has two data types - TEXT (character arrays) and INTEGER (4 or 8 byte integral values), will 'p' ever be 'small' enough to transform an INTEGER value in-situ or in place? Or will the database need a new, larger integer?

I'm asking because I'm curious if an INTEGER value can be encrypted and homomorphically evaluated in a practical sense. I suspect not, but I want to ensure I'm not missing something obvious.

$\endgroup$
3
$\begingroup$

I'll do this backwards

If a database has two data types - TEXT (character arrays) and INTEGER (4 or 8 byte integral values), will 'p' ever be 'small' enough to transform an INTEGER value in-situ or in place?

No. Homomorphic ciphertexts are still way to big to be stored in a 32 or 64 bit integer. You would likely store the ciphertexts in a string (encoded in some way).

When the authors discuss a small modulus p used for the transition from (n, log q) to (k, log p), how 'small' are they talking about?

They give the following hint in the paper

To give a hint as to the magnitude of improvement, we typically set $k$ to be of size the security parameter and $p = poly(k)$. We can then set $n = k^c$ for essentially any constant $c$, and $q = 2^{n^\epsilon}$. We will thus be able to homomorphically evaluate functions of degree roughly $D = n^\epsilon = k^{c\cdot\epsilon}$ and we can choose $c$ to be large enough so that this is sufficient to evaluate the ($k$; $\log p$) decryption circuit.

So the size of $p$ is polynomial in the size of the security parameter. Note that the size of $q$ is $n^\epsilon$. $n$ is exponential in the size of the security parameter. So you go from exponential in the security parameter to polynomial, but we are still talking very, very large compared to a 32 or 64 bit integer. I believe ciphertexts in other FHE systems are on the order of kilobytes or megabytes and those were systems that improved upon this scheme.

$\endgroup$
  • $\begingroup$ Thanks mikeazo. That's basically what I thought (including, roughly, how large q could be), but wanted to ensure I was not missing something obvious. I almost asked if everything should be a BLOB for these types of databases, but it looks that way (unless you object, of course). $\endgroup$ – user10496 Nov 21 '13 at 23:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy