HEAAN新版学习

本篇文章对最新版的HEAAN库进行研究，老版的介绍见 HEAAN库学习

主要参考：slide-HEAAN.pdf

HEAAN介绍

HEAAN是一个支持在加密的复数数组之间进行操作的库，方案的安全性取决于\(log_Q\)、\(log^N\)和高斯分布的标准差\(\sigma =3.2\)。如果使用 Martin’s LWE parameter estimator，你可以检测这个方案的安全性。

lwe-estimator，是一个Sage函数【Sage更多：参考】，用于测试求解LWE问题的运行时间

个人理解，求解LWE运行时间越长，越安全，所以推荐用此时的参数？后面单独花时间再研究这个，在这里我就理解成从这里这里选取更好的参数。

下面是难点之一编码，将一个复数向量编码成一整数多项式：

\[encode: (m_1,...,m_l)\in \mathbb{C}^l\Rightarrow \left \lfloor \Delta m(x)\right \rceil\in \mathbb{Z}[X]/(X^N+1)
\]

密文是一对多项式\((a(x),b(x))\in\mathbb{Z}_Q\)，例如：对于私钥是\(s(x)\)，\(\mathbb{Z}=\mathbb{Z}[X]/(X^N+1)\)，\(\mathbb{Z}_Q=\mathbb{R}/Q\mathbb{R}\)

\[b(x)=-a(x)s(x)+\left \lfloor\Delta m(x)\right \rceil+e(x)，其中a(x)\in \mathbb{R}[X]/(X^N+1)
\]

下面是主要函数：

\(encode:\)输入\(\overrightarrow{m}\in \mathbb{C^l}\)，输出一个多项式\(m(x)\)

\(decode:\)输入\(m(x)\)，输出一个复数向量\(\overrightarrow{m}\)

\(encrypt:\)输入\(\overrightarrow{m}\)，编码，加密，返回密文\((a(x),b(x))\)

\(decrypt:\)输入\((a(x),b(x))\)，解密，解码，返回\(\overrightarrow{m}\)

\(add:\)输入两个密文，返回密文\(\overrightarrow{m_1}+\overrightarrow{m_2}\)

\(square:\)输入一个密文，返回密文\(\overrightarrow{m}+\overrightarrow{m}\)

\(mult:\)输入两个密文，返回密文\(\overrightarrow{m_1}*\overrightarrow{m_2}\)

\(rotate:\)输入一个密文，返回旋转后的密文

HEAAN使用

预备知识

首先需要确定缩放因子\(\Delta\)和目标电路深度(乘法次数)\(L\)，这将会确定最大模数\(Q=\Delta^L\)。使用安全参数\(\lambda\)和LWE参数评估器（这里理解为lwe-estimator），我们将会选择密文多项式的维数（次数）\(N\)。

Context context(logN, logQ);

用于编码和解密时计算复数，这个类包含encode和decode函数，这个类在老版本中出现。

ZZX mx = context.encode(mvec,slots,pBits);

返回编码结果\(m(x)\)，即一个整数多项式；这里的pBits是\(log_2^{\Delta}\)。

密钥生成

在HEAAN方案中，我们需要额外的公钥，即用于乘法运算的计算密钥，这是在\(\mathbb{R}_{PQ}^2\)上的一对多项式，这里的\(P\)是一个特殊的模数，和\(Q\)有相同的比特位数，其安全性基于\(RLWE(2log^Q,log^N,\sigma)\)问题

SecretKey sk(logN, h);

生成私钥（一个稀疏多项式）\(s(x)\)，该多项式的系数取自\(HWT(h)=\left\{-1,0,1 \right\}\)分布，即多项式系数中有\(h\)个正整数。

Scheme scheme(sk, context);

生成下面两个公钥：

\[pk_{enc}=(a(x),-a(x)s(x)+e(x))\in \mathbb{Z}_{PQ}^2
\]

\[pk_{mult}=(a(x),-a(x)s(x)+Ps^2(x)+e(x))\in \mathbb{Z}_{PQ}^2
\]

如果需要旋转功能的话，也需要生成一个公钥：

scheme.addConjKey(sk);

scheme.addLeftRotKey(sk,i);

scheme.addRightRotKey(sk.i);

为左旋转和右旋转生成对应的公钥

\[pk_{leftRot,i} =(a(x),-a(x)s(x)+P*s^2(x^k)e(x))\in \mathbb{Z}_{PQ}^2
\]

其中\(k=5^I mod N\)，共轭情况下\(k=2N-1\)，用作右旋转下\(k=5^{-i}\)，该公钥用于索引为i的明文数组的左旋转，如果运行scheme.addLeftRotKeys和scheme.addRightRotKeys将会产生两个方向上旋转的公钥。

一直有一个疑惑，为什么要进行旋转？

因为明文都是向量（实数或复数），用旋转可以提升效率！

什么是旋转？

CKKS中的旋转大多就是进行对于矩阵的旋转，通俗一点讲就是，对于矩阵来说，旋转列可能就是将一列元素进行向左或者是向右进行平移。旋转行可能就是将矩阵的每两行进行对调，从而实现旋转的操作。旋转是不消耗任何的噪音预算的。

同态计算

同态加法有多种版本，注意，我们也可以在明文和密文之间进行加法。

cipher3 = scheme.add(cipher1, cipher2);

scheme.addAndEqual(cipher1, cipher2);

cipher2 = scheme.addConst(cipher1, const);

这些算法相当快。对于常用参数，两个密文之间的相加只需要10毫秒到20毫秒。请注意，addAndEqual 将计算新结果直接赋值给输入的第一个密文，由于内存分配时间的原因，这会稍微快一点。

同态乘法有多种版本，注意，我们也可以在明文和密文之间进行乘法：

cipher2 = scheme.square(cipher1);

cipher2 = scheme.squareAndEqual(cipher1);

cipher3 = scheme.mult(cipher1, cipher2);

scheme.multAndEqual(cipher1, cipher2);

cipher2 = scheme.multByConst(cipher1, const);

那些算法除了multByConst都会使用计算密钥\(pk_{mult}\)，这大约需要100毫秒到1000毫秒，这取决于缩放因子\(\Delta\)和目标电路深度(乘法次数)\(L\)

重缩放

密文（缩放因子为\(\Delta\)）相乘后缩放因子变为\(\Delta^2\)，所以我们需要使用重缩放，其中pBits是\(log_2^{\Delta}\)。

cipher2 = scheme.reScaleBy(cipher1, pBits);

scheme.reScaleByAndEqual(cipher1, pBits);

缩放因子变为\(\Delta\)，密文模数变为\(Q/\Delta\)

同态旋转

cipher2 = scheme.leftRotateBy(cipher1, i);

scheme.leftRotateByAndEqual(cipher1, i);

cipher2 = scheme.rightRotateBy(cipher1, i);

scheme.rightRotateByAndEqual(cipher1, i);

每一次旋转都需要使用对应的旋转公钥，如果没有，将自动 combine power of two shifting【没看太懂，是自动生成么？】

例子

// Key Generation

Context context(logN, logQ);

SecretKey sk(logN);//私钥

Scheme scheme(sk, context);//公钥、计算密钥

scheme.addLeftRotKey(sk, 1);//左旋转密钥

// Encrypt

Ciphertext cipher1 = scheme.encrypt(mvec1, slots, pBits, logQ);

Ciphertext cipher2 = scheme.encrypt(mvec2, slots, pBits, logQ);

// Homomorphic Operations

Ciphertext addCipher = scheme.add(cipher1, cipher2);

Ciphertext multCipher = scheme.mult(cipher1, cipher2);//乘法

scheme.reScaleByAndEqual(multCipher, pBits);//重缩放

Ciphertext rotCipher = scheme.leftRotate(cipher1, 1);//将密文1向左旋转一位

// Decrypt

complex<double>* dvecAdd = scheme.decrypt(sk, addCipher);

complex<double>* dvecMult = scheme.decrypt(sk, multCipher);

complex<double>* dvecRot = scheme.decrypt(sk, rotCipher);

巴特西