Functional signatures: new definition and constructions

Functional signatures (FS) enable a master authority to delegate its signing privilege to an assistant. Concretely, the master authority uses its secret key skF to issue a signing key skf for a designated function f∈ ℱFS and sends both f and skf to the assistant ℰ, which is then able to compute a signature σf with respect to pkF for a message y in the range of f. In this paper, we modify the syntax of FS slightly to support the application scenario where a certificate of authorization is necessary. Compared with the original FS, our definition requires that ℱFS is an injective function family and for any f0, f1∈ ℱFS there does not exist an intersection between range(f0) and range(f1). Accordingly, we redefine the security of FS and introduce two additional security notions, called unlinkability and accountability. Signatures σf in our definition do not expose the intention of the master authority. We propose two constructions of FS. The first one is a generic construction based on signatures with perfectly re-randomizable keys, non-interactive zero-knowledge proof (NIZK) and traditional digital signatures, and the other is based on RSA (Rivest-Shamir-Adleman) signatures with full domain hash and NIZK. We prove that both schemes are secure under the given security models.