Score:2

Claims about universally composable oblivious transfer, which ones are correct?

jp flag

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?

jp flag
I found a newer version of the second paper on IACR preprint: https://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.
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.