5
$\begingroup$

Much like this question: Public key in fully homomorphic encryption over the integers

I am also reading I'm reading Fully Homomorphic Encryption over the Integers, but I'm working on implementing the symmetric key implementation.

It says on the first page:

The key is an odd integer, chosen from some interval $p ∈ [2^{η−1},2^η)$.

Where $η$ is the number of bits in the key and $p$ is the secret key.

Why is it that the high and low bit must be set to 1?

I've read the answer to the other question in regards to the low bit (the key being odd), but I don't see how it applies in this case so am a bit stumped.

Improve this question
$\endgroup$
7
  • $\begingroup$ I have a guess about why the high bit has to be set... is it to prevent the key from ever being a small number, which is more easily figured out? $\endgroup$
    – Alan Wolfe
    Commented Aug 26, 2015 at 15:47
  • $\begingroup$ You asked, you commented, you answered... XD But in wich part of the paper it is said that the high bit must be one? If we chose $p$ inside this interval, we don't need to care about it, because $p$ will already be big enough. In fact, saying that $p$ has $η$ bits and saying $p$ is a integer inside $[2^{η−1},2^η)$ means the samething... $\endgroup$
    – Hilder Vitor Lima Pereira
    Commented Aug 28, 2015 at 0:10
  • $\begingroup$ Why not say that the key needs to be between 0 and 2^n then? Why have a lower bound at all? $\endgroup$
    – Alan Wolfe
    Commented Aug 28, 2015 at 0:24
  • 1
    $\begingroup$ Because the scheme is not secure if we use a small $p$ as the key. Also, the maximum "supported noise" is bounded by $\frac{p}{2}$ and it impacts on the number of homomorphic operations we can do... $\endgroup$
    – Hilder Vitor Lima Pereira
    Commented Aug 28, 2015 at 1:04
  • $\begingroup$ Interesting points! Do you happen to know what size of p is considered secure? I can ask a new question if you prefer. $\endgroup$
    – Alan Wolfe
    Commented Aug 28, 2015 at 1:08

1 Answer 1

Reset to default
0
$\begingroup$

It turns out that just like the question linked to in the question, the key needs to be an odd number so that the encrypted number doesn't have the same parity (odd or even-ness) as the plain text value. When it has the same parity, the encryption failed because you can tell exactly what the plaintext bit was!

As for why the high bit needs to be set, I'm going to just assume that it's to make sure the key is large, which helps security. If someone knows differently, please inform me!

Improve this answer
$\endgroup$

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.