Introduction- 1.1

1.1   The New privacy enhanced matchmaking protocol

Baldwin and Gramlich brought out the idea of online matchmaking in 1985[BG85]. Take, for example, the concept of arrange marriages. In arrange marriages, both parties have knowledge of each other’s identities, but they do not reveal anything to each other unless their wishes match with each other. To explain a little further, both the girl and boy wants to marry someone having certain characteristics/wishes (skills, financial stability, social status, well-being, location, qualification, etc.). A meeting is then set up where they both talk to each other, spend time together without telling each other at this point, that each of their wish matches with each other. If their wishes match with each other, then it is a match and then they can reveal the information to each other.

There can be some other examples of matchmaking protocols like job hires and dating services.

The main reason behind bringing the idea of online matchmaking was to support the anonymity of users, matches and last but the not least, if the wish of both the parties matches, then both the users will be notified.

But this idea required a middleman who has the knowledge of identities of both the users and their wishes, now it is up to the middleman not to expose their information.

Upon further research, it was found that this idea of Baldwin and Gramlich is vulnerable to a simple message replacement attack [ZN01] which can expose the identities of both parties and their wishes too.

Later in the Late 1980s, another researcher Meadows brought another matchmaking protocol that does not require a middleman [Mea86] beyond the very first step. But again, the problem found in this approach was that it could provide privacy to credentials but does not provide the anonymity to both parties.

The most recent one was given by Zhang and Needham [ZN01]. Their protocol had some amount of anonymity/privacy. It achieved so by not allowing both the parties to communicate directly. This protocol requires an untrusted online matchmaker that will work/behave as an open discussion forum/broadcast board thereby removing anyone to one communication among users. Any user can go and match his wishes against some other’s user wishes by simply downloading any pair of ciphertexts. If the wish matches, he gets the session key for communicating to that person further.

While this protocol solves the problem of privacy and anonymity, but it did not have any framework to notify both the users in case their wishes match. Adding this functionality would then require the middleman service to be used.

There are some other problems also in this protocol: -

1.      The identity of the person posting wishes on the broadcast forum can be compromised by launching a dictionary attack by the attacker.

2.      The attacker can take any set of wishes, hash them to generate the key and then decrypt the pair of ciphertexts

3.      In simple words, the attacker can perform an exhaustive search (brute force) of all possible wishes to find a matching wish and the identity of the users posting it.

4.      Secondly, Let us assume for a moment that wishes posted by users have very low predictability, even then it is enough for an attacker to break the privacy of a wish that has been posted on the broadcast forum and as a result, and it also creates a vulnerable situation to compromise all the previous protocols that contain that particular wish.

1.1.1   Our Benefactions

We aim to supplement the objectives of matchmaking protocols with some new security objectives which are basic and important to matchmaking. So, to summarise all the new objectives, here are they: -

- The authenticity of users and wish matches
- Privacy of users' identities and of their wishes
= anonymity of users and privacy of wish matches
= privacy resistance to off-line dictionary attacks
= forward privacy of users' identities and their wishes

When 2 users authenticate, there needs to be a trust between them so that they can be assured that no one is impersonating them which leads to a factor called authenticity. As we have already discussed, wishes vary from each class of user to other classes. Wish privacy is desired or else it will lead to a breach of privacy of both the parties. Practically, the wish space is limited and easy to predict. It leads to attacks on the wish space. So, the protocol should have resistance to these attacks.

Last but not least, forward privacy is pretty significant. If there is an outbreak in the privacy of the currently running protocol, it should not spread to the older runs of the protocol. We will, therefore, present an amplified privacy matchmaking protocol that will oppose/face any perpetrator that tries to attack the security objectives explained above. The improved and enhanced protocol will be very simple and implemented by taking into account the PAKE protocol. [BPR00, CHK05, GL03, GL01, KOY01, MPS00, NV04].