大域上安全椭圆曲线子群的构造

Question

如何在更大的有限域上，包括素数\Bbb F_p上，从椭圆曲线中构造出密码学兴趣的椭圆曲线子群？离散对数问题及其相关问题需要\mathcal O(\sqrt q)域运算，其中q是子群的阶数，这是必须知道的。

动机:在Schnorr签名中，具有与施诺尔(子)群)类似的特性，但对NFS和索引演算具有抵抗能力，而不考虑p的选择；但仍然使用参数p来稍微调整实地操作的成本，以便在给定的组/签名大小下提高对ASIC和可用于密码分析的假想量子计算机的安全性。

满足这一需要的一种方法是对p和q (p大得多)按比特大小进行参数化的随机生成过程，产生素数p和q，以及场\Bbb F_p上的椭圆曲线组方程，该方程的阶数为q，并假定了D13的硬度。

对于给定大小的q，我更关心安全性，以及签名验证器端(其中侧通道是非问题)实现的简单性，而不是速度，以及使用私钥进行安全(抗侧通道)实现的容易程度。

我设想了一个192到512位的q，用于96到256位的猜测安全性(在\Bbb F_p中的实地操作中计算)，p是这个大小的几倍(至少两倍)。

Answer 1

Hasse定理注意到，对于有限域上具有\mathcal{Q}元素的椭圆曲线(这意味着具有N点的素数域\mathbb{F}_p的\mathcal{Q}=p )，如下所示：

|N-(\mathcal{Q}+1)|\le 2 \sqrt{\mathcal{Q}}

为了举例说明，让我们以\mathcal{Q}=p=8191为例。这给了我们|N-(8191+1)| \le 2\sqrt{8191}，导致了这一系列可能的点数(四舍五入)：8011 \le N \le 8373。由于这给出了点数的硬下界和上界，很明显，在一个大域上的质数曲线是不可能的，它的约束条件是曲线q的阶数明显小于场素数p。

因此，你需要忽略素数阶曲线，而是有一个很大的群\ell和一个由协因子h给出的小得多的素数子群。与标准的Pollard 大系数的最坏情况影响攻击相比，\sqrt{h}的攻击只能加速D14的一个因素--但这主要集中在大群\ell上，而不是辅助因素本身。由于\ell是“辅助性因素”，而真正的主要群体是通常被认为是辅助性因素，事情似乎变得毛茸茸的，它们的实际影响也不清楚。

即使这是一个可以接受的风险，Igor E.Shparlinksi和Andrew V.Sutherland，“寻找具有指定大小的子群的椭圆曲线”，2017年年也给出了一个非常密集的轮廓，说明一个算法在预先确定的范围内寻找带有辅助因子的曲线可能是什么样子。即使如此，对于足够大的p，对于\mathbb{F}_p (假设您处于p的2048位范围内)，该算法的运行速度非常慢，也就是说，mp^{1/2+o(1)}很可能不切实际。