Subject: Re: [Cfrg] Fwd: I-D Action: draft-yonezawa-pairing-friendly-curves-01.txt

From: Marek Jankowski <[email-masked]>
Date: Mon, 1 Apr 2019 04:50:08 +0200

Dear Uri,

Please allow me to step in and share my opinion regarding developing non
quantum secure schemes.

A. As Mike says, we don't know much about current post-quantum schemes,
even against a classical attacker. Due to their theoretical complexity, it
may take dozens of years to develop considerable trust in such schemes. In
the meantime it is worthwhile to develop (classically-)strong PK schemes
with cryptographic advantages. What I mean is - until PQ schemes are made
secure, we will use classical schemes; I think the capabilities pairings
offer (e.g. IBE, short and aggregateable signatures) are appealing enough
to justify standardization.

B. > data produced in year x-k (encrypted by good and intercepted by bad
players) may still have value in year x, x+1, etc.
I agree; yet, given the choice to encrypt data using a provably
(classically-)secure scheme, and a non proven PQ scheme, I would prefer the
former: we don't know if current PQ schemes may be broken by a classical
computer before year x. Classical computers are available today to millions
of potential bad guys, while even when quantum computers are built, it
makes sense that for some time very few people will have access to one.
It is also worth mentioning that pairing based crypto offers signature
schemes with nice qualities (see the recent I-D by Boneh et al.); for
signatures it is perfectly acceptable to use quantum-vulnerable schemes
today. (But not in year x.)

C. Post quantum crypto is generally much more resource intensive than
classical crypto (including pairings), in both complexity and traffic.
Therefore pairing based cryptography works better for lightweight
processors. Data encrypted by such devices is likely to be irrelevant in
20-30 years after transmission (e.g. IoT, smart cars). So it is OK to use
classical crypto there.

D. Pairings are getting into practical use. Examples are several RFCs
(5091, 6508, 6539, 6509), Cloudflare's GeoKey Manager and more, as listed
in the I-D. The rising popularity strengthens the need for a well thought
out standard/set of standards.

To conclude, I believe that developing PQ crypto and classical PK crypto
should be done in parallel, and not one instead of the other. While using
non quantum secure chemes will threaten one's data once a quantum computer
is built, I think it should not slow down research of new crypto
capabilities.

Regards,
Marek.

On Fri, Mar 29, 2019 at 5:59 PM Blumenthal, Uri - 0553 - MITLL <
[email-masked]> wrote:

> It doesn’t but we did already discuss that, and good arguments were put
> forth for continuing the work despite this. (See the mail archive, I guess.)
>
> So far I’ve found this (which IMHO doesn't look like a set of good
> arguments):
>
> >  1) Pairing-based crypto threw open the doors to lots of nice new crypto
> possibilities, enabling stuff that we couldn't do before
> >  2) Gradually post-quantum crypto is catching up and demonstrating
> capabilities that mirror some (but not all) of these achievements
> >  3) Post-quantum crypto depends on hard problems that it will take time
> to develop full confidence in, even in regard to attacks from
> non-quantum computers
> >  4) In the meantime (and that could be quite a long time) it makes
> perfect sense to proceed with the development and standardization
> >       of non-quantum safe methods.
> >  5) In the year x out pops a quantum computer. However in the year x-1
> out popped well-developed and well-understood
> >       post-quantum crypto replacements in which we can have complete
> confidence.
>
> Re. (1): sure, it would do great stuff, but for how long? What’s the
> expected lifetime of an algorithm/protocol/approach that would justify
> efforts spent on formalizing, implementing, and deploying it? What
> application field or use case would support it?
>
> Re. (2) and (3): sure, but irrelevant with regard to the main question -
> is it worth developing (for deploying later, as there's an inevitable lag)
> non-quantum-resistant crypto now?
>
> Re. (4): I see no logic in that statement. We don't have full confidence
> in post-quantum hard problems, therefore we should standardize methods that
> we know are not quantum-resistant?
>
> Re. (5): It's only true for data that loses value rapidly. It may work
> for, e.g., throw-away TLS sessions, but not for, e.g., sensitive email. It
> seems to ignore the fact that data produced in year x-k (encrypted by good
> and intercepted by bad players) may still have value in year x, x+1, etc.
>
> I cannot (nor do I want to) tell people what to research or experiment
> with, and what not to. But common sense suggests that systems/algorithms
> that do not offer long-term protection won't see large-scale commercial
> deployment, IRTF draft or not.
>
>
>

---

From: Dan Brown <[email-masked]>
Date: Mon, 1 Apr 2019 18:30:32 +0000

The topic of non-PQ crypto's value applies to other CFRG drafts, such as PAKEs, VRFs, Oblivious functions, etc., so maybe this discussion should be taken outside this thread?

Non-PQ crypto still seems worthwhile to me, mainly because I estimate the chance of a practical ECC-breaking quantum computer to be low, e.g. 2^(-10), yet still high enough to warrant a hybrid of PQ and non-PQ crypto, e.g. McEliece + ECC. (See further below.)

> -----Original Message-----
> From: Cfrg <[email-masked]> On Behalf Of Blumenthal, Uri - 0553 -
> MITLL
> 
> It doesn’t but we did already discuss that, and good arguments were put forth
> for continuing the work despite this. (See the mail archive, I guess.)
> 
> So far I’ve found this (which IMHO doesn't look like a set of good arguments):
> 
> >  3) Post-quantum crypto depends on hard problems that it will take time to
> develop full confidence in, even in regard to attacks from non-
> quantum computers
> >  4) In the meantime (and that could be quite a long time) it makes perfect
> sense to proceed with the development and standardization
> >  5) In the year x out pops a quantum computer. However in the year x-1 out
> popped well-developed and well-understood
> Re. (1): sure, it would do great stuff, but for how long? What’s the expected
> lifetime of an algorithm/protocol/approach that would justify efforts spent on
> formalizing, implementing, and deploying it? What application field or use case
> would support it?
> 
> Re. (2) and (3): sure, but irrelevant with regard to the main question - is it
> worth developing (for deploying later, as there's an inevitable lag) non-
> quantum-resistant crypto now?

It would be smart to answer these types questions with quantified support, but all I get so far is the naïve estimates below. (Presumably, experts have already documented more sophisticated reasoning, maybe see ia.cr/2015/1018).

For simplicity, consider any crypto as broken or not (at some attack cost and success rate), and then compare 3 alteratnives: ECC, McEliece (McC), and their hybrid (in the strongest link sense).

Define five event probabilities, but please replace my personal (ultra-low-confidence) estimates with your own:

Break ECC classically: e  ~  2^-40
Break ECC quantumly: E = 1 [Shor]
Build quantum computer: Q ~ 2^-10 [(Mosca's estimate = 1/2) ^ (my_grain_of_salt ~ see also cold fusion:)]
Break McC classically: m ~ 2^-20 
Break McC quantumly: M ~ 2^-20

Assuming e,E,Q,m,M independent (in the usual sense that their products are the probabilities of intersection of corresponding events), deduce 3 event probabilities:

Break ECC:  X = e+Q-eQ.
Break McC: Y = m+MQ-mMQ.
Break hybrid ECC+McC: Z = mX+Y-m  = em+mQ+MQ-emQ-mMQ.

For brevity, I omit the tedious derivations.  Assuming X,Y,Z correct:

If Q=1, then X=1 and Z=Y, so ECC is essentially redundant (out with old...).

If Q=0, then X=e and Z=XY, which means that hybrid is generally better (see * below) than either individual crypto, and the lower of X and Y (ECC in my estimation) can be considered as the main contributor to the lowness of Z.

(*) Assume 0 < X,Y < 1. Ignore the issue of declining returns for very low probabilities, e.g. X=2^-128 might be just as good as Z=2^-256 (who needs new?).

For 0 < Q < 1, then the conclusions smoothly vary between the two extremes (Q=0) and (Q=1) above.  

My (e,Q,m,M) estimates lead to an estimate (X,Y,Z) ~ 2^-(10,-20,-30).  I admit to using my (biased?) intuition for the ordering X<Y<Z to cook my (e,Q,m,M) estimates.  

Anyway, with my estimates and (circular?) reasoning, hybrid is usually worthwhile (for protecting high-value data), except as Q gets too close to 1.  

If there is a fancy security goal that McC lacks, e.g. some kind of identity-based forward secrecy, then put m=1 relative to this goal.   (Perhaps replace ECC by pairing-ECC to meet this goal.)  If m=1 and Q=1, then we have Z=1, so we might as well abandon the fancy goal.  If Q<1, then Z=X, and (pairing-)ECC is our only hope to meet the fancy goal.

---

From: John Mattsson <[email-masked]>
Date: Mon, 1 Apr 2019 18:45:53 +0000

Dan Brown <[email-masked]> wrote:

> The topic of non-PQ crypto's value applies to other CFRG drafts, such as PAKEs, VRFs, Oblivious
> functions, etc., so maybe this discussion should be taken outside this thread?

+1

> Non-PQ crypto still seems worthwhile to me, mainly because I estimate the chance of a practical ECC-
> breaking quantum computer to be low, e.g. 2^(-10), yet still high enough to warrant a hybrid of PQ and
> non-PQ crypto, e.g. McEliece + ECC. (See further below.)

I would not be too surprised if ECC breaking quantum computers turn out to be like (warm) fusion power and always be an estimated 20 years away. (first fusion power reactor patents was in the 1940s). However artificial intelligence beating humans in Go was always estimated to be far into the future, until DeepMind did it.

John

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Mon, 1 Apr 2019 20:09:10 +0000

Marek,

Thank you for your comments. Please see inline.

From: Marek Jankowski <[email-masked]>

  1.  As Mike says, we don't know much about current post-quantum schemes, even against a classical attacker. Due to their theoretical complexity, it may take dozens of years to develop considerable trust in such schemes. In the meantime, it is worthwhile to develop (classically-)strong PK schemes with cryptographic advantages. What I mean is - until PQ schemes are made secure, we will use classical schemes; I think the capabilities pairings offer (e.g. IBE, short and aggregateable signatures) are appealing enough to justify standardization.

I think we differ in how much we do or do not know about security of post-quantum schemes. I think all of the NIST PQC submissions came with security proofs, so – no offense meant – I think the “we don’t know much about PQ …” part is a bit disingenuous. If I’m wrong here, or am missing something, or you see problems with the proofs of, e.g., SIKE  – please feel free to post here and/or let me know.

Regardless of how sure/unsure we are of the PQ schemes, we’d probably agree that we are sure that all the “classical” asymmetric crypto (factoring-based, DL-based, etc.) is completely broken with quantum computers. That means – the question is how much time we have before all the classical asymmetric is dead, and how that maps onto the required security lifetime for our data.

I agree that some data won’t need to live that long, and could be fine with “classic” protection, whatever it is. Who/how is going to ensure that only the appropriate data is protected by this mechanism?

Research, implementation, standardization, commercialization of implementation, deployment in the field all take time. It is quite possible that by the time this (or other non-quantum-resistant) approach becomes deployable technology, it gets life-time of zero or only a couple of (or a few) years. If/when, e.g., a hash-function is broken – you simply replace it with a new one as a field upgrade (and even that turned out to be a big hurdle in the field, one wonders why).  As you and Mike pointed out, there is no PQ-secure analog for BLS. Once it is broken, it will stay broken for good, until a new discovery is made. Is it a risk you’re willing to accept? If so, may I ask why?

  1.  > data produced in year x-k (encrypted by good and intercepted by bad players) may still have value in year x, x+1, etc.

I agree; yet, given the choice to encrypt data using a provably (classically-)secure scheme, and a non proven PQ scheme, I would prefer the former: we don't know if current PQ schemes may be broken by a classical computer before year x. Classical computers are available today to millions of potential bad guys, while even when quantum computers are built, it makes sense that for some time very few people will have access to one. It is also worth mentioning that pairing based crypto offers signature schemes with nice qualities (see the recent I-D by Boneh et al.); for signatures it is perfectly acceptable to use quantum-vulnerable schemes today. (But not in year x.)

As I said above, most/all of the NIST PQC submissions came with security proofs. There’s no need to resort to “non-proven PQ scheme”. Unless you’re not happy with the proofs…? In which case, please share what makes you happy with “pre-quantum” proofs and unhappy with PQ ones.

For the second part, it depends on whether the data signed today needs to stay secure in and after year x. One problem is – we do not know how soon (or far away) that year x is. But we do know that it is not a Sci-Fi any more. Quantum computers are built today, they just aren’t a direct threat yet.

  1.  Post quantum crypto is generally much more resource intensive than classical crypto (including pairings), in both complexity and traffic. Therefore pairing based cryptography works better for lightweight processors. Data encrypted by such devices is likely to be irrelevant in 20-30 years after transmission (e.g. IoT, smart cars). So it is OK to use classical crypto there.

You are probably correct here. I.e., if I authenticate to a remote Web site today with a smartcard, somebody’s ability to break my smartcard’s key several years from now is probably not very important. Except that there’s a chance that I logged in to a secure web site to fill out some sensitive form, disclosure of which even several years from now would be highly undesirable.

As you see, it may be hard to draw a line apriori between OK and Not OK.

  1.  Pairings are getting into practical use. Examples are several RFCs (5091, 6508, 6539, 6509), Cloudflare's GeoKey Manager and more, as listed in the I-D. The rising popularity strengthens the need for a well thought out standard/set of standards.

There is a difference between getting an RFC and getting into practical use. But I concede your point.

To conclude, I believe that developing PQ crypto and classical PK crypto should be done in parallel, and not one instead of the other. While using non quantum secure chemes will threaten one's data once a quantum computer is built, I think it should not slow down research of new crypto capabilities.

My concern here is that the life window of the non-quantum is shrinking, maybe shrinking rapidly (and alas, I don’t know how fast). So, with every year and every day there is less and less sense to invest time and efforts into non-quantum crypto. Are we already at the point when it already doesn’t make …? I personally think we are.

Dan Brown made a good point about hybrid approaches. Offhand, I concur with him. Perhaps we need to invest more efforts there.

On Fri, Mar 29, 2019 at 5:59 PM Blumenthal, Uri - 0553 - MITLL <[email-masked]<mailto:[email-masked]>> wrote:
It doesn’t but we did already discuss that, and good arguments were put forth for continuing the work despite this. (See the mail archive, I guess.)

So far I’ve found this (which IMHO doesn't look like a set of good arguments):

>  1) Pairing-based crypto threw open the doors to lots of nice new crypto possibilities, enabling stuff that we couldn't do before
>  2) Gradually post-quantum crypto is catching up and demonstrating capabilities that mirror some (but not all) of these achievements
>  3) Post-quantum crypto depends on hard problems that it will take time to develop full confidence in, even in regard to attacks from non-quantum computers
>  4) In the meantime (and that could be quite a long time) it makes perfect sense to proceed with the development and standardization
>  5) In the year x out pops a quantum computer. However in the year x-1 out popped well-developed and well-understood
>       post-quantum crypto replacements in which we can have complete confidence.

Re. (1): sure, it would do great stuff, but for how long? What’s the expected lifetime of an algorithm/protocol/approach that would justify efforts spent on formalizing, implementing, and deploying it? What application field or use case would support it?

Re. (2) and (3): sure, but irrelevant with regard to the main question - is it worth developing (for deploying later, as there's an inevitable lag) non-quantum-resistant crypto now?

Re. (4): I see no logic in that statement. We don't have full confidence in post-quantum hard problems, therefore we should standardize methods that we know are not quantum-resistant?

Re. (5): It's only true for data that loses value rapidly. It may work for, e.g., throw-away TLS sessions, but not for, e.g., sensitive email. It seems to ignore the fact that data produced in year x-k (encrypted by good and intercepted by bad players) may still have value in year x, x+1, etc.

I cannot (nor do I want to) tell people what to research or experiment with, and what not to. But common sense suggests that systems/algorithms that do not offer long-term protection won't see large-scale commercial deployment, IRTF draft or not.

---

From: denis bider <[email-masked]>
Date: Mon, 1 Apr 2019 16:35:31 -0500

The following graph is commonly shared about why fusion is always 30 years
away:

http://i.imgur.com/3vYLQmm.png

I am surprised by Dan's probability estimation for QC capable of breaking
ECC at 2^(-10). This could be taken to mean that out of 1024 probable
universes that start in this moment, quantum decoherence and other
obstacles would be solved in only 1.

This is a prediction with 99.9% confidence. The human track record of
predicting the future does not seem to support predictions with such
confidence. When billions of USD are being invested into research by people
who expect a pay off, we could entertain a prediction that they're 90%
likely to fail, but a prediction that they're 99.9% likely to fail seems
overly confident.

On Mon, Apr 1, 2019 at 1:46 PM John Mattsson <[email-masked]>
wrote:

> I would not be too surprised if ECC breaking quantum computers turn out to
> be like (warm) fusion power and always be an estimated 20 years away.
> (first fusion power reactor patents was in the 1940s). However artificial
> intelligence beating humans in Go was always estimated to be far into the
> future, until DeepMind did it.
>
> John
>
>
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg
>

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Mon, 1 Apr 2019 21:44:51 +0000

+1
    
    > Non-PQ crypto still seems worthwhile to me, mainly because I estimate the chance of a practical
   > ECC-breaking quantum computer to be low, e.g. 2^(-10),

I don't know enough to agree or argue with your estimation. Would you mind explaining the reasons behind it?

   > ...yet still high enough to warrant a hybrid of PQ and non-PQ crypto, e.g. McEliece + ECC. (See further below.)
    
+1. Hybrid approach is probably it. Depending on what kind of performance we'd get from pure PQC compared to hybrid, and whether hybrid would preserve the non-PQ capabilities while raising the bar for quantum-based attacks.

    > It would be smart to answer these types questions with quantified support, but all I
    > get so far is the naïve estimates below. (Presumably, experts have already documented
    > more sophisticated reasoning, maybe see ia.cr/2015/1018).

I do not understand the ECC-related reasoning in that paper by Koblitz and Menezes. Perhaps you can explain it for me? What I read there is: "NSA backdoored EC-DRBG, but they could not break ECC. Therefore, despite themselves promoting ECC and defining it as their mandatory standard, they are now trying to get people off ECC and onto something weaker, using Quantum threat as a prod". 
    
   > For simplicity, consider any crypto as broken or not (at some attack cost and success rate), and then 
   > compare 3 alteratnives: ECC, McEliece (McC), and their hybrid (in the strongest link sense)....

I personally would prefer Isogenies-based approach, otherwise we're probably on the same page.

---

From: Peter Gutmann <[email-masked]>
Date: Tue, 2 Apr 2019 01:09:12 +0000

denis bider <[email-masked]> writes:

>When billions of USD are being invested into research by people who expect a
>pay off, we could entertain a prediction that they're 90% likely to fail, but
>a prediction that they're 99.9% likely to fail seems overly confident.

That's actually what the fusion graph you posted is showing, initially there
was a spike in funding and progress appeared to be following either the
"accelerated" or "aggressive" path.  Then after the initial enthusiasm died
out due to little progress being made, the funding dried up as well and it
dropped to below "never" levels.

Currently we're at the same "spike in funding" stage for quantum computers.
Little progress is being made.

(Going from 2 qubits to 70-odd qubits in twenty years isn't progress, it's
just more refined experimentation when you look at the sort of system that'd
be needed to pose a threat to crypto).

Peter.

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Tue, 2 Apr 2019 04:29:04 +0000

> ...Currently we're at the same "spike in funding" stage for quantum computers.
    
Do you think then, that quantum computers capable of threatening, e.g., ECC, won't come in the next 50 years or so, if at all?

---

From: Peter Gutmann <[email-masked]>
Date: Tue, 2 Apr 2019 06:18:39 +0000

Blumenthal, Uri - 0553 - MITLL <[email-masked]> writes:

>Do you think then, that quantum computers capable of threatening, e.g., ECC,
>won't come in the next 50 years or so, if at all?

>From the existing data we've got, yes.

  Someone may or may not build a cryptanalysis-capable quantum computer,
  someone may or may not prove/disprove one of the many mathematical
  assumptions underlying our cryptosystems, space aliens may land and tell us
  that what we're using is the sort of crypto that newly-hatched space spawn
  solve as basic homework exercises, or any other kind of fantastic event may
  or may not occur, but what will definitely happen is that attackers will use
  trojan-horse software to steal keys, take advantage of software bugs, employ
  side-channel attacks, backdoor the crypto, and perform a million other
  actual attacks that are being used right now.

  It doesn't matter whether you can build a magic quantum computer or not when
  another process in the system can suck your crypto keys right out of memory.
  It's not magical attacks from the future that you need to worry about, it's
  real attacks from right now.

Having said that, it doesn't mean cryptographers won't invest vast amounts of
time and effort into PQC.  It's a cool chance to reset the crypto world and
start again with entirely new designs, which is always fun to do.  There's
entire conference tracks just waiting to be held on all this, new journals,
research funding, government contracts, the sky's the limit.

Peter.

---

From: Björn Haase <[email-masked]>
Date: Tue, 2 Apr 2019 17:35:07 +0200

Hi to all,

02.04.2019 at 08:18 Peter Gutmann wrote:
 > ... but what will definitely happen is that attackers will use

I do agree with Peter Gutmann's point of view.

When assessing the likelyhood that a large-scale working
quantum-computer will ever be able at attacking today's ECC or large
characteristic prime field crypto: there is a small but maybe
non-negligible chance that this might happen. Moreover even if one could
be built, it could reasonably be expected that the cost is truly
significant, putting at risk only few actual applications where secrets
might be "worth" the effort.

The likelyhood that the real-world threats mentioned by Peter exist is
100%. The likelyhood that actual-world roll-out of (classically) more
secure or insecure crypto depends on the efficiency and resources
available on resource-constrained devices is also 100%. We know that the
cost of conventional attacks is low and many applications are actually
"worth" the effort of an attack.

This alone is worth seriously considering non-PQ crypto also nowadays,
specifically if it serves use-cases not covered by mainstream web
crypto, such as identity-based encryption or secure communication
between humans and machines in environments where we could not trust on
a PKI!

Yours,

Björn.

P.S.:

As a quantum physicist having worked on optical analysis of quantum
correlations in semiconductors as Ph.D. student and Post-Doc I believe
to have a quite clear picture of the challenge of basing a quantum
computer based on optics. On this basis designs based on optical systems
don't scare me at all!

I have somewhat lesser insight into systems who are based on josephson
junctions and superconductors, but there the planar structure and the
challenge to build something similar to random-access memory with
flexible addressing in addition to error-correcting mechanisms and the
challange of cooling don't make scared as well.

If there stands some chance that my above assessment regarding
feasibility of sufficiently large quantum-computers is correct, the
bigger real-world threat might actually be that a PQ hype keeps
cryptographers and security people away from resolving much more
important problems?

---

From: Peter Gutmann <[email-masked]>
Date: Tue, 2 Apr 2019 23:56:30 +0000

Björn Haase <[email-masked]> writes:

>We know that the cost of conventional attacks is low and many applications
>are actually "worth" the effort of an attack.

Another thing about PQC is that all of this is entirely new crypto that we
have no experience in using.  We've had decades of experience with using
PreQC, and have mostly managed to get it right (a lot of the attacks being
performed were known about years ago but were ignored until someone published
an attack paper with accompanying tools and newsworthy name, and even then
there's a huge amount of code in PreQC crypto designed specifically to prevent
entire classes of attacks), while we have zero experience with using PQC.
Which means we're going to see years if not decades of new attacks, or the
same old attacks that were fixed in PreQC implementations, popping up with
PQC.  It's quite possible that PQC will make us a lot *less* secure, if QC
never really happens but the expected vulnerabilities in using PQC do.

In fact I'll make this prediction now:

  Likelihood of successful attacks due to QC: Epsilon.
  Likelihood of successful attacks due to use of PQC over PreQC: 100.0%.

(the second figure should actually be much higher than 100%, because there'll
be many, many of them, not just one).

Peter.

---

From: Michael Scott <[email-masked]>
Date: Wed, 3 Apr 2019 10:08:24 +0100

.. as a follow up to my comments on the curve BN462..

I note this choice

F_p6 = F_p2[v] / (v^3 - u - 2)

Its not clear to me why you did not choose the simpler irreducible
polynomial

x^6-(1+sqrt(-1))

which will always be more efficient. See the section on "BN towers" in
https://eprint.iacr.org/2009/556.pdf

where the conditions for this choice are satisfied.

  – If x0 ≡ 7 or 11 mod 12 then x^6 − (1 + √ −1) is irreducible over Fp2 =
Fp( √ −1).

(in the case of BN462 x0=7 mod 12)

Mike

On Sun, Mar 31, 2019 at 8:28 PM Michael Scott <[email-masked]> wrote:

> Hello Shoko,
>
> Thanks for previous clarifications.
>
> I am a bit puzzled by the proposed BN462 curve
>
> You chose the curve E:y^2=x^3+5
> On the twisted curve you choose E':y^2=x^3-u+2 (and I am unclear where
> -u+2 came from)
>
> In the paper that first suggested the curve -
> https://eprint.iacr.org/2017/334.pdf
>
> the authors suggest
> E: y^2=x^3-4, and
> E': y^2=x^3-4(1+u)
>
> which seems simpler, and closer to the BLS381 approach
>
> I am attempting to implement these curves (and already have BLS381 done).
> Any help is much appreciated.
>
> Mike
>
> On Fri, Mar 29, 2019 at 10:03 AM Shoko YONEZAWA <[email-masked]>
> wrote:
>
>> Hi Mike,
>>
>> This difference is probably caused by representation of an extension
>> field.
>> We encoded the generator G' = (x', y') where x' = a'*u + b' and y' =
>> c'*u + d' by
>>
>> x' : a'*p + b' (in Z) and
>> y' : c'*p + d' (in Z),
>>
>> whereas zkcrypto encoded it like
>>
>> x' : a' || b' and
>> y' : c' || d'.
>>
>> We followed the convention shown in IEEE 1363a-2004.
>>
>> As you suggested, it is helpful to describe a',b',c',d' as well as x', y'.
>> We add these value in the next version.
>>
>> Thank you again,
>> Shoko
>>
>> On 2019/03/28 20:11, Michael Scott wrote:
>> > OK. However for the BL381 curve for example the G2 generator point does
>> not
>> > appear to be the same as the one given here...
>> >
>> > https://github.com/zkcrypto/pairing/tree/master/src/bls12_381
>> >
>> > Also it would help if the individual components of x' and  y' were
>> > highlighted. For example if x'=a'u+b' it would be useful to know were a'
>> > ends and b' begins.
>> >
>> >   Also as in the above link it would I think be good practice to state
>> > exactly how the values for G1 and G2 were arrived at.
>> >
>> > Mike
>> >
>> > On Thu, Mar 28, 2019 at 7:27 AM Shoko YONEZAWA <[email-masked]>
>> > wrote:
>> >
>> >> Hi Mike,
>> >>
>> >> Thank you again for the feedback.
>> >>
>> >>   > It would be helpful for implementors to know if the curves support
>> an
>> >>   > M-Type or D-Type twist.
>> >>   >
>> >>   > BLS381 and BN462 are both M-Type. BLS48_581 is D-Type.
>> >>
>> >> As the information for implementers,
>> >> we add the description of M-type or D-type for each curve.
>> >>
>> >>   > Also I think a standard should also include a generator point for
>> G2 for
>> >>   > interoperability, as well as for G1. For example an implementation
>> of
>> >> BLS
>> >>   > short signature probably requires a generator in G2.
>> >>
>> >> The generator point for G2 is described as a base point G' = (x', y')
>> >> in our draft.
>> >> We revise the description for clarification.
>> >>
>> >> Best,
>> >> Shoko
>> >>
>> >> On 2019/03/21 0:48, Michael Scott wrote:
>> >>> A couple of further observations..
>> >>>
>> >>> It would be helpful for implementors to know if the curves support an
>> >>> M-Type or D-Type twist.
>> >>>
>> >>> BLS381 and BN462 are both M-Type. BLS48_581 is D-Type.
>> >>>
>> >>> Also I think a standard should also include a generator point for G2
>> for
>> >>> interoperability, as well as for G1. For example an implementation of
>> BLS
>> >>> short signature probably requires a generator in G2.
>> >>>
>> >>> Mike
>> >>>
>> >>> On Tue, Mar 19, 2019 at 3:39 AM Shoko YONEZAWA <
>> [email-masked]>
>> >>> wrote:
>> >>>
>> >>>> Dear Mike,
>> >>>>
>> >>>> Thank you very much for your comments.
>> >>>>
>> >>>>> The suggested curves do not appear to meet the requirement for
>> subgroup
>> >>>>> security which is indicated as being a desirable property in section
>> >>>> 3.1 -
>> >>>>> “One has to choose parameters so that the cofactors of G_1, G_2 and
>> G_T
>> >>>>> contain no prime factors smaller than |G_1|, |G_2| and |G_T|”..
>> >>>>>
>> >>>>> The case could be made that subgroup security is not so important,
>> but
>> >> if
>> >>>>> so the text in 3.1 should be modified to reflect this point of view.
>> >>>>
>> >>>> As you pointed out, we found that our suggested curves are not
>> >>>> subgroup-secure.
>> >>>> For standardization, we focus on the existing implementations as
>> well as
>> >>>> sufficient security.
>> >>>> We think it impractical to choose a completely new parameter and
>> >>>> implement it from now.
>> >>>> Therefore, we would like to recommend the current parameters we
>> >>>> described in the draft with modifying our description of subgroup
>> >> security.
>> >>>>
>> >>>> We are keeping watching the research activity and ready to change
>> >>>> parameters if a critical attack for pairing-friendly curves which
>> don't
>> >>>> meet subgroup security is found.
>> >>>>
>> >>>>> Another point – the BLS381 curve was chosen for a very particular
>> >> (albeit
>> >>>>> important) application where it is a requirement that r-1 has a
>> factor
>> >> of
>> >>>>> 2^m for a large value of m. Curves chosen with application-specific
>> >>>>> benefits should I suggest be considered carefully if proposed as
>> more
>> >>>>> general purpose standards. Note that this particular application
>> >>>>> disadvantages BN curves, as due to the form of its formula for r,
>> this
>> >>>>> particular condition is much harder to achieve.
>> >>>>
>> >>>> We guess that BLS12-381 is chosen for the efficient computation of
>> their
>> >>>> zero-knowledge proof. Nonetheless, we think BLS12-381 has sufficient
>> >>>> performance for general purpose.
>> >>>>
>> >>>> Best regards,
>> >>>> Shoko
>> >>>>
>> >>>> On 2019/03/15 3:52, Michael Scott wrote:
>> >>>>> Another point..
>> >>>>>
>> >>>>> For the BLS curves, the cofactor h in G_1 is calculated here as
>> >>>>> ((t-1)^2)/3, and this will work fine as a co-factor, where a random
>> >> point
>> >>>>> on the curve over the base field can be multiplied by this
>> co-factor to
>> >>>>> create a point of order r in G_1. But this co-factor is
>> unnecessarily
>> >>>> large.
>> >>>>>
>> >>>>> The same can be achieved by using (t-1) as a co-factor, due to the
>> >>>>> structure of pairing friendly fields. This will be twice as fast.
>> >>>>>
>> >>>>>
>> >>>>> Mike
>> >>>>>
>> >>>>>
>> >>>>> However to
>> >>>>>
>> >>>>> On Thu, Mar 14, 2019 at 3:21 PM Michael Scott <
>> [email-masked]>
>> >>>> wrote:
>> >>>>>
>> >>>>>> Hello,
>> >>>>>>
>> >>>>>> I greatly welcome this proposal, and would not want to slow its
>> >> progress
>> >>>>>> in any way. It is long overdue that pairing-friendly curves be
>> >>>>>> standardized, before unsuitable de-facto standards emerge, which
>> may
>> >>>> not be
>> >>>>>> ideal, but which may nevertheless become widely deployed.
>> >>>>>>
>> >>>>>> However I make the following observations about the particular
>> curves
>> >>>>>> suggested.
>> >>>>>>
>> >>>>>> The suggested curves do not appear to meet the requirement for
>> >> subgroup
>> >>>>>> security which is indicated as being a desirable property in
>> section
>> >>>> 3.1 -
>> >>>>>> “One has to choose parameters so that the cofactors of G_1, G_2 and
>> >> G_T
>> >>>>>> contain no prime factors smaller than |G_1|, |G_2| and |G_T|”.
>> >>>>>>
>> >>>>>> The case could be made that subgroup security is not so important,
>> but
>> >>>> if
>> >>>>>> so the text in 3.1 should be modified to reflect this point of
>> view.
>> >>>>>>
>> >>>>>> The curve BN462 is not sub-group secure, as in G_T (p^4-p^2+1) /r
>> has
>> >>>>>> small factors of 2953, 5749 and 151639045476553 (amongst others). I
>> >>>> didn’t
>> >>>>>> check G_2.
>> >>>>>>
>> >>>>>> The curve BLS381 has the same problem, as (p^4-p^2+1) /r has small
>> >>>> factor
>> >>>>>> of 4513, 584529700689659162521 and more. Again I didn’t check G_2
>> >>>>>>
>> >>>>>> The curve BLS48-581 has the same problem, as (p^4-p^2+1) /r has a
>> >> small
>> >>>>>> factor of 76369, and probably others. Again I didn’t check for G_2
>> >>>>>>
>> >>>>>> The draft does point out that for BLS curves, when hashing to a
>> point
>> >> in
>> >>>>>> G_1, multiplication by a small co-factor h>1 will always be
>> necessary.
>> >>>>>>
>> >>>>>> In my opinion sub-group security in G_T is particularly important
>> if
>> >> it
>> >>>> is
>> >>>>>> desirable to offload the pairing calculation to an untrusted
>> server,
>> >>>> and so
>> >>>>>> it is a feature I would consider useful in a standard curve. In our
>> >>>>>> experience finding such curves is relatively easy (although finding
>> >>>> curves
>> >>>>>> that are sub-group secure in both G_2 and G_T is more
>> problematical)..
>> >>>>>>
>> >>>>>> Another point – the BLS381 curve was chosen for a very particular
>> >>>> (albeit
>> >>>>>> important) application where it is a requirement that r-1 has a
>> factor
>> >>>> of
>> >>>>>> 2^m for a large value of m. Curves chosen with application-specific
>> >>>>>> benefits should I suggest be considered carefully if proposed as
>> more
>> >>>>>> general purpose standards. Note that this particular application
>> >>>>>> disadvantages BN curves, as due to the form of its formula for r,
>> this
>> >>>>>> particular condition is much harder to achieve.
>> >>>>>>
>> >>>>>>
>> >>>>>> Mike
>> >>>>>>
>> >>>>>> On Wed, Mar 13, 2019 at 10:33 AM Shoko YONEZAWA <
>> >> [email-masked]
>> >>>>>
>> >>>>>> wrote:
>> >>>>>>
>> >>>>>>> Hi there,
>> >>>>>>>
>> >>>>>>> Thank you for your comments to our pairing-friendly curve draft.
>> >>>>>>> We submitted a new version.
>> >>>>>>>
>> >>>>>>> According to Kenny's comments,
>> >>>>>>> we added the following description to the new version.
>> >>>>>>>
>> >>>>>>> - Pseudo-codes for pairing computation
>> >>>>>>> - Example parameters and test vectors of each curve
>> >>>>>>>
>> >>>>>>> We now published our working draft on GitHub,
>> >>>>>>> together with the BLS signature group.
>> >>>>>>> Please feel free to submit issues. Your comments are really
>> >>>> appreciated.
>> >>>>>>>
>> >>>>>>> https://github.com/pairingwg/pfc_standard/
>> >>>>>>>
>> >>>>>>> Best,
>> >>>>>>> Shoko
>> >>>>>>>
>> >>>>>>> -------- Forwarded Message --------
>> >>>>>>> Subject: I-D Action: draft-yonezawa-pairing-friendly-curves-01.txt
>> >>>>>>> Date: Mon, 11 Mar 2019 08:34:48 -0700
>> >>>>>>> From: [email-masked]
>> >>>>>>> Reply-To: [email-masked]
>> >>>>>>> To: [email-masked]
>> >>>>>>>
>> >>>>>>>
>> >>>>>>> A New Internet-Draft is available from the on-line Internet-Drafts
>> >>>>>>> directories.
>> >>>>>>>
>> >>>>>>>
>> >>>>>>>             Title           : Pairing-Friendly Curves
>> >>>>>>>             Authors         : Shoko Yonezawa
>> >>>>>>>                               Sakae Chikara
>> >>>>>>>                               Tetsutaro Kobayashi
>> >>>>>>>                               Tsunekazu Saito
>> >>>>>>>            Filename        :
>> >>>> draft-yonezawa-pairing-friendly-curves-01.txt
>> >>>>>>>            Pages           : 28
>> >>>>>>>            Date            : 2019-03-11
>> >>>>>>>
>> >>>>>>> Abstract:
>> >>>>>>>        This memo introduces pairing-friendly curves used for
>> >> constructing
>> >>>>>>>        pairing-based cryptography.  It describes recommended
>> >> parameters
>> >>>> for
>> >>>>>>>        each security level and recent implementations of
>> >> pairing-friendly
>> >>>>>>>        curves.
>> >>>>>>>
>> >>>>>>>
>> >>>>>>> The IETF datatracker status page for this draft is:
>> >>>>>>>
>> >>>>
>> >>
>> https://datatracker.ietf.org/doc/draft-yonezawa-pairing-friendly-curves/
>> >>>>>>>
>> >>>>>>> There are also htmlized versions available at:
>> >>>>>>>
>> >> https://tools.ietf.org/html/draft-yonezawa-pairing-friendly-curves-01
>> >>>>>>>
>> >>>>>>>
>> >>>>
>> >>
>> https://datatracker.ietf.org/doc/html/draft-yonezawa-pairing-friendly-curves-01
>> >>>>>>>
>> >>>>>>> A diff from the previous version is available at:
>> >>>>>>>
>> >>>>>>>
>> >>>>
>> >>
>> https://www.ietf.org/rfcdiff?url2=draft-yonezawa-pairing-friendly-curves-01
>> >>>>>>>
>> >>>>>>>
>> >>>>>>> Please note that it may take a couple of minutes from the time of
>> >>>>>>> submission
>> >>>>>>> until the htmlized version and diff are available at
>> tools.ietf.org..
>> >>>>>>>
>> >>>>>>> Internet-Drafts are also available by anonymous FTP at:
>> >>>>>>> ftp://ftp.ietf.org/internet-drafts/
>> >>>>>>>
>> >>>>>>> I-D-Announce mailing list
>> >>>>>>> [email-masked]
>> >>>>>>> https://www.ietf.org/mailman/listinfo/i-d-announce
>> >>>>>>> Internet-Draft directories: http://www.ietf.org/shadow.html
>> >>>>>>> or ftp://ftp.ietf.org/ietf/1shadow-sites.txt
>> >>>>>>>
>> >>>> --
>> >>>> Shoko YONEZAWA
>> >>>> Lepidum Co. Ltd.
>> >>>> [email-masked]
>> >>>> TEL: +81-3-6276-5103
>> >> --
>> >> Shoko YONEZAWA
>> >> Lepidum Co. Ltd.
>> >> [email-masked]
>> >> TEL: +81-3-6276-5103
>> --
>> Shoko YONEZAWA
>> Lepidum Co. Ltd.
>> [email-masked]
>> TEL: +81-3-6276-5103

---

From: William Whyte <[email-masked]>
Date: Wed, 3 Apr 2019 07:28:35 -0400

Hi Peter,

have no experience in using.  We've had decades of experience with using
PreQC, and have mostly managed to get it right (a lot of the attacks being
performed were known about years ago but were ignored until someone
published
an attack paper with accompanying tools and newsworthy name, and even then
there's a huge amount of code in PreQC crypto designed specifically to
prevent
entire classes of attacks), while we have zero experience with using PQC.

This is an argument for being cautious about deploying PQC. It's not an
argument
that it's a good idea to develop new PreQC primitives. If anything, it's an
argument
against that.

Cheers,

William

-- 

---

I may have sent this email out of office hours. I never expect a response
outside yours.

---

From: Watson Ladd <[email-masked]>
Date: Wed, 3 Apr 2019 07:47:52 -0700

On Wed, Apr 3, 2019 at 4:29 AM William Whyte <[email-masked]> wrote:
> This is an argument for being cautious about deploying PQC. It's not an argument
> that it's a good idea to develop new PreQC primitives. If anything, it's an argument
> against that.

There are protocols that only work with new primitives. Some people
are willing to accept the risk.
What's the problem?

>
> Cheers,
>
> William
>
>
> On Tue, Apr 2, 2019 at 7:57 PM Peter Gutmann <[email-masked]> wrote:
>>
> I may have sent this email out of office hours. I never expect a response outside yours.

-- 
"Man is born free, but everywhere he is in chains".
--Rousseau.

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Wed, 3 Apr 2019 14:54:22 +0000

In short, the problem is that one group of people accepts the risks for another group of people. 

As one of back officials said in a private discussion: "Your risk is always lower than our cost."

Regards,
Uri

Sent from my iPhone

> On Apr 3, 2019, at 10:48, Watson Ladd <[email-masked]> wrote:
>

---

From: Watson Ladd <[email-masked]>
Date: Wed, 3 Apr 2019 07:57:58 -0700

> As one of back officials said in a private discussion: "Your risk is always lower than our cost."

If you don't like these protocols, don't use them. I really do not
understand the issue here: pairings provide all sorts of efficiencies
and nice protocols that we cannot get other ways. The argument that
now we need to stop doing some kinds of cryptography because in some
as of yet unknown timeframe quantum computers will break all the
schemes (ignoring the difference between authentication and
encryption) made as much sense in 1996 as it does today. And yet today
it is problem but was not in 1996?  TLS 1.3 does not have any
post-quantum ciphersuites. The answer here is a good security
considerations section.

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Wed, 3 Apr 2019 16:44:49 +0000

On 4/3/19, 10:59 AM, "Watson Ladd" <[email-masked]> wrote:
    > If you don't like these protocols, don't use them. 

This approach would work just fine for protocols and algorithms like PGP. This would absolutely not work for protocols like TLS. I leave it for you to figure why.

    > I really do not understand the issue here:

I can see that. ;-)

    > ...pairings provide all sorts of efficiencies
    > and nice protocols that we cannot get other ways.

That is true, and nobody is disputing it.

    > The argument that
    > encryption) made as much sense in 1996 as it does today.
    > And yet today it is problem but was not in 1996?

Some people tend to think that now, in 2019, the threat to crypto by quantum computers is much closer to reality than it was 23 years ago (to remind, DES was deployed with expectation of 15 years of life). 

They think that since sensitive data tends to "maintain its value, the time for designing new non-quantum-resistant algorithms is coming to an end. Because when you factor in (no pun intended :) the time for commercial implementation and deployment, what's left for the actual use of the algorithm would be too short to justify the effort spent on it.

Other people tend to think that there's no way quantum computers could become a threat in the near/foreseeable future (10-20-30 years, some say 50+, whatever).

Yet others say "yeah, maybe - but due to the cost etc. of such devices, the risk applies mainly to high-level government communications, the majority of the population would still be safe for a long time even after these devices are actually made."

Which camp got it right?

    > TLS 1.3 does not have any post-quantum ciphersuites. 

For TLS the update is trivially simple - though you probably saw for yourself that even such a simple thing takes huge time and effort to deploy the fix/update to the majority. We'll probably see PQ ciphersuites after NIST PQC competition concludes. Google has been experimenting with PQ algorithms/protocols for a couple of years now, if not longer. 

This still doesn't deal with the "golden oldies" - valuable data secured with the old stuff...

    > The answer here is a good security considerations section.

For a nerd deciding what to play with - sure. For a consumer who uses whatever's provided to connect to his account at Amazon/Deutsche Bank/etc. - hardly.

P.S. You used to express opinion that developers screw up implementations even when guiding documents are pretty decent. What made you change your mind? ;-)

---

From: John Mattsson <[email-masked]>
Date: Wed, 3 Apr 2019 18:25:05 +0000

The US Suite B were, and the CNSA suite are, approved to protect information up to the TOP SECRET level. Such information is to my knowledge often protected for 50 years, in extraordinary case for 75 years, and after special permission for more than 75 years.

That NSA is not planning to require US governments to use of PQC before 2022/2024 would suggest that they do not expect quantum computers capable of breaking P-384 and RSA-3072 to be available to any foreign government before 2024 + 50/75 years... 

Looking how e.g. the PKI industry has acted in the past with e.g. RSA-1024 and SHA-1, my prediction is that many deployments  will continue to use non-PQC until someone has built or is very close to building a quantum computer capable of breaking current ECC and RSA....  

-----Original Message-----
From: Cfrg <[email-masked]> on behalf of "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Wednesday, 3 April 2019 at 18:45
To: Watson Ladd <[email-masked]>
Cc: cfrg <[email-masked]>
Subject: Re: [Cfrg] Fwd: I-D Action: draft-yonezawa-pairing-friendly-curves-01.txt

    
    
    I can see that. ;-)

    

    

    Which camp got it right?

---

From: Damien Miller <[email-masked]>
Date: Thu, 4 Apr 2019 11:25:19 +1100 (AEDT)

> never really happens but the expected vulnerabilities in using PQC do.

If anything this prediction (with which I agree) heightens the need for
strong and performant preQC algorithms, so they may be (ahem) paired
with the postQC algorithms to ensure that the combination is resistant
to attack in at least the classical setting.

-d

---

From: Peter Gutmann <[email-masked]>
Date: Mon, 15 Apr 2019 03:36:43 +0000

Björn Haase <[email-masked]> writes:

>Saying this, I think that it is important to have researchers working on PQ-
>Crypto such that we have a solution "in the box", even if the actual
>probability that we'd actually need it might be small.

If it was researchers publishing via standard academic venues that'd be fine,
the problem is that the CFRG is a de facto standards body so anything
published will become an Internet standard.  At that point the yet-to-be-
given-a-cool-name rule [0] which says that the best crypto is the latest
trendiest bleeding-edge stuff and not the long-established stuff that we have
a lot of experience with will kick in, and whatever PQC is written up will
start being deployed and rushed into production before the RFC is even
published.

The end result will be the worst of both worlds, we'll have a bunch of PQC
algorithms that work nothing like existing stuff so that people will be able
revisit thirty years of mistakes in applying it, alongside the existing crypto
that also needs to be supported.

So standardising PQC at this point is hugely premature.  Leave it for academic
conferences from which it can be pulled as required, but don't give
implementers an excuse to re-make all the mistakes that have been made in the
past with an entirely new set of algorithms.

Peter.

[0] Suggestions for a name welcome, currently "The Hipster Crypto Rule" but
    I'm not too happy with that.

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Mon, 15 Apr 2019 16:08:47 +0000

While not a quantum physicist myself, I do think you are downplaying the risks:

https://www.insidequantumtechnology.com/news/new-hope-quantum-computers-factorizations-rsa-thousand-fold-excess/?utm_source=IQT+Daily+Newsletter&utm_campaign=a7528b4239-RSS_EMAIL_CAMPAIGN&utm_medium=email&utm_term=0_e8f238b4dd-a7528b4239-72197729 

I understand Peter's point that unlike QC, attacks against implementations are really bad *now* (and probably will stay that way), but that's not an excuse to ignore the upcoming threat on the algorithmic level.
--
Regards,
Uri 

On 4/14/2019, 23:37, "Peter Gutmann" <[email-masked]> wrote:

    

    
    Peter.

---

From: Ruslan Kiyanchuk <[email-masked]>
Date: Mon, 15 Apr 2019 11:04:48 -0700

@Uri, the link statement reads fishy. I am also not a professional quantum
physicist, but my understanding was that D-Wave computers can only do
quantum annealing, which makes them applicable to a very narrow set of
quantum problems, and makes them unsuitable for running Shor's or Grover's
algorithms, which are not quantum annealing problems. At least that's how
it used to be couple of years ago. Did D-Wave broaden the scope of their
computers recently?

On Mon, Apr 15, 2019 at 9:09 AM Blumenthal, Uri - 0553 - MITLL <
[email-masked]> wrote:

> I understand Peter's point that unlike QC, attacks against implementations
> are really bad *now* (and probably will stay that way), but that's not an
> excuse to ignore the upcoming threat on the algorithmic level.
> --
> Regards,
> Uri
>

---

From: mcgrew <[email-masked]>
Date: Mon, 15 Apr 2019 15:10:02 -0400

Hi Ruslan,

> On Apr 15, 2019, at 2:04 PM, Ruslan Kiyanchuk <[email-masked]> wrote:
> 
> @Uri, the link statement reads fishy. I am also not a professional quantum physicist, but my understanding was that D-Wave computers can only do quantum annealing, which makes them applicable to a very narrow set of quantum problems, and makes them unsuitable for running Shor's or Grover's algorithms, which are not quantum annealing problems. At least that's how it used to be couple of years ago. Did D-Wave broaden the scope of their computers recently?

It is not that D-Wave can run Shor’s algorithm, but rather that researchers are studying how an adiabatic quantum computer can be used for factoring.  See for instance "Quantum Annealing for Prime Factorization”, https://www.nature.com/articles/s41598-018-36058-z:
We have developed a framework to convert an arbitrary integer factorization problem to an executable Ising model by first writing it as an optimization function then transforming the k-bit coupling (k ≥ 3) terms to quadratic terms using ancillary variables. Our resource-efficient method uses O(log_2(N)) binary variables (qubits) for finding the factors of an integer N. We present how to factorize 15, 143, 59989, and 376289 using 4, 12, 59, and 94 logical qubits, respectively. This method was tested using the D-Wave 2000Q for finding an embedding and determining the prime factors for a given composite number.  

David

> 
> On Mon, Apr 15, 2019 at 9:09 AM Blumenthal, Uri - 0553 - MITLL <[email-masked] <mailto:[email-masked]>> wrote:
> https://www.insidequantumtechnology.com/news/new-hope-quantum-computers-factorizations-rsa-thousand-fold-excess/?utm_source=IQT+Daily+Newsletter&utm_campaign=a7528b4239-RSS_EMAIL_CAMPAIGN&utm_medium=email&utm_term=0_e8f238b4dd-a7528b4239-72197729 <https://www.insidequantumtechnology.com/news/new-hope-quantum-computers-factorizations-rsa-thousand-fold-excess/?utm_source=IQT+Daily+Newsletter&utm_campaign=a7528b4239-RSS_EMAIL_CAMPAIGN&utm_medium=email&utm_term=0_e8f238b4dd-a7528b4239-72197729> 
> 
> On 4/14/2019, 23:37, "Peter Gutmann" <[email-masked] <mailto:[email-masked]>> wrote:
> 
>     Björn Haase <[email-masked] <mailto:[email-masked]>> writes:
> 
>     >probability that we'd actually need it might be small..
> 
> [email-masked] <mailto:[email-masked]>
> https://www.irtf.org/mailman/listinfo/cfrg <https://www.irtf.org/mailman/listinfo/cfrg>

---

From: "Paterson Kenneth" <[email-masked]>
Date: Mon, 15 Apr 2019 21:01:16 +0000

Hi,

I read that Nature paper at the time it appeared. It was not clear to me that they had actually factored any number larger than 143 using a D-wave machine. Certainly, the paper presents no experimental data beyond N=143 (for which case, see Figure 3, but with no data concerning success probabilities, numbers of experiments, etc).

So I sent the authors some basic questions about scaling and about details of their computations and experiments. (Naturally I first tried to establish my scientific credentials so as not to look like too much of a crank.)

I also asked the authors for data concerning the larger and more impressive numbers mentioned throughout the paper (e.g. 249919).

The authors did not provide this information, in contrast to the statement made towards the end of the paper concerning data availability:

“The data that support the plots within this paper and other findings of this study are available from the corresponding author upon reasonable request.”

Readers may draw their own conclusions from this.

Cheers,

Kenny

PS for those wondering, 143 = 13*11.

From: Cfrg <[email-masked]> on behalf of mcgrew <[email-masked]>
Date: Monday, 15 April 2019 at 21:11
To: Ruslan Kiyanchuk <[email-masked]>
Cc: Björn Haase <[email-masked]>, CFRG <[email-masked]>, Peter Gutmann <[email-masked]>
Subject: Re: [Cfrg] Fwd: I-D Action: draft-yonezawa-pairing-friendly-curves-01.txt

Hi Ruslan,

On Apr 15, 2019, at 2:04 PM, Ruslan Kiyanchuk <[email-masked]<mailto:[email-masked]>> wrote:

David

On Mon, Apr 15, 2019 at 9:09 AM Blumenthal, Uri - 0553 - MITLL <[email-masked]<mailto:[email-masked]>> wrote:
While not a quantum physicist myself, I do think you are downplaying the risks:

On 4/14/2019, 23:37, "Peter Gutmann" <[email-masked]<mailto:[email-masked]>> wrote:

    Peter.

_______________________________________________
Cfrg mailing list
[email-masked]<mailto:[email-masked]>
https://www.irtf.org/mailman/listinfo/cfrg
_______________________________________________
Cfrg mailing list
[email-masked]<mailto:[email-masked]>
https://www.irtf.org/mailman/listinfo/cfrg

---

From: mcgrew <[email-masked]>
Date: Mon, 15 Apr 2019 17:07:53 -0400

Hi Kenny, 

Thanks for sharing your experiences with the authors.   I don’t have any deeper insight into this work; I only cited it as an example of factorization using an adiabatic QC instead of Shor’s algorithm.

David

> On Apr 15, 2019, at 5:01 PM, Paterson Kenneth <[email-masked]> wrote:
> 
> Hi,
>  
> On Apr 15, 2019, at 2:04 PM, Ruslan Kiyanchuk <[email-masked] <mailto:[email-masked]>> wrote:
>  
> It is not that D-Wave can run Shor’s algorithm, but rather that researchers are studying how an adiabatic quantum computer can be used for factoring.  See for instance "Quantum Annealing for Prime Factorization”, https://www.nature.com/articles/s41598-018-36058-z: <https://www.nature.com/articles/s41598-018-36058-z:>

---

From: Peter Gutmann <[email-masked]>
Date: Tue, 16 Apr 2019 00:58:36 +0000

>While not a quantum physicist myself, I do think you are downplaying the risks:

Nor am I, but this guy is, or at least he's a theoretical physicist:

https://spectrum.ieee.org/computing/hardware/the-case-against-quantum-computing

with expected "case against the case" responses, the main one being that as a
theoretical physicist he focuses on somewhat red-herring issues like the issue
of working with continuous parameters rather than the more pressing practical
issues of decoherence and error control, which is what's actually killing it
at any scale beyond "toy lab experiment".

>https://www.insidequantumtechnology.com

That's sort of like going to Russia Today for news about Russia... I chose the
IEEE ref as an example not because it's the perfect critique (it's actually
somewhat flawed) but because they get technically knowledgeable people while
not being outright QC cheerleaders.

>that's not an excuse to ignore the upcoming threat on the algorithmic level.

Sure, but you need to keep in mind when doing that that anything standardised
by the CFRG will be immediately rushed into production by people with no
understanding of how to correctly implement it, deploy it, and apply it,
simply because it's trendy.

Prediction: As soon as any significant standards body like the CFRG
standardises PQC algorithms, there will be not just one but multiple PQC forks
of Bitcoin/blockchain tech and/or new cryptocurrencies built on PQC, not
because it's required or useful but just because it's there.  And the moment
it's done there, the herd will follow because anything that BTC does has to be
good.

Anyone want to make a bet with me on this?  I'll take anything from "dinner at
Tony's Steak House" to "your research funding for the next five years" as the
stake, depending on how strongly you believe in PQC :-).

Peter.

---

From: "A. Huelsing" <[email-masked]>
Date: Tue, 16 Apr 2019 10:37:58 +0200

I am not sure if this reference already came up but let me add a large group of
people with their opinion.
The National Academies of Sciences, Engineering, and Medicine published the
following consensus report:

Quantum Computing <https://www.nap.edu/read/25196>
Progress and Prospects (2019)

Contributors are
National Academies of Sciences, Engineering, and Medicine; Division on
Engineering and Physical Sciences <https://www.nap.edu/author/DEPS>; Computer
Science and Telecommunications Board <https://www.nap.edu/author/CSTB>;
Intelligence Community Studies Board; Committee on Technical Assessment of the
Feasibility and Implications of Quantum Computing
<https://www.nap.edu/initiative/committee-on-technical-assessment-of-the-feasibility-and-implications-of-quantum-computing>;
Emily Grumbling and Mark Horowitz, Editors

Freely available at
https://www.nap.edu/catalog/25196/quantum-computing-progress-and-prospects

While it generally is an interesting read, I would like to draw your attention
to key finding 10 which says:

"Even if a quantum computer that can decrypt current cryptographic ciphers is
more than
a decade off, the hazard of such a machine is high enough—and the time frame for
transitioning to a new
security protocol is sufficiently long and uncertain—that prioritization of the
development,
standardization, and deployment of post-quantum cryptography is critical for
minimizing the chance of a
potential security and privacy disaster."

There also is the urgency caused by the problem that things sent encrypted today
can be stored and decrypted when a sufficiently large quantum computer is
available. But who would store all the encrypted traffic on the Internet....

I do agree that there are a lot of things to get wrong when rolling out new
crypto and that established schemes should be strictly preferred to old schemes
as long as those are still providing the necessary security guarantees.
Admittedly, I am not a pairings person but my impression is that pairings are
not really an example of a long established scheme that we totally figured out
how to implement.  

However, my feeling is that it will still take some time till PQC algorithms for
advanced functionalities are mature enough to be selected and, hence, if people
are already starting to use conventional algorithms of this kind it is probably
a good idea to agree on the right ones. I would just argue that we should make
sure that we can easily replace the conventional schemes we define now with PQC
schemes in the somewhat near future.

Andreas

---

From: "Paul Hoffman" <[email-masked]>
Date: Tue, 16 Apr 2019 07:17:39 -0700

> potential security and privacy disaster."

And key finding 1 which says:

Given the current state of quantum computing and recent rates of 
progress, it is highly unexpected that a quantum computer that can 
compromise RSA 2048 or comparable discrete logarithm-based public key 
cryptosystems will be built within the next decade.

Chapter 7 of that document goes into much more detail about the current 
state of development.

CFRG should look at standardizing only after the PQC community has 
vastly narrowed down the currently-large set of algorithms to hopefully 
just one or two. If an individual organization wants to roll their own 
dice now about using a PQC algorithm for encrypting, they are of course 
free to do so. My personal view of watching the NIST algorithm selection 
process is that such an organization might strongly consider instead 
using larger EC keys until the rest of crypto community has chosen an 
algorithm and looked at safe and unsafe implementations of it.

--Paul Hoffman

---

From: "Salz, Rich" <[email-masked]>
Date: Tue, 16 Apr 2019 18:00:53 +0000

>    So standardising PQC at this point is hugely premature.

Which is what Kenny, one of the CFRG co-chairs, has been saying for a couple of years now.

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Tue, 16 Apr 2019 19:43:29 +0000

> Which is what Kenny, one of the CFRG co-chairs, has been saying for a couple of years now.
    
This is not about whether we're ready to standardize on a PQC at this point. We’re all in agreement that we haven't settled yet on any specific PQC.

This is about whether it's wise to standardize at this point a new non-PQ-resistant crypto. Some, myself included, think it's a bad idea, given the inevitable lag between standardization and deployment, and the (as some of us believe) inevitable need to abolish it.

---

From: Shoko YONEZAWA <[email-masked]>
Date: Mon, 22 Apr 2019 20:26:26 +0900

Hello Mike,

I'm sorry for being late for responding to your comments,
all of which are important and valuable.
Please allow me to reply to all of your comments in this single mail.

Thank you for your suggestions of the curve parameters.
As you mentioned, there are the curve parameters which provide more 
efficient computation than we described,
but we emphasize the implementation status, that is,
whether the curves have been already available.

As for BN462, we refer to the parameters implemented in mcl
(https://github.com/herumi/mcl).
In this implementation, the twisted curve is set to E':y^2=x^3-u+2
and the tower of extension field is F_p6 = F_p2[v] / (v^3 - u - 2).
Their implementation of BLS12-381 has been adopted to Zcash
and we cannot ignore the curve parameters chosen in mcl.
Therefore, we would like to choose the existing curve parameters in our 
draft in order for interoperability.

We understand that the parameters you suggested can indeed improve the 
efficiency.
We can add these parameters to our draft if it is accepted to describe 
multiple parameters.

I would be grateful if my answers could make sense.

Best,
Shoko

On 2019/04/03 18:08, Michael Scott wrote:
>    – If x0 ≡ 7 or 11 mod 12 then x^6 − (1 + √ −1) is irreducible over 
> Fp2 = Fp( √ −1).
> 
> On Sun, Mar 31, 2019 at 8:28 PM Michael Scott <[email-masked] 
> <mailto:[email-masked]>> wrote:
> 
>     Hello Shoko,
> 
>     On the twisted curve you choose E':y^2=x^3-u+2 (and I am unclear
>     where -u+2 came from)
> 
>     I am attempting to implement these curves (and already have BLS381
>     done). Any help is much appreciated.
> 
>     Mike
> 
>     On Fri, Mar 29, 2019 at 10:03 AM Shoko YONEZAWA
>     <[email-masked] <mailto:[email-masked]>> wrote:
> 
>         Hi Mike,
> 
>         This difference is probably caused by representation of an
>         extension field.
>          > OK. However for the BL381 curve for example the G2 generator
>         point does not
>          > On Thu, Mar 28, 2019 at 7:27 AM Shoko YONEZAWA
>         <[email-masked] <mailto:[email-masked]>>
>          > wrote:
>          >
>          >> Hi Mike,
>          >>
>          >>   > It would be helpful for implementors to know if the
>         curves support an
>          >>   > M-Type or D-Type twist.
>          >>   >
>          >>   > BLS381 and BN462 are both M-Type. BLS48_581 is D-Type.
>          >>
>          >>   > Also I think a standard should also include a generator
>         point for G2 for
>          >>   > interoperability, as well as for G1. For example an
>         implementation of
>          >> BLS
>          >>   > short signature probably requires a generator in G2.
>          >>
>          >>> Also I think a standard should also include a generator
>         point for G2 for
>          >>> interoperability, as well as for G1. For example an
>         implementation of BLS
>          >>> On Tue, Mar 19, 2019 at 3:39 AM Shoko YONEZAWA
>         <[email-masked] <mailto:[email-masked]>>
>          >>> wrote:
>          >>>
>          >>>> Dear Mike,
>          >>>>
>          >>>>> The suggested curves do not appear to meet the
>         requirement for subgroup
>          >>>>> “One has to choose parameters so that the cofactors of
>         G_1, G_2 and G_T
>          >>>>> The case could be made that subgroup security is not so
>         important, but
>          >> if
>          >>>> For standardization, we focus on the existing
>         implementations as well as
>          >>>> sufficient security.
>          >>>> parameters if a critical attack for pairing-friendly
>         curves which don't
>          >>>>> important) application where it is a requirement that r-1
>         has a factor
>          >> of
>          >>>>> benefits should I suggest be considered carefully if
>         proposed as more
>          >>>>> disadvantages BN curves, as due to the form of its
>         formula for r, this
>          >>>> We guess that BLS12-381 is chosen for the efficient
>         computation of their
>          >>>>> on the curve over the base field can be multiplied by
>         this co-factor to
>          >>>>> On Thu, Mar 14, 2019 at 3:21 PM Michael Scott
>         <[email-masked] <mailto:[email-masked]>>
>          >>>> wrote:
>          >>>>>
>          >>>>>> Hello,
>          >>>>>>
>          >>>>>> standardized, before unsuitable de-facto standards
>         emerge, which may
>          >>>> not be
>          >>>>>> However I make the following observations about the
>         particular curves
>          >>>>>> suggested.
>          >>>>>>
>          >>>>>> The case could be made that subgroup security is not so
>         important, but
>          >>>> if
>          >>>>>> The curve BN462 is not sub-group secure, as in G_T
>         (p^4-p^2+1) /r has
>          >>>>>> The draft does point out that for BLS curves, when
>         hashing to a point
>          >> in
>          >>>>>> G_1, multiplication by a small co-factor h>1 will always
>         be necessary.
>          >>>>>>
>          >>>>>> In my opinion sub-group security in G_T is particularly
>         important if
>          >> it
>          >>>> is
>          >>>>>> desirable to offload the pairing calculation to an
>         untrusted server,
>          >>>> and so
>          >>>>>> important) application where it is a requirement that
>         r-1 has a factor
>          >>>> of
>          >>>>>> benefits should I suggest be considered carefully if
>         proposed as more
>          >>>>>> disadvantages BN curves, as due to the form of its
>         formula for r, this
>          >> [email-masked] <mailto:[email-masked]>
>          >>>>>
>          >>>>>> wrote:
>          >>>>>>
>          >>>>>>> Hi there,
>          >>>>>>>
>          >>>>>>> Subject: I-D Action:
>         <mailto:[email-masked]>
>         <mailto:[email-masked]>
>          >>>>>>> To: [email-masked] <mailto:[email-masked]>
>          >>>>>>>
>          >>>>>>>
>         https://datatracker..ietf.org/doc/draft-yonezawa-pairing-friendly-curves/
>         <https://datatracker.ietf.org/doc/draft-yonezawa-pairing-friendly-curves/>
>          >>>>>>>
>         tools.ietf.org <http://tools.ietf.org>..
>          >>>>>>>
>          >>>>>>> [email-masked] <mailto:[email-masked]>
>          >>>> [email-masked] <mailto:[email-masked]>
>          >>>> TEL: +81-3-6276-5103
>          >>>>
>          >>>
>          >>>
>          >> [email-masked] <mailto:[email-masked]>
>          >> TEL: +81-3-6276-5103
>          >>
>         [email-masked] <mailto:[email-masked]>
>         TEL: +81-3-6276-5103
> 

-- 
Shoko YONEZAWA
Lepidum Co. Ltd.
[email-masked]
TEL: +81-3-6276-5103

---

From: Michael Scott <[email-masked]>
Date: Mon, 22 Apr 2019 14:46:09 +0100

(Re-sending as this thread has bloated to over 40k bytes)

Hello Shoko,

And thanks for your reply. I am OK with the choice of parameters for the
BLS381 curve.

For the BN462 curve it would be a pity to use a suboptimal representation,
when a better representation is possible. For example in
https://eprint.iacr.org/2017/334.pdf , all the suggested curves use the
simpler form, as it offers "the best possible arithmetic", including the
original BN462 suggested curve.

Maybe, as you suggest, a choice of parameters would be a solution (or some
guidance on how to switch between representations)

Mike

---

From: "Paterson Kenneth" <[email-masked]>
Date: Tue, 23 Apr 2019 13:59:02 +0000

Dear Shoko,

I think it's acceptable to describe a variety of different pairing parameters - some already deployed at scale, and some offering better efficiency/security trade-offs.

Regards,

Kenny

-----Original Message-----
From: Cfrg <[email-masked]> on behalf of Shoko YONEZAWA <[email-masked]>
Date: Monday, 22 April 2019 at 13:27
To: "[email-masked]" <[email-masked]>
Subject: Re: [Cfrg] Fwd: I-D Action: draft-yonezawa-pairing-friendly-curves-01.txt

    Hello Mike,

    

    
    Best,
    Shoko
    
    On 2019/04/03 18:08, Michael Scott wrote:
    >         requirement for
    >         G_1, G_2 and
    
    -- 
    Shoko YONEZAWA
    Lepidum Co. Ltd.
    [email-masked]
    TEL: +81-3-6276-5103