An Algebraic Framework for Pseudorandom Functions and Applications to Related-Key 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 : In this work, we provide a new algebraic framework for pseudorandom functions which encompasses many of the existing algebraic constructions, including the ones by Naor and Reingold (FOCS’97), by Lewko and Waters (CCS’09), and by Boneh, Montgomery, and Raghunathan (CCS’10), as well as the related-key-secure pseudorandom functions by Bellare and Cash (Crypto’10) and by Abdalla et al. (Crypto’14). To achieve this goal, we introduce two versions of our framework. The first, termed linearly independent polynomial security, states that the values (g^{P_1(a)}, ..., g^{P_q(a)}) are indistinguishable from a random tuple of the same size, when P_1, ..., P_q are linearly independent multivariate polynomials of the secret key vector a. The second, which is a natural generalization of the first framework, additionally deals with constructions based on the decision linear and matrix Diffie-Hellman assumptions. In addition to unifying and simplifying proofs for existing schemes, our framework also yields new results, such as related-key security with respect to arbitrary permutations of polynomials. Our constructions are in the standard model and do not require the existence of multilinear maps.
Type de document :
Communication dans un congrès
Rosario Gennaro; Matthew Robshaw. CRYPTO 2015, Aug 2015, Santa Barbara, United States. Springer, 9215, pp.388-409, 2015, Lecture Notes in Computer Science. 〈10.1007/978-3-662-47989-6_19〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01175786
Contributeur : Michel Abdalla <>
Soumis le : lundi 13 juillet 2015 - 00:27:22
Dernière modification le : mardi 17 avril 2018 - 11:26:55

Identifiants

Collections

Citation

Michel Abdalla, Fabrice Benhamouda, Alain Passelègue. An Algebraic Framework for Pseudorandom Functions and Applications to Related-Key Security. Rosario Gennaro; Matthew Robshaw. CRYPTO 2015, Aug 2015, Santa Barbara, United States. Springer, 9215, pp.388-409, 2015, Lecture Notes in Computer Science. 〈10.1007/978-3-662-47989-6_19〉. 〈hal-01175786〉

Partager

Métriques

Consultations de la notice

118