Towards Secure and Efficient Realization of Pairing-Based Signatures from Static Assumptions.

Abstract

Bilinear pairing defined over elliptic curve group was first used to design novel cryptosystem in 2000. Since then a large number of cryptosystems has been proposed in pairing-based cryptography (PBC). The main tool for all such cryptosystems is the pairing map which can be defined on either composite or prime-order groups. Security of a public key cryptosystem is typically proved under some computational hardness assumption. PBC has witnessed a plenty of parameterized/interactive assumptions. However, it is well-known that such assumptions have several limitations. In this thesis we explore the question of security and efficiency of pairing-based signature schemes based on static assumptions. We have investigated the efficacy of the following approaches towards this goal: (i). frameworks for converting cryptosystems from composite to prime-order bilinear pairing setting, (ii). DejaQ framework, for removing dependency on parameterized assumption and (iii). dual-form signature (DFS) technique, for removing dependency on parameterized/interactive assumption.

First, we focus on the conversion framework. In 2005, Boneh et al. introduced a novel homomorphic encryption scheme using composite-order pairing setting. From then there are plenty of cryptosystems constructed in the composite-order pairing setting. However, it is well known that a composite-order pairing is significantly slower than its prime-order counterpart. This motivated Freeman to propose his conversion framework that converts some cryptographic protocols to the prime-order pairing setting. He formally defined certain properties called projecting and canceling, which are used in the protocol construction and/or in the security argument. Since then several frameworks have been proposed for conversion purpose. We revisit all the projecting frameworks and establish that Freeman's framework is still optimal in the asymmetric pairing setting. We also present an alternative security proof for Seo-Cheon's projecting and canceling framework under the static symmetric external Diffie-Hellman (SXDH) assumption, instead of the original tailor-made assumption. Next, we formalize the full-decomposition notion in the existing projecting frameworks and show that this notion is sufficient instead of the so-called translating property. Then, we abstract an unbalanced projecting framework in the asymmetric pairing setting that allows the pairing source groups to have different orders. As application, we convert the following schemes to the prime-order asymmetric pairing setting: Shacham-Waters ring signature, Boyen-Waters group signature and Meiklejohn et al's round optimal blind signature. In their original construction, security of the above schemes requires both projecting and canceling properties in the composite-order symmetric pairing setting. We show that the framework for projecting and canceling is not necessary to instantiate these schemes.

Next, we focus on a set of parameterized assumptions called the BTA family. Such parameterized assumptions play a crucial role in the security of many novel pairing-based cryptosystems. However, they have some negative impact on efficiency at a concrete security level. A prominent approach to remove the dependency on parameterized assumption is the DejaQ framework of Chase et al. The DejaQ framework aims to establish that certain parameterized assumptions are implied by the subgroup hiding assumption in the composite-order pairing setting. Applying DejaQ framework to a family of assumptions is an important question, as it covers several parameterized assumptions which in turn cover more cryptographic protocols. However, the existing DejaQ framework could cover only Boyen's Uber assumption family. Recently Ghadafi and Groth introduced the bilinear target assumption (BTA) family, that covers more parameterized assumptions including the Uber assumption family. We show that the parameterized assumptions that belong to the BTA family are reducible from the subgroup hiding assumption. In the process, we first suitably extend a property called parameter-hiding and then adapt the DejaQ proof technique on the parameterized assumptions that belong to the BTA family.

Finally, we focus on the applicability of the dual-form signature (DFS) technique on some pairing-based signatures. The DejaQ framework does not address the question of how to remove the dependency on interactive assumption. The DFS technique can be used for this purpose and it is applied directly in the security argument of the protocol. We use the DFS technique to prove the security of Abe et al's structure-preserving signature, Boyen-Waters group signature and Pointcheval-Sanders rerandomizable signature (RRS) under some static assumptions. We also present an efficient construction of RRS scheme in the prime-order setting. Then, we use the proposed RRS scheme as a building block to construct a sequential aggregate signature (SeqAS) scheme with constant-size public key under the SXDH assumption. The performance of the proposed schemes is comparable to that of previous proposals based on some non-standard interactive assumptions.