{"id":252,"date":"2025-08-27T18:56:00","date_gmt":"2025-08-27T10:56:00","guid":{"rendered":"http:\/\/www.triode.cc\/?p=252"},"modified":"2025-10-02T15:35:29","modified_gmt":"2025-10-02T07:35:29","slug":"hssp","status":"publish","type":"post","link":"https:\/\/www.triode.cc\/index.php\/2025\/08\/27\/hssp\/","title":{"rendered":"\u9690\u5b50\u96c6\u548c\u95ee\u9898(Hidden Subset Sum Problem)"},"content":{"rendered":"\n
\n

\u53c2\u8003\u8d44\u6599\uff1aA Polynomial-Time Algorithm for Solving the Hidden Subset Sum Problem<\/a><\/p>\n<\/blockquote>\n\n\n\n

\u524d\u7f6e\u77e5\u8bc6<\/h2>\n\n\n\n

\u6b63\u4ea4\u683c<\/h3>\n\n\n\n

\u5bf9\u4e8e\\(\\mathbb{Z}^m\\)\u4e0a\u4e00\u4e2a\u683c\\(\\mathcal{L}\\)\uff0c\u5b9a\u4e49\u5176\u6b63\u4ea4\u683c\u4e3a\uff1a<\/p>\n\n\n\n

$$
\\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\\}
$$<\/p>\n\n\n\n

\u5b8c\u5907\u683c<\/h3>\n\n\n\n

\u5bf9\u4e8e\\(\\mathbb{Z}^m\\)\u4e0a\u4e00\u4e2a\u683c\\(\\mathcal{L}\\)\uff0c\u5b9a\u4e49\u5176\u5b8c\u5907\u683c\u4e3a\\(\\overline{\\mathcal{L}}=(\\mathcal{L}^{\\bot})^{\\bot}\\).\u663e\u7136\u7684\uff0c\\(\\mathcal{L}\\)\u4e3a\\(\\overline{\\mathcal{L}}\\)\u7684\u4e00\u4e2a\u6ee1\u79e9\u5b50\u683c.<\/p>\n\n\n\n

\u95ee\u9898\u7b80\u8ff0<\/h2>\n\n\n\n

\u8bbe\\(M\\)\u4e3a\u4e00\u6574\u6570\uff0c\u8bbe\\(\\alpha_1,\\alpha_2,\\cdots,\\alpha_n\\)\u662f\\(\\mathbb{Z}\/M\\mathbb{Z}\\)\u4e0a\u968f\u673a\u9009\u53d6\u7684\\(n\\)\u4e2a\u6574\u6570\uff0c\\(\\pmb{x}_1,\\pmb{x}_2,\\cdots,\\pmb{x}_n\\)\u4e3a\\(\\mathbb{Z}^{m}\\)\u4e0a\u968f\u673a\u9009\u53d6\u7684\\(m\\)\u4e2a\\(0-1\\)\u5411\u91cf\uff08\u5373\\(\\pmb{x}_1,\\pmb{x}_2,\\cdots,\\pmb{x}_n\\in\\left\\{0,1\\right\\}^m\\)\uff09\uff0c\u4ee4 <\/p>\n\n\n\n

$$ \\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}
$$<\/p>\n\n\n\n

\u9690\u5b50\u96c6\u548c\u95ee\u9898\uff08Hidden Subset Sum Problem\uff0c\u7b80\u79f0HSSP\uff09\u5373\u4e3a\u5df2\u77e5\u6574\u6570\\(M\\)\u4ee5\u53ca\u5411\u91cf\\(\\pmb{h}\\)\uff0c\u6062\u590d\\((\\alpha_1,\\alpha_2,\\cdots,\\alpha_n)\\)\u4ee5\u53ca\\((\\pmb{x_1},\\pmb{x_2},\\cdots,\\pmb{x_n})\\).<\/p>\n\n\n\n

Nguyen-Stern\u7b97\u6cd5<\/h2>\n\n\n\n

\u6c42\u89e3HSSP\u7684\u4e00\u79cd\u6bd4\u8f83\u884c\u4e4b\u6709\u6548\u7684\u65b9\u6cd5\u5c31\u662fNguyen-Stern\u7b97\u6cd5\uff0c\u8fd9\u4e2a\u7b97\u6cd5\u4e3b\u8981\u5206\u4e3a\u4e24\u6b65\uff1a<\/p>\n\n\n\n

    \n
  1. \u4ece\\(\\pmb{h}\\)\u4e2d\u5f97\u5230\u7531\\(\\pmb{x_1},\\pmb{x_2},\\cdots,\\pmb{x_n}\\)\u6240\u751f\u6210\u7684\u683c\\(\\mathcal{L}_{\\pmb{x}}\\)\u7684\u5b8c\u5907\u683c\\(\\overline{\\mathcal{L}}_{\\pmb{x}}\\).<\/li>\n\n\n\n
  2. \u4ece\\(\\overline{\\mathcal{L}}_{\\pmb{x}}\\)\u4e2d\u6062\u590d\u5411\u91cf\\(\\pmb{x_1},\\pmb{x_2},\\cdots,\\pmb{x_n}\\)\uff0c\u4ece\u800c\u6839\u636e\\(\\pmb{h},M,\\pmb{x_1},\\pmb{x_2},\\cdots,\\pmb{x_n}\\)\u6062\u590d\u51fa\\(\\alpha_1,\\alpha_2,\\cdots,\\alpha_n\\).<\/li>\n<\/ol>\n\n\n\n

    \u7b2c\u4e00\u6b65<\/h3>\n\n\n\n

    \u9996\u5148\u6211\u4eec\u9700\u8981\u901a\u8fc7\u6b63\u4ea4\u683c\u653b\u51fb\uff08Orthogonal Lattice Attack\uff09\u6765\u83b7\u5f97\\(\\overline{\\mathcal{L}}_{\\pmb{x}}\\)\uff0c\u6211\u4eec\u8bbe\u6240\u6709\u6a21\\(M\\)\u4e0b\u4e0e\u5411\u91cf\\(\\pmb{h}\\)\u6b63\u4ea4\u7684\u5411\u91cf\u6240\u6784\u6210\u7684\u683c\u4e3a\uff1a <\/p>\n\n\n\n

    $$ \\mathcal{L}_0=\\left\\{\\pmb{u}\\in\\mathbb{Z}^m\\mid\\langle\\pmb{u},\\pmb{h}\\rangle\\equiv0\\pmod{M}\\right\\} $$ <\/p>\n\n\n\n

    \u663e\u7136\u7684\uff0c\u5bf9\u4e8e\\(\\mathcal{L}_0\\)\u4e2d\u4efb\u4e00\u5411\u91cf\\(\\pmb{u}\\)\uff0c\u5fc5\u7136\u6709\uff1a <\/p>\n\n\n\n

    $$
    \\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}
    $$ <\/p>\n\n\n\n

    \u53ef\u4ee5\u77e5\u9053\uff0c\u5411\u91cf\\((\\langle\\pmb{u},\\pmb{x}_1\\rangle,\\langle\\pmb{u},\\pmb{x}_2\\rangle,\\cdots,\\langle\\pmb{u},\\pmb{x}_n\\rangle)\\)\u4e0e\u5411\u91cf\\((\\alpha_1,\\alpha_2,\\cdots,\\alpha_n)\\)\u5728\u6a21\\(M\\)\u4e0b\u662f\u6b63\u4ea4\u7684\uff0c\u56e0\u4e3a\\(\\pmb{x}_1,\\pmb{x}_2,\\cdots,\\pmb{x}_n\\)\uff0c\u90a3\u4e48\u5982\u679c\\(\\pmb{u}\\)\u8db3\u591f\u77ed\u7684\u8bdd\uff0c\u5411\u91cf\\((\\langle\\pmb{u},\\pmb{x}_1\\rangle,\\langle\\pmb{u},\\pmb{x}_2\\rangle,\\cdots,\\langle\\pmb{u},\\pmb{x}_n\\rangle)\\)\u4e5f\u4f1a\u6bd4\u8f83\u77ed\uff0c\u800c\u5982\u679c\u5411\u91cf\\((\\langle\\pmb{u},\\pmb{x}_1\\rangle,\\langle\\pmb{u},\\pmb{x}_2\\rangle,\\cdots,\\langle\\pmb{u},\\pmb{x}_n\\rangle)\\)\u6bd4\u4e0e\\((\\alpha_1,\\alpha_2,\\cdots,\\alpha_n)\\)\u5728\u6a21\\(M\\)\u4e0b\u6b63\u4ea4\u7684\u975e\u96f6\u5411\u91cf\u90fd\u77ed\u7684\u8bdd\uff0c\u90a3\u4e48\u5b83\u53ea\u80fd\u662f\u96f6\u5411\u91cf\uff0c\u4e5f\u5c31\u662f\u6709\uff1a <\/p>\n\n\n\n

    $$ (\\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)
    $$ <\/p>\n\n\n\n

    \u90a3\u4e48\u6211\u4eec\u53ef\u4ee5\u901a\u8fc7\u4e00\u4e9b\u65b9\u6cd5\u6784\u9020\\(\\mathcal{L}_0\\)\u5e76\u8fdb\u884c\u89c4\u7ea6\uff0c\u53d6\u51fa\u7ea6\u51cf\u57fa\u7684\u524d\\(m-n\\)\u4e2a\u77ed\u5411\u91cf\\(\\pmb{u}_1,\\pmb{u}_2,\\cdots,\\pmb{u}_{m-n}\\)\u53ef\u4ee5\u6784\u6210\\(\\mathcal{L}_{\\pmb{x}}^{\\bot}\\)\uff0c\u518d\u6c42\u5176\u6b63\u4ea4\u683c\u5373\u53ef\u5f97\u5230\u5b8c\u5907\u683c\\(\\overline{\\mathcal{L}}_{\\pmb{x}}=(\\mathcal{L}_{\\pmb{x}}^{\\bot})^{\\bot}\\).<\/p>\n\n\n\n

    \u5728\u53c2\u8003\u8d44\u6599\u4e2d\u7ed9\u51fa\u4e00\u79cd\u901a\u8fc7\\(\\pmb{h}\\)\u6765\u6784\u9020\\(\\mathcal{L}_0\\)\u7684\u65b9\u6cd5\uff0c\u6211\u4eec\u8bbe\\(\\pmb{h}=(h_1,h_2,\\cdots,h_n)\\)\uff0c\u5982\u679c\\(\\gcd(h_1,M)=1\\)\uff0c\u90a3\u4e48\u5bf9\u4e8e\\(\\pmb{u}=(u_1,u_2,\\cdots,u_m)\\in\\mathcal{L}_0\\)\u6211\u4eec\u53ef\u4ee5\u5f97\u5230\uff1a <\/p>\n\n\n\n

    $$
    \\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}
    $$<\/p>\n\n\n\n

    \u4e24\u8fb9\u540c\u4e58\\(h_1^{-1}\\)\u6709\uff1a<\/p>\n\n\n\n


    $$
    u_1+\\sum_{i=2}^mu_ih_{1}^{-1}h_i\\equiv0\\pmod{M}
    $$<\/p>\n\n\n\n

    \u5373\uff1a<\/p>\n\n\n\n

    $$
    u_1+\\sum_{i=2}^m(u_ih_{1}^{-1}h_i\\mod{M})=kM
    $$<\/p>\n\n\n\n

    \u90a3\u4e48\u53ef\u4ee5\u5f97\u5230\u4e00\u7ebf\u6027\u5173\u7cfb\uff1a<\/p>\n\n\n\n

    $$
    u_1=kM-\\sum_{i=2}^m(u_ih_{1}^{-1}h_i\\mod{M})
    $$<\/p>\n\n\n\n

    \u901a\u8fc7\u8fd9\u4e00\u7ebf\u6027\u5173\u7cfb\u6211\u4eec\u53ef\u4ee5\u6784\u9020\u51fa\u683c\uff1a<\/p>\n\n\n\n

    $$
    \\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)
    $$ <\/p>\n\n\n\n

    \u5bf9\u4e8e\u8fd9\u4e2a\u683c\uff0c\u6709\uff1a <\/p>\n\n\n\n

    $$
    (k,u_2,\\cdots,u_m)\\mathcal{L}_0=(u_1,u_2,\\cdots,u_m)
    $$ <\/p>\n\n\n\n

    \u6839\u636e\u524d\u9762\u7684\u5206\u6790\u53ef\u4ee5\u77e5\u9053\u8fd9\u4e2a\u683c\u89c4\u7ea6\u540e\u5f97\u5230\u7684\u7ea6\u51cf\u57fa\u7684\u524d\\(m-n\\)\u4e2a\u77ed\u5411\u91cf\\(\\pmb{u}_1,\\pmb{u}_2,\\cdots,\\pmb{u}_{m-n}\\)\u53ef\u4ee5\u6784\u6210\\(\\mathcal{L}_{\\pmb{x}}^{\\bot}\\)\uff0c\u5728\u83b7\u5f97\\(\\mathcal{L}_{\\pmb{x}}^{\\bot}\\)\u4e4b\u540e\uff0c\u53ea\u9700\u8981\u6c42\\(\\mathcal{L}_{\\pmb{x}}^{\\bot}\\)\u7684\u6838\u7a7a\u95f4\u5373\u53ef\u5f97\u5230\\(\\overline{\\mathcal{L}}_{\\pmb{x}}=(\\mathcal{L}_{\\pmb{x}}^{\\bot})^{\\bot}\\).<\/p>\n\n\n\n

    \u7b2c\u4e8c\u6b65<\/h3>\n\n\n\n

    \u56e0\u4e3a\\(\\mathcal{L}_{\\pmb{x}}\\)\u4e3a\\(\\overline{\\mathcal{L}}_{\\pmb{x}}\\)\u7684\u4e00\u4e2a\u5b50\u683c\uff0c\u6240\u4ee5\\(\\overline{\\mathcal{L}}_{\\pmb{x}}\\)\u4e2d\u5fc5\u7136\u662f\u5305\u542b\\(\\pmb{x}_1,\\pmb{x}_2,\\cdots,\\pmb{x}_n\\)\u7684\uff0c\u53c8\u56e0\u4e3a\\(\\pmb{x}_1,\\pmb{x}_2,\\cdots,\\pmb{x}_n\\in\\left\\{0,1\\right\\}^m\\)\uff0c\u90a3\u4e48\u76f4\u63a5\u5bf9\\(\\overline{\\mathcal{L}}_{\\pmb{x}}\\)\u8fdb\u884c\u89c4\u7ea6\u5927\u6982\u7387\u662f\u53ef\u4ee5\u5f97\u5230\\(\\pmb{x}_1,\\pmb{x}_2,\\cdots,\\pmb{x}_n\\)\u7684\uff0c\u4e5f\u53ef\u4ee5\u6784\u9020\u683c\uff1a <\/p>\n\n\n\n

    $$
    \\mathcal{L}_{\\pmb{x}}’=\\left(\\begin{matrix}2\\mathcal{L_{\\pmb{x}}}\\\\-\\pmb{e}\\end{matrix}\\right)
    $$<\/p>\n\n\n\n

    \u6765\u89c4\u7ea6\u6c42\u5f97\\(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\\)\uff08\u5176\u4e2d\\(\\pmb{e}=(1,1,\\cdots,1)\\)\uff0c\u8981\u53bb\u6389\u89c4\u7ea6\u540e\u7684\u683c\u57fa\u91cc\u9762\u5168\u4e3a\\(1\\)\u6216\u5168\u4e3a\\(-1\\)\u7684\u884c\u5411\u91cf\uff0c\u4e14\u6709\u90e8\u5206\u5411\u91cf\u6c42\u51fa\u662f\\(\\pmb{e}-2\\pmb{x}_i\\)\uff09. \u5728\u83b7\u5f97\\(\\pmb{x}_1,\\pmb{x}_2,\\cdots,\\pmb{x}_n\\)\u4e4b\u540e\uff0c\u53ea\u9700\u8981\u6c42\u89e3\u65b9\u7a0b\uff1a<\/p>\n\n\n\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)
    $$<\/p>\n\n\n\n

    \u5c31\u53ef\u4ee5\u6062\u590d\u51fa\\(\\alpha_1,\\alpha_2,\\cdots,\\alpha_n\\).<\/p>\n\n\n\n

    \u4ee3\u7801\u5b9e\u73b0<\/h3>\n\n\n\n

    \u6839\u636e\u4e0a\u8ff0\u5206\u6790\uff0c\u901a\u8fc7\u5982\u4e0b\u4ee3\u7801\u5c31\u53ef\u4ee5\u6c42\u89e3HSSP\uff08\u56e0\u4e3a\u683c\u8f83\u5927\uff0c\u6240\u4ee5\u5728\u6b63\u4ea4\u683c\u653b\u51fb\u4e00\u6b65\u4e2d\u4f7f\u7528flatter\u8fdb\u884c\u52a0\u901f\uff09<\/p>\n\n\n\n

    <\/circle><\/circle><\/circle><\/g><\/svg><\/span>