椭圆曲线密码在多方安全计算中的应用

为了行文逻辑的连续性，这里我重提一些椭圆曲线密码[1]的基本知识。

椭圆曲线上的基本运算

在密码学中使用的椭圆曲线一般是定义在素数域 或2的扩域 上。这里为了介绍方便，我规定椭圆曲线都是定义在素数域上的，记作 ，并将曲线上的点个数记为 。

椭圆曲线的基本运算是标量乘(scalar multiplication)，即给定 计算 。标量乘可以由Double-and-add算法或者一些更优化的算法实现，这里我不在赘述，读者可以参考这里[2]获得细节内容。简而言之，标量乘的计算复杂度为 次 乘法。

椭圆曲线上的离散对数问题

椭圆曲线密码的安全性来源于椭圆曲线上的离散对数问题(Elliptic Curve Discrete Log Problem, ECDLP)。

ECDLP就是椭圆曲线版本的DLP（Discrete Log Problem, DLP）, 定义如下[3]：

• 给定椭圆曲线 上的两个点 , 寻找这样的一个整数 ，使得 。

解决ECDLP是一个艰深的数学难题，目前学界已知的最有效方法包括Baby-step giant-step,Pollard's rho algorithm，Index calculus等[4]，然后这些方法都不能在多项式时间内解决问题，它们的计算复杂度都不超过 ，这里 是选定的椭圆曲线 上的点的个数， 即 。

另外注意到给定一条椭圆曲线，确定它上面的点个数 是非常耗时的，因此密码学使用的都是事先选定的，已经知晓点个数的椭圆曲线。Hasse定理[5]阐明了椭圆曲线的点个数和所在素数域有下面的关系： 。 

简而言之，我们有 ，如果我们希望ECDLP有128-bit安全级别，那么应当选取 即 。

椭圆曲线上的Diffie-Hellman假设

Diffie-Hellman假设[6]在椭圆曲线上也是成立的，它包含了两个方面的内容，即计算性的Diffie-Hellman假设和判定性的Diffie-Hellman假设。

计算性的Diffie-Hellman假设(Elliptic Curve Computational Diffie-Hellman Assumption, EC-CDH)定义如下：

• 给定 , 计算 是困难的。 

目前已知解决EC-CDH的方法是基于ECDLP的，因此EC-CDH的困难程度得到了保障。

判定性的Diffie-Hellman假设(Elliptic Curve Decisional Diffie-Hellman Assumption, EC-DDH)定义如下：

• 给定 , 判定 是否成立。 

EC-DDH是一个比EC-DLP更强的(stronger)困难假设：如果我们可以有效地解决EC-DLP, 那么解决EC-DDH是显然的；但同时注意到存在一些椭圆曲线, 使得EC-DDH是一个容易解决的问题。因此在使用EC-DDH时，我们应该特别小心选择合适的椭圆曲线确保EC-DDH确实是困难的。

隐私求交（Private Set Intersection, PSI) [7][8]是一个非常重要的多方安全计算问题，它在计算方Client和计算法Server之间完成求交集的运算，并且不泄露除了交集本身以外的其他任何信息。借助EC-DDH我们可以构造如下图所示的隐私求交协议：

ECDDH-based PSI Protocol

这里，函数 将集合中的元素映射到椭圆曲线上的相应点。首先Client生成随机数 且对集合 中的每一个元素 都做一次椭圆曲线标量乘运算 ，记作 并发送给Server; 接着Server生成随机数 且对集合 进行标量乘运算得到 , 对集合 进行标量乘运算得到 ,并发送给Client。Client拿到 后对 做标量乘运算得到 , 最终通过比较 确定交集 。

协议的正确性是显然的。下面我借助模拟器概念[9]证明上图的PSI协议确实是安全的(passive security, semi-honest security)。

首先假定Server被敌手控制(Server is corrupted), 那么从Server的视角来看，它仅仅看到了Client发送过来的 ，又因为 是随机的，那么 一定服从均匀分布；因此，Server的模拟器 是非常简单的，只需要随机生成 即可, 容易看出 。

接着假定Client被敌手控制(Client is corrupted), 从Client的视角来看，它看到了Server发送过来的 , 构造Client的模拟器 如下：随机生成 并使用 模拟 , 因为ECDDH假设的缘故，容易看出 ; 接着准备集合 , 这里 表示交集 , 表示补充生成的随机元素使得 , 接着算 用来模拟 , 又因为 是随机的，因此有 , 且 , 证毕。

参考

[1]https://en.wikipedia.org/wiki/Elliptic-curve_cryptography

[2]https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication

[3]https://eprint.iacr.org/2015/1022.pdf

[4]https://en.wikipedia.org/wiki/Discrete_logarithm

[5]https://en.wikipedia.org/wiki/Counting_points_on_elliptic_curves

[6]https://en.wikipedia.org/wiki/Decisional_Diffie%E2%80%93Hellman_assumption

[7]https://zhuanlan.zhihu.com/p/589081394

[8]https://zhuanlan.zhihu.com/p/586433710

[9]https://zhuanlan.zhihu.com/p/588114150

本文作者：hujwei

知乎链接：https://zhuanlan.zhihu.com/p/597457384