A Framework for Efficient and Composable Oblivious Transfer

We will explore a generic secure Oblivious Transfer protocol with the help of any dual-encryption cryptosystem. An Oblivious Transfer (OT) protocol is a cryptographic protocol between a sender A and a receiver B, which enables B to receive one out of two (or more) messages from A with respect to B's choice bit(s). The OT almost resembles an Encoder, omitting the security part. The transfer is said to be oblivious, because A is unaware of which message B received, and B does not receive any information about the remaining messages of A.

With this requirement in mind, we now see a new cryptographic primitive known as dual-mode encryption cryptosystem.  As the name suggests, this cryptosystem can be operated in 2 modes, which differ only in the Setup phase, which is run before the execution of protocol. The difference between the modes of operation is achieved through the generation of a parameter crs by the corresponding Setup algorithm, which is then passed to the remaining operations. The two modes are Messy Mode and Decryption Mode, and they each have their corresponding SetupMessy() and SetupDecryption() algorithms.

In addition to this, the cryptosystem can be operated in two branches. Denoting them as 0 and 1, it has the property that a message encrypted in one branch can only be decrypted in the same branch. This is fulfilled by giving the Key Generation algorithm an additional parameter b=0 or 1 to denote the branch.  It then outputs a public key-secret key pair for use in that particular branch.  

Additionally, Encryption also takes the branch as a parameter.  Decryption can only succeed if the given ciphertext and secret key are generated using Encryption and Key Generation (respectively) with respect to the same branch.

For a chosen mode, we can operate the cryptosystem in either of the two branches.

Given the properties we can intuitively see that a one-out-of-two OT protocol can be constructed as follows, for any mode of operation.

•        Both A and B receive the same crs corresponding to either Messy Mode/Decryption Mode.

•        A has messages m₀ and m₁

•        B picks a bit b, for which message he wishes to receive, and runs the key generation for branch b. He receives a secret key (sk) and public key (pk) for this branch.

•        B sends pk to A, who encrypts both his messages using this public key  as follows

•        He encrypts m₀ with the public key, and branch 0 to get c₀

•        He encrypts m₁ with the public key, and branch 1 to get c₁

•        He then sends both c₀ and c₁ to B

•        It is now easy to see that if B has b=0, he has the secret key for branch 0 and can decrypt c0. Similarly if he had b=1, he would have the secret key for branch 1 and he would be able to decrypt c₁.

We can clearly see from the property of the dual-mode cryptosystem that B cannot decrypt the ciphertext c_1-b as he does not have the secret key corresponding to the branch (1-b).  Additionally, since the sender receives only the public key, he cannot know which branch the receiver is operating in. This protocol satisfies the properties of OT. We also saw the security proof for each of the modes as follows.

Mode Security for	Messy	Decryption
Sender	Statistical Security	Computational Security
Receiver	Computational Security	Statistical Security

Security specified in each cell of this table can be proven using a Real World-Ideal World paradigm where we use the remaining functions defined (TrapKeyGen(), FindMessy() in cases of Decryption mode and Messy mode, respectively) along with the properties of the dual-mode cryptosystem, to aid the Simulator. The Simulator, who is the adversary in the ideal world, can then simulate the protocol with the real world adversary such that it is indistinguishable to the adversary from a complete real world execution.

Knowing that the only difference between the two modes lies in the generation of crs in the Setup phase, we can conveniently switch the mode of operation of the cryptosystem to change the levels of security for the sender and the receiver, depending on our protocol requirements.

There also exist several practical instantiations of the protocol, with security based on the DDH assumption and the Quadratic Residuosity assumption, among others.

We have seen that the dual-encryption primitive intuitively leads to a secure and practical OT protocol.