Re: [CFRG] draft-irtf-cfrg-vrf-08 research group last call (RGLC)

[Leonid Reyzin <[e-mail]>]

Thank you, Watson, for your comments and for subsequent clarifications!


> My one textual comment is that typically implementation status is in a
> section that says "Note to RFC editor: Remove before publication".
>

Will fix, thanks.


> My one trivial substantive comment is that forcing recomputation by
> the verifier of the points hashed to produce the challenge, rather
> than having them hash the commitments to obtain the challenge and
> verify the equations, prevents batching of verification. In
> applications where multiple proofs are verified at once this is a big
> improvement.
>

As Watson and I clarified in subsequent (private) emails, by adding U and V
(instead of c) to pi_string in Section 5.1 and thus lengthening the proof
(from 80 bytes to 128 bytes for typical parameter values), we can
significantly improve verification times in Section 5.3 when multiple VRFs
are verified in a single batch, by designing a batch verification
algorithm. However, this change does little to improve verification time
when a single VRF is being verified, which is what is currently specified.

Given that this change offers a different point on the bandwidth /
computation tradeoff for batch verification, but requires additional design
and analysis for the batch verification algorithm, and offers little
advantage in the standalone (non-batch) case, I suggest that we consider it
as a different, additional ciphersuite if we feel that there is a
compelling case. The draft is designed in a modular way, so that
ciphersuites can be added as the need arises, without delaying the progress
of the current draft. While batch verification works well when everything
is honest, a single malicious pi will poison the entire batch, forcing
slower verifications. Thus, batch verification is sometimes not a suitable
alternative even when there are many proofs to verify.

[Technical details of bandwidth/computation tradeoff are as follows: if we
include U and V, then steps 5 and 6 of Section 5.3 become equation
verifications, rather than computations. Multiple equation verifications
can be combined into a single equation verification by a random linear
combination of equations. We thus will go from separate exponentiations to
a single multiexponentiation, which is faster, especially for large
batches. We would need to decide how the verifier obtains randomness for
this random linear combination (presumably, by hashing, but details matter)
and analyze exact security of batch verification. This change would not
speed up single-VRF verification by much (because it would combine only two
equations, one of which is already anyway fast because of a fixed B and a
short c, and at the same time it would destroy the advantage of having a
short c, because c would get multiplied by a large random coefficient).]


> My serious substantive comment is that the formation of the
> distinguisher string imposes limitations on the hash2curve registry as
> the encoding is not injective. The anachronist in me suggests RS as a
> way to split the different parts of the distinguisher. Hash points
> seems to assume that the point format will be self-delineating. I
> think this can be fixed as part of the last call comments.
>
>
We have figured out that this formation does not need to assume anything
about the hash2curve registry, after all. It merely needs to assume that
our ciphersuite identifiers in the vrf draft have distinct last bytes (in
any case the current design is based on single-byte ciphersuite
identifiers; if we suddenly go to over 256 ciphersuites, which seems
extremely unlikely, there are reasonable backward-compatible options for
new longer ciphersuite identifiers to coexist with the shorter ones).

Best,

 Leo