Biblio

List
Filter

Found 2 results

Filters: Author is Paliath Narendran, University at Albany-SUNY [Clear All Filters]

2015-11-18

Fan Yang, University of Illinois at Urbana-Champaign, Santiago Escobar, Universidad Politécnica de Valencia, Spain, Catherine Meadows, Naval Research Laboratory, Jose Meseguer, University of Illinois at Urbana-Champaign, Paliath Narendran, University at Albany-SUNY. 2014. Theories for Homomorphic Encryption, Unification and the Finite Variant Property. 16th International Symposium on Principles and Practice of Declarative Programming (PPDP 2014).

Recent advances in the automated analysis of cryptographic protocols have aroused new interest in the practical application of unification modulo theories, especially theories that describe the algebraic properties of cryptosystems. However, this application requires unification algorithms that can be easily implemented and easily extended to combinations of different theories of interest. In practice this has meant that most tools use a version of a technique known as variant unification. This requires, among other things, that the theory be decomposable into a set of axioms B and a set of rewrite rules R such that R has the finite variant property with respect to B. Most theories that arise in cryptographic protocols have decompositions suitable for variant unification, but there is one major exception: the theory that describes encryption that is homomorphic over an Abelian group.

In this paper we address this problem by studying various approximations of homomorphic encryption over an Abelian group. We construct a hierarchy of increasingly richer theories, taking advantage of new results that allow us to automatically verify that their decompositions have the finite variant property. This new verification procedure also allows us to construct a rough metric of the complexity of a theory with respect to variant unification, or variant complexity. We specify different versions of protocols using the different theories, and analyze them in the Maude-NPA cryptographic protocol analysis tool to assess their behavior. This gives us greater understanding of how the theories behave in actual application, and suggests possible techniques for improving performance.

Serdar Erbatur, Università degli Studi di Verona, Santiago Escobar, Universidad Politécnica de Valencia, Spain, Deepak Kapur, University of New Mexico, Zhiqiang Liu, Clarkson University, Christopher A. Lynch, Clarkson University, Catherine Meadows, Naval Research Laboratory, Jose Meseguer, University of Illinois at Urbana-Champaign, Paliath Narendran, University at Albany-SUNY, Sonia Santiago, Universidad Politécnica de Valencia, Spain, Ralf Sasse, Institute of Information Security, ETH. 2013. Asymmetric Unification: A New Unification Paradigm for Cryptographic Protocol Analysis. 24th International Conference on Automated Deduction (CADE 2013) .

We present a new paradigm for uniﬁcation arising out of a technique commonly used in cryptographic protocol analysis tools that employ uniﬁcation modulo equational theories. This paradigm relies on: (i) a decomposition of an equational theory into (R, E) where R is conﬂuent, terminating, and coherent modulo E, and (ii) on reducing uniﬁ- cation problems to a set of problems s =^?t under the constraint that t remains R/E-irreducible. We call this method asymmetric unification . We ﬁrst present a general-purpose generic asymmetric uniﬁcation algorithm.and then outline an approach for converting special-purpose conventional uniﬁcation algorithms to asymmetric ones, demonstrating it for exclusive-or with uninterpreted function symbols. We demonstrate how asymmetric uniﬁcation can improve performanceby running the algorithm on a set of benchmark problems. We also give results on the complexity and decidability of asymmetric uniﬁcation.