
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Fast and Scalable BilinearType Conversion Method for Large Scale Crypto Schemes
Masayuki ABE Fumitaka HOSHINO Miyako OHKUBO
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E102A
No.1
pp.251269 Publication Date: 2019/01/01 Online ISSN: 17451337
DOI: 10.1587/transfun.E102.A.251 Type of Manuscript: PAPER Category: Cryptography and Information Security Keyword: pairingbased cryptography, bilineartype conversion, integer programming, cryptographic scheme design, GrothSahai proofs,
Full Text: FreePDF(4.6MB)
Summary:
Bilineartype conversion is to translate a cryptographic scheme designed over symmetric bilinear groups into one that works over asymmetric bilinear groups with small overhead regarding the size of objects concerned in the target scheme. In this paper, we address scalability for converting complex cryptographic schemes. Our contribution is threefold. Investigating complexity of bilineartype conversion. We show that there exists no polynomialtime algorithm for worstcase inputs under standard complexity assumption. It means that bilineartype conversion in general is an inherently difficult problem. Presenting a new scalable conversion method. Nevertheless, we show that largescale conversion is indeed possible in practice when the target schemes are built from smaller building blocks with some structure. We present a novel conversion method, called IPConv, that uses 01 Integer Programming instantiated with a widely available IP solver. It instantly converts schemes containing more than a thousand of variables and hundreds of pairings. Application to computeraided design. Our conversion method is also useful in modular design of middle to large scale cryptographic applications; first construct over simpler symmetric bilinear groups and run over efficient asymmetric groups. Thus one can avoid complication of manually allocating variables over asymmetric bilinear groups. We demonstrate its usefulness by somewhat counterintuitive examples where converted DLINbased GrothSahai proofs are more compact than manually built SXDHbased proofs. Though the early purpose of bilineartype conversion is to save existing schemes from attacks against symmetric bilinear groups, our new scalable conversion method will find more applications beyond the original goal. Indeed, the above computeraided design can be seen as a step toward automated modular design of cryptographic schemes.

