A couple of questions..

[QRCS-CORP]

Hi, First off, thanks for this great work.. I've been translating this to C# (and eventually java), and I have a couple of questions. Do you have the implementation of Knuth Yao used to create the tables, I'd like to make n, q, and sigma assignable, and generate them on initialization based on a parameter set. After binary encoding of a message, payload size is limited to 32 or 64 bytes, am I reading that right?

Anyways, thanks again John

[ruandc]

Hi,

Computation of the tables is easy. How the lookup table was computed:

1. Use a standard mathematics processor (gp/pari or magma or .. ) and generate the probability vectors for a given discrete Gaussian distribution.
2. Run the bit-by-bit scan based Knuth-Yao algorithm. This algorithm is already there in the code. In the code it starts from an initial distance d and then scans from the column number 9. To generate the lookup table, start the bit by bit scan from the first column and initialize d to zero. In this computation of the lookup table, 8-bit random numbers are input to the algorithm. So, run the algorithm for all possible 256 values of 8-bit random numbers and load the output of the Knuth-Yao algorithm in the desired lookup table.

The current tool supports two different parameter sets. For the encoded message, each coefficient can only contain a single bit. Therefore, for n=256 the payload 32 bytes, while for n=512 the payload is 64 bytes.

Ruan

[QRCS-CORP]

Hi Ruan, I published the first version: https://github.com/Steppenwolfe65/Ring-LWE The straight translation is in the 'Original' folder. Parallelized the FFT, (I'm generating about 900 keys p/s on my quad core), and made it very easy to use. I plan to revisit this next week, and look into Knuth-Yao.. I may have another question then..

Best regards, John

[ruandc]

Hi John,

Nice! I didn't look at your code, but I am curious about how you generate random numbers for the Knuth-Yao algorithm?

Ruan

On 06/09/2015 12:58 AM, Steppenwolfe65 wrote:

Hi Ruan, I published the first version: https://github.com/Steppenwolfe65/Ring-LWE The straight translation is in the 'Original' folder. Parallelized the FFT, (I'm generating about 900 keys p/s on my quad core), and made it very easy to use. I plan to revisit this next week, and look into Knuth-Yao.. I may have another question then..

Best regards, John

---

Reply to this email directly or view it on GitHub: https://github.com/ruandc/Ring-LWE-Encryption/issues/1#issuecomment-110166769

[QRCS-CORP]

Hi Ruan, Default uses RngCrypto, (windows random generator), but this is assignable; can use any of the Prng's from the main project including a passphrase-digest generator, or a symmetric cipher ctr..

John

[QRCS-CORP]

Hi Ruan, I had time to work on this over the weekend, with some good results.. I parallelized the key generation and encryption routines, and added the prng's from my main library. With the 256 parameter, I am getting speeds of over 5 thousand keys per second, 2700 encryptions, and over 14k decryptions p/s, the 512 parameter yields about 60% of those numbers. This is on a 5yr old Acer with 2gb of memory, I'm betting a proper server could get 10 times those rates. So, speed is good, (for C#), and now I am thinking about parameters again.. what I need is a parameter set that can encrypt 128 bytes, and is at least 256 bits of security. A third 'fixed' parameter set is fine for now, as long as it can handle the larger payload.

So the questions are these: Can you recommend a parameter set (n, q, sigma) that would qualify? I think I know how to generate the tables via your description, but my reluctance is that I don't want to make a mistake, and produce something that is insecure.. if you had said tables and constants from previous work, or have any helpful links, that would be a tremendous help, if not, who/where would I ask to check my work? Anyways, thanks for your time, and this great code and research, your efforts have made mine possible..

Best regards, John

[ruandc]

Hi,

(n, q, s) = (512, 12289, 12.18) has security compatible with AES256,

s = sqrt(2Pi) \ sigma. Ruan

On Mon, Jun 15, 2015 at 9:40 PM, Steppenwolfe65 notifications@github.com wrote:

Hi Ruan, I had time to work on this over the weekend, with some good results.. I parallelized the key generation and encryption routines, and added the prng's from my main library. With the 256 parameter, I am getting speeds of over 5 thousand keys per second, 2700 encryptions, and over 14k decryptions p/s, the 512 parameter yields about 60% of those numbers. This is on a 5yr old Acer with 2gb of memory, I'm betting a proper server could get 10 times those rates. So, speed is good, (for C#), and now I am thinking about parameters again.. what I need is a parameter set that can encrypt 128 bytes, and is at least 256 bits of security. A third 'fixed' parameter set is fine for now, as long as it can handle the larger payload.

So the questions are these: Can you recommend a parameter set (n, q, sigma) that would qualify? I think I know how to generate the tables via your description, but my reluctance is that I don't want to make a mistake, and produce something that is insecure.. if you had said tables and constants from previous work, or have any helpful links, that would be a tremendous help, if not, who/where would I ask to check my work? Anyways, thanks for your time, and this great code and research, your efforts have made mine possible..

Best regards, John

— Reply to this email directly or view it on GitHub https://github.com/ruandc/Ring-LWE-Encryption/issues/1#issuecomment-112183793 .

Regards, Ruan de Clercq Mobile: +32 048 605 8774 ruandeclercq@gmail.com

[QRCS-CORP]

That's just it though.. some of the ciphers I've developed are much stronger than aes256, (like RHX, which uses the rijndael transform, but the key schedule is hkdf powered by skein, blake, keccak or sha-2, and assignable rounds of 10 to 38). Minimum key size is 96 bytes, plus vector, so I need 128 bytes of payload.. So, are there any configurations with n=1024?

[ruandc]

Hi,

I think no one has tried to find a parameter set that gives exact 256 bit security. Papers say they use this parameter set for "high-security". More and more cryptanalytic attacks decreased bit-security.

Sorry I typed wrong in the previous email. The n=512 parameter set actually provides around 240 bits of security.

On Tue, Jun 16, 2015 at 4:51 PM, Steppenwolfe65 notifications@github.com wrote:

That's just it though.. some of the ciphers I've developed are much stronger than aes256, (like RHX, which uses the rijndael transform, but the key schedule is hkdf powered by skein, blake, keccak or sha-2, and assignable rounds of 10 to 38). Minimum key size is 96 bytes, plus vector, so I need 128 bytes of payload.. So, are there any configurations with n=1024?

— Reply to this email directly or view it on GitHub https://github.com/ruandc/Ring-LWE-Encryption/issues/1#issuecomment-112458955 .

Regards, Ruan de Clercq Mobile: +32 048 605 8774 ruandeclercq@gmail.com

[QRCS-CORP]

Hi Ruan, Thanks anyways.. I'll do some research and see what I can come up with..

Regards, John