Puncte:1

Corelația OWF și iO

drapel br

Care este relația dintre funcțiile unidirecționale (OWF) și ofuscarea indistinguită (iO)? Știu că iO există chiar și atunci când P=NP și OWF nu există. Dar existența OWF implică iO?

Geoffroy Couteau avatar
drapel cn
Rețineți că iO încă implică „moral” OWF: dacă NP nu este conținut în (infinit des) BPP, atunci iO implică OWF - vezi [aici](https://eprint.iacr.org/2014/347.pdf).
Puncte:4
drapel kr

Nu cunoaștem nicio construcție a iO din funcții unidirecționale[*] și ar fi foarte surprinzător dacă ar exista așa ceva. Într-adevăr, iO + OWF implică criptarea cu cheie publică (și diverse alte âcriptomaniaâ primitive), deci dacă numai OWF ar implica iO, ar implica și PKE.

[*] În acest moment, nu cunoaștem nicio construcție a iO din ipoteze standard, punct, din câte știu eu (vezi comentariul lui Geoffroy mai jos).

Fractalice avatar
drapel in
Bănuiesc că nu știm cum să construim PKE din OWF?
drapel kr
Da, și avem motive întemeiate să credem că o astfel de construcție nu ar trebui să existe. De exemplu, se știe că o construcție *cutie neagră* este imposibilă și chiar și unele clase de construcții care nu sunt cutie neagră au fost excluse. Vezi de ex. acest răspuns: https://crypto.stackexchange.com/a/83929/1423
Geoffroy Couteau avatar
drapel cn
„În acest moment, nu cunoaștem nicio construcție a iO din ipoteze standard, punct, din câte știu eu” Nu sunt de acord, acum avem construcții de iO din ipoteze perfect fine: LPN subexponențial pe câmpuri mari + duritatea subexponențială a lui Goldreich PRG + SXDH subexponențial. Toate sunt presupuneri vechi, bine studiate, foarte plauzibile, pe care le-aș numi standard.
drapel kr
Destul de corect, nu am urmărit toate rezultatele recente!

Postează un răspuns

Majoritatea oamenilor nu înțeleg că a pune multe întrebări deblochează învățarea și îmbunătățește legătura interpersonală. În studiile lui Alison, de exemplu, deși oamenii își puteau aminti cu exactitate câte întrebări au fost puse în conversațiile lor, ei nu au intuit legătura dintre întrebări și apreciere. În patru studii, în care participanții au fost implicați în conversații ei înșiși sau au citit transcrieri ale conversațiilor altora, oamenii au avut tendința să nu realizeze că întrebarea ar influența – sau ar fi influențat – nivelul de prietenie dintre conversatori.