The generic group model
is an idealised cryptographic model, where the adversary is only given access to a randomly chosen encoding of a
group, instead of efficient encodings, such as those used by the
finite field
In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) is a field that contains a finite number of elements. As with any field, a finite field is a set on which the operations of multiplication, addition, subt ...
or
elliptic curve groups used in practice.
The model includes an
oracle
An oracle is a person or agency considered to provide wise and insightful counsel or prophetic predictions, most notably including precognition of the future, inspired by deities. As such, it is a form of divination.
Description
The wor ...
that executes the
group operation
Operation or Operations may refer to:
Arts, entertainment and media
* ''Operation'' (game), a battery-operated board game that challenges dexterity
* Operation (music), a term used in musical set theory
* ''Operations'' (magazine), Multi-Man ...
. This oracle takes two encodings of group elements as input and outputs an encoding of a third element. If the group should allow for a
pairing
In mathematics, a pairing is an ''R''-bilinear map from the Cartesian product of two ''R''- modules, where the underlying ring ''R'' is commutative.
Definition
Let ''R'' be a commutative ring with unit, and let ''M'', ''N'' and ''L'' be ''R''- ...
operation this operation would be modeled as an additional oracle.
One of the main uses of the generic group model is to analyse
computational hardness assumptions
In computational complexity theory, a computational hardness assumption is the hypothesis that a particular problem cannot be solved efficiently (where ''efficiently'' typically means "in polynomial time"). It is not known how to prove (uncondition ...
. An analysis in the generic group model can answer the question: "What is the fastest generic algorithm for breaking a cryptographic hardness assumption". A generic algorithm is an algorithm that only makes use of the group operation, and does not consider the encoding of the group. This question was answered for the discrete logarithm problem by
Victor Shoup
Victor Shoup is a computer scientist and mathematician. He obtained a PhD in computer science from the University of Wisconsin–Madison in 1989, and he did his undergraduate work at the University of Wisconsin-Eau Claire. He is a professor at t ...
using the generic group model.
[ Other results in the generic group model are for instance. The model can also be extended to other algebraic structures like rings.
The generic group model suffers from some of the same problems as the ]random oracle model
In cryptography, a random oracle is an oracle (a theoretical black box) that responds to every ''unique query'' with a (truly) random response chosen uniformly from its output domain. If a query is repeated, it responds the same way every time tha ...
. In particular, it has been shown using a similar argument[Ran Canetti, Oded Goldreich and Shai Halevi, The Random Oracle Methodology Revisited, STOC 1998, pp. 209–21]
(PS and PDF)
that there exist cryptographic schemes which are provably secure
Provable security refers to any type or level of computer security that can be proved. It is used in different ways by different fields.
Usually, this refers to mathematical proofs, which are common in cryptography. In such a proof, the capabiliti ...
in the generic group model but which are trivially insecure once the random group encoding is replaced with an efficiently computable instantiation of the encoding function.
References
Theory of cryptography
{{Cryptographic models