# Abstract Models of Computation in Cryptography

## Ueli Maurer

```
```Computational security proofs in cryptography, without unproven
intractability assumptions, exist today only if one restricts the
computational model. For example, one can prove a lower bound on the
complexity of computing discrete logarithms in a cyclic group if one
considers only generic algorithms which can not exploit the
properties of the representation of the group elements.
We propose an abstract model of computation which allows to capture
such reasonable restrictions on the power of algorithms. The
algorithm interacts with a black-box with hidden internal state
variables which allows to perform a certain set of operations on the
internal state variables, and which provides output only by allowing
to check whether some state variables satisfy certain relations. For
example, generic algorithms correspond to the special case where
only the equality relation, and possibly also an abstract total order
relation, can be tested.
We consider several instantiation of the model and different types
of computational problems and prove a few known and new lower bounds
for computational problems of interest in cryptography, for example
that computing discrete logarithms is generically hard even if
an oracle for the decisional Diffie-Hellman problem and/or other low
degree relations were available.