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

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.

Note: Appendix is updated.

Metadata
Available format(s)
PDF
Publication info
A minor revision of an IACR publication in CRYPTO 2016
Keywords
ConversionBilinear GroupsInteger ProgrammingGroth-Sahai ProofsZero-Knowledge
Contact author(s)
m ohkubo @ nict go jp
History
2016-06-05: revised
2016-06-03: received
See all versions
Short URL
https://ia.cr/2016/570
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/570,
      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{https://eprint.iacr.org/2016/570}},
      url = {https://eprint.iacr.org/2016/570}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.