1
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • $\begingroup$ But what computations this $F$ is supposed to do? $\endgroup$
    – Hilder Vitor Lima Pereira
    Jan 14, 2017 at 13:05

1 Answer 1

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$
4
  • $\begingroup$ "Sure. ​ Just let signing key and verification key be part of the homomorphic information. " --> How exactly it would work? $\endgroup$
    – Hilder Vitor Lima Pereira
    Jan 14, 2017 at 12:47
  • $\begingroup$ Apply the inner homomorphing information, then use the signing key to generate the signature. ​ ​ $\endgroup$
    – user991
    Jan 15, 2017 at 18:36
  • $\begingroup$ But the question says that "no one knows the private key, and therefore no one can generate the signature without running F", so, how could the cloud generate the signature without knowing the signing key? $\endgroup$
    – Hilder Vitor Lima Pereira
    Jan 16, 2017 at 20:42
  • $\begingroup$ See my answer: ​ "Change the ... use,". ​ ​ ​ ​ $\endgroup$
    – user991
    Jan 16, 2017 at 22:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.