原文链接：https://tover.xyz/p/HSSP-note/ 看看能不能抢到2024年的最后一篇帖子以下正文：现在是个人都会用正交格攻击了，搞得我不学好像就落后似的，所以抽空学习了一下其中，和正交格相关的最出名的就是HSSP问题了，于是下面就把HSSP问题怼一遍 # HSSP问题 HSSP（Hidden Subset Sum Problem）问题大概如下令[imath:0]M[/imath:0]为大整数，整数[imath:0]\alpha_1, \cdots, \alpha_n \in \mathbb{Z}_M[/imath:0]，向量[imath:0]\pmb{x_1}, \cdots, \pmb{x_n} \in \mathbb{Z}^m[/imath:0]为[imath:0]m[/imath:0]维向量，且[imath:0]\pmb{x_i}[/imath:0]的元素落在[imath:0]\{0, 1\}[/imath:0]中，令 [math:0] \pmb{h} = (h_1, \cdots, h_m) \equiv \sum_{i=1}^n \alpha_i \pmb{x_i} \pmod M [/math:0] 现知道[imath:0]M[/imath:0]和[imath:0]\pmb{h}[/imath:0]，求[imath:0]\pmb{\alpha} = (\alpha_1, \cdots, \alpha_n)[/imath:0]和[imath:0]\pmb{x_1}, \cdots, \pmb{x_n}[/imath:0] PS：根据Coron的测试数据，M的大小大概是[imath:0]M = O(2 \iota n^2 + n \cdot log\ n)[/imath:0]，其中[imath:0]\iota = 0.035[/imath:0]，（也有[imath:0]m>n[/imath:0]）和经典背包问题（SSP）的区别是，在HSSP中隐藏（Hidden）了[imath:0]\alpha_1, \cdots, \alpha_n[/imath:0]，所以无法直接通过构造格来解给一个生成问题的样例代码 ```python def genHssp(m, n, M): R. = PolynomialRing(Zmod(M)) x = [R([randint(0, 1) for mi in range(m)]) for ni in range(n)] a = [randint(0, M-1) for ni in range(n)] h = sum([a[i] * x[i] for i in range(n)]) return (a, [xi.list() for xi in x]), (M, h.list()) m = 200 n = 100 M = 199999999999997 (a, X), (M, h) = genHssp(m, n, M) ``` # 线性代数知识在讲正交格前先来补充一点线性代数的前置知识，更详细的内容可以参考 Strang, Gilbert. *Introduction to linear algebra*. Wellesley-Cambridge Press, 2022. 讲到线性代数，第一个想到的应该都是像 [math:0] A \pmb{x} = \pmb{b} [/math:0] 这样的矩阵和向量的运算如果不把矩阵和向量看成单纯的数字，而是看成是空间和空间中的点的话，就可以得到著名的四大基本子空间：行空间、列空间、零空间（核空间）和左零空间给定一个[imath:0]m \times n[/imath:0]（[imath:0]m[/imath:0]行[imath:0]n[/imath:0]列）的矩阵[imath:0]A[/imath:0]，可以把[imath:0]A[/imath:0]的每一列看成空间的基，用这个行向量的基张成（Span，即进行线性组合）的空间就叫列空间，数学方式表示大概是（如果是格的话就是[imath:0]\forall \pmb{x} \in \mathbb{Z}^n[/imath:0]） [math:0] \{b \in \mathbb{R}^m\ |\ A \pmb{x} = b,\ \forall \pmb{x} \in \mathbb{R}^n\} [/math:0] 如果把[imath:0]A[/imath:0]的每一行看作空间的基，那么张成的空间就叫行空间，数学表示大概是 [math:0] \{b \in \mathbb{R}^n\ |\ \pmb{x} A = b,\ \forall \pmb{x} \in \mathbb{R}^m\} [/math:0] 如果只关注[imath:0]A \pmb{x} = \pmb{0}[/imath:0]这个方程，那么方程的所有解落在零空间（又叫核空间）中 [math:0] \{\pmb{x} \in \mathbb{R}^n\ |\ A \pmb{x} = \pmb{0}\} [/math:0] 如果把[imath:0]\pmb{x}[/imath:0]放在[imath:0]A[/imath:0]的左边，得到的空间又叫左零空间 [math:0] \{\pmb{x} \in \mathbb{R}^m\ |\ \pmb{x} A = \pmb{0}\} [/math:0] 令[imath:0]r[/imath:0]为矩阵[imath:0]A[/imath:0]的秩（Rank），那么列空间和行空间的维度都是[imath:0]r[/imath:0]，零空间的维度是[imath:0]n-r[/imath:0]，左零空间的维度是[imath:0]m-r[/imath:0] 直观上看，[imath:0]A[/imath:0]消元后非零的列和行的数量都是[imath:0]r[/imath:0]，零的列是[imath:0]n-r[/imath:0]，零的行是[imath:0]m-r[/imath:0]，详细的证明可以看书或者网上找找 ![](https://tover.xyz/p/HSSP-note/image-20241224172351767.png) 在四大基本子空间中有一个重要的结论是，行空间与零空间相互垂直，列空间与左零空间相互垂直可以简单证明一下，令[imath:0]\pmb{b} = \pmb{x}_b A[/imath:0]为行空间的一个向量，令[imath:0]\pmb{x}[/imath:0]为零空间的一个向量，那么两个向量相乘 [math:0] \pmb{b} \cdot \pmb{x} = \pmb{x}_b A \pmb{x} [/math:0] 根据零空间的性质，[imath:0]A \pmb{x} = \pmb{0}[/imath:0]，所以 [math:0] \pmb{b} \cdot \pmb{x} = \pmb{x}_b \pmb{0} = 0 [/math:0] 也就是任意一个行空间的向量与任意一个零空间的向量都相互垂直，即行空间与零空间相互垂直列空间与左零空间的证明类似 ![](https://tover.xyz/p/HSSP-note/image-20241224172405837.png) 另一个重要的结论是，行空间与零空间可以张成整个[imath:0]\mathbb{R}^n[/imath:0]空间，列空间与左零空间可以张成整个[imath:0]\mathbb{R}^m[/imath:0]空间直观上看，行空间与零空间相互垂直就是不相关，然后两个空间的维度加起来刚好是[imath:0]n[/imath:0] 列空间与左零空间的也类似由这两个结论可得，如果要求一个格的正交格（就是相互垂直的），那么只要求他的零空间（行看作基）或者左零空间（列看作基）就好 # Flatter Flatter是一个比LLL更快的格规约算法和LLL不同的是，目前SageMath没有原生集成Flatter，所以需要装一个安装方法可以直接看[Github](https://github.com/keeganryan/flatter)，大概就是 ```sh git clone https://github.com/keeganryan/flatter.git sudo apt install libgmp-dev libmpfr-dev fplll-tools libfplll-dev libeigen3-dev mkdir build && cd ./build cmake .. make -j8 # 软链接路径改成自己的PATH ln -s `pwd`/bin/flatter [imath:0]HOME/.local/bin flatter -h ``` 然后我直接抄了[@Neobeo](https://github.com/Neobeo/HackTM2023/blob/main/solve420.sage)的做法，通过子进程调用Flatter二进制应用 ```python # https://github.com/Neobeo/HackTM2023/blob/main/solve420.sage # faster LLL reduction to replace `M.LLL()` wiith `flatter(M)` def flatter(M): from subprocess import check_output from re import findall M = matrix(ZZ,M) # compile https://github.com/keeganryan/flatter and put it in [/imath:0]PATH 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))) ``` 在SageMath中用的时候直接把正常用的``M.LLL()``换成``flatter(M)``即可 HSSP问题的格通常都比较大，所以用Flatter会比LLL节约不少时间 # Nguyen-Stern算法接下来就看看这个HSSP到底要怎么解，以下内容我参考了 Coron, Jean-Sébastien, and Agnese Gini. "A polynomial-time algorithm for solving the hidden subset sum problem." *Annual International Cryptology Conference*. Cham: Springer International Publishing, 2020. 还有文章对应的[代码](https://pastebin.com/ZFk1qjfP)，和[@tl2的文章](https://github.com/tl2cents/Implementation-of-Cryptographic-Attacks/blob/main/MultivariateHSSP/A%20Polynomial-Time%20Algorithm%20for%20Solving%20the%20Hidden%20Subset%20Sum%20Problem.ipynb)，有很多被我忽略掉的内容都可以在这篇文章中看到 Nguyen和Stern的做法是，给定[imath:0]\pmb{h} \pmod M[/imath:0]，首先找与[imath:0]\pmb{h}[/imath:0]垂直的向量[imath:0]\pmb{u}[/imath:0]，那么就有 [math:0] \pmb{u} \cdot \pmb{h} \equiv \sum_{i=1}^n \alpha_i (\pmb{u} \cdot \pmb{x_i}) \equiv 0 \pmod M [/math:0] 令向量 [math:0] \pmb{p_u} = ((\pmb{u} \cdot \pmb{x_1}), (\pmb{u} \cdot \pmb{x_2}), \cdots, (\pmb{u} \cdot \pmb{x_n})) [/math:0] 那么问题就可以转化为 [math:0] \pmb{p_u} \cdot \pmb{\alpha} \equiv 0 \pmod M [/math:0] 也就是[imath:0]\pmb{p_u}[/imath:0]和[imath:0]\pmb{\alpha}[/imath:0]在模[imath:0]M[/imath:0]的情况下相互垂直然后如果[imath:0]\pmb{u}[/imath:0]是短向量的话，那么[imath:0]\pmb{p_u}[/imath:0]也会是短向量（因为[imath:0]\pmb{x_i}[/imath:0]的元素落在[imath:0]\{0, 1\}[/imath:0]中），如果[imath:0]\pmb{p_u}[/imath:0]比所有与[imath:0]\pmb{\alpha}[/imath:0]垂直的非零向量都短的话，那么就只能是[imath:0]\pmb{p_u} = \pmb{0}[/imath:0] 而如果[imath:0]\pmb{p_u} = \pmb{0}[/imath:0]的话，就是[imath:0]\pmb{u} \cdot \pmb{x_i} = 0[/imath:0]，令[imath:0]L_x[/imath:0]是以[imath:0]\pmb{x_1}, \cdots, \pmb{x_n}[/imath:0]为基的格，就可以得到[imath:0]\pmb{u} \in L_x[/imath:0]，即[imath:0]\pmb{u}[/imath:0]是[imath:0]L_x[/imath:0]的正交格[imath:0]L_x^\bot[/imath:0]中的向量 [imath:0]L_x^\bot[/imath:0]的维度是[imath:0]m-n[/imath:0]：因为[imath:0]L_x^\bot[/imath:0]的基的秩是[imath:0]r=n[/imath:0]（[imath:0]n \le m[/imath:0]），然后我这里是看成行向量为基的空间（行空间），且[imath:0]L_x[/imath:0]的基是[imath:0]n[/imath:0]行[imath:0]m[/imath:0]列的，所以根据前面的线性代数知识，与行空间垂直的零空间的维度就是[imath:0]m-r = m-n[/imath:0] 所以，如果我们可以找到[imath:0]m-n[/imath:0]个满足条件的向量[imath:0]\pmb{u}[/imath:0]的话，就相当于找到了[imath:0]L_x[/imath:0]的正交格[imath:0]L_x^\bot[/imath:0]，进而使用[imath:0]L_x^\bot[/imath:0]找到[imath:0]L_x[/imath:0]，最后由[imath:0]L_x[/imath:0]恢复基[imath:0]\pmb{x_1}, \cdots, \pmb{x_n}[/imath:0] 于是，最后得到的**攻击路线**就是 1. 用[imath:0]\pmb{h}[/imath:0]构造格基，LLL找到[imath:0]m-n[/imath:0]个短向量[imath:0]\pmb{u}_i[/imath:0] 2. 用[imath:0]\pmb{u}_i[/imath:0]构造格[imath:0]L_x^\bot[/imath:0]，用[imath:0]L_x^\bot[/imath:0]找[imath:0]L_x[/imath:0]的正交补[imath:0]\bar{L_x}[/imath:0]（可以看作是和[imath:0]L_x[/imath:0]同一个空间，但基不是[imath:0]\pmb{x}_i[/imath:0]） 3. 对[imath:0]\bar{L_x}[/imath:0]使用BKZ恢复[imath:0]\pmb{x}_i[/imath:0] ## Part.1 找短向量u 这里我直接用Coron论文中的方法造格首先拆开 [math:0] \pmb{u} \cdot \pmb{h} \equiv 0 \pmod M [/math:0] 得到 [math:0] \sum_{i=1}^m u_i h_i \pmod 0 \pmod M [/math:0] 然后提出其中的[imath:0]u_1[/imath:0] [math:0] u_1 h_1 + \sum_{i=2}^m u_i h_i \pmod 0 \pmod M [/math:0] 两边乘[imath:0]h_1^{-1} \pmod M[/imath:0] [math:0] u_1 + \sum_{i=2}^m u_i (h_i h_1^{-1}) \pmod 0 \pmod M [/math:0] 最后拆开模数[imath:0]M[/imath:0]，并换一下位置 [math:0] kM + \sum_{i=2}^m u_i (-h_i h_1^{-1}) = u_1 [/math:0] 根据这个关系就可以构造格基 [math:0] B_1 = \begin{bmatrix} M & \\ -h_2 h_1^{-1} & 1 \\ -h_3 h_1^{-1} & & 1 & \\ \vdots & & & \ddots \\ -h_m h_1^{-1} & & & & 1 \end{bmatrix}_{m \times m} [/math:0] 令 [math:0] \begin{aligned} \pmb{v}_1 &= (k, u_2, u_3, \cdots, u_m) \\ \pmb{w}_1 &= (u_1, u_2, u_3, \cdots, u_m) \end{aligned} [/math:0] 那么就是 [math:0] \pmb{w}_1 \cdot B_1 = \pmb{w}_1 [/math:0] 根据Coron文章第三章的分析，可以保证对[imath:0]B_1[/imath:0]规约后的前[imath:0]m-n[/imath:0]行是满足条件的向量[imath:0]\pmb{u}[/imath:0]，这个，可以自己看论文... ```python B = matrix(ZZ, m) B[0, 0] = M h0i = Integer(h[0]).inverse_mod(M) for i in range(1, m): B[i, 0] = - h[i] * h0i B[i, i] = 1 L = flatter(B) vh = vector(Zmod(M), h) print([vector(Zmod(M), list(l)) * vh for l in L]) ``` 另外，还可以构造另一种更直观的格基 [math:0] B_2 = \begin{bmatrix} M & \\ h_1 & 1 \\ h_2 & & 1 & \\ \vdots & & & \ddots \\ h_m & & & & 1 \end{bmatrix}_{(m+1) \times (m+1)} [/math:0] 令 [math:0] \begin{aligned} \pmb{v}_2 &= (-k, u_1, u_2, u_3, \cdots, u_m) \\ \pmb{w}_2 &= (0, u_1, u_2, u_3, \cdots, u_m) \end{aligned} [/math:0] 那么就是 [math:0] \pmb{w}_2 \cdot B_2 = \pmb{w}_2 [/math:0] 这个格基在Coron的文章和@tl2的文章都有类似的，可以去参考一下 ## Part.2 恢复格Lx 这一步就比较简单首先根据上面分析，用``L``的前``m-n``就可以构造[imath:0]L_x^\bot[/imath:0] 然后只需要求[imath:0]L_x^\bot[/imath:0]的零空间就可以得到[imath:0]L_x[/imath:0]的正交补[imath:0]\bar{L_x}[/imath:0] 这里我直接用SageMath的``right_kernel``求令空间，亲测把``algorithm``指定为``pari``的话会快一点 ```python Lxo = matrix(ZZ, L[:m-n]) Lxc = Lxo.right_kernel(algorithm='pari').matrix() # faster print('right_kernel done.') Lx_real = matrix(ZZ, [xi + [0] * (m - len(xi)) for xi in X]) rsc = Lxc.row_space() print([xi in rsc for xi in Lx_real]) ``` ## Part.3 恢复xi 理论上直接对``Lxc``求个LLL或者BKZ就可以恢复[imath:0]\pmb{x_1}, \cdots, \pmb{x_n}[/imath:0]，但实际上并没有细看一下，[imath:0]\pmb{x_1}, \cdots, \pmb{x_n}[/imath:0]的元素在[imath:0]\{0, 1\}[/imath:0]中，这在01背包问题中也遇到过类似的问题，所以可以利用类似的解决方法，即把[imath:0]\pmb{x_1}, \cdots, \pmb{x_n}[/imath:0]转化为 [math:0] 2\pmb{x_1}-\pmb{1}, 2\pmb{x_2}-\pmb{1}, \cdots, 2\pmb{x_n}-\pmb{1} [/math:0] 就可以把元素转化到[imath:0](-1, 1)[/imath:0]中虽然这对向量长度影响不大，但乘上去的系数[imath:0]2[/imath:0]会增大格基的行列式，就更容易筛掉无关的变量于是就可以构造这样一个格基（其中[imath:0]E[/imath:0]是元素全为[imath:0]1[/imath:0]、大小和[imath:0]\bar{Lx}[/imath:0]一样的矩阵） [math:0] B_3 = \begin{bmatrix} -E \\ \hline 2 \bar{Lx} \end{bmatrix}_{2n \times m} [/math:0] 令（U是[imath:0]n \times n[/imath:0]，看作一种映射就好） [math:0] U \bar{L_x} = L_x [/math:0] 可以得到关系 [math:0] [I_{n}, U]_{n \times 2n} \cdot B_3 = [2 U \bar{Lx} - E]_{n \times m} = [2L_x - E] = \begin{bmatrix} 2\pmb{x_1}-\pmb{1} \\ \vdots \\ 2\pmb{x_n}-\pmb{1} \end{bmatrix} [/math:0] 所以对[imath:0]B_3[/imath:0]归约后就可能得到[imath:0]2\pmb{x_1}-\pmb{1}, 2\pmb{x_2}-\pmb{1}, \cdots, 2\pmb{x_n}-\pmb{1}[/imath:0] 进一步观察发现其实[imath:0]B_3[/imath:0]中的[imath:0]E[/imath:0]的每一行都是相关的（甚至相同的），实际作用的就一行，对[imath:0]B_3[/imath:0]规约后也发现有[imath:0]n-1[/imath:0]行全为[imath:0]0[/imath:0] 所以不妨令[imath:0]\pmb{e}[/imath:0]为全为[imath:0]1[/imath:0]的行向量，就可以把格简化为 [math:0] B_4 = \begin{bmatrix} -\pmb{e} \\ \hline 2 \bar{Lx} \end{bmatrix}_{n+1 \times m} [/math:0] 参考代码 ```python def checkMatrix(M, wl=[-1, 1]): M = [list(_) for _ in list(M)] ml = list(set(flatten(M))) logging.debug(ml) return sorted(ml) == sorted(wl) e = matrix(ZZ, [1] * m) B = block_matrix([[-e], [2*Lxc]]) Lx = B.BKZ() assert checkMatrix(Lx) assert len(set(Lx[0])) == 1 ``` 最后恢复一下[imath:0]\pmb{x}_i[/imath:0]和[imath:0]\alpha_i[/imath:0] ```python Lx = Lx[1:] E = matrix(ZZ, [[1 for c in range(Lxc.ncols())] for r in range(Lxc.nrows())]) Lx = (Lx + E) / 2 Lx2 = [] e = vector(ZZ, [1] * m) rsc = Lxc.row_space() for lx in Lx: if lx in rsc: Lx2 += [lx] continue lx = e - lx if lx in rsc: Lx2 += [lx] continue print('Something wrong?') Lx = matrix(Zmod(M), Lx2) vh = vector(Zmod(M), h) va = Lx.solve_left(vh) ``` PS：其实用[imath:0]\begin{bmatrix} 2 \bar{Lx} \\ \hline -\pmb{e} \end{bmatrix}[/imath:0]做格也可以，但是干扰的那一行就不会放在第一行，还要另外写代码找出来（就是全为``1``或者全为``-1``的行） # 模板/参考代码最后把上面所有的代码整合一下 ```python import logging logging.basicConfig( level=logging.DEBUG, format="[%(levelname)s] %(message)s" ) # https://github.com/Neobeo/HackTM2023/blob/main/solve420.sage # faster LLL reduction to replace `M.LLL()` wiith `flatter(M)` def flatter(M, **kwds): from subprocess import check_output from re import findall M = matrix(ZZ,M) # compile https://github.com/keeganryan/flatter and put it in [imath:0]PATH 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))) def genHssp(m, n, M): R. = PolynomialRing(Zmod(M)) x = [R([randint(0, 1) for mi in range(m)]) for ni in range(n)] a = [randint(0, M-1) for ni in range(n)] h = sum([a[i] * x[i] for i in range(n)]) return (a, [xi.list() for xi in x]), (M, h.list()) def checkMatrix(M, wl=[-1, 1]): M = [list(_) for _ in list(M)] ml = list(set(flatten(M))) logging.debug(ml) return sorted(ml) == sorted(wl) def Nguyen_Stern(h, m, n, M): B = matrix(ZZ, m) B[0, 0] = M h0i = Integer(h[0]).inverse_mod(M) for i in range(1, m): B[i, 0] = - h[i] * h0i B[i, i] = 1 #L = B.BKZ() # slooooooow L = flatter(B) logging.info('flatter done.') ''' vh = vector(Zmod(M), h) logging.debug([vector(Zmod(M), list(l)) * vh for l in L]) ''' Lxo = matrix(ZZ, L[:m-n]) Lxc = Lxo.right_kernel(algorithm='pari').matrix() # faster logging.info('right_kernel done.') ''' try: Lx_real = matrix(ZZ, [xi + [0] * (m - len(xi)) for xi in X]) rsc = Lxc.row_space() logging.debug([xi in rsc for xi in Lx_real]) except: pass ''' e = matrix(ZZ, [1] * m) B = block_matrix([[-e], [2*Lxc]]) Lx = B.BKZ() logging.info('BKZ done.') assert checkMatrix(Lx) assert len(set(Lx[0])) == 1 Lx = Lx[1:] E = matrix(ZZ, [[1 for c in range(Lxc.ncols())] for r in range(Lxc.nrows())]) Lx = (Lx + E) / 2 Lx2 = [] e = vector(ZZ, [1] * m) rsc = Lxc.row_space() for lx in Lx: if lx in rsc: Lx2 += [lx] continue lx = e - lx if lx in rsc: Lx2 += [lx] continue logging.warning('Something wrong?') Lx = matrix(Zmod(M), Lx2) vh = vector(Zmod(M), h) va = Lx.solve_left(vh) return Lx, va # stolen from https://github.com/tl2cents/Implementation-of-Cryptographic-Attacks/blob/main/MultivariateHSSP/A%20Polynomial-Time%20Algorithm%20for%20Solving%20the%20Hidden%20Subset%20Sum%20Problem.ipynb def derive_M(n): iota=0.035 Mbits=int(2 * iota * n^2 + n * log(n,2)) M = random_prime(2^Mbits, proof = False, lbound = 2^(Mbits - 1)) return Integer(M) m = 200 n = 100 M = derive_M(n) (a, X), (M, h) = genHssp(m, n, M) logging.debug('m: %d | n: %d' % (m, n)) logging.debug('%s, %s' % (M, M.nbits())) Lx, va = Nguyen_Stern(h, m, n, M) print(sorted(va) == sorted(a)) ``` ``M``的生成采用了Coron的 [imath:0]M = O(2 \iota n^2 + n \cdot log\ n)[/imath:0]，偷懒了一下直接偷@tl2的``derive_M``

PS：不要被 @"Bintou"#55 看到，不然又会被揪出一堆问题了（🤗x

> @"Tover"#p12035 看看能不能抢到2024年的最后一篇帖子抢到了！

@"LOV2"#p12039 看tll的（Doge

HSSP与正交格学习笔记

Tover

原文链接：https://tover.xyz/p/HSSP-note/
看看能不能抢到2024年的最后一篇帖子
以下正文：

现在是个人都会用正交格攻击了，搞得我不学好像就落后似的，所以抽空学习了一下

其中，和正交格相关的最出名的就是HSSP问题了，于是下面就把HSSP问题怼一遍

HSSP问题

HSSP（Hidden Subset Sum Problem）问题大概如下

令M为大整数，整数\alpha_1, \cdots, \alpha_n \in \mathbb{Z}_M，向量\pmb{x_1}, \cdots, \pmb{x_n} \in \mathbb{Z}^m为m维向量，且\pmb{x_i}的元素落在\{0, 1\}中，令
\pmb{h} = (h_1, \cdots, h_m) \equiv \sum_{i=1}^n \alpha_i \pmb{x_i} \pmod M
现知道M和\pmb{h}，求\pmb{\alpha} = (\alpha_1, \cdots, \alpha_n)和\pmb{x_1}, \cdots, \pmb{x_n}

PS：根据Coron的测试数据，M的大小大概是M = O(2 \iota n^2 + n \cdot log\ n)，其中\iota = 0.035，（也有m>n）

和经典背包问题（SSP）的区别是，在HSSP中隐藏（Hidden）了\alpha_1, \cdots, \alpha_n，所以无法直接通过构造格来解

给一个生成问题的样例代码

def genHssp(m, n, M):
  R.<z> = PolynomialRing(Zmod(M))
  x = [R([randint(0, 1) for mi in range(m)]) for ni in range(n)]
  a = [randint(0, M-1) for ni in range(n)]
  h = sum([a[i] * x[i] for i in range(n)])
  return (a, [xi.list() for xi in x]), (M, h.list())

m = 200
n = 100
M = 199999999999997
(a, X), (M, h) = genHssp(m, n, M)

线性代数知识

在讲正交格前先来补充一点线性代数的前置知识，更详细的内容可以参考

Strang, Gilbert. Introduction to linear algebra. Wellesley-Cambridge Press, 2022.

讲到线性代数，第一个想到的应该都是像
A \pmb{x} = \pmb{b}
这样的矩阵和向量的运算

如果不把矩阵和向量看成单纯的数字，而是看成是空间和空间中的点的话，就可以得到著名的四大基本子空间：行空间、列空间、零空间（核空间）和左零空间

给定一个m \times n（m行n列）的矩阵A，可以把A的每一列看成空间的基，用这个行向量的基张成（Span，即进行线性组合）的空间就叫列空间，数学方式表示大概是（如果是格的话就是\forall \pmb{x} \in \mathbb{Z}^n）
\{b \in \mathbb{R}^m\ |\ A \pmb{x} = b,\ \forall \pmb{x} \in \mathbb{R}^n\}
如果把A的每一行看作空间的基，那么张成的空间就叫行空间，数学表示大概是
\{b \in \mathbb{R}^n\ |\ \pmb{x} A = b,\ \forall \pmb{x} \in \mathbb{R}^m\}
如果只关注A \pmb{x} = \pmb{0}这个方程，那么方程的所有解落在零空间（又叫核空间）中
\{\pmb{x} \in \mathbb{R}^n\ |\ A \pmb{x} = \pmb{0}\}
如果把\pmb{x}放在A的左边，得到的空间又叫左零空间
\{\pmb{x} \in \mathbb{R}^m\ |\ \pmb{x} A = \pmb{0}\}
令r为矩阵A的秩（Rank），那么列空间和行空间的维度都是r，零空间的维度是n-r，左零空间的维度是m-r

直观上看，A消元后非零的列和行的数量都是r，零的列是n-r，零的行是m-r，详细的证明可以看书或者网上找找

在四大基本子空间中有一个重要的结论是，行空间与零空间相互垂直，列空间与左零空间相互垂直

可以简单证明一下，令\pmb{b} = \pmb{x}_b A为行空间的一个向量，令\pmb{x}为零空间的一个向量，那么两个向量相乘
\pmb{b} \cdot \pmb{x} = \pmb{x}_b A \pmb{x}
根据零空间的性质，A \pmb{x} = \pmb{0}，所以
\pmb{b} \cdot \pmb{x} = \pmb{x}_b \pmb{0} = 0
也就是任意一个行空间的向量与任意一个零空间的向量都相互垂直，即行空间与零空间相互垂直

列空间与左零空间的证明类似

另一个重要的结论是，行空间与零空间可以张成整个\mathbb{R}^n空间，列空间与左零空间可以张成整个\mathbb{R}^m空间

直观上看，行空间与零空间相互垂直就是不相关，然后两个空间的维度加起来刚好是n

列空间与左零空间的也类似

由这两个结论可得，如果要求一个格的正交格（就是相互垂直的），那么只要求他的零空间（行看作基）或者左零空间（列看作基）就好

Flatter

Flatter是一个比LLL更快的格规约算法

和LLL不同的是，目前SageMath没有原生集成Flatter，所以需要装一个

安装方法可以直接看Github，大概就是

git clone https://github.com/keeganryan/flatter.git
sudo apt install libgmp-dev libmpfr-dev fplll-tools libfplll-dev libeigen3-dev
mkdir build && cd ./build
cmake ..
make -j8
# 软链接路径改成自己的PATH
ln -s `pwd`/bin/flatter [imath:0]HOME/.local/bin
flatter -h

然后我直接抄了@Neobeo的做法，通过子进程调用Flatter二进制应用

# https://github.com/Neobeo/HackTM2023/blob/main/solve420.sage
# faster LLL reduction to replace `M.LLL()` wiith `flatter(M)`
def flatter(M):
    from subprocess import check_output
    from re import findall
    M = matrix(ZZ,M)
    # compile https://github.com/keeganryan/flatter and put it in [/imath:0]PATH
    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)))

在SageMath中用的时候直接把正常用的M.LLL()换成flatter(M)即可

HSSP问题的格通常都比较大，所以用Flatter会比LLL节约不少时间

Nguyen-Stern算法

接下来就看看这个HSSP到底要怎么解，以下内容我参考了

Coron, Jean-Sébastien, and Agnese Gini. "A polynomial-time algorithm for solving the hidden subset sum problem." Annual International Cryptology Conference. Cham: Springer International Publishing, 2020.

还有文章对应的代码，和@tl2的文章，有很多被我忽略掉的内容都可以在这篇文章中看到

Nguyen和Stern的做法是，给定\pmb{h} \pmod M，首先找与\pmb{h}垂直的向量\pmb{u}，那么就有
\pmb{u} \cdot \pmb{h} \equiv \sum_{i=1}^n \alpha_i (\pmb{u} \cdot \pmb{x_i}) \equiv 0 \pmod M
令向量
\pmb{p_u} = ((\pmb{u} \cdot \pmb{x_1}), (\pmb{u} \cdot \pmb{x_2}), \cdots, (\pmb{u} \cdot \pmb{x_n}))
那么问题就可以转化为
\pmb{p_u} \cdot \pmb{\alpha} \equiv 0 \pmod M
也就是\pmb{p_u}和\pmb{\alpha}在模M的情况下相互垂直

然后如果\pmb{u}是短向量的话，那么\pmb{p_u}也会是短向量（因为\pmb{x_i}的元素落在\{0, 1\}中），如果\pmb{p_u}比所有与\pmb{\alpha}垂直的非零向量都短的话，那么就只能是\pmb{p_u} = \pmb{0}

而如果\pmb{p_u} = \pmb{0}的话，就是\pmb{u} \cdot \pmb{x_i} = 0，令L_x是以\pmb{x_1}, \cdots, \pmb{x_n}为基的格，就可以得到\pmb{u} \in L_x，即\pmb{u}是L_x的正交格L_x^\bot中的向量

L_x^\bot的维度是m-n：因为L_x^\bot的基的秩是r=n（n \le m），然后我这里是看成行向量为基的空间（行空间），且L_x的基是n行m列的，所以根据前面的线性代数知识，与行空间垂直的零空间的维度就是m-r = m-n

所以，如果我们可以找到m-n个满足条件的向量\pmb{u}的话，就相当于找到了L_x的正交格L_x^\bot，进而使用L_x^\bot找到L_x，最后由L_x恢复基\pmb{x_1}, \cdots, \pmb{x_n}

于是，最后得到的攻击路线就是

用\pmb{h}构造格基，LLL找到m-n个短向量\pmb{u}_i
用\pmb{u}_i构造格L_x^\bot，用L_x^\bot找L_x的正交补\bar{L_x}（可以看作是和L_x同一个空间，但基不是\pmb{x}_i）
对\bar{L_x}使用BKZ恢复\pmb{x}_i

Part.1 找短向量u

这里我直接用Coron论文中的方法造格

首先拆开
\pmb{u} \cdot \pmb{h} \equiv 0 \pmod M
得到
\sum_{i=1}^m u_i h_i \pmod 0 \pmod M
然后提出其中的u_1
u_1 h_1 + \sum_{i=2}^m u_i h_i \pmod 0 \pmod M
两边乘h_1^{-1} \pmod M
u_1 + \sum_{i=2}^m u_i (h_i h_1^{-1}) \pmod 0 \pmod M
最后拆开模数M，并换一下位置
kM + \sum_{i=2}^m u_i (-h_i h_1^{-1}) = u_1
根据这个关系就可以构造格基
B_1 = \begin{bmatrix} M & \\ -h_2 h_1^{-1} & 1 \\ -h_3 h_1^{-1} & & 1 & \\ \vdots & & & \ddots \\ -h_m h_1^{-1} & & & & 1 \end{bmatrix}_{m \times m}
令
\begin{aligned} \pmb{v}_1 &= (k, u_2, u_3, \cdots, u_m) \\ \pmb{w}_1 &= (u_1, u_2, u_3, \cdots, u_m) \end{aligned}
那么就是
\pmb{w}_1 \cdot B_1 = \pmb{w}_1
根据Coron文章第三章的分析，可以保证对B_1规约后的前m-n行是满足条件的向量\pmb{u}，这个，可以自己看论文...

B = matrix(ZZ, m)
B[0, 0] = M
h0i = Integer(h[0]).inverse_mod(M)
for i in range(1, m):
  B[i, 0] = - h[i] * h0i
  B[i, i] = 1
L = flatter(B)

vh = vector(Zmod(M), h)
print([vector(Zmod(M), list(l)) * vh  for l in L])

另外，还可以构造另一种更直观的格基
B_2 = \begin{bmatrix} M & \\ h_1 & 1 \\ h_2 & & 1 & \\ \vdots & & & \ddots \\ h_m & & & & 1 \end{bmatrix}_{(m+1) \times (m+1)}
令
\begin{aligned} \pmb{v}_2 &= (-k, u_1, u_2, u_3, \cdots, u_m) \\ \pmb{w}_2 &= (0, u_1, u_2, u_3, \cdots, u_m) \end{aligned}
那么就是
\pmb{w}_2 \cdot B_2 = \pmb{w}_2
这个格基在Coron的文章和@tl2的文章都有类似的，可以去参考一下

Part.2 恢复格Lx

这一步就比较简单

首先根据上面分析，用L的前m-n就可以构造L_x^\bot

然后只需要求L_x^\bot的零空间就可以得到L_x的正交补\bar{L_x}

这里我直接用SageMath的right_kernel求令空间，亲测把algorithm指定为pari的话会快一点

Lxo = matrix(ZZ, L[:m-n])
Lxc = Lxo.right_kernel(algorithm='pari').matrix() # faster
print('right_kernel done.')

Lx_real = matrix(ZZ, [xi + [0] * (m - len(xi)) for xi in X])
rsc = Lxc.row_space()
print([xi in rsc for xi in Lx_real])

Part.3 恢复xi

理论上直接对Lxc求个LLL或者BKZ就可以恢复\pmb{x_1}, \cdots, \pmb{x_n}，但实际上并没有

细看一下，\pmb{x_1}, \cdots, \pmb{x_n}的元素在\{0, 1\}中，这在01背包问题中也遇到过类似的问题，所以可以利用类似的解决方法，即把\pmb{x_1}, \cdots, \pmb{x_n}转化为
2\pmb{x_1}-\pmb{1}, 2\pmb{x_2}-\pmb{1}, \cdots, 2\pmb{x_n}-\pmb{1}
就可以把元素转化到(-1, 1)中

虽然这对向量长度影响不大，但乘上去的系数2会增大格基的行列式，就更容易筛掉无关的变量

于是就可以构造这样一个格基（其中E是元素全为1、大小和\bar{Lx}一样的矩阵）
B_3 = \begin{bmatrix} -E \\ \hline 2 \bar{Lx} \end{bmatrix}_{2n \times m}
令（U是n \times n，看作一种映射就好）
U \bar{L_x} = L_x
可以得到关系
[I_{n}, U]_{n \times 2n} \cdot B_3 = [2 U \bar{Lx} - E]_{n \times m} = [2L_x - E] = \begin{bmatrix} 2\pmb{x_1}-\pmb{1} \\ \vdots \\ 2\pmb{x_n}-\pmb{1} \end{bmatrix}
所以对B_3归约后就可能得到2\pmb{x_1}-\pmb{1}, 2\pmb{x_2}-\pmb{1}, \cdots, 2\pmb{x_n}-\pmb{1}

进一步观察发现其实B_3中的E的每一行都是相关的（甚至相同的），实际作用的就一行，对B_3规约后也发现有n-1行全为0

所以不妨令\pmb{e}为全为1的行向量，就可以把格简化为
B_4 = \begin{bmatrix} -\pmb{e} \\ \hline 2 \bar{Lx} \end{bmatrix}_{n+1 \times m}
参考代码

 def checkMatrix(M, wl=[-1, 1]):
  M = [list(_) for _ in list(M)]
  ml = list(set(flatten(M)))
  logging.debug(ml)
  return sorted(ml) == sorted(wl)
    
e = matrix(ZZ, [1] * m)
B = block_matrix([[-e], [2*Lxc]])
Lx = B.BKZ()
assert checkMatrix(Lx)
assert len(set(Lx[0])) == 1

最后恢复一下\pmb{x}_i和\alpha_i

Lx = Lx[1:]
E = matrix(ZZ, [[1 for c in range(Lxc.ncols())] for r in range(Lxc.nrows())])
Lx = (Lx + E) / 2

Lx2 = []
e = vector(ZZ, [1] * m)
rsc = Lxc.row_space()
for lx in Lx:
  if lx in rsc:
    Lx2 += [lx]
    continue
  lx = e - lx
  if lx in rsc:
    Lx2 += [lx]
    continue
  print('Something wrong?')
Lx = matrix(Zmod(M), Lx2)
vh = vector(Zmod(M), h)
va = Lx.solve_left(vh)

PS：其实用\begin{bmatrix} 2 \bar{Lx} \\ \hline -\pmb{e} \end{bmatrix}做格也可以，但是干扰的那一行就不会放在第一行，还要另外写代码找出来（就是全为1或者全为-1的行）

模板/参考代码

最后把上面所有的代码整合一下

import logging
logging.basicConfig(
    level=logging.DEBUG,
    format="[%(levelname)s] %(message)s"
)

# https://github.com/Neobeo/HackTM2023/blob/main/solve420.sage
# faster LLL reduction to replace `M.LLL()` wiith `flatter(M)`
def flatter(M, **kwds):
    from subprocess import check_output
    from re import findall
    M = matrix(ZZ,M)
    # compile https://github.com/keeganryan/flatter and put it in [imath:0]PATH
    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)))

def genHssp(m, n, M):
  R.<z> = PolynomialRing(Zmod(M))
  x = [R([randint(0, 1) for mi in range(m)]) for ni in range(n)]
  a = [randint(0, M-1) for ni in range(n)]
  h = sum([a[i] * x[i] for i in range(n)])
  return (a, [xi.list() for xi in x]), (M, h.list())

def checkMatrix(M, wl=[-1, 1]):
  M = [list(_) for _ in list(M)]
  ml = list(set(flatten(M)))
  logging.debug(ml)
  return sorted(ml) == sorted(wl)

def Nguyen_Stern(h, m, n, M):
  B = matrix(ZZ, m)
  B[0, 0] = M
  h0i = Integer(h[0]).inverse_mod(M)
  for i in range(1, m):
    B[i, 0] = - h[i] * h0i
    B[i, i] = 1
  #L = B.BKZ()	# slooooooow
  L = flatter(B)
  logging.info('flatter done.')

  '''
  vh = vector(Zmod(M), h)
  logging.debug([vector(Zmod(M), list(l)) * vh  for l in L])
  '''

  Lxo = matrix(ZZ, L[:m-n])
  Lxc = Lxo.right_kernel(algorithm='pari').matrix() # faster
  logging.info('right_kernel done.')

  '''
  try:
    Lx_real = matrix(ZZ, [xi + [0] * (m - len(xi)) for xi in X])
    rsc = Lxc.row_space()
    logging.debug([xi in rsc for xi in Lx_real])
  except:
    pass
  '''

  e = matrix(ZZ, [1] * m)
  B = block_matrix([[-e], [2*Lxc]])
  Lx = B.BKZ()
  logging.info('BKZ done.')
  assert checkMatrix(Lx)
  assert len(set(Lx[0])) == 1

  Lx = Lx[1:]
  E = matrix(ZZ, [[1 for c in range(Lxc.ncols())] for r in range(Lxc.nrows())])
  Lx = (Lx + E) / 2

  Lx2 = []
  e = vector(ZZ, [1] * m)
  rsc = Lxc.row_space()
  for lx in Lx:
    if lx in rsc:
      Lx2 += [lx]
      continue
    lx = e - lx
    if lx in rsc:
      Lx2 += [lx]
      continue
    logging.warning('Something wrong?')
  Lx = matrix(Zmod(M), Lx2)

  vh = vector(Zmod(M), h)
  va = Lx.solve_left(vh)
  return Lx, va

# stolen from https://github.com/tl2cents/Implementation-of-Cryptographic-Attacks/blob/main/MultivariateHSSP/A%20Polynomial-Time%20Algorithm%20for%20Solving%20the%20Hidden%20Subset%20Sum%20Problem.ipynb
def derive_M(n):
    iota=0.035
    Mbits=int(2 * iota * n^2 + n * log(n,2))
    M = random_prime(2^Mbits, proof = False, lbound = 2^(Mbits - 1))
    return Integer(M)

m = 200
n = 100
M = derive_M(n)
(a, X), (M, h) = genHssp(m, n, M)
logging.debug('m: %d | n: %d' % (m, n))
logging.debug('%s, %s' % (M, M.nbits()))

Lx, va = Nguyen_Stern(h, m, n, M)
print(sorted(va) == sorted(a))

M的生成采用了Coron的 M = O(2 \iota n^2 + n \cdot log\ n)，偷懒了一下直接偷@tl2的derive_M

0x0001

Tover 看看能不能抢到2024年的最后一篇帖子

抢到了！

Tover

PS：不要被 @Bintou 看到，不然又会被揪出一堆问题了（🤗x

LOV2

Tover 大声密谋

Bintou

牛啊！牛啊！我要好好学习。

LOV2

刚好前段时间遇到一道题，应该就是得用正交格，这就有教程了，GOD！

Tover

LOV2 看tll的（Doge

deebato

牛啊牛啊，毕设就摸的这个