Tag Info

Hot answers tagged

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


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

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.


1

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

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


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

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


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



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