BGV/BFV 的统一自举算法

参考���献：

1. [GV23] Geelen R, Vercauteren F. Bootstrapping for BGV and BFV Revisited[J]. Journal of Cryptology, 2023, 36(2): 12.
2. Bit Extraction and Bootstrapping for BGV/BFV

文章目录

• Bootstrapping for BGV and BFV
• • Decryption Function
  • • BGV
    • BFV
    • Bootstrapping Procedure
    • Homomorphic Linear Transformations
    • • One-Dimensional Linear Transformations
      • Slot-to-Coefficient
      • • General Case
        • Power-of-Two Cyclotomics
        • Digit Extraction
        • • Halevi/Shoup Procedure
          • Chen/Han Procedure
          • Bootstrapping for BGV/BFV/CKKS

            [GV23] 给出了 BGV 和 BFV 的统一自举算法，指出两者复杂度是相同的。

            Bootstrapping for BGV and BFV

            Decryption Function

            稍微滥用符号， r r r 表示 hensel lifting 或者 overflow， e e e 表示待自举密文的模数规模或者加密噪声。

            密文模数 q q q，明文模数 p r p^r pr，分圆整数环 R = Z [ X ] / ( Φ m ( X ) ) R=\mathbb Z[X]/(\Phi_m(X)) R=Z[X]/(Φm​(X))

            BGV

            BGV 的密文形如：

            c 0 + c 1 ⋅ s = m + p r e ( m o d q ) c_0+c_1\cdot s = m+p^re \pmod{q} c0​+c1​⋅s=m+pre(modq)

            假设 q ≡ 1 ( m o d p e ) q\equiv1\pmod{p^e} q≡1(modpe)（这比 [HS15] 的要求松一些），解密可以简化为：

            1. 缩放 c i ′ ← [ p e − r c i ] q c_i' \gets [p^{e-r}c_i]_q ci′​←[pe−rci​]q​
            2. 内积 w ← [ c 0 ′ + c 1 ′ ⋅ s ] p e w \gets [c_0' + c_1' \cdot s]_{p^e} w←[c0′​+c1′​⋅s]pe​
            3. 纠错 m ← [ ⌊ w / p e − r ⌉ ] p r m \gets [\lfloor w/p^{e-r}\rceil]_{p^r} m←[⌊w/pe−r⌉]pr​

            现在我们确定参数 e e e 的合适数值，过大则自举效率很慢，过小则自举结果错误。我们计算

            u = p e − r ( c 0 + c 1 ⋅ s ) = p e − r ( m + p r e ) + q r u = p^{e-r}(c_0+c_1\cdot s) = p^{e-r}(m+p^re) + qr u=pe−r(c0​+c1​⋅s)=pe−r(m+pre)+qr

            根据 q ≡ 1 ( m o d p e ) q\equiv1\pmod{p^e} q≡1(modpe)，那么有

            w = [ u ] p e = [ p e − r m + r ] p e w = [u]_{p^e} = [p^{e-r}m + r]_{p^e} w=[u]pe​=[pe−rm+r]pe​

            这个解密噪声是 MSD 编码的（原始 BGV 的是 LSD 编码）。为了纠错的正确性，需要满足 ∥ r ∥ ∞ ≤ p e − r / 2 \|r\|_\infty \le p^{e-r}/2 ∥r∥∞​≤pe−r/2，用它的上界来约束，

            ∥ r ∥ ∞ ≤ ∥ ( c 0 ′ + c 1 ′ s ) / q ∥ ∞ + ∥ p e − r m / q ∥ ∞ + ∥ p e e / q ∥ ∞ \|r\|_\infty \le \|(c_0'+c_1's)/q\|_\infty + \|p^{e-r}m/q\|_\infty + \|p^ee/q\|_\infty ∥r∥∞​≤∥(c0′​+c1′​s)/q∥∞​+∥pe−rm/q∥∞​+∥pee/q∥∞​

            简记 d i = c i ′ / q d_i=c_i'/q di​=ci′​/q，那么近似要求

            ∥ d 0 + d 1 s ∥ ∞ + ∥ p e e / q ∥ ∞