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

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.