# Tag Info

10

Oblivious transfer is mostly studied as a theoretic construction, as it is an important component in achieving interesting protocols (like secure two-party computation and secure function evaluation). The interest in 1-2 OT is that it is a minimal definition theoretically, and most results that limit themselves to 1-2 are designed to improve some basic ...

6

the securty of 1-n OT is a function of the security of a 1-2 OT. So in analysis it is easy to use 1-2 OT for security proofs. A 1-n OT is essentially a multiple run of a 1-2 OT. (somewhat like a byte is made of 8 bits) So IMO the question is like asking why use bits when you can use bytes for communication. [it depends on the application]

6

No, as written, your protocol doesn't work -- the problem is that Bob is supposed to be allowed to choose $b$, your protocol selects a random one for him. However, it is close -- here is a modification that I believe does work: First, suppose Alice has her values $(x_0, x_1)$, and Bob has his bit $b$. They run their Random functionality R, and so Alice ...

6

There are two that I know of that are pretty simple. I'll first start with one that requires a "Trusted Initializer" where we assume that there is a party Ted which is trusted by both Alice and Bob and only needs to be present for the initialization stage. This is an extension of a quantum protocol and was proposed by Rivest in Section 7. Alice holds $... 6 Yes. The easiest way is if$K$is an RSA private key, and Bob has the public key. Then, here's how it works; we'll call the ciphertext that Bob has$C$: Bob selects a random number$r$, and computes both$C \cdot r^e \bmod N$and$r^{-1} \bmod N$(where$e$and$N$are the public exponent and the modulus from the public key) Bob sends$C \cdot r^e \bmod ...

5

What you are seeking for is a special case of secure multiparty computation, namely secure function evaluation or also called secure 2 party computation. However, general solutions to this problem require interaction, meaning that the parties performing the computation need to exchange more than two messages. You write: To compute some arbitrary ...

4

The other answers are good but I thought I would systemize the differences with a single example. Say Bob has a database with 10 entries of the form {name, salary} and Alice would like to query it. With PIR, Alice can retrieve any entry or entries of her choosing (say the 8th entry) without Bob learning which one. The trivial PIR is Alice just retrieves ...

4

Not a real answer, but some hints: Single DB PIR schemes (ones that don't need several non-colluding DB) have had serious efficiency problems for a long time. See paper 'on the computational practicality of private information retrieval' by Sion and Carbunar arguing that all schemes at that time (2007) were less efficient than downloading the whole DB (most ...

4

More generally, any encryption that is commutative can be used because then: $$(D_k \circ D_K \circ E_k \circ E_K)(m) = m$$ I.e. Bob can encrypt the ciphertext $E_K(m)$ with a new key $k$, then gives that to Alice for decoding with $K$ and finally decodes it himself with $k$. Stream ciphers are commutative, as is exponentiation modulo $n$ (used in RSA) ...

4

Here is a concrete example of how the receiver could extract information about the senders input: Assume the circuit to be evaluated is the simple circuit computing $(x \oplus (y \wedge z)) = w$, where $x, y$ is the input of the sender and $z$ the input of the receiver. Note, that $w$ and $z$ alone does not reveal the value of $y$ (you can write down the ...

4

The problem is because sender has provided the receiver with a garbled circuit in which the sender's inputs are hard coded (or has provided keys for those inputs, which is morally the same). If the receiver has both keys for each input wire then it is trivial to narrow down the possible values of the sender's input. Consider a concrete example, the ...

3

The problem is known in the literature as private function evaluation (PFE). A sender has input (a function) $f$; a receiver has input $x$, and only the receiver learns $f(x)$. If you are willing to leak the topology of a circuit that computes $f$ (but not the identity of the gates), then using classical garbled circuits / Yao's protocol will work. These ...

3

They could use 1 out of 2 oblivious transfer. Alice offers the messages $0$ and $a$ and Bob uses $b$ as his choice bit (I.e., choosing the first message if $b = 0$ and the second if $b = 1$.). It should be easy to see that Bob now receives $a \land b$ (if in doubt write down the truth-table). Now Bob can send the result to Alice (or they can do the protocol ...

3

OT is typically not used as an application in its own right. In the context of access control, OT limits the number of messages received by B but not which messages. I don't know of any real applications for this (you could talk about a subscription where B has purchased the right to read any $k$ articles, but this is pretty artificial in my opinion). ...

3

Approach 1 The simplest way of doing this is for the receiver, with choice $j \in \{1,\dots,n\}$, to input $1$ in the $j$-th 1-out-of-2 OT and $0$ elsewhere. The sender, with input $(x_1, \dots, x_n)$, inputs $(0,x_i)$ in the $i$-th OT. Approach 2 An alternative protocol (that just came out of a discussion with a colleague, and seems to be actively secure)...

3

You can use Oblivious transfer protocol for the answers: https://en.wikipedia.org/wiki/Oblivious_transfer Here is an example with only 2 answers ($m0$ and $m1$) and uses RSA ($e,d,N$) : In your case Alice would have to send $x_0 \ldots x_9$ and Bob would have to pick $b \in \{0,\ldots,9\}$ where $b$ is the number of his question. The operation $m + k$ ...

3

The simplest way to do this would be to have the sender randomly shuffle the elements. The receiver chooses a random element to request. That way the receiver has no idea which of the original (before the shuffle) elements he got.

3

The usual technique for having a group of prime size $q$ is to work modulo a prime $p$ such that $q$ divides $p-1$. The target group is then the subgroup of $q$-th roots of $1$ in $\mathbb{Z}_p$. To build such a group, first choose $q$, then selects random values $r$ until you find one such that $p = qr+1$ is prime. This is the way it is defined in the DSA ...

2

In differential privacy the concern is to protect the privacy of a single row of the database. Informally, the DP concept says that everything that can be learned from the database could be learned without access to that row. In a more technical sense, a mechanism respects this property if the distribution of the answers is almost identical (in a very strict ...

2

There is a slight distinction between PIR and OT. From Wikipedia: PIR is a weaker version of 1-out-of-n oblivious transfer, where it is also required that the user should not get information about other database items. In other words, OT is stronger in that the receiver only gets what is requested. Differential privacy is new to me, so I'll read up ...

2

There's a new really simple OT protocol based on DH. It's even practical. Watch this video. For the paper and source code, go here.

2

The computational assumption is a 2-message scheme that is PIR with respect to the client<-server message and can easily handle databases in which the number of entries is small but the entries themselves are large. I'll describe a candidate for that, followed by how it can be applied for your use-case. Notation Alert: "s" is not really related to "...

1

That is possible if and only if oblivious transfer is possible. Proof: For the left-to-right implication, Alice just lets the last 8 answers be independent of her inputs. For the right-to-left implication, Alice creates 6 extra answers that are independent of her inputs, splits each answer into 4 shares, and then for i in {0,1,2,3}, obliviously transfers ...

1

Kolesnikov & Kumaresan defined a primitive called "string select OT" which basically covers your setting but with a database of 2 items. Sender has $x^1, y^1, x^2, y^2$. Receiver has $x^*$. If $x^* = x^i$ then the receiver learns the corresponding $y^i$. I think a generalization of their protocol would work, at the cost of $n$ 1-out-of-2 string OTs ...

1

How about hashes? $P_i$ choose random numbers $R_i$ that they exchange through $S$. They calculate $H_i = H(R_1|R_2|m_i)$ that they give $S$. If $H_1 = H_2$, then $S$ can be reasonably sure $m_1=m_2$. Assuming $H$ is a strong cryptographic hash function and $R_i$ are long enough to avoid collisions (e.g. 256 bits), the worst the server can do is a brute ...

1

The obvious approach is to help Bob learn $s_0 \oplus (s_0 \oplus s_1) \times c$, presumably using $F$ to help him learn this information. So, here is the natural protocol: Alice and Bob invoke $F$. Alice provides the input $s_0 \oplus s_1$, Bob provides the input $c$. Alice learns $p$ and Bob learns $q$, where we are guaranteed that \$p \oplus q = (s_0 \...

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