Paper 2006/102

Efficient Blind and Partially Blind Signatures Without Random Oracles

Tatsuaki Okamoto

Abstract

This paper proposes a new efficient signature scheme from bilinear maps that is secure in the standard model (i.e., without the random oracle model). Our signature scheme is more effective in many applications (e.g., blind signatures, group signatures, anonymous credentials etc.) than the existing secure signature schemes in the standard model. As typical applications of our signature scheme, this paper presents efficient blind signatures and partially blind signatures that are secure in the standard model. Here, partially blind signatures are a generalization of blind signatures (i.e., blind signatures are a special case of partially blind signatures) and have many applications including electronic cash and voting. Our blind signature scheme is much more efficient than the existing secure blind signature schemes in the standard model such as the Camenisch-Koprowski-Warinsch and Juels-Luby-Ostrovsky schemes, and is also almost as efficient as the most efficient blind signature schemes whose security has been analyzed heuristically or in the random oracle model. Our partially blind signature scheme is the first one that is secure in the standard model and it is very efficient (as efficient as our blind signatures). The security proof of our blind and partially blind signature schemes requires the 2SDH assumption, a variant of the SDH assumption introduced by Boneh and Boyen, and the 2SDH-IND assumption. This paper also presents an efficient way to convert our (partially) blind signature scheme in the standard model to a scheme secure for a concurrent run of users in the common reference string (CRS) model. Finally, we present a blind signature scheme based on the Waters signature scheme.

Note: I corrected some errors in the previous manuscript.