Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer
    
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). –  jww Nov 21 '13 at 23:38

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.