Leakage resilient cryptographic scheme and GPU-based pairing operation

Abstract

Cryptographic schemes are designed to protect the privacy of the users. Numerous schemes have been proposed for different purposes. One important type of schemes is called the secret sharing scheme. In a secret sharing scheme, a secret value can be shard among authorized parties. Another important type of schemes is identity based encryption and its variant: certificateless encryption. Traditionally, both of them assume the absolute privacy of secret shares or secret keys. However, this assumption may not hold in the real world. Side-channel attack, such as time analysis and memory attack will enable the attackers to get partial information about them. Therefore, we propose the leakage resilient cryptographic schemes to guarantee the privacy under various key-exposure attack. Generally speaking, there are three leakage models: the bounded leakage model, continual leakage model and auxiliary input model. We will focus on the first two models in this thesis.

This thesis addresses two leakage resilient cryptographic schemes. The first one is called Continual Leakage-Resilient Dynamic Secret Sharing. In this scheme, the attacker can continuously leak on the private value owned by the user with the constrain that the length of the leaked information should be less than ℓ bits between updates. The dealer is able to dynamically choose a set of n users and a threshold of t users (which is called authorized set) to reconstruct secret with the same broadcast message. The user can also dynamic join and leave the scheme. The privacy of the secret value can be guaranteed even up to t-1 users are corrupted and the information of all other users are leaked.

The second one is called Leakage-Resilient Certificateless Public-Key Encryption. Certificateless encryption is proposed to solve the key escrow problem in PKG. Instead of relying on the PKG to generate the full secret key in the traditional model, we generate partial secret key on PKG. We then combine it with our selected secret value to generate the final secret key. This will solve the key escrow problem since the PKG has no knowledge about the secret value chosen. Our scheme is the first leakage-resilient version of certificateless encryption. In our security model, both the master key held by the PKG and the secret key (including the secret value) held by the user can be leaked by the attacker. We first construct the scheme in bounded leakage model and then extend it to continual leakage model.

Finally, all of these schemes require lots of composite order bilinear pairing operations. We will describe how to improve the efficient of it on graphics hardware in chapter 4. We run the parings in parallel on GPU to accelerate them. The implement scheme and efficient are presented in this thesis.