Return to Answer

No, we can't verify the relation $x = x_1+\cdots+x_n$ in less than $\mathcal O(n)$ operations. This holds even with some of the work offloaded to an helper, unless we trust them.

Argument (without a helper): changing any $x_i$ or $x$ to another value breaks (or makes) the equality, therefore each of the $n$ inputs $x_i$ must be taken into account (in full to prove equality, at least in part to disprove it), thus cost is at least $\mathcal O(n)$.

We can offload the work to some helper and discount the work they perform. It's trivial if we trust that helper: we just rely on their say, and have constant work. It's also possible if we don't trust them, but in that case, we still need to perform $\mathcal O(n)$ operations ourselves.

Argument (with an helper that we don't trust): Consider any public protocol attempting to allow what's asked. A rogue helper can randomly pick a $j\in\{1,\cdots,n\}$. If they try to make us believe in equality when it does not hold, they compute $x'_j=x+x_j-\sum x_j$, otherwise they pick any $x'_j\ne x_j$. Then they perform whatever the protocol requires as if the data set contained that $x'_j\ne x_j$ instead of $x_j$. The protocol can't allow use to detect their cheating unless it processes on our side the particular value $x_j$. Thus for constant residual probability $p$ of not detecting inequality, the protocol needs to process on our side as least $\lceil(1-p)\,n\rceil$ among the $n$ inputs $x_i$ (at least in part), thus cost is at least $\mathcal O(n)$ operations.

Note: I'm not claiming that my operations are group operations.

No, we can't verify the relation $x = x_1+\cdots+x_n$ in less than $\mathcal O(n)$ operations. This holds even with some of the work offloaded to an helper, unless we trust them.

Argument (without a helper): changing any $x_i$ or $x$ to another value breaks (or makes) the equality, therefore each of the $n$ inputs $x_i$ must be taken into account (in full to prove equality, at least in part to disprove it), thus cost is at least $\mathcal O(n)$.

We can offload the work to some helper and discount the work they perform. It's trivial if we trust that helper: we just rely on their say, and have constant work. It's also possible if we don't trust them, but in that case, we still need to perform $\mathcal O(n)$ operations ourselves.

Detailed argument (with an helper that we don't trust): Consider any public protocol attempting to allow what's asked. A rogue helper can randomly pick a $j\in\{1,\cdots,n\}$. If they try to make us believe in equality when it does not hold, they compute $x'_j=x+x_j-\sum x_j$, otherwise they pick any $x'_j\ne x_j$. Then they perform whatever the protocol requires as if the data set contained that $x'_j\ne x_j$ instead of $x_j$. The protocol can't allow us to detect their cheating unless it processes on our side the particular value $x_j$. Thus for constant residual probability $p$ of not detecting inequality, the protocol needs to process on our side as least $\lceil(1-p)\,n\rceil$ among the $n$ inputs $x_i$ (at least in part), thus cost is at least $\mathcal O(n)$ operations.

Note: I'm not claiming that my operations are group operations.

No, we can't verify the relation $x = x_1+\cdots+x_n$ in less than $\mathcal O(n)$ operations. This holds even with some of the work offloaded to an helper, unless we trust them.

Argument (without a helper): changing any $x_i$ or $x$ to another value breaks (or makes) the equality, therefore each of the $n$ inputs $x_i$ must be taken into account (in full to prove equality, at least in part to disprove it), thus cost is at least $\mathcal O(n)$.

We can offload the work to some helper and discount the work they perform. It's trivial if we trust that helper: we just rely on their say, and have constant work. It's also possible if we don't trust them, but in that case, we still need to perform $\mathcal O(n)$ work ourselves.

Argument (with an helper that we don't trust): a rogue helper can randomly pick a $j\in\{1,\cdots,n\}$. If they try to make us believe in equality when it does not hold, they compute $x'_j=x+x_j-\sum x_j$, otherwise they pick any $x'_j\ne x_j$. Then they perform whatever the protocol required as if the data set contained that $x'_j\ne x_j$ instead of $x_j$. We can't detect their cheating unless we consider the particular value $x_j$. Thus for constant residual probability $p$ of not detecting inequality, we need to process as least $\lceil(1-p)\,n\rceil$ among the $n$ inputs $x_i$ (at least in part), thus cost is at least $\mathcal O(n)$.

No, we can't verify the relation $x = x_1+\cdots+x_n$ in less than $\mathcal O(n)$ operations. This holds even with some of the work offloaded to an helper, unless we trust them.

Argument (without a helper): changing any $x_i$ or $x$ to another value breaks (or makes) the equality, therefore each of the $n$ inputs $x_i$ must be taken into account (in full to prove equality, at least in part to disprove it), thus cost is at least $\mathcal O(n)$.

We can offload the work to some helper and discount the work they perform. It's trivial if we trust that helper: we just rely on their say, and have constant work. It's also possible if we don't trust them, but in that case, we still need to perform $\mathcal O(n)$ operations ourselves.

Argument (with an helper that we don't trust): Consider any public protocol attempting to allow what's asked. A rogue helper can randomly pick a $j\in\{1,\cdots,n\}$. If they try to make us believe in equality when it does not hold, they compute $x'_j=x+x_j-\sum x_j$, otherwise they pick any $x'_j\ne x_j$. Then they perform whatever the protocol requires as if the data set contained that $x'_j\ne x_j$ instead of $x_j$. The protocol can't allow use to detect their cheating unless it processes on our side the particular value $x_j$. Thus for constant residual probability $p$ of not detecting inequality, the protocol needs to process on our side as least $\lceil(1-p)\,n\rceil$ among the $n$ inputs $x_i$ (at least in part), thus cost is at least $\mathcal O(n)$ operations.

Note: I'm not claiming that my operations are group operations.

No, we can't verify the relation $x = x_1+\cdots+x_n$ in less than $\mathcal O(n)$ operations. This holds even with some of the work offloaded to an helper, unless we trust them.

Argument (without a helper): changing any $x_i$ or $x$ to another value breaks (or makes) the equality, therefore each of the $n$ inputs $x_i$ must be taken into account (in full to prove equality, at least in part to disprove it), thus cost is at least $\mathcal O(n)$.

We can offload the work to some helper and discount the work they perform. It's trivial if we trust that helper: we just rely on their say, and have constant work. It's also possible if we don't trust them, but in that case, we still need to perform $\mathcal O(n)$ work ourselves.

Argument (with an helper that we don't trust): whatever the protocol used, the rogue helper could randomly pick a $j\in\{1,\cdots,n\}$, alter $x_j$ into a different $x'_j$ (if they try to make us believe in equality when it does not hold, they compute $x'_j=x+x_j-\sum x_j\,$ ), and perform as if the data set contained $x'_j$ instead of $x_j$. We can't detect their cheating unless we consider the particular $x_j$. Thus for constant residual probability $p$ of not detecting inequality, we need to process as least $\lceil(1-p)\,n\rceil$ among the $n$ inputs $x_i$ (at least in part), thus cost is at least $\mathcal O(n)$.

No, we can't verify the relation $x = x_1+\cdots+x_n$ in less than $\mathcal O(n)$ operations. This holds even with some of the work offloaded to an helper, unless we trust them.

Argument (without a helper): changing any $x_i$ or $x$ to another value breaks (or makes) the equality, therefore each of the $n$ inputs $x_i$ must be taken into account (in full to prove equality, at least in part to disprove it), thus cost is at least $\mathcal O(n)$.

We can offload the work to some helper and discount the work they perform. It's trivial if we trust that helper: we just rely on their say, and have constant work. It's also possible if we don't trust them, but in that case, we still need to perform $\mathcal O(n)$ work ourselves.

Argument (with an helper that we don't trust): a rogue helper can randomly pick a $j\in\{1,\cdots,n\}$. If they try to make us believe in equality when it does not hold, they compute $x'_j=x+x_j-\sum x_j$, otherwise they pick any $x'_j\ne x_j$. Then they perform whatever the protocol required as if the data set contained that $x'_j\ne x_j$ instead of $x_j$. We can't detect their cheating unless we consider the particular value $x_j$. Thus for constant residual probability $p$ of not detecting inequality, we need to process as least $\lceil(1-p)\,n\rceil$ among the $n$ inputs $x_i$ (at least in part), thus cost is at least $\mathcal O(n)$.