Subject: [Cfrg] Is an ECC public key Uniformly Random?

From: Robert Moskowitz <[email-masked]>
Date: Wed, 14 Apr 2010 08:35:42 -0400

In draft-mcgrew-fundamental-ecc-02.txt, sec 5.3.1 it states:

    The private key z is an integer between 1 and q - 1, inclusive,
    generated uniformly at random.  (See Appendix B regarding random
    integers.)  The public key is the group element
    Y = alpha^z.  Each public key is associated with a particular
    particular parameter set as per Section 3.3.

Is the public key thus uniformly random?

Also if a 256 bit number is uniformly random, is a subset of its bits 
(defined by some function SHORT(n,r)) uniformly random?  (Discussions I 
have read on functions like HMAC-h-n are not clear on this)

If it is, it would simplify HIP HIT generation for a very lightweight 
HIP exchange...

---

From: Robert Moskowitz <[email-masked]>
Date: Wed, 14 Apr 2010 09:07:54 -0400

I got my answer from a different email. The answer is, yes, uniformly 
within the set of possible PKs for the curve. I THINK that is 'good enough'.

Also it seems that the subset of bits is also uniform.

On 04/14/2010 08:35 AM, Robert Moskowitz wrote:
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg
>

---

From: Richard Barnes <[email-masked]>
Date: Wed, 14 Apr 2010 16:28:43 +0300

Don't have a proof, but here's a couple of thoughts:

I actually wondered about the same question a few years ago and ran an  
experiment: I generated a few thousand public keys and ran the NIST  
randomness tests on them.  Based on those tests, at least, the bits in  
the public keys did indeed look pretty random.

Actually, here's a proof sketch:
-- ECC public key has the form (x,y), where x,y in GF(2^n) satisfy the  
curve equations
-- Since the curve equations are quadratic in y, the standard compact  
form of a public key is (x,b), where b is a single bit that indicates  
which of the two possible y values (see, e.g., [1])
-- A random public key is generated as a random element of a cyclic  
group of order p~=2^n
-- So the entropy of the public key is approximately n bits, in a  
representation with n+1 bits
-- So the public key distribution has to be close to uniform, for some  
definition of "close" (e.g., in terms of Kullback-Liebler divergence)

[1] <http://csrc.nist.gov/rng/>
[1] <http://www.hpl.hp.com/techreports/98/HPL-98-94R1.pdf>

On Apr 14, 2010, at 3:35 PM, Robert Moskowitz wrote:

> Also if a 256 bit number is uniformly random, is a subset of its  
> bits (defined by some function SHORT(n,r)) uniformly random?   
> (Discussions I have read on functions like HMAC-h-n are not clear on  
> this)
>
> If it is, it would simplify HIP HIT generation for a very  
> lightweight HIP exchange...
>
>

---

From: "Dan Harkins" <[email-masked]>
Date: Wed, 14 Apr 2010 08:04:11 -0700 (PDT)

Hi Bob,

  I think it depends on your usage before you can say "good enough".

  The shared secret will also be a group element but that isn't uniformly
random so I don't think you can say the public key is either. If z is
random, the public key will be a random element from the set of (x,y)
that satisfy the equation of the curve but that's not the same thing.

  Dan.

---

From: Robert Moskowitz <[email-masked]>
Date: Wed, 14 Apr 2010 11:13:05 -0400

On 04/14/2010 11:04 AM, Dan Harkins wrote:
> random so I don't think you can say the public key is either.

I am not thinking of the shared secret from the ECDH exchange.  Rather 
only the nature of the public key generated from the randomly selected 
private key.

I am aware of nature of DH secrets from discussions aroung kdf-uses ID.

> If z is

---

From: David McGrew <[email-masked]>
Date: Wed, 14 Apr 2010 09:30:20 -0700

Hi Bob,

I think I misled you in my unicast note to you - I was answering a  
question about what uniform randomness means for *private* keys.  I  
was responding to the question that I thought you asked, not to the  
question that you actually asked.

More inline:

> Is the public key thus uniformly random?

Do you mean uniformly random as an element of the EC group (the set of  
all (x,y) pairs satisfying the curve equation)?   Or a uniformly  
random as an octet string?   It is certainly not a random octet  
string, but it is reasonably random as an element of the EC group.    
More precisely, it is reasonable to assume that the computational  
decision diffie-hellman assumption holds in this group (see http://en.wikipedia.org/wiki/Decisional_Diffie%E2%80%93Hellman_assumption) 
.

Why do you need the public key to be random?  Are you assuming that it  
will be unpredictable, say in a model where the public key is  
unpredictable before it is "released" and then afterwards it is made  
public?

> (Discussions I have read on functions like HMAC-h-n are not clear on  

Sure; if X is a uniformly random bit string, then any substring of X  
will be uniformly random as well.

David