{"id":219,"date":"2025-07-07T19:11:00","date_gmt":"2025-07-07T11:11:00","guid":{"rendered":"http:\/\/www.triode.cc\/?p=219"},"modified":"2025-09-30T23:56:46","modified_gmt":"2025-09-30T15:56:46","slug":"lwe","status":"publish","type":"post","link":"https:\/\/www.triode.cc\/index.php\/2025\/07\/07\/lwe\/","title":{"rendered":"LWE"},"content":{"rendered":"\n
\n

\u53c2\u8003\u8d44\u6599\uff1a<\/p>\n\n\n\n

    \n
  1. Lattice-based Cryptography: A survey on the security of the lattice-based NIST finalists<\/a><\/li>\n\n\n\n
  2. An Experimental Study of Kannan\u2019s Embedding Technique for the Search LWE Problem | SpringerLink<\/a><\/li>\n\n\n\n
  3. A detailed analysis of primal attack and its variants | Science China Information Sciences<\/a><\/li>\n<\/ol>\n<\/blockquote>\n\n\n\n

    LWE\u4ee5\u53caRLWE<\/h2>\n\n\n\n

    LWE<\/h3>\n\n\n\n

    \u8bbe\\(n,m\\)\u4ee5\u53ca\\(q\\)\u4e3a\u6b63\u6574\u6570\uff08\u5176\u4e2d\\(q\\)\u4e00\u822c\u4e3a\u8d28\u6570\uff09\uff0c\\(\\chi\\)\u4e3a\u4e00\u4e2a\\(\\mathbb{Z}^{m}\\)\u4e0a\u7684\u6982\u7387\u5206\u5e03\uff0c\u5e76\u8bbe\\(\\pmb{s}\\in(\\mathbb{Z}\/q\\mathbb{Z})^n\\)\u662f\u4e00\u6761\u201c\u79d8\u5bc6\u5411\u91cf\u201d\uff0c\u5728\\((\\mathbb{Z}\/q\\mathbb{Z})^{m\\times n}\\)\u4e0a\u5747\u5300\u968f\u673a\u9009\u53d6\u77e9\u9635\\(\\pmb{A}\\)\uff0c\u5e76\u5728\\(\\mathbb{Z}^m\\)\u4e0a\u9009\u53d6\u4e00\u4e2a\u5206\u5e03\u670d\u4ece\\(\\chi\\)\u7684\u5c0f\u5411\u91cf\\(\\pmb{e}\\)\u4f5c\u4e3a\u566a\u58f0\uff0c\u8ba1\u7b97\uff1a<\/p>\n\n\n\n

    $$
    \\pmb{b}\\equiv \\pmb{A}\\pmb{s}+\\pmb{e}\\pmod{q}
    $$<\/p>\n\n\n\n

    \u5e76\u7ed9\u51fa\\((\\pmb{A},\\pmb{b})\\)\uff0c\u90a3\u4e48\u4e00\u822c\u7684LWE\u95ee\u9898\uff08\u4e00\u822c\u79f0\u4e3a\u641c\u7d22LWE\uff0cSearch-LWE\uff09\u5373\u4e3a\u7ed9\u5b9a\\((\\pmb{A},\\pmb{b})\\)\uff0c\u8fd8\u539f\u51fa\\(\\pmb{s}\\).<\/p>\n\n\n\n

    \u73afLWE\uff08Ring-LWE\uff0cRLWE\uff09<\/h3>\n\n\n\n

    \u8bbe\\(n\\)\u4e3a\u4e00\u4e2a\u5927\u4e8e\u7b49\u4e8e\\(1\\)\u7684\u6574\u6570\uff0c\\(q\\)\u4e3a\u4e00\u8d28\u6570\uff0c\u5f97\u5230\u5546\u73af\uff1a<\/p>\n\n\n\n

    $$
    R=\\frac{\\mathbb{Z}[x]}{(x^n+1)},R_q=\\frac{(\\mathbb{Z}\/q\\mathbb{Z})[x]}{(x^n+1)}
    $$<\/p>\n\n\n\n

    \u800c\\(\\chi\\)\u4e3a\\(R\\)\u4e0a\u7684\u4e00\u4e2a\u6982\u7387\u5206\u5e03\uff0c\u9009\u53d6\u968f\u673a\u79d8\u5bc6\u591a\u9879\u5f0f\\(s(x)\\in R_q\\)\u4ee5\u53ca\u968f\u673a\u591a\u9879\u5f0f\\(A(x)\\in R_q\\)\uff0c\u5e76\u5728\\(R_q\\)\u4e0a\u9009\u53d6\u4e00\u4e2a\u5206\u5e03\u670d\u4ece\\(\\chi\\)\u7684\u591a\u9879\u5f0f\\(e\\)\u4f5c\u4e3a\u566a\u58f0\uff0c\u8ba1\u7b97\uff1a<\/p>\n\n\n\n

    $$
    b(x)=A(x)s(x)+e(x)
    $$<\/p>\n\n\n\n

    \u641c\u7d22RLWE\u95ee\u9898\u5373\u4e3a\u7ed9\u51fa\u82e5\u5e72\u7ec4\\((A_i(x),b_i(x))\\)\uff0c\u5e76\u4ece\u4e2d\u6062\u590d\u51fa\\(s(x)\\).<\/p>\n\n\n\n

    \u901a\u8fc7\u683c\u65b9\u6cd5\u6c42\u89e3LWE\u53ca\u5176\u53d8\u79cd<\/h2>\n\n\n\n

    LWE<\/h3>\n\n\n\n

    \u89c2\u5bdfLWE\u7684\u95ee\u9898\u5f62\u5f0f\uff1a<\/p>\n\n\n\n

    $$
    \\pmb{b}\\equiv \\pmb{A}\\pmb{s}+\\pmb{e}\\pmod{q}
    $$<\/p>\n\n\n\n

    \u4f5c\u4e3a\u653b\u51fb\u8005\uff0c\u6211\u4eec\u8981\u901a\u8fc7\u5df2\u77e5\u7684\\(\\pmb{A},\\pmb{b}\\)\u6765\u6062\u590d\\(\\pmb{s}\\)\uff0c\u4e14\\(\\pmb{e}\\)\u662f\u4e00\u4e2a\u672a\u77e5\u7684\u5c0f\u5411\u91cf\uff0c\u663e\u7136\u8fd9\u662f\u4e00\u4e2aCVP\u95ee\u9898\uff0c\u9996\u5148\u5c06\u539f\u95ee\u9898\u8f6c\u6362\u4e3a\uff1a<\/p>\n\n\n\n

    $$
    \\pmb{b}+q\\pmb{k}=\\pmb{A}\\pmb{s}+\\pmb{e}
    $$<\/p>\n\n\n\n

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

    $$
    q\\pmb{k}-\\pmb{A}\\pmb{s}+\\pmb{b}=\\pmb{e}
    $$<\/p>\n\n\n\n

    \u663e\u7136\u53ef\u4ee5\u6784\u9020\u51fa\u5982\u4e0b\u683c\u57fa\uff1a<\/p>\n\n\n\n

    $$
    \\pmb{B} = \\left(\\begin{matrix}
    q\\pmb{I}_m&0&0\\\\
    -\\pmb{A}^T&\\pmb{I}_n&0\\\\
    \\pmb{b}&0&1
    \\end{matrix}\\right)
    $$<\/p>\n\n\n\n

    \uff08\u5b9e\u9645\u4e0a\u662f\u5229\u7528Kannan\u5d4c\u5165\u6cd5\u6765\u5c06CVP\u8f6c\u6362\u4e3aSVP\u6c42\u89e3\uff09\u3002\u5bf9\u4e0a\u8ff0\u683c\u57fa\u6709\u5982\u4e0b\u5173\u7cfb\uff1a<\/p>\n\n\n\n

    $$
    (\\pmb{k}^{T},\\pmb{s}^{T},1)\\pmb{B}=(\\pmb{e}^{T},\\pmb{s}^{T},1)
    $$<\/p>\n\n\n\n

    \u901a\u8fc7\u683c\u57fa\u89c4\u7ea6\u7b97\u6cd5\uff08\u5982LLL\uff0cBKZ\u7b49\uff09\u5373\u53ef\u5f97\u5230\u77ed\u5411\u91cf\\((\\pmb{e}^{T},\\pmb{s}^{T},1)\\)\uff0csage\u5b9e\u73b0\u5982\u4e0b\uff1a<\/p>\n\n\n\n

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