4

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

Jan Leo
  • 905
  • 6
  • 12
  • 1
    You should look at these papers: 1) [Functional Encryption for Randomized Functionalities](https://eprint.iacr.org/2013/729), 2) [On the Relationship between Functional Encryption, Obfuscation, and Fully Homomorphic Encryption](http://web.mit.edu/dwilson/www/papers/abfggtw13.pdf), 3) [Controlled Homomorphic Encryption: Definition and Construction](https://eprint.iacr.org/2014/989), 4) [Functional Encryption for Randomized Functionalities in the Private-Key Setting from Minimal Assumptions](https://eprint.iacr.org/2014/868) – Alf Sep 04 '16 at 08:21

1 Answers1

3

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.

Travis Mayberry
  • 1,245
  • 8
  • 7
  • 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. –  Oct 19 '14 at 23:56
  • @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? – Jan Leo Oct 20 '14 at 06:25
  • @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](http://www.wisdom.weizmann.ac.il/~oded/PS/obf4.pdf#page=25) count as "non-deterministic"? $\;\;\;\;\;\;\;$ –  Oct 20 '14 at 06:39
  • @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. – Travis Mayberry Oct 20 '14 at 10:46
  • @TravisMayberry : $\:$ That depends on what the PRF takes as input. $\;\;\;\;$ –  Oct 20 '14 at 17:04