[noise] NXOF?

[Trevor Perrin]

Here's a cleaned-up version of the NXOF idea, including a question for
cryptographers at the end:


Definitions
------------
An NXOF is a stateful object with one method:
 - Hash(input, len)
     - returns byte-sequence of length len

Two functions are used for creating NXOFs:
 - RootHash(protocolname, len)
     - returns bytes that can be used to create a new NXOF
 - CreateNXOF(bytes[1..HASHLEN])
     - returns a new NXOF
     - must be called with a HASHLEN-length byte sequence taken from
the output of Hash() or RootHash().


Discussion
-----------
A root NXOF object will be created by a protocol (like Noise), using h
= RootHash(protocolname, HASHLEN) followed by CreateNXOF(h).

These functions are split into two steps so that the output from
RootHash() can be used by the protocol in addition to creating child
NXOFs (e.g. as a Noise "h" value for channel-binding), or RootHash()
can create multiple NXOFs.

We defined a RootHash() function instead of a "primordial" NXOF object
to prevent such an object from being passed as an NXOF to subfunctions
- it should only be used at the beginning of a protocol to create a
root NXOF.

In more detail, Noise usage would be something like:

InitializeSymmetric:
  h = RootHash(Noise protocol name, HASHLEN)

MixHash:
  h = CreateNXOF(h).Hash(input, HASHLEN)

Calling a PQ KEM:
  h, h' = CreateNXOF(h).Hash(empty, 2*HASHLEN)
  nxof = CreateNXOF(h')
  MixKey(KEM(nxof, ...))

The PQ KEM could derive additional children NXOFs from its NXOF input.
Or, it could just domain-separate its inputs to Hash() by prepending
labels.

Note that to created a "keyed" NXOF for MACs or PRFs we can simply
Hash(key) and then create a child NXOF from the output.


Implementing an NXOF
---------------------

Given an XOF like SHAKE128 or SHAKE256:
 - An NXOF contains an internal "state" of HASHLEN bytes
 - Define a primordial NXOF object with internal state of all-zeros
 - Define RootHash as primordial.Hash
 - Define CreateNXOF as state = input
 - Define Hash(input, len) as XOF(state || input, len)

Given HKDF:
 - As above, but HASH(input, len) is HKDF(salt=state, input, len)

Note that for existing hash functions, we wouldn't re-design all the
Noise hashing around an HKDF-based NXOF.  But we could still provide
such an NXOF to crypto subfunctions like PQ KEMs.

One question is whether one could design NXOF crypto-primitives that
are more efficient than SHAKE-based or HKDF-based constructions.  For
example, could there be a SHAKE variant that uses the "state" as as
the sponge's capacity, instead of prepending it to the sponge's rate?

Trevor