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?"

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.)