Improve performance of verify function for receiver in Committed OT

[th4s]

The current implementation (#86) fast-forwards the state of sender and receiver by splitting, if there is an offset. This requires to compute the complete KOS matrix.

An improvement would instantiate the sender and receiver with an rng offset, so that only the part of the KOS matrix, which is really needed for verification, would be created. This avoids some unnecessary computation.

This requires some adaptations to the inner workings:

• We can no longer use the rng to generate padding.
• There is not only a single rng per sender/receiver. The other rngs probably need to be set to the right offset, as well.

[sinui0]

Following up on this, we should be able to simplify things further.

This should be sufficient:

1) The Sender commits to their base choices $\Delta$ 2) The Sender and Receiver run the OT extension to acquire COTs, where the Sender holds $(t{i,0}, t{i,1}) \equiv (q{i,0}, q{i, 0} \oplus \Delta)$ and the Receiver holds $t_{i,c^{\$}}$

Note that the Sender and Receiver convert these to ROT by hashing $k{i,j} = \mathsf{H}(t{i,j}, i)$. The Sender encrypts their messages $m{i,j}$ where $C{i,j} = k{i,j} \oplus m{i,j}$

3) The Receiver receives and records $(C{i,0}, C{i,1})$, $t_{i,c^{\$}}$ and their choices $c_i$ for all OTs 4) The Sender reveals their base choices $\Delta$ to the Receiver 5) In the outer context the Receiver determines the expected messages for each OT $(m{i,0}, m{i,1})$ 6) The Receiver checks that the previously received ciphertexts are correct by computing $C{i,j} = k{i,j} \oplus m_{i,j}$

Note that the Receiver has recorded $t_{i,c^{\$}}$ and $c_i$, so checking the ciphertexts is trivial:

1) Recover $(q{i,0}, q{i, 0} \oplus \Delta)$ 2) Compute the keys $k{i,j} = \mathsf{H}(t{i,j}, i)$ 3) Assert the expected messages encrypt to the recorded ciphertexts $C{i,j} == k{i,j} \oplus m_{i,j}$

For memory optimization, the Receiver can record $\mathsf{H}((C{i,0}, C{i,1})..(C{n,0}, C{n,1}))$ instead then check against this hash.

[sinui0]

$\Delta$ Malleability

The above is vulnerable to malleability of $\Delta$, eg if the Sender reveals $\Delta^*$ which is different than $\Delta$ used in the setup. I'm pondering on how to bind this without having to rerun the entire setup.

Focusing on 1 OT, let's look at this malleability issue:

Denote the Sender as $\mathcal{S}$ and Receiver as $\mathcal{R}$

1) $\mathcal{S}$ commits to $\Delta^{*}$ where $\Delta^{*} \coloneqq \Delta \oplus \epsilon$ 2) $\mathcal{S}$ uses $\Delta$ for the OT extension, computing keys $(k_0, k_1) := (\mathsf{H}(q_0), \mathsf{H}(q_0 \oplus \Delta))$ 3) $\mathcal{S}$ sends messages $(m_0, m_1)$, first encrypting them $(C_0, C_1) \coloneqq (k_0 \oplus m_0, k_1 \oplus m_1)$ 4) $\mathcal{S}$ opens $\Delta^{*}$ to $\mathcal{R}$

Now the consistency check:

The setup can vary slightly depending on $\mathcal{R}$ extension choice bit $c$. In both cases $\mathcal{R}$ receives the expected messages $(m^{*}_0, m^{*}_1)$ from the outer context to use in the check. We must assume these messages are known and potentially chosen by $\mathcal{S}$.

If $c = 0$, $\mathcal{R}$ received $q_0$ during the extension setup, computing $k_0 = \mathsf{H}(q_0)$. $\mathcal{R}$ now also computes $k^{*}_1 = \mathsf{H}(q_0 \oplus \Delta^{*})$ then asserts:

$$ (k_0 \oplus m_0, k_1 \oplus m_1) \overset{?}{=} (k_0 \oplus m^{*}_0, k^{*}_1 \oplus m^{*}_1) $$

If $c = 1$, $\mathcal{R}$ received $q_0 \oplus \Delta$ during the extension setup, computing $k_1 = \mathsf{H}(q_0 \oplus \Delta)$. $\mathcal{R}$ now computes $k^{*}_0 = \mathsf{H}(q_0 \oplus \Delta \oplus \Delta^{*}) \equiv \mathsf{H}(q_0 \oplus \epsilon)$ then asserts:

$$ (k_0 \oplus m_0, k_1 \oplus m_1) \overset{?}{=} (k^{*}_0 \oplus m^{*}_0, k_1 \oplus m^{*}_1) $$

Attack

$\mathcal{S}$ can cheat with probability $1 \over 2$ by guessing $c$ and adjusting their messages accordingly.

When $c = 0$, set $m_1 = k_1 \oplus k^{*}_1 \oplus m^{*}_1$

When $c = 1$, set $m_0 = k_0 \oplus k^{*}_0 \oplus m^{*}_0$

Solution

We can address this by generating extra OTs and sacrificing them for this check... which we already do for the KOS check!

However, I'm not going to dive down that route right now. For now it will suffice to rerun the entire OT extension from setup, but remove the present redundancy.

[sinui0]

An alternative would be to implement committed/verifiable OT for the base OT. That way the Sender could prove $\Delta$ without having to do a more complicated consistency check using sacrificial OTs

[sinui0]

Committed OT for CO15

We can implement committed OT for CO15 fairly easily

1) $\mathcal{R}$ commits to their private keys $b_i$ where $0 \leq i \le n$, in our case $n = 128$ 2) $\mathcal{R}$ makes their choices $c_i$ as usual, where $\Delta = c_0 || ci || .. c{n-1}$ 3) $\mathcal{S}$ records all $B_i$ sent by $\mathcal{R}$

Later

4) $\mathcal{R}$ opens all keys $b_i$ to $\mathcal{S}$ and sends their purported choices $\Delta^{*}$ 5) $\mathcal{S}$ checks against their tape:

$$ \forall i: B_i \overset{?}{=} \begin{cases} g^{b_i} &\text{if } c^{*}_i = 0 \ Ag^{b_i} &\text{if } c^{*}_i = 1 \end{cases} $$

[sinui0]

37 Closes this