1
$\begingroup$

In the traditional 1-out-of-n OT, we suppose Alice has an array $A=\{x_1,{\cdots},x_n\}$ and Bob has $idx=i\in\{1,{\cdots},n\}$. After running the OT, Bob leans $x_i$ and nothing else, Alice learns nothing about $i$.

So, my question: is there a "shared" variant of 1-out-of-N oblivious transfer?

We consider the array and the queried index are secret-shared between Alice and Bob (e.g., additive secret sharing). That is, Alice holds the share of the array $A_{Alice}$ and the share of the queried index $idx_{Alice}$; Bob holds the share of the array $A_{Bob}$ and the queried index $idx_{Bob}$. After running the OT, Alice gets $[x_{idx}]_{Alice}$ and Bob gets $[x_{idx}]_{Bob}$, where $([x_{idx}]_{Alice}+[x_{idx}]_{Bob})modN=x_{idx}$.

Update:

Motivated by the CCS2021 paper Oblivious Linear Group Actions and Applications, in Section 5.1, they propose a protocol "Oblivious Selection" (called "shared" variant of OT) based on the permutation. But before each selection, we have to do the permutation on the array. So I proposed the above question: are there other protocols to obliviously select an element from the shared array at a shared index?

$\endgroup$
6
  • $\begingroup$ Can your question be stated as: How can Alice and Bob each commit to their own list of public keys (which they do not initially share with one another), where a list of Diffie-Hellman shared secrets would result if Alice and Bob intentionally collaborated to determine those shared secrets. Then, how can either party gain knowledge of one of those shared secrets at a specified index, without the other party discovering either the index or the shared secret at that index? $\endgroup$
    – knaccc
    May 23, 2022 at 19:19
  • $\begingroup$ @knaccc Yep! To recap the above question: in the 2PC setting, obliviously select an element from the shared array at a shared index while two parties cannot learn anything about the shared array element and index. Like warforgad said below: it's quite different from regular OT, but has similar functionality as the "shared" variant of OT. $\endgroup$
    – Dylan
    May 24, 2022 at 21:57
  • $\begingroup$ I'm confused that you just said "two parties cannot learn anything about the shared array element and index". Doesn't that mean that neither of them learn anything? Maybe you misspoke. I think I have a solution that allows one person to query and discover one of the DH secrets, without the other party learning which secret or which index has been requested. It's also impossible for one of them to cheat, because they will commit to their shares beforehand. $\endgroup$
    – knaccc
    May 24, 2022 at 22:01
  • $\begingroup$ Yes, I got it wrong. It should be: two parties cannot learn anything about the accessed element and specified index. $\endgroup$
    – Dylan
    May 24, 2022 at 22:07
  • $\begingroup$ One of the parties decides on the index and learns the shared secret at the index. I don't understand what you mean by "two parties cannot learn anything", when one of them is clearly learning something. $\endgroup$
    – knaccc
    May 24, 2022 at 22:09

2 Answers 2

1
$\begingroup$

While I wouldn't call this a shared variant of OT, your proposed functionality can indeed be implemented with a single call to 1-out-of-$(|\mathbb{F}|^n\cdot n)$ OT since OT is complete. Here $\mathbb{F}$ is the field of $A$'s entries.
First, consider a 2-party functionality where Bob receives a function $f(x,y)$, $x$ being held by Alice and $y$ by Bob. Let $a,b$ be Alice's and Bob's inputs respectively. Alice sets the array $A$ such that $A[i] = f_i(a) = f(a,i)$. They then employ an OT where Bob receives $A[b] = f_b(a) = f(a,b)$ as required.
Now to your functionality. Let Alice sample a random $r$, and consider the function $$f\left(\left(A_{Alice}, idx_{Alice}\right), \left(A_{Bob}, idx_{Bob}\right)\right) = A_{Alice}[idx_{Alice} + idx_{Bob}] + A_{Bob}[idx_{Alice} + idx_{Bob}] - r$$ I omitted the modulo for simplicity.
As described above, they use a single OT call to let Bob receive $[x_{idx}] -r$. Together with the $r$ that alice holds, they have a secret sharing of $[x_{idx}]$.
I wouldn't call this a shared OT because it's quite different. For example, Alice and Bob play a similar role while in regular OT they have distinct roles (one has an array, one chooses an entry).

$\endgroup$
1
  • $\begingroup$ You're right! It's quite different from the regular OT since Alice and Bob hold the same data (different shares). Calling the functionality a "shared" variant of OT is because I thought it obliviously selects an element from an array, kind of like OT. This functionality also appears in the paper CCS2021: oblivious linear group actions and applications. $\endgroup$
    – Dylan
    May 24, 2022 at 21:51
1
$\begingroup$

Alice picks a list of uniformly random private keys $\{a_i\}$. She calculates a list of corresponding public keys $\{A_i\}$ as $\{a_iG\}$. She then declares a list of corresponding public key hashes $\{P_i\}$ calculated as $\{hash(A_i)\}$.

$G$ is a well-known base point on the curve, and $hash()$ is a cryptographically secure hash function.

Bob does the same, so that Bob has private keys $\{b_i\}$, has public keys $\{B_i\}$, and declares public key hashes $\{Q_i\}$.

At this stage, Alice and Bob could decide to collaborate to determine the Diffie-Hellman shared secret list $\{S_i\}$ as $\{a_iB_i\}$ or $\{b_iA_i\}$. However, they do not do this.

Without loss of generality, if Alice wants to learn the shared secret at index $j$ without Bob discovering $j$ or the shared secret:

Alice picks a uniformly random blinding factor $r$, and sends $X=rA_j+jH$ to Bob. $H$ is a second well-known base point on the curve, where $h$ is not known such that $hG==H$.

Bob sends back to Alice the list $\{Z_i\}$ = $\{b_i(X-iH)\}$.

Alice can now only unblind and learn the shared secret $S_j$ by calculating $r^{-1}Z_j$. She is unable to learn anything about any other shared secret, because the $H$ component of Bob's list of responses will only cancel out at one particular index.

Since this Diffie-Hellman secret $S_j$ will be equal to $a_jB_j$, Alice can then verify that Bob's hash $Q_j$ matches by checking $Q_j\overset{?}{=}hash(a_j^{-1}S_j)$.

$\endgroup$

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.