[curves] MQV

[Watson Ladd]

On Wed, May 14, 2014 at 5:11 PM, Robert Ransom <rransom.8774 at gmail.com> wrote:
> On 5/14/14, Watson Ladd <watsonbladd at gmail.com> wrote:
>> On Wed, May 14, 2014 at 2:38 PM, Robert Ransom <rransom.8774 at gmail.com>
>> wrote:
>>> On 5/14/14, Trevor Perrin <trevp at trevp.net> wrote:
>>>> Anyone know what the best version of MQV is? (HMQV, FHMQV, CMQV, SMQV,
>>>> TMQV,
>>>> ??)
>> [cut]
>>>
>>> I don't see a good reason to use Schnorr's identification protocol
>>> instead of DH authentication, even now that Schnorr's protocol is
>>> legal to use.
>>
>> There is a reason: the Schnorr protocol involves a fixed base
>> exponentiation to a random exponent, while DH authentication involves
>> a variable base exponentiation to a fixed exponent. If you are willing
>> to burn ROM on a table with limited RAM and low CPU power, the Schnorr
>> protocol is more efficient on the prover side.
>
> * 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.
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})

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. It has the advantage of not requiring a random number
generator on constrained hardware.

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. 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.

Sincerely,
Watson Ladd