面向高中生的MPC协议

Question

我在给一个高中生解释MPC。他很兴奋，问我一些例子。我唯一能想到的就是使用混淆的电路。是否有一些简单的MPC协议，例如加法，乘法，指数，最大，最小，我可以很容易地解释给一个高中生？

编辑:我对加法和平均操作有很好的反应。其他操作也有简单的协议吗？

Answer 1

这里有一个简单的加法示例，它也可以扩展到其他操作。

假设教室里有X数量的孩子，每个人的分数都在0到100之间。我们要计算所有学生的平均分数，而老师或其他学生不知道他们的同学取得了什么成绩。

以下是我们如何实现这一目标。

步骤1：

让他们每个人都把他们在一张纸上得到的分数记下来，确保没有人合谋。只有当每个人都诚实地做这件事时，这才能奏效。

第2步：

告诉每个学生选择X号码，最好把它们写在小纸片上，因为有X号码的学生，这样这些数字加起来就等于他们想保密的分数。范围可以是从-∞到+∞。

第三步:告诉每个学生将X-1比特分发给其他学生，这样每个学生最终都会得到X比特。

第四步:现在每个学生都有了X的纸张，告诉他们把他们面前的所有数字加起来，然后写下他们在黑板上得到的价值。

第五步:把所有这些数字加起来，你就会得到每个学生的平均分数。

你可以在没有人知道他们的分数的情况下计算平均值。

您可以通过实际分数的平均值进行交叉验证。

Answer 2

一个有趣的方法(以及我是如何被介绍给MPC的)可能是计算班里的平均便秘率或类似的东西，其中每个学生的便秘率在0到100之间。这可以使用一张纸上写的随机值初始化的和协议来完成。这个价值是由老师选择的；学生收到一篇论文后，就把他/她的价值加起来，把结果写在一张新的纸上，然后把它传下去。最后，发布平均值。这就要求学生们诚实地玩游戏。

它也是引入现实世界(规范)和理想世界范式的一种方式。

当我们这样做的时候，这个过程的尴尬是很可笑的。