为同态加密选择模数

为同态加密选择模数

近乎完美的数据安全梦想即将实现，而其核心是基于格的密码学的使用。这将带来新的公钥加密方法，并且这些方法具有量子鲁棒性。例如，Kyber（用于密钥交换和公钥加密）和 Dilithium（用于数字签名）。但是，基于格的密码学的兴起将为同态加密（HE）带来巨大的机会。有了它，我们可以处理加密的值，例如：

Enc(a) * Enc(b) = Enc(a*b)

目前提出的三种主要方法是 BFV [1,2]、BGV [3] 和 CKKS [4]。使用 BFV 和 BGV，我们可以对整数值执行同态加密。在 OpenFHE 中，我们有一个 cryptocontext，它定义了我们使用的环的大小。总的来说，我们有一个明文模数，它将定义在明文中处理的位数。如果我们处理密文文本，并且使用的位数超过了设置的位数，我们将溢出结果。

为此，我们需要查看两个核心参数：

• 明文模数 (p): 这定义了系数的素数。
• 多项式模数 (m): 这定义了不可约多项式 x^m+1 的度数。例如，如果 m 是 5，我们有一个不可约多项式 x⁵+1。

如果我们的 m 为 5，则多项式将具有以下形式：

x⁴+x³+x²+x+1

其中 x⁴ 将是多项式的最高次数。对于 p，我们将定义多项式因子的系数的最大值。例如，如果我们有 p=11，那么：

61x³+12x (mod 11)

等于：

6x³+x

选择模数

在下面的程序中，我使用 OpenFHE 通过公钥对两个值进行同态加密，然后对它们进行同态相加，然后使用私钥解密以生成结果 [ here]：

##include <openfhe.h>
##include <iostream>
##include <vector>
##include <algorithm>
using namespace std;

using namespace lbcrypto;

##include <sstream>

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

  uint64_t mod=1656225793;

    CCParams<CryptoContextBFVRNS> parameters;

    parameters.SetPlaintextModulus(mod);
    parameters.SetMultiplicativeDepth(1);
    parameters.SetSecurityLevel(HEStd_128_classic);
   parameters.SetRingDim(16384/2);

    CryptoContext<DCRTPoly> cryptoContext = GenCryptoContext(parameters);
    cryptoContext->Enable(PKE);
    cryptoContext->Enable(LEVELEDSHE);

    KeyPair<DCRTPoly> keyPair;

    keyPair = cryptoContext->KeyGen();

    uint32_t x=5;
    uint32_t y=31;

    std::vector<int64_t>xval = {1};
 xval[0]=x;
    Plaintext xplaintext               = cryptoContext->MakePackedPlaintext(xval);

    std::vector<int64_t> yval = {1};
 yval[0]=y;
    Plaintext yplaintext               = cryptoContext->MakePackedPlaintext(yval);

    // Encrypt values
    auto ciphertext1 = cryptoContext->Encrypt(keyPair.publicKey, xplaintext);
    auto ciphertext2 = cryptoContext->Encrypt(keyPair.publicKey, yplaintext);

    // Add ciphertext
    auto ciphertextMult     = cryptoContext->EvalAdd(ciphertext1, ciphertext2);

    // Decrypt result
    Plaintext plaintextAddRes;
    cryptoContext->Decrypt(keyPair.secretKey, ciphertextMult, &plaintextAddRes);

    std::cout << "Modulus: : " << mod<< std::endl;

    std::cout << "\nx: " << xplaintext << std::endl;
    std::cout << "y: " << yplaintext << std::endl;

    // Output results
    std::cout << "\nResults" << std::endl;
    std::cout << "x+y= " << plaintextAddRes << std::endl;

    return 0;
}

一个示例运行给出：

Modulus: : 1656225793

x: ( 5 ... )
y: ( 31 ... )

Results
x+y= ( 36 ... )

在这种情况下，我们使用模数值 1,656,225,793，但是我们可以使用任何素数吗？好吧，答案是否定的。让我们尝试一个 32 位模数 2,122,221,719。当我们现在运行时，我们得到一个异常：

tnat::NativeIntegerT<long long unsigned int> >(): Please provide a
primeModulus(q) and a cyclotomic number(m) satisfying the condition:
(q-1)/m is an integer. The values of primeModulus = 2122221719 and m = 16384
do not satisfy this condition

我们可以看到该值不起作用，我们需要一个 32 位素数，其中：

Mod((q-1),16384) == 0

如果我们尝试 1,656,225,793，我们会得到：

>>> (1656225793-1)%16384
0

而 2,122,221,719：

>>> (2122221719-1)%16384
2198

那么，我们如何找到有效的素数呢？好吧，让我们用 Golang 搜索：

package main

import (
 "crypto/rand"
 "fmt"
 "math"
 "math/big"
 "os"
 "strconv"

)

func main() {

 bits := 32

 argCount := len(os.Args[1:])

 if argCount > 0 {
  bits, _ = strconv.Atoi(os.Args[1])
 }

 if bits < 3 {
  fmt.Printf("We need at least three bits")
 }

 var p *big.Int
 checks := int(math.Max(float64(bits)/16, 8))
 for {

  p, _ = rand.Prime(rand.Reader, int(bits)-1)

  if p.ProbablyPrime(checks)  {
   flag:=new(big.Int).Sub(p,big.NewInt(1))
   res:=new(big.Int).Mod(flag,big.NewInt(16384))

   if (res.Cmp(big.NewInt(0)) == 0) {
    fmt.Printf("%s\n", p)

   }
  }
 }

}

如果我们尝试 32 位的值，我们会得到：

1690730497
1760051201
1655996417
1672314881
2037497857
1861681153
2125643777
2010382337
2138816513
1779957761
1967620097
1799012353
1874870273
1657602049
1805418497
1886846977
1652948993
1765982209
1627340801
1818099713
2010529793
1894023169
...

而且，这就是你找出明文模数的方法。

• 原文链接： medium.com/asecuritysite...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～