5

As in the linked question, what you are missing is that the simulated view for a given input pair must be indistinguishable from the simulated view for the same input pair. So if $A$'s input $s$ is $0$, then the real view of $B$ will be $0$ with probability $1$. On the other hand, if your simulator just chooses a uniform bit, the simulated view of $B$ will ...


4

It is impossible to achieve (fully) information theoretic oblivious transfer (OT), since OT is complete (and so can compute all functions). Since many (most) functions cannot be securely computed information theoretically with two parties, this means that it's impossible. Having said that, we do have OT protocols that provide information-theoretic security ...


3

The short answer is: the algorithm that is trying to distinguish real from ideal interaction already knows the "correct" inputs. So it can easily distinguish in this case. More precisely, let's take the security definition from Hazay-Lindell (p21): $$ \{ S_2(1^n, y, f(x,y) \}_{x,y,n} \overset{c}\equiv \{ \textsf{view}_2^\pi(x,y,n) \}_{x,y,n} $$ The ...


3

I worry that the first problem is harder than your instructor suspects. We had to work a little hard to get a multi party PSI protocol based on efficient OT in our paper Practical Multi-party Private Set Intersection from Symmetric-Key Techniques, by Vladimir Kolesnikov, Naor Matania, Benny Pinkas, Mike Rosulek, Ni Trieu If I remember correctly, we may ...


2

The most straightward approach is to have Bob select two random symmetric keys $k_0$ and $k_1$ and have Bob publish $Encrypt_{k_0}( x_0^i )$ and $Encrypt_{k_1}( x_1^i)$. Then, Bob does an OT with Alice, allowing Alice to select between $k_0$ or $k_1$. She learns $k_b$, and then is able to decrypt all the $Encrypt_{k_b}( x_b^i )$ values, resulting in her ...


2

In MPC we judge security by comparing to the "ideal world" where a trusted third party does the entire computation. In the ideal world, an adversary can send anything it wants as input to the trusted third party. In the ideal world, when it comes to malicious adversaries, there really is no valid sense of a "correct/incorrect input" for the adversary. (For ...


2

It's easier to take the questions out of order. what can be said about the distribution of exponents a+b mod p when b is taken at random from Zp, but a is fixed? If $b$ is a uniform independent random value from the range $[0, p-1]$, that is, the probability of each possible value is $1/p$, and $b$ is distributed independently from $a$, then $a+b \bmod p$...


1

When we are analyzing the security of MPC protocols, we have to be aware that the judgment of some behavior as malicious depends on the enviroment. Another aspect is to consider if there a defense against this (supposably) malicious behavior. Let me explain: if the receiver of an OT Bob refuses to open it, is he acting maliciusly? That is, if he decided ...


1

A:Xb+k-X1, Xb+k-X2 -> k1, k2 A:m0+k0, m1+k1 -> m'1, m'2 -> B B knows Xb+k (transmitted it in a previous message), X1, X2 (A sent those), hence he can compute k1, k2. Hence, he can reconstruct both m0, m1, hence the protocol doesn't have the security properties we're looking at... Now, you don't have to use RSA, however you really do have to use ...


1

Any efficiently computable function can be represented by a circuit containing XOR gates and AND gates - AND gates alone would not suffice (but NAND gates would). The standard practice in secure computation is to use this {XOR, AND} basis to represent functions, since evaluating a XOR is often very cheap (it only involves cheap local operations, and no ...


1

First, what is $AND_B$? $AND_B$ is the asymmetric AND protocol, in which Alice and Bob each has a bit $x$ and $y$, at the end Alice always learns nothing (get output 0) and Bob learns $x \land y$. In Lemma 4 it says $AND_B$ can be realized by 1 invocation of $(^2_1)OT$. Then what is $G_{m+1}$? $G_{m}$ is a protocol in which Alice has a $m$-bit long string $...


1

With the most standard approaches, the cost of performing $m$ $1$-out-of-$n$ oblivious transfers of strings of length $\ell$ with security parameter $\lambda$ is $O(m(\lambda + n\ell))$ (see e.g. this paper, Section 5.3). Use $m=1$ above to have the asymptotic cost for a singe OT. Note that this can be improved in various settings - e.g., it can be typically ...


Only top voted, non community-wiki answers of a minimum length are eligible