AGCD近似最大公约数问题

发表于 更新于 本文字数： 2.1k 阅读时长 ≈ 2 分钟
有关AGCD/ACD近似最大公约数问题的简要笔记

AGCD 问题

AGCD 问题，又称 ACD 问题，the Approximate Common Divisor Problem。

描述的问题如下，如果说我们知道 \(x_1,\cdots,x_l\) 满足 \[ x_1=pq_1\newline x_2=pq_2\newline \vdots\newline x_l=pq_l \] 那么我们想要获得 \(p\)，仅需要求最大公约数即可，即 \[ p=\gcd(x_1,\cdots,x_l) \] 有许多最大公约数算法可以快速求出 \(p\)。

但是，如果说我们在其中加入误差 \(e_i\)，使得 \[ x_1=pq_1+e_1\newline x_2=pq_2+e_2\newline \vdots\newline x_l=pq_l+e_l \] 那么就难以直接求解最大公约数了。

正常来说可以尝试去爆破 \(e_1,e_2\) 使得 \(g=\gcd(x_1-e_1,x_2-e_2)\)，但如果当 \(r\) 比较大时，显然这是不现实的。

丢番图近似 SDA 格攻击

对于上述问题，我们需要描述得更精确些，其中 \(p\) 的大小为 \(\eta\) 位，\(e_i\) 的大小为 \(\rho\) 位（包含正负），而 \(q_i\) 的大小为 \(\gamma -\eta\) 位（即 \(x\) 的大小为 \(\gamma\) 位）。

ACD 所需参数为 \((\gamma,\eta,\rho)\)。

以 \((x_0,x_1)\) 对为例，我们考虑 \[ \begin{align} q_0x_1-q_1x_0&=q_0(q_1p+e_1)-q_1(q_0p+e_0)\\ &=q_0q_1p+q_0e_1-q_1q_0p-q_1e_0\\ &=q_0e_1-q_1e_0 \end{align} \] 那么对于 \(l-1\) 组，我们可以构建方程组 \[ (q_0,q_1,\cdots,q_l)\begin{bmatrix} 2^{\rho+1}&x_1&x_2&\cdots&x_l\\ &-x_0\\ &&-x_0\\ &&&\ddots\\ &&&&-x_0 \end{bmatrix}=(q_02^{\rho+1},q_0e_1-q_1e_0,\cdots,q_0e_l-q_le_0) \] 可以证明的是，解向量是格中的短向量。

以下为生成代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from Crypto.Util.number import getPrime, getRandomRange

def gen(k:int, gamma: int, eta: int, rho: int):
    xs = []
    qs = []
    es = []
    p = getPrime(eta)
    for _ in range(k):
        q = getPrime(gamma - eta)
        e = getRandomRange(-pow(2, rho) + 1, pow(2, rho) - 1)
        qs.append(q)
        es.append(e)
        xs.append(p * q + e)
    return p, qs, es, xs

k = 5
eta = 768
gamma = 1024 + eta
rho = 256
p, qs, es, xs = gen(k, gamma, eta, rho)
print(f'{p = }')
print(f'{qs = }')
print(f'{es = }')
print(f'{xs = }')

以下为格攻击代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
k = 5
rho = 256
xs = ...

A = ZZ(pow(2, rho + 1))
B = matrix(xs[1:])
C = matrix.diagonal([-xs[0]] * (k - 1))
M = matrix.block([[A, B], [ZZ(0), C]])
L = M.LLL()
q0 = ZZ(L[0, 0] / A).abs()
e0 = ZZ(xs[0] % q0)
p = ZZ((xs[0] - e0) / q0)
print(f'{e0 = }')
print(f'{q0 = }')
print(f'{p = }')

需满足 \[ l+1>\frac{\gamma-\rho}{\eta-\rho} \] 格攻击才有解。

正交格近似 OL 格攻击

需满足 \[ l>\frac{\gamma-\rho}{\eta-\rho} \] 格攻击才有解。

多项式近似 MP 格攻击

FHE 全同态加密

基于 ACD 问题，DGHV10 提出 FHE 全同态加密方案：

选取一个 \(\eta\) 位密钥 \(p\)，加密一位 \(m\in\{0,1\}\)，随机选取整数 \(r,q\)，计算密文 \[ c=pq+2r+m \]

将消息添加到具有均匀噪声的 ACD 样本中。

解密时计算 \[ c'=c\pmod{p}\in(-p/2,p/2) \] 输出消息的一位 \[ m=c'\pmod{2} \] 其满足加法同态和乘法同态，即明文乘等于密文乘，明文加等于密文加。