Abstrakt. En beräkningsgrupp är pseudo-fri om en motståndare inte kan hitta lösningar i denna grupp för ekvationer som inte är trivialt lösliga i den fria gruppen. Detta begrepp framfördes av Rivest som en enande abstraktion av flera grupprelaterade hårdhetsantaganden som vanligen används i kryptografi. Rivests gissning att RSA-koncernen är pseudo-fri hade lösts av Micciancio för RSA moduli som är en produkt av två säkra primer. Detta resultat håller för en statisk inställning där motståndaren endast ges beskrivningen av gruppen (tillsammans med en uppsättning slumpmässigt utvalda generatorer) och måste komma upp med ekvationen och lösningen. I detta dokument utforskar vi en kraftfull utvidgning av begreppet pseudofrihet. Vi identifierar, motiverar och studerar pseudo-frihet inför adaptiva motståndare som kan lära sig lösningar på andra icke-triviala ekvationer innan vi måste lösa en ny icke-trivial ekvation. Vårt första bidrag är en noggrant utformad definition av adaptiv pseudofrihet som går en fin linje mellan att vara för svag och att vara otillfredsställande. Vi ger generiska konstruktioner som visar hur alla grupper som uppfyller vår definition kan användas för att konstruera digitala signaturer och nätverkssignaturer. Därefter bevisar vi att RSA-gruppen uppfyller vår strängare uppfattning om pseudofrihet och som en följd av detta får vi olika resultat. Först får vi ett nytt nätverk (homomorphic) signatursystem i standardmodellen. För det andra visar vi att vår ram för signaturer är generell genom att visa att alla befintliga starka RSA-baserade signatursystem är en omedelbar del av vår allmänna konstruktion i RSA-gruppen.
Det senaste förslaget är av Catalano, Fiore och Warinschi som föreslår en homomorfisk nätverkskodning signatur som en tillämpning av begreppet Adaptive Pseudo-Free grupper REF.
Adaptive pseudo-free groups and applications
{'venue': 'Advances in Cryptology – EUROCRYPT 2011', 'journal': None, 'mag_field_of_study': ['Computer Science']}