Re: [Cfrg] Re-review of the four balanced PAKEs

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

Hi Sott,

When you consider the finite field setting (ModP), I think you need to count the cost of the hash-to-field-element operation, which is the equivalent of the hash-to-curve operation in the EC setting. To avoid the need for such an expensive mapping operation, SPEKE uses a safe prime for modulus. But then one exponentiation in SPEKE for 2048-bit modulus is about 7-8 times more expensive than that in J-PAKE. Overall, it can be even more expensive than J-PAKE! This is not reflected in your table. The same issue would apply to other PAKE candidates that rely on hash-to-curve functions.. One might avoid this issue by abandoning the finite field setting, but I think that’s inappropriate for the “completeness” of the protocol specification and the diversity of security choices. After all, the finite field and ECC are just two different ways to implement the same protocol. J-PAKE is specifically designed to eliminate a trusted setup and the need for any hash-to-curve (or the equivalent in the finite field), as neither was considered desirable. I hope this gives more context to understand the design rationale of this protocol.

Cheers,
Feng

Balanced PAKE summary (continued)

Name              | Comp per side (*) | Total Message Size (**)

------------------+-------------------|------------------

CPace             | H+2x              | 2P+2H

J-PAKE            | 2g+3x+3pg+3pv     | 6P+4Z+2H

SPAKE-2           | d+x               | 2P

SPEKE (EC based)  | H+2x              | 2P

SPEKE (ModP based)| 2M                | 2M

Cost:

H: Hash to point

x: Point multiplication

g: Point multiplication of the generator (which is potentially cheaper than a point multiplication of an arbitrary point)

d: Double scalar point multiply and add, that is, aB + cD

pg: Zero knowledge proof generation (approximately the same as a field multiplication)

pv: Zero knowledge proof verification (approximately the same as a double scalar point multiply and add)

M: Modular exponentiation