Sign a plaintext accepted by a secure function without revealing private key

Question

Imagine the following scenario: Alice is a well-respected chef. She is famous for reviewing recipes. Anyone can send her a recipe. If she likes it she'll add her famous line of approval to the end: "This is delicious, y'all". Cryptographically signed with her public key of course. Alice-approved recipes are universally delicious.

But let's be honest, cooking isn't that hard. Tasty food is pretty much just making adding a ton of salt, sugar, oil and MSG. Alice's seal of approval can be replicated by a computer program that makes sure the above are present in sufficient concentrations. Alice would like to kick-back and let the program do the hard work.

So, she hires an untrustworthy middleman, Bob. She hands Bob the computer program. Bob pretends to be Alice. Someone sends her a recipe, which gets forwarded to Bob. Bob runs the computer program, if the recipe passes, he adds her trademark seal and cryptographically signs it with her keys. However Alice only wants Bob to be able to sign recipes that pass. She wants to avoid a scenario where she has to trust Bob with access to her private keys.

Is there anyway to practically accomplish the above? As I understand, homographic encryption, garbled circuits and blind Turing machines can evaluate arbitrary computations. But current implementations are extremely inefficient for complex programs. The logic of the program itself doesn't need to be encrypted. The only thing Alice cares about is protecting her private keys, and restricting Bob to signing inputs that pass the function. Any ideas about whether this is feasible and what the best approach might be?

Answer 1

The cryptographic primitive you're looking for is known as functional signature: in a functional signature scheme, there is a standard signature and verification key pair, as well as an algorithm to derive functional signature and verification keys, for any function $f$. The signature scheme then allows to sign any message $m$ in the range of $f$. The notion was introduced in this paper (see also the papers that cite it on Google scholar, for more recent constructions).

To get a solution to your problem out of this, let me call $P$ the program that checks whether $m$ is a good recipe. Define $f$ as follow: $f(m)$ returns $m$ if $P(m) = 1$, and the symbol $\bot$ otherwise. Now, if Bob (who knows the signing key for this function $f$) can sign a recipe $m \neq \bot$, this means that $m$ is in the range of $f$, hence that $P(m)=1$.

From your scenario, I suppose that you additionally have a function-privacy requirement: $f$ should not be publicly known (otherwise anyone could always check whether a recipe is nice, without the help of Alice), hence the functional signature key should hide $f$. This is known as function-private functional signatures, and is also defined and constructed in the paper I mentioned above. Such a scheme can be constructed for any polytime-computable function, assuming one-way functions and succinct non-interactive zero-knowledge arguments. The latter is a strong assumption, but we now have relatively efficient constructions of such arguments for functions of reasonable size (although probably not standardised implementations) - for example, this one was published a few days ago on ePrint, and seems quite efficient.

Note that none of this would be "incredibly efficient", but still fairly feasible.