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

From: Nick Sullivan <[email-masked]>
Date: Tue, 9 Feb 2021 12:09:46 -0500

Dear CFRG participants,

The VRF draft has received significant reviews from the RG and the crypto
panel and is ready for last call. This email commences a
2-week last call for this document that will end on Feburary 23, 2021:

https://datatracker.ietf.org/doc/draft-irtf-cfrg-vrf/

If you've read the document by the end of this period and think that it is
ready (or not ready) for publication as an RFC, please send a message in
reply to this email. Detailed comments would be helpful. You can reach out
directly to CFRG chairs ([email-masked]) if you have questions about
process.

Thank you,
Nick & Stanislav & Alexey

---

From: Watson Ladd <[email-masked]>
Date: Tue, 9 Feb 2021 20:19:50 -0800

On Tue, Feb 9, 2021 at 9:10 AM Nick Sullivan
<nick=[email-masked]> wrote:
>
> Dear CFRG participants,
>
> The VRF draft has received significant reviews from the RG and the crypto panel and is ready for last call. This email commences a 2-week last call for this document that will end on Feburary 23, 2021:
>

I have read the document and support publication.

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

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.

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.

Sincerely,
Watson Ladd

-- 
Astra mortemque praestare gradatim

---

From: Leonid Reyzin <[email-masked]>
Date: Thu, 18 Feb 2021 20:56:49 -0500

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

> section that says "Note to RFC editor: Remove before publication".

Will fix, thanks.

> applications where multiple proofs are verified at once this is a big

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

> 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