Research On Provably Secure Digital Signatures

In this dissertation, motivated by a few focuses in applied cryptography, we design and analyze some digital signature schemes with additional properties. Our research follows the provable security approach. The main contributions are as follows.1. In chapter 2, a new ID-based blind signature scheme is constructed from bilinear pairings with following properties. (1) Provable security. It is the first provably secure ID-based blind signature scheme against generic parallel attack. (2) Computational assumption. It is the first ID-based blind signature scheme whose security does not depend on the ROS assumption (ROS-problem: find an overdetermined solvable system of linear equations modulo q with random inho-mogenities (right sides)). (3) Computational efficiency. Its security parameter is required to have the length which can ensure the intractability of the 1m-BDHI problem (one-more bilinear Difne-Hellman inversion). Maybe it is enough for the security parameter to be 160 bits long. If so, the proposed ID-based blind signature scheme will be the first one which can be pratically implemented. Here note that in previous analogues, the security parameter for ensuring the intractability of the ROS problem need to be at least 1600 bits. (4) Communication efficiency. It is the first ID-based blind signature scheme whose round complexity is optimal. Namely, each interactive signature generation requires the requesting user and the signer to transmit only one message each. (5) Underlying construction. It is con-struted based on no exiting ID-based signature scheme. Indeed, the underlying ID-based signature scheme is customized according to the detailed requirements. (6) Additionally, to prove its security, we propose a new plausible computational assumption, namely, one-more bilinear Diffie-Hellman inversion assumption (1m-BDHI, for short).2. In chapter 3, we propose a new ID-based threshold signature scheme from bilinear pairings, which is provably secure in the random oracle model under the bilinear Diffie-Hellman assumption. The proposed scheme has the following properties. (1) The private key associated with an identity rather than the master key of PKG is shared. (2) The private key of an identity is indirectly distributed by sharing a number x_id ∈ (?)_q, which is much efficient than directly sharing the element in the bilinear group. (3) The round-complexity of the threshold signing protocol is optimal. Namely, during the signing procedure, each party broadcasts only one...