"shared" variant of 1-out-of-N oblivious transfer

Question

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?

Answer 1

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).

Answer 2

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)$.