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.

Improve this question
$\endgroup$
9
  • $\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
    Commented Aug 8, 2015 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
    Commented Aug 8, 2015 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
    Commented Aug 8, 2015 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
    Commented Aug 10, 2015 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
    Commented Aug 10, 2015 at 21:01

1 Answer 1

Reset to default
-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.

Improve this answer
$\endgroup$
3
  • $\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
    Commented Aug 10, 2015 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
    Commented Sep 21, 2015 at 15:40
  • 2
    $\begingroup$ It says its easy to generate but doesn't elaborate $\endgroup$
    – Alan Wolfe
    Commented Sep 21, 2015 at 15:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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