Re: [Cfrg] J-PAKE and Schnorr NIZK for informational RFCs

Mike Hamburg <> Tue, 15 November 2016 00:55 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id 11006129593 for <>; Mon, 14 Nov 2016 16:55:41 -0800 (PST)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -3.499
X-Spam-Status: No, score=-3.499 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, RP_MATCHES_RCVD=-1.497, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001] autolearn=ham autolearn_force=no
Authentication-Results: (amavisd-new); dkim=pass (1024-bit key)
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id fMhHFKATtVUW for <>; Mon, 14 Nov 2016 16:55:38 -0800 (PST)
Received: from ( []) by (Postfix) with ESMTP id 10EA6129452 for <>; Mon, 14 Nov 2016 16:55:38 -0800 (PST)
Received: from [] (unknown []) (Authenticated sender: mike) by (Postfix) with ESMTPSA id 36F569FCB3; Mon, 14 Nov 2016 16:55:20 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=sldo; t=1479171320; bh=QQZc6zas8vrVVHS4ARIe4hxLPpvT23i4KGF+M9+lao8=; h=From:Subject:Date:In-Reply-To:Cc:To:References:From; b=i+GcO6Wpade00yzjn1VbC2BFAStJ7VmoRV7mTqvB/7CgGUW256wxlouQlDb9anqk5 mbIPp4ZPfbiU1q+Z1kKAAhNePxWpmuS+R/WzBpk/lALnfFK/7oOIs74ikTU4Sj+wjv h8O2TYPJjt2wAE5o8NGzADRylLDE6Co+P1J6C3Qo=
From: Mike Hamburg <>
Message-Id: <>
Content-Type: multipart/signed; boundary="Apple-Mail=_23E1982E-7673-4458-873E-526F958275D1"; protocol="application/pkcs7-signature"; micalg="sha1"
Mime-Version: 1.0 (Mac OS X Mail 10.2 \(3254\))
Date: Mon, 14 Nov 2016 16:55:35 -0800
In-Reply-To: <>
To: Feng Hao <>
References: <> <> <>
X-Mailer: Apple Mail (2.3254)
X-Virus-Scanned: clamav-milter 0.99.2 at astral
X-Virus-Status: Clean
Archived-At: <>
Cc: "" <>
Subject: Re: [Cfrg] J-PAKE and Schnorr NIZK for informational RFCs
X-Mailman-Version: 2.1.17
Precedence: list
List-Id: Crypto Forum Research Group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Tue, 15 Nov 2016 00:55:41 -0000

I’d like to note that for both SPEKE and SPAKE2-EE, the encoding to the curve doesn’t need to be uniform.  It just needs to be inverse-sampleable and within some reasonable factor of uniform.  This means that either SWU or Elligator can be used for this purpose.

If you’re doing SPEKE on a Montgomery curve y^2 = x(x^2+Ax+1), such as X25519, then Elligator2 is actually pretty simple to specify:

Let u be a fixed quadratic non-residue.  For example, u=-1 for 3mod4, or u=2 for 5mod 8.  (The other reasonable choice is u=sqrt(-1) for 5mod 8.)

Take as input a sequence of bytes to be encoded, eg h=really_slow_hash(salt,password).  Convert it to a field element using a little-endian convention, because Montgomery curves are Bernstein country.

Let x := -A / (1+u*h^2).

if x*(x^2+A*x+1) isn’t square, then change x := -A-x, which is also equal to x*u*h^2 by construction.

Now x is the x-coordinate of a point on the curve.  In the unlikely event that 1+uh^2=0, then the output is 0, or the point at infinity, or 0/0, or whatever.  These are all equivalent for SPEKE-X25519.  It doesn’t matter whether the point is in the subgroup or not, because you’ll multiply by the cofactor during the scalar mul.

For SPAKE2-EE, the specification is more complicated, but not by much.

Efficiency-wise, this can be implemented in constant time, in approximately the same amount of time as a single square root operation.  So can SWU, if you aren’t on a Montgomery or Edwards curve.

— Mike

> On Nov 14, 2016, at 2:56 PM, Feng Hao <> wrote:
> Hi Watson,
> Can you be specific what alternative you are talking about?
> In [1], J-PAKE is compared with EKE and SPEKE, which are widely considered
> the simplest and the most efficient balanced PAKEs. It is shown that the
> computational efficiency of J-PAKE is about the same as EKE and SPEKE in
> the finite field setting. J-PAKE is better in the EC setting because: 1)
> EKE in EC is unspecified (a straightforward implementation of EKE in EC
> will trivially leak information about the password); 2) SPEKE in EC
> requires an additional primitive of hashing a password to a random point
> on the curve (which is a non-trivial problem on its own). J-PAKE needs 2
> rounds instead of one, which is a downside and is acknowledged in the
> paper. But security is never perfect; it is always a trade-off.
> Two points are worth reminding:
> 1. There is an unfortunate misconception in quite a number of PAKE papers
> in the literature that merely count the number of exponentiations as the
> computational cost without considering the specific group settings
> required by the protocol (e.g., if the protocol accommodates short or long
> exponents). See Section 2.2 in [1] for a full discussion.
> 2. There is also a category of PAKE protocols that assume a trusted setup
> to define the randomness in the group setting: in particular, to define a
> pair of generators whose discrete logarithm must be unknown. SPAKE2 (which
> I understand you¹re working on for an IEFT submission) is only one
> example. Other examples include KOY [2], Jiang-Gong [3] and
> Gennaro-Lindell [4]. Implementing such as trusted set up (i.e., the common
> reference model if you¹re a fan of jargon) is a tricky task. The most
> concrete advice in terms of implementation that you may find is probably
> from Gennaro and Lindell [4]: ³An example of where it is reasonable to
> assume a common reference string is when a large organization wishes to
> implement secure login for its employees. In this case, the organization
> is trusted to choose the common reference string properly, and this string
> can then be hardwired into the software code.² As an example we can have
> Google to define a trusted setup, which will be trusted by its employees.
> However, it will limit the PAKE application to the internal use within
> that organization. EKE, SPEKE and SPEKE do not have this issue.
> Note that I¹m not objecting PAKE protocols that rely on a common reference
> string; they are one category of PAKE designs and are useful in
> specifically identified scenarios. I¹m merely highlighting that there are
> diversified PAKE designs with different assumptions and properties. Having
> the diversity is a good thing in the research field. However, disparaging
> some without noting the weaknesses/merits of others in the context of that
> diversity is not fair.
> Regards,
> Feng
> [1] J-PAE:
> [2] J. Katz, R. Ostrovsky, M. Yung, ³Efficient password-authenticated key
> exchange using human-memorable passwords², Advances in Cryptology, LNCS
> 2045, pp. 475-494, 2001.
> [3] S.Q. Jiang, G. Gong, ³Password based key exchange with mutual
> authentication,² Selected Area in Cryptography, LNCS 3357, pp. 267-279,
> 2004
> [4] R. Gennaro, Y. Lindell, ³A framework for password-based authenticated
> key exchange,² Eurucrypt¹03, LNCS, No. 2656, pp. 524-543, 2003.
> On 14/11/2016 15:14, "Watson Ladd" <> wrote:
>> I'm sad to see J-PAKE continue to have legs given its terrible
>> performance compared to alternatives. What's the point?
>> On Mon, Nov 14, 2016 at 3:53 AM, Feng Hao <>
>> wrote:
>>> Hi,
>>> Recently I submitted J-PAKE and Schnorr NIZK to IETF for "informational
>>> RFC". Both drafts are currently under review in the independent
>>> submission stream.
>>> As per the reviewers' comments, I've revised the drafts to clarify a
>>> few points.
>>> Schnorr draft
>>> * Clarify the parameters for the finite field and elliptic curves. The
>>> DSA/ECDSA parameters are used only as an example; other groups can also
>>> be used.
>>> * Clarify the requirement for the hash function. It needs to be
>>> collision-resistant in a practical realisation with recommended hash
>>> functions given.
>>> J-PAKE draft
>>> * Clarify that key confirmation can be implicit or explicit, and that
>>> explicit key confirmation is recommended in a practical implementation
>>> of J-PAKE.
>>> The latest drafts are below:
>>> Name:           draft-hao-schnorr
>>> Revision:       05
>>> Title:          Schnorr NIZK Proof: Non-interactive Zero Knowledge
>>> Proof for Discrete Logarithm
>>> Document date:  2016-11-14
>>> Group:          Individual Submission
>>> Pages:          11
>>> URL:            
>>> Status:
>>> Htmlized:
>>> Diff: 
>>> Name:           draft-hao-jpake
>>> Revision:       05
>>> Title:          J-PAKE: Password Authenticated Key Exchange by Juggling
>>> Document date:  2016-11-14
>>> Group:          Individual Submission
>>> Pages:          14
>>> URL:            
>>> Status:
>>> Htmlized:
>>> Diff: 
>>> Your comments are most welcome!
>>> Cheers,
>>> Feng
>>> _______________________________________________
>>> Cfrg mailing list
>> -- 
>> "Man is born free, but everywhere he is in chains".
>> --Rousseau.
> _______________________________________________
> Cfrg mailing list