1545:
854:
the hash to produce the message she sends to Bob, and Bob mixes in his secret value and gives the result back to Alice, who unblinds it to get the final output, Bob is not able to see either Alice's secret value or the final output, and Alice is not able to see Bob's secret input, but Alice sees the
111:
Essentially, a truly random function would just be composed of a lookup table filled with uniformly distributed random entries. However, in practice, a PRF is given an input string in the domain and a hidden random seed and runs multiple times with the same input string and seed, always returning the
115:
A PRF is considered to be good if its behavior is indistinguishable from a truly random function. Therefore, given an output from either the truly random function or a PRF, there should be no efficient method to correctly determine whether the output was produced by the truly random function or the
368:
855:
final output which is a PRF of the two inputs -- a PRF of Alice's secret and Bob's secret. This enables transactions of sensitive cryptographic information to be secure even between untrusted parties.
46:) between a function chosen randomly from the PRF family and a random oracle (a function whose outputs are fixed completely at random). Pseudorandom functions are vital tools in the construction of
850:
In an oblivious pseudorandom function, abbreviated OPRF, information is concealed from two parties that are involved in a PRF. That is, if Alice cryptographically hashes her secret value,
697:
891:; even if the adversary can change the key-distribution depending on the values the hashing function has assigned to the previous keys, the adversary can not force collisions.
167:
649:
571:
108:
A PRF is an efficient (i.e. computable in polynomial time), deterministic function that maps two distinct sets (domain and range) and looks like a truly random function.
415:
223:
818:
755:
601:
259:
787:
724:
512:
485:
203:
270:
96:
are used in most instances where a pseudorandom function is needed, they do not, in general, constitute a pseudorandom function family, as block ciphers such as
839:
532:
455:
435:
1525:
1355:
1208:
1068:
80:
A pseudorandom function family can be constructed from any pseudorandom generator, using, for example, the "GGM" construction given by
112:
same value. Nonetheless, given an arbitrary input string, the output looks random if the seed is taken from a uniform distribution.
1153:
1121:
1003:
859:
1578:
1201:
762:
is the security parameter. That is, for any adversary that can query the oracle of a function sampled from either
1573:
873:
1404:
1054:
1040:. Proceedings of the 22nd USENIX Security Symposium. Washington, DC, USA: USENIX Association. pp. 1–16.
1194:
909:
654:
97:
1520:
1475:
1288:
895:
35:
1399:
127:
1583:
1515:
606:
1505:
1495:
1350:
922:
43:
1500:
1490:
1293:
1253:
1246:
1236:
1231:
888:
851:
537:
47:
1164:
1241:
58:
32:
821:, the advantage that she can tell apart which kind of oracle is given to her is negligible in
384:
208:
1548:
1394:
1340:
1067:
Lauter, Kristin; Kannepalli, Sreekanth; Laine, Kim; Cruz Moreno, Radames (January 1, 2021).
793:
730:
576:
228:
1510:
1434:
954:
765:
702:
490:
463:
363:{\displaystyle f_{s}:\left\{0,1\right\}^{I(n)}\rightarrow \left\{0,1\right\}^{\lambda (n)}}
172:
8:
1273:
905:, which can be locally verified by stations that contain only a small amount of storage.
1379:
1363:
1310:
962:
824:
517:
440:
420:
73:
appear random, regardless of how the corresponding inputs were chosen, as long as the
1439:
1429:
1300:
1149:
1117:
1104:(1985). "On the Cryptographic Applications of Random Functions (Extended Abstract)".
999:
69:
if the input was chosen at random. On the other hand, the guarantee of a PRF is that
1374:
1109:
1097:
971:
950:
946:
85:
982:
1449:
1369:
1330:
1278:
1263:
1141:
1093:
942:
866:
81:
42:
in the following way: no efficient algorithm can distinguish (with significant
1567:
1530:
1485:
1444:
1424:
1320:
1283:
1258:
1113:
1101:
1028:
93:
89:
39:
16:
Collection of efficiently-computable functions which emulate a random oracle
1480:
1325:
1315:
1305:
1268:
1217:
20:
1459:
1419:
1389:
1384:
1345:
1032:
51:
976:
1409:
902:
1027:
1454:
1414:
603:
denote the uniform distribution over the set of all functions from
1108:. Lecture Notes in Computer Science. Vol. 196. p. 276.
1066:
1335:
898:
based) which are provably secure against chosen message attack.
894:
Constructing deterministic, memoryless authentication schemes (
66:
100:
are defined for only limited numbers of input and key sizes.
1069:"Password Monitor: Safeguarding passwords in Microsoft Edge"
1018:
Goldreich's FoC, vol. 1, def. 3.6.4. Pass's notes, def. 96.2
1092:
1034:
Dupless: server-aided encryption for deduplicated storage
941:
865:
An OPRF is used in the
Password Monitor functionality in
381:
There exists a polynomial-time algorithm that computes
1356:
Cryptographically secure pseudorandom number generator
827:
796:
768:
733:
705:
657:
609:
579:
540:
520:
493:
466:
443:
423:
387:
273:
231:
211:
175:
130:
1182:
103:
845:
57:Pseudorandom functions are not to be confused with
833:
812:
781:
749:
718:
691:
643:
595:
565:
526:
506:
479:
449:
429:
409:
362:
253:
217:
197:
161:
1565:
1031:; S. Keelveedhi; T. Ristenpart (August 2013).
1202:
758:are computationally indistinguishable, where
671:
658:
623:
610:
554:
541:
150:
137:
858:An OPRF is used in some implementations of
377:if the following conditions are satisfied:
1209:
1195:
987:
1148:. Cambridge: Cambridge University Press.
1140:
975:
77:was drawn at random from the PRF family.
61:(PRGs). The guarantee of a PRG is that a
1146:Foundations of Cryptography: Basic Tools
1049:
1047:
994:Lindell, Yehuda; Katz, Jonathan (2008).
1566:
998:. Chapman & Hall/CRC. p. 88.
1190:
1044:
692:{\displaystyle \{0,1\}^{\lambda (n)}}
860:password-authenticated key agreement
119:
996:Introduction to Modern Cryptography
955:"How to Construct Random Functions"
124:Pseudorandom functions take inputs
13:
14:
1595:
487:be the distribution of functions
104:Motivations from random functions
1544:
1543:
1216:
1162:
993:
874:Oblivious Pseudorandom Functions
846:Oblivious pseudorandom functions
162:{\displaystyle x\in \{0,1\}^{*}}
1405:Information-theoretic security
1086:
1060:
1021:
1012:
935:
879:
684:
678:
644:{\displaystyle \{0,1\}^{I(n)}}
636:
630:
534:is uniformly distributed over
404:
398:
355:
349:
322:
317:
311:
247:
239:
225:depend only on the index size
191:
183:
1:
1134:
910:identification friend or foe
25:pseudorandom function family
7:
1521:Message authentication code
1476:Cryptographic hash function
1289:Cryptographic hash function
916:
896:message authentication code
566:{\displaystyle \{0,1\}^{n}}
10:
1600:
1400:Harvest now, decrypt later
1539:
1516:Post-quantum cryptography
1468:
1224:
1186:
901:Distributing unforgeable
1579:Cryptographic primitives
1506:Quantum key distribution
1496:Authenticated encryption
1351:Random number generation
1166:A Course in Cryptography
1114:10.1007/3-540-39568-7_22
928:
923:Pseudorandom permutation
872:See the main article on
852:cryptographically blinds
410:{\displaystyle f_{s}(x)}
218:{\displaystyle \lambda }
48:cryptographic primitives
1501:Public-key cryptography
1491:Symmetric-key algorithm
1294:Key derivation function
1254:Cryptographic primitive
1247:Authentication protocol
1237:Outline of cryptography
1232:History of cryptography
1073:Microsoft Research Blog
1055:"Let’s talk about PAKE"
889:dynamic perfect hashing
59:pseudorandom generators
1574:Theory of cryptography
1242:Cryptographic protocol
1106:Advances in Cryptology
884:PRFs can be used for:
835:
814:
813:{\displaystyle RF_{n}}
783:
751:
750:{\displaystyle RF_{n}}
720:
693:
645:
597:
596:{\displaystyle RF_{n}}
567:
528:
508:
481:
451:
431:
411:
371:
364:
264:A family of functions,
255:
254:{\displaystyle n:=|s|}
219:
199:
169:. Both the input size
163:
33:efficiently-computable
1395:End-to-end encryption
1341:Cryptojacking malware
983:web page and preprint
836:
815:
784:
782:{\displaystyle F_{n}}
752:
721:
719:{\displaystyle F_{n}}
694:
646:
598:
568:
529:
509:
507:{\displaystyle f_{s}}
482:
480:{\displaystyle F_{n}}
452:
432:
412:
365:
266:
256:
220:
200:
198:{\displaystyle I=|x|}
164:
92:. While in practice,
31:, is a collection of
1511:Quantum cryptography
1435:Trusted timestamping
825:
794:
766:
731:
703:
655:
607:
577:
538:
518:
491:
464:
441:
421:
385:
271:
229:
209:
173:
128:
50:, especially secure
1274:Cryptographic nonce
1380:Subliminal channel
1364:Pseudorandom noise
1311:Key (cryptography)
963:Journal of the ACM
831:
810:
779:
747:
716:
699:. Then we require
689:
641:
593:
563:
524:
504:
477:
447:
427:
407:
360:
251:
215:
195:
159:
52:encryption schemes
1561:
1560:
1557:
1556:
1440:Key-based routing
1430:Trapdoor function
1301:Digital signature
1155:978-0-511-54689-1
1123:978-3-540-15658-1
1005:978-1-58488-551-1
977:10.1145/6490.6503
947:Goldwasser, Shafi
834:{\displaystyle n}
527:{\displaystyle s}
450:{\displaystyle x}
430:{\displaystyle s}
120:Formal definition
1591:
1584:Pseudorandomness
1547:
1546:
1375:Insecure channel
1211:
1204:
1197:
1188:
1187:
1184:
1183:
1179:
1178:
1176:
1171:
1159:
1128:
1127:
1090:
1084:
1083:
1081:
1079:
1064:
1058:
1051:
1042:
1041:
1039:
1025:
1019:
1016:
1010:
1009:
991:
985:
981:
979:
959:
953:(October 1986).
939:
840:
838:
837:
832:
819:
817:
816:
811:
809:
808:
788:
786:
785:
780:
778:
777:
756:
754:
753:
748:
746:
745:
725:
723:
722:
717:
715:
714:
698:
696:
695:
690:
688:
687:
650:
648:
647:
642:
640:
639:
602:
600:
599:
594:
592:
591:
572:
570:
569:
564:
562:
561:
533:
531:
530:
525:
513:
511:
510:
505:
503:
502:
486:
484:
483:
478:
476:
475:
456:
454:
453:
448:
436:
434:
433:
428:
416:
414:
413:
408:
397:
396:
369:
367:
366:
361:
359:
358:
344:
340:
321:
320:
306:
302:
283:
282:
260:
258:
257:
252:
250:
242:
224:
222:
221:
216:
205:and output size
204:
202:
201:
196:
194:
186:
168:
166:
165:
160:
158:
157:
38:which emulate a
1599:
1598:
1594:
1593:
1592:
1590:
1589:
1588:
1564:
1563:
1562:
1553:
1535:
1464:
1220:
1215:
1174:
1172:
1169:
1156:
1142:Goldreich, Oded
1137:
1132:
1131:
1124:
1091:
1087:
1077:
1075:
1065:
1061:
1053:Matthew Green.
1052:
1045:
1037:
1026:
1022:
1017:
1013:
1006:
992:
988:
957:
943:Goldreich, Oded
940:
936:
931:
919:
882:
848:
826:
823:
822:
804:
800:
795:
792:
791:
773:
769:
767:
764:
763:
741:
737:
732:
729:
728:
710:
706:
704:
701:
700:
674:
670:
656:
653:
652:
626:
622:
608:
605:
604:
587:
583:
578:
575:
574:
557:
553:
539:
536:
535:
519:
516:
515:
498:
494:
492:
489:
488:
471:
467:
465:
462:
461:
442:
439:
438:
422:
419:
418:
392:
388:
386:
383:
382:
345:
330:
326:
325:
307:
292:
288:
287:
278:
274:
272:
269:
268:
246:
238:
230:
227:
226:
210:
207:
206:
190:
182:
174:
171:
170:
153:
149:
129:
126:
125:
122:
106:
71:all its outputs
65:output appears
17:
12:
11:
5:
1597:
1587:
1586:
1581:
1576:
1559:
1558:
1555:
1554:
1552:
1551:
1540:
1537:
1536:
1534:
1533:
1528:
1526:Random numbers
1523:
1518:
1513:
1508:
1503:
1498:
1493:
1488:
1483:
1478:
1472:
1470:
1466:
1465:
1463:
1462:
1457:
1452:
1450:Garlic routing
1447:
1442:
1437:
1432:
1427:
1422:
1417:
1412:
1407:
1402:
1397:
1392:
1387:
1382:
1377:
1372:
1370:Secure channel
1367:
1361:
1360:
1359:
1348:
1343:
1338:
1333:
1331:Key stretching
1328:
1323:
1318:
1313:
1308:
1303:
1298:
1297:
1296:
1291:
1281:
1279:Cryptovirology
1276:
1271:
1266:
1264:Cryptocurrency
1261:
1256:
1251:
1250:
1249:
1239:
1234:
1228:
1226:
1222:
1221:
1214:
1213:
1206:
1199:
1191:
1181:
1180:
1163:Pass, Rafael,
1160:
1154:
1136:
1133:
1130:
1129:
1122:
1098:Goldwasser, S.
1085:
1059:
1043:
1020:
1011:
1004:
986:
970:(4): 792–807.
951:Micali, Silvio
933:
932:
930:
927:
926:
925:
918:
915:
914:
913:
906:
899:
892:
881:
878:
867:Microsoft Edge
847:
844:
843:
842:
830:
807:
803:
799:
776:
772:
744:
740:
736:
713:
709:
686:
683:
680:
677:
673:
669:
666:
663:
660:
638:
635:
632:
629:
625:
621:
618:
615:
612:
590:
586:
582:
560:
556:
552:
549:
546:
543:
523:
501:
497:
474:
470:
458:
446:
426:
406:
403:
400:
395:
391:
357:
354:
351:
348:
343:
339:
336:
333:
329:
324:
319:
316:
313:
310:
305:
301:
298:
295:
291:
286:
281:
277:
249:
245:
241:
237:
234:
214:
193:
189:
185:
181:
178:
156:
152:
148:
145:
142:
139:
136:
133:
121:
118:
105:
102:
27:, abbreviated
15:
9:
6:
4:
3:
2:
1596:
1585:
1582:
1580:
1577:
1575:
1572:
1571:
1569:
1550:
1542:
1541:
1538:
1532:
1531:Steganography
1529:
1527:
1524:
1522:
1519:
1517:
1514:
1512:
1509:
1507:
1504:
1502:
1499:
1497:
1494:
1492:
1489:
1487:
1486:Stream cipher
1484:
1482:
1479:
1477:
1474:
1473:
1471:
1467:
1461:
1458:
1456:
1453:
1451:
1448:
1446:
1445:Onion routing
1443:
1441:
1438:
1436:
1433:
1431:
1428:
1426:
1425:Shared secret
1423:
1421:
1418:
1416:
1413:
1411:
1408:
1406:
1403:
1401:
1398:
1396:
1393:
1391:
1388:
1386:
1383:
1381:
1378:
1376:
1373:
1371:
1368:
1365:
1362:
1357:
1354:
1353:
1352:
1349:
1347:
1344:
1342:
1339:
1337:
1334:
1332:
1329:
1327:
1324:
1322:
1321:Key generator
1319:
1317:
1314:
1312:
1309:
1307:
1304:
1302:
1299:
1295:
1292:
1290:
1287:
1286:
1285:
1284:Hash function
1282:
1280:
1277:
1275:
1272:
1270:
1267:
1265:
1262:
1260:
1259:Cryptanalysis
1257:
1255:
1252:
1248:
1245:
1244:
1243:
1240:
1238:
1235:
1233:
1230:
1229:
1227:
1223:
1219:
1212:
1207:
1205:
1200:
1198:
1193:
1192:
1189:
1185:
1168:
1167:
1161:
1157:
1151:
1147:
1143:
1139:
1138:
1125:
1119:
1115:
1111:
1107:
1103:
1099:
1095:
1094:Goldreich, O.
1089:
1074:
1070:
1063:
1056:
1050:
1048:
1036:
1035:
1030:
1024:
1015:
1007:
1001:
997:
990:
984:
978:
973:
969:
965:
964:
956:
952:
948:
944:
938:
934:
924:
921:
920:
911:
908:Constructing
907:
904:
900:
897:
893:
890:
887:
886:
885:
877:
875:
870:
868:
863:
861:
856:
853:
828:
820:
805:
801:
797:
774:
770:
761:
757:
742:
738:
734:
711:
707:
681:
675:
667:
664:
661:
633:
627:
619:
616:
613:
588:
584:
580:
558:
550:
547:
544:
521:
499:
495:
472:
468:
459:
444:
424:
401:
393:
389:
380:
379:
378:
376:
370:
352:
346:
341:
337:
334:
331:
327:
314:
308:
303:
299:
296:
293:
289:
284:
279:
275:
265:
262:
243:
235:
232:
212:
187:
179:
176:
154:
146:
143:
140:
134:
131:
117:
113:
109:
101:
99:
95:
94:block ciphers
91:
87:
83:
78:
76:
72:
68:
64:
60:
55:
53:
49:
45:
41:
40:random oracle
37:
34:
30:
26:
22:
1481:Block cipher
1326:Key schedule
1316:Key exchange
1306:Kleptography
1269:Cryptosystem
1218:Cryptography
1173:, retrieved
1165:
1145:
1105:
1088:
1076:. Retrieved
1072:
1062:
1033:
1023:
1014:
995:
989:
967:
961:
937:
883:
871:
864:
857:
849:
790:
759:
727:
375:pseudorandom
374:
372:
267:
263:
123:
114:
110:
107:
79:
74:
70:
62:
56:
28:
24:
21:cryptography
18:
1469:Mathematics
1460:Mix network
1175:22 December
880:Application
1568:Categories
1420:Ciphertext
1390:Decryption
1385:Encryption
1346:Ransomware
1135:References
1102:Micali, S.
1078:January 1,
1029:M. Bellare
903:ID numbers
573:, and let
417:given any
86:Goldwasser
1410:Plaintext
676:λ
347:λ
323:→
213:λ
155:∗
135:∈
82:Goldreich
44:advantage
36:functions
1549:Category
1455:Kademlia
1415:Codetext
1358:(CSPRNG)
1144:(2001).
917:See also
912:systems.
75:function
1225:General
1057:. 2018.
1336:Keygen
1152:
1120:
1002:
514:where
90:Micali
88:, and
67:random
63:single
1366:(PRN)
1170:(PDF)
1038:(PDF)
958:(PDF)
929:Notes
116:PRF.
1177:2015
1150:ISBN
1118:ISBN
1080:2021
1000:ISBN
726:and
460:Let
437:and
23:, a
1110:doi
972:doi
789:or
651:to
373:is
98:AES
29:PRF
19:In
1570::
1116:.
1100:;
1096:;
1071:.
1046:^
968:33
966:.
960:.
949:;
945:;
876:.
869:.
862:.
261:.
236::=
84:,
54:.
1210:e
1203:t
1196:v
1158:.
1126:.
1112::
1082:.
1008:.
980:.
974::
841:.
829:n
806:n
802:F
798:R
775:n
771:F
760:n
743:n
739:F
735:R
712:n
708:F
685:)
682:n
679:(
672:}
668:1
665:,
662:0
659:{
637:)
634:n
631:(
628:I
624:}
620:1
617:,
614:0
611:{
589:n
585:F
581:R
559:n
555:}
551:1
548:,
545:0
542:{
522:s
500:s
496:f
473:n
469:F
457:.
445:x
425:s
405:)
402:x
399:(
394:s
390:f
356:)
353:n
350:(
342:}
338:1
335:,
332:0
328:{
318:)
315:n
312:(
309:I
304:}
300:1
297:,
294:0
290:{
285::
280:s
276:f
248:|
244:s
240:|
233:n
192:|
188:x
184:|
180:=
177:I
151:}
147:1
144:,
141:0
138:{
132:x
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.