Paper 2016/570

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

Masayuki Abe, Fumitaka Hoshino, and Miyako Ohkubo


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.

Note: Appendix is updated.

Available format(s)
Publication info
A minor revision of an IACR publication in CRYPTO 2016
ConversionBilinear GroupsInteger ProgrammingGroth-Sahai ProofsZero-Knowledge
Contact author(s)
m ohkubo @ nict go jp
2016-06-05: revised
2016-06-03: received
See all versions
Short URL
Creative Commons Attribution


      author = {Masayuki Abe and Fumitaka Hoshino and Miyako Ohkubo},
      title = {Design in Type-I, Run in Type-{III}: Fast and Scalable Bilinear-Type Conversion using Integer Programming},
      howpublished = {Cryptology ePrint Archive, Paper 2016/570},
      year = {2016},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.