TY - GEN
T1 - Unification modulo homomorphic encryption
AU - Anantharaman, Siva
AU - Lin, Hai
AU - Lynch, Christopher
AU - Narendran, Paliath
AU - Rusinowitch, Michaël
PY - 2009
Y1 - 2009
N2 - 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.
AB - 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.
UR - https://www.scopus.com/pages/publications/76649093577
U2 - 10.1007/978-3-642-04222-5_6
DO - 10.1007/978-3-642-04222-5_6
M3 - Conference contribution
SN - 364204221X
SN - 9783642042218
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 100
EP - 116
BT - Frontiers of Combining Systems - 7th International Symposium, FroCoS 2009, Proceedings
T2 - 7th International Symposium on Frontiers of Combining Systems, FroCoS 2009
Y2 - 16 September 2009 through 18 September 2009
ER -