Structure-Preserving Pairing-Based Cryptography

Lead Research Organisation: University College London
Department Name: Computer Science

Abstract

Pairing-based cryptography has boomed over the last decade since it provides secure solutions to problems where traditional cryptographic methods do not suffice or are less efficient.

Boneh and Franklin in a seminal paper showed how to construct identity-based encryption using pairing-based techniques. This makes it possible to encrypt a message under somebody's identity, for instance their e-mail address, eliminating the need to obtain or manage a public key for each user. In large organizations this simplifies key management and identity-based key-management solutions are now used in several Fortune 500 companies.

Another example arises in the context of pervasive computing systems such as intelligent cars that communicate with each other. In an intelligent car processing hundreds of messages from surrounding vehicles in every 300ms interval it is essential to minimize communication and optimise efficiency. Pairing-based digital signatures can be useful in this scenario because they are smaller than traditional digital signatures and at the same time allow for fast verification of a large batch of signatures at once.

Other proposed applications of pairing-based cryptography include e-cash, searchable encrypted data, broadcast encryption and traitor tracing, delegatable anonymous credentials, and verifying the presence of data stored in a cloud computing facility.

Security is essential in all of these tasks. As our society has become increasingly digitized and networked so have criminals, hackers, industrial spies, enemy states, etc. It is therefore necessary to design secure cryptographic schemes that can be used to build a digital society that is resilient in the presence of malicious adversaries.

Designing cryptographic protocols for complex tasks requires significant effort and expertise since even a small mistake may render the entire system insecure. It is therefore natural to build cryptographic protocols in a modular fashion. This is what structure-preserving pairing-based cryptography allows. The term structure-preservation refers to pairing-based schemes that preserve their underlying mathematical structure. This structure-preserving property makes it easy to compose them with other pairing-based schemes and enables modular design.

We will design structure-preserving pairing-based cryptographic schemes, study the efficiency limits of structure-preserving pairing-based cryptographic schemes and evaluate the security of pairing-based cryptographic schemes.

By designing structure-preserving pairing-based schemes we develop new building blocks for the digital society. Moreover, the techniques we develop for the design of structure-preserving schemes may make it possible to build pairing-based schemes for significantly more complex tasks than is currently possible.

Very recent work has shown that there are limits to how efficient structure-preserving digital signatures can be. It is usually very difficult to find efficiency limitations, researchers just tend to get stuck at some point without knowing why, but because of their unique nature structure-preserving protocols lend themselves to exact efficiency analysis. By finding efficiency limits for structure-preserving pairing-based schemes, we can get an accurate picture of the exact efficiency for a variety of cryptographic tasks.

Security is essential when designing cryptographic protocols. The security of cryptographic schemes relies on hardness assumptions; for instance that it is computationally infeasible to factor large integers in a short amount of time. Unfortunately, pairing-based cryptographic schemes have been based on a large variety of assumptions making it hard to assess how secure they are. We will map out the landscape of assumptions that are used in pairing-based cryptography and make it easier to assess the security of pairing-based cryptographic schemes.

Planned Impact

Our aim is to enable businesses, organisations and citizens of the future digital society to carry out complex tasks and operations with each other in a secure manner. Our research will make the digital society more efficient and able to handle more complex tasks. It will also increase the security of the digital society by reducing the risk of attacks by criminals, hackers, industrial spies, enemy states, etc.

The path we take towards this goal goes through pairing-based cryptography, which is a technology that can be used to construct many of the secure protocols that will underpin the digital society. Our research will make it possible to compare the security of different pairing-based cryptographic protocols and to choose the most secure protocols. Moreover, our contributions in the area of structure-preserving pairing-based cryptography will make it possible to build pairing-based protocols capable of securely carrying out complex transactions.

The direct beneficiaries of our research are cryptographers designing pairing-based protocols and the users of these protocols. Our contributions are:
1) We will broaden the scope of structure-preserving pairing-based cryptography, which will make designing protocols for complex tasks easier and less error-prone.
2) We will find concrete efficiency limitations for structure-preserving pairing-based cryptography, which will help cryptographers determine which protocols to implement and aim for optimal efficiency.
3) We will make it possible to compare the security of pairing-based protocols. This will help cryptographers building complex protocols to choose protocol components in a way that relies on a small set of hardness assumptions and thereby increase the security of the protocols. It will also help users to pick the most secure protocols.
 
Description Digital signature schemes are used directly in commerce and as a tool when building cryptographic protocols. We have proposed a number of digital signature schemes that are easy to combine with other cryptographic tools, have minimal size, and can handle large messages at reasonable cost.
Zero-knowledge proofs allow somebody to prove they are acting honestly without revealing confidential data going into the protocol. We have developed very efficient and compact non-interactive zero-knowledge proofs.
In pairing-based cryptography many protocols have been designed in the so-called Type I setting, but actually another setting, Type III, is the most efficient. We have developed software to automatically convert protocols in the Type I setting to the Type III setting, such that this body of work gets the efficiency benefits from the latter setting.
Cryptography is based on computational assumptions about what an attacker is unable to compute. We have developed a classification of an important class of assumptions: non-interactive computational assumptions in cyclic groups.
Exploitation Route Our work has been taken up by other cryptographers. Our structure-preserving signatures are used in many proposals for cryptographic protocols (e-cash, group signatures, etc.). Our work on zero-knowledge is highly cited and used in many cryptographic schemes. Cryptographers may use our classification to decide which assumptions to use in the cryptographic schemes, and cryptanalysts may use it to decide which assumptions to study.
Sectors Digital/Communication/Information Technologies (including Software)

 
Description Structure-preserving cryptography 
Organisation NICT National Institute of Information and Communications Technology
Country Japan 
Sector Public 
PI Contribution The collaboration with M. Abe from NTT, Japan and M. Ohkubo from NICT, Japan has lead to a number of articles on structure-preserving cryptography.
Collaborator Contribution The collaboration with M. Abe from NTT, Japan and M. Ohkubo from NICT, Japan has lead to a number of articles on structure-preserving cryptography.
Impact See publications
Start Year 2010
 
Description Structure-preserving cryptography 
Organisation NTT Basic Research Laboratories
Country Japan 
Sector Public 
PI Contribution The collaboration with M. Abe from NTT, Japan and M. Ohkubo from NICT, Japan has lead to a number of articles on structure-preserving cryptography.
Collaborator Contribution The collaboration with M. Abe from NTT, Japan and M. Ohkubo from NICT, Japan has lead to a number of articles on structure-preserving cryptography.
Impact See publications
Start Year 2010