HW6 Q2b

HW6 Q2b

Mark (guest) 20 Jan 2018 20:38

In the question 2b, we need to prove FH of the PKE. However, it seems that the set of functions F_n is not well-defined, as f \in F_n either takes in l "simple" inputs or l ordered pairs, depending on the side of the equality to be proven. Is such a laxity in the definition of a function input permissible at all?

Re: HW6 Q2b

nbitansky 21 Jan 2018 07:14

In 2.b the set of functions is "all (poly-time) functions". That's what *fully* means.
So given a set of encryptions of bits $x_1,\dots,x_n$, you should be able to compute a new encryption of $f(x_1\dots x_n)$ for any $f$.

Mark (guest) 27 Jan 2018 20:39

In the same question, can we assume that Eval_f operates separately on the members of the tuples?

nbitansky 27 Jan 2018 20:47

No.

Shlomi (guest) 30 Jan 2018 09:21

In Q2's description of how to encrypt m: is there a XOR operator missing between "m" and xor-aggregator?

I mean, does ct include
"m XOR xor-of-those-r_i's", or
"m TIMES xor-of-those-r_i's"?

nbitansky 30 Jan 2018 09:46

It's an Xor. Will clarify this.

Noam (guest) 30 Jan 2018 10:11

Another question,
By the definition of homomorphic encryption, if E is homomorphic to Xor, Eval_Xor is not necessarily Xor but it is implied from the process of decryption that it is.
can you confirm this?

nbitansky 30 Jan 2018 12:37

Eval_Xor could be whatever. In the HE we constructed in class for example to homomoprhically compute Xor, we computed addition mod q of two ciphertext vectors.

Noam (guest) 30 Jan 2018 12:46

right. but in this case the encryption involves regular Xor of ciphertexts and decryption involves decrypting this Xor. for the decryption to work the secret key decryption has to be associative with a regular xor.

nbitansky 30 Jan 2018 13:03

I need some context. In which case "the encryption involves regular Xor"?

Does your confusion concern question 2? Note that there ct \oplus ct' is defined in the question as "their homomorphic Xor" and not as their Xor as bit strings.
This is an abuse of notation. I now made this clear. Also added another clarification about homomorphic evaluation.

Last edited on 30 Jan 2018 13:12 by nbitansky Show more