6
$\begingroup$

I am a professional developer with a mathematics background, but know next to nothing related to cryptography. I would like to know if the following scenario is even possible.

Let's say Alice and Bob each have a bitstring of length n. Alice sends her (encrypted) bitstring to a (maybe vulnerable) server where it is stored. Later, when Alice is no longer available, Bob computes the hamming distance between his bistring and Alice's, without learning its value. Additionally, Alice did not know of Bob beforehand.

I have been reading about secure function evaluation, oblivious transfer and others, but it seems that what I want to do is impossible. Is it really so ?

$\endgroup$

3 Answers 3

5
$\begingroup$

Call Alice's string $x$. We can make a few observations:

  • Given oracle access to the function $d(x,\cdot)$, it is easy to learn $x$. Pick your favorite $y$ and you can ask whether flipping one bit in $y$ makes $d(x,y)$ increase or decrease, and thereby learn the value of $x$ at that bit.

  • The server can run (in its head) the protocol between itself and an imaginary Bob, to non-interactively compute $d(x,y)$ for any $y$ of its choice. This is possible because Alice didn't know Bob's identity beforehand, so Bob cannot have any secrets that the server doesn't have. There is no way to prevent the server from assuming the role of Bob.

The server will always have unrestricted oracle access to the function $d(x,\cdot)$, so the server can always learn $x$ according to your requirements.

You can either conclude "what I want is not possible", or "what I want is possible, but the secure protocol is to have Alice send $x$ to the server."

$\endgroup$
2
  • $\begingroup$ Thanks, that makes sense. I guess the only option then is to do everything server-side and trust the server not to be compromised. $\endgroup$ Jan 14 at 1:45
  • $\begingroup$ @BenjaminLefebvre You could also reconsider if you need Hamming Distance? $\endgroup$ Jan 15 at 19:01
2
$\begingroup$

If you can have multiple servers of which at least one isn't compromised this is possible, using something similar to function secret sharing.

Let's say there are $n$ bits. Alice would share each of her bits $a_i$ additively, mod $n+1$, between the servers.

When Bob queries with his string $b$, each server would calculate $\sum{a_i^{(j)} (-1)^{b_i}} \pmod{n+1}$, where $a_i^{(j)}$ is the server's share of $a_i$. Bob could then sum up all of these to get $\sum{a_i (-1)^{b_i}} \pmod{n+1}$, and then $\sum{b_i + a_i (-1)^{b_i}} \pmod{n+1}$ is the Hamming distance.

$\endgroup$
1
  • 1
    $\begingroup$ Nice. Just to be clear, Mikero's oracle attack still applies: Bob (or anyone else pretending to be Bob) can learn all $n$ bits of $a$ using $n+1$ queries per server. (In fact, with a slightly fancier query strategy, I believe up to $n$ queries should suffice in the worst case, and possibly less if Bob gets lucky.) But if the non-compromised servers implement sufficiently strict query limiting (like allowing at most one query, ever, and erasing their shares after answering it), AFAICT this does indeed work. $\endgroup$ Jan 14 at 18:41
2
$\begingroup$

It is possible as long as Bob and the server are not on the same team.

To accomplish this, Alice must have a secure way to pass information to Bob, even though Alice doesn't know their identity in advance. Details will depend on implementation, but public key cryptography could work.

Then:

  1. Alice generates random one-time-pad for their bitstring.
  2. Alice sends bitstring XOR pad to server.
  3. Alice sends/encrypts pad somewhere so that Bob can later obtain it but server cannot.
  4. Bob sends bitstring2 XOR pad to server.
  5. Server sends Hamming distance to Bob and erases the values from its memory.

Neither Bob nor server learn the true value of Alice's bitstring, unless they conspire together to run the protocol multiple times.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.