# Tag Info

8

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 $m_0,... 7 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 ... 7 The term "stand alone" in secure computation typically refers to the case of a protocol being run once, and not to assumptions. In any case, what I assume you are really asking is what assumptions are needed for OT. You are indeed correct that OT is built from asymmetric assumptions, and this is actually inherent for black-box constructions. This was studied ... 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 N$... 5 Yes, if you take an instance out of the function family (e.g.$F_{K_1}$), then the evaluation of this function at$x$always yields the same result. You can think of it like that: If you fix a key$K$, then your PRF is basically a look-up-table. For every possible input$x \in \{0,1,\cdots,2^m-1\}$there is an entry in the look-up-table for the output$F_{...

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

5

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

5

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

5

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

5

You can take a look at LibOT, which is a C++ implementation of several OT extension protocols. In the Readme you can find a list with many base and extension Oblivious Transfer protocols. A protocol that people use a lot is the Simplest OT (although it was announced that the security proof has a bug by one of the authors at the TPMPC2018 workshop). ...

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

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

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

4

Recall the ElGamal encryption scheme: The secret key is some random $r \in \mathbb{Z}_q$, the public key is $h := g^r$ , together with the group order $q$ and the generator $g$ of the group $\mathcal{G}$. To encrypt a message $m \in \mathcal{G}$, one chooses a random $s \in \mathbb{Z}_q$ and computes the ciphertext $(c_1, c_2) := (g^s, m \cdot g^{rs})$. To ...

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

Are there any Oblivious Transfer (OT) protocols that don’t rely on asymmetrical encryption, public-key encryption or key-exchange? Surprisingly, there are indeed OT protocols which don't rely on public-key encryption. In Precomputing Oblivious Transfer, Beaver showed that if Alice and Bob are each given some correlated randomness by a trusted third party ...

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

The sender chooses log n pairs of secret keys (say, for encryption). Then, each number between 1 and n is naturally associated with a subset of exactly log n keys. The protocol then works by running log n 1-out-of-2 OTs where the receiver asks for the keys that are associated with its input (number between 1 and n). Finally, the sender encrypts each of the n ...

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

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

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

3

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.

3

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

3

Post-quantum oblivious transfer protocols are possible. If you base the security of the OT in a post-quantum assumption, this should give you an OT conjectured to be robust to quantum attackers. Besides the already mentioned OT based on supersingular isogeny (in comments), I can give you some other examples: Code-based: https://eprint.iacr.org/2008/138.pdf ,...

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

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

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

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