Ogólny model grupy

Ogólny model grupowy jest wyidealizowanym modelem kryptograficznym, w którym przeciwnik ma dostęp tylko do losowo wybranego kodowania grupy , zamiast wydajnych kodowań, takich jak te używane w praktyce przez skończone pola lub grupy krzywych eliptycznych .

Model zawiera wyrocznię , która wykonuje operację grupową . Ta wyrocznia przyjmuje dwa kodowania elementów grupowych jako dane wejściowe i wyprowadza kodowanie trzeciego elementu. Gdyby grupa zezwoliła na parowania , operacja ta byłaby modelowana jako dodatkowa wyrocznia.

Jednym z głównych zastosowań ogólnego modelu grupowego jest analiza obliczeniowych założeń dotyczących twardości . Analiza w ogólnym modelu grupowym może odpowiedzieć na pytanie: „Jaki jest najszybszy ogólny algorytm do złamania założenia o twardości kryptograficznej”. Algorytm ogólny to algorytm, który wykorzystuje tylko operację grupową i nie bierze pod uwagę kodowania grupy. Odpowiedzi na to pytanie dotyczące problemu logarytmu dyskretnego udzielił Victor Shoup przy użyciu ogólnego modelu grupowego. Inne wyniki w ogólnym modelu grupowym to na przykład. Model można również rozszerzyć na inne struktury algebraiczne, np pierścienie .

Ogólny model grupowy cierpi na niektóre z tych samych problemów, co losowy model wyroczni . W szczególności wykazano, używając podobnego argumentu, że istnieją schematy kryptograficzne, które są w sposób możliwy do udowodnienia bezpieczne w ogólnym modelu grupowym, ale które są trywialnie niepewne, gdy kodowanie grup losowych zostanie zastąpione wydajnie obliczalną instancją funkcji kodowania.