In this paper, we provide impossibility results on projecting bilinear pairings in a prime-order group setting. More precisely, we specify the lower bounds of
1. the image size of a projecting asymmetric bilinear pairing
2. the image size of a projecting symmetric bilinear pairing
3. the computational cost for a projecting asymmetric bilinear pairing
4. the computational cost for a projecting symmetric bilinear pairing
in a prime-order group setting naturally induced from the $k$-linear assumption, where the computational cost means the number of generic operations.
Our lower bounds regarding a projecting asymmetric bilinear pairing are tight, i.e., it is impossible to construct a more efficient projecting asymmetric bilinear pairing than the constructions of Groth-Sahai and Freeman. However, our lower bounds regarding a projecting symmetric bilinear pairing differ from Groth and Sahai's results regarding a symmetric bilinear pairing; We fill these gaps by constructing projecting symmetric bilinear pairings.
In addition, on the basis of the proposed symmetric bilinear pairings, we construct more efficient instantiations of cryptosystems that essentially use the projecting symmetric bilinear pairings in a modular fashion. Example applications include new instantiations of the Boneh-Goh-Nissim cryptosystem, the Groth-Sahai non-interactive proof system, and Seo-Cheon round optimal blind signatures proven secure under the DLIN assumption. These new instantiations are more efficient than the previous ones, which are also provably secure under the DLIN assumption. These applications are of independent interest.Category / Keywords: Bilinear Groups, Projecting, (im)possibility, Zero-Knowledge Proofs Publication Info: This is a full version of the extended abstract published in the proceeding of ASIACRYPT 2012 Date: received 1 Apr 2013, last revised 2 Apr 2013 Contact author: jhsbhs at gmail com Available format(s): PDF | BibTeX Citation Version: 20130403:022816 (All versions of this report) Short URL: ia.cr/2013/186 Discussion forum: Show discussion | Start new discussion