ROUND 2 OFFICIAL COMMENT: NewHope

[Martin Tomlinson]

The ISARA corporation have a patent granted in 2017, US Patent 9,698,986 B1 entitled
"Generating Shared Secrets For Lattice-based Cryptographic Protocols”
which seems to have some overlap with the NewHope Round 2 submission.

Claim 1 of the patent is very broad and may cover some of the other Round 2 lattice based submissions.

Maybe these are questions for NIST,
1) Does the NewHope submission (or any other lattice based submissions) need to be modified to avoid the claims of US Patent 9,698,986 ?
2) Should ISARA be approached to obtain an IP declaration regarding their intentions towards PQC submissions?

--Martin

--

PQ Solutions Limited (trading as ‘Post-Quantum’) is a private limited
company incorporated in England and Wales with registered number 06808505.
 

This email is meant only for the intended recipient. If you have received
this email in error, any review, use, dissemination, distribution, or
copying of this email is strictly prohibited. Please notify us immediately
of the error by return email and please delete this message from your
system. Thank you in advance for your cooperation.


For more information
about Post-Quantum, please visit www.post-quantum.com
<http://www.post-quantum.com>.

In the course of our business relationship,
we may collect, store and transfer information about you. Please see our
privacy notice at www.post-quantum.com/privacy-notice
<http://www.post-quantum.com/privacy-notice> to learn about how we use this
information.

[daniel.apon]

Hi Martin,

First: I am not a lawyer. Take anything I say as a layman's reading only. This should not be construed as legal advice.

1) Does the NewHope submission (or any other lattice based submissions) need to be modified to avoid the claims of US Patent 9,698,986 ? 

If you examine the patent itself -- http://patft.uspto.gov/netahtml/PTO/search-bool.html search for "9,698,986 B1" -- you can see that the Detailed Description section of the patent appears to refer to New Hope as prior art.
Specifically, paragraph 3 of the Detailed Description ends with "...resulting in a bandwidth savings in excess of 35% when compared with the New Hope protocol." This looks to me -- as NOT a lawyer -- as if they are primarily describing some kind of efficiency improvement to New Hope and/or RLWE-type KEMs. So, New Hope per se doesn't appear to need to be modified.

2) Should ISARA be approached to obtain an IP declaration regarding their intentions towards PQC submissions? 

If you're a large enough financial target for a patent lawsuit, ask your company's patent lawyer. :-)
We may try to check independently, but in my experience-- people tend to simply not respond to this kind of request from NIST..
I'll update this thread if I hear anything though.


--Daniel

[daniel.apon]

Hi Martin,

I wanted to also make clear that I was speaking from a personal point of view (as opposed to NIST's official point of view, or a lawyer's point of view) in my prior response.

Thanks for understanding,
--Daniel

[Mike Brown]

Hi All,

Thanks everyone for raising this. We had the opportunity to talk to NIST and ISARA will be working together with NIST to provide a royalty-free grant to all schemes in the NIST competition. Our goal is to ensure there is no confusion or concern related to IP so we thought this would be the simplest way to achieve this. We will work with NIST on the mechanics to accomplish this.

Thanks,

Mike Brown
CTO, ISARA

--
You received this message because you are subscribed to the Google Groups "pqc-forum" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+...@list.nist.gov.
Visit this group at https://groups.google.com/a/list.nist.gov/group/pqc-forum/.

[D. J. Bernstein]

Mike Brown writes:
> We had the opportunity to talk to NIST and ISARA will be working
> together with NIST to provide a royalty-free grant to all schemes in
> the NIST competition.

This sounds great if it actually happens. However, I'm concerned about
the following scenario:

* The _hope_ of free use of the patents leads the patents to be given
lower weight in selections than they would normally be given.

* Negotiations between NIST and ISARA drag on, and eventually it
turns out that NIST can't afford ISARA's buyout price.

* The selections thus end up more tilted towards ISARA's patents than
they otherwise would have been.

* Users ask, quite reasonably, why patents weren't assigned a higher
weight in the decision-making process.

Is there a more specific timeframe for "will be working together"?

---Dan

[Mike Brown]

Just to clarify two items.

1) There is no monetary compensation involved nor have we asked for any. ISARA is providing a free, royalty-free license grant. This is to ensure no confusion on status.

2) Discussions started Friday and we will get this sorted as soon as we can.

Thanks,

Mike.

[D. J. Bernstein]

Sanity checks show problems with the NewHope "provable security"
picture. My best guess is that the NewHope team will want to make the
following changes: modify the "DRLWE" definition to divide the number of
"samples" by n, and modify the statement of Theorem 4.4 to replace n and
n with n and 2n.

I don't vouch for the correctness and applicability of the proofs after
these two modifications, but with zero modifications there's a clear
applicability failure (the problem assumed to be hard in the theorem
statement is potentially much weaker than the analyzed problem), and
with only the DRLWE modification there's a clear correctness failure.

See Section 7.5 of my latticeproofs paper for details.

---Dan

[Thomas.Po...@infineon.com]

Dear all, dear Dan,

Indeed that is an inconsistency in the specification, thanks for bringing it to our attention, Dan. We've fixed the notation in the DRLWE definition to make it clear how it counts samples, and in Theorem 4.4 we've replaced the sample counts in the advantage statements with 1 and 2 samples, respectively. An updated version of the specification with these changes fixed has been posted at https://newhopecrypto.org (direct link: https://newhopecrypto.org/data/NewHope_2019_07_10.pdf).

On a side note, we have also fixed several typos and details in the failure analysis (Section D) of the original NewHope paper to which we reference in the NIST submission. The updated paper can be found at https://eprint.iacr.org/2015/1092. We are thankful to Christian Berghoff for thoroughly reporting and helping us to correct several mistakes here.

Thomas (on behalf of the NewHope team)

[David G]

Hi Thomas,

I wanted to reach out to you and the NewHope team before consulting the PQC group regarding this paper "A Complete and Optimized Key Mismatch Attack on NIST Candidate NewHope" [ https://eprint.iacr.org/2019/435.pdf ]

"Then, inspired by Ding et al.’s key mismatch attack, we propose an efficient strategy which with a probability of 96.88% succeeds in recovering all the coefficients in the secret key. Experiments show that our proposed method is very efficient, which completes the attack in about 137.56 ms using the NewHope parameters"

What are your thoughts on this paper, and does the newer version of your paper address this?  I searched through the PQC group postings and haven't found any references to this paper specifically.  Could you address this?  If you'd like to keep the discussions public, I can post my question on the forums too.  I see that there was some minor discussion on Twitter, but so far I haven't been able to find anything else regarding this.

Kind regards,

David Gotrik

To unsubscribe from this group and stop receiving emails from it, send an email to pqc-...@list.nist.gov.

[Leo Ducas]

Dear David,
    
the result of this paper (https://eprint.iacr.org/2019/435 )
 is a refinement in a long line of research, including (non-exhaustively):
   
https://eprint.iacr.org/2016/085
https://eprint.iacr.org/2016/1176
https://eprint.iacr.org/2019/075
    
This line studies active attacks (CCA) on schemes (or versions of 
schemes) designed to only be passively secure (CPA). While it does 
vindicate the importance of CCA security for non-ephemeral uses of 
such schemes, it does *not* affect the security claims of either the 
CPA or the CCA version of NewHope.

In the paper you cited, the CPA vs. CCA ambiguity is resolved in the 
last Section 5:
    
`` It is worth noting that the NewHope KEM submitted to NIST is CPA 
secure, which is then transformed into CCA-secure using 
Fujisaki-Okamoto transformation. Therefore, the proposed key mismatch 
attack does not harm the NewHope designers’ security goals. ''

Best regards
-- Leo