Subject: [Cfrg] Questions regarding new draft-irtf-cfrg-voprf-00 from A. Davidson, N. Sullivan and Chr. Wood // Will we need to consider IPR issues here?

From: Björn Haase <[email-masked]>
Date: Wed, 10 Jul 2019 22:24:36 +0200

Hello to all,

I have just read your recent VOPRF draft from
"https://tools.ietf.org/html/draft-irtf-cfrg-voprf-00" and first, I'd
like to thank the authors for their work. I believe that the OPRF
constructions might become a central primitive for password-based
operations such as PAKE.

In this mail, I would like to raise an unpleasant but maybe un-avoidable
topic: Intellectual property rights regarding efficient hashing to
elliptic curve groups.

For the constructions "OPAQUE" and "strong AuCPace" that Hugo and I did
nominate as candidates for the CFRG PAKE selection process the OPRF is
one important building block and used for keeping the salt value
confidential. In my opinion it is crucial to review and address possible
patent pitfalls regarding the OPRF construction. I also think that it
might be a good idea to prepare workarounds that we could pull out of
our desk -- in case of need.

In the VOPRF draft from July 7th it is suggested to use the
H2C-P256-SHA256-SSWU primitive for NIST P-256. I fully agree with the
authors that using the algorithm SWU *is* the right thing to do security
and efficiency-wise.

However, having worked on PAKE protocols for quite some time, I have
learned the painful lesson, that we need to carefully consider patents
here. I am aware of a patent family claiming priority from FR2946819B1
that claims rights in the context of SWU (for a version in english
language, see e.g. EP2443787B1).  The anticipated expiration will be in
2030. In my opinion this (or possibly other) IPRs are the main
motivation for seemingly strange work-arounds, e.g. in the PACE protocol
constructed by Bender, Kügler and FIschlin as used in electronic travel
documents. Also, I believe that the fact that the SPAKE, TBPEKE and
SESPAKE protocol families requires a trusted setup (with elliptic curve
points having an unknown discrete log relationship) might have come in
solely as part of a patent circumvention strategy.

In order to avoid a mis-understanding. I don't want to state that I
believe that H2C-P256-SHA256-SSWU is rightfully covered by patents.
(Moreover, I am convinced that H2C-Curve25519-SHA512-Elligator2 is not
covered by IPR.) However, I believe that we might seriously consider
this aspect and develop a clear strategy and opinion how to deal with
IPR. I think that it is important to specifically consider the case of
the important curve NIST-P-256.

I would therefore like to ask you whether the IPR aspect has been
considered already and I would like to hear your opinions.

I am not a lawyer, but I believe that there might be circumventions for
the patents also for SWU use on P-256. Still in my own proposal for the
CFRG PAKE selection process, I considered it important to have a
backup-solution readily available for the event that an in
depth-analysis comes to the conclusion that we won't get around the
patent. My suggestion for this case is to use the SPAKE2/TBPEKE/SESPAKE
circumvention approach (and live with the unpleasent need for a trusted
setup of some elliptic curve points).

Last week I have worked on the security proof for the OPRF extension for
"strong AuCPace" and came to the conclusion that (at least for the PAKE
use-case of strong AuCPace) the Diffie-Hellman OPRF construction should
remain secure also when replacing the hash2point(x) result with a point
(C^x * D) with two points with unknown discrete-log relationship. (As
stated in the paper, this will come with slight reductions regarding the
security guarantees due to the trusted setup and an emerging committment
problem in the UC proof restricting security to static adversaries).

I have added the proof as Appendix C in the AuCPace paper
(https://eprint.iacr.org/2018/286) and the patent-circumvention
construction is described in Appendix A. I did not carry out the proof
for the general case, but I believe that the circumvention approach from
Appendix A might also work with Hugo's OPAQUE nomination.

I would really your feedback on these points and again a "sorry" for
bringing up this rather unpleasent topic :-(.

Yours,

Björn

---

From: "Björn Haase" <[email-masked]>
Date: Sat, 13 Jul 2019 23:54:16 +0200

Hi to all,
 
during the last days I have spent a bit of time reviewed the IPR situation for hashing to curves such as P-256. 

The true issue seems rather to be Icart's invention from FR2946818A1 (held by morpho) and not FR2946819B1 (Icart and Coron). Both of these refer to some particular use of SWU for hashing to curves.

After re-reading the patentents, my personal assessment is now that simplified SWU as specified in the hash2curve RFC could be freely used for both, OPRF and PAKE applications also on curves such as P-256. 
However, I'd appreciate if somebody else could have a closer look.

In the more critical patent FR2946818A1 one of the three polynoms from SWU ( P_3(x) ) has been required to be -1 explicitly.
In fact for simplifying SWU, P_3(x) could be chosen such that it is any non-square. It seems that this latter thing
is what the current hash2curve RFC draft is doing when choosing the value Z from section 6.5.2 (i.e. avoiding the non-square value -1 that is claimed in the patent).
I thus conclude that this morpho patent does not apply to the algorithm of the RFC. Also in the text body of the patent I did not find any statement regarding the fact that instead of -1 any non-square could be used, such that any divisional application based on the contents of the descriptive text should not be able to cover the general case of a "non-square" P_3 as used in the RFC.

In fact in the other patent text by Icart and Coron, claim 4 explicitly refers also to the case that P_3(x) from SWU is an arbitrary non-square, i.e. not having the restriction above. However claim 4 of this patent refers to the context of claim 1 only which (in my opinion) does not correspond to what the hash2curve RFC is doing. Thus I believe that also this second patent will not be any issue for what is done in draft-irtf-cfrg-hash-to-curve.

Yours,

Björn.