In the definition of functional encryption ($FE$):

$FE.Setup(1^k)$ takes as input the security parameter $1^k$ and outputs a master public key $fmpk$ and a master secret key $fmsk$.

$FE.KeyGen(fmsk, f)$ takes as input the master secret key $fmsk$ and a function $f$ and outputs a key $sk_f$.

$FE.Enc(fmpk,x)$ takes as input the master public key $fmpk$ and an input $x$ and outputs a ciphertext $c$.

$FE.Dec(sk_f,c)$ takes as input a key $fsk_f$ and a ciphertext $c$ and outputs a value $f(x)$.

Suppose that Alice runs $FE.Setup(1^k)$ and $FE.KeyGen(fmsk, f)$ where $f$ is a probabilistic function. Then she sends $sk_f$ and $fmpk$ to Bob.

Bob runs $FE.Enc(fmk,x)$ and $FE.Dec(sk_f,c)$ to get $f(x)$.

Is this possible? I mean as $f$ is probabilistic, it has to access Bob's randomness pool.
Bob can provide a faked pool. How can one guarantee the privacy of $f$?


There are ways to prevent Bob from having complete control over the randomness pool. You could use some form of verified randomness, where your function $f$ checks that the random string is signed before executing. This would work using, for instance, the NIST randomness beacon. You could also contain within $f$ a PRNG, so Bob does not need to provide all the randomness but only a seed (which could actually be signed and provided by Alice or another trusted party). But in the end, there is no way to guarantee statefullness between function calls, so nothing stops Bob from providing the same randomness to $f$ every time. This is a fundamental issue I believe.

| improve this answer | |
  • $\begingroup$ You could instead "contain within $f$ a" PRF, so that Bob can only provide "the same randomness to $f$" on each call with the same input. $\endgroup$ – user991 Oct 19 '14 at 23:56
  • $\begingroup$ @RickyDemer Is there some measures to prevent Bob from providing the same randomness to $f$ very time? Is there a non-deterministic PRNG or PRF? $\endgroup$ – Jan Leo Oct 20 '14 at 6:25
  • $\begingroup$ @JianLiu : $\;\;\;$ If $sk_f$ can be quantum, then it might be possible "to prevent Bob from providing the same randomness to $\hspace{.04 in}f$" every time. $\:$ There are non-deterministic PRNGs, but that would just move the problem to preventing "Bob from providing the same" entropy to the PRNG every time. $\:$ Do invoker-randomizable PRFs count as "non-deterministic"? $\;\;\;\;\;\;\;$ $\endgroup$ – user991 Oct 20 '14 at 6:39
  • $\begingroup$ @RickyDemer That's not a probabilistic function then. Since the PRF is deterministic based on the input $x$, every execution of $f(x)$ will be identical, even if Bob is completely honest. $\endgroup$ – Travis Mayberry Oct 20 '14 at 10:46
  • $\begingroup$ @TravisMayberry : $\:$ That depends on what the PRF takes as input. $\;\;\;\;$ $\endgroup$ – user991 Oct 20 '14 at 17:04

Your Answer

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

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