# Non-interactive proof showing the multiplication of an encrypted matrix with a public vector is as claimed

Consider a "fantasy sports" setting where $$m$$ contestants each pick $$k$$ players from a set of $$n$$ players before a game. The state can be represented by a Boolean matrix $$\mathbf{A}$$ of size $$m \times n$$ where each row has exactly $$k$$ non-zero entries with the $$i$$-th row being the subset of $$n$$ players picked by the $$i$$-th contestant.

After the match is played, each of the $$n$$ players get a score in $$\mathbb{R}$$ representing their performance. Let $$\mathbf{v} \in \mathbb{R}^n$$ be this score vector. The winner of the fantasy sports is the contestant with the highest subset-score where the subset-score is the sum of scores of the players picked in the subset. That is, the winner is given by $$\underset{i\in [m]}{\operatorname{argmax}} \mathbf{A} \cdot \mathbf{v}$$.

Suppose we want to determine the winner and convince every contestant that the winner is as claimed without revealing contestants inputs, how can we do that?

I am thinking this in the context of Ethereum blockchain, assume there is one trusted (centralized off-chain) organizer Bob, and looking for practical implementable solutions.

My partial attempt is as follows. Assume contestants are $$a_1, \ldots, a_m$$.

1. Each contestant $$a_i$$ sends their input $$\mathbf{A}_i$$ to Bob.
2. Bob generates a random nonce $$z_i$$, computes a hash $$h_i = h(\mathbf{A}_i \circ z_i)$$, sends $$z_i$$ to $$a_i$$, and publishes $$h_i$$ on chain. Note one can think of the values $$h_1, \ldots, h_m$$ as encrypted version of matrix $$\mathbf{A}$$.
3. Each contestant can verify that Bob committed their value correctly on chain.
4. Once the match is played, everyone knows $$\mathbf{v}$$, it is essentially public.
5. Bob computes the matrix vector product $$\mathbf{r} = \mathbf{A} \cdot \mathbf{v}$$ and publishes this product on chain.
6. Bob publishes a "proof" so that each $$a_i$$ can verify that the published result $$\mathbf{r}$$ is indeed computed correctly as claimed by only examining everything that is published so far: $$h_1, \ldots, h_m$$, $$\mathbf{v}$$, and this "proof".

How do I accomplish Step (6) above?

• If you wish to keep $A$ secret, then I fear that step #5 may leak information. In particular, for each row in $A$, you can just test all $n^k$ possibilities and see which one lines up with the corresponding entry in the result vector $r$. For cases where $k$ and/or $n$ are small, this may be a non-trivially exploitable flaw.
– mhum
Oct 10, 2022 at 23:17
• Agree step #5 does leak information about A but wondering if the problem can be solved ignoring this issue. Later maybe a better framing would be how to output a ranked list in a zero knowledge way.... Oct 11, 2022 at 0:20