There are two papers that propose oblivious transfer protocols, both claiming to be universally composable (UC). The first protocol is more complex, and I am convinced that it is indeed UC. The second protocol is simple, but reminds me of the so-called "simplest OT protocol" of Chou and Orlandi, which is well-known to be not UC. Is the second paper making a mistake in claiming their protocol is UC?

First paper: https://eprint.iacr.org/2019/726.pdf

Second paper: https://arxiv.org/pdf/1710.08256.pdf

Chou and Orlandi paper: https://eprint.iacr.org/2015/267.pdf

Simple summary: Both protocols assume that there exists an OW-CPA public-key encryption scheme, whose public key is $n$ bits and indistinguishable from a random $n$ bit string. Let $H$ be a random oracle. Both protocols begin with the receiver generating a key pair $(pk_b, sk)$ and sampling a random $t$. Let $pk_{1-b} = pk_b \oplus H(t)$. The receiver sends $(pk_0, t)$ to the sender.

The sender chooses two random keys $k_0, k_1$ and encrypts them using $pk_0, pk_1$ respectively, with $pk_1 = pk_0 \oplus H(t)$. At this point the two protocols become different. The first paper uses an elaborate challenge to convince the sender that the receives knows one of $k_0, k_1$, and also convinces the receiver that the sender knows $k_b$. Then the messages $m_0, m_1$ are encrypted with $k_0, k_1$ and sent to the receiver. The second paper does not perform any challenge and simply sends the encrypted messages.

Structurally, the second paper is similar to the Chou and Orlandi protocol, but C-O is not UC due to a "timing bug" (the receiver can delay decrypting the messages, so the simulator may not be able to extract the bit $b$) and other defects (example: https://eprint.iacr.org/2017/370.pdf). My intuition is that the second paper also suffers from the same defects and so is not UC.

On the other hand, there are claims of UC-OT under other settings that also does not seem to require the elaborate challenge in the first paper (example: https://www.iacr.org/archive/asiacrypt2016/10031130/10031130.pdf). Is the second paper incorrectly claiming UC, or is the first paper doing unnecessary extra challenge for UC?

  • $\begingroup$ I found a newer version of the second paper on IACR preprint: eprint.iacr.org/2017/993, with the protocol modified to be almost the same as the first paper. I think that settles for now that the Arxiv version of the second paper is not UC. $\endgroup$ May 26, 2023 at 14:10


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.