# Tag Info

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 ... 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) ... 3 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 ... 3 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 ... 3 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 ... 2 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 ... 1 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 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 ...