1

I am currently working on a tedious project and I am stuck on a point that seems simple but very tricky. I want to preserve the privacy of search. Scenario: Bob is having an array of 10 unique numbers placed at several different indices For example [2 5 7 8 9 1 4 6 3]. Alice wants to tell Bob about the number she is interested in but doesn't want to send the number to do the comparison. Suppose if she is interested in the number 9, then bob should send the index number of 9 i.e. 5 to Alice but by sending the number 9 to bob she looses the privacy of data. I have searched for zero knowledge proofs but havent been successful.

1

You can use Oblivious Transfer.

Oblivious Transfer (OT) is a cryptographic primitive in which the sender transfers one of potentially many inputs to a receiver but remains oblivious to the input sent. The receiver also remains oblivious of the inputs he or she did not choose.

Chou and Orlandi define OT as it follows:

”In its simplest flavour, 1-out-of-2 OT, a sender has two input messages M0 and M1 and a receiver has a choice bit c. At the end of the protocol the receiver is supposed to learn the message M c and nothing else, while the sender is supposed to learn nothing.”

Below is an 1-out-of-2 OT protocol that is secure against semi-honest adversaries, as it was described by P. Snyder:

enter image description here

In your case, you have many numbers (ten to be precise) and you want to pick one each time. So you need a 1-out-of-K OT protocol. Such a protocol exists but it is much more complicated because it is based on Oblivious Transfer Extensions.

Oblivious Transfer Extensions:

There lies a problem found in every OT implementation. Due to the fact that every OT protocol is implemented via Public Key cryptography, it is increasingly difficult to simulate a very large number of OT transactions. To answer the previously stated problem, a solution would have to be found. Indeed, in 1996, Donald Beaver proved that OTs can be extended using symmetric cryptography. This notion was later proven efficient by Y. Ishai et al. As it explained by Asharov et al:

”An OT extension protocol works by running a small number of ”base OTs” de- pending on the security parameter (e.g. a few hundred) that are used as a base for obtaining many OTs via the use of cheap symmetric cryptographic operations only. This is conceptually similar to public-key encryption where instead of encrypting a large message using RSA, which would be too expensive, a hybrid encryption scheme is used such that the RSA computation is only carried out to encrypt a symmetric key, which is then used to encrypt the large message.”

You can check an implementation of the most known OT Extension protocol here.

Regarding the 1-out-of-K OT protocol, in 2013, Vladimir Kolesnikov and Ranjit Kumaresan proposed an optimization and generalization of the IKPN03 protocol which you can read here.


To conclude, OT is a known cryptographic primitive which does exactly what you want. You can use it in its simplest form (the 1-out-of-2 OT) and run it many times since you have 10 numbers instead of 2. Or, you can implement something more sophisticated such an OT Extension scheme.

See also:

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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