Cryptology ePrint Archive: Report 2016/570

Design in Type-I, Run in Type-III: Fast and Scalable Bilinear-Type Conversion using Integer Programming

Masayuki Abe, Fumitaka Hoshino, Miyako Ohkubo

Abstract: Bilinear-type conversion is to convert cryptographic schemes designed over symmetric groups instantiated with imperilled curves into ones that run over more secure and efficient asymmetric groups. In this paper we introduce a novel type conversion method called {\em IPConv} using 0-1 Integer Programming. Instantiated with a widely available IP solver, it instantly converts existing intricate schemes, and can process large-scale schemes that involves more than a thousand variables and hundreds of pairings.

Such a quick and scalable method allows a new approach in designing cryptographic schemes over asymmetric bilinear groups. Namely, designers work without taking much care about asymmetry of computation but the converted scheme runs well in the asymmetric setting. We demonstrate the usefulness of conversion-aided design by presenting somewhat counter-intuitive examples where converted DLIN-based Groth-Sahai proofs are more compact than manually built SXDH-based proofs.

Category / Keywords: Conversion, Bilinear Groups, Integer Programming, Groth-Sahai Proofs, Zero-Knowledge

Original Publication (with minor differences): IACR-CRYPTO-2016

Date: received 3 Jun 2016, last revised 4 Jun 2016

Contact author: m ohkubo at nict go jp

Available format(s): PDF | BibTeX Citation

Note: Appendix is updated.

Version: 20160605:021213 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]