Embedding a secret private key in a homomorphic encryption system Is there a way to create a homomorphic encryption function F such that given an input it would produce an output and also cryptographically sign the input and output? More formally, an F such that: F(x, S) = y | sig(x | y), where:


x is the input
S is an optional publicly known "helper" state
y is an output of some computation
| is concatenation
sig(x | y) is a signature of x and y, with a secret private key
Anyone can verify the signature according to the public key, but no one knows the private key, and therefore no one can generate the signature without running F. Hence the signature proves the correctness of y for the given x.


Optionally, the state S can be created in an initialization phase using a secure multi party computation (MPC), so the parties could figure out the private key but only if they all collude.

The idea is that given some x, someone could run F(x) and then give { x, y, sig(x | y) } to verifiers, proving the computation was done correctly without needing the verifiers to run the computation themselves.
"Is there a way to create a homomorphic encryption function F such that given an input

it would produce an output and also cryptographically sign the input and output?"

Sure. ​ Just let signing key and verification key be part of the homomorphing information.

"Anyone can verify the signature according to the public key,

but no one knows the private key"

Change the signature scheme so that the signing key includes a random part,

which neither the signing algorithm nor the verification algorithm use,

and leave that part out of the homomorphing information.

", and therefore"

The part just after that quote does not follow from what's before that quote.

"no one can generate the signature without running F."

gets into parallelism-resistance without the

"generating a puzzle should take less time than solving it." condition,

and/or quantitative things that mainly apply to password-hashing.



Your stated idea would have complexity-theoretic consequences;

namely, showing that non-uniform MATIME is unexpectedly powerful.

It seems like you'd be interested in publicly-verifiable SNARGs.

(Note that they are arguments, not proofs.)