Re: [Cfrg] [CFRG] PAKE / Hash2Curve First Internet draft for balanced CPace subcomponent available

["Hao, Feng" <[e-mail]>]

Dear Bjorn,

> I aim at being fair to all candidates in the discussions and specifically also to J-PAKE.

Thanks for doing this. I believe a fact-based approach is what's needed to drive this process forward. We often see too many opinions which are not substantiated.

> J-PAKE beside the two additional rounds and the efficiency disadvantages, in my opinion has four outstanding points:

Being 2 rounds is a factual limitation for J-PAKE as compared to 1-round PAKE (acknowledged in the original J-PAKE paper). However, in terms of computation efficiency, J-PAKE has no disadvantage if you compare protocols side-by-side fairly.
    
So far, the most established 1-round protocol (without trusted setup) is the (patched) SPEKE, which is specified in ISO/IEC 11770-4 (2017). We can have a fair comparison since neither requires a trusted setup.

 * In the finite field setting, SPEKE requires 2 modular exponentiations (with long exponents) while J-PAKE needs 14 modular exponentiation (with short exponents). Overall, the computational cost of SPEKE is about the same as (or even higher than) J-PAKE. This is explained in the original J-PAKE paper. Unfortunately, several experts in the reviewing process only counted the number of modular exponentiations without considering the critical difference in the bit length on the exponent. The unfortunate use of the long bit length in SPEKE is a known idiosyncrasy in the design, which is rooted in the need to perform an hash-to-field-element operation. Given that CPace is a SPEKE variant, if you specify CPace in the finite field, you should find it will have no computational advantage than J-PAKE for the same reason.
 * In the elliptic curve setting, the SPEKE specification in ISO/IEC 11770-4 is not really established, so its efficiency is yet to be established. For this reason, it cannot be compared with J-PAKE. SPEKE critically depends on a hash-to-curve function (also called Integer-to-Point or I2P in the IEEE P1363.2 and ISO/IEC documents; but it's the same thing). Such a function is provided in ISO/IEC 11770-4, but with the following note

" This function is believed to hold properties of the randomness and onewayness, i.e. converting an integer to a point such that the point is randomly distributed in the selected group and that given current knowledge, recovering the integer from the point is computationally infeasible. This function is also used by IEEE P1363[7]. However, there is no formal security proof of this function published"

The same note might be applicable to the current IETF draft on hash-to-curve. This is why I suggested that we should wait until the IETF draft to be finalized before we can evaluate the security and efficiency of PAKE protocols that critically depend on it.

> Even if it was quite obviously not your main objective, I believe that from all of the advantages the feature 4.) might indeed have been the single one most valuable property of J-PAKE for industry.
    
I agree parents have unfortunately messed up the PAKE field, but if you look at the history of the developments in this field and take a critical view to examine all the proposed solutions, you may find that a more fundamental obstacle in deploying PAKE is actually a technical one.

About 10-20 years ago (IEEE P1363.2 had a public and intensive standardization process on PAKE in 2000-2008), many people believed the PAKE problem had been solved - with an "ideal cipher" that performs a random-oracle like mapping keyed by a low-entry password, you can have a "provably secure" PAKE with formal security proofs. Hence the problem is reduced to a simpler task of instantiating the "ideal cipher". But later it turned out that this was much trickier than what one might have expected. Instead, alternative approaches were proposed based on "trusted setup", and "hash-to-curve" functions. All these proposals were intensively reviewed during the IEEE standardization process, but by the end of 2008 (8 years after when the standardization started and that was the maximum life span normally expected for a standardization project), it became all clear that the PAKE problem had actually remained unsolved, as none of the techniques (including patented ones) was found filling the bill. This was what motivated us to design a practical solution to this engineering problem back in 2008, by taking a fresh and completely different approach. Whether J-PAKE has actually solved this problem of if there will be a better solution remains to be seen but I recall back in the time when I was a PhD student, David Wheeler (Cambridge) used to say to us: 

"In computer science, you can solve any problem by adding an extra layer of indirection, until that extra layer of indirection becomes a new problem."

I'm happy to say, at least, J-PAKE was fully specified and fixed (without any extra layer of indirection) at the time when it was first presented at SPW'08, and since then it hasn't changed despite intensive public scrutiny.