6
$\begingroup$

I'm looking for a special Pseudo Random Function (PRF) $F_k()$ which follows the below.

For fully homomorphic encryption (FHE), $\mathit{FHE}(F_k(x)) = F_k(\mathit{FHE}(x))$.

Or is there any homomorphically evaluable doubling pseudorandom number generator algorithm? (because Goldreich-Goldwasser-Micali PRF construction is based on the doubling pseudorandom number generator.)

Thanks.

$\endgroup$
  • $\begingroup$ Do mean encryption of x by FHE(x) ? $\endgroup$ – Hilder Vitor Lima Pereira Dec 3 '17 at 21:25
  • $\begingroup$ @HilderVitorLimaPereira Yes, I meant it. $\endgroup$ – takita Dec 4 '17 at 2:41
  • 1
    $\begingroup$ I assume FHE has to have some key, say $\kappa$. Suppose the family $\{F_k\}_k$ has the property that for any $\kappa$ and $k$, $\mathit{FHE}_\kappa(F_k(x)) = F_k(\mathit{FHE}_\kappa(x))$. Now I can trivially distinguish $F_k$ for uniform random $k$ from a uniform random function $G$. If this is the property you mean, then the answer is no, this is a contradiction in terms. So you'll need to be a little more specific if that's not the property you want! $\endgroup$ – Squeamish Ossifrage Dec 4 '17 at 17:28
  • $\begingroup$ What does "=" mean in the context of your question? Do you mean the ciphertexts are equal or that the ciphertexts are encryptions of the same plaintext? $\endgroup$ – mikeazo Dec 4 '17 at 21:05
  • $\begingroup$ @mikeazo I meant the latter. $\endgroup$ – takita Dec 5 '17 at 6:56
3
$\begingroup$

There is an Eurocrypt'15 paper published by Albrecht et al. which creates a cipher minimizing the number of multiplications needed to produce an encryption. This cipher is called LowMC and it can also be used as a PRF with almost same parameters as in the block-cipher - check out LowMC section in this paper.

Fortunately, there is open-source code which evaluates LowMC homomorphically with HElib. To evaluate the cipher homomorphically is to compute $\mathsf{Enc}_{\mathsf{k}}(\mathsf{LowMC}(x))$ from $\mathsf{Enc}_\mathsf{k}(x)$.

So you can plug in the PRF parameters given by Grassi et al. (for 128 bit PRF security) in the script provided by Albrecht and there you have it: LowMC becomes a PRF and your question is solved - compute $\mathsf{Enc}_\mathsf{k}(\mathsf{PRF}(x))$ from $\mathsf{Enc}_\mathsf{k}(x)$. And I think this is the state of the art for computing PRFs in HE land.

$\endgroup$

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.