4
$\begingroup$

The site below explains that part of doing homomorphic encryption, you need to generate a vector of random numbers that have the property that its dot product against a randomly generated bit vector mod 2 has an absolute value less than some amount (but greater than zero).

http://windowsontheory.org/2012/05/02/building-the-swiss-army-knife/

Is there any way to generate such a vector other than brute force? Seems like it could take a long time for a large vector.

$\endgroup$
  • $\begingroup$ Your question seems to be about full-homomorphic encryption, which is much more difficult to realize than simple homomorphic encryption. Maybe you should indicate this more clearly in your question. $\endgroup$ – Chris Aug 8 '15 at 7:50
  • $\begingroup$ It isn't, I'm just trying to figure out if there's a better way to generate the vector with this property than brute force (: $\endgroup$ – Alan Wolfe Aug 8 '15 at 14:10
  • $\begingroup$ One does not need such a vector to do homomorphic encryption. Therefore people (like me) reading your question will wonder what you are talking about. I think if you specify 'full-homomorphic encryption', then it will be easier to understand why you need such a vector. $\endgroup$ – Chris Aug 8 '15 at 15:01
  • $\begingroup$ Is this site creating this homomorphic scheme or it is describing it and not citing the source? $\endgroup$ – Hilder Vitor Lima Pereira Aug 10 '15 at 20:45
  • 1
    $\begingroup$ It's basically a very summarized overview of Craig Gentry's paper crypto.stanford.edu/craig/craig-thesis.pdf $\endgroup$ – Alan Wolfe Aug 10 '15 at 21:01
-1
$\begingroup$

After thinking about it here's what I think. Let me know what you think.

First, I generate a random vector of floats and figure out what the dot product is.

I then pick one of the elements of the float vector that correspond to a 1 in the binary array (randomly?), and then adjust that value the necessary amount to make the dot product come out to the value I want.

Thoughts? Seems like it should be ok.

$\endgroup$
  • $\begingroup$ Also wanted to note, when doing this I realized a naiive implementation could cause some values in the vector to be pegged at 1 or -1 and that could let someone know that the key has a 1 in that bit index. I'm currently thinking maybe only allowing to use up to half of the headroom available when adjusting an index to adjust the dot product. Might be issues with that too though but not sure yet. Like indices that correspond to a 1 in the secret key may tend to have higher absolute values maybe. $\endgroup$ – Alan Wolfe Aug 10 '15 at 5:25
  • 2
    $\begingroup$ Why don't you just read the paper and see exactly how it's done, instead of guessing? $\endgroup$ – pg1989 Sep 21 '15 at 15:40
  • 2
    $\begingroup$ It says its easy to generate but doesn't elaborate $\endgroup$ – Alan Wolfe Sep 21 '15 at 15:43

Your Answer

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

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