Unification modulo Homomorphic Encryption - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Journal of Automated Reasoning Année : 2012

Unification modulo Homomorphic Encryption

Hai Lin
  • Fonction : Auteur
  • PersonId : 866283
Christopher Lynch
  • Fonction : Auteur
  • PersonId : 866284
Paliath Narendran
  • Fonction : Auteur
  • PersonId : 833673

Résumé

Encryption 'distributing over pairs' is a technique employed in several cryptographic protocols. We show that unification is decidable for an equational theory HE specifying such an encryption. The method consists in transforming any given problem in such a way, that the resulting problem can be solved by combining a graph-based reasoning on its equations involving the homomorphisms, with a syntactic reasoning on its pairings. We show HE-unification to be NP-hard and in EXPTIME. We also indicate, briefly, how to extend HE-unification to Cap unification modulo HE, that can be used as a tool for modeling and analyzing cryptographic protocols where encryption follows the ECB mode, i.e., is done block-wise on messages.

Dates et versions

inria-00618336 , version 1 (01-09-2011)

Identifiants

Citer

Siva Anantharaman, Hai Lin, Christopher Lynch, Paliath Narendran, Michael Rusinowitch. Unification modulo Homomorphic Encryption. Journal of Automated Reasoning, 2012, 48 (2), pp.135-158. ⟨10.1007/s10817-010-9205-y⟩. ⟨inria-00618336⟩
226 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More