Re: sntrup761 key size

[Simon Tatham <anakin%pobox.com@localhost>]

Niels Möller <nisse%lysator.liu.se@localhost> wrote:
> But then it seems some implementations instead use a private key size of
> 1763 bytes, where the last 32 bytes are a hash of the public key _K_
> (more precisely, Hash_4(_K_)). Which to me looks like a somewhat weird
> optimization, since this value is very cheap to recompute whenever needed,
> compared to the rest of the decapsulation operation.
> 
> Is there some authoritative spec nailing down the private key size and
> representation?

That hash is mentioned at the top of page 20 of the document you cite:

  *Key-hash caching.* Caching Hash_4(_K_) saves time when K is reused in
  encapsulation or decapsulation. We cache Hash_4(_K_) at the end of
  secret keys.

and is also consistent with the reference implementations and test
vectors at https://ntruprime.cr.yp.to/nist/ntruprime-20190330.html . I
think if anything is an authoritative specification of the bytewise
format, the reference implementations come closest. (Though I also think
that you're right in saying that all the pieces of the secret key are
simply concatenated in the specified order, so that apart from the
existence of that cached hash, there aren't any remaining complications
in the format spec.)

I suppose the rationale is that 32 bytes of storage costs _even_ less
than the time taken to do the hash, and since it's CPU cycles that _can_
be saved, they save them!

But in the SSH usage of NTRU Prime (and indeed all other PQ KEMs so
far), there's no real need to use the prescribed byte encoding of secret
keys in any case, since a key pair is generated, used for one exchange
and discarded all within the same process, so you might as well just
leave it in whatever internal data structure your implementation finds
most useful. Encoding it to a byte string is for people who need to keep
it long-term and maybe share it between multiple implementations.

Cheers,
Simon

-- 
for k in [pow(x,37,0x1a1298d262b49c895d47f) for x in [0x50deb914257022de7fff,
0x213558f2215127d5a2d1, 0x90c99e86d08b91218630, 0x109f3d0cfbf640c0beee7,
0xc83e01379a5fbec5fdd1, 0x19d3d70a8d567e388600e, 0x534e2f6e8a4a33155123]]:
 print("".join([chr(32+3*((k>>x)&1))for x in range(79)])) # <anakin%pobox.com@localhost>