Algebraic Algorithms

Algebraic Security Games and Algorithms

We consider algebraic security games  for which we set  to a fixed group description  where  is a cyclic group of prime order  generated by 

In algebraic security games, we syntactically distinguish between elements of group  (written in bold, uppercase letters, e.g.,  ) and all other elements, which must not depend on any group elements.

As an example of an algebraic security game, consider the Computational Diffie-Hellman game , depicted in Figure 1 (left).

The algebraic adversary  additionally returns a representation  of  such that . Figure 1 (Right)

We now define algebraic algorithms. Intuitively, the only way for an algebraic algorithm to output a new group element  is to derive it via group multiplications from known group elements.

Definition (Algebraic algorithm) An algorithm  executed in an algebraic game  is called algebraic if for all group elements  that  outputs (i.e., the elements in bold uppercase letters), it additionally provides the representation of  relative to all previously received group elements. That is, if  is the list of group elements  that has received so far (w.l.o.g.  ), then  must also provide a vector  such that . We denote such an output as .

Generic Security Games and Algorithms

Generic algorithms  are only allowed to use generic properties of group . Informally, an algorithm is generic if it works regardless of what group it is run in. This is usually modeled by giving an algorithm indirect access to group elements via abstract handles. It is straight-forward to translate all of our algebraic games into games that are syntactically compatible with generic algorithms accessing group elements only via abstract handles.

We say that winning algebraic game  is  -hard in the generic group model if for every generic algorithm  it holds that

We remark that usually in the generic group model one considers group operations (i.e., oracle calls) instead of the running time. In our context it is more convenient to measure the running time instead, assuming every oracle call takes one unit time.

As an important example, consider the algebraic Discrete Logarithm Game  in Figure 2 which is  -hard in the generic group model [Sho97, Mau05].

We assume that a generic algorithm  additionally provides the representation of  relative to all previously received group elements, for all group elements  that it outputs. This assumption is w.l.o.g. since a generic algorithm can only obtain new group elements by multiplying two known group elements; hence it always knows a valid representation. This way, every generic algorithm is also an algebraic algorithm.

Furthermore, if  is a generic algorithm and  is an algebraic algorithm, then   is also is an algebraic algorithm. We refer to [Mau05] for more on generic algorithms.

Generic Reductions Between Algebraic Security Games

Let  and  be two algebraic security games. We write  if there exists a generic algorithm  (called generic  -reduction  such that for every algebraic algorithm , algorithm  defined as  satisfies

Note that we deliberately require reduction  to be generic. Hence, if  is algebraic, then  is algebraic; if  is generic, then  is generic. If one is only interested in algebraic adversaries, then it suffices to require reduction  to be algebraic. But in that case one can no longer infer that  is generic in case  is generic.

The following lemma explains how statements in the AGM carry over to the GGM.

Lemma: Let  and  be algebraic security games such that  and winning  is  -hard in the GGM. Then,  is  -hard in the GGM.

. Let  be a generic algorithm playing in game . Then by our premise there exists a generic algorithm  such that

Assume  then .

Since winning  is  -hard in the GGM, it follows that

and thus  which proves that  is  -hard in the GGM.