Functional signatures use some master key to create a functional signature key. The functional key can be used to sign messages, but only if the message is accepted by some predicate function. For example if Bob is Alice's assistant, she can let him sign documents under her credentials, but only if the document contains the string "Signed by Assistant." Bob can then send to Veronica, who can be sure that Alice (functionally) approved this document.

The paper establishing functional signatures is found here. In their construction (found on pages 18-19) they rely on an underlying public key signature scheme, and a non-interactive zero-knowledge proof (ZKP). Specifically the verification step is running ZKP verification with a) function output, b) the ZKP proof, and c) the common reference string (CRS).

However consider if Veronica is not capable of running the ZKP verification routine. Veronica can only verify in the underlying signature scheme (let's assume ECDSA). Maybe she's stuck in her ways and refuses to install ZKP software. Or she's a resource constrained embedded device. Or she's a popular blockchain protocol that has to maintain backwards compatibility.

Either way we're stuck having to verify signature with a client who can only run ECDSA. We are free to give Veronica new function-specific signing keys at the outset. I.e. she doesn't have to verify with Alice's master signing keys. If it helps, we can even give her some not too-large N of keys and verify with an M-of-N signature. We're also flexible with whatever ZKP protocol is used: ZK-SNARK, NIZKAoK, Pinnochio, etc. The signer also has nearly unbound computational resources.

I have a couple of half-baked ideas here. One is to use signature aggregation. Maybe there's a way to covert aggregate the CRS, function circuit, and master signing key into a single functional signature. Another possible approach might be to use an elliptic curve based ZKP protocol, like Pinnochio, and pair that to the ECDSA curve. Finally maybe a constrained private pseudorandom function (PRF). The PRF itself could just puncture when the function matches and output the signed ECDSA message. The circuit would have to contain the master signing key, but if the circuit's garbled its inaccessible (?).

Is there anyway for the original functional signature scheme to accommodate these constraints? Are any of my above approaches anywhere in the vicinity of what's needed? Or am I just barking up the wrong tree here.

  • $\begingroup$ Another possibility is using functional encryption which under recent protocols is Turing Complete. The decode function (Dec) wraps the predicate function (P). Dec(m) = Signed(m) if P(m) = 1. Otherwise Error. $\endgroup$ – user79126 Dec 5 '17 at 21:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.