{"id":48327,"date":"2025-07-30T11:37:30","date_gmt":"2025-07-30T03:37:30","guid":{"rendered":"https:\/\/www.wsisp.com\/helps\/48327.html"},"modified":"2025-07-30T11:37:30","modified_gmt":"2025-07-30T03:37:30","slug":"%e9%9a%90%e7%a7%81%e8%ae%a1%e7%ae%97%e5%9f%ba%e7%a1%80%e5%ad%a6%e4%b9%a0-%e5%90%8c%e6%80%81%e5%8a%a0%e5%af%86%e6%8a%80%e6%9c%af%ef%bc%88%e4%bb%8e%e9%83%a8%e5%88%86%e5%90%8c%e6%80%81","status":"publish","type":"post","link":"https:\/\/www.wsisp.com\/helps\/48327.html","title":{"rendered":"\u9690\u79c1\u8ba1\u7b97\u57fa\u7840\u5b66\u4e60\u2014\u2014\u540c\u6001\u52a0\u5bc6\u6280\u672f\uff08\u4ece\u90e8\u5206\u540c\u6001\u5230\u5168\u540c\u6001\u7684\u53d1\u5c55\u4e0e\u7b97\u6cd5\u4ecb\u7ecd 4\/4\uff09"},"content":{"rendered":"

\u672c\u6587\u4e3b\u8981\u8bb0\u5f55\u9690\u79c1\u8ba1\u7b97\u4e2d\u7684\u540c\u6001\u52a0\u5bc6（Homomorphic Encryption，HE）\u6280\u672f，\u5305\u62ec\u90e8\u5206\u540c\u6001\u52a0\u5bc6（RSA\u3001GM\u3001ElGamal\u3001Paillier）\u3001\u8fd1\u4f3c\u540c\u6001\u52a0\u5bc6（BGN）\u3001\u6709\u9650\u7ea7\u6570\u5168\u540c\u6001\u52a0\u5bc6\u548c\u5168\u540c\u6001\u52a0\u5bc6（DGHV\u3001BGV\u3001BFV\u3001CKKS\u3001GSW\u3001FHEW\u3001TFHE）\u7b49\u6280\u672f，\u4ec5\u4f9b\u53c2\u8003\u3002<\/p>\n

\u7531\u4e8e\u7bc7\u5e45\u9650\u5236，\u5c06\u540c\u6001\u52a0\u5bc6\u6280\u672f\u7684\u4ecb\u7ecd\u5206\u4e3a\u56db\u4e2a\u90e8\u5206，\u7b2c\u4e00\u90e8\u5206\u8bb2\u8ff0\u90e8\u5206\u540c\u6001\u52a0\u5bc6\u548c\u8fd1\u4f3c\u540c\u6001\u52a0\u5bc6\u6280\u672f；\u7b2c\u4e8c\u90e8\u5206\u8bb2\u8ff0 Bootstrapping \u548c DGHV\u3001BGV \u5168\u540c\u6001\u52a0\u5bc6\u65b9\u6848；\u7b2c\u4e09\u90e8\u5206\u8bb2\u8ff0 SIMD \u6253\u5305\u6280\u672f\u4e0e BFV\u3001CKKS \u5168\u540c\u6001\u52a0\u5bc6\u65b9\u6848；\u7b2c\u56db\u90e8\u5206\u8bb2\u8ff0 GSW\u3001FHEW\u3001TFHE \u5168\u540c\u6001\u52a0\u5bc6\u65b9\u6848\u3002<\/p>\n

\u5728\u672c\u6587\u4e2d\u4e3a\u7b80\u5316\u8868\u793a，\u5c06\u52a0\u5bc6\u8bb0\u4e3a Enc(\u22c5)Enc(\\\\cdot)<\/span><\/span>E<\/span>n<\/span>c<\/span>(<\/span>\u22c5<\/span>)<\/span><\/span><\/span><\/span><\/span>，\u89e3\u5bc6\u8bb0\u4e3a Dec(\u22c5)Dec(\\\\cdot)<\/span><\/span>Dec<\/span>(<\/span>\u22c5<\/span>)<\/span><\/span><\/span><\/span><\/span>，\u4e0d\u6807\u660e\u4f7f\u7528\u7684\u516c\u94a5\u548c\u79c1\u94a5\u4ee3\u8868\u53ea\u6709\u4e00\u5bf9\u516c\u79c1\u94a5\u3002\u672c\u6587\u4e2d\u4ecb\u7ecd\u7684\u52a0\u5bc6\u65b9\u6848\u57fa\u672c\u90fd\u4f9d\u8d56\u4e8e\u5404\u79cd\u8ba1\u7b97\u96be\u9898，\u5728\u4e4b\u524d\u7684\u6587\u7ae0\u4e2d\u6709\u8fc7\u4ecb\u7ecd\u3002<\/p>\n

\u56db\u3001（\u6709\u9650\u7ea7\u6570）\u5168\u540c\u6001\u52a0\u5bc6（\u7eed）<\/h2>\n

7. GSW \u52a0\u5bc6\u65b9\u6848<\/h3>\n

GSW \u65b9\u6848\u7531 Gentry\u3001Sahai \u548c Waters \u53d1\u8868[14]^{[14]}<\/span><\/span><\/span><\/span>[<\/span>14<\/span>]<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>，\u5f00\u521b\u4e86\u7b2c\u4e09\u4ee3\u5168\u540c\u6001\u52a0\u5bc6\u65b9\u6848\u3002GSW \u52a0\u5bc6\u65b9\u6848\u521b\u65b0\u6027\u5730\u63d0\u51fa\u4e86\u548c\u7b2c\u4e8c\u4ee3\u5168\u540c\u6001\u52a0\u5bc6\u65b9\u6848\u4e0d\u540c\u7684\u52a0\u5bc6\u8def\u5f84，\u4e3b\u8981\u601d\u60f3\u662f\u5229\u7528\u8fd1\u4f3c\u77e9\u9635\u7279\u5f81\u503c\u7684\u7279\u6027，\u4ee5\u66f4\u590d\u6742\u7684\u5bc6\u6587\u4e3a\u4ee3\u4ef7，\u5b9e\u73b0\u8f83\u5c0f\u566a\u58f0\u589e\u957f\u7684\u4e58\u6cd5\u540c\u6001\u8fd0\u7b97\u3002\u7531\u4e8e\u566a\u58f0\u7684\u589e\u957f\u4e0e\u660e\u6587\u7a7a\u95f4\u5927\u5c0f\u6709\u5173，GSW \u65b9\u6848\u53ca\u4e4b\u540e\u7684\u4f18\u5316\u65b9\u6848\u591a\u96c6\u4e2d\u4e8e\u903b\u8f91\u7535\u8def\u7684\u5168\u540c\u6001\u8fd0\u7b97（\u5373\u660e\u6587\u7a7a\u95f4\u4e3a m\u2208{0,1}m\\\\in \\\\{0,1\\\\}<\/span><\/span>m<\/span><\/span>\u2208<\/span><\/span><\/span><\/span>{<\/span>0<\/span>,<\/span><\/span>1<\/span>}<\/span><\/span><\/span><\/span><\/span> ）\u3002<\/p>\n

\u8bba\u6587\u4e2d\u5448\u73b0\u7684 GSW \u65b9\u6848\u5e76\u975e\u5728\u591a\u9879\u5f0f\u73af\u4e0a\u8fdb\u884c\u52a0\u5bc6，\u672c\u6587\u9996\u5148\u4ecb\u7ecd\u539f\u8bba\u6587\u65b9\u6848，\u968f\u540e\u4ecb\u7ecd GSW \u65b9\u6848\u5728\u591a\u9879\u5f0f\u73af\u4e0a\u7684\u884d\u751f\u65b9\u6848\u3002<\/p>\n

\u9996\u5148\u7ed9\u51fa\u8bba\u6587\u4e2d\u5b9a\u4e49\u7684\u4e09\u79cd\u8fd0\u7b97，\u5bf9\u4e8e\u5411\u91cf a=(a1,\u22ef\u2009,an)\u2208Zqna=(a_1,\\\\cdots,a_n)\\\\in \\\\mathbb{Z}_q^n<\/span><\/span>a<\/span><\/span>=<\/span><\/span><\/span><\/span>(<\/span>a<\/span><\/span>1<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>,<\/span><\/span>\u22ef<\/span><\/span><\/span>,<\/span><\/span>a<\/span><\/span>n<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>)<\/span><\/span>\u2208<\/span><\/span><\/span><\/span>Z<\/span><\/span>q<\/span><\/span><\/span><\/span>n<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>，\u8bbe \u2113=\u230alog2q\u230b+1\\\\ell=\\\\lfloor log_2q \\\\rfloor + 1<\/span><\/span>\u2113<\/span><\/span>=<\/span><\/span><\/span><\/span>\u230a<\/span>l<\/span>o<\/span>g<\/span><\/span>2<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>q<\/span>\u230b<\/span><\/span>+<\/span><\/span><\/span><\/span>1<\/span><\/span><\/span><\/span><\/span> \u4ee3\u8868\u5143\u7d20\u4e8c\u8fdb\u5236\u957f\u5ea6（\u66f4\u901a\u7528\u7684\u53ef\u4ee5\u8bbe\u4e3a BB<\/span><\/span>B<\/span><\/span><\/span><\/span><\/span> \u8fdb\u5236，\u8fd9\u91cc\u65b9\u4fbf\u8868\u793a\u7edf\u4e00\u4ee5\u4e8c\u8fdb\u5236\u4e3a\u4f8b），\u6709\u5982\u4e0b\u4e09\u79cd\u8fd0\u7b97：<\/p>\n

  • \n

    BitDecomp：\u8be5\u8fd0\u7b97\u5c06\u5411\u91cf\u6240\u6709\u5143\u7d20\u8fdb\u884c\u4e8c\u8fdb\u5236\u5206\u89e3：
    \nBitDecomp(a)=a\u2032=(a1,0,\u22ef\u2009,a1,\u2113\u22121,a2,0,\u22ef\u2009,a2,\u2113\u22121,\u22ef\u2009,an,\u2113\u22121)
    \nBitDecomp(a)=a'=(a_{1,0},\\\\cdots,a_{1,\\\\ell -1},a_{2,0},\\\\cdots,a_{2,\\\\ell -1},\\\\cdots,a_{n,\\\\ell-1})
    \n<\/span><\/span>B<\/span>i<\/span>t<\/span>Deco<\/span>m<\/span>p<\/span>(<\/span>a<\/span>)<\/span><\/span>=<\/span><\/span><\/span><\/span>a<\/span><\/span>\u2032<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>=<\/span><\/span><\/span><\/span>(<\/span>a<\/span><\/span>1<\/span>,<\/span>0<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>,<\/span><\/span>\u22ef<\/span><\/span><\/span>,<\/span><\/span>a<\/span><\/span>1<\/span>,<\/span>\u2113<\/span>\u2212<\/span>1<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>,<\/span><\/span>a<\/span><\/span>2<\/span>,<\/span>0<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>,<\/span><\/span>\u22ef<\/span><\/span><\/span>,<\/span><\/span>a<\/span><\/span>2<\/span>,<\/span>\u2113<\/span>\u2212<\/span>1<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>,<\/span><\/span>\u22ef<\/span><\/span><\/span>,<\/span><\/span>a<\/span><\/span>n<\/span>,<\/span>\u2113<\/span>\u2212<\/span>1<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>)<\/span><\/span><\/span><\/span><\/span><\/span>
    \n\u5176\u4e2d ai=\u2211j=0j<\u2113(ai,j\u22c52j)a_i = \\\\sum_{j=0}^{j<\\\\ell}{(a_{i,j}\\\\cdot 2^j)}<\/span><\/span>a<\/span><\/span>i<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>=<\/span><\/span><\/span><\/span>\u2211<\/span><\/span>j<\/span>=<\/span>0<\/span><\/span><\/span><\/span><\/span>j<\/span><<\/span>\u2113<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>(<\/span>a<\/span><\/span>i<\/span>,<\/span>j<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u22c5<\/span><\/span>2<\/span><\/span>j<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>)<\/span><\/span><\/span><\/span><\/span><\/span>，\u5176\u9006\u8fd0\u7b97\u4e3a\u91cd\u65b0\u7ec4\u5408：BitDecomp\u22121(a\u2032)=aBitDecomp^{-1}(a')=a<\/span><\/span>B<\/span>i<\/span>t<\/span>Deco<\/span>m<\/span>p<\/span><\/span>\u2212<\/span>1<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>(<\/span>a<\/span><\/span>\u2032<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>)<\/span><\/span>=<\/span><\/span><\/span><\/span>a<\/span><\/span><\/span><\/span><\/span>\u3002<\/p>\n<\/li>\n

  • \n

    Powersof2：\u8be5\u8fd0\u7b97\u5c06\u5411\u91cf\u6240\u6709\u5143\u7d20\u586b\u51452\u6b21\u5e42：
    \nPowersof2(a)=(a120,\u22ef\u2009,a12\u2113\u22121,a220,\u22ef\u2009,a22\u2113\u22121,\u22ef\u2009,an2\u2113\u22121)
    \nPowersof2(a)=(a_{1}2^0,\\\\cdots,a_{1}2^{\\\\ell -1},a_{2}2^0,\\\\cdots,a_{2}2^{\\\\ell -1},\\\\cdots,a_{n}2^{\\\\ell-1})
    \n<\/span><\/span>P<\/span>o<\/span>w<\/span>erso<\/span>f<\/span>2<\/span>(<\/span>a<\/span>)<\/span><\/span>=<\/span><\/span><\/span><\/span>(<\/span>a<\/span><\/span>1<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>2<\/span><\/span>0<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>,<\/span><\/span>\u22ef<\/span><\/span><\/span>,<\/span><\/span>a<\/span><\/span>1<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>2<\/span><\/span>\u2113<\/span>\u2212<\/span>1<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>,<\/span><\/span>a<\/span><\/span>2<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>2<\/span><\/span>0<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>,<\/span><\/span>\u22ef<\/span><\/span><\/span>,<\/span><\/span>a<\/span><\/span>2<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>2<\/span><\/span>\u2113<\/span>\u2212<\/span>1<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>,<\/span><\/span>\u22ef<\/span><\/span><\/span>,<\/span><\/span>a<\/span><\/span>n<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>2<\/span><\/span>\u2113<\/span>\u2212<\/span>1<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>)<\/span><\/span><\/span><\/span><\/span><\/span><\/p>\n<\/li>\n

  • \n

    Flatten：\u8be5\u8fd0\u7b97\u5c06\u5411\u91cf\u6240\u6709\u5143\u7d20\u201c\u94fa\u5e73\u201d，\u5373\u5c06\u5143\u7d20\u5927\u5c0f\u5206\u914d\u5747\u5300：
    \nFlatten(a)=BitDecomp(BitDecomp\u22121(a))
    \nFlatten(a)=BitDecomp(BitDecomp^{-1}(a))
    \n<\/span><\/span>Fl<\/span>a<\/span>tt<\/span>e<\/span>n<\/span>(<\/span>a<\/span>)<\/span><\/span>=<\/span><\/span><\/span><\/span>B<\/span>i<\/span>t<\/span>Deco<\/span>m<\/span>p<\/span>(<\/span>B<\/span>i<\/span>t<\/span>Deco<\/span>m<\/span>p<\/span><\/span>\u2212<\/span>1<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>(<\/span>a<\/span>))<\/span><\/span><\/span><\/span><\/span><\/span><\/p>\n<\/li>\n

    \u4e0a\u8ff0\u8fd0\u7b97\u82e5\u5e94\u7528\u5230\u77e9\u9635\u4e0a\u5219\u662f\u5bf9\u77e9\u9635\u6bcf\u4e00\u884c\u5206\u522b\u8fdb\u884c\u8fd0\u7b97\u3002\u7531\u4e0a\u8ff0\u8fd0\u7b97\u7684\u89c4\u5219，\u5bf9\u4e8e a,b\u2208Zqna,b\\\\in \\\\mathbb{Z}_q^{n}<\/span><\/span>a<\/span>,<\/span><\/span>b<\/span><\/span>\u2208<\/span><\/span><\/span><\/span>Z<\/span><\/span>q<\/span><\/span><\/span><\/span>n<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u663e\u7136\u53ef\u4ee5\u5f97\u5230\u5411\u91cf\u5185\u79ef\u5173\u7cfb：<\/p>\n

    BitDecomp(a)\u22c5Powersof2(b)=a\u22c5b
    \nBitDecomp(a)\\\\cdot Powersof2(b)=a\\\\cdot b
    \n<\/span><\/span>B<\/span>i<\/span>t<\/span>Deco<\/span>m<\/span>p<\/span>(<\/span>a<\/span>)<\/span><\/span>\u22c5<\/span><\/span><\/span><\/span>P<\/span>o<\/span>w<\/span>erso<\/span>f<\/span>2<\/span>(<\/span>b<\/span>)<\/span><\/span>=<\/span><\/span><\/span><\/span>a<\/span><\/span>\u22c5<\/span><\/span><\/span><\/span>b<\/span><\/span><\/span><\/span><\/span><\/span><\/p>\n

    \u5bf9\u4e8e a\u2032\u2208Zqn\u2113,b\u2208Zqna'\\\\in \\\\mathbb{Z}_q^{n\\\\ell},b\\\\in \\\\mathbb{Z}_q^{n}<\/span><\/span>a<\/span><\/span>\u2032<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u2208<\/span><\/span><\/span><\/span>Z<\/span><\/span>q<\/span><\/span><\/span><\/span>n<\/span>\u2113<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>,<\/span><\/span>b<\/span><\/span>\u2208<\/span><\/span><\/span><\/span>Z<\/span><\/span>q<\/span><\/span><\/span><\/span>n<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>，\u6709：<\/p>\n

    a\u2032\u22c5Powersof2(b)=Flatten(a\u2032)\u22c5Powersof2(b)=BitDecomp\u22121(a\u2032)\u22c5b
    \na' \\\\cdot Powersof2(b) = Flatten(a')\\\\cdot Powersof2(b) = BitDecomp^{-1}(a')\\\\cdot b
    \n<\/span><\/span>a<\/span><\/span>\u2032<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u22c5<\/span><\/span><\/span><\/span>P<\/span>o<\/span>w<\/span>erso<\/span>f<\/span>2<\/span>(<\/span>b<\/span>)<\/span><\/span>=<\/span><\/span><\/span><\/span>Fl<\/span>a<\/span>tt<\/span>e<\/span>n<\/span>(<\/span>a<\/span><\/span>\u2032<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>)<\/span><\/span>\u22c5<\/span><\/span><\/span><\/span>P<\/span>o<\/span>w<\/span>erso<\/span>f<\/span>2<\/span>(<\/span>b<\/span>)<\/span><\/span>=<\/span><\/span><\/span><\/span>B<\/span>i<\/span>t<\/span>Deco<\/span>m<\/span>p<\/span><\/span>\u2212<\/span>1<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>(<\/span>a<\/span><\/span>\u2032<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>)<\/span><\/span>\u22c5<\/span><\/span><\/span><\/span>b<\/span><\/span><\/span><\/span><\/span><\/span><\/p>\n

    \u5373 Flatten(\u22c5)Flatten(\\\\cdot)<\/span><\/span>Fl<\/span>a<\/span>tt<\/span>e<\/span>n<\/span>(<\/span>\u22c5<\/span>)<\/span><\/span><\/span><\/span><\/span> \u4e0d\u6539\u53d8\u4e0a\u8ff0\u4e8c\u8fdb\u5236\u7ec4\u5408\u4e0b\u7684\u5411\u91cf\u5185\u79ef\u7ed3\u679c\u3002<\/p>\n

    \n

    7.1 \u5bc6\u94a5\u751f\u6210\u7b97\u6cd5<\/h4>\n
  • \n

    \u968f\u673a\u9009\u53d6\u6a21\u6570 qq<\/span><\/span>q<\/span><\/span><\/span><\/span><\/span>，\u968f\u673a\u53d6 s\u2032,e\u2208Zqn，A\u2032\u2208Zqm\u00d7ns',e\\\\in \\\\mathbb{Z}_q^n，A'\\\\in \\\\mathbb{Z}_q^{m\\\\times n}<\/span><\/span>s<\/span><\/span>\u2032<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>,<\/span><\/span>e<\/span><\/span>\u2208<\/span><\/span><\/span><\/span>Z<\/span><\/span>q<\/span><\/span><\/span><\/span>n<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>，<\/span>A<\/span><\/span>\u2032<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u2208<\/span><\/span><\/span><\/span>Z<\/span><\/span>q<\/span><\/span><\/span><\/span>m<\/span>\u00d7<\/span>n<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>，\u8ba1\u7b97 b=A\u2032s\u2032+e\u2208Zqnb= A's' + e\\\\in \\\\mathbb{Z}_q^n<\/span><\/span>b<\/span><\/span>=<\/span><\/span><\/span><\/span>A<\/span><\/span>\u2032<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>s<\/span><\/span>\u2032<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>+<\/span><\/span><\/span><\/span>e<\/span><\/span>\u2208<\/span><\/span><\/span><\/span>Z<\/span><\/span>q<\/span><\/span><\/span><\/span>n<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u3002\u53ef\u4ee5\u770b\u51fa\u8fd9\u662f\u751f\u6210\u4e86 mm<\/span><\/span>m<\/span><\/span><\/span><\/span><\/span> \u5bf9 LWE \u95ee\u9898\u5b9e\u4f8b，\u4ee5 s\u2032s'<\/span><\/span>s<\/span><\/span>\u2032<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span> \u4e3a\u5bc6\u94a5，ee<\/span><\/span>e<\/span><\/span><\/span><\/span><\/span> \u4e3a\u5c0f\u566a\u58f0\u3002（\u8fd9\u91cc\u7684\u8868\u8ff0\u4e3a\u4e86\u4e0e\u524d\u6587\u4e00\u81f4\u4e0e\u8bba\u6587\u4e0d\u5b8c\u5168\u76f8\u540c，\u672c\u8d28\u662f\u4e00\u6837\u7684\u3002）<\/p>\n<\/li>\n

  • \n

    \u516c\u94a5\u4e3a A=(b,A\u2032)\u2208Zqm\u00d7(n+1)A=(b,A') \\\\in \\\\mathbb{Z}_q^{m\\\\times (n+1)}<\/span><\/span>A<\/span><\/span>=<\/span><\/span><\/span><\/span>(<\/span>b<\/span>,<\/span><\/span>A<\/span><\/span>\u2032<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>)<\/span><\/span>\u2208<\/span><\/span><\/span><\/span>Z<\/span><\/span>q<\/span><\/span><\/span><\/span>m<\/span>\u00d7<\/span>(<\/span>n<\/span>+<\/span>1<\/span>)<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span> \u4e3a\u4e00\u4e2a\u6a2a\u5411\u62fc\u63a5\u5728\u4e00\u8d77\u7684\u77e9\u9635，\u79c1\u94a5\u4e3a s=(1,\u2212s\u2032)\u2208Zq(n+1)s=(1,-s') \\\\in \\\\mathbb{Z}_q^{(n+1)}<\/span><\/span>s<\/span><\/span>=<\/span><\/span><\/span><\/span>(<\/span>1<\/span>,<\/span><\/span>\u2212<\/span>s<\/span><\/span>\u2032<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>)<\/span><\/span>\u2208<\/span><\/span><\/span><\/span>Z<\/span><\/span>q<\/span><\/span><\/span><\/span>(<\/span>n<\/span>+<\/span>1<\/span>)<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>，\u663e\u7136\u6709 As=eAs=e<\/span><\/span>A<\/span>s<\/span><\/span>=<\/span><\/span><\/span><\/span>e<\/span><\/span><\/span><\/span><\/span> \u6210\u7acb\u3002<\/p>\n<\/li>\n

    7.2 \u52a0\u5bc6\u7b97\u6cd5<\/h4>\n

    \u8bbe N=(n+1)\u2113N=(n+1)\\\\ell<\/span><\/span>N<\/span><\/span>=<\/span><\/span><\/span><\/span>(<\/span>n<\/span><\/span>+<\/span><\/span><\/span><\/span>1<\/span>)<\/span>\u2113<\/span><\/span><\/span><\/span><\/span>，\u4e14 IN\u2208{0,1}N\u00d7NI_N\\\\in\\\\{0,1\\\\}^{N\\\\times N}<\/span><\/span>I<\/span><\/span>N<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u2208<\/span><\/span><\/span><\/span>{<\/span>0<\/span>,<\/span><\/span>1<\/span>}<\/span><\/span>N<\/span>\u00d7<\/span>N<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span> \u4e3a\u5355\u4f4d\u77e9\u9635\u3002\u5bf9\u4e8e\u660e\u6587 \u03bc\u2208Zq\\\\mu \\\\in Z_q<\/span><\/span>\u03bc<\/span><\/span>\u2208<\/span><\/span><\/span><\/span>Z<\/span><\/span>q<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>，\u968f\u673a\u9009\u53d6 R\u2208{0,1}N\u00d7mR\\\\in\\\\{0,1\\\\}^{N\\\\times m}<\/span><\/span>R<\/span><\/span>\u2208<\/span><\/span><\/span><\/span>{<\/span>0<\/span>,<\/span><\/span>1<\/span>}<\/span><\/span>N<\/span>\u00d7<\/span>m<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>，\u4f7f\u7528\u516c\u94a5\u52a0\u5bc6\u8fc7\u7a0b\u5982\u4e0b：<\/p>\n

    C=Enc(\u03bc)=Flatten(\u03bcIN+BitDecomp(R\u00d7A))\u2208ZqN\u00d7N
    \nC=Enc(\\\\mu)=Flatten(\\\\mu I_N+BitDecomp(R\\\\times A)) \\\\in \\\\mathbb{Z}_q^{N\\\\times N}
    \n<\/span><\/span>C<\/span><\/span>=<\/span><\/span><\/span><\/span>E<\/span>n<\/span>c<\/span>(<\/span>\u03bc<\/span>)<\/span><\/span>=<\/span><\/span><\/span><\/span>Fl<\/span>a<\/span>tt<\/span>e<\/span>n<\/span>(<\/span>\u03bc<\/span>I<\/span><\/span>N<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>+<\/span><\/span><\/span><\/span>B<\/span>i<\/span>t<\/span>Deco<\/span>m<\/span>p<\/span>(<\/span>R<\/span><\/span>\u00d7<\/span><\/span><\/span><\/span>A<\/span>))<\/span><\/span>\u2208<\/span><\/span><\/span><\/span>Z<\/span><\/span>q<\/span><\/span><\/span><\/span>N<\/span>\u00d7<\/span>N<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/p>\n

    \u5176\u4e2d RR<\/span><\/span>R<\/span><\/span><\/span><\/span><\/span> \u7684\u5b58\u5728\u53ea\u662f\u4e3a\u4e86\u4f7f\u5bc6\u6587\u968f\u673a，\u4e0d\u96be\u9a8c\u8bc1 R\u00d7AR\\\\times A<\/span><\/span>R<\/span><\/span>\u00d7<\/span><\/span><\/span><\/span>A<\/span><\/span><\/span><\/span><\/span> \u4ecd\u7136\u662f\u82e5\u5e72 LWE \u95ee\u9898\u5b9e\u4f8b\u7ec4\u6210\u7684\u77e9\u9635，\u6ee1\u8db3 R\u00d7A\u00d7s=R\u00d7eR\\\\times A\\\\times s=R\\\\times e<\/span><\/span>R<\/span><\/span>\u00d7<\/span><\/span><\/span><\/span>A<\/span><\/span>\u00d7<\/span><\/span><\/span><\/span>s<\/span><\/span>=<\/span><\/span><\/span><\/span>R<\/span><\/span>\u00d7<\/span><\/span><\/span><\/span>e<\/span><\/span><\/span><\/span><\/span>\u3002FlattenFlatten<\/span><\/span>Fl<\/span>a<\/span>tt<\/span>e<\/span>n<\/span><\/span><\/span><\/span><\/span> \u64cd\u4f5c\u53ea\u662f\u4e3a\u4e86\u4f7f\u53d6\u503c\u5e73\u5747，\u51cf\u5c11\u540e\u7eed\u8fd0\u7b97\u4ea7\u751f\u7684\u566a\u58f0，\u5728\u7406\u89e3\u52a0\u5bc6\u7b97\u6cd5\u65f6\u53ef\u4ee5\u5ffd\u89c6\u3002<\/p>\n

    7.3 \u89e3\u5bc6\u7b97\u6cd5<\/h4>\n

    \u4f7f\u7528\u79c1\u94a5\u89e3\u5bc6，\u9996\u5148\u8ba1\u7b97 C\u00d7Powersof2(s)C\\\\times Powersof2(s)<\/span><\/span>C<\/span><\/span>\u00d7<\/span><\/span><\/span><\/span>P<\/span>o<\/span>w<\/span>erso<\/span>f<\/span>2<\/span>(<\/span>s<\/span>)<\/span><\/span><\/span><\/span><\/span>，\u7136\u540e\u53d6\u5176\u7b2c ii<\/span><\/span>i<\/span><\/span><\/span><\/span><\/span> \u884c\u7684\u503c xix_i<\/span><\/span>x<\/span><\/span>i<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>（\u6ee1\u8db3 2i\u2208(q4,q2]2^i\\\\in(\\\\frac{q}{4},\\\\frac{q}{2}]<\/span><\/span>2<\/span><\/span>i<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u2208<\/span><\/span><\/span><\/span>(<\/span><\/span><\/span>4<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>q<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>,<\/span><\/span><\/span><\/span>2<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>q<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>]<\/span><\/span><\/span><\/span><\/span>），\u8ba1\u7b97\u5f97\u5230\u660e\u6587 \u03bc=\u230axi2i\u230b\\\\mu = \\\\lfloor \\\\frac{x_i}{2^i} \\\\rfloor<\/span><\/span>\u03bc<\/span><\/span>=<\/span><\/span><\/span><\/span>\u230a<\/span><\/span><\/span>2<\/span><\/span>i<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>x<\/span><\/span>i<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u230b<\/span><\/span><\/span><\/span><\/span>\u3002<\/p>\n

    \n

    \u6b63\u786e\u6027<\/h4>\n

    \u8bbe v=Powersof2(s)v = Powersof2(s)<\/span><\/span>v<\/span><\/span>=<\/span><\/span><\/span><\/span>P<\/span>o<\/span>w<\/span>erso<\/span>f<\/span>2<\/span>(<\/span>s<\/span>)<\/span><\/span><\/span><\/span><\/span>，\u53ef\u4ee5\u89c2\u5bdf\u5230\u5728\u89e3\u5bc6\u65f6：<\/p>\n

    C\u00d7v=\u03bc\u22c5v+R\u00d7A\u00d7s=\u03bc\u22c5v+R\u00d7e=\u03bcv+e\u2032
    \nC\\\\times v = \\\\mu \\\\cdot v +R\\\\times A \\\\times s = \\\\mu \\\\cdot v + R\\\\times e = \\\\mu v+e'
    \n<\/span><\/span>C<\/span><\/span>\u00d7<\/span><\/span><\/span><\/span>v<\/span><\/span>=<\/span><\/span><\/span><\/span>\u03bc<\/span><\/span>\u22c5<\/span><\/span><\/span><\/span>v<\/span><\/span>+<\/span><\/span><\/span><\/span>R<\/span><\/span>\u00d7<\/span><\/span><\/span><\/span>A<\/span><\/span>\u00d7<\/span><\/span><\/span><\/span>s<\/span><\/span>=<\/span><\/span><\/span><\/span>\u03bc<\/span><\/span>\u22c5<\/span><\/span><\/span><\/span>v<\/span><\/span>+<\/span><\/span><\/span><\/span>R<\/span><\/span>\u00d7<\/span><\/span><\/span><\/span>e<\/span><\/span>=<\/span><\/span><\/span><\/span>\u03bcv<\/span><\/span>+<\/span><\/span><\/span><\/span>e<\/span><\/span>\u2032<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/p>\n

    \u53d6\u7b2c ii<\/span><\/span>i<\/span><\/span><\/span><\/span><\/span> \u884c\u540e\u5f97\u5230 \u03bc\u22c5vi+ei\u2032\\\\mu \\\\cdot v_i+e'_i<\/span><\/span>\u03bc<\/span><\/span>\u22c5<\/span><\/span><\/span><\/span>v<\/span><\/span>i<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>+<\/span><\/span><\/span><\/span>e<\/span><\/span>i<\/span><\/span><\/span><\/span>\u2032<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>，\u663e\u7136\u566a\u58f0 \u2223\u2223ei\u2032\u2223\u2223=\u2223\u2223Ri\u22c5e\u2223\u2223\u2264\u2223\u2223e\u2223\u22231||e'_i||=||R_i\\\\cdot e||\\\\le ||e||_1<\/span><\/span>\u2223\u2223<\/span>e<\/span><\/span>i<\/span><\/span><\/span><\/span>\u2032<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u2223\u2223<\/span><\/span>=<\/span><\/span><\/span><\/span>\u2223\u2223<\/span>R<\/span><\/span>i<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u22c5<\/span><\/span><\/span><\/span>e<\/span>\u2223\u2223<\/span><\/span>\u2264<\/span><\/span><\/span><\/span>\u2223\u2223<\/span>e<\/span>\u2223<\/span>\u2223<\/span><\/span>1<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>（\u8303\u6570 \u2223\u2223\u22c5\u2223\u2223||\\\\cdot||<\/span><\/span>\u2223\u2223<\/span><\/span>\u22c5<\/span><\/span><\/span><\/span>\u2223\u2223<\/span><\/span><\/span><\/span><\/span> \u4e0d\u6807\u4e0b\u6807\u9ed8\u8ba4\u4e3a\u65e0\u7a77\u8303\u6570），\u5f53\u566a\u58f0\u5927\u5c0f\u4e0d\u8d85\u8fc7 q8\\\\frac{q}{8}<\/span><\/span><\/span><\/span>8<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>q<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span> \u65f6，\u7531\u4e8e vi\u2208(q4,q2]v_i \\\\in(\\\\frac{q}{4},\\\\frac{q}{2}]<\/span><\/span>v<\/span><\/span>i<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u2208<\/span><\/span><\/span><\/span>(<\/span><\/span><\/span>4<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>q<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>,<\/span><\/span><\/span><\/span>2<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>q<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>]<\/span><\/span><\/span><\/span><\/span>，\u5219 \u2223\u2223ei\u2032vi\u2223\u2223<12||\\\\frac{e'_i}{v_i}||\\\\lt\\\\frac{1}{2}<\/span><\/span>\u2223\u2223<\/span><\/span><\/span>v<\/span><\/span>i<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>e<\/span><\/span>i<\/span><\/span><\/span><\/span>\u2032<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u2223\u2223<\/span><\/span><<\/span><\/span><\/span><\/span><\/span><\/span>2<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>1<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>，\u56e0\u6b64\u89e3\u5bc6\u53ef\u4ee5\u6210\u529f\u3002\u566a\u58f0\u4e0a\u9650\u4e3a q8\\\\frac{q}{8}<\/span><\/span><\/span><\/span>8<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>q<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u3002<\/p>\n

    \u5b89\u5168\u6027<\/h4>\n

    GSW \u65b9\u6848\u5b9e\u9645\u4e0a\u4f7f\u7528\u4e86\u82e5\u5e72\u7ec4 LWE \u95ee\u9898，\u5b9e\u73b0\u4e86\u660e\u6587\u4f5c\u4e3a\u8fd1\u4f3c\u7279\u5f81\u503c\u7684\u6548\u679c，\u5373 Cv=\u03bcv+e\u2032Cv=\\\\mu v +e'<\/span><\/span>C<\/span>v<\/span><\/span>=<\/span><\/span><\/span><\/span>\u03bcv<\/span><\/span>+<\/span><\/span><\/span><\/span>e<\/span><\/span>\u2032<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>（\u6b63\u5e38\u7279\u5f81\u503c\u6ee1\u8db3 Cv=\u03bcvCv=\\\\mu v<\/span><\/span>C<\/span>v<\/span><\/span>=<\/span><\/span><\/span><\/span>\u03bcv<\/span><\/span><\/span><\/span><\/span>）\u3002\u8be5\u7ec4\u5408\u672c\u8d28\u4e0a\u8fd8\u662f LWE \u95ee\u9898，\u7531\u4e8e\u89e3\u51b3 LWE \u95ee\u9898\u662f\u56f0\u96be\u7684，GSW \u65b9\u6848\u516c\u5f00 AA<\/span><\/span>A<\/span><\/span><\/span><\/span><\/span> \u4f5c\u4e3a\u516c\u94a5\u4e0d\u4f1a\u6cc4\u9732 ss<\/span><\/span>s<\/span><\/span><\/span><\/span><\/span> \u7684\u53d6\u503c，\u4e14\u5728\u52a0\u5bc6\u65f6 RR<\/span><\/span>R<\/span><\/span><\/span><\/span><\/span> \u662f\u968f\u673a\u9009\u53d6\u7684，\u53ef\u4ee5\u8ba4\u4e3a GSW \u65b9\u6848\u662f\u5b89\u5168\u7684\u3002<\/p>\n

    \u52a0\u6cd5\u540c\u6001\u6027<\/h4>\n

    GSW \u52a0\u5bc6\u65b9\u6848\u5177\u6709\u52a0\u6cd5\u540c\u6001\u6027，\u5bb9\u6613\u9a8c\u8bc1：<\/p>\n

    (C0+C1)v=(\u03bc0+\u03bc1)v+e0\u2032+e1\u2032
    \n(C_0+C_1)v=(\\\\mu_0+\\\\mu_1)v+e_0'+e_1'
    \n<\/span><\/span>(<\/span>C<\/span><\/span>0<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>+<\/span><\/span><\/span><\/span>C<\/span><\/span>1<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>)<\/span>v<\/span><\/span>=<\/span><\/span><\/span><\/span>(<\/span>\u03bc<\/span><\/span>0<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>+<\/span><\/span><\/span><\/span>\u03bc<\/span><\/span>1<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>)<\/span>v<\/span><\/span>+<\/span><\/span><\/span><\/span>e<\/span><\/span>0<\/span><\/span><\/span><\/span>\u2032<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>+<\/span><\/span><\/span><\/span>e<\/span><\/span>1<\/span><\/span><\/span><\/span>\u2032<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/p>\n

    \u4e14\u566a\u58f0\u589e\u957f\u8f83\u5c0f\u3002<\/p>\n

    \u4e58\u6cd5\u540c\u6001\u6027<\/h4>\n

    GSW \u52a0\u5bc6\u65b9\u6848\u5177\u6709\u4e58\u6cd5\u540c\u6001\u6027，\u5bb9\u6613\u9a8c\u8bc1：<\/p>\n

    (C0\u00d7C1)v=C0\u00d7(\u03bc1v+Re1)=\u03bc0\u03bc1v+\u03bc1e0\u2032+C0e1\u2032
    \n(C_0\\\\times C_1)v=C_0\\\\times (\\\\mu_1v+Re_1) =\\\\mu_0\\\\mu_1v+\\\\mu_1e_0'+C_0e_1'
    \n<\/span><\/span>(<\/span>C<\/span><\/span>0<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u00d7<\/span><\/span><\/span><\/span>C<\/span><\/span>1<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>)<\/span>v<\/span><\/span>=<\/span><\/span><\/span><\/span>C<\/span><\/span>0<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u00d7<\/span><\/span><\/span><\/span>(<\/span>\u03bc<\/span><\/span>1<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>v<\/span><\/span>+<\/span><\/span><\/span><\/span>R<\/span>e<\/span><\/span>1<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>)<\/span><\/span>=<\/span><\/span><\/span><\/span>\u03bc<\/span><\/span>0<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u03bc<\/span><\/span>1<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>v<\/span><\/span>+<\/span><\/span><\/span><\/span>\u03bc<\/span><\/span>1<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>e<\/span><\/span>0<\/span><\/span><\/span><\/span>\u2032<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>+<\/span><\/span><\/span><\/span>C<\/span><\/span>0<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>e<\/span><\/span>1<\/span><\/span><\/span><\/span>\u2032<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/p>\n

    \u566a\u58f0\u53d8\u4e3a e\u2032=\u03bc1e0\u2032+C0e1\u2032e'=\\\\mu_1e_0'+C_0e_1'<\/span><\/span>e<\/span><\/span>\u2032<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>=<\/span><\/span><\/span><\/span>\u03bc<\/span><\/span>1<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>e<\/span><\/span>0<\/span><\/span><\/span><\/span>\u2032<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>+<\/span><\/span><\/span><\/span>C<\/span><\/span>0<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>e<\/span><\/span>1<\/span><\/span><\/span><\/span>\u2032<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u3002\u7531\u4e8e C0C_0<\/span><\/span>C<\/span><\/span>0<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span> \u8fdb\u884c\u8fc7\u4e8c\u8fdb\u5236\u5206\u89e3，\u56e0\u6b64\u53ef\u4ee5\u5f97\u5230 \u2223\u2223C0e1\u2032\u2223\u2223\u2264Ne1||C_0e_1'||\\\\le Ne_1<\/span><\/span>\u2223\u2223<\/span>C<\/span><\/span>0<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>e<\/span><\/span>1<\/span><\/span><\/span><\/span>\u2032<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u2223\u2223<\/span><\/span>\u2264<\/span><\/span><\/span><\/span>N<\/span>e<\/span><\/span>1<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u3002\u6240\u4ee5\u566a\u58f0\u4e3b\u8981\u53d7 \u03bc1\\\\mu_1<\/span><\/span>\u03bc<\/span><\/span>1<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span> \u5373\u660e\u6587\u7a7a\u95f4\u5927\u5c0f\u5f71\u54cd，\u82e5 GSW \u53ea\u9488\u5bf9\u5355\u4e2a\u6bd4\u7279\u52a0\u5bc6，\u5219\u8be5\u65b9\u6848\u540c\u6001\u4e58\u6cd5\u8fd0\u7b97\u7684\u566a\u58f0\u6700\u591a\u53ea\u589e\u52a0 N+1N+1<\/span><\/span>N<\/span><\/span>+<\/span><\/span><\/span><\/span>1<\/span><\/span><\/span><\/span><\/span> \u500d，\u76f8\u8f83\u4e8e\u7b2c\u4e8c\u4ee3\u540c\u6001\u52a0\u5bc6\u5927\u5927\u51cf\u5c11，\u4e5f\u7701\u53bb\u4e86\u5bc6\u94a5\u5207\u6362\u548c\u6a21\u6570\u5207\u6362\u64cd\u4f5c，\u4f46\u5bc6\u6587\u5927\u5c0f\u589e\u52a0\u4e86\u5927\u7ea6 NN<\/span><\/span>N<\/span><\/span><\/span><\/span><\/span> \u500d\u3002<\/p>\n

    \u4e0e\u975e（NAND）\u540c\u6001\u6027<\/h4>\n

    \u5728\u5e03\u5c14\u7535\u8def\u4e2d，\u8003\u8651\u5230\u4e0e\u975e\u8fd0\u7b97（NAND）\u53ef\u4ee5\u751f\u6210\u5176\u4ed6\u6240\u6709\u7535\u8def\u95e8，GSW \u52a0\u5bc6\u65b9\u6848\u7ed9\u51fa\u4e86\u4e0e\u975e\u540c\u6001\u8ba1\u7b97\u65b9\u6848\u5b9e\u73b0\u5e03\u5c14\u7535\u8def\u4e0a\u7684\u540c\u6001\u8ba1\u7b97\u3002\u8003\u8651\u5230\u5728\u6a21 2 \u8ba1\u7b97\u4e2d，\u4e0e\u975e\u8fd0\u7b97\u7b49\u4ef7\u4e8e 1\u2212\u03bc0\u03bc11-\\\\mu_0\\\\mu_1<\/span><\/span>1<\/span><\/span>\u2212<\/span><\/span><\/span><\/span>\u03bc<\/span><\/span>0<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u03bc<\/span><\/span>1<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>，\u56e0\u6b64\u4e0e\u975e\u540c\u6001\u8ba1\u7b97\u53ef\u4ee5\u9a8c\u8bc1\u5982\u4e0b：<\/p>\n

    (IN\u2212C0\u00d7C1)v=(1\u2212\u03bc0\u03bc1)v\u2212\u03bc1e0\u2032\u2212C0e1\u2032
    \n(I_N-C_0\\\\times C_1)v =(1-\\\\mu_0\\\\mu_1)v-\\\\mu_1e_0'-C_0e_1'
    \n<\/span><\/span>(<\/span>I<\/span><\/span>N<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u2212<\/span><\/span><\/span><\/span>C<\/span><\/span>0<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u00d7<\/span><\/span><\/span><\/span>C<\/span><\/span>1<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>)<\/span>v<\/span><\/span>=<\/span><\/span><\/span><\/span>(<\/span>1<\/span><\/span>\u2212<\/span><\/span><\/span><\/span>\u03bc<\/span><\/span>0<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u03bc<\/span><\/span>1<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>)<\/span>v<\/span><\/span>\u2212<\/span><\/span><\/span><\/span>\u03bc<\/span><\/span>1<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>e<\/span><\/span>0<\/span><\/span><\/span><\/span>\u2032<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u2212<\/span><\/span><\/span><\/span>C<\/span><\/span>0<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>e<\/span><\/span>1<\/span><\/span><\/span><\/span>\u2032<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/p>\n

    \u672c\u8d28\u4e0a\u662f\u4e58\u6cd5\u540c\u6001\u8fd0\u7b97，\u566a\u58f0\u589e\u957f\u4e0e\u4e58\u6cd5\u540c\u6001\u8fd0\u7b97\u4e00\u81f4\u3002<\/p>\n

    \u7531\u4e8e\u5b9e\u73b0\u4e86\u4e0e\u975e\u540c\u6001\u8ba1\u7b97\u5c31\u53ef\u4ee5\u8ba1\u7b97\u4efb\u610f\u7535\u8def\u95e8，\u4e14\u7ecf\u8fc7\u6bcf\u4e00\u4e2a\u7535\u8def\u95e8\u566a\u58f0\u6700\u591a\u653e\u5927 N+1N+1<\/span><\/span>N<\/span><\/span>+<\/span><\/span><\/span><\/span>1<\/span><\/span><\/span><\/span><\/span> \u500d，\u5728\u4e0d\u8fdb\u884c Bootstrapping \u8fd0\u7b97\u7684\u60c5\u51b5\u4e0b，\u82e5\u521d\u59cb\u566a\u58f0\u4e3a BB<\/span><\/span>B<\/span><\/span><\/span><\/span><\/span>，\u5219\u7ecf\u8fc7 LL<\/span><\/span>L<\/span><\/span><\/span><\/span><\/span> \u4e2a\u7535\u8def\u95e8\u540e\u566a\u58f0\u4e0a\u754c\u53d8\u4e3a B(N+1)LB(N+1)^L<\/span><\/span>B<\/span>(<\/span>N<\/span><\/span>+<\/span><\/span><\/span><\/span>1<\/span>)<\/span><\/span>L<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>，\u53ef\u4ee5\u6839\u636e\u566a\u58f0\u4e0a\u754c\u8861\u91cf\u53ef\u8ba1\u7b97\u7535\u8def\u7684\u6df1\u5ea6\u3002\u81ea GSW \u65b9\u6848\u540e，\u5f88\u591a\u8bba\u6587\u5173\u6ce8\u4e8e\u5feb\u901f\u7684\u5b9e\u73b0\u5e03\u5c14\u7535\u8def\u8ba1\u7b97（NAND \u95e8）\u4e2d\u7684 Bootstrapping \u8fd0\u7b97，\u4ee5\u8fbe\u5230\u5168\u540c\u6001\u8fd0\u7b97\u7684\u76ee\u7684，\u5728\u540e\u7eed FHEW \u548c TFHE \u65b9\u6848\u4e2d\u4f1a\u8fdb\u884c\u4ecb\u7ecd\u3002GSW \u65b9\u6848\u66f4\u591a\u7684\u662f\u63d0\u4f9b\u4e86\u4e00\u79cd\u5168\u65b0\u601d\u8def，\u73b0\u4eca\u4e00\u822c\u4e0d\u76f4\u63a5\u4f7f\u7528 GSW \u65b9\u6848\u52a0\u5bc6\u5e76\u8ba1\u7b97（GSW \u65b9\u6848\u5728\u6570\u503c\u8ba1\u7b97\u4e0a\u5bc6\u6587\u8f83\u5927，\u4e14\u4e0d\u652f\u6301\u7b2c\u4e8c\u4ee3\u5168\u540c\u6001\u52a0\u5bc6\u65b9\u6848\u4e2d\u7684 SIMD \u6279\u5904\u7406\u6280\u672f；\u5728\u5e03\u5c14\u8ba1\u7b97\u4e0a FHEW \u63d0\u51fa\u4e86\u4e00\u79cd\u66f4\u9ad8\u6548\u7684 NAND \u8fd0\u7b97\u95e8），\u800c\u66f4\u591a\u7684\u662f\u4f5c\u4e3a\u5e03\u5c14\u7535\u8def\u5168\u540c\u6001\u8ba1\u7b97\u4e2d Bootstrapping \u6280\u672f\u5b9e\u73b0\u7684\u5173\u952e\u90e8\u5206\u3002<\/p>\n

    8. RGSW \u52a0\u5bc6\u65b9\u6848<\/h3>\n

    \u8bb0 RGSW \u4e3a GSW \u65b9\u6848\u7684\u73af\u53d8\u5f0f，\u8fd0\u7b97\u64cd\u4f5c\u5728\u591a\u9879\u5f0f\u73af\u4e4b\u4e0a，\u539f\u7406\u4e0e GSW \u4e00\u81f4，\u4e3b\u8981\u5e94\u7528\u5728 Bootstrapping \u6280\u672f\u7684\u5b9e\u73b0\u4e0a，\u5176\u539f\u7406\u4ecb\u7ecd\u5982\u4e0b\u3002<\/p>\n

    RGSW \u65b9\u6848\u672c\u8d28\u4e0a\u662f\u82e5\u5e72 RLWE \u65b9\u6848\u7684\u7ec4\u5408\u3002\u5728 RLWE \u65b9\u6848\u4e2d，\u52a0\u5bc6\u683c\u5f0f\u4e00\u822c\u4e3a（\u8fd9\u91cc\u7528 BFV\u65b9\u6848\u4e2d\u7684\u52a0\u5bc6\u65b9\u5f0f）：<\/p>\n

    RLWEst\/q(m)=(a,as+e+qtm)
    \nRLWE_s^{t\/q}(m)=(a,as+e+\\\\frac{q}{t}m)
    \n<\/span><\/span>R<\/span>L<\/span>W<\/span>E<\/span><\/span>s<\/span><\/span><\/span><\/span>t<\/span>\/<\/span>q<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>(<\/span>m<\/span>)<\/span><\/span>=<\/span><\/span><\/span><\/span>(<\/span>a<\/span>,<\/span><\/span>a<\/span>s<\/span><\/span>+<\/span><\/span><\/span><\/span>e<\/span><\/span>+<\/span><\/span><\/span><\/span><\/span><\/span>t<\/span><\/span><\/span><\/span><\/span><\/span><\/span>q<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>m<\/span>)<\/span><\/span><\/span><\/span><\/span><\/span><\/p>\n

    \u5176\u4e2d a,s,e,m\u2208Rqa,s,e,m \\\\in R_q<\/span><\/span>a<\/span>,<\/span><\/span>s<\/span>,<\/span><\/span>e<\/span>,<\/span><\/span>m<\/span><\/span>\u2208<\/span><\/span><\/span><\/span>R<\/span><\/span>q<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span> \u5747\u4e3a\u591a\u9879\u5f0f\u73af\u4e2d\u7684\u5143\u7d20（Rq=Zq[x]\/(xN+1)R_q=\\\\mathbb{Z}_q[x]\/(x^N+1)<\/span><\/span>R<\/span><\/span>q<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>=<\/span><\/span><\/span><\/span>Z<\/span><\/span>q<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>[<\/span>x<\/span>]<\/span>\/<\/span>(<\/span>x<\/span><\/span>N<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>+<\/span><\/span><\/span><\/span>1<\/span>)<\/span><\/span><\/span><\/span><\/span> \u4e3a\u591a\u9879\u5f0f\u73af），tt<\/span><\/span>t<\/span><\/span><\/span><\/span><\/span> \u4e3a\u660e\u6587\u7a7a\u95f4\u4e2d\u591a\u9879\u5f0f\u7cfb\u6570\u6a21\u6570，qq<\/span><\/span>q<\/span><\/span><\/span><\/span><\/span> \u4e3a\u5bc6\u6587\u7a7a\u95f4\u6a21\u6570（\u53c2\u8003 BFV \u65b9\u6848），\u4e3a\u4e86\u65b9\u4fbf，\u8bbe t\u2223qt|q<\/span><\/span>t<\/span>\u2223<\/span>q<\/span><\/span><\/span><\/span><\/span>，\u56e0\u6b64 qt\\\\frac{q}{t}<\/span><\/span><\/span><\/span>t<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>q<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span> \u53ef\u89c6\u4e3a\u6574\u6570\u3002<\/p>\n

    \n

    8.1 \u5bc6\u94a5\u751f\u6210\u7b97\u6cd5<\/h4>\n
  • \u8bbe qq<\/span><\/span>q<\/span><\/span><\/span><\/span><\/span> \u4e3a\u6a21\u6570，BgB_g<\/span><\/span>B<\/span><\/span>g<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span> \u4e3a\u5206\u89e3\u57fa\u5e95（\u5728GSW\u65b9\u6848\u4e2d\u4ee5\u4e8c\u8fdb\u5236\u5206\u89e3\u4e3a\u4f8b\u4ecb\u7ecd，\u5373 Bg=2B_g=2<\/span><\/span>B<\/span><\/span>g<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>=<\/span><\/span><\/span><\/span>2<\/span><\/span><\/span><\/span><\/span>，\u6b64\u5904\u4e5f\u53ef\u4ee5\u4ee3\u5165\u4e8c\u8fdb\u5236\u7406\u89e3），dg=\u230alogBgq\u230b+1d_g = \\\\lfloor log_{B_g}q \\\\rfloor + 1<\/span><\/span>d<\/span><\/span>g<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>=<\/span><\/span><\/span><\/span>\u230a<\/span>l<\/span>o<\/span>g<\/span><\/span>B<\/span><\/span>g<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>q<\/span>\u230b<\/span><\/span>+<\/span><\/span><\/span><\/span>1<\/span><\/span><\/span><\/span><\/span> \u4e3a\u5143\u7d20\u957f\u5ea6\u3002\u751f\u6210\u91cd\u7ec4\u77e9\u9635 G\u2208Zq2dg\u00d72G\\\\in \\\\mathbb{Z}_{q}^{2d_g\\\\times 2}<\/span><\/span>G<\/span><\/span>\u2208<\/span><\/span><\/span><\/span>Z<\/span><\/span>q<\/span><\/span><\/span><\/span><\/span>2<\/span>d<\/span><\/span>g<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u00d7<\/span>2<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>：<\/li>\n

    G=[Bg00Bg10\u22ee\u22eeBgdg\u2212100Bg0\u22ee\u22ee0Bgdg\u22121]
    \nG=\\\\begin{bmatrix}
    \nB_g^0 & 0 \\\\\\\\
    \nB_g^1 & 0 \\\\\\\\
    \n\\\\vdots & \\\\vdots \\\\\\\\
    \nB_g^{d_g-1} & 0 \\\\\\\\
    \n0 & B_g^0 \\\\\\\\
    \n\\\\vdots & \\\\vdots \\\\\\\\
    \n0 & B_g^{d_g-1} \\\\\\\\
    \n\\\\end{bmatrix}
    \n<\/span><\/span>G<\/span><\/span>=<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>B<\/span><\/span>g<\/span><\/span><\/span><\/span>0<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>B<\/span><\/span>g<\/span><\/span><\/span><\/span>1<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u22ee<\/span><\/span><\/span><\/span><\/span><\/span>B<\/span><\/span>g<\/span><\/span><\/span><\/span>d<\/span><\/span>g<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u2212<\/span>1<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>0<\/span><\/span><\/span><\/span>\u22ee<\/span><\/span><\/span><\/span><\/span><\/span>0<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>0<\/span><\/span><\/span><\/span>0<\/span><\/span><\/span><\/span>\u22ee<\/span><\/span><\/span><\/span><\/span><\/span>0<\/span><\/span><\/span><\/span>B<\/span><\/span>g<\/span><\/span><\/span><\/span>0<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u22ee<\/span><\/span><\/span><\/span><\/span><\/span>B<\/span><\/span>g<\/span><\/span><\/span><\/span>d<\/span><\/span>g<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u2212<\/span>1<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/p>\n

  • \u968f\u673a\u9009\u53d6\u5bc6\u94a5 s\u2208Rqs\\\\in R_q<\/span><\/span>s<\/span><\/span>\u2208<\/span><\/span><\/span><\/span>R<\/span><\/span>q<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>，\u5e76\u751f\u6210\u7531 2dg2d_g<\/span><\/span>2<\/span>d<\/span><\/span>g<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span> \u5bf9 RLWEs(0)RLWE_s(0)<\/span><\/span>R<\/span>L<\/span>W<\/span>E<\/span><\/span>s<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>(<\/span>0<\/span>)<\/span><\/span><\/span><\/span><\/span> \u5bc6\u6587\u7ec4\u6210\u7684\u77e9\u9635 A\u2208Rq2dg\u00d72A\\\\in R_{q}^{2d_g\\\\times 2}<\/span><\/span>A<\/span><\/span>\u2208<\/span><\/span><\/span><\/span>R<\/span><\/span>q<\/span><\/span><\/span><\/span><\/span>2<\/span>d<\/span><\/span>g<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u00d7<\/span>2<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>：<\/li>\n

    A=[a1a1s+e1a2a2s+e2\u22ee\u22eea2dga2dgs+e2dg]
    \nA=\\\\begin{bmatrix}
    \na_1 & a_1s+e_1 \\\\\\\\
    \na_2 & a_2s+e_2 \\\\\\\\
    \n\\\\vdots & \\\\vdots \\\\\\\\
    \na_{2d_g} & a_{2d_g}s+e_{2d_g}
    \n\\\\end{bmatrix}
    \n<\/span><\/span>A<\/span><\/span>=<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>a<\/span><\/span>1<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>a<\/span><\/span>2<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u22ee<\/span><\/span><\/span><\/span><\/span><\/span>a<\/span><\/span>2<\/span>d<\/span><\/span>g<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>a<\/span><\/span>1<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>s<\/span><\/span>+<\/span><\/span>e<\/span><\/span>1<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>a<\/span><\/span>2<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>s<\/span><\/span>+<\/span><\/span>e<\/span><\/span>2<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u22ee<\/span><\/span><\/span><\/span><\/span><\/span>a<\/span><\/span>2<\/span>d<\/span><\/span>g<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>s<\/span><\/span>+<\/span><\/span>e<\/span><\/span>2<\/span>d<\/span><\/span>g<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/p>\n

  • \u516c\u94a5\u4e3a AA<\/span><\/span>A<\/span><\/span><\/span><\/span><\/span>，\u79c1\u94a5\u4e3a ss<\/span><\/span>s<\/span><\/span><\/span><\/span><\/span>\u3002<\/li>\n

    8.2 \u52a0\u5bc6\u7b97\u6cd5<\/h4>\n

    \u5bf9\u4e8e\u660e\u6587 \u03bc\u2208Zq\\\\mu \\\\in \\\\mathbb{Z}_q<\/span><\/span>\u03bc<\/span><\/span>\u2208<\/span><\/span><\/span><\/span>Z<\/span><\/span>q<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>，\u5c06\u5176\u660e\u6587\u7f16\u7801\u4e3a m=x\u03bc\u00a0mod\u00a0(xN+1)m=x^\\\\mu \\\\ mod \\\\ (x^N+1)<\/span><\/span>m<\/span><\/span>=<\/span><\/span><\/span><\/span>x<\/span><\/span>\u03bc<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u00a0<\/span>m<\/span>o<\/span>d<\/span>\u00a0<\/span>(<\/span>x<\/span><\/span>N<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>+<\/span><\/span><\/span><\/span>1<\/span>)<\/span><\/span><\/span><\/span><\/span>，\u5219\u663e\u7136 m\u2208Rqm \\\\in R_q<\/span><\/span>m<\/span><\/span>\u2208<\/span><\/span><\/span><\/span>R<\/span><\/span>q<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>，\u5176\u7cfb\u6570\u4ec5\u6709\u4e00\u5904\u4e3a 1, \u5176\u4f59\u4e3a 0（\u8fd9\u91cc\u7684\u7f16\u7801\u4e3a\u540e\u7eed FHEW \u65b9\u6848\u4f5c\u94fa\u57ab，\u5e76\u975e\u4e00\u5b9a\u8981\u5982\u6b64\u7f16\u7801）\u3002\u8bbe\u7f29\u653e\u7cfb\u6570\u4e3a u=q2u=\\\\frac{q}{2}<\/span><\/span>u<\/span><\/span>=<\/span><\/span><\/span><\/span><\/span><\/span>2<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>q<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>（\u5047\u8bbe 2\u2223q2|q<\/span><\/span>2\u2223<\/span>q<\/span><\/span><\/span><\/span><\/span>，\u8be5\u7cfb\u6570\u53ef\u6839\u636e\u566a\u58f0\u8981\u6c42\u8c03\u6574），\u52a0\u5bc6\u7b97\u6cd5\u5982\u4e0b（\u4e3a\u4e86\u8f85\u52a9\u7406\u89e3\u5c06\u7f29\u653e\u56e0\u5b50 uu<\/span><\/span>u<\/span><\/span><\/span><\/span><\/span> \u4e5f\u653e\u5165 RLWE()RLWE()<\/span><\/span>R<\/span>L<\/span>W<\/span>E<\/span>(<\/span>)<\/span><\/span><\/span><\/span><\/span> \u4e2d，\u4e8b\u5b9e\u4e0a\u8be5\u7f29\u653e\u56e0\u5b50\u662f\u9690\u542b\u5728 RLWERLWE<\/span><\/span>R<\/span>L<\/span>W<\/span>E<\/span><\/span><\/span><\/span><\/span> \u65b9\u6848\u4e2d\u7684）：<\/p>\n

    C=RGSW(\u03bc)=A+muG=[a1+uBg0ma1s+e1a2+uBg1ma2s+e2\u22ee\u22eea2dga2dgs+e2dg+uBgdg\u22121m]=[RLWE(\u2212uBg0ms)\u22eeRLWE(\u2212uBgdg\u22121ms)RLWE(uBg0m)\u22eeRLWE(uBgdg\u22121m)]
    \nC = RGSW(\\\\mu)=A+muG=\\\\begin{bmatrix}
    \na_1 +uB_g^0m& a_1s+e_1 \\\\\\\\
    \na_2 +uB_g^1m& a_2s+e_2 \\\\\\\\
    \n\\\\vdots & \\\\vdots \\\\\\\\
    \na_{2d_g} & a_{2d_g}s+e_{2d_g} +uB_g^{d_g-1}m
    \n\\\\end{bmatrix} =\\\\begin{bmatrix}
    \nRLWE(-uB_g^0ms) \\\\\\\\
    \n\\\\vdots \\\\\\\\
    \nRLWE(-uB_g^{d_g-1}ms) \\\\\\\\
    \nRLWE(uB_g^0m) \\\\\\\\
    \n\\\\vdots \\\\\\\\
    \nRLWE(uB_g^{d_g-1}m)
    \n\\\\end{bmatrix}
    \n<\/span><\/span>C<\/span><\/span>=<\/span><\/span><\/span><\/span>RGS<\/span>W<\/span>(<\/span>\u03bc<\/span>)<\/span><\/span>=<\/span><\/span><\/span><\/span>A<\/span><\/span>+<\/span><\/span><\/span><\/span>m<\/span>u<\/span>G<\/span><\/span>=<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>a<\/span><\/span>1<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>+<\/span><\/span>u<\/span>B<\/span><\/span>g<\/span><\/span><\/span><\/span>0<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>m<\/span><\/span><\/span><\/span>a<\/span><\/span>2<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>+<\/span><\/span>u<\/span>B<\/span><\/span>g<\/span><\/span><\/span><\/span>1<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>m<\/span><\/span><\/span><\/span>\u22ee<\/span><\/span><\/span><\/span><\/span><\/span>a<\/span><\/span>2<\/span>d<\/span><\/span>g<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>a<\/span><\/span>1<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>s<\/span><\/span>+<\/span><\/span>e<\/span><\/span>1<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>a<\/span><\/span>2<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>s<\/span><\/span>+<\/span><\/span>e<\/span><\/span>2<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u22ee<\/span><\/span><\/span><\/span><\/span><\/span>a<\/span><\/span>2<\/span>d<\/span><\/span>g<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>s<\/span><\/span>+<\/span><\/span>e<\/span><\/span>2<\/span>d<\/span><\/span>g<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>+<\/span><\/span>u<\/span>B<\/span><\/span>g<\/span><\/span><\/span><\/span>d<\/span><\/span>g<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u2212<\/span>1<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>m<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>=<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>R<\/span>L<\/span>W<\/span>E<\/span>(<\/span>\u2212<\/span>u<\/span>B<\/span><\/span>g<\/span><\/span><\/span><\/span>0<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>m<\/span>s<\/span>)<\/span><\/span><\/span><\/span>\u22ee<\/span><\/span><\/span><\/span><\/span><\/span>R<\/span>L<\/span>W<\/span>E<\/span>(<\/span>\u2212<\/span>u<\/span>B<\/span><\/span>g<\/span><\/span><\/span><\/span>d<\/span><\/span>g<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u2212<\/span>1<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>m<\/span>s<\/span>)<\/span><\/span><\/span><\/span>R<\/span>L<\/span>W<\/span>E<\/span>(<\/span>u<\/span>B<\/span><\/span>g<\/span><\/span><\/span><\/span>0<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>m<\/span>)<\/span><\/span><\/span><\/span>\u22ee<\/span><\/span><\/span><\/span><\/span><\/span>R<\/span>L<\/span>W<\/span>E<\/span>(<\/span>u<\/span>B<\/span><\/span>g<\/span><\/span><\/span><\/span>d<\/span><\/span>g<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u2212<\/span>1<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>m<\/span>)<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/p>\n

    \u5176\u4e2d\u6709 (ai+uBgi\u22121m,ais+ei)=RLWE(\u2212uBgi\u22121ms)(a_i+uB_g^{i-1}m,a_is+e_i)=RLWE(-uB_g^{i-1}ms)<\/span><\/span>(<\/span>a<\/span><\/span>i<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>+<\/span><\/span><\/span><\/span>u<\/span>B<\/span><\/span>g<\/span><\/span><\/span><\/span>i<\/span>\u2212<\/span>1<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>m<\/span>,<\/span><\/span>a<\/span><\/span>i<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>s<\/span><\/span>+<\/span><\/span><\/span><\/span>e<\/span><\/span>i<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>)<\/span><\/span>=<\/span><\/span><\/span><\/span>R<\/span>L<\/span>W<\/span>E<\/span>(<\/span>\u2212<\/span>u<\/span>B<\/span><\/span>g<\/span><\/span><\/span><\/span>i<\/span>\u2212<\/span>1<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>m<\/span>s<\/span>)<\/span><\/span><\/span><\/span><\/span>，\u56e0\u4e3a\u5728\u89e3\u5bc6\u65f6：<\/p>\n

    (ais+ei)\u2212(ai+uBgi\u22121m)s=\u2212uBgi\u22121ms+ei
    \n(a_is+e_i) – (a_i+uB_g^{i-1}m)s = -uB_g^{i-1}ms+e_i
    \n<\/span><\/span>(<\/span>a<\/span><\/span>i<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>s<\/span><\/span>+<\/span><\/span><\/span><\/span>e<\/span><\/span>i<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>)<\/span><\/span>\u2212<\/span><\/span><\/span><\/span>(<\/span>a<\/span><\/span>i<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>+<\/span><\/span><\/span><\/span>u<\/span>B<\/span><\/span>g<\/span><\/span><\/span><\/span>i<\/span>\u2212<\/span>1<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>m<\/span>)<\/span>s<\/span><\/span>=<\/span><\/span><\/span><\/span>\u2212<\/span>u<\/span>B<\/span><\/span>g<\/span><\/span><\/span><\/span>i<\/span>\u2212<\/span>1<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>m<\/span>s<\/span><\/span>+<\/span><\/span><\/span><\/span>e<\/span><\/span>i<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/p>\n

    8.3 \u89e3\u5bc6\u7b97\u6cd5<\/h4>\n

    \u4f7f\u7528\u79c1\u94a5\u89e3\u5bc6，\u53d6\u5bc6\u6587\u7b2cdg+1d_g+1<\/span><\/span>d<\/span><\/span>g<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>+<\/span><\/span><\/span><\/span>1<\/span><\/span><\/span><\/span><\/span>\u884c RLWE(um)RLWE(um)<\/span><\/span>R<\/span>L<\/span>W<\/span>E<\/span>(<\/span>u<\/span>m<\/span>)<\/span><\/span><\/span><\/span><\/span>，\u89e3\u5bc6\u5982\u4e0b：<\/p>\n

    adg+1s+edg+1+um\u2212adg+1s=um+edg+1
    \na_{d_g+1}s+e_{d_g+1}+um-a_{d_g+1}s=um+e_{d_g+1}
    \n<\/span><\/span>a<\/span><\/span>d<\/span><\/span>g<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>+<\/span>1<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>s<\/span><\/span>+<\/span><\/span><\/span><\/span>e<\/span><\/span>d<\/span><\/span>g<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>+<\/span>1<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>+<\/span><\/span><\/span><\/span>u<\/span>m<\/span><\/span>\u2212<\/span><\/span><\/span><\/span>a<\/span><\/span>d<\/span><\/span>g<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>+<\/span>1<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>s<\/span><\/span>=<\/span><\/span><\/span><\/span>u<\/span>m<\/span><\/span>+<\/span><\/span><\/span><\/span>e<\/span><\/span>d<\/span><\/span>g<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>+<\/span>1<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/p>\n

    \u5f53 \u2223\u2223edg+1u\u2223\u2223<12||\\\\frac{e_{d_g+1}}{u}||\\\\lt \\\\frac{1}{2}<\/span><\/span>\u2223\u2223<\/span><\/span><\/span>u<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>e<\/span><\/span>d<\/span><\/span>g<\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>+<\/span>1<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u2223\u2223<\/span><\/span><<\/span><\/span><\/span><\/span><\/span><\/span>2<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>1<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span> \u65f6，\u5bf9\u4e0a\u8ff0\u7ed3\u679c\u9664\u53bb uu<\/span><\/span>u<\/span><\/span><\/span><\/span><\/span> \u5e76\u5bf9\u7cfb\u6570\u56db\u820d\u4e94\u5165\u53d6\u6574\u5f97\u5230 mm<\/span><\/span>m<\/span><\/span><\/span><\/span><\/span>，\u8fdb\u800c\u5f97\u5230 \u03bc\\\\mu<\/span><\/span>\u03bc<\/span><\/span><\/span><\/span><\/span>（\u53c2\u8003 BFV \u89e3\u5bc6\u6b63\u786e\u6027）\u3002<\/p>\n

    \n

    \u6b63\u786e\u6027<\/h4>\n

    \u6b63\u786e\u6027\u672c\u8d28\u4e0e BFV \u65b9\u6848\u89e3\u5bc6\u6b63\u786e\u6027\u4e00\u81f4\u3002<\/p>\n

    \u5b89\u5168\u6027<\/h4>\n

    RGSW \u65b9\u6848\u5b89\u5168\u6027\u4f9d\u8d56\u4e8e RLWE \u95ee\u9898，\u53ea\u8981 RLWE \u95ee\u9898\u96be\u89e3，RGSW \u65b9\u6848\u5c31\u53ef\u4ee5\u8ba4\u4e3a\u662f\u5b89\u5168\u7684\u3002<\/p>\n

    \u52a0\u6cd5\u540c\u6001\u6027<\/h4>\n

    RGSW \u65b9\u6848\u5177\u6709\u52a0\u6cd5\u540c\u6001\u6027，\u6b63\u786e\u6027\u5bb9\u6613\u9a8c\u8bc1，\u4e0e BFV \u65b9\u6848\u7684\u52a0\u6cd5\u540c\u6001\u6027\u4e00\u81f4，\u4e14\u566a\u58f0\u589e\u52a0\u8f83\u5c0f，\u6b64\u5904\u7565\u8fc7\u3002<\/p>\n

    \u4e58\u6cd5\u540c\u6001\u6027<\/h4>\n

    RGSW \u65b9\u6848\u5177\u6709\u4e58\u6cd5\u540c\u6001\u6027，\u8fd9\u91cc\u501f\u7528 TFHE \u65b9\u6848\u4e2d\u7684\u8868\u793a\u65b9\u5f0f，\u5c06 RGSW \u65b9\u6848\u7684\u4e58\u6cd5\u5206\u4e3a\u5916\u79ef\u548c\u5185\u79ef\u3002<\/p>\n

    \u5916\u79ef<\/h5>\n

    RGSW \u65b9\u6848\u7684\u5916\u79ef\u53ef\u8868\u793a\u4e3a \u22c5：RLWE\u00d7RGSW\u27f6RLWE\\\\boxed{\\\\cdot}：RLWE \\\\times RGSW \\\\longrightarrow RLWE<\/span><\/span><\/span>\u22c5<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span>：<\/span>R<\/span>L<\/span>W<\/span>E<\/span><\/span>\u00d7<\/span><\/span><\/span><\/span>RGS<\/span>W<\/span><\/span>\u27f6<\/span><\/span><\/span><\/span>R<\/span>L<\/span>W<\/span>E<\/span><\/span><\/span><\/span><\/span>，\u5373\u4e00\u4e2a RLWE \u5bc6\u6587\u4e0e\u4e00\u4e2a RGSW \u5bc6\u6587\u8fd0\u7b97\u5f97\u5230\u4e00\u4e2a RLWE \u5bc6\u6587\u3002<\/p>\n

    \u8bbe RLWE \u5bc6\u6587\u4e3a c=(a,b)c=(a,b)<\/span><\/span>c<\/span><\/span>=<\/span><\/span><\/span><\/span>(<\/span>a<\/span>,<\/span><\/span>b<\/span>)<\/span><\/span><\/span><\/span><\/span>，\u5bf9\u5176\u8fdb\u884c\u5206\u89e3\u540e\u5f97\u5230 BitDecomp(c)=(a0,\u22ef\u2009,adg\u22121,b0,\u22ef\u2009,bdg\u22121)BitDecomp(c)=(a_0,\\\\cdots,a_{d_g-1},b_0,\\\\cdots, b_{d_g-1})<\/span><\/span>B<\/span>i<\/span>t<\/span>Deco<\/span>m<\/span>p<\/span>(<\/span>c<\/span>)<\/span><\/span>=<\/span><\/span><\/span><\/span>(<\/span>a<\/span><\/span>0<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>,<\/span><\/span>\u22ef<\/span><\/span><\/span>,<\/span><\/span>a<\/span><\/span>d<\/span><\/span>g<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u2212<\/span>1<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>,<\/span><\/span>b<\/span><\/span>0<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>,<\/span><\/span>\u22ef<\/span><\/span><\/span>,<\/span><\/span>b<\/span><\/span>d<\/span><\/span>g<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u2212<\/span>1<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>)<\/span><\/span><\/span><\/span><\/span>，\u5219\u540c\u6001\u5916\u79ef\u8ba1\u7b97\u5982\u4e0b（\u8fd9\u91cc\u5c06\u7f29\u653e\u56e0\u5b50\u9690\u542b\u5728 RLWERLWE<\/span><\/span>R<\/span>L<\/span>W<\/span>E<\/span><\/span><\/span><\/span><\/span> \u65b9\u6848\u5185\u90e8）：<\/p>\n

    RLWE(m\u2032)\u00d7RGSW(m)=BitDecomp(c)\u00d7C=(a0,\u22ef\u2009,adg\u22121,b0,\u22ef\u2009,bdg\u22121)\u00d7[RLWE(\u2212Bg0ms)\u22eeRLWE(\u2212Bgdg\u22121ms)RLWE(Bg0m)\u22eeRLWE(Bgdg\u22121m)]=\u2211i=0dg\u22121ai\u22c5RLWE(\u2212Bgims)+\u2211i=0dg\u22121bi\u22c5RLWE(Bgim)=\u2211i=0dg\u22121RLWE(\u2212ms\u22c5(aiBgi)+m\u22c5(biBgi))=RLWE(m(b\u2212as))=RLWE(mm\u2032)
    \n\\\\begin{align}
    \nRLWE(m') \\\\times RGSW(m) & =BitDecomp(c)\\\\times C \\\\nonumber \\\\\\\\
    \n&=(a_0,\\\\cdots,a_{d_g-1},b_0,\\\\cdots, b_{d_g-1})\\\\times \\\\begin{bmatrix}
    \nRLWE(-B_g^0ms) \\\\\\\\
    \n\\\\vdots \\\\\\\\
    \nRLWE(-B_g^{d_g-1}ms) \\\\\\\\
    \nRLWE(B_g^0m) \\\\\\\\
    \n\\\\vdots \\\\\\\\
    \nRLWE(B_g^{d_g-1}m)
    \n\\\\end{bmatrix} \\\\nonumber \\\\\\\\
    \n&=\\\\sum_{i=0}^{d_g-1}{a_i\\\\cdot RLWE(-B_g^ims)} + \\\\sum_{i=0}^{d_g-1}{b_i\\\\cdot RLWE(B_g^im)} \\\\nonumber \\\\\\\\
    \n&= \\\\sum_{i=0}^{d_g-1}{RLWE(-ms\\\\cdot(a_iB_g^i)+m\\\\cdot (b_iB_g^i))}\\\\nonumber \\\\\\\\
    \n&= RLWE(m(b-as)) \\\\nonumber \\\\\\\\
    \n&=RLWE(mm') \\\\nonumber
    \n\\\\end{align}
    \n<\/span><\/span><\/span>R<\/span>L<\/span>W<\/span>E<\/span>(<\/span>m<\/span><\/span>\u2032<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>)<\/span><\/span>\u00d7<\/span><\/span>RGS<\/span>W<\/span>(<\/span>m<\/span>)<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>=<\/span><\/span>B<\/span>i<\/span>t<\/span>Deco<\/span>m<\/span>p<\/span>(<\/span>c<\/span>)<\/span><\/span>\u00d7<\/span><\/span>C<\/span><\/span><\/span><\/span><\/span><\/span>=<\/span><\/span>(<\/span>a<\/span><\/span>0<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>,<\/span><\/span>\u22ef<\/span><\/span><\/span>,<\/span><\/span>a<\/span><\/span>d<\/span><\/span>g<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u2212<\/span>1<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>,<\/span><\/span>b<\/span><\/span>0<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>,<\/span><\/span>\u22ef<\/span><\/span><\/span>,<\/span><\/span>b<\/span><\/span>d<\/span><\/span>g<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u2212<\/span>1<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>)<\/span><\/span>\u00d7<\/span><\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>R<\/span>L<\/span>W<\/span>E<\/span>(<\/span>\u2212<\/span>B<\/span><\/span>g<\/span><\/span><\/span><\/span>0<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>m<\/span>s<\/span>)<\/span><\/span><\/span><\/span>\u22ee<\/span><\/span><\/span><\/span><\/span><\/span>R<\/span>L<\/span>W<\/span>E<\/span>(<\/span>\u2212<\/span>B<\/span><\/span>g<\/span><\/span><\/span><\/span>d<\/span><\/span>g<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u2212<\/span>1<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>m<\/span>s<\/span>)<\/span><\/span><\/span><\/span>R<\/span>L<\/span>W<\/span>E<\/span>(<\/span>B<\/span><\/span>g<\/span><\/span><\/span><\/span>0<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>m<\/span>)<\/span><\/span><\/span><\/span>\u22ee<\/span><\/span><\/span><\/span><\/span><\/span>R<\/span>L<\/span>W<\/span>E<\/span>(<\/span>B<\/span><\/span>g<\/span><\/span><\/span><\/span>d<\/span><\/span>g<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u2212<\/span>1<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>m<\/span>)<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>=<\/span><\/span><\/span>i<\/span>=<\/span>0<\/span><\/span><\/span><\/span><\/span>\u2211<\/span><\/span><\/span><\/span>d<\/span><\/span>g<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u2212<\/span>1<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>a<\/span><\/span>i<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u22c5<\/span><\/span>R<\/span>L<\/span>W<\/span>E<\/span>(<\/span>\u2212<\/span>B<\/span><\/span>g<\/span><\/span><\/span><\/span>i<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>m<\/span>s<\/span>)<\/span><\/span><\/span>+<\/span><\/span><\/span>i<\/span>=<\/span>0<\/span><\/span><\/span><\/span><\/span>\u2211<\/span><\/span><\/span><\/span>d<\/span><\/span>g<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u2212<\/span>1<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>b<\/span><\/span>i<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u22c5<\/span><\/span>R<\/span>L<\/span>W<\/span>E<\/span>(<\/span>B<\/span><\/span>g<\/span><\/span><\/span><\/span>i<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>m<\/span>)<\/span><\/span><\/span><\/span><\/span><\/span><\/span>=<\/span><\/span><\/span>i<\/span>=<\/span>0<\/span><\/span><\/span><\/span><\/span>\u2211<\/span><\/span><\/span><\/span>d<\/span><\/span>g<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u2212<\/span>1<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>R<\/span>L<\/span>W<\/span>E<\/span>(<\/span>\u2212<\/span>m<\/span>s<\/span><\/span>\u22c5<\/span><\/span>(<\/span>a<\/span><\/span>i<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>B<\/span><\/span>g<\/span><\/span><\/span><\/span>i<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>)<\/span><\/span>+<\/span><\/span>m<\/span><\/span>\u22c5<\/span><\/span>(<\/span>b<\/span><\/span>i<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>B<\/span><\/span>g<\/span><\/span><\/span><\/span>i<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>))<\/span><\/span><\/span><\/span><\/span><\/span><\/span>=<\/span><\/span>R<\/span>L<\/span>W<\/span>E<\/span>(<\/span>m<\/span>(<\/span>b<\/span><\/span>\u2212<\/span><\/span>a<\/span>s<\/span>))<\/span><\/span><\/span><\/span><\/span><\/span>=<\/span><\/span>R<\/span>L<\/span>W<\/span>E<\/span>(<\/span>m<\/span>m<\/span><\/span>\u2032<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>)<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/p>\n

    \u4e0a\u8ff0\u63a8\u5bfc\u8fc7\u7a0b\u4e2d，\u4e3a\u4e86\u4fbf\u4e8e\u7406\u89e3，\u7701\u53bb\u4e86\u566a\u58f0\u7684\u8868\u793a，\u4e0d\u96be\u63a8\u5bfc\u51fa\u566a\u58f0\u589e\u52a0\u7684\u90e8\u5206\u4e3b\u8981\u662f aiea_ie<\/span><\/span>a<\/span><\/span>i<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>e<\/span><\/span><\/span><\/span><\/span> \u548c bieb_ie<\/span><\/span>b<\/span><\/span>i<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>e<\/span><\/span><\/span><\/span><\/span>，\u7531\u4e8e\u8fdb\u884c\u4e86\u8fdb\u5236\u5206\u89e3，\u8fd9\u6837\u7684\u566a\u58f0\u589e\u52a0\u662f\u53ef\u63a5\u53d7\u7684\u3002<\/p>\n

    \u5185\u79ef<\/h5>\n

    RGSW \u65b9\u6848\u7684\u5185\u79ef\u53ef\u8868\u793a\u4e3a \u00d7：RGSW\u00d7RGSW\u27f6RGSW\\\\boxed{\\\\times}：RGSW \\\\times RGSW \\\\longrightarrow RGSW<\/span><\/span><\/span>\u00d7<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span>：<\/span>RGS<\/span>W<\/span><\/span>\u00d7<\/span><\/span><\/span><\/span>RGS<\/span>W<\/span><\/span>\u27f6<\/span><\/span><\/span><\/span>RGS<\/span>W<\/span><\/span><\/span><\/span><\/span>，\u5373\u4e24\u4e2a RGSW \u5bc6\u6587\u8fd0\u7b97\u5f97\u5230\u4e00\u4e2a RGSW \u5bc6\u6587\u3002<\/p>\n

    RGSW \u7684\u5185\u79ef\u8f83\u4e3a\u590d\u6742，\u672c\u8d28\u4e0a\u7531\u82e5\u5e72\u5916\u79ef\u64cd\u4f5c\u7ec4\u6210，\u8ba1\u7b97\u5982\u4e0b（\u8fd9\u91cc\u5c06\u7f29\u653e\u56e0\u5b50\u9690\u542b\u5728 RLWERLWE<\/span><\/span>R<\/span>L<\/span>W<\/span>E<\/span><\/span><\/span><\/span><\/span> \u65b9\u6848\u5185\u90e8）：<\/p>\n

    RGSW(m0)\u00d7RGSW(m1)=[RLWE(\u2212Bg0m0s)\u22eeRLWE(\u2212Bgdg\u22121m0s)RLWE(Bg0m0)\u22eeRLWE(Bgdg\u22121m0)]\u00d7RGSW(m1)=[RLWE(\u2212Bg0m0s)\u00d7RGSW(m1)\u22eeRLWE(\u2212Bgdg\u22121m0s)\u00d7RGSW(m1)RLWE(Bg0m0)\u00d7RGSW(m1)\u22eeRLWE(Bgdg\u22121m0)\u00d7RGSW(m1)]=[RLWE(\u2212Bg0m0m1s)\u22eeRLWE(\u2212Bgdg\u22121m0m1s)RLWE(Bg0m0m1)\u22eeRLWE(Bgdg\u22121m0m1)]=RGSW(m0m1)
    \n\\\\begin{align}
    \nRGSW(m_0) \\\\times RGSW(m_1) &=\\\\begin{bmatrix}
    \nRLWE(-B_g^0m_0s) \\\\\\\\
    \n\\\\vdots \\\\\\\\
    \nRLWE(-B_g^{d_g-1}m_0s) \\\\\\\\
    \nRLWE(B_g^0m_0) \\\\\\\\
    \n\\\\vdots \\\\\\\\
    \nRLWE(B_g^{d_g-1}m_0)
    \n\\\\end{bmatrix} \\\\times RGSW(m_1)\\\\nonumber \\\\\\\\
    \n&=\\\\begin{bmatrix}
    \nRLWE(-B_g^0m_0s) \\\\times RGSW(m_1) \\\\\\\\
    \n\\\\vdots \\\\\\\\
    \nRLWE(-B_g^{d_g-1}m_0s) \\\\times RGSW(m_1) \\\\\\\\
    \nRLWE(B_g^0m_0) \\\\times RGSW(m_1) \\\\\\\\
    \n\\\\vdots \\\\\\\\
    \nRLWE(B_g^{d_g-1}m_0) \\\\times RGSW(m_1)
    \n\\\\end{bmatrix} \\\\nonumber \\\\\\\\
    \n&= \\\\begin{bmatrix}
    \nRLWE(-B_g^0m_0m_1s) \\\\\\\\
    \n\\\\vdots \\\\\\\\
    \nRLWE(-B_g^{d_g-1}m_0m_1s) \\\\\\\\
    \nRLWE(B_g^0m_0m_1) \\\\\\\\
    \n\\\\vdots \\\\\\\\
    \nRLWE(B_g^{d_g-1}m_0m_1)
    \n\\\\end{bmatrix} \\\\nonumber \\\\\\\\
    \n&= RGSW(m_0m_1) \\\\nonumber
    \n\\\\end{align}
    \n<\/span><\/span><\/span>RGS<\/span>W<\/span>(<\/span>m<\/span><\/span>0<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>)<\/span><\/span>\u00d7<\/span><\/span>RGS<\/span>W<\/span>(<\/span>m<\/span><\/span>1<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>)<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>=<\/span><\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>R<\/span>L<\/span>W<\/span>E<\/span>(<\/span>\u2212<\/span>B<\/span><\/span>g<\/span><\/span><\/span><\/span>0<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>m<\/span><\/span>0<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>s<\/span>)<\/span><\/span><\/span><\/span>\u22ee<\/span><\/span><\/span><\/span><\/span><\/span>R<\/span>L<\/span>W<\/span>E<\/span>(<\/span>\u2212<\/span>B<\/span><\/span>g<\/span><\/span><\/span><\/span>d<\/span><\/span>g<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u2212<\/span>1<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>m<\/span><\/span>0<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>s<\/span>)<\/span><\/span><\/span><\/span>R<\/span>L<\/span>W<\/span>E<\/span>(<\/span>B<\/span><\/span>g<\/span><\/span><\/span><\/span>0<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>m<\/span><\/span>0<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>)<\/span><\/span><\/span><\/span>\u22ee<\/span><\/span><\/span><\/span><\/span><\/span>R<\/span>L<\/span>W<\/span>E<\/span>(<\/span>B<\/span><\/span>g<\/span><\/span><\/span><\/span>d<\/span><\/span>g<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u2212<\/span>1<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>m<\/span><\/span>0<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>)<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u00d7<\/span><\/span>RGS<\/span>W<\/span>(<\/span>m<\/span><\/span>1<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>)<\/span><\/span><\/span><\/span><\/span><\/span>=<\/span><\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>R<\/span>L<\/span>W<\/span>E<\/span>(<\/span>\u2212<\/span>B<\/span><\/span>g<\/span><\/span><\/span><\/span>0<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>m<\/span><\/span>0<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>s<\/span>)<\/span><\/span>\u00d7<\/span><\/span>RGS<\/span>W<\/span>(<\/span>m<\/span><\/span>1<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>)<\/span><\/span><\/span><\/span>\u22ee<\/span><\/span><\/span><\/span><\/span><\/span>R<\/span>L<\/span>W<\/span>E<\/span>(<\/span>\u2212<\/span>B<\/span><\/span>g<\/span><\/span><\/span><\/span>d<\/span><\/span>g<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u2212<\/span>1<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>m<\/span><\/span>0<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>s<\/span>)<\/span><\/span>\u00d7<\/span><\/span>RGS<\/span>W<\/span>(<\/span>m<\/span><\/span>1<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>)<\/span><\/span><\/span><\/span>R<\/span>L<\/span>W<\/span>E<\/span>(<\/span>B<\/span><\/span>g<\/span><\/span><\/span><\/span>0<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>m<\/span><\/span>0<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>)<\/span><\/span>\u00d7<\/span><\/span>RGS<\/span>W<\/span>(<\/span>m<\/span><\/span>1<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>)<\/span><\/span><\/span><\/span>\u22ee<\/span><\/span><\/span><\/span><\/span><\/span>R<\/span>L<\/span>W<\/span>E<\/span>(<\/span>B<\/span><\/span>g<\/span><\/span><\/span><\/span>d<\/span><\/span>g<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u2212<\/span>1<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>m<\/span><\/span>0<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>)<\/span><\/span>\u00d7<\/span><\/span>RGS<\/span>W<\/span>(<\/span>m<\/span><\/span>1<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>)<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>=<\/span><\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>R<\/span>L<\/span>W<\/span>E<\/span>(<\/span>\u2212<\/span>B<\/span><\/span>g<\/span><\/span><\/span><\/span>0<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>m<\/span><\/span>0<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>m<\/span><\/span>1<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>s<\/span>)<\/span><\/span><\/span><\/span>\u22ee<\/span><\/span><\/span><\/span><\/span><\/span>R<\/span>L<\/span>W<\/span>E<\/span>(<\/span>\u2212<\/span>B<\/span><\/span>g<\/span><\/span><\/span><\/span>d<\/span><\/span>g<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u2212<\/span>1<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>m<\/span><\/span>0<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>m<\/span><\/span>1<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>s<\/span>)<\/span><\/span><\/span><\/span>R<\/span>L<\/span>W<\/span>E<\/span>(<\/span>B<\/span><\/span>g<\/span><\/span><\/span><\/span>0<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>m<\/span><\/span>0<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>m<\/span><\/span>1<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>)<\/span><\/span><\/span><\/span>\u22ee<\/span><\/span><\/span><\/span><\/span><\/span>R<\/span>L<\/span>W<\/span>E<\/span>(<\/span>B<\/span><\/span>g<\/span><\/span><\/span><\/span>d<\/span><\/span>g<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u2212<\/span>1<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>m<\/span><\/span>0<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>m<\/span><\/span>1<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>)<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>=<\/span><\/span>RGS<\/span>W<\/span>(<\/span>m<\/span><\/span>0<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>m<\/span><\/span>1<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>)<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/p>\n

    \u4e0a\u8ff0\u63a8\u5bfc\u8fc7\u7a0b\u4e2d\u4e5f\u7701\u7565\u4e86\u566a\u58f0\u7684\u8868\u793a，\u53ef\u4ee5\u770b\u51fa\u6700\u7ec8\u5bc6\u6587\u6bcf\u4e00\u884c\u566a\u58f0\u7684\u589e\u957f\u4e0e RGSW \u5916\u79ef\u7684\u566a\u58f0\u589e\u957f\u4e00\u81f4\u3002<\/p>\n

    9. FHEW \u52a0\u5bc6\u65b9\u6848<\/h3>\n

    FHEW \u65b9\u6848\u7531 Ducas \u548c Micciancio \u53d1\u8868[15]^{[15]}<\/span><\/span><\/span><\/span>[<\/span>15<\/span>]<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>，\u5176\u4e3b\u8981\u521b\u65b0\u5728\u4e8e\u63d0\u51fa\u4e00\u79cd\u65b0\u578b\u7684 XAND \u903b\u8f91\u7535\u8def\u95e8\u7684\u540c\u6001\u8fd0\u7b97，\u5e76\u5229\u7528 RGSW \u5b9e\u73b0\u4e00\u4e2a\u7d2f\u52a0\u5668，\u4ece\u800c\u7ed9\u51fa\u4e86\u8be5\u7535\u8def\u95e8 Bootstrapping \u7684\u6784\u9020\u65b9\u5f0f，\u5c5e\u4e8e Gate-Bootstrapping\u3002<\/p>\n

    FHEW \u65b9\u6848\u5229\u7528 LWE \u95ee\u9898\u5728\u6574\u6570\u73af\u4e0a\u52a0\u5bc6，\u8bb0 LWEst\/q(m,E)LWE_s^{t\/q}(m,E)<\/span><\/span>L<\/span>W<\/span>E<\/span><\/span>s<\/span><\/span><\/span><\/span>t<\/span>\/<\/span>q<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>(<\/span>m<\/span>,<\/span><\/span>E<\/span>)<\/span><\/span><\/span><\/span><\/span> \u4ee3\u8868\u4f7f\u7528\u5bc6\u94a5\u5411\u91cf s\u2208Zqns\\\\in \\\\mathbb{Z}_q^n<\/span><\/span>s<\/span><\/span>\u2208<\/span><\/span><\/span><\/span>Z<\/span><\/span>q<\/span><\/span><\/span><\/span>n<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span> \u5bf9\u660e\u6587 m\u2208Ztm\\\\in \\\\mathbb{Z}_t<\/span><\/span>m<\/span><\/span>\u2208<\/span><\/span><\/span><\/span>Z<\/span><\/span>t<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span> \u52a0\u5bc6，\u52a0\u5bc6\u566a\u58f0\u5927\u5c0f\u4e0d\u8d85\u8fc7 EE<\/span><\/span>E<\/span><\/span><\/span><\/span><\/span>\u3002\u4e3a\u4e86\u4fbf\u4e8e\u8868\u793a，\u5728\u672c\u65b9\u6848\u4ecb\u7ecd\u4e2d\u8ba4\u4e3a t\u2223qt|q<\/span><\/span>t<\/span>\u2223<\/span>q<\/span><\/span><\/span><\/span><\/span>，\u5373 qt\\\\frac{q}{t}<\/span><\/span><\/span><\/span>t<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>q<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span> \u4e3a\u6574\u6570\u3002<\/p>\n

    \n

    9.1 \u5bc6\u94a5\u751f\u6210\u7b97\u6cd5<\/h4>\n

    FHEW \u65b9\u6848\u4f7f\u7528\u7684\u52a0\u5bc6\u65b9\u5f0f\u4e3a\u5bf9\u79f0\u52a0\u5bc6，\u56e0\u6b64\u53ea\u6709\u79c1\u94a5\u3002\u8bbe qq<\/span><\/span>q<\/span><\/span><\/span><\/span><\/span> \u4e3a\u6a21\u6570，\u968f\u673a\u53d6\u79c1\u94a5 s\u2208Zqns\\\\in \\\\mathbb{Z}_q^n<\/span><\/span>s<\/span><\/span>\u2208<\/span><\/span><\/span><\/span>Z<\/span><\/span>q<\/span><\/span><\/span><\/span>n<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u3002<\/p>\n

    9.2 \u52a0\u5bc6\u7b97\u6cd5<\/h4>\n

    \u5bf9\u4e8e\u660e\u6587 m\u2208{0,1}m \\\\in \\\\{0,1\\\\}<\/span><\/span>m<\/span><\/span>\u2208<\/span><\/span><\/span><\/span>{<\/span>0<\/span>,<\/span><\/span>1<\/span>}<\/span><\/span><\/span><\/span><\/span>，\u8bbe\u660e\u6587\u7a7a\u95f4\u5927\u5c0f t=4t=4<\/span><\/span>t<\/span><\/span>=<\/span><\/span><\/span><\/span>4<\/span><\/span><\/span><\/span><\/span>，\u4e14\u566a\u58f0\u9650\u4e3a E=q16E=\\\\frac{q}{16}<\/span><\/span>E<\/span><\/span>=<\/span><\/span><\/span><\/span><\/span><\/span>16<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>q<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>（\u548c\u6b63\u5e38\u7684 LWE \u52a0\u5bc6\u4e0d\u540c，\u4e3a\u4e0e\u975e\u540c\u6001\u8ba1\u7b97\u8003\u8651）\u3002\u968f\u673a\u53d6\u5c0f\u566a\u58f0 ee<\/span><\/span>e<\/span><\/span><\/span><\/span><\/span>，\u4ee5\u53ca a\u2208Zqna\\\\in\\\\mathbb{Z}_q^n<\/span><\/span>a<\/span><\/span>\u2208<\/span><\/span><\/span><\/span>Z<\/span><\/span>q<\/span><\/span><\/span><\/span>n<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>，\u5229\u7528\u79c1\u94a5\u52a0\u5bc6\u5f97\u5230：<\/p>\n

    c=Enc(m)=(a,b)=(a,as+e+qtm)
    \nc=Enc(m)=(a,b)=(a,as+e+\\\\frac{q}{t}m)
    \n<\/span><\/span>c<\/span><\/span>=<\/span><\/span><\/span><\/span>E<\/span>n<\/span>c<\/span>(<\/span>m<\/span>)<\/span><\/span>=<\/span><\/span><\/span><\/span>(<\/span>a<\/span>,<\/span><\/span>b<\/span>)<\/span><\/span>=<\/span><\/span><\/span><\/span>(<\/span>a<\/span>,<\/span><\/span>a<\/span>s<\/span><\/span>+<\/span><\/span><\/span><\/span>e<\/span><\/span>+<\/span><\/span><\/span><\/span><\/span><\/span>t<\/span><\/span><\/span><\/span><\/span><\/span><\/span>q<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>m<\/span>)<\/span><\/span><\/span><\/span><\/span><\/span><\/p>\n

    9.3 \u89e3\u5bc6\u7b97\u6cd5<\/h4>\n

    \u4f7f\u7528\u79c1\u94a5\u89e3\u5bc6\u6d41\u7a0b\u5982\u4e0b：<\/p>\n

    m=Dec(c)=\u230atq(b\u2212as)\u2309\u00a0mod\u00a0t
    \nm=Dec(c)=\\\\lfloor \\\\frac{t}{q}(b-as) \\\\rceil \\\\ mod \\\\ t
    \n<\/span><\/span>m<\/span><\/span>=<\/span><\/span><\/span><\/span>Dec<\/span>(<\/span>c<\/span>)<\/span><\/span>=<\/span><\/span><\/span><\/span>\u230a<\/span><\/span><\/span>q<\/span><\/span><\/span><\/span><\/span><\/span><\/span>t<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>(<\/span>b<\/span><\/span>\u2212<\/span><\/span><\/span><\/span>a<\/span>s<\/span>)\u2309<\/span>\u00a0<\/span>m<\/span>o<\/span>d<\/span>\u00a0<\/span>t<\/span><\/span><\/span><\/span><\/span><\/span><\/p>\n

    \n

    \u6b63\u786e\u6027<\/h4>\n

    \u5728\u89e3\u5bc6\u8fc7\u7a0b\u4e2d，\u6709：<\/p>\n

    tq(b\u2212as)=tq(e+qtm)=tqe+m
    \n\\\\frac{t}{q}(b-as)= \\\\frac{t}{q}(e+\\\\frac{q}{t}m)= \\\\frac{t}{q}e+m
    \n<\/span><\/span><\/span><\/span>q<\/span><\/span><\/span><\/span><\/span><\/span><\/span>t<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>(<\/span>b<\/span><\/span>\u2212<\/span><\/span><\/span><\/span>a<\/span>s<\/span>)<\/span><\/span>=<\/span><\/span><\/span><\/span><\/span><\/span>q<\/span><\/span><\/span><\/span><\/span><\/span><\/span>t<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>(<\/span>e<\/span><\/span>+<\/span><\/span><\/span><\/span><\/span><\/span>t<\/span><\/span><\/span><\/span><\/span><\/span><\/span>q<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>m<\/span>)<\/span><\/span>=<\/span><\/span><\/span><\/span><\/span><\/span>q<\/span><\/span><\/span><\/span><\/span><\/span><\/span>t<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>e<\/span><\/span>+<\/span><\/span><\/span><\/span>m<\/span><\/span><\/span><\/span><\/span><\/span><\/p>\n

    \u663e\u7136\u5f53\u566a\u58f0\u6ee1\u8db3 \u2223tqe\u2223<12|\\\\frac{t}{q}e|\\\\lt \\\\frac{1}{2}<\/span><\/span>\u2223<\/span><\/span><\/span>q<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>t<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>e<\/span>\u2223<\/span><\/span><<\/span><\/span><\/span><\/span><\/span><\/span>2<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>1<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span> \u65f6，\u56db\u820d\u4e94\u5165\u4f1a\u5c06\u5176\u6d88\u6389\u3002\u7531\u4e8e\u52a0\u5bc6\u8981\u6c42 \u2223e\u2223<q16|e|\\\\lt\\\\frac{q}{16}<\/span><\/span>\u2223<\/span>e<\/span>\u2223<\/span><\/span><<\/span><\/span><\/span><\/span><\/span><\/span>16<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>q<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>，\u8be5\u6761\u4ef6\u663e\u7136\u6210\u7acb，\u56e0\u6b64\u6b63\u786e\u6027\u5f97\u8bc1\u3002<\/p>\n

    \u5b89\u5168\u6027<\/h4>\n

    FHEW \u65b9\u6848\u5b89\u5168\u6027\u4f9d\u8d56\u4e8e LWE \u95ee\u9898，\u82e5 LWE \u95ee\u9898\u96be\u89e3，\u53ef\u4ee5\u8ba4\u4e3a FHEW \u65b9\u6848\u662f\u5b89\u5168\u7684\u3002<\/p>\n

    \u4e0e\u975e（XAND）\u540c\u6001\u6027<\/h4>\n

    FHEW \u65b9\u6848\u5173\u6ce8\u4e8e\u5e03\u5c14\u7535\u8def\u7684\u540c\u6001\u8ba1\u7b97，\u63d0\u51fa\u4e86\u4e00\u4e2a\u65b0\u578b XAND \u540c\u6001\u8fd0\u7b97\u65b9\u5f0f，\u8be5\u65b9\u5f0f\u53ea\u9700\u8981\u7528\u5230\u540c\u6001\u52a0\u6cd5，\u76f8\u8f83\u4e8e GSW \u4e2d\u4f7f\u7528\u540c\u6001\u4e58\u6cd5\u800c\u8a00\u6548\u7387\u548c\u7a7a\u95f4\u4e0a\u90fd\u5f97\u5230\u8f83\u5927\u4f18\u5316\u3002<\/p>\n

    \u65b0\u578b XAND \u8fd0\u7b97<\/h5>\n

    \u6ce8\u610f\u5230\u4e0e\u975e\u8fd0\u7b97\u4ec5\u5728 m0=m1=1m_0=m_1=1<\/span><\/span>m<\/span><\/span>0<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>=<\/span><\/span><\/span><\/span>m<\/span><\/span>1<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>=<\/span><\/span><\/span><\/span>1<\/span><\/span><\/span><\/span><\/span> \u65f6\u7ed3\u679c\u4e3a 0，\u5176\u4f59\u7ed3\u679c\u5747\u4e3a 1，\u56e0\u6b64 FHEW \u5c06\u5176\u8f6c\u6362\u4e3a：<\/p>\n

    m0m1\u203e=\u230a54\u221212(m0+m1)\u2309
    \n\\\\overline{m_0m_1} = \\\\lfloor \\\\frac{5}{4}-\\\\frac{1}{2}(m_0+m_1) \\\\rceil
    \n<\/span><\/span><\/span>m<\/span><\/span>0<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>m<\/span><\/span>1<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>=<\/span><\/span><\/span><\/span>\u230a<\/span><\/span><\/span>4<\/span><\/span><\/span><\/span><\/span><\/span><\/span>5<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u2212<\/span><\/span><\/span><\/span><\/span><\/span>2<\/span><\/span><\/span><\/span><\/span><\/span><\/span>1<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>(<\/span>m<\/span><\/span>0<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>+<\/span><\/span><\/span><\/span>m<\/span><\/span>1<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>)\u2309<\/span><\/span><\/span><\/span><\/span><\/span><\/p>\n

    \u4e0a\u8ff0\u8f6c\u6362\u6b63\u786e\u6027\u5bb9\u6613\u9a8c\u8bc1，\u4e0b\u9762\u5177\u4f53\u4ecb\u7ecd FHEW \u65b9\u6848\u4e2d\u7684\u4e0e\u975e\u540c\u6001\u8ba1\u7b97\u3002<\/p>\n

    \u8be5\u540c\u6001\u8ba1\u7b97\u5c06 LWEs4\/q(m0,q16)LWE_s^{4\/q}(m_0,\\\\frac{q}{16})<\/span><\/span>L<\/span>W<\/span>E<\/span><\/span>s<\/span><\/span><\/span><\/span>4\/<\/span>q<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>(<\/span>m<\/span><\/span>0<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>,<\/span><\/span><\/span><\/span>16<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>q<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>)<\/span><\/span><\/span><\/span><\/span> \u548c LWEs4\/q(m1,q16)LWE_s^{4\/q}(m_1,\\\\frac{q}{16})<\/span><\/span>L<\/span>W<\/span>E<\/span><\/span>s<\/span><\/span><\/span><\/span>4\/<\/span>q<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>(<\/span>m<\/span><\/span>1<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>,<\/span><\/span><\/span><\/span>16<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>q<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>)<\/span><\/span><\/span><\/span><\/span> \u8f6c\u6362\u4e3a LWEs2\/q(m0m1\u203e,q4)LWE_s^{2\/q}(\\\\overline{m_0m_1},\\\\frac{q}{4})<\/span><\/span>L<\/span>W<\/span>E<\/span><\/span>s<\/span><\/span><\/span><\/span>2\/<\/span>q<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>(<\/span><\/span>m<\/span><\/span>0<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>m<\/span><\/span>1<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span>,<\/span><\/span><\/span><\/span>4<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>q<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>)<\/span><\/span><\/span><\/span><\/span>，\u8ba1\u7b97\u65b9\u5f0f\u5982\u4e0b：<\/p>\n

    c=LWEs2\/q(m0m1\u203e,q4)=(a,b)=(\u2212a0\u2212a1,5q8\u2212b0\u2212b1)
    \nc=LWE_s^{2\/q}(\\\\overline{m_0m_1},\\\\frac{q}{4})=(a,b) =(-a_0-a_1,\\\\frac{5q}{8}-b_0-b_1)
    \n<\/span><\/span>c<\/span><\/span>=<\/span><\/span><\/span><\/span>L<\/span>W<\/span>E<\/span><\/span>s<\/span><\/span><\/span><\/span>2\/<\/span>q<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>(<\/span><\/span>m<\/span><\/span>0<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>m<\/span><\/span>1<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span>,<\/span><\/span><\/span><\/span>4<\/span><\/span><\/span><\/span><\/span><\/span><\/span>q<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>)<\/span><\/span>=<\/span><\/span><\/span><\/span>(<\/span>a<\/span>,<\/span><\/span>b<\/span>)<\/span><\/span>=<\/span><\/span><\/span><\/span>(<\/span>\u2212<\/span>a<\/span><\/span>0<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u2212<\/span><\/span><\/span><\/span>a<\/span><\/span>1<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>,<\/span><\/span><\/span><\/span>8<\/span><\/span><\/span><\/span><\/span><\/span><\/span>5<\/span>q<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u2212<\/span><\/span><\/span><\/span>b<\/span><\/span>0<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u2212<\/span><\/span><\/span><\/span>b<\/span><\/span>1<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>)<\/span><\/span><\/span><\/span><\/span><\/span><\/p>\n

    \u6b63\u786e\u6027\u5bb9\u6613\u9a8c\u8bc1：<\/p>\n

    b\u2212as=5q8\u2212(b0+b1\u2212a0s\u2212a1s)=5q8\u2212q4(m0+m1)\u2212e0\u2212e1=q2(54\u221212(m0+m1))\u2212e0\u2212e1
    \n\\\\begin{align}
    \nb-as&=\\\\frac{5q}{8} – (b_0+b_1 – a_0s-a_1s) \\\\nonumber \\\\\\\\
    \n&=\\\\frac{5q}{8} – \\\\frac{q}{4}(m_0+m_1)-e_0-e_1 \\\\nonumber \\\\\\\\
    \n&= \\\\frac{q}{2}(\\\\frac{5}{4}-\\\\frac{1}{2}(m_0+m_1)) -e_0 -e_1 \\\\nonumber
    \n\\\\end{align}
    \n<\/span><\/span><\/span>b<\/span><\/span>\u2212<\/span><\/span>a<\/span>s<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>=<\/span><\/span><\/span><\/span>8<\/span><\/span><\/span><\/span><\/span><\/span><\/span>5<\/span>q<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u2212<\/span><\/span>(<\/span>b<\/span><\/span>0<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>+<\/span><\/span>b<\/span><\/span>1<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u2212<\/span><\/span>a<\/span><\/span>0<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>s<\/span><\/span>\u2212<\/span><\/span>a<\/span><\/span>1<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>s<\/span>)<\/span><\/span><\/span><\/span><\/span><\/span>=<\/span><\/span><\/span><\/span>8<\/span><\/span><\/span><\/span><\/span><\/span><\/span>5<\/span>q<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u2212<\/span><\/span><\/span><\/span>4<\/span><\/span><\/span><\/span><\/span><\/span><\/span>q<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>(<\/span>m<\/span><\/span>0<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>+<\/span><\/span>m<\/span><\/span>1<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>)<\/span><\/span>\u2212<\/span><\/span>e<\/span><\/span>0<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u2212<\/span><\/span>e<\/span><\/span>1<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>=<\/span><\/span><\/span><\/span>2<\/span><\/span><\/span><\/span><\/span><\/span><\/span>q<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>(<\/span><\/span><\/span>4<\/span><\/span><\/span><\/span><\/span><\/span><\/span>5<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u2212<\/span><\/span><\/span><\/span>2<\/span><\/span><\/span><\/span><\/span><\/span><\/span>1<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>(<\/span>m<\/span><\/span>0<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>+<\/span><\/span>m<\/span><\/span>1<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>))<\/span><\/span>\u2212<\/span><\/span>e<\/span><\/span>0<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u2212<\/span><\/span>e<\/span><\/span>1<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/p>\n

    \u7531\u4e8e 54\u221212(m0+m1)=m0m1\u203e\u00b114\\\\frac{5}{4}-\\\\frac{1}{2}(m_0+m_1) =\\\\overline{m_0m_1} \\\\pm\\\\frac{1}{4}<\/span><\/span><\/span><\/span>4<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>5<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u2212<\/span><\/span><\/span><\/span><\/span><\/span>2<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>1<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>(<\/span>m<\/span><\/span>0<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>+<\/span><\/span><\/span><\/span>m<\/span><\/span>1<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>)<\/span><\/span>=<\/span><\/span><\/span><\/span><\/span>m<\/span><\/span>0<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>m<\/span><\/span>1<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u00b1<\/span><\/span><\/span><\/span><\/span><\/span>4<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>1<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>，\u56e0\u6b64\u6709：<\/p>\n

    b\u2212as=q2m0m1\u203e\u00b1q8\u2212e0\u2212e1=q2m0m1\u203e+e=Enc(m0m1\u203e)
    \nb-as = \\\\frac{q}{2}\\\\overline{m_0m_1} \\\\pm \\\\frac{q}{8} -e_0-e_1 =\\\\frac{q}{2}\\\\overline{m_0m_1}+e=Enc(\\\\overline{m_0m_1})
    \n<\/span><\/span>b<\/span><\/span>\u2212<\/span><\/span><\/span><\/span>a<\/span>s<\/span><\/span>=<\/span><\/span><\/span><\/span><\/span><\/span>2<\/span><\/span><\/span><\/span><\/span><\/span><\/span>q<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>m<\/span><\/span>0<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>m<\/span><\/span>1<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u00b1<\/span><\/span><\/span><\/span><\/span><\/span>8<\/span><\/span><\/span><\/span><\/span><\/span><\/span>q<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u2212<\/span><\/span><\/span><\/span>e<\/span><\/span>0<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u2212<\/span><\/span><\/span><\/span>e<\/span><\/span>1<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>=<\/span><\/span><\/span><\/span><\/span><\/span>2<\/span><\/span><\/span><\/span><\/span><\/span><\/span>q<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>m<\/span><\/span>0<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>m<\/span><\/span>1<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>+<\/span><\/span><\/span><\/span>e<\/span><\/span>=<\/span><\/span><\/span><\/span>E<\/span>n<\/span>c<\/span>(<\/span><\/span>m<\/span><\/span>0<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>m<\/span><\/span>1<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span>)<\/span><\/span><\/span><\/span><\/span><\/span><\/p>\n

    \u7531\u4e8e e=\u00b1q4\u2212e0\u2212e1e=\\\\pm \\\\frac{q}{4} -e_0-e_1<\/span><\/span>e<\/span><\/span>=<\/span><\/span><\/span><\/span>\u00b1<\/span><\/span><\/span>4<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>q<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u2212<\/span><\/span><\/span><\/span>e<\/span><\/span>0<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u2212<\/span><\/span><\/span><\/span>e<\/span><\/span>1<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>，\u4e14 \u2223e0\u2223,\u2223e1\u2223<q16|e_0|,|e_1|\\\\lt \\\\frac{q}{16}<\/span><\/span>\u2223<\/span>e<\/span><\/span>0<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u2223<\/span>,<\/span><\/span>\u2223<\/span>e<\/span><\/span>1<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u2223<\/span><\/span><<\/span><\/span><\/span><\/span><\/span><\/span>16<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>q<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u5219 \u2223e\u2223<q4|e|\\\\lt \\\\frac{q}{4}<\/span><\/span>\u2223<\/span>e<\/span>\u2223<\/span><\/span><<\/span><\/span><\/span><\/span><\/span><\/span>4<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>q<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>，\u56e0\u6b64\u901a\u8fc7\u4e0e\u975e\u540c\u6001\u8ba1\u7b97\u6b63\u786e\u5f97\u5230\u4e86 LWEs2\/q(m0m1\u203e,q4)LWE_s^{2\/q}(\\\\overline{m_0m_1},\\\\frac{q}{4})<\/span><\/span>L<\/span>W<\/span>E<\/span><\/span>s<\/span><\/span><\/span><\/span>2\/<\/span>q<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>(<\/span><\/span>m<\/span><\/span>0<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>m<\/span><\/span>1<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span>,<\/span><\/span><\/span><\/span>4<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>q<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>)<\/span><\/span><\/span><\/span><\/span>\u3002<\/p>\n

    \u4f46\u662f\u4ec5\u4ec5\u8fd9\u6837\u8fd8\u65e0\u6cd5\u5b9e\u73b0\u5168\u540c\u6001\u8fd0\u7b97，\u56e0\u4e3a\u4e0a\u8ff0\u8fd0\u7b97\u5f97\u5230\u7684\u7ed3\u679c\u5e76\u975e\u4e3a LWEs4\/q(m0m1\u203e,q16)LWE_s^{4\/q}(\\\\overline{m_0m_1},\\\\frac{q}{16})<\/span><\/span>L<\/span>W<\/span>E<\/span><\/span>s<\/span><\/span><\/span><\/span>4\/<\/span>q<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>(<\/span><\/span>m<\/span><\/span>0<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>m<\/span><\/span>1<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span>,<\/span><\/span><\/span><\/span>16<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>q<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>)<\/span><\/span><\/span><\/span><\/span>\u3002 FHEW \u65b9\u6848\u8bbe\u8ba1\u4e86\u4e00\u4e2a\u7d2f\u52a0\u5668，\u5e76\u901a\u8fc7 RGSW \u65b9\u6848\u8fdb\u884c\u5b9e\u4f8b\u5316\u6765\u5b8c\u6210\u8fd9\u4e2a\u8f6c\u6362\u4efb\u52a1\u3002<\/p>\n

    \u7d2f\u52a0\u5668（ACC）<\/h5>\n

    \u5728 FHEW \u4f7f\u7528\u7684\u7d2f\u52a0\u5668\u4e2d，\u8f93\u5165\u548c\u8f93\u51fa\u5747\u4e3a LWE \u52a0\u5bc6\u65b9\u6848，\u5728\u4e2d\u95f4\u8fc7\u7a0b\u4e2d\u4f1a\u4f7f\u7528\u53e6\u4e00\u4e2a\u52a0\u5bc6\u65b9\u6848 EE<\/span><\/span>E<\/span><\/span><\/span><\/span><\/span>\u3002\u7d2f\u52a0\u5668（ACC）\u5305\u62ec\u4e09\u4e2a\u529f\u80fd：<\/p>\n

  • \n

    \u521d\u59cb\u5316：\u8bb0 vv<\/span><\/span>v<\/span><\/span><\/span><\/span><\/span> \u4e3a\u521d\u59cb\u503c，\u5219\u7d2f\u52a0\u5668\u521d\u59cb\u5316\u64cd\u4f5c\u8bb0\u4e3a ACC\u2190vACC\\\\leftarrow v<\/span><\/span>A<\/span>CC<\/span><\/span>\u2190<\/span><\/span><\/span><\/span>v<\/span><\/span><\/span><\/span><\/span>\u3002<\/p>\n<\/li>\n

  • \n

    \u7d2f\u52a0：\u8bb0 vv<\/span><\/span>v<\/span><\/span><\/span><\/span><\/span> \u4e3a\u5f85\u7d2f\u52a0\u503c，\u5219\u7d2f\u52a0\u64cd\u4f5c（\u540c\u6001\u6267\u884c，\u9700\u8981\u5bf9\u6570\u636e\u52a0\u5bc6）\u8bb0\u4e3a ACC\u2190+E(v)ACC \\\\xleftarrow{+} E(v)<\/span><\/span>A<\/span>CC<\/span><\/span><\/span>+<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>E<\/span>(<\/span>v<\/span>)<\/span><\/span><\/span><\/span><\/span>\u3002<\/p>\n<\/li>\n

  • \n

    \u63d0\u53d6\u6700\u9ad8\u4f4d：\u5373\u540c\u6001\u7684\u63d0\u53d6\u7d2f\u52a0\u5668\u4e2d\u52a0\u5bc6\u5143\u7d20\u7684\u6700\u9ad8\u4f4d，\u7ed3\u679c\u4ecd\u4e3a\u5bc6\u6587，\u8bb0\u4e3a c\u2190msbExtract(ACC)c\\\\leftarrow msbExtract(ACC)<\/span><\/span>c<\/span><\/span>\u2190<\/span><\/span><\/span><\/span>m<\/span>s<\/span>b<\/span>E<\/span>x<\/span>t<\/span>r<\/span>a<\/span>c<\/span>t<\/span>(<\/span>A<\/span>CC<\/span>)<\/span><\/span><\/span><\/span><\/span>\u3002<\/p>\n<\/li>\n

    \u8bbe m=m0m1\u203em=\\\\overline{m_0m_1}<\/span><\/span>m<\/span><\/span>=<\/span><\/span><\/span><\/span><\/span>m<\/span><\/span>0<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>m<\/span><\/span>1<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>，\u5219\u4f7f\u7528\u4e0a\u8ff0\u4e09\u4e2a\u529f\u80fd，\u5c06 c=(a,b)=LWEs2\/q(m,q4)c=(a,b)=LWE_s^{2\/q}(m,\\\\frac{q}{4})<\/span><\/span>c<\/span><\/span>=<\/span><\/span><\/span><\/span>(<\/span>a<\/span>,<\/span><\/span>b<\/span>)<\/span><\/span>=<\/span><\/span><\/span><\/span>L<\/span>W<\/span>E<\/span><\/span>s<\/span><\/span><\/span><\/span>2\/<\/span>q<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>(<\/span>m<\/span>,<\/span><\/span><\/span><\/span>4<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>q<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>)<\/span><\/span><\/span><\/span><\/span> \u8f6c\u6362\u4e3a c\u2032=(a\u2032,b\u2032)=LWEs4\/q(m,q16)c'=(a',b')=LWE_s^{4\/q}(m,\\\\frac{q}{16})<\/span><\/span>c<\/span><\/span>\u2032<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>=<\/span><\/span><\/span><\/span>(<\/span>a<\/span><\/span>\u2032<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>,<\/span><\/span>b<\/span><\/span>\u2032<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>)<\/span><\/span>=<\/span><\/span><\/span><\/span>L<\/span>W<\/span>E<\/span><\/span>s<\/span><\/span><\/span><\/span>4\/<\/span>q<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>(<\/span>m<\/span>,<\/span><\/span><\/span><\/span>16<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>q<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>)<\/span><\/span><\/span><\/span><\/span> \u7684\u6b65\u9aa4\u5982\u4e0b：<\/p>\n

  • \n

    \u521d\u59cb\u5316 ACC\u2190b+q4ACC \\\\leftarrow b + \\\\frac{q}{4}<\/span><\/span>A<\/span>CC<\/span><\/span>\u2190<\/span><\/span><\/span><\/span>b<\/span><\/span>+<\/span><\/span><\/span><\/span><\/span><\/span>4<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>q<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u3002<\/p>\n<\/li>\n

  • \n

    \u5bf9\u5411\u91cf aa<\/span><\/span>a<\/span><\/span><\/span><\/span><\/span> \u4e2d\u5143\u7d20\u8fdb\u884c\u5206\u89e3，\u5f97\u5230 BitDecomp(a)=(a1,0,\u22ef\u2009,a1,dg\u22121,a2,0,\u22ef\u2009,a2,dg\u22121,\u22ef\u2009,an,dg\u22121)BitDecomp(a)=(a_{1,0},\\\\cdots,a_{1,d_g -1},a_{2,0},\\\\cdots,a_{2,d_g -1},\\\\cdots,a_{n,d_g-1})<\/span><\/span>B<\/span>i<\/span>t<\/span>Deco<\/span>m<\/span>p<\/span>(<\/span>a<\/span>)<\/span><\/span>=<\/span><\/span><\/span><\/span>(<\/span>a<\/span><\/span>1<\/span>,<\/span>0<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>,<\/span><\/span>\u22ef<\/span><\/span><\/span>,<\/span><\/span>a<\/span><\/span>1<\/span>,<\/span>d<\/span><\/span>g<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u2212<\/span>1<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>,<\/span><\/span>a<\/span><\/span>2<\/span>,<\/span>0<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>,<\/span><\/span>\u22ef<\/span><\/span><\/span>,<\/span><\/span>a<\/span><\/span>2<\/span>,<\/span>d<\/span><\/span>g<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u2212<\/span>1<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>,<\/span><\/span>\u22ef<\/span><\/span><\/span>,<\/span><\/span>a<\/span><\/span>n<\/span>,<\/span>d<\/span><\/span>g<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u2212<\/span>1<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>)<\/span><\/span><\/span><\/span><\/span>\u3002<\/p>\n<\/li>\n

  • \n

    \u5bf9\u4e8e 1\u2264i\u2264n1\\\\le i \\\\le n<\/span><\/span>1<\/span><\/span>\u2264<\/span><\/span><\/span><\/span>i<\/span><\/span>\u2264<\/span><\/span><\/span><\/span>n<\/span><\/span><\/span><\/span><\/span> \u4e14 0\u2264j<dg0\\\\le j \\\\lt d_g<\/span><\/span>0<\/span><\/span>\u2264<\/span><\/span><\/span><\/span>j<\/span><\/span><<\/span><\/span><\/span><\/span>d<\/span><\/span>g<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>，\u8ba1\u7b97 Ki,j=\u2212ai,jsiBgjK_{i,j}=-a_{i,j}s_iB_g^{j}<\/span><\/span>K<\/span><\/span>i<\/span>,<\/span>j<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>=<\/span><\/span><\/span><\/span>\u2212<\/span>a<\/span><\/span>i<\/span>,<\/span>j<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>s<\/span><\/span>i<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>B<\/span><\/span>g<\/span><\/span><\/span><\/span>j<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>，\u5e76\u6267\u884c\u7d2f\u52a0\u64cd\u4f5c ACC\u2190+E(Ki,j)ACC \\\\xleftarrow{+} E(K_{i,j})<\/span><\/span>A<\/span>CC<\/span><\/span><\/span>+<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>E<\/span>(<\/span>K<\/span><\/span>i<\/span>,<\/span>j<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>)<\/span><\/span><\/span><\/span><\/span>\u3002<\/p>\n<\/li>\n

  • \n

    \u8f93\u51fa c\u2032\u2190msbExtract(ACC)c' \\\\leftarrow msbExtract(ACC)<\/span><\/span>c<\/span><\/span>\u2032<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u2190<\/span><\/span><\/span><\/span>m<\/span>s<\/span>b<\/span>E<\/span>x<\/span>t<\/span>r<\/span>a<\/span>c<\/span>t<\/span>(<\/span>A<\/span>CC<\/span>)<\/span><\/span><\/span><\/span><\/span>\u3002<\/p>\n<\/li>\n

    \u5bb9\u6613\u9a8c\u8bc1 ACCACC<\/span><\/span>A<\/span>CC<\/span><\/span><\/span><\/span><\/span> \u5728\u6240\u6709\u7d2f\u52a0\u7ed3\u675f\u540e（\u6267\u884c msbExtractmsbExtract<\/span><\/span>m<\/span>s<\/span>b<\/span>E<\/span>x<\/span>t<\/span>r<\/span>a<\/span>c<\/span>t<\/span><\/span><\/span><\/span><\/span> \u4e4b\u524d） \u7684\u5185\u5bb9\u4e3a：<\/p>\n

    v=b+q4\u2212\u2211i,jai,jsiBgj=b\u2212as+q4=q2m+e+q4
    \nv = b + \\\\frac{q}{4} – \\\\sum_{i,j}{a_{i,j}s_iB_g^{j}}=b-as+\\\\frac{q}{4}=\\\\frac{q}{2}m+e + \\\\frac{q}{4}
    \n<\/span><\/span>v<\/span><\/span>=<\/span><\/span><\/span><\/span>b<\/span><\/span>+<\/span><\/span><\/span><\/span><\/span><\/span>4<\/span><\/span><\/span><\/span><\/span><\/span><\/span>q<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u2212<\/span><\/span><\/span><\/span><\/span>i<\/span>,<\/span>j<\/span><\/span><\/span><\/span><\/span>\u2211<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>a<\/span><\/span>i<\/span>,<\/span>j<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>s<\/span><\/span>i<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>B<\/span><\/span>g<\/span><\/span><\/span><\/span>j<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>=<\/span><\/span><\/span><\/span>b<\/span><\/span>\u2212<\/span><\/span><\/span><\/span>a<\/span>s<\/span><\/span>+<\/span><\/span><\/span><\/span><\/span><\/span>4<\/span><\/span><\/span><\/span><\/span><\/span><\/span>q<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>=<\/span><\/span><\/span><\/span><\/span><\/span>2<\/span><\/span><\/span><\/span><\/span><\/span><\/span>q<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>m<\/span><\/span>+<\/span><\/span><\/span><\/span>e<\/span><\/span>+<\/span><\/span><\/span><\/span><\/span><\/span>4<\/span><\/span><\/span><\/span><\/span><\/span><\/span>q<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/p>\n

    \u7531\u4e8e \u2223e\u2223<q4|e|\\\\lt \\\\frac{q}{4}<\/span><\/span>\u2223<\/span>e<\/span>\u2223<\/span><\/span><<\/span><\/span><\/span><\/span><\/span><\/span>4<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>q<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>，\u663e\u7136\u6709 msbExtract(v)=mmsbExtract(v)=m<\/span><\/span>m<\/span>s<\/span>b<\/span>E<\/span>x<\/span>t<\/span>r<\/span>a<\/span>c<\/span>t<\/span>(<\/span>v<\/span>)<\/span><\/span>=<\/span><\/span><\/span><\/span>m<\/span><\/span><\/span><\/span><\/span> \u6210\u7acb\u3002\u53ef\u4ee5\u770b\u51fa，\u4e0a\u8ff0\u6b65\u9aa4\u672c\u8d28\u4e0a\u662f\u4e00\u79cd\u540c\u6001\u89e3\u5bc6，\u5728\u53e6\u4e00\u79cd\u52a0\u5bc6\u73af\u5883\u4e0b\u89e3\u5bc6\u8f93\u5165\u7684\u5bc6\u6587，\u5f97\u5230\u53e6\u4e00\u4e2a\u73af\u5883\u7684\u5bc6\u6587\u3002\u5373\u4e0a\u8ff0\u6b65\u9aa4\u5168\u90e8\u6267\u884c\u5b8c\u6bd5\u540e\u5c06\u5f97\u5230\u5bf9 mm<\/span><\/span>m<\/span><\/span><\/span><\/span><\/span> \u7684\u53e6\u4e00\u79cd\u52a0\u5bc6，\u5176\u566a\u97f3\u4e0a\u9650\u4e0e\u6a21\u6570\u53d6\u51b3\u4e8e\u5982\u4f55\u5b9e\u73b0\u4e0a\u8ff0\u6b65\u9aa4\u3002<\/p>\n

    RGSW \u65b9\u6848\u5b9e\u4f8b\u5316\u7d2f\u52a0\u5668<\/h5>\n

    FHEW \u65b9\u6848\u91c7\u7528 RGSW \u52a0\u5bc6\u5b9e\u73b0\u4e0a\u8ff0\u7d2f\u52a0\u5668\u7684\u529f\u80fd，\u9996\u5148\u8bbe\u7f6e\u4e00\u4e9b\u53c2\u6570\u3002<\/p>\n

    \u8bbe RQ=ZQ[x]\/(xN+1)R_Q=\\\\mathbb{Z}_Q[x]\/(x^N+1)<\/span><\/span>R<\/span><\/span>Q<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>=<\/span><\/span><\/span><\/span>Z<\/span><\/span>Q<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>[<\/span>x<\/span>]<\/span>\/<\/span>(<\/span>x<\/span><\/span>N<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>+<\/span><\/span><\/span><\/span>1<\/span>)<\/span><\/span><\/span><\/span><\/span> \u4e3a\u591a\u9879\u5f0f\u73af，\u5176\u4e2d Q=BgdgQ=B_g^{d_g}<\/span><\/span>Q<\/span><\/span>=<\/span><\/span><\/span><\/span>B<\/span><\/span>g<\/span><\/span><\/span><\/span>d<\/span><\/span>g<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>，BgB_g<\/span><\/span>B<\/span><\/span>g<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span> \u4e3a\u5206\u89e3\u57fa\u5e95\u5e76\u8bbe\u4e3a 33<\/span><\/span>3<\/span><\/span><\/span><\/span><\/span> \u7684\u5e42\u6b21，NN<\/span><\/span>N<\/span><\/span><\/span><\/span><\/span> \u8bbe\u4e3a 22<\/span><\/span>2<\/span><\/span><\/span><\/span><\/span> \u7684\u5e42\u6b21\u4e14\u8981\u6c42\u6ee1\u8db3 q\u22232Nq|2N<\/span><\/span>q<\/span>\u22232<\/span>N<\/span><\/span><\/span><\/span><\/span>（\u8fd9\u91cc\u4e3a\u4e86\u7b80\u5355\u53ef\u4ee5\u76f4\u63a5\u8bbe q=2Nq=2N<\/span><\/span>q<\/span><\/span>=<\/span><\/span><\/span><\/span>2<\/span>N<\/span><\/span><\/span><\/span><\/span>）\u3002<\/p>\n

    \u8bbe tt<\/span><\/span>t<\/span><\/span><\/span><\/span><\/span> \u4e3a\u6700\u7ec8\u8f6c\u6362\u540e\u8981\u6c42\u7684\u660e\u6587\u7a7a\u95f4\u5927\u5c0f（\u6b64\u5904 t=4t=4<\/span><\/span>t<\/span><\/span>=<\/span><\/span><\/span><\/span>4<\/span><\/span><\/span><\/span><\/span>），\u53d6\u53ef\u9006\u5143\u7d20 u\u2208ZQu\\\\in \\\\mathbb{Z}_Q<\/span><\/span>u<\/span><\/span>\u2208<\/span><\/span><\/span><\/span>Z<\/span><\/span>Q<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span> \u4e3a \u230aQ2t\u230b\\\\lfloor \\\\frac{Q}{2t} \\\\rfloor<\/span><\/span>\u230a<\/span><\/span><\/span>2<\/span>t<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>Q<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u230b<\/span><\/span><\/span><\/span><\/span> \u548c \u2308Q2t\u2309\\\\lceil \\\\frac{Q}{2t} \\\\rceil<\/span><\/span>\u2308<\/span><\/span><\/span>2<\/span>t<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>Q<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u2309<\/span><\/span><\/span><\/span><\/span> \u4e8c\u8005\u4e4b\u4e00，\u7531\u4e8e QQ<\/span><\/span>Q<\/span><\/span><\/span><\/span><\/span> \u4e3a 3 \u7684\u5e42\u6b21，\u663e\u7136\u4e8c\u8005\u5fc5\u6709\u4e00\u4e2a\u662f\u53ef\u9006\u7684\u3002<\/p>\n

    \u8bbe\u6d88\u606f m\u2208Zqm\\\\in \\\\mathbb{Z}_q<\/span><\/span>m<\/span><\/span>\u2208<\/span><\/span><\/span><\/span>Z<\/span><\/span>q<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span> \u88ab\u7f16\u7801\u4e3a ym\u2208RQy^m \\\\in R_Q<\/span><\/span>y<\/span><\/span>m<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u2208<\/span><\/span><\/span><\/span>R<\/span><\/span>Q<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>，\u5176\u4e2d y=x2Nqy=x^{\\\\frac{2N}{q}}<\/span><\/span>y<\/span><\/span>=<\/span><\/span><\/span><\/span>x<\/span><\/span><\/span><\/span>q<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>2<\/span>N<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u3002\u5f53 q=2Nq=2N<\/span><\/span>q<\/span><\/span>=<\/span><\/span><\/span><\/span>2<\/span>N<\/span><\/span><\/span><\/span><\/span> \u65f6，\u7f16\u7801\u7b49\u4e8e xmx^m<\/span><\/span>x<\/span><\/span>m<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u3002<\/p>\n

    \u7d2f\u52a0\u5668\u4e2d\u91c7\u7528\u7684\u52a0\u5bc6\u65b9\u6848 EE<\/span><\/span>E<\/span><\/span><\/span><\/span><\/span> \u8bbe\u4e3a RGSW \u52a0\u5bc6\u65b9\u6848（\u7f29\u653e\u56e0\u5b50\u4e3a uu<\/span><\/span>u<\/span><\/span><\/span><\/span><\/span>，\u5bc6\u94a5\u8bbe\u4e3a zz<\/span><\/span>z<\/span><\/span><\/span><\/span><\/span>，\u53ef\u53c2\u8003\u524d\u6587\u4ecb\u7ecd\u5982\u4f55\u52a0\u5bc6）\u3002\u8bbe\u91cd\u7ec4\u77e9\u9635 G\u2208RQ2dg\u00d72G\\\\in R_{Q}^{2d_g\\\\times 2}<\/span><\/span>G<\/span><\/span>\u2208<\/span><\/span><\/span><\/span>R<\/span><\/span>Q<\/span><\/span><\/span><\/span><\/span>2<\/span>d<\/span><\/span>g<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u00d7<\/span>2<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>（\u8fd9\u91cc\u4e0e\u539f\u8bba\u6587\u987a\u5e8f\u4e0d\u4e00\u6837，\u672c\u8d28\u4e0a\u4e0d\u53d8）：<\/p>\n

    G=[Bg00Bg10\u22ee\u22eeBgdg\u2212100Bg0\u22ee\u22ee0Bgdg\u22121]
    \nG=\\\\begin{bmatrix}
    \nB_g^0 & 0 \\\\\\\\
    \nB_g^1 & 0 \\\\\\\\
    \n\\\\vdots & \\\\vdots \\\\\\\\
    \nB_g^{d_g-1} & 0 \\\\\\\\
    \n0 & B_g^0 \\\\\\\\
    \n\\\\vdots & \\\\vdots \\\\\\\\
    \n0 & B_g^{d_g-1} \\\\\\\\
    \n\\\\end{bmatrix}
    \n<\/span><\/span>G<\/span><\/span>=<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>B<\/span><\/span>g<\/span><\/span><\/span><\/span>0<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>B<\/span><\/span>g<\/span><\/span><\/span><\/span>1<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u22ee<\/span><\/span><\/span><\/span><\/span><\/span>B<\/span><\/span>g<\/span><\/span><\/span><\/span>d<\/span><\/span>g<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u2212<\/span>1<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>0<\/span><\/span><\/span><\/span>\u22ee<\/span><\/span><\/span><\/span><\/span><\/span>0<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>0<\/span><\/span><\/span><\/span>0<\/span><\/span><\/span><\/span>\u22ee<\/span><\/span><\/span><\/span><\/span><\/span>0<\/span><\/span><\/span><\/span>B<\/span><\/span>g<\/span><\/span><\/span><\/span>0<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u22ee<\/span><\/span><\/span><\/span><\/span><\/span>B<\/span><\/span>g<\/span><\/span><\/span><\/span>d<\/span><\/span>g<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u2212<\/span>1<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/p>\n

    \u5219\u521d\u59cb\u5316\u64cd\u4f5c ACC\u2190vACC \\\\leftarrow v<\/span><\/span>A<\/span>CC<\/span><\/span>\u2190<\/span><\/span><\/span><\/span>v<\/span><\/span><\/span><\/span><\/span> \u8bbe\u4e3a：<\/p>\n

    ACC=uxvG\u2208RQ2dg\u00d72
    \nACC = ux^vG \\\\in R_{Q}^{2d_g\\\\times 2}
    \n<\/span><\/span>A<\/span>CC<\/span><\/span>=<\/span><\/span><\/span><\/span>u<\/span>x<\/span><\/span>v<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>G<\/span><\/span>\u2208<\/span><\/span><\/span><\/span>R<\/span><\/span>Q<\/span><\/span><\/span><\/span><\/span>2<\/span>d<\/span><\/span>g<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u00d7<\/span>2<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/p>\n

    \u6ce8\u610f\u5230\u521d\u59cb\u5316\u53ef\u4ee5\u770b\u4f5c\u5bf9 xvx^v<\/span><\/span>x<\/span><\/span>v<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span> \u7684\u4e00\u79cd\u7279\u6b8a RGSW \u52a0\u5bc6（\u6ca1\u6709 LWE \u52a0\u5bc6\u5bf9），\u53ef\u4ee5\u7406\u89e3\u4e3a\u660e\u6587\u7248 RGSW，\u6ca1\u6709\u52a0\u5bc6\u7279\u6027\u4f46\u6ee1\u8db3\u540c\u6001\u7279\u6027，\u4e5f\u548c\u6b63\u5e38\u52a0\u5bc6\u4e00\u6837\u8bb0\u4e3a RGSW(xv)RGSW(x^v)<\/span><\/span>RGS<\/span>W<\/span>(<\/span>x<\/span><\/span>v<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>)<\/span><\/span><\/span><\/span><\/span>\u3002<\/p>\n

    \u8bbe vv<\/span><\/span>v<\/span><\/span><\/span><\/span><\/span> \u4e3a\u5f53\u524d\u7d2f\u52a0\u5668\u5185\u7684\u503c（\u5305\u88f9\u5728 RGSW \u4e2d），\u7d2f\u52a0\u64cd\u4f5c ACC\u2190+E(v\u2032)ACC \\\\xleftarrow{+} E(v')<\/span><\/span>A<\/span>CC<\/span><\/span><\/span>+<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>E<\/span>(<\/span>v<\/span><\/span>\u2032<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>)<\/span><\/span><\/span><\/span><\/span> \u8bbe\u4e3a RGSW \u5185\u79ef：<\/p>\n

    ACC=ACC\u00d7E(v\u2032)=RGSW(xv)\u00d7RGSW(xv\u2032)=RGSW(xv+v\u2032)
    \nACC = ACC \\\\times E(v') = RGSW(x^v) \\\\times RGSW(x^{v'}) = RGSW(x^{v+v'})
    \n<\/span><\/span>A<\/span>CC<\/span><\/span>=<\/span><\/span><\/span><\/span>A<\/span>CC<\/span><\/span>\u00d7<\/span><\/span><\/span><\/span>E<\/span>(<\/span>v<\/span><\/span>\u2032<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>)<\/span><\/span>=<\/span><\/span><\/span><\/span>RGS<\/span>W<\/span>(<\/span>x<\/span><\/span>v<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>)<\/span><\/span>\u00d7<\/span><\/span><\/span><\/span>RGS<\/span>W<\/span>(<\/span>x<\/span><\/span>v<\/span><\/span>\u2032<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>)<\/span><\/span>=<\/span><\/span><\/span><\/span>RGS<\/span>W<\/span>(<\/span>x<\/span><\/span>v<\/span>+<\/span>v<\/span><\/span>\u2032<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>)<\/span><\/span><\/span><\/span><\/span><\/span><\/p>\n

    \u663e\u7136\u5f53\u7d2f\u52a0\u5668\u7684\u6240\u6709\u7d2f\u52a0\u7ed3\u675f\u540e（\u6267\u884c msbExtractmsbExtract<\/span><\/span>m<\/span>s<\/span>b<\/span>E<\/span>x<\/span>t<\/span>r<\/span>a<\/span>c<\/span>t<\/span><\/span><\/span><\/span><\/span> \u4e4b\u524d），\u5bb9\u5668\u5185\u4e3a RGSW(xq2m+e+q4)RGSW(x^{\\\\frac{q}{2}m+e + \\\\frac{q}{4}})<\/span><\/span>RGS<\/span>W<\/span>(<\/span>x<\/span><\/span><\/span><\/span>2<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>q<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>m<\/span>+<\/span>e<\/span>+<\/span><\/span><\/span>4<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>q<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>)<\/span><\/span><\/span><\/span><\/span>\u3002<\/p>\n

    \u8bbe\u4e00\u4e2a\u6d4b\u8bd5\u5411\u91cf t\u20d7=\u2212\u2211i=0i<q2yi\u20d7\\\\vec{t}=-\\\\sum_{i=0}^{i\\\\lt \\\\frac{q}{2}}\\\\vec{y^i}<\/span><\/span><\/span>t<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>=<\/span><\/span><\/span><\/span>\u2212<\/span><\/span>\u2211<\/span><\/span>i<\/span>=<\/span>0<\/span><\/span><\/span><\/span><\/span>i<\/span><<\/span><\/span><\/span>2<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>q<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>y<\/span><\/span>i<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>，\u5176\u4e2d yi\u20d7\\\\vec{y^i}<\/span><\/span><\/span>y<\/span><\/span>i<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span> \u4e3a\u591a\u9879\u5f0f yiy^{i}<\/span><\/span>y<\/span><\/span>i<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span> \u7684\u957f\u5ea6\u4e3a NN<\/span><\/span>N<\/span><\/span><\/span><\/span><\/span> \u7684\u7cfb\u6570\u5411\u91cf\u3002\u663e\u7136\u5f53 q=2Nq=2N<\/span><\/span>q<\/span><\/span>=<\/span><\/span><\/span><\/span>2<\/span>N<\/span><\/span><\/span><\/span><\/span> \u65f6，\u6709 t\u20d7=\u2212\u2211i=0i<q2xi\u20d7={\u22121}N\\\\vec{t}=-\\\\sum_{i=0}^{i\\\\lt \\\\frac{q}{2}}\\\\vec{x^i}=\\\\{-1\\\\}^N<\/span><\/span><\/span>t<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>=<\/span><\/span><\/span><\/span>\u2212<\/span><\/span>\u2211<\/span><\/span>i<\/span>=<\/span>0<\/span><\/span><\/span><\/span><\/span>i<\/span><<\/span><\/span><\/span>2<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>q<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>x<\/span><\/span>i<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>=<\/span><\/span><\/span><\/span>{<\/span>\u2212<\/span>1<\/span>}<\/span><\/span>N<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u3002\u8be5\u6d4b\u8bd5\u5411\u91cf\u5c31\u662f\u63d0\u53d6\u6700\u9ad8\u4f4d\u7684\u5173\u952e\u90e8\u5206，\u4e0d\u96be\u770b\u51fa t\u20d7\u22c5yv\u20d7\\\\vec{t}\\\\cdot \\\\vec{y^v}<\/span><\/span><\/span>t<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u22c5<\/span><\/span><\/span><\/span><\/span>y<\/span><\/span>v<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span> \u7684\u503c\u5728 0\u2264v<N0 \\\\le v \\\\lt N<\/span><\/span>0<\/span><\/span>\u2264<\/span><\/span><\/span><\/span>v<\/span><\/span><<\/span><\/span><\/span><\/span>N<\/span><\/span><\/span><\/span><\/span> \u65f6\u4e3a \u22121-1<\/span><\/span>\u2212<\/span>1<\/span><\/span><\/span><\/span><\/span>，\u5728 N\u2264v<2NN \\\\le v \\\\lt 2N<\/span><\/span>N<\/span><\/span>\u2264<\/span><\/span><\/span><\/span>v<\/span><\/span><<\/span><\/span><\/span><\/span>2<\/span>N<\/span><\/span><\/span><\/span><\/span> \u65f6\u4e3a 11<\/span><\/span>1<\/span><\/span><\/span><\/span><\/span>，\u8fd9\u5c31\u76f8\u5f53\u4e8e\u63d0\u53d6\u4e86 vv<\/span><\/span>v<\/span><\/span><\/span><\/span><\/span> \u7684\u6700\u9ad8\u4f4d\u3002<\/p>\n

    FHEW \u5c31\u662f\u5229\u7528\u8fd9\u4e2a\u7279\u6027\u6765\u5b9e\u73b0\u7d2f\u52a0\u5668\u7684\u540c\u6001\u63d0\u53d6\u6700\u9ad8\u4f4d\u64cd\u4f5c c\u2190msbExtract(ACC)c\\\\leftarrow msbExtract(ACC)<\/span><\/span>c<\/span><\/span>\u2190<\/span><\/span><\/span><\/span>m<\/span>s<\/span>b<\/span>E<\/span>x<\/span>t<\/span>r<\/span>a<\/span>c<\/span>t<\/span>(<\/span>A<\/span>CC<\/span>)<\/span><\/span><\/span><\/span><\/span>：<\/p>\n

    \u9996\u5148\u53d6\u7d2f\u52a0\u5668\u5bb9\u5668\u4e2d\u7684 RGSW(xq2m+e+q4)RGSW(x^{\\\\frac{q}{2}m+e + \\\\frac{q}{4}})<\/span><\/span>RGS<\/span>W<\/span>(<\/span>x<\/span><\/span><\/span><\/span>2<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>q<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>m<\/span>+<\/span>e<\/span>+<\/span><\/span><\/span>4<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>q<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>)<\/span><\/span><\/span><\/span><\/span> \u7684\u7b2c dg+1d_g+1<\/span><\/span>d<\/span><\/span>g<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>+<\/span><\/span><\/span><\/span>1<\/span><\/span><\/span><\/span><\/span> \u884c（\u539f\u8bba\u6587\u4e2d\u4e3a\u7b2c 2 \u884c，\u4ec5\u4e3a\u987a\u5e8f\u533a\u522b）\u7684\u503c\u4e3a RLWE(xq2m+e+q4)=(a,b)RLWE(x^{\\\\frac{q}{2}m+e + \\\\frac{q}{4}})=(a,b)<\/span><\/span>R<\/span>L<\/span>W<\/span>E<\/span>(<\/span>x<\/span><\/span><\/span><\/span>2<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>q<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>m<\/span>+<\/span>e<\/span>+<\/span><\/span><\/span>4<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>q<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>)<\/span><\/span>=<\/span><\/span><\/span><\/span>(<\/span>a<\/span>,<\/span><\/span>b<\/span>)<\/span><\/span><\/span><\/span><\/span>，\u8ba1\u7b97：<\/p>\n

    c=(t\u20d7\u22c5a,t\u20d7\u22c5b+u)=(t\u20d7\u22c5a,t\u20d7\u22c5az+t\u20d7e+ut\u20d7xq2m+e+q4+u)
    \nc=(\\\\vec{t}\\\\cdot a,\\\\vec{t}\\\\cdot b+u) = (\\\\vec{t}\\\\cdot a,\\\\vec{t}\\\\cdot az + \\\\vec{t}e + u\\\\vec{t}x^{\\\\frac{q}{2}m+e + \\\\frac{q}{4}} +u)
    \n<\/span><\/span>c<\/span><\/span>=<\/span><\/span><\/span><\/span>(<\/span><\/span>t<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u22c5<\/span><\/span><\/span><\/span>a<\/span>,<\/span><\/span><\/span>t<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u22c5<\/span><\/span><\/span><\/span>b<\/span><\/span>+<\/span><\/span><\/span><\/span>u<\/span>)<\/span><\/span>=<\/span><\/span><\/span><\/span>(<\/span><\/span>t<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u22c5<\/span><\/span><\/span><\/span>a<\/span>,<\/span><\/span><\/span>t<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u22c5<\/span><\/span><\/span><\/span>a<\/span>z<\/span><\/span>+<\/span><\/span><\/span><\/span><\/span>t<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>e<\/span><\/span>+<\/span><\/span><\/span><\/span>u<\/span><\/span>t<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>x<\/span><\/span><\/span><\/span>2<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>q<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>m<\/span>+<\/span>e<\/span>+<\/span><\/span><\/span>4<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>q<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>+<\/span><\/span><\/span><\/span>u<\/span>)<\/span><\/span><\/span><\/span><\/span><\/span><\/p>\n

    \u5176\u4e2d t\u20d7\\\\vec{t}<\/span><\/span><\/span>t<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span> \u4e3a\u5411\u91cf，\u5176\u4e0e\u5411\u91cf\u4e58\u6cd5\u4e3a\u5185\u79ef\u8fd0\u7b97，\u7ed3\u679c\u4e3a\u6570\u503c；\u4e0e\u591a\u9879\u5f0f\u4e58\u6cd5\u53ef\u4ee5\u770b\u4f5c\u5c06\u5411\u91cf\u4f5c\u4e3a\u591a\u9879\u5f0f\u7cfb\u6570\u7ec4\u6210\u591a\u9879\u5f0f\u540e，\u8fdb\u884c\u591a\u9879\u5f0f\u4e58\u6cd5，\u518d\u53d6\u7cfb\u6570\u5411\u91cf，\u7ed3\u679c\u8fd8\u662f\u5411\u91cf\u3002\u8bb0 a\u2032=t\u20d7\u22c5a,e\u2032=t\u20d7ea'=\\\\vec{t}\\\\cdot a, e'=\\\\vec{t}e<\/span><\/span>a<\/span><\/span>\u2032<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>=<\/span><\/span><\/span><\/span><\/span>t<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u22c5<\/span><\/span><\/span><\/span>a<\/span>,<\/span><\/span>e<\/span><\/span>\u2032<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>=<\/span><\/span><\/span><\/span><\/span>t<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>e<\/span><\/span><\/span><\/span><\/span>，\u540c\u65f6\u6709 ut\u20d7xq2m+e+q4+u=2u\u22c5msbExtract(q2m+e+q4)=2umu\\\\vec{t}x^{\\\\frac{q}{2}m+e + \\\\frac{q}{4}} +u=2u\\\\cdot msbExtract(\\\\frac{q}{2}m+e + \\\\frac{q}{4})=2um<\/span><\/span>u<\/span><\/span>t<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>x<\/span><\/span><\/span><\/span>2<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>q<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>m<\/span>+<\/span>e<\/span>+<\/span><\/span><\/span>4<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>q<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>+<\/span><\/span><\/span><\/span>u<\/span><\/span>=<\/span><\/span><\/span><\/span>2<\/span>u<\/span><\/span>\u22c5<\/span><\/span><\/span><\/span>m<\/span>s<\/span>b<\/span>E<\/span>x<\/span>t<\/span>r<\/span>a<\/span>c<\/span>t<\/span>(<\/span><\/span><\/span>2<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>q<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>m<\/span><\/span>+<\/span><\/span><\/span><\/span>e<\/span><\/span>+<\/span><\/span><\/span><\/span><\/span><\/span>4<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>q<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>)<\/span><\/span>=<\/span><\/span><\/span><\/span>2<\/span>u<\/span>m<\/span><\/span><\/span><\/span><\/span>，\u56e0\u6b64\u6709：<\/p>\n

    c=(a\u2032,b\u2032)=(a\u2032,a\u2032z+e\u2032+2um)
    \nc = (a',b')=(a',a'z+e'+2um)
    \n<\/span><\/span>c<\/span><\/span>=<\/span><\/span><\/span><\/span>(<\/span>a<\/span><\/span>\u2032<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>,<\/span><\/span>b<\/span><\/span>\u2032<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>)<\/span><\/span>=<\/span><\/span><\/span><\/span>(<\/span>a<\/span><\/span>\u2032<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>,<\/span><\/span>a<\/span><\/span>\u2032<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>z<\/span><\/span>+<\/span><\/span><\/span><\/span>e<\/span><\/span>\u2032<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>+<\/span><\/span><\/span><\/span>2<\/span>u<\/span>m<\/span>)<\/span><\/span><\/span><\/span><\/span><\/span><\/p>\n

    \u8003\u8651\u5230 2u\u2248Qt2u\\\\approx \\\\frac{Q}{t}<\/span><\/span>2<\/span>u<\/span><\/span>\u2248<\/span><\/span><\/span><\/span><\/span><\/span>t<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>Q<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>，\u56e0\u6b64\u4e0a\u8ff0\u5bc6\u6587 cc<\/span><\/span>c<\/span><\/span><\/span><\/span><\/span> \u76f8\u5f53\u4e8e LWEzt\/Q(m)LWE_z^{t\/Q}(m)<\/span><\/span>L<\/span>W<\/span>E<\/span><\/span>z<\/span><\/span><\/span><\/span>t<\/span>\/<\/span>Q<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>(<\/span>m<\/span>)<\/span><\/span><\/span><\/span><\/span>\u3002<\/p>\n

    \u968f\u540e\u6267\u884c\u5bc6\u94a5\u8f6c\u6362\u5f97\u5230（\u548c BGV \/ BFV \u65b9\u6848\u4e2d\u7684\u5bc6\u94a5\u8f6c\u6362\u7c7b\u4f3c，\u672c\u8d28\u4e3a\u7528\u65b0\u5bc6\u94a5\u52a0\u5bc6\u65e7\u5bc6\u94a5，\u8fd9\u91cc\u4e0d\u518d\u8d58\u8ff0）：<\/p>\n

    c\u2032=LWEst\/Q(m)=KeySwitch(LWEzt\/Q(m))
    \nc'=LWE_s^{t\/Q}(m)=KeySwitch(LWE_z^{t\/Q}(m))
    \n<\/span><\/span>c<\/span><\/span>\u2032<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>=<\/span><\/span><\/span><\/span>L<\/span>W<\/span>E<\/span><\/span>s<\/span><\/span><\/span><\/span>t<\/span>\/<\/span>Q<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>(<\/span>m<\/span>)<\/span><\/span>=<\/span><\/span><\/span><\/span>Key<\/span>Sw<\/span>i<\/span>t<\/span>c<\/span>h<\/span>(<\/span>L<\/span>W<\/span>E<\/span><\/span>z<\/span><\/span><\/span><\/span>t<\/span>\/<\/span>Q<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>(<\/span>m<\/span>))<\/span><\/span><\/span><\/span><\/span><\/span><\/p>\n

    \u518d\u6267\u884c\u6a21\u6570\u8f6c\u6362\u5f97\u5230（\u53c2\u8003 BGV \u65b9\u6848）：<\/p>\n

    c\u2032\u2032=LWEst\/q(m)=ModSwitch(LWEst\/Q(m))
    \nc'' = LWE_s^{t\/q}(m) = ModSwitch(LWE_s^{t\/Q}(m))
    \n<\/span><\/span>c<\/span><\/span>\u2032\u2032<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>=<\/span><\/span><\/span><\/span>L<\/span>W<\/span>E<\/span><\/span>s<\/span><\/span><\/span><\/span>t<\/span>\/<\/span>q<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>(<\/span>m<\/span>)<\/span><\/span>=<\/span><\/span><\/span><\/span>M<\/span>o<\/span>d<\/span>Sw<\/span>i<\/span>t<\/span>c<\/span>h<\/span>(<\/span>L<\/span>W<\/span>E<\/span><\/span>s<\/span><\/span><\/span><\/span>t<\/span>\/<\/span>Q<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>(<\/span>m<\/span>))<\/span><\/span><\/span><\/span><\/span><\/span><\/p>\n

    \u81f3\u6b64\u4e3a\u7d2f\u52a0\u5668\u7684\u540c\u6001\u63d0\u53d6\u6700\u9ad8\u4f4d\u64cd\u4f5c c\u2190msbExtract(ACC)c\\\\leftarrow msbExtract(ACC)<\/span><\/span>c<\/span><\/span>\u2190<\/span><\/span><\/span><\/span>m<\/span>s<\/span>b<\/span>E<\/span>x<\/span>t<\/span>r<\/span>a<\/span>c<\/span>t<\/span>(<\/span>A<\/span>CC<\/span>)<\/span><\/span><\/span><\/span><\/span> \u7684\u5168\u90e8\u6d41\u7a0b，\u7ed3\u679c\u4e3a c\u2032\u2032c''<\/span><\/span>c<\/span><\/span>\u2032\u2032<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u3002<\/p>\n

    \u8bba\u6587\u7ed9\u51fa\u4e86 c\u2032\u2032c''<\/span><\/span>c<\/span><\/span>\u2032\u2032<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span> \u566a\u58f0\u5927\u5c0f \u2223e\u2032\u2032\u2223<q16|e''|\\\\lt \\\\frac{q}{16}<\/span><\/span>\u2223<\/span>e<\/span><\/span>\u2032\u2032<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u2223<\/span><\/span><<\/span><\/span><\/span><\/span><\/span><\/span>16<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>q<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span> \u7684\u8be6\u7ec6\u8bc1\u660e，\u5305\u62ec\u5982\u4f55\u5408\u7406\u7684\u9009\u53d6\u53c2\u6570，\u8fd9\u91cc\u4e0d\u518d\u5c55\u5f00\u8be6\u7ec6\u8ba8\u8bba，\u53ea\u8fdb\u884c\u7b80\u5355\u8bf4\u660e\u3002\u53ef\u4ee5\u770b\u51fa\u539f\u5bc6\u6587\u7684\u566a\u58f0\u4e0a\u9650 q4\\\\frac{q}{4}<\/span><\/span><\/span><\/span>4<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>q<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span> \u5728\u7ecf\u8fc7\u6700\u9ad8\u4f4d\u63d0\u53d6\u4e4b\u540e\u88ab\u6d88\u9664\u6389\u4e86（\u56e0\u4e3a\u566a\u58f0\u5728 xvx^v<\/span><\/span>x<\/span><\/span>v<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span> \u7684\u6307\u6570 vv<\/span><\/span>v<\/span><\/span><\/span><\/span><\/span> \u4e2d，\u6700\u9ad8\u4f4d\u63d0\u53d6\u7ed3\u679c\u8981\u4e48\u4e3a 0 \u8981\u4e48\u4e3a 1），\u800c\u65b0\u4ea7\u751f\u7684\u566a\u58f0\u53ea\u4e0e\u7d2f\u52a0\u5668\u4e2d\u7684 RGSW \u52a0\u5bc6\u548c\u4e58\u6cd5\u8fd0\u7b97\u6709\u5173\u3002\u800c RGSW \u52a0\u5bc6\u65f6\u5f15\u5165\u7684\u566a\u58f0\u53ef\u4ee5\u6839\u636e\u5b89\u5168\u53c2\u6570\u5408\u7406\u8bbe\u7f6e，\u5bc6\u6587\u540c\u6001\u5185\u79ef\u4ea7\u751f\u7684\u566a\u58f0\u4e3a\u82e5\u5e72 BgeB_ge<\/span><\/span>B<\/span><\/span>g<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>e<\/span><\/span><\/span><\/span><\/span> \u4e4b\u548c，\u901a\u8fc7\u5408\u7406\u7684\u8bbe\u7f6e\u53c2\u6570\u5c31\u80fd\u5b9e\u73b0\u6700\u7ec8\u7684\u5bc6\u6587\u566a\u58f0\u5927\u5c0f\u6ee1\u8db3 \u2223e\u2032\u2032\u2223<q16|e''|\\\\lt \\\\frac{q}{16}<\/span><\/span>\u2223<\/span>e<\/span><\/span>\u2032\u2032<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u2223<\/span><\/span><<\/span><\/span><\/span><\/span><\/span><\/span>16<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>q<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u3002<\/p>\n

    \u53ef\u4ee5\u770b\u5230，\u7ecf\u8fc7\u4e0a\u8ff0\u7d2f\u52a0\u5668\u8fd0\u7b97，FHEW \u65b9\u6848\u5c06 XAND \u8fd0\u7b97\u7684\u8f93\u51fa LWEs2\/q(m0m1\u203e,q4)LWE_s^{2\/q}(\\\\overline{m_0m_1},\\\\frac{q}{4})<\/span><\/span>L<\/span>W<\/span>E<\/span><\/span>s<\/span><\/span><\/span><\/span>2\/<\/span>q<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>(<\/span><\/span>m<\/span><\/span>0<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>m<\/span><\/span>1<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span>,<\/span><\/span><\/span><\/span>4<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>q<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>)<\/span><\/span><\/span><\/span><\/span> \u8f6c\u6362\u4e3a\u4e86 XAND \u8fd0\u7b97\u5408\u6cd5\u7684\u8f93\u5165 LWEs4\/q(m0m1\u203e,q16)LWE_s^{4\/q}(\\\\overline{m_0m_1},\\\\frac{q}{16})<\/span><\/span>L<\/span>W<\/span>E<\/span><\/span>s<\/span><\/span><\/span><\/span>4\/<\/span>q<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>(<\/span><\/span>m<\/span><\/span>0<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>m<\/span><\/span>1<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span>,<\/span><\/span><\/span><\/span>16<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>q<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>)<\/span><\/span><\/span><\/span><\/span>，\u7b49\u4ef7\u4e8e\u5b9e\u73b0\u4e86 XAND \u7535\u8def\u95e8\u7684 Bootstrapping\u8fd0\u7b97，\u8fd9\u610f\u5473\u7740 FHEW \u65b9\u6848\u652f\u6301\u4efb\u610f\u6df1\u5ea6\u5e03\u5c14\u7535\u8def\u7684\u5168\u540c\u6001\u8fd0\u7b97，\u6bcf\u7ecf\u8fc7\u4e00\u4e2a\u7535\u8def\u95e8\u6267\u884c\u4e00\u6b21 Bootstrapping\u3002<\/p>\n

    10. TFHE \u52a0\u5bc6\u65b9\u6848<\/h3>\n

    TFHE \u65b9\u6848\u7531 Chillotti\u3001Gama\u3001Georgieva \u548c Izabach\u00e8ne \u53d1\u8868[16]^{[16]}<\/span><\/span><\/span><\/span>[<\/span>16<\/span>]<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>，\u8be5\u65b9\u6848\u4f18\u5316\u4e86 FHEW \u4e2d\u7684 Bootstrapping \u64cd\u4f5c，\u5e76\u7ed9\u51fa\u4e00\u79cd\u66f4\u901a\u7528\u7684 LWE \u548c GSW \u5b9a\u4e49\u4ee5\u53ca\u82e5\u5e72\u540c\u6001\u8ba1\u7b97\u65b9\u6cd5\u3002<\/p>\n

    \u8be5\u65b9\u6848\u4e2d\u5f15\u5165\u4e86\u4e00\u4e2a\u65b0\u7684\u6570\u636e\u7ed3\u6784 Torus，\u5728\u8be5\u7ed3\u6784\u4e0a\u52a0\u5bc6\u6570\u636e\u6216\u591a\u9879\u5f0f\u7684 LWE \u548c GSW \u7b97\u6cd5\u5206\u522b\u8bb0\u4e3a T\u00aeLWE \u548c T\u00aeGSW\u3002\u5f15\u5165 Torus \u4e3b\u8981\u76ee\u7684\u662f\u5bf9\u82e5\u5e72\u7c7b\u4f3c\u52a0\u5bc6\u65b9\u6848\u8fdb\u884c\u7edf\u4e00\u8868\u793a，\u53ef\u4ee5\u884d\u751f\u51fa\u5982 LWE\u3001RLWE\u3001approx-GCD \u7b49\u52a0\u5bc6\u65b9\u5f0f\u3002\u4e3a\u4e86\u4fbf\u4e8e\u7406\u89e3，\u5728\u4ecb\u7ecd TFHE \u65b9\u6848\u65f6\u4ecd\u7136\u6cbf\u7528\u524d\u6587\u7684\u8868\u793a\u65b9\u5f0f（LWE\u3001RLWE\u3001GSW\u3001RGSW）\u3002<\/p>\n

    \u540c\u6001\u903b\u8f91\u8ba1\u7b97<\/h4>\n

    TFHE \u65b9\u6848\u7ed9\u51fa\u4e86\u82e5\u5e72 LWE-to-LWE \u7684\u540c\u6001\u903b\u8f91\u8ba1\u7b97\u95e8（NOT\u3001AND\u3001NAND\u3001OR\u3001XOR），\u5176\u4e3b\u8981\u601d\u60f3\u4e0e FHEW \u4e00\u81f4，\u5747\u4e3a\u5229\u7528\u4e00\u4e9b\u7ebf\u6027\u53d8\u6362\u5c06\u903b\u8f91\u8fd0\u7b97\u8f6c\u6362\u4e3a\u540c\u6001\u52a0\u6cd5\u548c\u6700\u9ad8\u4f4d\u7684\u63d0\u53d6，\u4e14\u52a0\u5bc6\u65b9\u5f0f\u4e0e FHEW \u7c7b\u4f3c，\u7ebf\u6027\u53d8\u6362\u7b80\u5355\u63cf\u8ff0\u5982\u4e0b：<\/p>\n

      \n
    • \n

      \u540c\u6001 NOT：(0,14)\u2212c(0, \\\\frac{1}{4})-c<\/span><\/span>(<\/span>0<\/span>,<\/span><\/span><\/span><\/span>4<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>1<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>)<\/span><\/span>\u2212<\/span><\/span><\/span><\/span>c<\/span><\/span><\/span><\/span><\/span><\/p>\n<\/li>\n

    • \n

      \u540c\u6001 AND：(0,\u221218)+c1+c2(0, -\\\\frac{1}{8})+c_1+c_2<\/span><\/span>(<\/span>0<\/span>,<\/span><\/span>\u2212<\/span><\/span><\/span>8<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>1<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>)<\/span><\/span>+<\/span><\/span><\/span><\/span>c<\/span><\/span>1<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>+<\/span><\/span><\/span><\/span>c<\/span><\/span>2<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/p>\n<\/li>\n

    • \n

      \u540c\u6001 NAND：(0,58)\u2212c1\u2212c2(0, \\\\frac{5}{8})-c_1-c_2<\/span><\/span>(<\/span>0<\/span>,<\/span><\/span><\/span><\/span>8<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>5<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>)<\/span><\/span>\u2212<\/span><\/span><\/span><\/span>c<\/span><\/span>1<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u2212<\/span><\/span><\/span><\/span>c<\/span><\/span>2<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/p>\n<\/li>\n

    • \n

      \u540c\u6001 OR：(0,18)+c1+c2(0, \\\\frac{1}{8})+c_1+c_2<\/span><\/span>(<\/span>0<\/span>,<\/span><\/span><\/span><\/span>8<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>1<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>)<\/span><\/span>+<\/span><\/span><\/span><\/span>c<\/span><\/span>1<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>+<\/span><\/span><\/span><\/span>c<\/span><\/span>2<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/p>\n<\/li>\n

    • \n

      \u540c\u6001 XOR：2\u22c5(c1\u2212c2)2\\\\cdot (c_1-c_2)<\/span><\/span>2<\/span><\/span>\u22c5<\/span><\/span><\/span><\/span>(<\/span>c<\/span><\/span>1<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u2212<\/span><\/span><\/span><\/span>c<\/span><\/span>2<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>)<\/span><\/span><\/span><\/span><\/span><\/p>\n<\/li>\n<\/ul>\n

      Bootstrapping \u4f18\u5316<\/h4>\n

      TFHE \u65b9\u6848\u7ed9\u51fa\u4e86\u4e00\u4e2a CMux \u95e8\u6765\u66ff\u4ee3 FHEW \u65b9\u6848\u5728 Bootstrapping \u65f6\u4f7f\u7528\u7684 RGSW \u7684\u5185\u79ef，\u5176\u4e2d CMux \u95e8\u7531 RGSW \u548c RLWE \u7684\u5916\u79ef\u7ec4\u6210，\u56e0\u6b64\u80fd\u7701\u53bb FHEW \u4e2d RGSW \u5185\u79ef\u6d6a\u8d39\u7684\u65f6\u95f4\u548c\u7a7a\u95f4\u3002<\/p>\n

      CMux \u9009\u62e9\u95e8<\/h5>\n

      CMux \u9009\u62e9\u95e8\u7531\u4e24\u4e2a\u8f93\u5165 d0,d1d_0,d_1<\/span><\/span>d<\/span><\/span>0<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>,<\/span><\/span>d<\/span><\/span>1<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span> \u548c\u4e00\u4e2a\u63a7\u5236\u7aef CC<\/span><\/span>C<\/span><\/span><\/span><\/span><\/span> \u7ec4\u6210，\u5176\u4e2d CC<\/span><\/span>C<\/span><\/span><\/span><\/span><\/span> \u4e3a\u7531 RGSW \u65b9\u6848\u52a0\u5bc6\u7684\u5355\u4e2a\u6bd4\u7279c\u2208{0,1}c\\\\in\\\\{0,1\\\\}<\/span><\/span>c<\/span><\/span>\u2208<\/span><\/span><\/span><\/span>{<\/span>0<\/span>,<\/span><\/span>1<\/span>}<\/span><\/span><\/span><\/span><\/span>，\u800c d0,d1d_0,d_1<\/span><\/span>d<\/span><\/span>0<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>,<\/span><\/span>d<\/span><\/span>1<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span> \u4e3a\u7531 RLWE \u65b9\u6848\u52a0\u5bc6\u7684\u6570\u636e\u3002<\/p>\n

      \u8be5\u95e8\u7684\u4f5c\u7528\u662f\u6839\u636e\u63a7\u5236\u4fe1\u53f7\u9009\u62e9\u8f93\u51fa：\u5f53 c=0c=0<\/span><\/span>c<\/span><\/span>=<\/span><\/span><\/span><\/span>0<\/span><\/span><\/span><\/span><\/span> \u65f6\u8f93\u51fa d0d_0<\/span><\/span>d<\/span><\/span>0<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>，\u5426\u5219\u8f93\u51fa d1d_1<\/span><\/span>d<\/span><\/span>1<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u3002\u5b9e\u73b0\u65b9\u5f0f\u5982\u4e0b：<\/p>\n

      CMux(C,d0,d1)=C\u22c5(d1\u2212d0)+d0
      \nCMux(C,d_0,d_1)=C \\\\boxed{\\\\cdot} (d_1-d_0) + d_0
      \n<\/span><\/span>CM<\/span>ux<\/span>(<\/span>C<\/span>,<\/span><\/span>d<\/span><\/span>0<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>,<\/span><\/span>d<\/span><\/span>1<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>)<\/span><\/span>=<\/span><\/span><\/span><\/span>C<\/span><\/span>\u22c5<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span>(<\/span>d<\/span><\/span>1<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u2212<\/span><\/span><\/span><\/span>d<\/span><\/span>0<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>)<\/span><\/span>+<\/span><\/span><\/span><\/span>d<\/span><\/span>0<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/p>\n

      \u663e\u7136\u4e0a\u8ff0\u8ba1\u7b97\u7531\u4e00\u6b21 RGSW \u548c RLWE \u7684\u5185\u79ef\u8fd0\u7b97\u4e0e\u82e5\u5e72 RLWE \u7684\u540c\u6001\u52a0\u6cd5\u540c\u6001\u8ba1\u7b97\u5b8c\u6210，\u6b63\u786e\u6027\u663e\u7136\u53ef\u8bc1\u3002<\/p>\n

      TFHE \u7d2f\u52a0\u5668<\/h5>\n

      TFHE \u65b9\u6848\u5728 Bootstrapping \u4e2d\u4f7f\u7528\u7684\u7d2f\u52a0\u5668（ACC）\u672c\u8d28\u4e0a\u4e0e FHEW \u65b9\u6848\u4e00\u81f4\u3002<\/p>\n

      \u5728 TFHE \u65b9\u6848\u4e2d，\u5728\u5bf9\u591a\u9879\u5f0f\u4e58\u4e0a xvx^v<\/span><\/span>x<\/span><\/span>v<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span> \u79f0\u4f5c\u201c\u65cb\u8f6c\u201d（\u56e0\u4e3a\u4ec5\u591a\u9879\u5f0f\u7cfb\u6570\u987a\u5e8f\u548c\u7b26\u53f7\u6539\u53d8），\u5e76\u5229\u7528\u4e00\u4e2a\u65cb\u8f6c\u591a\u9879\u5f0f 1+x+x2+\u22ef+xN\u221211+x+x^2+\\\\cdots + x^{N-1}<\/span><\/span>1<\/span><\/span>+<\/span><\/span><\/span><\/span>x<\/span><\/span>+<\/span><\/span><\/span><\/span>x<\/span><\/span>2<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>+<\/span><\/span><\/span><\/span>\u22ef<\/span><\/span>+<\/span><\/span><\/span><\/span>x<\/span><\/span>N<\/span>\u2212<\/span>1<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span> \u6765\u4ee3\u66ff FHEW \u65b9\u6848\u4e2d\u7684\u6d4b\u8bd5\u5411\u91cf t\u20d7\\\\vec{t}<\/span><\/span><\/span>t<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>，\u4f46\u4e24\u8005\u672c\u8d28\u90fd\u662f\u6839\u636e\u6307\u6570\u7684\u4e0d\u540c\u53d6\u503c\u5f71\u54cd\u6765\u63d0\u53d6\u6307\u6570\u7684\u6700\u9ad8\u4f4d\u3002<\/p>\n

      \u540c\u65f6，TFHE \u65b9\u6848\u5c06\u7d2f\u52a0\u5668\u7684\u7d2f\u52a0\u64cd\u4f5c\u8868\u793a\u4e3a\u4e00\u4e2a CMux \u9009\u62e9\u95e8\u3002\u8003\u8651\u5230 FHEW \u65b9\u6848\u5728\u8fdb\u884c\u7d2f\u52a0\u65f6，\u5f85\u7d2f\u52a0\u5143\u7d20\u4e3a ai,jsiBgja_{i,j}s_iB_g^{j}<\/span><\/span>a<\/span><\/span>i<\/span>,<\/span>j<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>s<\/span><\/span>i<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>B<\/span><\/span>g<\/span><\/span><\/span><\/span>j<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>，TFHE \u65b9\u6848\u5c06\u7d2f\u52a0\u64cd\u4f5c\u8f6c\u6362\u4e3a：<\/p>\n

      ACC\u2190CMux(RGSW(si),xai\u22c5ACC,ACC)
      \nACC \\\\leftarrow CMux(RGSW(s_i),x^{a_i}\\\\cdot ACC, ACC)
      \n<\/span><\/span>A<\/span>CC<\/span><\/span>\u2190<\/span><\/span><\/span><\/span>CM<\/span>ux<\/span>(<\/span>RGS<\/span>W<\/span>(<\/span>s<\/span><\/span>i<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>)<\/span>,<\/span><\/span>x<\/span><\/span>a<\/span><\/span>i<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u22c5<\/span><\/span><\/span><\/span>A<\/span>CC<\/span>,<\/span><\/span>A<\/span>CC<\/span>)<\/span><\/span><\/span><\/span><\/span><\/span><\/p>\n

      \u5176\u4e2d Bootstrapping \u7684\u8f93\u5165 LWE \u5bc6\u6587\u52a0\u5bc6\u7684\u5bc6\u94a5\u4e3a s\u2208{0,1}ns\\\\in \\\\{0,1\\\\}^n<\/span><\/span>s<\/span><\/span>\u2208<\/span><\/span><\/span><\/span>{<\/span>0<\/span>,<\/span><\/span>1<\/span>}<\/span><\/span>n<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>，\u5bb9\u6613\u9a8c\u8bc1：<\/p>\n

      CMux(RGSW(si),xai\u22c5ACC,ACC)=xaisi\u22c5ACC
      \nCMux(RGSW(s_i),x^{a_i}\\\\cdot ACC, ACC)=x^{a_is_i} \\\\cdot ACC
      \n<\/span><\/span>CM<\/span>ux<\/span>(<\/span>RGS<\/span>W<\/span>(<\/span>s<\/span><\/span>i<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>)<\/span>,<\/span><\/span>x<\/span><\/span>a<\/span><\/span>i<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u22c5<\/span><\/span><\/span><\/span>A<\/span>CC<\/span>,<\/span><\/span>A<\/span>CC<\/span>)<\/span><\/span>=<\/span><\/span><\/span><\/span>x<\/span><\/span>a<\/span><\/span>i<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>s<\/span><\/span>i<\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u22c5<\/span><\/span><\/span><\/span>A<\/span>CC<\/span><\/span><\/span><\/span><\/span><\/span><\/p>\n

      \u548c FHEW \u65b9\u6848\u8981\u5b9e\u73b0\u7684\u76ee\u7684\u4e00\u6837，\u4f46\u662f\u4ece\u5185\u79ef\u53d8\u6210\u4e86\u5916\u79ef，\u65f6\u95f4\u548c\u7a7a\u95f4\u90fd\u6709\u6240\u4f18\u5316\u3002\u53ef\u4ee5\u6ce8\u610f\u5230\u5728 FHEW \u65b9\u6848\u4e2d Bootstrapping \u6700\u7ec8\u53ea\u9700\u8981\u53d6\u7ed3\u679c\u77e9\u9635\u7684\u67d0\u4e00\u884c\u5373\u53ef，\u56e0\u6b64\u4f1a\u6709\u5927\u91cf\u7684\u5197\u4f59\u8ba1\u7b97，TFHE \u6b63\u662f\u5bf9\u6b64\u8fdb\u884c\u4e86\u4f18\u5316\u3002<\/p>\n

      TFHE \u5bc6\u94a5\u8f6c\u6362<\/h5>\n

      TFHE \u65b9\u6848\u4e2d\u7ed9\u51fa\u4e86\u4e24\u79cd\u5bc6\u94a5\u8f6c\u6362\u7b97\u6cd5：Public Functional Key Switching \u548c Private Functional Key Switching，\u4e24\u8005\u5747\u53ef\u628a pp<\/span><\/span>p<\/span><\/span><\/span><\/span><\/span> \u4e2a LWE \u52a0\u5bc6\u5bc6\u6587\u8f6c\u6362\u4e3a\u53e6\u4e00\u79cd\u6307\u5b9a\u5bc6\u94a5\u7684 LWE \u6216 RLWE \u5bc6\u6587，\u4e14\u8f6c\u6362\u8fc7\u7a0b\u4e2d\u53ef\u4ee5\u5bf9\u52a0\u5bc6\u7684\u5bc6\u6587\u6267\u884c\u4e00\u6b21\u51fd\u6570\u8fd0\u7b97 f:Zp\u2192Z[x]f:\\\\mathbb{Z}^p\\\\rightarrow \\\\mathbb{Z}[x]<\/span><\/span>f<\/span><\/span>:<\/span><\/span><\/span><\/span>Z<\/span><\/span>p<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u2192<\/span><\/span><\/span><\/span>Z<\/span>[<\/span>x<\/span>]<\/span><\/span><\/span><\/span><\/span>（\u5373\u628a\u6574\u6570\u5411\u91cf\u4ee5\u67d0\u79cd\u89c4\u5219\u8f6c\u6362\u4e3a\u4e00\u4e2a\u591a\u9879\u5f0f）\u3002<\/p>\n

      Public Functional Key Switching \u548c Private Functional Key Switching \u7684\u533a\u522b\u662f\u524d\u8005\u51fd\u6570 ff<\/span><\/span>f<\/span><\/span><\/span><\/span><\/span> \u662f\u516c\u5f00\u7684，\u800c\u540e\u8005\u662f\u4e0d\u516c\u5f00\u7684，\u8f6c\u6362\u601d\u8def\u4e0e\u6b63\u5e38\u7684\u5bc6\u94a5\u8f6c\u6362\u7c7b\u4f3c，\u53ea\u662f\u5728\u8f6c\u6362\u65f6\u989d\u5916\u8ba1\u7b97\u51fd\u6570 ff<\/span><\/span>f<\/span><\/span><\/span><\/span><\/span>\u3002<\/p>\n

      \u5728 TFHE \u7684 Gate-Bootstrapping （LWE to LWE）\u4e2d\u6700\u540e\u8fd8\u662f\u4f7f\u7528\u6b63\u5e38\u7684\u5bc6\u94a5\u8f6c\u6362（\u4e0e FHEW \u4e00\u81f4）\u8fdb\u884c\u5904\u7406，\u8bbe\u8ba1\u4e0a\u8ff0\u5bc6\u94a5\u8f6c\u6362\u662f\u4e3a\u4e86\u5b9e\u73b0 TFHE \u7684 Circuit-Bootstrapping （LWE to RGSW）\u3002\u56e0\u4e3a TFHE \u63d0\u4f9b\u4e86\u5f88\u591a\u8f93\u5165 RGSW \u5bc6\u6587\u8f93\u51fa LWE \u5bc6\u6587\u7684\u540c\u6001\u8ba1\u7b97\u7535\u8def，\u4e3a\u4e86\u5b9e\u73b0\u65e0\u9650\u6df1\u5ea6\u7684\u5168\u540c\u6001\u8ba1\u7b97\u5fc5\u987b\u63d0\u4f9b\u5bf9\u5e94\u7684 Bootstrapping \u8fd0\u7b97，\u611f\u5174\u8da3\u53ef\u4ee5\u67e5\u770b\u539f\u8bba\u6587\u3002<\/p>\n

      \n

      \u81f3\u6b64，\u5bf9\u4e8e\u540c\u6001\u52a0\u5bc6\u6280\u672f\u7684\u5927\u81f4\u4ecb\u7ecd\u7ed3\u675f\u3002\u4e8b\u5b9e\u4e0a\u8fd8\u6709\u5f88\u591a\u6ca1\u6709\u63d0\u5230\u7684\u5185\u5bb9，\u6216\u8bb8\u4f1a\u5728\u4ee5\u540e\u8fdb\u884c\u8865\u5145\u3002<\/p>\n

      \u53c2\u8003\u6587\u732e（\u7eed）<\/h2>\n
        \n
      • \n

        [14] C. Gentry, A. Sahai, and B. Waters, \u201cHomomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based,\u201d in Advances in Cryptology \u2013 CRYPTO 2013, R. Canetti and J. A. Garay, Eds., Berlin, Heidelberg: Springer, 2013, pp. 75\u201392.<\/p>\n<\/li>\n

      • \n

        [15] L. Ducas and D. Micciancio, \u201cFHEW: Bootstrapping Homomorphic Encryption in Less Than a Second,\u201d in Advances in Cryptology \u2013 EUROCRYPT 2015, E. Oswald and M. Fischlin, Eds., Berlin, Heidelberg: Springer, 2015, pp. 617\u2013640.<\/p>\n<\/li>\n

      • \n

        [16] I. Chillotti, N. Gama, M. Georgieva, and M. Izabach\u00e8ne, \u201cTFHE: Fast Fully Homomorphic Encryption Over the Torus,\u201d J. Cryptol., vol. 33, no. 1, pp. 34\u201391, Jan. 2020.<\/p>\n<\/li>\n<\/ul>\n

        \n

        \u672c\u6587\u4e3a\u4f5c\u8005\u5728\u5b66\u4e60\u76f8\u5173\u77e5\u8bc6\u65f6\u7684\u4e00\u79cd\u8bb0\u5f55，\u4fbf\u4e8e\u4ee5\u540e\u7684\u56de\u987e\u3002\u4f5c\u8005\u5e76\u6ca1\u6709\u7cfb\u7edf\u5730\u5b66\u4e60\u8fc7\u5bc6\u7801\u5b66，\u56e0\u6b64\u5728\u8868\u8ff0\u4e0a\u53ef\u80fd\u4f1a\u5b58\u5728\u4e0d\u4e25\u8c28\u751a\u81f3\u51fa\u9519\u7684\u5730\u65b9，\u6587\u7ae0\u4ec5\u4f9b\u53c2\u8003，\u6b22\u8fce\u5927\u5bb6\u4e0e\u6211\u4ea4\u6d41，\u4e00\u8d77\u8fdb\u6b65！<\/p>\n

        \u5176\u4ed6\u5e73\u53f0：<\/p>\n

          \n
        • \u77e5\u4e4e（Totoro）：https:\/\/www.zhihu.com\/people\/totoro-14-60<\/li>\n
        • B\u7ad9（Totoro_134）：https:\/\/space.bilibili.com\/279377771<\/li>\n
        • Github（Totoro134）：https:\/\/github.com\/Totoro134<\/li>\n
        • \u516c\u4f17\u53f7（\u77e5\u8bc6\u957f\u751f\u6240）<\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"

          \u6587\u7ae0\u6d4f\u89c8\u9605\u8bfb14\u6b21\u3002\u672c\u6587\u4e3b\u8981\u8bb0\u5f55\u9690\u79c1\u8ba1\u7b97\u4e2d\u7684\u540c\u6001\u52a0\u5bc6\uff08Homomorphic Encryption\uff0cHE\uff09\u6280\u672f\uff0c\u5305\u62ec\u90e8\u5206\u540c\u6001\u52a0\u5bc6\uff08RSA\u3001GM\u3001ElGamal\u3001Paillier\uff09\u3001\u8fd1\u4f3c\u540c\u6001\u52a0\u5bc6\uff08BGN\uff09\u3001\u6709\u9650\u7ea7\u6570\u5168\u540c\u6001\u52a0\u5bc6\u548c\u5168\u540c\u6001\u52a0\u5bc6\uff08DGHV\u3001BGV\u3001BFV\u3001CKKS\u3001GSW\u3001FHEW\u3001TFHE\uff09\u7b49\u6280\u672f\uff0c\u4ec5\u4f9b\u53c2\u8003\u3002<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[4672,371,61,1425,427,4671],"topic":[],"class_list":["post-48327","post","type-post","status-publish","format-standard","hentry","category-server","tag-4672","tag-371","tag-61","tag-1425","tag-427","tag-4671"],"yoast_head":"\n\u9690\u79c1\u8ba1\u7b97\u57fa\u7840\u5b66\u4e60\u2014\u2014\u540c\u6001\u52a0\u5bc6\u6280\u672f\uff08\u4ece\u90e8\u5206\u540c\u6001\u5230\u5168\u540c\u6001\u7684\u53d1\u5c55\u4e0e\u7b97\u6cd5\u4ecb\u7ecd 4\/4\uff09 - \u7f51\u7855\u4e92\u8054\u5e2e\u52a9\u4e2d\u5fc3<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/www.wsisp.com\/helps\/48327.html\" \/>\n<meta property=\"og:locale\" content=\"zh_CN\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"\u9690\u79c1\u8ba1\u7b97\u57fa\u7840\u5b66\u4e60\u2014\u2014\u540c\u6001\u52a0\u5bc6\u6280\u672f\uff08\u4ece\u90e8\u5206\u540c\u6001\u5230\u5168\u540c\u6001\u7684\u53d1\u5c55\u4e0e\u7b97\u6cd5\u4ecb\u7ecd 4\/4\uff09 - \u7f51\u7855\u4e92\u8054\u5e2e\u52a9\u4e2d\u5fc3\" \/>\n<meta property=\"og:description\" content=\"\u6587\u7ae0\u6d4f\u89c8\u9605\u8bfb14\u6b21\u3002\u672c\u6587\u4e3b\u8981\u8bb0\u5f55\u9690\u79c1\u8ba1\u7b97\u4e2d\u7684\u540c\u6001\u52a0\u5bc6\uff08Homomorphic Encryption\uff0cHE\uff09\u6280\u672f\uff0c\u5305\u62ec\u90e8\u5206\u540c\u6001\u52a0\u5bc6\uff08RSA\u3001GM\u3001ElGamal\u3001Paillier\uff09\u3001\u8fd1\u4f3c\u540c\u6001\u52a0\u5bc6\uff08BGN\uff09\u3001\u6709\u9650\u7ea7\u6570\u5168\u540c\u6001\u52a0\u5bc6\u548c\u5168\u540c\u6001\u52a0\u5bc6\uff08DGHV\u3001BGV\u3001BFV\u3001CKKS\u3001GSW\u3001FHEW\u3001TFHE\uff09\u7b49\u6280\u672f\uff0c\u4ec5\u4f9b\u53c2\u8003\u3002\" \/>\n<meta property=\"og:url\" content=\"https:\/\/www.wsisp.com\/helps\/48327.html\" \/>\n<meta property=\"og:site_name\" content=\"\u7f51\u7855\u4e92\u8054\u5e2e\u52a9\u4e2d\u5fc3\" \/>\n<meta property=\"article:published_time\" content=\"2025-07-30T03:37:30+00:00\" \/>\n<meta name=\"author\" content=\"admin\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"\u4f5c\u8005\" \/>\n\t<meta name=\"twitter:data1\" content=\"admin\" \/>\n\t<meta name=\"twitter:label2\" content=\"\u9884\u8ba1\u9605\u8bfb\u65f6\u95f4\" \/>\n\t<meta name=\"twitter:data2\" content=\"23 \u5206\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"WebPage\",\"@id\":\"https:\/\/www.wsisp.com\/helps\/48327.html\",\"url\":\"https:\/\/www.wsisp.com\/helps\/48327.html\",\"name\":\"\u9690\u79c1\u8ba1\u7b97\u57fa\u7840\u5b66\u4e60\u2014\u2014\u540c\u6001\u52a0\u5bc6\u6280\u672f\uff08\u4ece\u90e8\u5206\u540c\u6001\u5230\u5168\u540c\u6001\u7684\u53d1\u5c55\u4e0e\u7b97\u6cd5\u4ecb\u7ecd 4\/4\uff09 - \u7f51\u7855\u4e92\u8054\u5e2e\u52a9\u4e2d\u5fc3\",\"isPartOf\":{\"@id\":\"https:\/\/www.wsisp.com\/helps\/#website\"},\"datePublished\":\"2025-07-30T03:37:30+00:00\",\"dateModified\":\"2025-07-30T03:37:30+00:00\",\"author\":{\"@id\":\"https:\/\/www.wsisp.com\/helps\/#\/schema\/person\/358e386c577a3ab51c4493330a20ad41\"},\"breadcrumb\":{\"@id\":\"https:\/\/www.wsisp.com\/helps\/48327.html#breadcrumb\"},\"inLanguage\":\"zh-Hans\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/www.wsisp.com\/helps\/48327.html\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/www.wsisp.com\/helps\/48327.html#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"\u9996\u9875\",\"item\":\"https:\/\/www.wsisp.com\/helps\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"\u9690\u79c1\u8ba1\u7b97\u57fa\u7840\u5b66\u4e60\u2014\u2014\u540c\u6001\u52a0\u5bc6\u6280\u672f\uff08\u4ece\u90e8\u5206\u540c\u6001\u5230\u5168\u540c\u6001\u7684\u53d1\u5c55\u4e0e\u7b97\u6cd5\u4ecb\u7ecd 4\/4\uff09\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/www.wsisp.com\/helps\/#website\",\"url\":\"https:\/\/www.wsisp.com\/helps\/\",\"name\":\"\u7f51\u7855\u4e92\u8054\u5e2e\u52a9\u4e2d\u5fc3\",\"description\":\"\u9999\u6e2f\u670d\u52a1\u5668_\u9999\u6e2f\u4e91\u670d\u52a1\u5668\u8d44\u8baf_\u670d\u52a1\u5668\u5e2e\u52a9\u6587\u6863_\u670d\u52a1\u5668\u6559\u7a0b\",\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/www.wsisp.com\/helps\/?s={search_term_string}\"},\"query-input\":\"required name=search_term_string\"}],\"inLanguage\":\"zh-Hans\"},{\"@type\":\"Person\",\"@id\":\"https:\/\/www.wsisp.com\/helps\/#\/schema\/person\/358e386c577a3ab51c4493330a20ad41\",\"name\":\"admin\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"zh-Hans\",\"@id\":\"https:\/\/www.wsisp.com\/helps\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/gravatar.wp-china-yes.net\/avatar\/?s=96&d=mystery\",\"contentUrl\":\"https:\/\/gravatar.wp-china-yes.net\/avatar\/?s=96&d=mystery\",\"caption\":\"admin\"},\"sameAs\":[\"http:\/\/wp.wsisp.com\"],\"url\":\"https:\/\/www.wsisp.com\/helps\/author\/admin\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"\u9690\u79c1\u8ba1\u7b97\u57fa\u7840\u5b66\u4e60\u2014\u2014\u540c\u6001\u52a0\u5bc6\u6280\u672f\uff08\u4ece\u90e8\u5206\u540c\u6001\u5230\u5168\u540c\u6001\u7684\u53d1\u5c55\u4e0e\u7b97\u6cd5\u4ecb\u7ecd 4\/4\uff09 - \u7f51\u7855\u4e92\u8054\u5e2e\u52a9\u4e2d\u5fc3","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/www.wsisp.com\/helps\/48327.html","og_locale":"zh_CN","og_type":"article","og_title":"\u9690\u79c1\u8ba1\u7b97\u57fa\u7840\u5b66\u4e60\u2014\u2014\u540c\u6001\u52a0\u5bc6\u6280\u672f\uff08\u4ece\u90e8\u5206\u540c\u6001\u5230\u5168\u540c\u6001\u7684\u53d1\u5c55\u4e0e\u7b97\u6cd5\u4ecb\u7ecd 4\/4\uff09 - \u7f51\u7855\u4e92\u8054\u5e2e\u52a9\u4e2d\u5fc3","og_description":"\u6587\u7ae0\u6d4f\u89c8\u9605\u8bfb14\u6b21\u3002\u672c\u6587\u4e3b\u8981\u8bb0\u5f55\u9690\u79c1\u8ba1\u7b97\u4e2d\u7684\u540c\u6001\u52a0\u5bc6\uff08Homomorphic Encryption\uff0cHE\uff09\u6280\u672f\uff0c\u5305\u62ec\u90e8\u5206\u540c\u6001\u52a0\u5bc6\uff08RSA\u3001GM\u3001ElGamal\u3001Paillier\uff09\u3001\u8fd1\u4f3c\u540c\u6001\u52a0\u5bc6\uff08BGN\uff09\u3001\u6709\u9650\u7ea7\u6570\u5168\u540c\u6001\u52a0\u5bc6\u548c\u5168\u540c\u6001\u52a0\u5bc6\uff08DGHV\u3001BGV\u3001BFV\u3001CKKS\u3001GSW\u3001FHEW\u3001TFHE\uff09\u7b49\u6280\u672f\uff0c\u4ec5\u4f9b\u53c2\u8003\u3002","og_url":"https:\/\/www.wsisp.com\/helps\/48327.html","og_site_name":"\u7f51\u7855\u4e92\u8054\u5e2e\u52a9\u4e2d\u5fc3","article_published_time":"2025-07-30T03:37:30+00:00","author":"admin","twitter_card":"summary_large_image","twitter_misc":{"\u4f5c\u8005":"admin","\u9884\u8ba1\u9605\u8bfb\u65f6\u95f4":"23 \u5206"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"WebPage","@id":"https:\/\/www.wsisp.com\/helps\/48327.html","url":"https:\/\/www.wsisp.com\/helps\/48327.html","name":"\u9690\u79c1\u8ba1\u7b97\u57fa\u7840\u5b66\u4e60\u2014\u2014\u540c\u6001\u52a0\u5bc6\u6280\u672f\uff08\u4ece\u90e8\u5206\u540c\u6001\u5230\u5168\u540c\u6001\u7684\u53d1\u5c55\u4e0e\u7b97\u6cd5\u4ecb\u7ecd 4\/4\uff09 - \u7f51\u7855\u4e92\u8054\u5e2e\u52a9\u4e2d\u5fc3","isPartOf":{"@id":"https:\/\/www.wsisp.com\/helps\/#website"},"datePublished":"2025-07-30T03:37:30+00:00","dateModified":"2025-07-30T03:37:30+00:00","author":{"@id":"https:\/\/www.wsisp.com\/helps\/#\/schema\/person\/358e386c577a3ab51c4493330a20ad41"},"breadcrumb":{"@id":"https:\/\/www.wsisp.com\/helps\/48327.html#breadcrumb"},"inLanguage":"zh-Hans","potentialAction":[{"@type":"ReadAction","target":["https:\/\/www.wsisp.com\/helps\/48327.html"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/www.wsisp.com\/helps\/48327.html#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"\u9996\u9875","item":"https:\/\/www.wsisp.com\/helps"},{"@type":"ListItem","position":2,"name":"\u9690\u79c1\u8ba1\u7b97\u57fa\u7840\u5b66\u4e60\u2014\u2014\u540c\u6001\u52a0\u5bc6\u6280\u672f\uff08\u4ece\u90e8\u5206\u540c\u6001\u5230\u5168\u540c\u6001\u7684\u53d1\u5c55\u4e0e\u7b97\u6cd5\u4ecb\u7ecd 4\/4\uff09"}]},{"@type":"WebSite","@id":"https:\/\/www.wsisp.com\/helps\/#website","url":"https:\/\/www.wsisp.com\/helps\/","name":"\u7f51\u7855\u4e92\u8054\u5e2e\u52a9\u4e2d\u5fc3","description":"\u9999\u6e2f\u670d\u52a1\u5668_\u9999\u6e2f\u4e91\u670d\u52a1\u5668\u8d44\u8baf_\u670d\u52a1\u5668\u5e2e\u52a9\u6587\u6863_\u670d\u52a1\u5668\u6559\u7a0b","potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/www.wsisp.com\/helps\/?s={search_term_string}"},"query-input":"required name=search_term_string"}],"inLanguage":"zh-Hans"},{"@type":"Person","@id":"https:\/\/www.wsisp.com\/helps\/#\/schema\/person\/358e386c577a3ab51c4493330a20ad41","name":"admin","image":{"@type":"ImageObject","inLanguage":"zh-Hans","@id":"https:\/\/www.wsisp.com\/helps\/#\/schema\/person\/image\/","url":"https:\/\/gravatar.wp-china-yes.net\/avatar\/?s=96&d=mystery","contentUrl":"https:\/\/gravatar.wp-china-yes.net\/avatar\/?s=96&d=mystery","caption":"admin"},"sameAs":["http:\/\/wp.wsisp.com"],"url":"https:\/\/www.wsisp.com\/helps\/author\/admin"}]}},"_links":{"self":[{"href":"https:\/\/www.wsisp.com\/helps\/wp-json\/wp\/v2\/posts\/48327","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wsisp.com\/helps\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wsisp.com\/helps\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wsisp.com\/helps\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wsisp.com\/helps\/wp-json\/wp\/v2\/comments?post=48327"}],"version-history":[{"count":0,"href":"https:\/\/www.wsisp.com\/helps\/wp-json\/wp\/v2\/posts\/48327\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wsisp.com\/helps\/wp-json\/wp\/v2\/media?parent=48327"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wsisp.com\/helps\/wp-json\/wp\/v2\/categories?post=48327"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wsisp.com\/helps\/wp-json\/wp\/v2\/tags?post=48327"},{"taxonomy":"topic","embeddable":true,"href":"https:\/\/www.wsisp.com\/helps\/wp-json\/wp\/v2\/topic?post=48327"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}