In question 4.a. :

What do you mean when you say "Use the characterization given in class" ?

I don't understand, what are we supposed to show in this question ?

you defined in class what it means to privately compute a function in the presence of unbounded parties. You gave a characterization of which functions can or can't be computed this way. You're supposed to use it to show that the given function cannot be privately computed.

In question 3:

Are X1,…,Xn supposed to be bits and not strings in length n ?

What is the definition of Eval when it is given a set of encryptions in the second argument ?

האם שאלה 4 מתייחסת לטענה שדיברה על קיום של תת מטריצה כלשהי ?

לא נראה לי שממש הבנתי מה הטענה אומרת, שלא נדבר בכלל על הסיבה שהיא נכונה.

האם אפשר לקבל הסבר יותר פורמלי של הטענה הזו ?

וגם מה זה אומר בדיוק תת-מטריצה ?

תודה

**Submatrix:**

Let M be a matrix with rows indexed by a set X and columns indexed by a set Y: For every $x\in X, y\in Y$ there is a value

M[x,y]. Let $X'\subseteq X, Y'\subseteq Y$. A submatrix M' of M on $X'\times Y'$ is a matrix whose rows indexed by the set X' and whose columns are indexed by the set Y, such that for $(x,y)\in X'\times Y', M[x,y]=M'[x,y]$.

**The equivalence relation:**

Let F be a function defined on $X\times Y$ (a finite set), and let M be the matrix defined by the function F, namely M[x,y]=F(x,y).

Define a relation ~ on the rows by $x_1 \sim x_2$ if there is a $y\in Y$ such that $M[x_1,y]=M[x_2,y]$. Let the equivalence relation $\approx$ be the transitive closure of the relation $\sim$. Define likewise an equivalence relation

on the columns.

**Claim** (no proof given or required): F is privately computable for two honest but curious, computationally unbounded parties iff its matrix, M, has no submatrix

M' such that all rows of M' are equivalent by $\approx$, all columns of M' are equivalent, and M' has at least two entries with different values.

The simplest examples for a function that is not privately computable are OR of two bits and AND of two bits. XOR is privately computable.

In question 2(a), the i'th son must sample sk(i,c) given c and sk(i) or can he compute sk(i,c) given those inputs?

Thanks

In this construction, indeed he can deterministically compute $sk_{i,c}$ from $sk_i$ and $c$, so we couldv'e said "compute" rather than "sample".

While decrypting, can the sons share their secret keys SK_i (and not SK_i,c)? Is it possible to divide the shares in a way that if they do that (share their SK_i keys), each of them will be able to decrypt new ciphers individually (but still sharing the SK_i,c keys will not allow them to do that)?

you got it the other way around. They should never be able to decrypt individually, only together. Moreover, you don't want that once they decrypted together one cipher, then any of them can decrypt the next cipher, which is why they won't use directly their $sk_i$ in the decryption process of a given cipher $c$, but rather a key $sk_{i,c}$ which will be useful only for this cipher.

בשאלה 3, האם Eval

שנתונה בשאלה היא $\epsilon$-function-hiding ?

האם מספיק לתאר את הפרוטוקול מבלי להוכיח נכונות ?

Regarding question 1.c (bonus)

Can you elaborate on the differences between this question and question 1.b?

From what I understand in this question we still need to simulate the prover, but now we don't get b as input - which seems a bit impossible

Or maybe we're requested to simulate both the prover and the verifier? (If so - I don't really understand why this shows resistance to a malicious verifier)

Thanks!

We talked about it in the recitation. In the malicious verifier case. You are given an arbitrary verifier algorithm $V^*$ that may choose his message $b$ however he wants and possibly depending on the first prover (real/simulated) message.

In question 4.b, what is the definition of a privately computable function in the case of two computationally unbounded parties ?

In question 4.c, when did you mention that oblivious transfer is not privately computable if the parties are computationally unbounded ?

I don't understand how is oblivious transfer related to privately computable functions ?

Joining the question regarding 4.b

It seems that if both party's wish to learn F_2(x,y) then Benny will always learns Nir's input, which contradicts the definition from the recitation/lecture.

In the context of two computationally unbounded, curious but honest parties, we say that a protocol for computing F(x,y) is private

if: Whenever F(x1,y)=F(x2,y), the communication between the two parties on inputs (x1,y) is (x2,y) are distributed identically. Likewise,

whenever F(x,y1)=F(x,y2), the communication between the two parties on inputs (x1,y) is (x2,y) are distributed identically.

An alternative definition (equivalent in this context) is that given x and F(x,y), party 1 can simulate the communication exactly, and likewise given y and F(x,y), party 2 can simulate the communication exactly.

The definition given above is in under the assumption that at the end of the computation, both parties see F(x,y). If just one of

them gets to know F(x,y) upon termination, the definition and criteria would change.

I mentioned that XOR is privately computable (with a trivial protocol - each party can reveal its bit). In general, if F(x,y) is privately computable, such computation will follow the decomposition of the associated matrix to equivalence classes.

Regarding Question 1.b

A general question. Given a value y in QR is it possible to calculate x such that x^2 = y? (where x,y belong to Z*_N where N = pq)

Could it be the link to assigment 4 is broken?

When I try to open it a get a message: "The file does not exist."

Regarding question 2a: are the sons honest? Do they follow the protocol, or try to hack it?

In question 4.b it's written that variable * x* range over subsets of

*. Did you meant elements of*

**{0,1,2} * {0,1,2}***?*

**{0,1,2} * {0,1,2}**Q4.b

Hi,

I can't think of any protocol that would allow computation of F2 privately.

If I understand correctly both participants(Benny, Nir) with private inputs x,y should get the value of F2(x,y), as well they both know F2.

But by knowing input x and output F2(x,y) you can go over all possible y' values and compare F2(x,y) == F2(x,y'), if true then you reveal the input of second participant.

Please correct me if i wrong.

Thanks!