We show how to improve the efficiency of the computation of fast Fourier transforms over F_p where p is a word-sized prime. Our main technique is optimisation of the basic arithmetic, in effect decreasing the total number of reductions modulo p, by making use of a redundant representation for integers modulo p. We give performance results showing a significant improvement over Shoup's NTL library.

Pre-2012: Various LWE & RLWE encryption (KEM) schemes with large ciphertext size. Framework of DH-like key exchange construction appeared. No concrete error reconciliation mechanism 2012: Ding et al. invented the first complete LWE & RLWE-based Diffie-Hellman-like key exchange protocols (DING12) 2014: Peikert tweaked DING12 reconciliation slightly 2015: Bos et al. implemented PKT14 (BCNS) 2016: Alkim et al. improved BCNS (NewHope)

6.1 RLWE问题的参数选择 RLWE问题所涉及的参数有：环 R的多项式次 数 n，模值 q，离散高斯分布 ,D  。所以 RLWE的 安全性主要是由 ( , , )n q  决定。 方案中使用的分布c为 , nD  ，即各个分量按照 ,D  进行抽样。 离散高斯分布 ,D  的概率密度函 数为 2 2exp( )x  ，根据文献 [18]引理 1.5： , Pr ( / 2)x D x k erf k        。当 9.2k  ，可使 得 64( / 2) 2erf k  ，可见离散高斯分布 ,D  是一个 有界分布，可以设置界 9.2B  。 定义 9 埃尔米特因子 m 。对于一个m维格 的一个格基 B ，有这样一个参数 m 使得 1 1 det( ) m mb   ，其中 1b 是格基 B中最短的向量，  也被称为埃尔米特根因子。 Gamma,Nguyen[19]得出：给定  ，约化出具有 埃尔米特因子 m 的格基所需要的时间主要取决 于 。 对于文献[17]给出的区分攻击，为了使得其区 分优势为，需要找到一个长度为 q  的格向量， 其中 ln(1 ) π  。Lindner,Peikert[17]使用了一个 优化的攻击策略（一种格基约化方法），得到了具有 埃尔米特因子 m 的格基，该策略所能计算出最短向 量的长度为 2 log log2 n q  ，并给出了关于该攻击策略所 需时间的一个粗略估计公式 log 1.8 log 110T   。 如果  为安全参数，即要求方案的安全级别为 2T  ，则有 log 1.8 ( 110)   ，设置 128  ， 得到 1.0052  。 由上可知，给定一个埃尔米特根因子 ，使用 Lindner,Peikert 所给优化的攻击策略，计算出一个 长度为 2 log log2 n q  的格向量，所花费的时间大约为 1.8 log 1102   ，如果 2 log log2 n qq    ，则在区分攻击 中，取得的区分优势将小于 2πe  。 根据 2 log log2 n qq    对本文所提方案的参数 进行选择，例如设置区分优势为 642  ,攻击时间 为 1282T  ，则 1.0052  , 3.758  。代入不等式 得到1.910 log log 0.173 logq n q  ≤ 。那么固定 次数 n ，就可以确定一系列 ( , )q  的值。如 1 024, log 38, 55.062n q      ； 2048, logn q   64, 9.69  。 6.2 全同态加密方案的参数选择 第 4节所提出的非自举全同态加密方案，需要 提前给一个电路深度 L，然后才能生成一个同态计 算能力为 L的加密方案。在此方案中除了需要设置 参数 ( , )n  ，还需要设置 1L  个模值 0 1( , , , )Lq q q 。 下面将给出 0 1( , , , )Lq q q 的参数选取。 令第 i层电路的密文噪声大小为 iE 。由方案的 加 密 算 法 可 知 ， 新 鲜 密 文 的 初 始 噪 声 为 2 0 4 2 1E nB B ≤ 。同态加和同态乘导致的噪声变 化如下。 同态加 1 1 (2 2 log ) 1i i i i iE q q E nB q n s     ≤ 同态乘 2 1 1 ( 4 log ) 1i i i i iE q q n E nB q n s      ≤ 由于同态乘的噪声增长比同态加大很多，所以 主要考虑方案能够同态计算的乘法深度。模转换技 术可以 1i iq q 的因子降低密文的噪声，假设通过 4.1 节的方案 FHE，可以把电路每一层的噪声控制在 0E 以内，而只是每一层的模值 iq 在不断地减小。 令 Reline, 1( )4 logi i i iq q nB q  ， Scale, 1i n s   ，如果有以下 2个条件成立。 1) 0 Reline, Scale,2( + )i iE  ≥ 。 2) 1 02i iq q nE ≥ 。 那么有 2 1 0 Reline, Scale, 0( )i i i iq q nE E     ≤ 对此进行粗略地估计：假设模值以 01 2nE 的比 率降低，经过 L 次同态操作之后，模值变为 0 0(2 ) L Lq q nE 。为了保证解密的正确性，必须满 足 0 0 0( (2 ) ) 2 L E q nE≤ 。那么 0q 的比特长度为 0 0log ( 1) log(2 ) logq L nE n ≥ ，进一步得到 iq 的 比特长度为： 0log ( 1 ) log(2 ) logiq L i nE n  ≥ 。 由 2 log log2 n qq    得到 (log logq  log 2)∕ 4 logn q log ，可以看出 q的减小将使得 log 减 小。又因为 log 1.8 log 110T   ，则攻击所花费的 时间将会增加。所以只需要保证最大模值 RLWE的 安全性，亦保证了其他模值的 RLWE安全性。 7 结束语 Brakerski, Gentry 在文献[12]中提出了不需要 自举的全同态加密方案构造方法。他们的方案中的 “密钥转换技术”使用了较复杂的矩阵运算。本文 所提出的方案，通过在重线性化中引入密钥转换，