An Algebraic Framework for Diffie-Hellman Assumptions

作者：Escala Alex^*; Herold Gottfried; Kiltz Eike; Rafols Carla; Villar Jorge

来源：Journal of Cryptology, 2017, 30(1): 242-288.

DOI：10.1007/s00145-015-9220-6

• Diffie-Hellman assumption
• Generic hardness
• Groth-Sahai proofs
• Hash proof systems
• Public-key encryption

We put forward a new algebraic framework to generalize and analyze Diffie-Hellman like decisional assumptions which allows us to argue about security and applications by considering only algebraic properties. Our Assumption states that it is hard to decide whether a vector in is linearly dependent of the columns of some matrix in sampled according to distribution . It covers known assumptions such as (Linear Assumption) and (the k-Linear Assumption). Using our algebraic viewpoint, we can relate the generic hardness of our assumptions in m-linear groups to the irreducibility of certain polynomials which describe the output of . We use the hardness results to find new distributions for which the Assumption holds generically in m-linear groups. In particular, our new assumptions and are generically hard in bilinear groups and, compared to , have shorter description size, which is a relevant parameter for efficiency in many applications. These results support using our new assumptions as natural replacements for the assumption which was already used in a large number of applications. To illustrate the conceptual advantages of our algebraic framework, we construct several fundamental primitives based on any Assumption. In particular, we can give many instantiations of a primitive in a compact way, including public-key encryption, hash proof systems, pseudo-random functions, and Groth-Sahai NIZK and NIWI proofs. As an independent contribution, we give more efficient NIZK and NIWI proofs for membership in a subgroup of . The results imply very significant efficiency improvements for a large number of schemes.

• 出版日期2017-1