I’m aware of a couple of OT protocols, most of which use Public Key Cryptography, Key Establishment (or similar constructs) as the base. I don’t really have specific knowledge on other OT protocols, however lately we’ve been discussing post-quantum OT, which actually inspired this approach on some “new(?)” type of asymmetric encryption. Which might potentially be useful, if an OT shows up which is not built on Public Key Cryptography or Key Establishment and proven to be post-quantum secure.

Here I would like to describe some form of encryption, humbly named “Oblivious Encryption”

Encryption: For each bit $b_i$ in Alice’s message, Bob creates two random numbers $r_{i_0}$ and $r_{i_1}$. By means of OT, Alice chooses one of these random values as $r_i$, based on the bit value of $b_i$. Alice sends all $r_i$ segments to Bob as the encrypted message.

Note: Bob is using a PRG with a seed (the seed acts as the key, and should not be reused)

Decryption: Bob initiates the PRG with the same seed. For each $r_i$ segment, Bob recreates the two random numbers $r_{i_0}$ and $r_{i_1}$ picks the value, that was associated with bit $0$ or $1$, constructing the $b_i$ values for message $m$

This, in essence, is a really silly symmetrical encryption scheme (probably akin to OTP); however with the touch of OT, it becomes somewhat asymmetrical, thus named Oblivious Encryption. First of all, does this make sense? Are there similar constructs, and what can you say about the security of this scheme?


1 Answer 1


If your goal is to let Alice to securely send a message to Bob (in the presence of a passive eavesdropper), then it achieves this goal. It is not secure if the adversary is active.

Potentially you can use OT extension (if random oracle model is acceptable) instead of OT to improve efficiency, if Alice and Bob needs to communicate multiple times. Basically OT extension uses a small number of base OT invocations (involving public key operations) to bootstrap, then you can invoke symmetric key based OT functionality many times. Some References:

That's said, your protocol is not quite efficient (for achieving the goal) and there are easier and better ways of doing that (e.g. just do a key exchange and encrypt the message with the session key).

  • $\begingroup$ I’m also trying to come up with something post-quantum as well. $\endgroup$
    – zetaprime
    Sep 14, 2018 at 14:32

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.