0
$\begingroup$

In one of the first FHE schemes by Gentry, the KeyGen algorithm is defined as follow:

For a security parameter $\lambda$, set $N = \lambda ^ 2, P = \lambda ^ 2, Q = \lambda ^ 5$.

KeyGen$(\lambda)$: Generate a random $P$-bit odd integer, $p$. A set $\vec{y} = \{ y_1, y_2, \ldots, y_\beta\}$ is generated with $y_i$ bits. There must exist a sparse subset $S \subset \vec{y}$ of $\alpha$ elements such that $\sum\limits_{y_j \in S} (y_j) = \frac{1}{p} \mod 2$.

Set $sk$ to be a binary encoding of the subset $S$, where $s = (0,1)^\beta$. Set $pk \leftarrow (p, \vec{y})$.

My problem here is with the subset S. Especially, for a large enough security parameter, the random integer $p$ is so large that I don't see how to print its inverse on my terminal. Are there some specific libraries in Python or C to handle this kind of inverse? I have tried to shift it by the size of p in base 10 but the problem remains as I can't convert p to float/double before dividing.

This may not be the most accurate forum for this question, and I apologize in advance if it is not.

$\endgroup$

closed as off-topic by fkraiem, Maarten Bodewes, e-sushi Nov 12 '18 at 2:07

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Programming questions are off-topic even if you are writing or debugging cryptographic code. Unless your question is specifically about how the cryptographic algorithm, protocol or side-channel (mitigation) works, you should look into asking on Stack Overflow instead." – fkraiem, e-sushi
If this question can be reworded to fit the rules in the help center, please edit the question.

2
$\begingroup$

The first $k$ digits on the right of the decimal point of the representation of $1/p$ in base $b$ also are the representation in base $b$ of $\left\lfloor b^k/p\right\rfloor$ left-padded to $k$ digits with zeroes.

If we want to perform computations to $k$ places after the decimal point for quantity $x\in\Bbb R$, we can use the integer quantity $\left\lfloor b^k\,x\right\rfloor$, or better $\left\lfloor b^k\,x+\frac12\right\rfloor$.

Any language (e.g. python) or library (e.g. GMP) capable of handling arbitrary precision integers let you make the necessary computations.

E.g. in python 3,

p = 3**161
print("{0:b}".format(2**700//p))

yields a 445-bit bitstring which, padded with 255 0 on the left, and then 0. on the left, is $1/p$ in binary to 700 binary places.

$\endgroup$
  • $\begingroup$ hmmm your example actually works but for my case with larger p (especially the example above of 16k bits) I simply get 0... And this size in bits can be potentially bigger than 16k (I tried both on my IDE and in a terminal with different versions of python 3) $\endgroup$ – Robin S. Nov 9 '18 at 8:34
  • 1
    $\begingroup$ Oh sorry I think I understood my mystake, I was keeping 2**700 for my bigger p but of course I need to update it... Thanks for your help! $\endgroup$ – Robin S. Nov 9 '18 at 8:42

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