通讯
Rectangle property
在 MPC 设定下，如果暂时不考虑 Active malicious adversary 的话，节点的私有状态 i.e. 输入和随机性可以确定性决定 Transcript 。将这一映射称为 .
具有 “Rectangle property”， 是一个 Rectangle：
可以理解成，如果有任意两个所有 Party 的私有状态集合 满足 ，那么可以把 和 任意组合（每个 Party 任意在两者中选一个），那么最终 Transcript 依旧是 。
证明把 T 当成一个消息列，归纳。
这有两个很直接的后果：
-
如果至少有 3 个 Party，那么不存在在纯广播信道上的 的计算元素和的协议。原因是如果存在，假设 Party 1 semi-honest，Fix ，注意到只要 不变，那么 Party 1 的 View 也不变。这是纯广播，因此 Transcript 不变。只要有限域大小大于 2, 总能选出来两个不同的元素 ，假设他们是 Party 2 和 Party 3 的输入，那么交换他们，Party 1 View 不变，所以把 Party 3 的输入从 改成 ，Party 1 View 依旧不变，但是结果变了，矛盾。
-
不存在 2-Party 计算 AND 的协议。如果存在， 和 都会输出 , 所以 Adversary View 相同，只有两个 Party 所以 View 包含整个 Transcript，整个 Transcript 也就相同。所以 也应该产生一样的 Transcript，但是这会产生不同的输出，矛盾。
相关历史综述见 Gemini DeepResearch。AI 幻觉有风险，4.6 Opus 就给我幻觉了几个 Ref。不过 DeepResearch 至少给链接了。
Reed-Solomon 纠错
Reed-Solomon 如果有 冗余可以纠 个错 (Also, Shamir Secret Sharing).
考虑有限域 上的 Reed-Solomon 码，共 个数据， 个冗余，总共采样点 个。现在要找出来其中最多 个错的点。
假设 Underlying polynomial 是 ，Claim 存在一个多项式 ，满足 。如果 不是错误的点，对 没有要求。因为最多 个错误，所以我们可以要求 ，并且最高次项系数为 ， 剩下 个系数未知。
对所有采样点成立。这给我们提供了 个方程，，令 ，，线性系统 一共 个方程， 个未知数，可以解出 和 ，之后 或者 Chien search. 复杂度
Alternatively, 这是一个 Rational polynomial interpolation 问题， 经过 个点。wo/ FFT 复杂度 , w/ FFT 复杂度 。（但我都不会）
TODO: 看看 Berlekamp-Massey
