Round-optimal ID-based blind signature schemes without ROS assumption

This paper presents two Identity-Based Blind Signature (IBBS) schemes based on bilinear pairings. Both of them enjoy the following features. First, they achieve the optimal bound of round complexity for blind signatures, i.e., each signature can be blindly generated with one round (or two moves) of message exchanges between the signature requesting user and signer. Second, their security is proved without the ROS assumption, which assumes that it is infeasible to find an overdetermined, solvable system of linear equations modulo q with random inhomogenities. Due to this reason, the order of underlying group does not need to be very large any more, as compared to the previous work. Third, the key extraction algorithm used is the most popular one in ID-based cryptography. In fact, the proposed two constructions are first IBBS schemes enjoying all the above advantages. Different from other IBBS schemes, these two IBBS schemes are constructed from scratch in the sense that new ID-based signature schemes are customized and new assumptions (e.g., two versions of one-more bilinear Diffie- Hellman inversion assumption) are formalized.We also show that the new ID-based schemes and new assumptions may have other interesting applications.