Paper 2015/290

Automating Fast and Secure Translations from Type-I to Type-III Pairing Schemes

Joseph A. Akinyele, Christina Garman, and Susan Hohenberger

Abstract

Pairing-based cryptography has exploded over the last decade, as this algebraic setting offers good functionality and efficiency. However, there is a huge security gap between how schemes are usually analyzed in the academic literature and how they are typically implemented. The issue at play is that there exist multiple types of pairings: Type-I called “symmetric” is typically how schemes are presented and proven secure in the literature, because it is simpler and the complexity assumptions can be weaker; however, Type-III called “asymmetric” is typically the most efficient choice for an implementation in terms of bandwidth and computation time. There are two main complexities when moving from one pairing type to another. First, the change in algebraic setting invalidates the original security proof. Second, there are usually multiple (possibly thousands) of ways to translate from a Type-I to a Type-III scheme, and the “best” translation may depend on the application. Our contribution is the design, development and evaluation of a new software tool, AutoGroup+, that automatically translates from Type-I to Type-III pairings. The output of AutoGroup+ is: (1) “secure” provided the input is “secure” and (2) optimal based on the user’s efficiency constraints (excluding software and run-time errors). Prior automation work for pairings was either not guaranteed to be secure or only partially automated and impractically slow. This work addresses the pairing security gap by realizing a fast and secure translation tool.