16、椭圆曲线离散对数的量子计算

椭圆曲线离散对数的量子计算

椭圆曲线密码系统

数字签名方案可以通过有限域 (F_q) 上的椭圆曲线或 (Z/nZ)（其中 (n = pq)，(p) 和 (q) 为素数）进行类比，就像公钥密码学那样。已经有几种椭圆曲线数字签名方案被提出。

Menezes - Vanstone ECC

之前提到的椭圆曲线密码系统存在一个严重问题，即明文消息单元 (m) 需位于椭圆曲线上 (E)，但目前没有方便的确定性方法来生成这样的点。幸运的是，Menezes 和 Vanstone 发现了一种更高效的变体。在这种变体中，椭圆曲线用于“掩码”，明文和密文对可以位于 (F_p^\times F_p^) 中，而不是椭圆曲线上。

• 密钥生成：Alice 和 Bob 公开选择一个 (F_p) 上的椭圆曲线 (E)（(p > 3) 为素数）和一个随机基点 (P\in E(F_p))，使得 (P) 生成 (E(F_p)) 的一个大子群 (H)，最好 (H) 的大小与 (E(F_p)) 本身相同。假设随机选择的 (k\in Z_{|H|}) 和 (a\in N) 是秘密的。
• 加密：假设 Alice 想向 Bob 发送消息 (m = (m_1, m_2)\in (Z/pZ)^\times (Z/pZ)^)，她进行以下操作：
  1. (\beta = aP)，其中 (P) 和 (\beta) 是公开的。
  2. ((y_1, y_2) = k\beta)。