HElib 使用样例

参考文献：

HElib：编译安装

文章目录

helib::BGV

helib::BGV

BGV 方案的 SIMD 技术，

模数 $p\ge 2$ ，Hensel Lifting 指数 $\ge 1$ ，分圆环的次数 $\in \mathbb Z$
明文空间：多项式环 $\mathbb A_{p^r} = \mathbb Z_{p^r}[X]/(\Phi_m(X))$
明文槽：多项式环 $\mathbb Z_{p^r}[X]/(F_i(X))$ ，其中 $\Phi_m = \prod_i F_i \pmod{p^r}$ 是环 $\mathbb Z_{p^r}$ 上的不可约分解

示例代码

计时器：

#ifndef CPUTIMER_H
#define CPUTIMER_H

#include <stdio.h>

#if defined(__linux__)
// Linux系统
#include <unistd.h>
#elif defined(_WIN32)
// Windows系统
#include <intrin.h>
#include <windows.h>
#endif

/*单位：毫秒*/
void sleepms(int time)
{
#if defined(__linux__)
    // Linux系统
    usleep(time * 1000);
#elif defined(_WIN32)
    // Windows系统
    Sleep(time);
#endif
}

/* Needs echo 2 > /sys/devices/cpu/rdpmc */
unsigned long long cputimer()
{
    // 以下三种方法，是等价的（只在 x86 上运行，而 x64 不支持内联汇编）

    // 1.
    /*__asm {
        rdtsc;
        shl edx, 32;
        or eax, edx;
    }*/

    // 2.
    //__asm RDTSC;

    // 3.
    /*__asm _emit 0x0F
    __asm _emit 0x31*/

#if _WIN32
    return __rdtsc();
#else
    unsigned int lo, hi;
    __asm__ volatile("rdtsc" : "=a"(lo), "=d"(hi));
    return ((unsigned long long)hi << 32) | lo;
#endif
}
// unsigned long long cputimer();   // 独立汇编代码
/*
    align 16

    _cputimer:
    rdtsc
    shl rdx, 32
    or rax, rdx
    ret
*/

unsigned long long CPUFrequency;

// 测量 CPU 主频
unsigned long long GetFrequency()
{
    unsigned long long t1 = cputimer();
    sleepms(1000);
    unsigned long long t2 = cputimer();
    CPUFrequency = t2 - t1;
    printf("CPU Frequency = %lld\n", CPUFrequency);
    return CPUFrequency;
}

unsigned long long TM_start, TM_end;
#define Timer(code)        \
    TM_start = cputimer(); \
    code;                  \
    TM_end = cputimer();   \
    printf("time = %lld cycles (%f s)\n", TM_end - TM_start, (double)(TM_end - TM_start) / CPUFrequency); // 对code部分计时

unsigned long long TM_mem[10000];
#define Loop(loop, str, code)          \
    for (int i = 0; i < loop; i++)     \
    {                                  \
        TM_start = cputimer();         \
        code;                          \
        TM_end = cputimer();           \
        TM_mem[i] = TM_end - TM_start; \
    }                                  \
    Analyis_TM(loop, str);

void __quick_sort(unsigned long long *arr, int begin, int end) // 快速排序，简化版
{
    if (begin >= end)
        return;

    unsigned long long temp1 = arr[begin], temp2;
    int k = begin;
    for (int i = begin + 1; i <= end; i++)
    {
        if (temp1 > arr[i])
        {
            temp2 = arr[i];
            int j;
            for (j = i - 1; j >= k; j--)
                arr[j + 1] = arr[j];
            arr[j + 1] = temp2;
            k++;
        }
    }
    __quick_sort(arr, begin, k - 1);
    __quick_sort(arr, k + 1, end);
}

void quick_sort(unsigned long long *arr, int size)
{
    __quick_sort(arr, 0, size - 1);
}

void Analyis_TM(int loop, const char *str) // 分析代码性能
{
    unsigned long long min, max, med, aver = 0;
    quick_sort(TM_mem, loop);
    min = TM_mem[0];
    max = TM_mem[loop - 1];
    med = TM_mem[loop >> 1];
    for (int i = 0; i < loop; i++)
    {
        aver += TM_mem[i];
    }
    aver /= loop;
    printf("Running Time of <%s>:\n\tLoop\t%10ld times\n\tMinimum\t%10ld cycles (%10.6f ms)\n\tMaximum\t%10ld cycles (%10.6f ms)\n\tMedian\t%10ld cycles (%10.6f ms)\n\tAverage\t%10ld cycles (%10.6f ms)\n",
           str, loop, min, (double)min / CPUFrequency * 1000, max, (double)max / CPUFrequency * 1000, med, (double)med / CPUFrequency * 1000, aver, (double)aver / CPUFrequency * 1000);
}

#endif // CPUTIMER_H

示例代码：

#include <iostream>
#include <helib/helib.h>
#include "cputimer.h"

#define pn puts("")
#define where printf("%s(%d)-<%s>.\n\n", __FILE__, __LINE__, __FUNCTION__)

using namespace std;
using namespace helib;

int main(int argc, char *argv[])
{
    GetFrequency();

    long k = 80;      // 安全参数
    long nbits = 300; // 密文模数
    long c = 2;       // KS分解列数
    long p = 2;       // 域特征
    long r = 1;       // Hensel Lifting
    long d = 60;      // 槽嵌入度数
    long s = 30;      // 明文槽个数

    long m = helib::FindM(k, nbits, c, p, d, s, 0, 0); // 分圆多项式次数
    printf("m = %ld\n\n", m);

    long skHwt = 128;   // 三元私钥的密度
    long scale = 30;    // 编码因子（BGV 需要么）
    double stdev = 3.2; // 噪声标准差

    helib::Context context = helib::ContextBuilder<helib::BGV>()
                                 .m(m)
                                 .p(p)
                                 .r(r)
                                 .bits(nbits)
                                 .c(c)
                                 .stdev(stdev)
                                 .scale(scale)
                                 .skHwt(skHwt)
                                 .build();

    context.printout();
    pn;

    long nslots = context.getNSlots();

    helib::SecKey secret_key(context);
    cout << "Generate the secret key..." << endl;
    long pr = 2;
    long maxDegKswitch = 10;
    secret_key.GenSecKey(pr, maxDegKswitch); // 生成 sk 以及 maxDegKswitch 对应的 relin-key，利用 GenKeySWmatrix() 生成 s^e(X) -> s(X)
    // secret_key.GenKeySWmatrix(Spow, Xpow, fromKey, toKey)

    cout << "Generating key-switching matrices..." << endl;
    helib::addSome1DMatrices(secret_key); // 生成一部分 KSK，利用 GenKeySWmatrix() 生成形如 s(X^e) -> s(X)

    cout << "Generating the public key..." << endl;
    const helib::PubKey &public_key = secret_key;

    cout << "Get the EncryptedArray of the context..." << endl;
    const helib::EncryptedArray &ea = context.getEA();

    helib::Ptxt<helib::BGV> ptxt(context);
    for (int i = 0; i < 4; i++)
    {
        vector<long> v(d, 0);
        v[i % d] = 1; // 明文槽 = X^i
        ptxt[i] = v;
    }
    cout << "Initial Plaintext: " << ptxt << endl;
    where;

    helib::Ctxt ctxt(public_key), tmp(public_key);
    int loop = 3;
    cout << "Loop = " << loop << endl;
    where;

    Loop(loop, "Enc",
         public_key.Encrypt(ctxt, ptxt););
    printf("bit Capacity = %ld\n", ctxt.bitCapacity());
    where;

    Loop(loop, "Dec",
         secret_key.Decrypt(ptxt, ctxt););
    cout << "Decrypted Result: " << ptxt << endl;
    where;

    tmp = ctxt;
    Loop(loop, "addConstant #1",
         tmp.addConstant(ptxt)); // 未编码的明文向量，较慢
    printf("bit Capacity = %ld\n", tmp.bitCapacity());
    where;

    helib::EncodedPtxt eptxt;
    ptxt.encode(eptxt); // 编码的明文多项式，NTL::ZZX
    helib::FatEncodedPtxt feptxt;
    feptxt.expand(eptxt, context.getCtxtPrimes()); // 编码的明文多项式，helib::DoubleCRT

    Loop(loop, "addConstant #2",
         tmp.addConstant(eptxt)); // 较慢
    printf("bit Capacity = %ld\n", tmp.bitCapacity());
    where;

    Loop(loop, "addConstant #3",
         tmp.addConstant(feptxt)); // 很快
    printf("bit Capacity = %ld\n", tmp.bitCapacity());
    where;

    tmp = ctxt;
    Loop(loop, "addCtxt",
         tmp.addCtxt(ctxt));
    printf("bit Capacity = %ld\n", tmp.bitCapacity());
    where;

    tmp = ctxt;
    Loop(loop, "multByConstant #1",
         tmp.multByConstant(ptxt)); // 较慢
    printf("bit Capacity = %ld\n", tmp.bitCapacity());
    where;

    Loop(loop, "multByConstant #2",
         tmp.multByConstant(eptxt)); // 很快
    printf("bit Capacity = %ld\n", tmp.bitCapacity());
    where;

    Loop(loop, "multByConstant #3",
         tmp.multByConstant(feptxt)); // 很快
    printf("bit Capacity = %ld\n", tmp.bitCapacity());
    where;

    tmp = ctxt;
    Loop(loop, "multiplyBy",
         tmp.multiplyBy(ctxt)); // 张量积之前自动模切换，张量积之后自动重线性化
    printf("bit Capacity = %ld\n", tmp.bitCapacity());
    where;

    tmp = ctxt;
    Loop(loop, "multiplyBy2",
         tmp.multiplyBy2(ctxt, ctxt)); // 高级乘法，依次做 multLowLvl，然后统一 reLinearize
    printf("bit Capacity = %ld\n", tmp.bitCapacity());
    where;

    tmp = ctxt;
    Loop(loop, "multLowLvl",
         tmp.multLowLvl(ctxt)); // 张量积之前自动模切换，做 INTT 获得 NTL:ZZX delta，然后做 NTT 接着 -= 和 /=
    printf("bit Capacity = %ld\n", tmp.bitCapacity());
    where;

    // void Ctxt::tensorProduct(const Ctxt& c1, const Ctxt& c2); //密文向量的张量积，Ctxt 的 private 成员，无法访问（烦人）

    Loop(loop, "reLinearize",
         tmp.reLinearize()); // 执行 s^e(X) -> s(X) 内积运算
    printf("bit Capacity = %ld\n", tmp.bitCapacity());
    where;

    tmp = ctxt;
    Loop(loop, "rotate",
         ea.rotate(tmp, -1)); // 循环旋转，正数是右移，负数是左移
    printf("bit Capacity = %ld\n", tmp.bitCapacity());
    secret_key.Decrypt(ptxt, tmp);
    cout << "Decrypted Result: " << ptxt << endl;
    where;

    tmp = ctxt;
    Loop(loop, "shift",
         ea.shift(tmp, 1)); // 零填充移位，正数是右移，负数是左移
    printf("bit Capacity = %ld\n", tmp.bitCapacity());
    secret_key.Decrypt(ptxt, tmp);
    cout << "Decrypted Result: " << ptxt << endl;
    where;

    return 0;
}

配置 & 编译

下载 VScode 插件 WSL，在工作目录下启动子系统 WSL，执行指令 code .，使得 VScode 远程连接 WSL，从而可以使用 WSL 上的文件夹 \usr\local\include 和 \usr\local\lib。

编写 CMakeLists.txt，

SET(CMAKE_CXX_COMPILER "g++")
set(CMAKE_CXX_STANDARD 17)
set(CMAKE_CXX_STANDARD_REQUIRED ON)

add_compile_options(
    -march=native -O3 -fopenmp -fPIC -pthread
    -lhelib -lntl -lgmp -lgf2x -lssl -lstdc++ -lm 
    -mavx2 -mno-avx256-split-unaligned-load -mno-avx256-split-unaligned-store
    -Wno-unused-command-line-argument -Wwrite-strings -v
)

SET(EXECUTABLE_OUTPUT_PATH ${PROJECT_SOURCE_DIR}/bin)
SET(LIBRARY_OUTPUT_PATH ${PROJECT_SOURCE_DIR}/lib/)

add_executable(BGV_packed_arithmetic BGV_packed_arithmetic.cpp)
target_link_libraries(BGV_packed_arithmetic helib)

find_package(helib)

第一种方法：命令行执行 mkdir build，cd build，cmake ..，make

第二种方法，在 VScode 中执行：

文件 ./.cscode/c_cpp_properties.json（只用于编辑器），在 "includePath" 中配置头文件目录，这在写代码查看函数定义的时候很有用

 {
   "configurations": [
       {
           "name": "Linux",
           "includePath": [
               "${workspaceFolder}/**",
               "/usr/local/include/helib",
               "/usr/local/include/hexl"
           ],
           "defines": [],
           "compilerPath": "/usr/bin/gcc",
           "cStandard": "c17",
           "cppStandard": "c++17",
           "intelliSenseMode": "linux-gcc-x64"
       }
   ],
   "version": 4
}

文件 ./.cscode/tasks.json（用于代码编译），在 "args" 中配置：头文件目录 -I、库文件目录 -L、链接的库 -lhelib -lntl -lgmp -lgf2x -lssl -lstdc++ -lm（注意 gcc 遵循 “从左到右” 编译顺序，依赖其他库的库应当放在前面，被依赖的库必须放在后面，否则依旧会出现 undefined reference to 报错，不过 cmake 似乎会自动重排）

{
    "tasks": [
        {
            "type": "cppbuild",
            "label": "C/C++: gcc 生成活动文件",
            "command": "/usr/bin/gcc",
            "args": [
                "-fdiagnostics-color=always",
                "-g",
                "${file}",
                "-o",
                "${fileDirname}/${fileBasenameNoExtension}",
                "-I/usr/local/include/helib",
                "-I/usr/local/include/hexl",
                "-I/usr/local/include/NTL",
                "-fPIC",
                "-L/usr/local/lib",
                "-lhelib",
                "-lssl",
                "-lntl",
                "-lgmp",
                "-lgf2x",
                "-lstdc++",
                "-lm"
            ],
            "options": {
                "cwd": "${fileDirname}"
            },
            "problemMatcher": [
                "$gcc"
            ],
            "group": {
                "kind": "build",
                "isDefault": true
            },
            "detail": "调试器生成的任务。"
        }
    ],
    "version": "2.0.0"
}

编译执行：

执行 Ctrl + F5（不调试执行），目标 ./build，不产生 gmon.out
执行 F5（调试执行），目标 ./，产生 gmon.out，可生成分析文件 gprof main gmon.out > report.txt

测试结果

CPU Frequency = 2919221615
m = 13571

m = 13571, p = 2, phi(m) = 13200
  ord(p) = 60
  normBnd = 1.62033
  polyNormBnd = 4.36982
  factors = [41 331]
  generator 3 has order (!= Z_m^*) of 220
r = 1
nslots = 220
hwt = 128
ctxtPrimes = [6,7,8,9,10,11,12]
specialPrimes = [13,14,15,16]
number of bits = 498

security level = 84.1162

Generate the secret key...
Generating key-switching matrices...
Generating the public key...
Get the EncryptedArray of the context...
Initial Plaintext: {"HElibVersion":"2.2.0","content":{"scheme":"BGV","slots":[[1],[0,1],[0,0,1],[0,0,0,1],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0]]},"serializationVersion":"0.0.1","type":"Ptxt"}
/mnt/e/Mycode/C++/UseHElib/obj1/use_helib.cpp(70)-<main>.

Loop = 3
/mnt/e/Mycode/C++/UseHElib/obj1/use_helib.cpp(75)-<main>.

Running Time of <Enc>:
        Loop             3 times
        Minimum   54216236 cycles ( 18.572155 ms)
        Maximum   60112622 cycles ( 20.592004 ms)
        Median    58604374 cycles ( 20.075343 ms)
        Average   57644410 cycles ( 19.746500 ms)
bit Capacity = 296
/mnt/e/Mycode/C++/UseHElib/obj1/use_helib.cpp(80)-<main>.

Running Time of <Dec>:
        Loop             3 times
        Minimum   64732097 cycles ( 22.174437 ms)
        Maximum  130025611 cycles ( 44.541192 ms)
        Median    68997595 cycles ( 23.635614 ms)
        Average   87918434 cycles ( 30.117081 ms)
Decrypted Result: {"HElibVersion":"2.2.0","content":{"scheme":"BGV","slots":[[1],[0,1],[0,0,1],[0,0,0,1],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0]]},"serializationVersion":"0.0.1","type":"Ptxt"}
/mnt/e/Mycode/C++/UseHElib/obj1/use_helib.cpp(85)-<main>.

Running Time of <addConstant #1>:
        Loop             3 times
        Minimum   23644220 cycles (  8.099495 ms)
        Maximum   25715956 cycles (  8.809183 ms)
        Median    24451296 cycles (  8.375964 ms)
        Average   24603824 cycles (  8.428214 ms)
bit Capacity = 296
/mnt/e/Mycode/C++/UseHElib/obj1/use_helib.cpp(91)-<main>.

Running Time of <addConstant #2>:
        Loop             3 times
        Minimum   19239144 cycles (  6.590505 ms)
        Maximum   22151209 cycles (  7.588053 ms)
        Median    19842843 cycles (  6.797306 ms)
        Average   20411065 cycles (  6.991955 ms)
bit Capacity = 296
/mnt/e/Mycode/C++/UseHElib/obj1/use_helib.cpp(101)-<main>.

Running Time of <addConstant #3>:
        Loop             3 times
        Minimum     108438 cycles (  0.037146 ms)
        Maximum     216896 cycles (  0.074299 ms)
        Median      125570 cycles (  0.043015 ms)
        Average     150301 cycles (  0.051487 ms)
bit Capacity = 296
/mnt/e/Mycode/C++/UseHElib/obj1/use_helib.cpp(106)-<main>.

Running Time of <addCtxt>:
        Loop             3 times
        Minimum     255610 cycles (  0.087561 ms)
        Maximum     385168 cycles (  0.131942 ms)
        Median      269512 cycles (  0.092323 ms)
        Average     303430 cycles (  0.103942 ms)
bit Capacity = 294
/mnt/e/Mycode/C++/UseHElib/obj1/use_helib.cpp(112)-<main>.

Running Time of <multByConstant #1>:
        Loop             3 times
        Minimum   17839970 cycles (  6.111208 ms)
        Maximum   19142682 cycles (  6.557461 ms)
        Median    18257308 cycles (  6.254170 ms)
        Average   18413320 cycles (  6.307613 ms)
bit Capacity = 271
/mnt/e/Mycode/C++/UseHElib/obj1/use_helib.cpp(118)-<main>.

Running Time of <multByConstant #2>:
        Loop             3 times
        Minimum   15434170 cycles (  5.287084 ms)
        Maximum   18974816 cycles (  6.499957 ms)
        Median    15442322 cycles (  5.289877 ms)
        Average   16617102 cycles (  5.692306 ms)
bit Capacity = 247
/mnt/e/Mycode/C++/UseHElib/obj1/use_helib.cpp(123)-<main>.

Running Time of <multByConstant #3>:
        Loop             3 times
        Minimum     784630 cycles (  0.268781 ms)
        Maximum    1021762 cycles (  0.350012 ms)
        Median      795104 cycles (  0.272368 ms)
        Average     867165 cycles (  0.297054 ms)
bit Capacity = 222
/mnt/e/Mycode/C++/UseHElib/obj1/use_helib.cpp(128)-<main>.

Running Time of <multiplyBy>:
        Loop             3 times
        Minimum  301254500 cycles (103.196859 ms)
        Maximum  432288148 cycles (148.083361 ms)
        Median   370922128 cycles (127.061997 ms)
        Average  368154925 cycles (126.114072 ms)
bit Capacity = 254
/mnt/e/Mycode/C++/UseHElib/obj1/use_helib.cpp(134)-<main>.

Running Time of <multiplyBy2>:
        Loop             3 times
        Minimum  586851584 cycles (201.030159 ms)
        Maximum  837038438 cycles (286.733434 ms)
        Median   714548504 cycles (244.773641 ms)
        Average  712812842 cycles (244.179078 ms)
bit Capacity = 230
/mnt/e/Mycode/C++/UseHElib/obj1/use_helib.cpp(140)-<main>.

Running Time of <multLowLvl>:
        Loop             3 times
        Minimum  159771298 cycles ( 54.730788 ms)
        Maximum  270929658 cycles ( 92.808870 ms)
        Median   222590257 cycles ( 76.249866 ms)
        Average  217763737 cycles ( 74.596507 ms)
bit Capacity = 252
/mnt/e/Mycode/C++/UseHElib/obj1/use_helib.cpp(146)-<main>.

Running Time of <reLinearize>:
        Loop             3 times
        Minimum        228 cycles (  0.000078 ms)
        Maximum  509903313 cycles (174.670984 ms)
        Median         674 cycles (  0.000231 ms)
        Average  169968071 cycles ( 58.223764 ms)
bit Capacity = 252
/mnt/e/Mycode/C++/UseHElib/obj1/use_helib.cpp(153)-<main>.

Running Time of <rotate>:
        Loop             3 times
        Minimum  513130675 cycles (175.776540 ms)
        Maximum  553318857 cycles (189.543286 ms)
        Median   541143294 cycles (185.372461 ms)
        Average  535864275 cycles (183.564095 ms)
bit Capacity = 265
Decrypted Result: {"HElibVersion":"2.2.0","content":{"scheme":"BGV","slots":[[0,0,0,1],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[1],[0,1],[0,0,1]]},"serializationVersion":"0.0.1","type":"Ptxt"}
/mnt/e/Mycode/C++/UseHElib/obj1/use_helib.cpp(161)-<main>.

Running Time of <shift>:
        Loop             3 times
        Minimum  119398553 cycles ( 40.900818 ms)
        Maximum  229372568 cycles ( 78.573195 ms)
        Median   216684818 cycles ( 74.226916 ms)
        Average  188485313 cycles ( 64.566976 ms)
bit Capacity = 272
Decrypted Result: {"HElibVersion":"2.2.0","content":{"scheme":"BGV","slots":[[0],[0],[0],[1],[0,1],[0,0,1],[0,0,0,1],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0]]},"serializationVersion":"0.0.1","type":"Ptxt"}
/mnt/e/Mycode/C++/UseHElib/obj1/use_helib.cpp(169)-<main>.

生成密码参数

不幸的是 helib 本身没有实现用户友好的参数选择程序。查看 [HS15]，我自己写了一个：

#include "GenParams.h"
#include <helib/helib.h>

long CRT_base(vector<long> &base, const vector<long> &m)
{
    int t = m.size();
    long M = helib::computeProd(m);

    for (int i = 0; i < t; i++)
    {
        long Mi = M / m[i];
        long Mi_inv = NTL::InvMod(Mi, m[i]);
        base[i] = Mi * Mi_inv % M;
    }

    return M;
}

long CRT_comb(vector<long> &a, const vector<long> &base, const long M)
{
    int t = base.size();

    long A = 0;
    for (int i = 0; i < t; i++)
    {
        A += base[i] * a[i];
        A %= M;
    }

    return A;
}

long GenParams(vector<long> &mvec, vector<long> &gens, vector<long> &ords, long kappa, long nbits, long ndigits, long p, long degree, long nslots, long lowerbound)
{
    if (lowerbound <= 0)
        lowerbound = helib::FindM(kappa, nbits, ndigits, p, degree, nslots, 0, 0); // 安全强度下界

    long m; // 分圆环次数
    for (m = lowerbound; m < 65535; m++)
    {
        if (gcd(m, p) != 1) // 互素
            continue;

        long d = helib::multOrd(p, m);
        if ((d % degree) != 0 || helib::phi_N(m) < d * nslots) // 明文槽是否包含长度degree的子环，并且要求明文槽个数足够多
            continue;

        vector<long> factors;
        helib::pp_factorize(factors, m); // 素数幂分解

        int tag = -1;
        int t = factors.size();

        for (int i = 0; i < t; i++)
        {
            if (helib::multOrd(p, factors[i]) == d) // 是否存在 mi 满足 ord(p mod m) == ord(p mod mi)
            {
                tag = i;
                break;
            }
        }

        if (tag != -1)
        {
            mvec.clear();
            gens.clear();
            ords.clear();
            mvec.reserve(t);
            gens.resize(t);
            ords.resize(t);

            mvec.push_back(factors[tag]); // d1 = d, d2 = ... = dt = 1
            for (int i = 0; i < t; i++)
                if (i != tag)
                    mvec.push_back(factors[i]);

            vector<long> base(t, 0);
            CRT_base(base, mvec); // CRT-Coeff

            bool err = 0;
            for (int i = 0; i < t; i++)
            {
                vector<long> gi_hat;
                vector<long> ki;

                if (i == 0)
                    helib::findGenerators(gi_hat, ki, mvec[0], p); // 循环群 Z_{m1}^*/(p) 的生成元
                else
                    helib::findGenerators(gi_hat, ki, mvec[i], 1); // 循环群 Z_{mi}^*/(p^{d1...d_{i-1}}) 的生成元，i>1 时 p^d1 = 1 mod m

                if (i == 0 && gi_hat.size() == 0) // p 已经是 Z_{m1}^* 的生成元
                {
                    gi_hat.push_back(1);
                    ki.push_back(1);
                }

                if (gi_hat.size() > 1) // 不是循环群
                {
                    err = 1;
                    break;
                }

                vector<long> v(t, 1);
                v[i] = gi_hat[0];
                gens[i] = CRT_comb(v, base, m); // gi = CRT([...,1,gi_hat,1,...])
                ords[i] = ki[0];
            }
            if (err == 1)
                continue;

            reverse(gens.begin(), gens.end()); // 将生成元 ord(gi mod mi) = ord(gi mod m) 放在前端
            reverse(ords.begin(), ords.end());
            reverse(mvec.begin(), mvec.end());

            while (ords.back() == 1) // 移除无用数据
            {
                gens.pop_back();
                ords.pop_back();
            }

            return m;
        }
    }

    return -1;
}

文章目录

helib::BGV

示例代码

配置 & 编译

测试结果

生成密码参数

相关推荐

最近更新

热门阅读