Lattice based cryptosystems
hash_hash
  2022-05-06 21:39:38 2022-05-06 21:39    

Lattice based cryptosystems

LLL algorithm

算法细节

NTRU

之前就有了解过，只不过是在数域上的，理解起来较为简单，这里介绍的是环上的NTRU及其实现

加密前需选择公共参数N，p，q，d满足gcd(N,p,q)=1，q>(6d+1)p

其中N一般在250到2500之间

记R为商环，为，为

定义三值多项式

{的系数存在个个其余均为}

加密过程

随机选取多项式f(x)∈T(d+1,d)，g(x)∈T(d,d)

h(x)为公钥，为私钥

随机选择r(x)∈T(d,d)

明文多项式m(x)∈R，且其系数均在-p/2到p/2之间

密文c(x)=ph(x)·r(x)+m(x)∈

解密过程

考虑pg(x)·r(x)+f(x)·m(x)的各项系数最大不会超过(3d+1/2)p<q/2

故计算s(x)模q后提升至R上得到的是pg(x)·r(x)+f(x)·m(x)的未约化的值

=>s(x)=pg(x)·r(x)+f(x)·m(x)

计算

注意到开始对m(x)系数的约束，故我们最后能得到明文多项式m(x)

Lattice-based attacks

为了保证穷举密钥时的密钥空间，d取值约为N/3

希望通过公钥导出私钥或私钥的循环位移结果

根据

=>f(x)·h(x)=g(x)+qu(x)

设h(x)的系数为到

构造格

∵

可知向量在格L上

下面估计v的范围

||v||=

λ(L)的高斯期望为

可以看出在N较大时||v||有较大几率为最短向量

于是我们可以采用LLL或BKZ算法对NTRU的公钥进行攻击来恢复私钥

具体攻击的实现在低维度的情况下直接按上述构造LLL约化即可，高维可能需要BKZ算法才能解决

算法实现可以看看这篇文章，讲的很详细

代码实现

充分利用sage打包好的玩意

Poly

Zx.表示以x为自变量的多项式

1
2
3
4
Zx.<x>=ZZ[]
f=Zx([3,2,1])
print(f)
#x^2 + 2*x + 3

Cyclic convolution

就是上述说的模的商环

1
2
3
4
5
6
7
8
9
10
11
12
13
def convolution(f,g):
    return f*g%(x^n-1)

n=5
Zx.<x>=ZZ[]
f=Zx([1,2,3])
g=Zx([2,4,6,8])
print(f)
print(g)
print(convolution(f,g))
#3*x^2 + 2*x + 1
#8*x^3 + 6*x^2 + 4*x + 2
#34*x^4 + 32*x^3 + 20*x^2 + 8*x + 26

ps:Sage可以直接使用R=Zx.quotient(x^n-1)生成运算都在商环内的类

Modular Reduction

∵对系数的限制，在计算s(x)和a(x)后都做了模约计算，一般采用的是最小正剩余系，但这里使用的最小剩余系

1
2
3
4
5
6
7
8
9
10
def balancedmod(f,q):
    g=list((f[i]+q//2)%q-q//2 for i in range(n))
    return Zx(g)
    
Zx.<x>=ZZ[]
f=Zx([1,5,3,7,6])
print(f)
blancedmod(f,3)
#6*x^4 + 7*x^3 + 3*x^2 + 5*x + 1
#x^3 - x + 1

Random polynomials with d1+d2 nonzero coefficients

即上述d1个系数为1和d2个系数为-1其余系数为0的三值多项式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def randompoly(d1,d2):
    assert d1+d2<=n
    ans=n*[0]
    for i in range(d1):
        while True:
            r=randrange(n)
            if not ans[r]:break
        ans[r]=1
    for i in range(d2):
        while True:
            r=randrange(n)
            if not ans[r]:break
        ans[r]=-1
    return Zx(ans)

n=7
Zx.<x>=ZZ[]
randompoly(3,2)
#-x^4 + x^3 - x^2 + x + 1

Polynomial inversion

在商环下求逆

1
2
3
4
5
6
7
8
9
def invertmodprime(f,p):
    T=Zx.change_ring(Integers(p)).quotient(x^n-1)
    return Zx(lift(1/T(f)))

Zx.<x>=ZZ[]
n=5
f=x^3+3*x+2
invertmodprime(f,11)
#6*x^4 + 3*x^3 + x^2 + x + 2

ps:q不一定为素数为2的幂次也可

1
2
3
4
5
6
7
def invertmodpowerof2(f,q):
     assert q.is_power_of(2)
     g = invertmodprime(f,2)
     while True:
       r = balancedmod(convolution(g,f),q)
       if r == 1: return g
       g = balancedmod(convolution(g,2 - r),q)

NTRU密钥生成

p一般为3，d大约为N/3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def keypair():
    while True:
        try:
            f=randompoly(d+1,d)
            fp=invertmodprime(f,p)
            fq=invertmodprime(f,q)
            break
        except:
            pass
    g=randompoly(d,d)
    pk=balancedmod(p*convolution(fq,g),q)
    sk=f,fp
    return pk,sk

Zx.<x>=ZZ[]
n=11
p=3
q=13
d=4
keypair()
#(4*x^9 + 5*x^8 - 2*x^7 - x^6 - 4*x^5 - x^4 - 3*x^3 - x^2 + x + 2,(-x^10 - x^8 + x^7 + x^6 + x^5 + x^4 - x^3 - x^2 + 1,2*x^8 + 2*x^7 + 2*x^5 + x^4 + x + 2))

encrypt

1
2
3
4
5
6
7
8
9
10
11
def encrypt(m,pk):
    r=randompoly(d,d)
    return balancedmod(convolution(pk,r)+m,q)

Zx.<x>=ZZ[]
n=13
q=11
p=3
m=Zx([1,-1,1,0,1])
pk,sk=keypair()
encrypt(m,pk)

decrypt

1
2
3
4
def decrypt(c,sk):
     f,fp = sk
     a = balancedmod(convolution(c,f),q)
     return balancedmod(convolution(a,fp),p)

attack

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def attack(pk):
    inverse_p=inverse(p,q)
    pk=balancedmod(inverse_p*pk,q)
    L=Matrix(2*n,2*n)
    for i in range(n):
        L[i,i]=1
        L[i+n,i+n]=q
    for i in range(n):
        for j in range(n):
            h=convolution(x^i,pk)
            L[i,n+j]=h[j]
    L=L.LLL()
    for i in range(2*n):
        try:
            f=Zx(list(L[i][:n]))
            fp=invertmodprime(f,p)
            return (f,fp)
        except:
            pass
    return (f,f)

ps:这里我实验了一下发现n≥90时无法通过上述算法恢复私钥，需要采用其他的格约减算法

GGH

相比NTRU这个公钥系统好理解多了，实现起来也很方便

GGH是基于CVP的一个密码学方案，但是在1999年被发现在算法设计中有很大缺陷，可以泄露部分明文信息，且可将原CVP转化为一个更为简单的CVP，最终被认定是broken的

接收者选定一个优质基L，通过乘幺模矩阵转化为坏基B，将B作为公钥

加密过程

c=m×B+e

其中

  • m:明文组成的1×n向量
  • e:扰动向量(这个地方最初好像设定的是3或-3，Nguyen’s Attack可以根据这一点降低CVP难度)
  • c:密文向量

解密过程

接收者利用优质基L采用babai算法找c的最近向量v=m×B

Lattice-based attacks

通过对公钥B进行约化，找到一组优质基，再采用babai算法找c的最近向量

这里通过Nguyen’s Attack可以降低CVP的难度

可以参考这篇文章，对攻击方式做了详细推导

ps:

embeded technique也是一种有效的攻击方式，可以将CVP转化为高一个维度的SVP

具体参考这篇文章

LBH

基于格中的困难问题SIS构造的杂凑函数

算法流程

单输入LBH

函数

将需要进行摘要的信息转为向量x(坐标只能为0或1)，求出的即为x的哈希值

基于格的实现满足了哈希算法的高效性，不可逆的性质在同余下是容易实现的

所以我们更多地关注其抗碰撞性

抗碰撞性

希望能将其归约到困难问题上，即如果我们能获得高效的碰撞算法，相当于我们解决了困难问题

若存在

=>A×(x-y)=0 (mod q) (※)

∵x，y两个向量的分量取值均只能为0或1

∴x-y的分量只能为0，-1，1

这就转化为了我们熟知的SIS问题的形式

故我们能找到一组碰撞<=>找到了SIS问题的一组解

又SIS可以归约到SIVP问题上，且SIVP是困难的

至此我们就证明了LBH的抗碰撞性

关于SIS问题的更多应用可以参考这篇文章

基于格的哈希算法这的确是个很有意思的问题，但是由于很多的前置知识没学明白就只能浅显地描述该算法了，等我学会了再来补充

BFV

一个基于RLWE的全同态加密方案

加密过程

首先选取一分圆多项式，常选

构建密文空间的商环

明文空间的商环

通过私钥采样生成私钥s，往往选择离散高斯分布

随机分布中采样得，噪声分布中采样e，计算，公钥为

对于明文M，先将其编码到记为m，从私钥分布中采样u，从噪声分布中采样

计算

密文即为

解密过程

只需即可正常解密，此处与其编码规则有关，通过取整系数的项来获得明文多项式

  • Post title：Lattice based cryptosystems
  • Post author：hash_hash
  • Create time：2022-05-06 21:39:38
  • Post link：https://hash-hash.github.io/2022/05/06/Lattice-based-cryptosystems/
  • Copyright Notice：All articles in this blog are licensed under BY-NC-SA unless stating additionally.
Contents
  1. Lattice based cryptosystems
    1. LLL algorithm
    2. NTRU
      1. 加密过程
      2. 解密过程
      3. Lattice-based attacks
      4. 代码实现
  2. GGH
    1. 加密过程
    2. 解密过程
    3. Lattice-based attacks
  • LBH
    1. 算法流程
  • BFV
    1. 加密过程
    2. 解密过程