A Generic Construction of Efficient Oblivious Signature Protocols

In an oblivious signature, a receiver can obtain a signature from the signer for a message in the specified message set. It satisfies unforgeability and blind property similar to blind signature, and in-addition satisfies constrained-message property, i.e. the signer can only obtain valid signatures from the specified message set. Most existing oblivious signature protocols have communication complexity that's linearly proportional to the message set size, which makes the applications less scalable. Another common issue is they usually do not satisfy unlinkable, i.e. the signer cannot map a signature back to a specific run/receiver. In this work, we propose a generic construction of oblivious signature protocol from a set-membership NIZK and a blind signature protocol. Our construction has communication complexity that does not grow linearly with respect to the message set, and preserves unlinkability from the underlying blind signature protocol.