[curves] MQV

[Robert Ransom]

On 5/14/14, Watson Ladd <watsonbladd at gmail.com> wrote:
> On Wed, May 14, 2014 at 5:11 PM, Robert Ransom <rransom.8774 at gmail.com>
> wrote:

>> * Schnorr identification requires a minimum of two messages in each
>> direction (the verifier must commit to the challenge at the beginning
>> of the protocol), which adds both complexity and latency to the
>> protocol.
>
> Patent US4995082 seems to describe the following protocol in claim 1
> where V wants to verify P has identity Y=g^x:
>
> P->V: g^r with r random.
> V->P: e
> P->V: x*e+r
>
> (Yes, that is a plus sign)
> There is no hash function, and this is three messages, not four.

There is no commitment scheme of any kind in that protocol, which
means that the verifier can obtain a signature (on any message) as a
result of the protocol.  At the very least, the verifier can use that
to obtain undeniable proof that it communicated with the prover.

In order for Schnorr's identification scheme to be deniable (and/or
compatible with use of the same keypair with signatures), the verifier
must commit to e (in your notation) before the prover sends g^r.  The
most efficient way to do this is to use a hash-based commitment
scheme.

> Because this is a fixed-base I can precompute a large table and do
> only additions. (I can also use signed-bit encodings, etc).
>
> What you seem to propose is the following:
> V->P: g^r
> P->V: H(g^{ar})

Actually, I propose (if a is P's long-term secret key):

V->P: g^r
P uses symmetric cryptography to prove knowledge of g^(ar)

The proof of knowledge can be done in several ways, e.g. using a MAC,
or by including the shared secret g^(ar) in the input to a KDF.

> This is one message shorter, but requires a hash function and does a
> variable-base exponentiation. If we drop the hash function, we have
> exposed a static DH oracle, and so interaction-based attacks become a
> possibility.

The difference here is that the hash function is, in some sense,
separate from the group operation.  (This separation really does
matter for implementation purposes.)

> It has the advantage of not requiring a random number
> generator on constrained hardware.

If the verifier sends a commitment to the challenge first, the prover
can use that commitment as the input to a hash/PRF to generate r
deterministically.


> Which to use is likely to depend on exact details. With more gates
> your protocol saves on interactions and avoids a tricky bit of
> hardware, at the cost of computational performance. Your protocol also
> winds up with a shared key, which is useful to have, while the Schnorr
> protocol does not.

The shared key from DH authentication can't provide forward secrecy,
so I don't consider that to be useful for anything other than
authentication.

(I'm assuming that the parties either already have a shared key or are
deriving a separate shared key at the same time as the authentication
protocol.)

> If gate count matters significantly, I have a RNG
> from somewhere (and the power for it), and only need to do identity
> verification, Schnorr wins out. If the RNG is uncertain, then your
> protocol is a good idea.

I still consider latency and protocol complexity to be more important,
and those argue against Schnorr identification.  (Schnorr signature is
still better, when deniability isn't the goal.)


Robert Ransom