参考资料：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算法，这个算法主要分为两步：

  1. 从\(\pmb{h}\)中得到由\(\pmb{x_1},\pmb{x_2},\cdots,\pmb{x_n}\)所生成的格\(\mathcal{L}_{\pmb{x}}\)的完备格\(\overline{\mathcal{L}}_{\pmb{x}}\).

  2. 从\(\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}\)，必然有： \[ \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} \] 可以知道，向量\((\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))