参考资料：A Polynomial-Time Algorithm for Solving the Hidden Subset Sum Problem
前置知识
正交格
对于\(\mathbb{Z}^m\)上一个格\(\mathcal{L}\)，定义其正交格为：
$$
\mathcal{L}^{\bot}=\left\{\pmb{v}\in\mathbb{Z}^m\mid\forall\pmb{b}\in\mathcal{L},\langle\pmb{v},\pmb{b}\rangle=0\right\}
$$
完备格
对于\(\mathbb{Z}^m\)上一个格\(\mathcal{L}\)，定义其完备格为\(\overline{\mathcal{L}}=(\mathcal{L}^{\bot})^{\bot}\).显然的，\(\mathcal{L}\)为\(\overline{\mathcal{L}}\)的一个满秩子格.
问题简述
设\(M\)为一整数，设\(\alpha_1,\alpha_2,\cdots,\alpha_n\)是\(\mathbb{Z}/M\mathbb{Z}\)上随机选取的\(n\)个整数，\(\pmb{x}_1,\pmb{x}_2,\cdots,\pmb{x}_n\)为\(\mathbb{Z}^{m}\)上随机选取的\(m\)个\(0-1\)向量（即\(\pmb{x}_1,\pmb{x}_2,\cdots,\pmb{x}_n\in\left\{0,1\right\}^m\)），令
$$ \pmb{h}\equiv\sum_{i=1}^{n}\alpha_i\pmb{x}_i\equiv\alpha_1\pmb{x}_1+\alpha_2\pmb{x}_2+\cdots+\alpha_n\pmb{x}_n\pmod{M}
$$
隐子集和问题（Hidden Subset Sum Problem，简称HSSP）即为已知整数\(M\)以及向量\(\pmb{h}\)，恢复\((\alpha_1,\alpha_2,\cdots,\alpha_n)\)以及\((\pmb{x_1},\pmb{x_2},\cdots,\pmb{x_n})\).
Nguyen-Stern算法
求解HSSP的一种比较行之有效的方法就是Nguyen-Stern算法，这个算法主要分为两步：
- 从\(\pmb{h}\)中得到由\(\pmb{x_1},\pmb{x_2},\cdots,\pmb{x_n}\)所生成的格\(\mathcal{L}_{\pmb{x}}\)的完备格\(\overline{\mathcal{L}}_{\pmb{x}}\).
- 从\(\overline{\mathcal{L}}_{\pmb{x}}\)中恢复向量\(\pmb{x_1},\pmb{x_2},\cdots,\pmb{x_n}\)，从而根据\(\pmb{h},M,\pmb{x_1},\pmb{x_2},\cdots,\pmb{x_n}\)恢复出\(\alpha_1,\alpha_2,\cdots,\alpha_n\).
第一步
首先我们需要通过正交格攻击（Orthogonal Lattice Attack）来获得\(\overline{\mathcal{L}}_{\pmb{x}}\)，我们设所有模\(M\)下与向量\(\pmb{h}\)正交的向量所构成的格为：
$$ \mathcal{L}_0=\left\{\pmb{u}\in\mathbb{Z}^m\mid\langle\pmb{u},\pmb{h}\rangle\equiv0\pmod{M}\right\} $$
显然的，对于\(\mathcal{L}_0\)中任一向量\(\pmb{u}\)，必然有：
$$
\begin{aligned}
\langle\pmb{u},\pmb{h}\rangle&\equiv\left\langle\pmb{u},\sum{i=1}^n\alpha_i\pmb{x}_i\right\rangle\\
&\equiv\sum{i=1}^n\alpha_i\langle\pmb{u},\pmb{x}_i\rangle\\
&\equiv\alpha_1\langle\pmb{u},\pmb{x}_1\rangle+\alpha_2\langle\pmb{u},\pmb{x}_2\rangle+\cdots+\alpha_n\langle\pmb{u},\pmb{x}_n\rangle\\
&\equiv0\pmod{M}
\end{aligned}
$$
可以知道，向量\((\langle\pmb{u},\pmb{x}_1\rangle,\langle\pmb{u},\pmb{x}_2\rangle,\cdots,\langle\pmb{u},\pmb{x}_n\rangle)\)与向量\((\alpha_1,\alpha_2,\cdots,\alpha_n)\)在模\(M\)下是正交的，因为\(\pmb{x}_1,\pmb{x}_2,\cdots,\pmb{x}_n\)，那么如果\(\pmb{u}\)足够短的话，向量\((\langle\pmb{u},\pmb{x}_1\rangle,\langle\pmb{u},\pmb{x}_2\rangle,\cdots,\langle\pmb{u},\pmb{x}_n\rangle)\)也会比较短，而如果向量\((\langle\pmb{u},\pmb{x}_1\rangle,\langle\pmb{u},\pmb{x}_2\rangle,\cdots,\langle\pmb{u},\pmb{x}_n\rangle)\)比与\((\alpha_1,\alpha_2,\cdots,\alpha_n)\)在模\(M\)下正交的非零向量都短的话，那么它只能是零向量，也就是有：
$$ (\langle\pmb{u},\pmb{x}_1\rangle,\langle\pmb{u},\pmb{x}_2\rangle,\cdots,\langle\pmb{u},\pmb{x}_n\rangle)=(0,0,\cdots,0)\Rightarrow\langle\pmb{u},\pmb{x}_i\rangle=0(i=1,2,\cdots,n)
$$
那么我们可以通过一些方法构造\(\mathcal{L}_0\)并进行规约，取出约减基的前\(m-n\)个短向量\(\pmb{u}_1,\pmb{u}_2,\cdots,\pmb{u}_{m-n}\)可以构成\(\mathcal{L}_{\pmb{x}}^{\bot}\)，再求其正交格即可得到完备格\(\overline{\mathcal{L}}_{\pmb{x}}=(\mathcal{L}_{\pmb{x}}^{\bot})^{\bot}\).
在参考资料中给出一种通过\(\pmb{h}\)来构造\(\mathcal{L}_0\)的方法，我们设\(\pmb{h}=(h_1,h_2,\cdots,h_n)\)，如果\(\gcd(h_1,M)=1\)，那么对于\(\pmb{u}=(u_1,u_2,\cdots,u_m)\in\mathcal{L}_0\)我们可以得到：
$$
\langle\pmb{u},\pmb{h}\rangle\equiv\sum_{i=1}^mu_ih_i\equiv u_1h_1+\sum_{i=2}^mu_ih_i\equiv0\pmod{M}
$$
两边同乘\(h_1^{-1}\)有：
$$
u_1+\sum_{i=2}^mu_ih_{1}^{-1}h_i\equiv0\pmod{M}
$$
即：
$$
u_1+\sum_{i=2}^m(u_ih_{1}^{-1}h_i\mod{M})=kM
$$
那么可以得到一线性关系：
$$
u_1=kM-\sum_{i=2}^m(u_ih_{1}^{-1}h_i\mod{M})
$$
通过这一线性关系我们可以构造出格：
$$
\mathcal{L}_0=\left(\begin{matrix}
M&0&0&\cdots&0\\
-h_1^{-1}h_2\mod{M}&1&0&\cdots&0\\
-h_1^{-1}h_3\mod{M}&0&1&\cdots&0\\
\vdots&\vdots&\vdots&\ddots&\vdots\\
-h_1^{-1}h_m\mod{M}&0&0&\cdots&1
\end{matrix}\right)
$$
对于这个格，有：
$$
(k,u_2,\cdots,u_m)\mathcal{L}_0=(u_1,u_2,\cdots,u_m)
$$
根据前面的分析可以知道这个格规约后得到的约减基的前\(m-n\)个短向量\(\pmb{u}_1,\pmb{u}_2,\cdots,\pmb{u}_{m-n}\)可以构成\(\mathcal{L}_{\pmb{x}}^{\bot}\)，在获得\(\mathcal{L}_{\pmb{x}}^{\bot}\)之后，只需要求\(\mathcal{L}_{\pmb{x}}^{\bot}\)的核空间即可得到\(\overline{\mathcal{L}}_{\pmb{x}}=(\mathcal{L}_{\pmb{x}}^{\bot})^{\bot}\).
第二步
因为\(\mathcal{L}_{\pmb{x}}\)为\(\overline{\mathcal{L}}_{\pmb{x}}\)的一个子格，所以\(\overline{\mathcal{L}}_{\pmb{x}}\)中必然是包含\(\pmb{x}_1,\pmb{x}_2,\cdots,\pmb{x}_n\)的，又因为\(\pmb{x}_1,\pmb{x}_2,\cdots,\pmb{x}_n\in\left\{0,1\right\}^m\)，那么直接对\(\overline{\mathcal{L}}_{\pmb{x}}\)进行规约大概率是可以得到\(\pmb{x}_1,\pmb{x}_2,\cdots,\pmb{x}_n\)的，也可以构造格：
$$
\mathcal{L}_{\pmb{x}}’=\left(\begin{matrix}2\mathcal{L_{\pmb{x}}}\\-\pmb{e}\end{matrix}\right)
$$
来规约求得\(2\pmb{x}_1-\pmb{e},2\pmb{x}_2-\pmb{e},\cdots,2\pmb{x}_n-\pmb{e}\in\left\{-1,1\right\}^m\)（其中\(\pmb{e}=(1,1,\cdots,1)\)，要去掉规约后的格基里面全为\(1\)或全为\(-1\)的行向量，且有部分向量求出是\(\pmb{e}-2\pmb{x}_i\)）. 在获得\(\pmb{x}_1,\pmb{x}_2,\cdots,\pmb{x}_n\)之后，只需要求解方程：
$$
\pmb{h}=(\alpha_1,\alpha_2,\cdots,\alpha_n)\left(\begin{matrix}\pmb{x}_1\\\pmb{x}_2\\\vdots\\\pmb{x}_n\end{matrix}\right)
$$
就可以恢复出\(\alpha_1,\alpha_2,\cdots,\alpha_n\).
代码实现
根据上述分析，通过如下代码就可以求解HSSP（因为格较大，所以在正交格攻击一步中使用flatter进行加速）
from Crypto.Util.number import *
def flatter(M):
from subprocess import check_output
from re import findall
global count
z = "[[" + "]\n[".join(" ".join(map(str, row)) for row in M) + "]]"
ret = check_output(["flatter"], input=z.encode())
return matrix(M.nrows(), M.ncols(), map(int, findall(b"-?\\d+", ret)))
m = ...
n = ...
M = ...
h = [...]
L0 = matrix(ZZ, m, m)
L0[0, 0] = M
inv_h0 = inverse(h[0], M)
for i in range(1, m):
L0[i, 0] = -h[i] * inv_h0
L0[i, i] = 1
Lx_ort = matrix(ZZ, flatter(L0)[0: m-n])
Lx = Lx_ort.right_kernel(algorithm='pari').matrix()
e = matrix(ZZ, [1 for _ in range(m)])
L = block_matrix(ZZ, [[2*Lx], [-e]])
e = vector(ZZ, [1 for _ in range(m)])
tmpMat = L.BKZ()
B = []
space = Lx.row_space()
for v in tmpMat:
if len(set(v)) == 1:
continue
else:
tmp = (v + e) / 2
if tmp in space:
B.append(tmp)
elif e - tmp in space:
B.append(e - tmp)
L_x = matrix(Zmod(M), B)
H = vector(Zmod(M), h)
print(L_x.solve_left(H))