Hi Peter,
That's great news! Any thoughts on the license? Can you place it into public domain?
I am not 100% sure but I think it will be the same as the current NTRU implementation.
Did the attachment get lost?
Sorry. Here are the data extracted from our paper. The final version will be ready in a couple of days.
The data are based on ntru-443 with CCA-2. By moving to CPA, we may be able to save say 30% of computation. The ntru-743 is roughly 2.5x slower than ntru-443.
Cheers, Zhenfei
On Thu, May 26, 2016 at 1:35 AM, Peter Schwabe peter@cryptojedi.org wrote:
Zhenfei Zhang zzhang@securityinnovation.com wrote:
Hi Peter,
Hi Zhenfei, hi all,
We are working on a constant-time implementation of NTRU. We expect to release the source code this summer.
That's great news! Any thoughts on the license? Can you place it into public domain?
However, as far as I know, timing attacks are much more powerful against encryption algorithm (that uses long-lived key for multiple times), rather than KEMs (use ephemeral keys). Our proposal treats NTRU as a KEM so I think the timing attack is not so useful.
It's tricky; I agree that if you get only a single timing trace with the same key, it will be much harder to get useful information about the key than in a public-key encryption (or signature) setting where the private key is used many times. Then again, I also think that it will be very hard to prove that it's impossible to extract useful information about keys from timing on any platform. Maybe more importantly, Tor does not only have to be concerned about leaking the key, but also leaking de-anonymizing information. That's why Isis and I sat down and wrote a constant-time version of the sampling of the public polynomial in NewHope. My general take on this is that it's much easier to write constant-time code than to deal with the fallout caused by software that is vulnerable to timing attacks.
Please see the attached for some benchmark results.
Did the attachment get lost?
We are working on the camera-ready version of the paper. The final version should be out soon. Also note that we are using an IND-CCA-2 secure version of NTRU. The performance can be further improved by switching to the IND-CPA secure version. IND-CPA is enough to provide channel security, provide that the ciphertext is accepted for only once for a given key. (This may open doors to some DoS attack.) As far as I can tell, the NewHope and NTRU-prime all uses CPA secure encryption algorithms.
Definitely true for NewHope.
Here's what my answers would be to your questions:
It would be nice to have a final decision on a. shall we use non-production form
Would be interesting to see benchmarks of both.
b. shall we remove the IND-CCA-2 feature
Again, it would be interesting in a larger context to have benchmarks of both; the Tor handshake should be fine with IND-CPA.
c. shall we use ntru-743/887 to build a sufficiently large margin just
like
NTRUprime
Definitely. As I wrote in my previous mail, in NewHope we went for a much larger margin than NTRUprime did; I would probably feel better with 887, but for long-term security (and this is what the whole thing is about), 743 is a must-have.
Cheers,
Peter
tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
-
Zhenfei Zhang