Hi Peter,Â
Thanks for such a nice overview of current discussions. Just want toÂ> - NTRU is around for the longest time and has, even with high-security
> Â parameters, fairly short messages. However, existing software
> Â implementations (at least the ones in SUPERCOP) are highly vulnerable
>ÂÂ to timing attacks. Key generation (with protection to against timing
> Â attacks) is, as far as I can tell, fairly expensive.
We are working on a constant-time implementation of NTRU. We expect toÂ
release the source code this summer. 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).
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.
> What I'm missing in the discussion are benchmarks of NTRU and NTRUprime (in
> the context of key exchange).
> What I'm missing in the discussion are benchmarks of NTRU and NTRUprime (in
> the context of key exchange).
Please see the attached for some benchmark results. 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.
> Would it help the discussion at this point to fix NTRU parameters, produce
> an optimized implementation of NTRU (not production-quality code for Tor, but
> something to obtain benchmarks) and compare performance of NewHope, NTRU, and
> NTRUprime in an ephemeral key exchange? This would be a nice project for a
> Ph.D. student.
It would be very interesting indeed. We need to fix the parameter sets for NTRU.
Currently we haveÂ
1. ntru-443 with product form, providing 128Âpre-quantum/post-quantumÂsecurityÂ
2. ntru-743 with product form, providing 256Âpre-quantumÂand >128Âpost-quantumÂsecurity
3. ntru-887 with non-product form, providing 256Âpre-quantumÂsecurity
And all of those parameter sets uses SHA256 rather than SHA-3 as suggested
by the community.Â
It would be nice to have a final decision on
a. shall we use non-production form
b. shall we remove the IND-CCA-2 feature
c. shall we use ntru-743/887 to build a sufficiently large margin just like NTRUprime
Cheers,
Zhenfei
On Tue, May 24, 2016 at 6:32 PM, Peter Schwabe <peter@xxxxxxxxxxxxxx> wrote:
bancfc@xxxxxxxxxxxxxxx wrote:
Hi all,
> Some great developments in lattice-based crypto. DJB just released a paper
> on NTRU Prime:
Let me just also throw in my 2 cents:
As far as I can tell, there are now 5 approaches to post-quantum key
exchange that are discussed (or at least have surfaced) in this thread:
- NTRU
- NewHope
- NTRUprime
- McEliece
- SIDH
In some of the posts I got the impression that there are considerations
for some sort of "algorithm agility" in the key exchange. This can mean
two things:
- runtime algorithm agility, such that a client can choose what
 algorithm to use according to some strategy; or
- upgrading algorithm agility, which means that for each version number
 of a client, it is very clear which algorithm it will use, but the key
 exchange supports (easy) upgrading to better algorithms with
 increasing version numbers.
In my opinion, the second approach is extremely important, in particular
because at the moment we certainly want some sort of PQ key exchange,
but are quite uncertain about what approach will prove best in the long
run.
I'm not really sure whether anybody really suggested the first approach,
but just in case, I think it's a terrible idea. If the decision of what
algorithms to use is left to users, they will certainly end up making
worse choices than experts; if it's left to randomness, users inevitably
get the worst out of the set from time to time. I simply cannot think of
any strategy that lets the user win here.
Now, out of the 5 proposals, my impression is that McEliece with binary
Goppa codes has been killed as an idea for key exchange in Tor and that
whenever somebody mentions it again, Isis will just shout "KEYSIZE" to
make sure that it remains dead.
I can see good reasons for each of the first three (lattice-based)
proposals:
- NTRU is around for the longest time and has, even with high-security
 parameters, fairly short messages. However, existing software
 implementations (at least the ones in SUPERCOP) are highly vulnerable
 to timing attacks. Key generation (with protection to against timing
 attacks) is, as far as I can tell, fairly expensive.
- NewHope is explicitely designed for ephemeral key exchange (not
 public-key encryption), i.e, for the operation that is required. It
 offers best performance and, as Isis pointed out, the paramters we
 propose have the largest security margin against all known attacks.
 Disadvantage (price to pay for the security margin): somewhat longer
 messages.
- NTRUprime is much less conservative than NewHope in its parameter
 choices against known attacks but offers "defenses" against attacks
 that may or may not work against NewHope and NTRU.
 The advertisement of those defenses is a pretty good job of the
 marketing department: the wording suggests that NTRUprime is, at the
 same bit-security level, at least as secure as NTRU or NewHope, but
 then has those defenses as additional safeguards. This is not quite
 true: NTRUprime operates in a different mathematical structure, which
 may in the long run prove more secure, it may also prove less secure
 and it could turn out that the "defenses" against hypothetical attacks
 turn out to be weaknesses against other attacks.
 Having said that, I really like the ideas of the NTRUprime paper and
 much more often than not have Dan and Tanja been right with their
 intuition for cryptographic design.
What I'm missing in the discussion are benchmarks of NTRU and NTRUprime (in
the context of key exchange). For NTRUprime there is not even a proposal for
ephemeral key exchange as needed in Tor; however, I assume that it's not too
hard to replace NTRU operations (from the NTRU proposal) by NTRUprime
operations. Also (please correct me if I'm wrong), for NTRU it's not clear
what parameters to use and there is no optimized and timing-attack protected
implementation.
Would it help the discussion at this point to fix NTRU parameters, produce
an optimized implementation of NTRU (not production-quality code for Tor, but
something to obtain benchmarks) and compare performance of NewHope, NTRU, and
NTRUprime in an ephemeral key exchange? This would be a nice project for a
Ph.D. student.
Now, then there is SIDH: I really like SIDH, not so much for the shorter
public keys (that's nice, but it's not like a difference of an order of
magnitude), but because of two other reasons:
1.) It is a completely different approach and even if all
  non-standard lattice crypto falls, SIDH may survive.
2.) It's offering the same functionality as (EC)DH right now; both
  parties can compute their public keys without having received the
  public key of the other party. This is a great feature for protocol
  design and for migrating existing DH-based protocols to a
  post-quantum setting.
However, I don't think that SIDH is ready for use at the moment. The
reason is not only that it's about 300x slower than ECC, the reason is
that security is really not understood at all. While probably everybody
in the crypto community expects some progress in lattice attacks over
the next few decades, I don't think that anybody seriously expects a
polynomial-time algorithm that breaks, for example, Ring-LWE with
suitably chosen paramters. A polynomial-time algorithm to break SIDH
would clearly be a major breakthrough with an immediate-accept at any of
the big crypto venues, but I would not want to really bet anything
important (like my life in freedom) against this happening.
I talked to Michael Naehrig (co-author of the Crypto paper this year
implementing SIDH) two days ago and mentioned that SIDH popped up in
this discussion as a possible approach for Tor. His reaction was roughly
along the lines of "We say in our paper that you shouldn't use this, and
very certainly not in Tor".
So, I hope that SIDH will survive in the long run, after serious
cryptanalytic effort trying to break it; I hope that it will become
faster by, say, a factor of 100 (that's not totally inconceivable,
pairings took minutes to compute at the beginning, now we're below a
millisecond) and if this happens then Tor should migrate to SIDH. Not
now.
As I said, just my 2 cents.
Cheers,
Peter
_______________________________________________
tor-dev mailing list
tor-dev@xxxxxxxxxxxxxxxxxxxx
https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev