Computationally sound analysis of protocols using bilinear pairings

Issue title: 7th International Workshop on Issues in the Theory of Security (WITS'07)

Guest editors: Riccardo Focardi

Article type: Research Article

Authors: Kremer, Steve^a | Mazaré, Laurent^b

Affiliations: [a] LSV, ENS Cachan & CNRS & INRIA, Cachan, France. E-mail: kremer@lsv.ens-cachan.fr | [b] LexiFi SAS, Boulogne-Billancourt, France. E-mail: laurent.mazare@polytechnique.org

Abstract: In this paper, we introduce a symbolic model to analyse protocols that use a bilinear pairing between two cyclic groups. This model consists in an extension of the Abadi–Rogaway logic and we prove that the logic is still computationally sound: symbolic indistinguishability implies computational indistinguishability provided that the Bilinear Decisional Diffie–Hellman assumption holds and that the encryption scheme is IND-CPA secure. We illustrate our results on classical protocols using bilinear pairing like Joux tripartite Diffie–Hellman protocol or the TAK-2 and TAK-3 protocols. We also investigate the security of a newly designed variant of the Burmester–Desmedt protocol using bilinear pairings. More precisely, we show for each of these protocols that the generated key is indistinguishable from a random element.

Keywords: Security, formal methods, Dolev–Yao model, computational soundness, bilinear pairing

DOI: 10.3233/JCS-2009-0388

Journal: Journal of Computer Security, vol. 18, no. 6, pp. 999-1033, 2010