This repository was archived by the owner on Aug 2, 2026. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 2
Expand file tree
/
Copy pathvrf.html
More file actions
1586 lines (1412 loc) · 100 KB
/
Copy pathvrf.html
File metadata and controls
1586 lines (1412 loc) · 100 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html lang="en" xmlns="http://www.w3.org/1999/xhtml" xml:lang="en">
<head profile="http://www.w3.org/2006/03/hcard http://dublincore.org/documents/2008/08/04/dc-html/">
<meta http-equiv="Content-Type" content="text/html; charset=us-ascii" />
<title>Verifiable Random Functions (VRFs)</title>
<style type="text/css" title="Xml2Rfc (sans serif)">
/*<![CDATA[*/
a {
text-decoration: none;
}
/* info code from SantaKlauss at http://www.madaboutstyle.com/tooltip2.html */
a.info {
/* This is the key. */
position: relative;
z-index: 24;
text-decoration: none;
}
a.info:hover {
z-index: 25;
color: #FFF; background-color: #900;
}
a.info span { display: none; }
a.info:hover span.info {
/* The span will display just on :hover state. */
display: block;
position: absolute;
font-size: smaller;
top: 2em; left: -5em; width: 15em;
padding: 2px; border: 1px solid #333;
color: #900; background-color: #EEE;
text-align: left;
}
a.smpl {
color: black;
}
a:hover {
text-decoration: underline;
}
a:active {
text-decoration: underline;
}
address {
margin-top: 1em;
margin-left: 2em;
font-style: normal;
}
body {
color: black;
font-family: verdana, helvetica, arial, sans-serif;
font-size: 10pt;
max-width: 55em;
}
cite {
font-style: normal;
}
dd {
margin-right: 2em;
}
dl {
margin-left: 2em;
}
ul.empty {
list-style-type: none;
}
ul.empty li {
margin-top: .5em;
}
dl p {
margin-left: 0em;
}
dt {
margin-top: .5em;
}
h1 {
font-size: 14pt;
line-height: 21pt;
page-break-after: avoid;
}
h1.np {
page-break-before: always;
}
h1 a {
color: #333333;
}
h2 {
font-size: 12pt;
line-height: 15pt;
page-break-after: avoid;
}
h3, h4, h5, h6 {
font-size: 10pt;
page-break-after: avoid;
}
h2 a, h3 a, h4 a, h5 a, h6 a {
color: black;
}
img {
margin-left: 3em;
}
li {
margin-left: 2em;
margin-right: 2em;
}
ol {
margin-left: 2em;
margin-right: 2em;
}
ol p {
margin-left: 0em;
}
p {
margin-left: 2em;
margin-right: 2em;
}
pre {
margin-left: 3em;
background-color: lightyellow;
padding: .25em;
}
pre.text2 {
border-style: dotted;
border-width: 1px;
background-color: #f0f0f0;
width: 69em;
}
pre.inline {
background-color: white;
padding: 0em;
}
pre.text {
border-style: dotted;
border-width: 1px;
background-color: #f8f8f8;
width: 69em;
}
pre.drawing {
border-style: solid;
border-width: 1px;
background-color: #f8f8f8;
padding: 2em;
}
table {
margin-left: 2em;
}
table.tt {
vertical-align: top;
}
table.full {
border-style: outset;
border-width: 1px;
}
table.headers {
border-style: outset;
border-width: 1px;
}
table.tt td {
vertical-align: top;
}
table.full td {
border-style: inset;
border-width: 1px;
}
table.tt th {
vertical-align: top;
}
table.full th {
border-style: inset;
border-width: 1px;
}
table.headers th {
border-style: none none inset none;
border-width: 1px;
}
table.left {
margin-right: auto;
}
table.right {
margin-left: auto;
}
table.center {
margin-left: auto;
margin-right: auto;
}
caption {
caption-side: bottom;
font-weight: bold;
font-size: 9pt;
margin-top: .5em;
}
table.header {
border-spacing: 1px;
width: 95%;
font-size: 10pt;
color: white;
}
td.top {
vertical-align: top;
}
td.topnowrap {
vertical-align: top;
white-space: nowrap;
}
table.header td {
background-color: gray;
width: 50%;
}
table.header a {
color: white;
}
td.reference {
vertical-align: top;
white-space: nowrap;
padding-right: 1em;
}
thead {
display:table-header-group;
}
ul.toc, ul.toc ul {
list-style: none;
margin-left: 1.5em;
margin-right: 0em;
padding-left: 0em;
}
ul.toc li {
line-height: 150%;
font-weight: bold;
font-size: 10pt;
margin-left: 0em;
margin-right: 0em;
}
ul.toc li li {
line-height: normal;
font-weight: normal;
font-size: 9pt;
margin-left: 0em;
margin-right: 0em;
}
li.excluded {
font-size: 0pt;
}
ul p {
margin-left: 0em;
}
.comment {
background-color: yellow;
}
.center {
text-align: center;
}
.error {
color: red;
font-style: italic;
font-weight: bold;
}
.figure {
font-weight: bold;
text-align: center;
font-size: 9pt;
}
.filename {
color: #333333;
font-weight: bold;
font-size: 12pt;
line-height: 21pt;
text-align: center;
}
.fn {
font-weight: bold;
}
.hidden {
display: none;
}
.left {
text-align: left;
}
.right {
text-align: right;
}
.title {
color: #990000;
font-size: 18pt;
line-height: 18pt;
font-weight: bold;
text-align: center;
margin-top: 36pt;
}
.vcardline {
display: block;
}
.warning {
font-size: 14pt;
background-color: yellow;
}
@media print {
.noprint {
display: none;
}
a {
color: black;
text-decoration: none;
}
table.header {
width: 90%;
}
td.header {
width: 50%;
color: black;
background-color: white;
vertical-align: top;
font-size: 12pt;
}
ul.toc a::after {
content: leader('.') target-counter(attr(href), page);
}
ul.ind li li a {
content: target-counter(attr(href), page);
}
.print2col {
column-count: 2;
-moz-column-count: 2;
column-fill: auto;
}
}
@page {
@top-left {
content: "Internet-Draft";
}
@top-right {
content: "December 2010";
}
@top-center {
content: "Abbreviated Title";
}
@bottom-left {
content: "Doe";
}
@bottom-center {
content: "Expires June 2011";
}
@bottom-right {
content: "[Page " counter(page) "]";
}
}
@page:first {
@top-left {
content: normal;
}
@top-right {
content: normal;
}
@top-center {
content: normal;
}
}
/*]]>*/
</style>
<link href="#rfc.toc" rel="Contents">
<link href="#rfc.section.1" rel="Chapter" title="1 Introduction">
<link href="#rfc.section.1.1" rel="Chapter" title="1.1 Rationale">
<link href="#rfc.section.1.2" rel="Chapter" title="1.2 Requirements">
<link href="#rfc.section.1.3" rel="Chapter" title="1.3 Terminology">
<link href="#rfc.section.2" rel="Chapter" title="2 VRF Algorithms">
<link href="#rfc.section.3" rel="Chapter" title="3 VRF Security Properties">
<link href="#rfc.section.3.1" rel="Chapter" title="3.1 Full Uniqueness or Trusted Uniqueness">
<link href="#rfc.section.3.2" rel="Chapter" title="3.2 Full Collison Resistance or Trusted Collision Resistance">
<link href="#rfc.section.3.3" rel="Chapter" title="3.3 Full Pseudorandomness or Selective Pseudorandomness">
<link href="#rfc.section.3.4" rel="Chapter" title="3.4 A random-oracle-like unpredictability property">
<link href="#rfc.section.4" rel="Chapter" title="4 RSA Full Domain Hash VRF (RSA-FDH-VRF)">
<link href="#rfc.section.4.1" rel="Chapter" title="4.1 RSA-FDH-VRF Proving">
<link href="#rfc.section.4.2" rel="Chapter" title="4.2 RSA-FDH-VRF Proof To Hash">
<link href="#rfc.section.4.3" rel="Chapter" title="4.3 RSA-FDH-VRF Verifying">
<link href="#rfc.section.5" rel="Chapter" title="5 Elliptic Curve VRF (ECVRF)">
<link href="#rfc.section.5.1" rel="Chapter" title="5.1 ECVRF Proving">
<link href="#rfc.section.5.2" rel="Chapter" title="5.2 ECVRF Proof To Hash">
<link href="#rfc.section.5.3" rel="Chapter" title="5.3 ECVRF Verifying">
<link href="#rfc.section.5.4" rel="Chapter" title="5.4 ECVRF Auxiliary Functions">
<link href="#rfc.section.5.4.1" rel="Chapter" title="5.4.1 ECVRF Hash To Curve">
<link href="#rfc.section.5.4.2" rel="Chapter" title="5.4.2 ECVRF Nonce Generation">
<link href="#rfc.section.5.4.3" rel="Chapter" title="5.4.3 ECVRF Hash Points">
<link href="#rfc.section.5.4.4" rel="Chapter" title="5.4.4 ECVRF Decode Proof">
<link href="#rfc.section.5.5" rel="Chapter" title="5.5 ECVRF Ciphersuites">
<link href="#rfc.section.5.6" rel="Chapter" title="5.6 When the ECVRF Keys are Untrusted">
<link href="#rfc.section.5.6.1" rel="Chapter" title="5.6.1 ECVRF Validate Key">
<link href="#rfc.section.6" rel="Chapter" title="6 Implementation Status">
<link href="#rfc.section.7" rel="Chapter" title="7 Security Considerations">
<link href="#rfc.section.7.1" rel="Chapter" title="7.1 Key Generation">
<link href="#rfc.section.7.1.1" rel="Chapter" title="7.1.1 Uniqueness and collision resistance with untrusted keys">
<link href="#rfc.section.7.1.2" rel="Chapter" title="7.1.2 Pseudorandomness with untrusted keys">
<link href="#rfc.section.7.2" rel="Chapter" title="7.2 Selective vs Full Pseudorandomness">
<link href="#rfc.section.7.3" rel="Chapter" title="7.3 Proper pseudorandom nonce for ECVRF">
<link href="#rfc.section.7.4" rel="Chapter" title="7.4 Side-channel attacks">
<link href="#rfc.section.7.5" rel="Chapter" title="7.5 Proofs Provide No Secrecy for VRF Input">
<link href="#rfc.section.7.6" rel="Chapter" title="7.6 Prehashing">
<link href="#rfc.section.7.7" rel="Chapter" title="7.7 Hash function domain separation and future-proofing">
<link href="#rfc.section.8" rel="Chapter" title="8 Change Log">
<link href="#rfc.section.9" rel="Chapter" title="9 Contributors">
<link href="#rfc.references" rel="Chapter" title="10 References">
<link href="#rfc.references.1" rel="Chapter" title="10.1 Normative References">
<link href="#rfc.references.2" rel="Chapter" title="10.2 Informative References">
<link href="#rfc.appendix.A" rel="Chapter" title="A Test Vectors for the ECVRFs">
<link href="#rfc.appendix.A.1" rel="Chapter" title="A.1 ECVRF-P256-SHA256-TAI">
<link href="#rfc.appendix.A.2" rel="Chapter" title="A.2 ECVRF-P256-SHA256-SSWU">
<link href="#rfc.appendix.A.3" rel="Chapter" title="A.3 ECVRF-EDWARDS25519-SHA512-TAI">
<link href="#rfc.appendix.A.4" rel="Chapter" title="A.4 ECVRF-EDWARDS25519-SHA512-ELL2">
<link href="#rfc.authors" rel="Chapter">
<meta name="generator" content="xml2rfc version 2.9.8 - https://tools.ietf.org/tools/xml2rfc" />
<link rel="schema.dct" href="http://purl.org/dc/terms/" />
<meta name="dct.creator" content="Goldberg, S., Reyzin, L., Papadopoulos, D., and J. Vcelak" />
<meta name="dct.identifier" content="urn:ietf:id:draft-irtf-cfrg-vrf-08" />
<meta name="dct.issued" scheme="ISO8601" content="2020-09" />
<meta name="dct.abstract" content="A Verifiable Random Function (VRF) is the public-key version of a keyed cryptographic hash. Only the holder of the private key can compute the hash, but anyone with public key can verify the correctness of the hash. VRFs are useful for preventing enumeration of hash-based data structures. This document specifies several VRF constructions that are secure in the cryptographic random oracle model. One VRF uses RSA and the other VRF uses Eliptic Curves (EC). " />
<meta name="description" content="A Verifiable Random Function (VRF) is the public-key version of a keyed cryptographic hash. Only the holder of the private key can compute the hash, but anyone with public key can verify the correctness of the hash. VRFs are useful for preventing enumeration of hash-based data structures. This document specifies several VRF constructions that are secure in the cryptographic random oracle model. One VRF uses RSA and the other VRF uses Eliptic Curves (EC). " />
</head>
<body>
<table class="header">
<tbody>
<tr>
<td class="left">CFRG</td>
<td class="right">S. Goldberg</td>
</tr>
<tr>
<td class="left">Internet-Draft</td>
<td class="right">Boston University</td>
</tr>
<tr>
<td class="left">Intended status: Standards Track</td>
<td class="right">L. Reyzin</td>
</tr>
<tr>
<td class="left">Expires: May 13, 2021</td>
<td class="right">Boston University and Algorand</td>
</tr>
<tr>
<td class="left"></td>
<td class="right">D. Papadopoulos</td>
</tr>
<tr>
<td class="left"></td>
<td class="right">Hong Kong University of Science and Techology</td>
</tr>
<tr>
<td class="left"></td>
<td class="right">J. Vcelak</td>
</tr>
<tr>
<td class="left"></td>
<td class="right">NS1</td>
</tr>
<tr>
<td class="left"></td>
<td class="right">November 9, 2020</td>
</tr>
</tbody>
</table>
<p class="title">Verifiable Random Functions (VRFs)<br />
<span class="filename">draft-irtf-cfrg-vrf-08</span></p>
<h1 id="rfc.abstract"><a href="#rfc.abstract">Abstract</a></h1>
<p>A Verifiable Random Function (VRF) is the public-key version of a keyed cryptographic hash. Only the holder of the private key can compute the hash, but anyone with public key can verify the correctness of the hash. VRFs are useful for preventing enumeration of hash-based data structures. This document specifies several VRF constructions that are secure in the cryptographic random oracle model. One VRF uses RSA and the other VRF uses Eliptic Curves (EC). </p>
<h1 id="rfc.status"><a href="#rfc.status">Status of This Memo</a></h1>
<p>This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79.</p>
<p>Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet-Drafts is at https://datatracker.ietf.org/drafts/current/.</p>
<p>Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress."</p>
<p>This Internet-Draft will expire on May 13, 2021.</p>
<h1 id="rfc.copyrightnotice"><a href="#rfc.copyrightnotice">Copyright Notice</a></h1>
<p>Copyright (c) 2020 IETF Trust and the persons identified as the document authors. All rights reserved.</p>
<p>This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License.</p>
<hr class="noprint" />
<h1 class="np" id="rfc.toc"><a href="#rfc.toc">Table of Contents</a></h1>
<ul class="toc">
<li>1. <a href="#rfc.section.1">Introduction</a>
</li>
<ul><li>1.1. <a href="#rfc.section.1.1">Rationale</a>
</li>
<li>1.2. <a href="#rfc.section.1.2">Requirements</a>
</li>
<li>1.3. <a href="#rfc.section.1.3">Terminology</a>
</li>
</ul><li>2. <a href="#rfc.section.2">VRF Algorithms</a>
</li>
<li>3. <a href="#rfc.section.3">VRF Security Properties</a>
</li>
<ul><li>3.1. <a href="#rfc.section.3.1">Full Uniqueness or Trusted Uniqueness</a>
</li>
<li>3.2. <a href="#rfc.section.3.2">Full Collison Resistance or Trusted Collision Resistance</a>
</li>
<li>3.3. <a href="#rfc.section.3.3">Full Pseudorandomness or Selective Pseudorandomness</a>
</li>
<li>3.4. <a href="#rfc.section.3.4">A random-oracle-like unpredictability property</a>
</li>
</ul><li>4. <a href="#rfc.section.4">RSA Full Domain Hash VRF (RSA-FDH-VRF)</a>
</li>
<ul><li>4.1. <a href="#rfc.section.4.1">RSA-FDH-VRF Proving</a>
</li>
<li>4.2. <a href="#rfc.section.4.2">RSA-FDH-VRF Proof To Hash</a>
</li>
<li>4.3. <a href="#rfc.section.4.3">RSA-FDH-VRF Verifying</a>
</li>
</ul><li>5. <a href="#rfc.section.5">Elliptic Curve VRF (ECVRF)</a>
</li>
<ul><li>5.1. <a href="#rfc.section.5.1">ECVRF Proving</a>
</li>
<li>5.2. <a href="#rfc.section.5.2">ECVRF Proof To Hash</a>
</li>
<li>5.3. <a href="#rfc.section.5.3">ECVRF Verifying</a>
</li>
<li>5.4. <a href="#rfc.section.5.4">ECVRF Auxiliary Functions</a>
</li>
<ul><li>5.4.1. <a href="#rfc.section.5.4.1">ECVRF Hash To Curve</a>
</li>
<li>5.4.2. <a href="#rfc.section.5.4.2">ECVRF Nonce Generation</a>
</li>
<li>5.4.3. <a href="#rfc.section.5.4.3">ECVRF Hash Points</a>
</li>
<li>5.4.4. <a href="#rfc.section.5.4.4">ECVRF Decode Proof</a>
</li>
</ul><li>5.5. <a href="#rfc.section.5.5">ECVRF Ciphersuites</a>
</li>
<li>5.6. <a href="#rfc.section.5.6">When the ECVRF Keys are Untrusted</a>
</li>
<ul><li>5.6.1. <a href="#rfc.section.5.6.1">ECVRF Validate Key</a>
</li>
</ul></ul><li>6. <a href="#rfc.section.6">Implementation Status</a>
</li>
<li>7. <a href="#rfc.section.7">Security Considerations</a>
</li>
<ul><li>7.1. <a href="#rfc.section.7.1">Key Generation</a>
</li>
<ul><li>7.1.1. <a href="#rfc.section.7.1.1">Uniqueness and collision resistance with untrusted keys</a>
</li>
<li>7.1.2. <a href="#rfc.section.7.1.2">Pseudorandomness with untrusted keys</a>
</li>
</ul><li>7.2. <a href="#rfc.section.7.2">Selective vs Full Pseudorandomness</a>
</li>
<li>7.3. <a href="#rfc.section.7.3">Proper pseudorandom nonce for ECVRF</a>
</li>
<li>7.4. <a href="#rfc.section.7.4">Side-channel attacks</a>
</li>
<li>7.5. <a href="#rfc.section.7.5">Proofs Provide No Secrecy for VRF Input</a>
</li>
<li>7.6. <a href="#rfc.section.7.6">Prehashing</a>
</li>
<li>7.7. <a href="#rfc.section.7.7">Hash function domain separation and future-proofing</a>
</li>
</ul><li>8. <a href="#rfc.section.8">Change Log</a>
</li>
<li>9. <a href="#rfc.section.9">Contributors</a>
</li>
<li>10. <a href="#rfc.references">References</a>
</li>
<ul><li>10.1. <a href="#rfc.references.1">Normative References</a>
</li>
<li>10.2. <a href="#rfc.references.2">Informative References</a>
</li>
</ul><li>Appendix A. <a href="#rfc.appendix.A">Test Vectors for the ECVRFs</a>
</li>
<ul><li>A.1. <a href="#rfc.appendix.A.1">ECVRF-P256-SHA256-TAI</a>
</li>
<li>A.2. <a href="#rfc.appendix.A.2">ECVRF-P256-SHA256-SSWU</a>
</li>
<li>A.3. <a href="#rfc.appendix.A.3">ECVRF-EDWARDS25519-SHA512-TAI</a>
</li>
<li>A.4. <a href="#rfc.appendix.A.4">ECVRF-EDWARDS25519-SHA512-ELL2</a>
</li>
</ul><li><a href="#rfc.authors">Authors' Addresses</a>
</li>
</ul>
<h1 id="rfc.section.1">
<a href="#rfc.section.1">1.</a> <a href="#intro" id="intro">Introduction</a>
</h1>
<h1 id="rfc.section.1.1">
<a href="#rfc.section.1.1">1.1.</a> Rationale</h1>
<p id="rfc.section.1.1.p.1">A Verifiable Random Function (VRF) <a href="#MRV99" class="xref">[MRV99]</a> is the public-key version of a keyed cryptographic hash. Only the holder of the private VRF key can compute the hash, but anyone with corresponding public key can verify the correctness of the hash. </p>
<p id="rfc.section.1.1.p.2">A key application of the VRF is to provide privacy against offline enumeration (e.g. dictionary attacks) on data stored in a hash-based data structure. In this application, a Prover holds the VRF private key and uses the VRF hashing to construct a hash-based data structure on the input data. Due to the nature of the VRF, only the Prover can answer queries about whether or not some data is stored in the data structure. Anyone who knows the public VRF key can verify that the Prover has answered the queries correctly. However no offline inferences (i.e. inferences without querying the Prover) can be made about the data stored in the data strucuture. </p>
<h1 id="rfc.section.1.2">
<a href="#rfc.section.1.2">1.2.</a> Requirements</h1>
<p id="rfc.section.1.2.p.1">The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in <a href="#RFC2119" class="xref">[RFC2119]</a>. </p>
<h1 id="rfc.section.1.3">
<a href="#rfc.section.1.3">1.3.</a> Terminology</h1>
<p id="rfc.section.1.3.p.1">The following terminology is used through this document: </p>
<p></p>
<dl>
<dt>SK:</dt>
<dd style="margin-left: 8">The private key for the VRF. </dd>
<dt>PK:</dt>
<dd style="margin-left: 8">The public key for the VRF. </dd>
<dt>alpha or alpha_string:</dt>
<dd style="margin-left: 8">The input to be hashed by the VRF. </dd>
<dt>beta or beta_string:</dt>
<dd style="margin-left: 8">The VRF hash output. </dd>
<dt>pi or pi_string:</dt>
<dd style="margin-left: 8">The VRF proof. </dd>
<dt>Prover:</dt>
<dd style="margin-left: 8">The Prover holds the private VRF key SK and public VRF key PK. </dd>
<dt>Verifier:</dt>
<dd style="margin-left: 8">The Verifier holds the public VRF key PK. </dd>
</dl>
<p> </p>
<h1 id="rfc.section.2">
<a href="#rfc.section.2">2.</a> VRF Algorithms</h1>
<p id="rfc.section.2.p.1">A VRF comes with a key generation algorithm that generates a public VRF key PK and private VRF key SK. </p>
<p id="rfc.section.2.p.2">The prover hashes an input alpha using the private VRF key SK to obtain a VRF hash output beta </p>
<ul class="empty"><li>beta = VRF_hash(SK, alpha) </li></ul>
<p> The VRF_hash algorithm is deterministic, in the sense that it always produces the same output beta given a pair of inputs (SK, alpha). The prover also uses the private key SK to construct a proof pi that beta is the correct hash output </p>
<ul class="empty"><li>pi = VRF_prove(SK, alpha)</li></ul>
<p> The VRFs defined in this document allow anyone to deterministically obtain the VRF hash output beta directly from the proof value pi as </p>
<ul class="empty"><li>beta = VRF_proof_to_hash(pi)</li></ul>
<p> Notice that this means that </p>
<ul class="empty"><li>VRF_hash(SK, alpha) = VRF_proof_to_hash(VRF_prove(SK, alpha))</li></ul>
<p> and thus this document will specify VRF_prove and VRF_proof_to_hash rather than VRF_hash. </p>
<p id="rfc.section.2.p.3">The proof pi allows a Verifier holding the public key PK to verify that beta is the correct VRF hash of input alpha under key PK. Thus, the VRF also comes with an algorithm </p>
<ul class="empty"><li>VRF_verify(PK, alpha, pi)</li></ul>
<p> that outputs (VALID, beta = VRF_proof_to_hash(pi)) if pi is valid, and INVALID otherwise. </p>
<h1 id="rfc.section.3">
<a href="#rfc.section.3">3.</a> <a href="#secdef" id="secdef">VRF Security Properties</a>
</h1>
<p id="rfc.section.3.p.1">VRFs are designed to ensure the following security properties. </p>
<h1 id="rfc.section.3.1">
<a href="#rfc.section.3.1">3.1.</a> Full Uniqueness or Trusted Uniqueness</h1>
<p id="rfc.section.3.1.p.1">Uniqueness means that, for any fixed public VRF key and for any input alpha, there is a unique VRF output beta that can be proved to be valid. Uniqueness must hold even for an adversarial Prover that knows the VRF private key SK. </p>
<p id="rfc.section.3.1.p.2">More precisely, "full uniqueness" states that a computationally-bounded adversary cannot choose a VRF public key PK, a VRF input alpha, and two proofs pi1 and pi2 such that VRF_verify(PK, alpha, pi1) outputs (VALID, beta1), VRF_verify(PK, alpha, pi2) outputs (VALID, beta2), and beta1 is not equal to beta2. </p>
<p id="rfc.section.3.1.p.3">A slightly weaker security property called "trusted uniqueness" sufficies for many applications. Trusted uniqueness is the same as full uniqueness, but it must hold only if the VRF keys PK and SK were generated in a trustworthy manner. In other words, uniqueness might not hold if keys were generated in an invalid manner or with bad randomness. </p>
<h1 id="rfc.section.3.2">
<a href="#rfc.section.3.2">3.2.</a> Full Collison Resistance or Trusted Collision Resistance</h1>
<p id="rfc.section.3.2.p.1">Like any cryprographic hash function, VRFs need to be collision resistant. Collison resistance must hold even for an adversarial Prover that knows the VRF private key SK. </p>
<p id="rfc.section.3.2.p.2">More precisely, "full collision resistance" states that it should be computationally infeasible for an adversary to find two distinct VRF inputs alpha1 and alpha2 that have the same VRF hash beta, even if that adversary knows the private VRF key SK. </p>
<p id="rfc.section.3.2.p.3">For most applications, a slightly weaker security property called "trusted collision resistance" suffices. Trusted collision resistance is the same as collision resistance, but it holds only if PK and SK were generated in a trustworthy manner. </p>
<h1 id="rfc.section.3.3">
<a href="#rfc.section.3.3">3.3.</a> <a href="#pseudodef" id="pseudodef">Full Pseudorandomness or Selective Pseudorandomness</a>
</h1>
<p id="rfc.section.3.3.p.1">Pseudorandomness ensures that when an adversarial Verifier sees a VRF hash output beta without its corresponding VRF proof pi, then beta is indistinguishable from a random value. </p>
<p id="rfc.section.3.3.p.2">More precisely, suppose the public and private VRF keys (PK, SK) were generated in a trustworthy manner. Pseudorandomness ensures that the VRF hash output beta (without its corresponding VRF proof pi) on any adversarially-chosen "target" VRF input alpha looks indistinguishable from random for any computationally bounded adversary who does not know the private VRF key SK. This holds even if the adversary also gets to choose other VRF inputs alpha' and observe their corresponding VRF hash outputs beta' and proofs pi'. </p>
<p id="rfc.section.3.3.p.3">With "full pseudorandomness", the adversary is allowed to choose the "target" VRF input alpha at any time, even after it observes VRF outputs beta' and proofs pi' on a variety of chosen inputs alpha'. </p>
<p id="rfc.section.3.3.p.4">"Selective pseudorandomness" is a weaker security property which suffices in many applications. Here, the adversary must choose the target VRF input alpha independently of the public VRF key PK, and before it observes VRF outputs beta' and proofs pi' on inputs alpha' of its choice. </p>
<p id="rfc.section.3.3.p.5">It is important to remember that the VRF output beta does not look random to the Prover, or to any other party that knows the private VRF key SK! Such a party can easily distinguish beta from a random value by comparing beta to the result of VRF_hash(SK, alpha). </p>
<p id="rfc.section.3.3.p.6">Also, the VRF output beta does not look random to any party that knows valid VRF proof pi corresponding to the VRF input alpha, even if this party does not know the private VRF key SK. Such a party can easily distinguish beta from a random value by checking whether VRF_verify(PK, alpha, pi) returns (VALID, beta). </p>
<p id="rfc.section.3.3.p.7">Also, the VRF output beta may not look random if VRF key generation was not done in a trustworthy fashion. (For example, if VRF keys were generated with bad randomness.) </p>
<h1 id="rfc.section.3.4">
<a href="#rfc.section.3.4">3.4.</a> A random-oracle-like unpredictability property</h1>
<p id="rfc.section.3.4.p.1">Pseudorandomness, as defined in <a href="#pseudodef" class="xref">Section 3.3</a>, does not hold if the VRF keys were generated adversarially. For instance, if an adversary outputs VRF keys that are deterministically generated (or hard-coded and publicly known), then the outputs are easily derived by anyone. </p>
<p id="rfc.section.3.4.p.2">There is, however, a different type of unpredictability that is desirable in certain VRF applications (such as <a href="#GHMVZ17" class="xref">[GHMVZ17]</a> and <a href="#DGKR18" class="xref">[DGKR18]</a>). This property is similar to the unpredictability achieved by an (ordinary, unkeyed) cryptographic hash function: if the input has enough entropy (i.e., cannot be predicted), then the correct output is indistinguishable from uniform. </p>
<p id="rfc.section.3.4.p.3">A formal definition of this property appears in Section 3.2 of <a href="#DGKR18" class="xref">[DGKR18]</a>. The VRF schemes presented in this specification are believed to satisfy this property if the public key was generated in a trustworthy manner. Additionally, the ECVRF is believed to also satisify this property even if the public key was not generated in a trustworthy manner, as long as the public key satisfies the key validation procedure in <a href="#keycheck" class="xref">Section 5.6</a>.</p>
<h1 id="rfc.section.4">
<a href="#rfc.section.4">4.</a> <a href="#fdh" id="fdh">RSA Full Domain Hash VRF (RSA-FDH-VRF)</a>
</h1>
<p id="rfc.section.4.p.1">The RSA Full Domain Hash VRF (RSA-FDH-VRF) is a VRF that satisfies the "trusted uniqueness", "trusted collision resistance", and "full pseudorandomness" properties defined in <a href="#secdef" class="xref">Section 3</a>. Its security follows from the standard RSA assumption in the random oracle model. Formal security proofs are in <a href="#PWHVNRG17" class="xref">[PWHVNRG17]</a>. </p>
<p id="rfc.section.4.p.2">The VRF computes the proof pi as a deterministic RSA signature on input alpha using the RSA Full Domain Hash Algorithm <a href="#RFC8017" class="xref">[RFC8017]</a> parametrized with the selected hash algorithm. RSA signature verification is used to verify the correctness of the proof. The VRF hash output beta is simply obtained by hashing the proof pi with the selected hash algorithm. </p>
<p id="rfc.section.4.p.3">The key pair for RSA-FDH-VRF MUST be generated in a way that it satisfies the conditions specified in Section 3 of <a href="#RFC8017" class="xref">[RFC8017]</a>. </p>
<p id="rfc.section.4.p.4">In this document, the notation from <a href="#RFC8017" class="xref">[RFC8017]</a> is used. </p>
<p id="rfc.section.4.p.5">Parameters used: </p>
<ul class="empty">
<li>(n, e) - RSA public key</li>
<li>K - RSA private key</li>
<li>k - length in octets of the RSA modulus n (k must be less than 2^32)</li>
</ul>
<p> </p>
<p id="rfc.section.4.p.6">Fixed options: </p>
<ul class="empty">
<li>Hash - cryptographic hash function</li>
<li>hLen - output length in octets of hash function Hash</li>
</ul>
<p> </p>
<p id="rfc.section.4.p.7">Primitives used: </p>
<ul class="empty">
<li>I2OSP - Conversion of a nonnegative integer to an octet string as defined in Section 4.1 of <a href="#RFC8017" class="xref">[RFC8017]</a> </li>
<li>OS2IP - Conversion of an octet string to a nonnegative integer as defined in Section 4.2 of <a href="#RFC8017" class="xref">[RFC8017]</a> </li>
<li>RSASP1 - RSA signature primitive as defined in Section 5.2.1 of <a href="#RFC8017" class="xref">[RFC8017]</a> </li>
<li>RSAVP1 - RSA verification primitive as defined in Section 5.2.2 of <a href="#RFC8017" class="xref">[RFC8017]</a> </li>
<li>MGF1 - Mask Generation Function based on the hash function Hash as defined in Section B.2.1 of <a href="#RFC8017" class="xref">[RFC8017]</a> </li>
<li>|| - octet string concatenation </li>
</ul>
<p> </p>
<h1 id="rfc.section.4.1">
<a href="#rfc.section.4.1">4.1.</a> RSA-FDH-VRF Proving</h1>
<p id="rfc.section.4.1.p.1">RSAFDHVRF_prove(K, alpha_string) </p>
<p id="rfc.section.4.1.p.2">Input: </p>
<ul class="empty">
<li>K - RSA private key</li>
<li>alpha_string - VRF hash input, an octet string</li>
</ul>
<p> </p>
<p id="rfc.section.4.1.p.3">Output: </p>
<ul class="empty"><li>pi_string - proof, an octet string of length k</li></ul>
<p> </p>
<p id="rfc.section.4.1.p.4">Steps: </p>
<ol>
<li>one_string = 0x01 = I2OSP(1, 1), a single octet with value 1</li>
<li>EM = MGF1(one_string || I2OSP(k, 4) || I2OSP(n, k) || alpha_string, k - 1)</li>
<li>m = OS2IP(EM)</li>
<li>s = RSASP1(K, m)</li>
<li>pi_string = I2OSP(s, k)</li>
<li>Output pi_string</li>
</ol>
<p> </p>
<h1 id="rfc.section.4.2">
<a href="#rfc.section.4.2">4.2.</a> RSA-FDH-VRF Proof To Hash</h1>
<p id="rfc.section.4.2.p.1">RSAFDHVRF_proof_to_hash(pi_string) </p>
<p id="rfc.section.4.2.p.2">Input: </p>
<ul class="empty"><li>pi_string - proof, an octet string of length k</li></ul>
<p> </p>
<p id="rfc.section.4.2.p.3">Output: </p>
<ul class="empty"><li>beta_string - VRF hash output, an octet string of length hLen</li></ul>
<p> </p>
<p id="rfc.section.4.2.p.4">Important note: </p>
<ul class="empty"><li>RSAFDHVRF_proof_to_hash should be run only on pi_string that is known to have been produced by RSAFDHVRF_prove, or from within RSAFDHVRF_verify as specified in <a href="#rsaverify" class="xref">Section 4.3</a>.</li></ul>
<p> </p>
<p id="rfc.section.4.2.p.5">Steps: </p>
<ol>
<li>two_string = 0x02 = I2OSP(2, 1), a single octet with value 2</li>
<li>beta_string = Hash(two_string || pi_string)</li>
<li>Output beta_string</li>
</ol>
<p> </p>
<h1 id="rfc.section.4.3">
<a href="#rfc.section.4.3">4.3.</a> <a href="#rsaverify" id="rsaverify">RSA-FDH-VRF Verifying</a>
</h1>
<p id="rfc.section.4.3.p.1">RSAFDHVRF_verify((n, e), alpha_string, pi_string) </p>
<p id="rfc.section.4.3.p.2">Input: </p>
<ul class="empty">
<li>(n, e) - RSA public key</li>
<li>alpha_string - VRF hash input, an octet string</li>
<li>pi_string - proof to be verified, an octet string of length n</li>
</ul>
<p> </p>
<p id="rfc.section.4.3.p.3">Output: </p>
<ul class="empty"><li>("VALID", beta_string), where beta_string is the VRF hash output, an octet string of length hLen; or <br>"INVALID"</li></ul>
<p> </p>
<p id="rfc.section.4.3.p.4">Steps: </p>
<ol>
<li>s = OS2IP(pi_string)</li>
<li>m = RSAVP1((n, e), s)</li>
<li>EM = I2OSP(m, k - 1)</li>
<li>one_string = 0x01 = I2OSP(1, 1), a single octet with value 1</li>
<li>EM' = MGF1(one_string || I2OSP(k, 4) || I2OSP(n, k) || alpha_string, k - 1)</li>
<li>If EM and EM' are equal, output ("VALID", RSAFDHVRF_proof_to_hash(pi_string)); else output "INVALID". </li>
</ol>
<p> </p>
<h1 id="rfc.section.5">
<a href="#rfc.section.5">5.</a> <a href="#ecvrf" id="ecvrf">Elliptic Curve VRF (ECVRF)</a>
</h1>
<p id="rfc.section.5.p.1">The Elliptic Curve Verifiable Random Function (ECVRF) is a VRF that satisfies the trusted uniqueness, trusted collision resistance, and full pseudorandomness properties defined in <a href="#secdef" class="xref">Section 3</a>. The security of this VRF follows from the decisional Diffie-Hellman (DDH) assumption in the random oracle model. Formal security proofs are in <a href="#PWHVNRG17" class="xref">[PWHVNRG17]</a>. </p>
<p id="rfc.section.5.p.2">To additionally satisfy "full uniqueness" and "full collision resistance", the Verifier MUST additionally perform the validation procedure specified in <a href="#keycheck" class="xref">Section 5.6</a> upon receipt of the public VRF key. </p>
<p id="rfc.section.5.p.3">Notation used: </p>
<ul class="empty">
<li>Elliptic curve operations are written in additive notation, with P+Q denoting point addition and x*P denoting scalar multiplication of a point P by a scalar x</li>
<li>x^y - x raised to the power y</li>
<li>x*y - x multiplied by y</li>
<li>s || t - concatenation of octet strings s and t</li>
</ul>
<p> </p>
<p id="rfc.section.5.p.4">Fixed options (specified in <a href="#suites" class="xref">Section 5.5</a>): </p>
<ul class="empty">
<li>F - finite field</li>
<li>2n - length, in octets, of a field element in F, rounded up to the nearest even integer</li>
<li>E - elliptic curve (EC) defined over F</li>
<li>ptLen - length, in octets, of an EC point encoded as an octet string</li>
<li>G - subgroup of E of large prime order</li>
<li>q - prime order of group G</li>
<li>qLen - length of q in octets, i.e., smallest integer such that 2^(8qLen)>q (note that in the typical case, qLen equals 2n or is close to 2n)</li>
<li>cofactor - number of points on E divided by q</li>
<li>B - generator of group G</li>
<li>Hash - cryptographic hash function</li>
<li>hLen - output length in octets of Hash; must be at least 2n</li>
<li>ECVRF_hash_to_curve - a function that hashes strings to an EC point.</li>
<li>ECVRF_nonce_generation - a function that derives a pseudorandom nonce from SK and the input as part of ECVRF proving.</li>
<li>suite_string - a single nonzero octet specifying the ECVRF ciphersuite, which determines the above options as well as type conversions and parameter generation </li>
</ul>
<p> </p>
<p id="rfc.section.5.p.5">Type conversions (specified in <a href="#suites" class="xref">Section 5.5</a>): </p>
<ul class="empty">
<li>int_to_string(a, len) - conversion of nonnegative integer a to to octet string of length len</li>
<li>string_to_int(a_string) - conversion of an octet string a_string to a nonnegative integer</li>
<li>point_to_string - conversion of EC point to an ptLen-octet string</li>
<li>string_to_point - conversion of an ptLen-octet string to EC point. string_to_point returns INVALID if the octet string does not convert to a valid EC point.</li>
<li>Note that with certain software libraries (for big integer and elliptic curve arithmetic), the int_to_string and point_to_string conversions are not needed. For example, in some implementations, EC point operations will take octet strings as inputs and produce octet strings as outputs, without introducing a separate elliptic curve point type. </li>
</ul>
<p> </p>
<p id="rfc.section.5.p.6">Parameters used (the generation of these parameters is specified in <a href="#suites" class="xref">Section 5.5</a>): </p>
<ul class="empty">
<li>SK - VRF private key</li>
<li>x - VRF secret scalar, an integer <ul class="empty"><li>Note: depending on the ciphersuite used, the VRF secret scalar may be equal to SK; else, it is derived from SK </li></ul>
<p> </p>
</li>
<li>Y = x*B - VRF public key, an EC point</li>
</ul>
<p> </p>
<h1 id="rfc.section.5.1">
<a href="#rfc.section.5.1">5.1.</a> <a href="#ecvrfprove" id="ecvrfprove">ECVRF Proving</a>
</h1>
<p id="rfc.section.5.1.p.1">ECVRF_prove(SK, alpha_string) </p>
<p id="rfc.section.5.1.p.2">Input: </p>
<ul class="empty">
<li>SK - VRF private key</li>
<li>alpha_string = input alpha, an octet string</li>
</ul>
<p> </p>
<p id="rfc.section.5.1.p.3">Output: </p>
<ul class="empty"><li>pi_string - VRF proof, octet string of length ptLen+n+qLen</li></ul>
<p> </p>
<p id="rfc.section.5.1.p.4">Steps: </p>
<ol>
<li>Use SK to derive the VRF secret scalar x and the VRF public key Y = x*B <br>(this derivation depends on the ciphersuite, as per <a href="#suites" class="xref">Section 5.5</a>; <br>these values can be cached, for example, after key generation, and need not be rederived each time)</li>
<li>H = ECVRF_hash_to_curve(Y, alpha_string)</li>
<li>h_string = point_to_string(H)</li>
<li>Gamma = x*H</li>
<li>k = ECVRF_nonce_generation(SK, h_string)</li>
<li>c = ECVRF_hash_points(H, Gamma, k*B, k*H) (see <a href="#ecvrfHashPoints" class="xref">Section 5.4.3</a>)</li>
<li>s = (k + c*x) mod q</li>
<li>pi_string = point_to_string(Gamma) || int_to_string(c, n) || int_to_string(s, qLen)</li>
<li>Output pi_string</li>
</ol>
<p> </p>
<h1 id="rfc.section.5.2">
<a href="#rfc.section.5.2">5.2.</a> ECVRF Proof To Hash</h1>
<p id="rfc.section.5.2.p.1">ECVRF_proof_to_hash(pi_string) </p>
<p id="rfc.section.5.2.p.2">Input: </p>
<ul class="empty"><li>pi_string - VRF proof, octet string of length ptLen+n+qLen</li></ul>
<p> </p>
<p id="rfc.section.5.2.p.3">Output: </p>
<ul class="empty">
<li>"INVALID", or </li>
<li>beta_string - VRF hash output, octet string of length hLen</li>
</ul>
<p> </p>
<p id="rfc.section.5.2.p.4">Important note: </p>
<ul class="empty"><li>ECVRF_proof_to_hash should be run only on pi_string that is known to have been produced by ECVRF_prove, or from within ECVRF_verify as specified in <a href="#ecverify" class="xref">Section 5.3</a>.</li></ul>
<p> </p>
<p id="rfc.section.5.2.p.5">Steps: </p>
<ol>
<li>D = ECVRF_decode_proof(pi_string) (see <a href="#ecvrfDecodeProof" class="xref">Section 5.4.4</a>)</li>
<li>If D is "INVALID", output "INVALID" and stop</li>
<li>(Gamma, c, s) = D</li>
<li>three_string = 0x03 = int_to_string(3, 1), a single octet with value 3 </li>
<li>zero_string = 0x00 = int_to_string(0, 1), a single octet with value 0 </li>
<li>beta_string = Hash(suite_string || three_string || point_to_string(cofactor * Gamma) || zero_string)</li>
<li>Output beta_string</li>
</ol>
<p> </p>
<h1 id="rfc.section.5.3">
<a href="#rfc.section.5.3">5.3.</a> <a href="#ecverify" id="ecverify">ECVRF Verifying</a>
</h1>
<p id="rfc.section.5.3.p.1">ECVRF_verify(Y, pi_string, alpha_string) </p>
<p id="rfc.section.5.3.p.2">Input: </p>
<ul class="empty">
<li>Y - public key, an EC point</li>
<li>pi_string - VRF proof, octet string of length ptLen+n+qLen</li>
<li>alpha_string - VRF input, octet string</li>
</ul>
<p> </p>
<p id="rfc.section.5.3.p.3">Output: </p>
<ul class="empty"><li>("VALID", beta_string), where beta_string is the VRF hash output, octet string of length hLen; or <br> "INVALID"</li></ul>
<p> </p>
<p id="rfc.section.5.3.p.4">Steps: </p>
<ol>
<li>D = ECVRF_decode_proof(pi_string) (see <a href="#ecvrfDecodeProof" class="xref">Section 5.4.4</a>)</li>
<li>If D is "INVALID", output "INVALID" and stop</li>
<li>(Gamma, c, s) = D</li>
<li>H = ECVRF_hash_to_curve(Y, alpha_string)</li>
<li>U = s*B - c*Y</li>
<li>V = s*H - c*Gamma</li>
<li>c' = ECVRF_hash_points(H, Gamma, U, V) (see <a href="#ecvrfHashPoints" class="xref">Section 5.4.3</a>)</li>
<li>If c and c' are equal, output ("VALID", ECVRF_proof_to_hash(pi_string)); else output "INVALID" </li>
</ol>
<p> </p>
<h1 id="rfc.section.5.4">
<a href="#rfc.section.5.4">5.4.</a> ECVRF Auxiliary Functions</h1>
<h1 id="rfc.section.5.4.1">
<a href="#rfc.section.5.4.1">5.4.1.</a> <a href="#ecvrfH2C" id="ecvrfH2C">ECVRF Hash To Curve</a>
</h1>
<p id="rfc.section.5.4.1.p.1">The ECVRF_hash_to_curve algorithm takes in the VRF input alpha and converts it to H, an EC point in G. This algorithm is the only place the VRF input alpha is used for proving and verfying. See <a href="#prehash" class="xref">Section 7.6</a> for further discussion. </p>
<p id="rfc.section.5.4.1.p.2">This section specifies a number of such algorithms, which are not compatible with each other. The choice of a particular algorithm from the options specified in this section is made in <a href="#suites" class="xref">Section 5.5</a>.</p>
<h1 id="rfc.section.5.4.1.1">
<a href="#rfc.section.5.4.1.1">5.4.1.1.</a> <a href="#ecvrfH2C1" id="ecvrfH2C1">ECVRF_hash_to_curve_try_and_increment</a>
</h1>
<p id="rfc.section.5.4.1.1.p.1">The following ECVRF_hash_to_curve_try_and_increment(Y, alpha_string) algorithm implements ECVRF_hash_to_curve in a simple and generic way that works for any elliptic curve. </p>
<p id="rfc.section.5.4.1.1.p.2">The running time of this algorithm depends on alpha_string. For the ciphersuites specified in <a href="#suites" class="xref">Section 5.5</a>, this algorithm is expected to find a valid curve point after approximately two attempts (i.e., when ctr=1) on average. </p>
<p id="rfc.section.5.4.1.1.p.3">However, because the running time of algorithm depends on alpha_string, this algorithm SHOULD be avoided in applications where it is important that the VRF input alpha remain secret. </p>
<p id="rfc.section.5.4.1.1.p.4">ECVRF_hash_to_try_and_increment(Y, alpha_string) </p>
<p id="rfc.section.5.4.1.1.p.5">Input: </p>
<ul class="empty">
<li>Y - public key, an EC point</li>
<li>alpha_string - value to be hashed, an octet string</li>
</ul>
<p> </p>
<p id="rfc.section.5.4.1.1.p.6">Output: </p>
<ul class="empty"><li>H - hashed value, a finite EC point in G </li></ul>
<p> </p>
<p id="rfc.section.5.4.1.1.p.7">Fixed option (specified in <a href="#suites" class="xref">Section 5.5</a>): </p>
<ul class="empty"><li>arbitrary_string_to_point - conversion of an arbitrary octet string to an EC point.</li></ul>
<p> </p>
<p id="rfc.section.5.4.1.1.p.8">Steps: </p>
<ol>