Multilinear and Aggregate Pseudorandom Functions: New Constructions and Improved Security

Michel Abdalla 1, 2, 3 Fabrice Benhamouda 2, 3, 1 Alain Passelègue 3, 2, 1
1 CASCADE - Construction and Analysis of Systems for Confidentiality and Authenticity of Data and Entities
DI-ENS - Département d'informatique de l'École normale supérieure, Inria Paris-Rocquencourt, CNRS - Centre National de la Recherche Scientifique : UMR 8548
Abstract : Since its introduction, pseudorandom functions (PRFs) have become one of the main building blocks of cryptographic protocols. In this work, we revisit two recent extensions of standard PRFs, namely multilinear and aggregate PRFs, and provide several new results for these primitives. In the case of aggregate PRFs, one of our main results is a proof of security for the Naor-Reingold PRF with respect to read-once boolean aggregate queries under the standard Decision Diffie-Hellman problem, which was an open problem. In the case of multilinear PRFs, one of our main contributions is the construction of new multilinear PRFs achieving indistinguishability from random symmetric and skew- symmetric multilinear functions, which was also left as an open problem. In order to achieve these results, our main technical tool is a simple and natural generalization of the recent linear independent polynomial framework for PRFs proposed by Abdalla, Benhamouda, and Passel`egue in Crypto 2015, that can handle larger classes of PRF constructions. In addition to simplifying and unifying proofs for multilinear and aggregate PRFs, our new framework also yields new constructions which are secure under weaker assumptions, such as the decisional k-linear assumption.
Type de document :
Communication dans un congrès
Tetsu Iwata; Jung Hee Cheon. ASIACRYPT 2015, Nov 2015, Auckland, New Zealand. Springer, 9452, pp.103-120, Lecture Notes in Computer Science. 〈10.1007/978-3-662-48797-6_5〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01233740
Contributeur : Michel Abdalla <>
Soumis le : mercredi 25 novembre 2015 - 16:49:20
Dernière modification le : jeudi 11 janvier 2018 - 06:22:10

Identifiants

Collections

Citation

Michel Abdalla, Fabrice Benhamouda, Alain Passelègue. Multilinear and Aggregate Pseudorandom Functions: New Constructions and Improved Security. Tetsu Iwata; Jung Hee Cheon. ASIACRYPT 2015, Nov 2015, Auckland, New Zealand. Springer, 9452, pp.103-120, Lecture Notes in Computer Science. 〈10.1007/978-3-662-48797-6_5〉. 〈hal-01233740〉

Partager

Métriques

Consultations de la notice

170