Two Applications of Multilinear Maps: Group Key Exchange and Witness Encryption

Constructing multilinear maps has been long-standing open problem, before recently the rst construction based on ideal lattices has been proposed by Garg et al. After this break-through, various new cryptographic systems have been pro-posed. They introduce the concept of level into the encod-ings, and the system has a function that extracts a deter-ministic value at only a specic level, and the encodings are unable to downgrade to the lower levels. These properties are useful for cryptography. We study how this graded en-coding system be applied to cryptosystems, and we propose two protocols, group key exchange and witness encryption. In our group key exchange, we achieve the communication size and the computation costs per party are both O(1) with respect to the number of parties by piling the encodings of passed parties in one encoding. A witness encryption is a new type cryptosystem using NP-complete problem. The rst construction is based on EXACT-COVER problem. We construct it based on another NP-complete Hamilton Cycle problem, and prove its security under the Generic Cycli