t-Out-of-n String/Bit Oblivious Transfers Revisited

In this paper, we focus on lowering the complexity of

t

-out-of-

n

string/bit OTs for large

t

. The notion of oblivious public-key cryptosystem (OPKC) is introduced, in which Bob possesses

n

public keys but only

t

private keys and no one knows which

t

private keys Bob possesses. If the sender, say, Alice, encrypts each message using the

n

oblivious public keys, resp., the receiver, Bob, can obtain only

t

messages by

t

decryptions with his known

t

private keys. This approach can be directly applied to

t

-out-of-

n

bit OT. However, it is very inefficient due to heavy message expansion and many encryption/decryption operations. To construct

t

-out-of-

n

bit OT, we introduce bit oblivious public-key cryptosystem (BOPKC), which is a special public-key cryptosystem with a message space of

n

bits, and the private key only enables its owner to decrypt

t

bits of

n

secret bits. After an offline generation of such a BOPKC, it requires only one encryption, one decryption and one ciphertext. Finally, we show the concrete implementations of OPKC/BOPKC based on ElGamal/Paillier cryptosystem, and efficient

t

-out-of-

n

string/bit OTs are achieved.