Practical round‐optimal blind signatures without random oracles or non‐interactive zero‐knowledge proofs

Abstract

ABSTRACT Blind signatures are generated by means of a protocol between the signer and a user such that the signer can neither see the message being signed and nor learn any information on the signature being produced. Time/space complexity and security model (random oracle model versus standard model; sequential, parallel, or concurrent security) are commonly used to evaluate blind signature schemes. The paper presents the first round‐optimal blind signatures without random oracles or non‐interactive zero‐knowledge proofs. The proposed blind signature scheme achieves concurrent security and perfect blindness while preserving the efficiency of computation and communication. A novel class of computational problems, called one‐more‐output (OMO) problems, is introduced to prove the unforgeability of the scheme. The paper states the corresponding lower bound of the OMO problem in the generic group model. Such a computational problem might be of independent interests in designing other cryptographic protocol and primitives. Copyright © 2011 John Wiley & Sons, Ltd.