学习

门限密码

安全性要求以及实现

Posted by Keeno on October 13, 2019

门限密码的安全性要求以及实现

需要实现的安全性要求

  1. 每个人对消息使用自己的私钥份额解密密文得到解密份额，$t$个”解密份额”即可恢复整个明文，而已知任何少于$t$份”解密份额”均不能获得整个明文的任何信息。

  2. 已知解密份额也无法获得关于主私钥和私钥份额的任何信息。

    为了检验秘密分散管理系统中的欺骗着的问题

  3. 每个成员能够检验密文的有效性。

  4. 每个成员应该都能检验自己的密钥份额的有效性。

  5. 解密份额的有效性可以被检测，即成员中的欺骗者可以被识别。

    [BZ03]论文中提出一个门限密码方案，是基于在椭圆曲线上使用双线性映射构造的GDH群实现的。

  • 介绍GDP群之前，需要先介绍一下DDH问题和CDH问题

  • DDH问题

    Decision Diffie-Hellman（DDH）假设是关于涉及循环群中离散对数的某个问题的计算难度假设。 它被用作证明许多加密协议（特别是ElGamal、Cramer-Shoup密码系统）安全性的基础。

    对于一个q阶的乘法循环群G,具有一个素数生成元g。DDH问题是指，均匀地随机选取$a, b,c \in \mathbb{Z}_{q}$，给定$(g,g^a,g^b,g^c)$，判定$g^{ab}=g^c$。

  • CDH问题

    对于一个q阶的乘法循环群G,具有一个素数生成元g。CDH问题是指，均匀地随机选取$a, b,c \in \mathbb{Z}_{q}$，给定$(g,g^a,g^b)$，计算$g^{ab}$。

    这两个是相关的问题，不同的是，CDH问题比DDH问题的假设更弱，CDH问题要求我们能够计算离散对数，从$g^a$中求出离散对数$a$来解决，而DDH问题只需要我们判别值是否相等。

  • 一个群G被称为GDP群是指， 在这个群中，存在一个有效的算法来解决DDH问题，但是没有多项式时间内的算法来解决CDH问题，可以通过有限域上的超椭圆曲线的双线性映射来构造一个GDH群。

    双线性映射

    定义：一个双线性映射是由两个向量空间上的元素，生成第三个向量空间上一个元素之函数，并且该函数对每个参数都是线性的

    素数双线性群可以由五元组$(p,G_1,G_2,G_T,e)$来描述。五元组中$p$是一个与给定安全常数$\lambda$相关的大素数，$G_1,G_2,G_T$均是阶为$p$的乘法循环群，$e$为双线性映射$e:G_1×G_2→G_T$，它满足以下3个条件：

    双线性（Bilinearity）：对于任意的$g∈G_1$，$h∈G_2$，$a,b∈Z_p$，有$e(g^a,h^b)=e(g,h)^{ab}$；

    非退化性（Non-degeneracy）：至少存在元素$g_1 \in G_1$,$g2\in G_2$，满足$e(g_1,g_2)≠1$；

    可计算性（Efficiency）：对于任意的$u\in G_1$,$v\in G_2$，存在一个与给定安全常数$\lambda$相关的多项式时间算法，可以高效地计算$e(u,v)$。

    椭圆曲线上的双线性映射可由有限域上的超椭圆曲线的Weil对或Tate对来构造。

    椭圆曲线的介绍

    • 实数上的椭圆曲线是在射影平面（射影平面就是对普通平面直角坐标系的扩展，是一种能够表示无穷远点的平面坐标系）上满足Weierstrass方程$Y^{2} Z+a_{1} X Y Z+a_{3} Y Z^{2}=X^{3}+a_{2} X^{2} Z+a_{4} X Z^{2}+a_{6} Z^{3}$的曲线。

    • 椭圆曲线上有一个无穷远点$O(0:1:0)$,普通平面直角坐标系上求出椭圆曲线上所有平常点组成的曲线方程再加上无穷远点O，就构成了椭圆曲线，简化后得到$E: y^{2}=x^{3}+a x+b$其中有两个变量，一个度数为2，一个度数为3。

    • 椭圆曲线同时需要是非奇异的，即满足$\Delta=-16\left(4 a^{3}+27 b^{2}\right)≠0$。判别式用来判别E是否有重根，即曲线上的所有点都没有两个或两个以上不同的切线。

    • 椭圆曲线的图形化表示例子

      ellipse

    • 椭圆曲线上的加法

      定义椭圆曲线的加法阿贝尔群（满足封闭性、结合性、单位元、逆元、交换性），任意取椭圆曲线上两点P、Q（若P、Q两点重合，则作P点的切线），作直线交于椭圆曲线的另一点$R’$，过$R’$做$y$轴的平行线交于$R$，定义$P+Q=R$。这样，加法的和也在椭圆曲线上，并同样具备加法的交换律、结合律。

      根据这个法则，可以知道椭圆曲线无穷远点$O∞$与椭圆曲线上一点$P$的连线交于$P’$，过$P’$作$y$轴的平行线交于$P$，所以有无穷远点 $O∞+ P = P$ 。这样，无穷远点$O∞$的作用与普通加法中零的作用相当，我们把无穷远点$O∞$ 称为零元。同时我们把$P’$称为$P$的负元。

    • $k$个相同的点$P$相加，我们记作$kP$。如下图：$P+P+P = 2P+P = 3P$。

    • 密码学上应用椭圆曲线

      实数域上的椭圆曲线是连续的，并不适合加密，所以必须把椭圆曲线变成离散的点。因此要把椭圆曲线定义在有限域$\mathbb{F}_ {q}$（由$q$个元素$ { 0, \dots ,q-1 }$组成的域，在有限域上的加减乘除法则都是在$mod\ q$下的）上。

      $E\left(\mathbb{F}_ {23}\right)$：$E=y^2=x^3+x+1$是有限域$\mathbb{F}_ {23}$上的一个椭圆曲线

      无限远点$O∞$为零元

      对于E上的点$P\left(x_{1}, y_{1}\right)$,$Q\left(x_{2}, y_{2}\right)$,$R\left(x_{3}, y_{3}\right)$，有$P+Q=R$：

      $x_{3} \equiv k^{2}-x_{1}-x_{2} \quad(\bmod p)$

      $y_{3} \equiv k\left(x_{1}-x_{3}\right)-y_{1} \quad(\bmod p)$

      若$P=Q$，则$k=\frac{3 x_{1}^{2}+a}{2 y_{1}} \quad(\bmod p)$

      若$P≠Q$，则$k=\frac{y_{2}-y_{1}}{x_{2}-x_{1}} \quad(\bmod p)$

      如果椭圆曲线上一点$P$，存在最小的正整数$n$，使得数乘$n P=O∞$，则将$n$称为点$P$的阶，也称$P$为$n-torsion$点。

    • 椭圆曲线加密

    考虑$K=kG$，其中$K、G$为椭圆曲线$E_q(a,b)$上的点，$n$为$G$的阶($n G=O_{\infty}$)，$k$为小于$n$的整数。则给定$k$和$G$，根据加法法则，计算$K$很容易但反过来，给定$K$和$G$，求$k$就非常困难。因为实际使用中的ECC原则上把$q$取得相当大，$n$也相当大，采用穷举法求出$k$是不可行的。这就是椭圆曲线加密算法的数学依据。

    • 优点
      1. 安全性更高
      2. 160位ECC与1024位RSA、DSA有相同的安全强度
      3. 处理速度更快
      4. 在私钥的处理速度上，ECC远 比RSA、DSA快得多
      5. 带宽要求更低
      6. 存储空间更小
      7. ECC的密钥尺寸和系统参数与RSA、DSA相比要小得多
    • 椭圆曲线上的映射是什么：(Weil配对/Tate配对的定义)

    定义$p$为一个素数，E为定义在$\mathbb{F}_ p$上的椭圆曲线。令$E[q]$为E的q-扭点所组成的子群。椭圆曲线上的映射$e$是指：

    $e:E[q] \times E[q] \rightarrow \mathbb{F}_ {p^{k}}^{* }$

    将$E[q]$上的一对点${P,Q} \in E[q]$，映射到一个扩展域$F_{p^k}$上的$r$阶单位根组成的子群里的一个元素，$k$满足$q | p^k-1$，扩展域恰好包含$r^2$个点，满足双线性性质：

    Identity：对于所有$R \in E[q]$，有$e(R,R)=1$。

    Bilinear：对于所有$R_1,R_2 \in E[q]$，$a, b \in \mathbb{Z}$，有$e(aR_1,bR_2)=e(R_1,R_2)^{ab}$。

    Non-degenerate：有$R \in E[q]$， 如果对$R^{\prime} \in E[q]$，存在$e(R,R^{\prime})=1$，则有$R=\mathcal{O}$。

    Computable：对于所有$R_1,R_2 \in E[q]$，$e(R_1,R_2)$是容易计算的。

    然而根据双线性配对的已知特性(非退化性)，不足以证明当$P$是同一个扭点时，满足$e(P,P) ≠1$，在Weil配对中，根据Weil配对的定义，$e(P,P)$始终等于1，不能够解决DDH问题。因此需要构造一个具有强非退化性的配对，来实现对称双线性映射。

  • 椭圆曲线上对称双线性映射的定义：

    当$G_1 = G_2=G$时，对于一个双线性映射$e:G×G→G_T$,$G$上的一个扭点$P$满足：

    非退化性：$e(P,P)≠1$

    双线性：对于任意的$a,b∈Z_p$,有$e(aP,bP)=e(P,P)^{ab}$

上述称为一个对称双线性映射，利用对称双线性映射的性质， DDH问题能够被解决，CDH问题依旧困难，也就构造出来一个GDH群。

由于在Weil配对中，因为Weil配对只满足$P,Q∈G$时的非退化性，因此Verheul在论文中引入某些特殊的内同态，他称为失真，对Weil和Tate的配对进行修改，得到了一种满足对称双线性映射的方案。具体就是定义一个失真映射(distortion map)：$\Psi(x, y)=(-x, i y)$。即是将$E\left(\mathbb{F}_ {q}\right)$上的点映射为一个扩展域$E\left(\mathbb{F}_ {q^{2}}\right) \backslash E\left(\mathbb{F}_ {q}\right)$上的点，从而有$(P, \Phi(P)) \neq 1$。

为了抵抗选择密文攻击，门限密码方案需要实现公开可验证性，在解密服务器解密时，对密文进行验证，以及在$Compiler$组合解密份额恢复明文时，能够对解密份额$U_i$进行验证。

  • 因此提出了一种基于GDH群困难问题的门限密码方案，通过GDH群的性质在方案中来实现门限密码方案中，解密份额以及密文的验证。

  • 方案是基于在椭圆曲线上使用双线性映射来构造的GDH群，因此需要在一个适合的椭圆曲线上构造一个具有强非退化性的配对，实现GDH群的性质。采用的方案是pbc库提供的Type a配对方案，是在有限域$\mathbb{F}_ {q}$上满足Weierstrass方程$y^2 = x^3 + x$的一个超奇异椭圆曲线(#$E(\mathbb{F}_ {q})=q+1$)上构造的双线性映射。输入是，输出是

  • 因此Type a中的方案，就是通过修改后的Tate对，构造了一个椭圆曲线上的双线性映射，实现了GDH的性质。

    论文中的门限密码方案

  • 假设和定义:

    1. 假设一个$q$阶的GDH群$\mathcal{G}$，并将生成元$P$分享给所有参与者

    2. 定义两个随机谕言机$\mathrm{G}$,$\mathrm{H}$：

      $\mathrm{G}: \mathcal{G} \rightarrow{0,1}^{l}$

      $\mathrm{H}: \mathcal{G} \times{0,1}^{l} \rightarrow \mathcal{G}$

  • 具体方案如下：

  1. $\mathrm{K}(k, n, t)$：

    输入：安全参数$k$，参与协议的解密服务器数$n$，门限参数$t$，算法从$\mathbb{Z}_ {q}^{* }$中均匀随机地选取$a_{0}, a_{1}, \dots, a_{t-1}$，定义一 个多项式$\operatorname{Poly}(X)=\sum_{j=0}^{t-1} a_{j} X^{j}$。对$0 \leq i \leq n$，计算$x_{i}=Poly(i) \in \mathbb{Z}_ {q}^{* }$， $Y_{i}=x_ {i} P$，$x \stackrel{\text { def }}{=} a_ {0}=\operatorname{Poly}(0)$，$Y \stackrel{\text { def }}{=} Y_{0}=x P$。

    输出：公钥$p k=Y$，验证密钥$v k=\left(p k, Y_{1}, Y_{2}, \dots, Y_{n}\right)$。

    私钥$\mathbf{sk}={sk_{i}}={(pk, i, x_{i})}$分发给对应参与者$1 \leq i \leq n$。

  2. $E_{pk}(m)$：

    输入：明文$m \in {0,1}^n$，$r \in \mathbb{Z}_ {q}^{* }$，计算：$U=r P, V=\mathrm{G}(r Y) \oplus m \text { and } W=r \mathrm{H}(U, V)$

    输出：密文$C=(U,V,W)$

  3. $\mathrm{D}_ {s k_{i}}(C)$：

    输入：密文$C$，计算$H=\mathrm{H}(U, V)$，检查密文$C$的有效性$\hat{e}(P, W)=\hat{e}(U, H)$，若满足条件，计算$U_{i}=x_{i} U$。

    输出：$D_{i}=\left(i, U_{i}\right)$或$D_{i}=\left(i, ?\right)$。

  4. $\mathrm{V}_ {v k}\left(C, D_{i},vk \right)$：

    输入：密文$C$，解密份额$D_i$，验证密钥$vk$。首先计算$H=\mathrm{H}(U, V)$，检查密文$C$的有效性$\hat{e}(P, W)=\hat{e}(U, H)$，若满足条件，则继续验证解密份额：

    通过$Y_i$，判定$\hat{e}\left(P, U_{i}\right)=\hat{e}\left(U, Y_{i}\right)$，若成立，则说明是正确的解密份额

    输出：$valid$（验证都通过），$invalid$（验证存在失败）

  5. $\mathrm{SC}_ {vk}(C,{D_{i}}_ {i \in \Phi})$：

    输入：密文$C$，$t$个人提交的解密份额$D_i$。若对于所有的$D_i$，满足$\mathrm{V}_ {v k}\left(C, D_{i},vk \right)=valid$。则计算$m=\mathrm{G}\left(\sum_{i \in \Phi} \lambda_{0 i}^{\Phi} U_{i}\right) \oplus V$。

    输出：$m$或者$?$。

  • 方案能够抵御适应性选择密文攻击、具有比较高的效率、构造简单、解密过程非交互的优势。

tag5

CATALOG
    FEATURED TAGS
    学习
    FRIENDS