Gaussian Sampling

[kalyan-kumar]

According to the paper, the polynomials sampled must be from an error distribution, like the Gaussian Distribution. But in this implementation, the random polynomial seems to be sampled from a uniform distribution. Can someone explain why it was done so, or am I missing something here?

[yarkindoroz]

Dear Kalyan, In the implementation our normal setting was {%25, %50, %25} for {-1, 0, +1} and our implementation was like that. Later for a more generic B we used the NTL's random number generator which is uniform. We should have made a note in the code sorry for the confusion. The main reason was the practicality. At the time of the implementation the ciphertext required sampling size in the order of log{q}. There are some algorithms such as ziggurat and I find some implementation of the algorithm. However, it was causing the encryption to take too much time. In order to test our codes in a timely manner we switch it to uniform. Now there might be better Gaussian sampling algorithms which can be implemented or ziggurat implementations that might faster than before. An important note !! Another reason we did not pursue it is that it does not effect security, actually it should be even more secure since you are using more noise space. Furthermore, when you multiply 2 ciphertext with a gaussian distribution, its noise distribution starts turning to uniform distribution (basically there is a path from gaussian to uniform). In a few multiplicative levels, the noise in a ciphertext actually becomes a uniform distribution. The noise analysis still holds as well. Since the above paragraph is true, for practical reasons we just used the NTL's function. I hope it is clear. Do you still need a gaussian? If so I might try and find ziggurat. Best, Yarkin

…

On Thu, Feb 9, 2017 at 5:43 AM, Kalyan Kumar ***@***.***> wrote: According to the paper, the polynomials sampled must be from an error distribution, like the Gaussian Distribution. But in this implementation, the random polynomial seems to be sampled from a uniform distribution. Can someone explain why it was done so, or am I missing something here? — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#1>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AQ5A6aFDQQiV7qjibwfLGLdnE3jS-CoFks5rau3agaJpZM4L79-l> .

-- Yarkın Doröz Master Student, Computer Science and Engineering Program Sabanci University Faculty of Engineering and Natural Sciences Tuzla 34956, Istanbul, Turkey

[kalyan-kumar]

Thank You so much Yarkin for the detailed answer, explaining everything so clearly :).

Actually, I am trying to implement modules that are trivially used in all Lattice-based cryptography primitives. I was unable to find a Discrete Gaussian sampler's implementation anywhere, finally ending up here. I would be really thankful if you know of any library or simple implementations of the primitives, so that any public key encryption schemes, functional encryption schemes could be conveniently implemented in software. Thank you again :)

[yarkindoroz]

There are other FHE implementations. One of them is Helib. Here is the link: https://github.com/shaih/HElib It seems there is a guassian sampling under NumTh.cpp. Not sure how efficient, but I believe it should be since it is a decent library. For Lattice operations, I think NTL is good since it has vector, matrix and polynomial types with multiplication and addition operations.

…

On Fri, Feb 10, 2017 at 5:00 AM, Kalyan Kumar ***@***.***> wrote: Thank You so much Yarkin for the detailed answer, explaining everything so clearly :). Actually, I am trying to implement modules that are trivially used in all Lattice-based cryptography primitives. I was unable to find a Discrete Gaussian sampler's implementation anywhere, finally ending up here. I would be really thankful if you know of any library or simple implementations of the primitives, so that any public key encryption schemes, functional encryption schemes could be conveniently implemented in software. Thank you again :) — You are receiving this because you commented. Reply to this email directly, view it on GitHub <#1 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AQ5A6X3wWvMFDM5tiVFI97l1rBIfhDYlks5rbDUmgaJpZM4L79-l> .

-- Yarkın Doröz Master Student, Computer Science and Engineering Program Sabanci University Faculty of Engineering and Natural Sciences Tuzla 34956, Istanbul, Turkey

[kalyan-kumar]

Thank You Yarkin. I am not aware of the Box-Muller method that is mentioned in that implementation. I will look into it.