Groups with pairing are now considered as standard building blocks for cryptographic primitives. The security of schemes based on such groups relies on hypotheses related to the discrete logarithm problem. As these hypotheses are not proved, one would like to have some positive security argument for them. It is usual to assess their security in the so called generic group model introduced by Nechaev and Shoup. Over the time, this model has been extended in different directions to cover new features.
The relevance of this model is nevertheless subject to criticisms: in particular, the fact that the answer to any fresh query is a random bit string is not what one expects from a usual group law.
In this chapter, we first present the original model of Nechaev and Shoup as well as some classical extensions, with a focus on ideas rather than formal correctness. Then, we develop rigorously a generic group model with pairing which generalizes all models seen so far in the literature. We provide a general framework in order to prove difficulty assumptions in this setting. In order to improve the realism of this model, we introduce the notion of pseudo-random families of groups.We show how to reduce the security of a problem in such a family to the security of the same problem in the generic group model and to the security of an underlying strong pseudo-random family of permutations.
IOS Press, Inc.
6751 Tepper Drive
Clifton, VA 20124
Tel.: +1 703 830 6300
Fax: +1 703 830 2300 email@example.com
(Corporate matters and books only) IOS Press c/o Accucoms US, Inc.
For North America Sales and Customer Service
West Point Commons
Lansdale PA 19446
Tel.: +1 866 855 8967
Fax: +1 215 660 5042 firstname.lastname@example.org