inria-00426798, version 1
Unification Modulo Homomorphic Encryption
Siva Anantharaman 1Hai Lin aChristopher Lynch bPaliath Narendran
2Michael Rusinowitch 3
7th International Symposium on Frontiers of Combining Systems - FroCoS 2009 5749 (2009) 100-116
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 NEXPTIME.
- a – University of Clarckson
- b – Clarckson University
- 1 : Laboratoire d'Informatique Fondamentale d'Orléans (LIFO)
- Université d'Orléans : EA4022 – Ecole Nationale Supérieure d'Ingénieurs de Bourges
- 2 : University at Albany
- State university of New York
- 3 : CASSIS (INRIA Lorraine - LORIA / LIFC)
- INRIA – CNRS : FRE2661 – Université de Franche-Comté – Université Henri Poincaré - Nancy I – Université Nancy II – Institut National Polytechnique de Lorraine (INPL)
- Domaine : Informatique/Logique en informatique
- Commentaire : The original publication is available at www.springerlink.com
- inria-00426798, version 1
- http://hal.inria.fr/inria-00426798
- oai:hal.inria.fr:inria-00426798
- Contributeur : Michael Rusinowitch
- Soumis le : Mercredi 28 Octobre 2009, 08:43:42
- Dernière modification le : Lundi 9 Novembre 2009, 16:15:27
Documents associés
Exporter