Generisk gruppmodell

Den generiska gruppmodellen är en idealiserad kryptografisk modell, där motståndaren endast ges tillgång till en slumpmässigt vald kodning av en grupp istället för effektiva kodningar, såsom de som används av det finita fältet eller elliptiska kurvgrupper som används i praktiken.

Modellen inkluderar ett orakel som utför gruppoperationen . Detta orakel tar två kodningar av gruppelement som ingång och matar ut en kodning av ett tredje element. Om gruppen skulle tillåta en parningsoperation skulle denna operation modelleras som ett extra orakel.

En av de huvudsakliga användningsområdena för den generiska gruppmodellen är att analysera antaganden om beräkningshårdhet . En analys i den generiska gruppmodellen kan svara på frågan: "Vad är den snabbaste generiska algoritmen för att bryta ett kryptografiskt hårdhetsantagande". En generisk algoritm är en algoritm som endast använder sig av gruppoperationen och inte tar hänsyn till gruppens kodning. Denna fråga besvarades för det diskreta logaritmproblemet av Victor Shoup med hjälp av den generiska gruppmodellen. Andra resultat i den generiska gruppmodellen är till exempel. Modellen kan också utökas till andra algebraiska strukturer som ringar .

Den generiska gruppmodellen lider av några av samma problem som den slumpmässiga orakelmodellen . I synnerhet har det visats med ett liknande argument att det finns kryptografiska scheman som bevisligen är säkra i den generiska gruppmodellen men som är trivialt osäkra när väl den slumpmässiga gruppkodningen ersätts med en effektivt beräkningsbar instansiering av kodningsfunktionen.