Cryptology ePrint Archive: Report 2014/480

Towards a Unified Theory of Cryptographic Agents

Shashank Agrawal and Shweta Agrawal and Manoj Prabhakaran

Abstract: In recent years there has been a fantastic boom of increasingly sophisticated ''cryptographic objects'' -- identity-based encryption, fully-homomorphic encryption, functional encryption, and most recently, various forms of obfuscation. These objects often come in various flavors of security, and as these constructions have grown in number, complexity and inter-connectedness, the relationships between them have become increasingly confusing.

We provide a new framework of cryptographic agents that unifies various cryptographic objects and security definitions, similar to how the Universal Composition framework unifies various multi-party computation tasks like commitment, coin-tossing and zero-knowledge proofs.

Our contributions can be summarized as follows.

- Our main contribution is a new model of cryptographic computation, that unifies and extends cryptographic primitives such as Obfuscation, Functional Encryption, Fully Homomorphic Encryption, Witness encryption, Property Preserving Encryption and the like, all of which can be cleanly modeled as ''schemata'' in our framework. We provide a new indistinguishability preserving (IND-PRE) definition of security that interpolates indistinguishability and simulation style definitions, implying the former while (often) sidestepping the impossibilities of the latter.

- We present a notion of reduction from one schema to another and a powerful composition theorem with respect to IND-PRE security. This provides a modular means to build and analyze secure schemes for complicated schemata based on those for simpler schemata. Further, this provides a way to abstract out and study the relative complexity of different schemata. We show that obfuscation is a ''complete'' schema under this notion, under standard cryptographic assumptions.

- IND-PRE-security can be parameterized by the choice of the ''test'' family. For obfuscation, the strongest security definition (by considering all PPT tests) is unrealizable in general. But we identify a family of tests, called \Delta, such that all known impossibility results, for obfuscation as well as functional encryption, are by-passed. On the other hand, for each of the example primitives we consider in this paper -- obfuscation, functional encryption, fully-homomorphic encryption and property-preserving encryption -- \Delta-IND-PRE security for the corresponding schema implies the standard achievable security definitions in the literature.

- We provide a stricter notion of reduction that composes with respect to \Delta-IND-PRE security.

- Based on \Delta-IND-PRE-security we obtain a new definition for security of obfuscation, called adaptive differing-inputs obfuscation. We illustrate its power by using it for new constructions of functional encryption schemes, with and without function-hiding.

- Last but not the least, our framework can be used to model abstractions like the generic group model and the random oracle model, letting one translate a general class of constructions in these heuristic models to constructions based on standard model assumptions. We illustrate this by adapting a functional encryption scheme (for inner product predicate) that was shown secure in the generic group model to be secure based on a new standard model assumption we propose, called the generic bilinear group agents assumption.

Category / Keywords: foundations /

Date: received 17 Jun 2014, last revised 17 Jun 2014

Contact author: sagrawl2 at illinois edu; shweta a@gmail com; mmp@illinois edu

Available format(s): PDF | BibTeX Citation

Version: 20140621:163449 (All versions of this report)

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]