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 ...


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

GMW protocol says that A and B can locally compute $c_i = a_i \oplus b_i$ and the result should be same for both. I highlighted the part that is incorrect. They started with secret shares of $a=0$ and secret shares of $b=1$. Now they have secret shares of the XOR $c= a \oplus b =1$. Only if the secret value $c$ is zero will their shares be the same (and ...


1

With some assumptions I think you can do this with a simple protocol. We will break i into two parts: attempt an allocation which may succeed with reasonable liklyhood. And verify it. If verification fails try again. The first step we can do by each party randomly selecting for himself if he is the chosen one with probability 1/n. Verification we do with ...


1

You're looking for PIR, Private Information Retrieval or OT, Oblivious Transfer and possibly also PSI, Private Set Intersection. PIR enables a client to query a server for the $i$-th entry of a database without the server learning the query. However, the client may learn values for other indices too. OT is a stronger PIR without this leak. PSI enables a ...


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