用Python代码可视化CKKS同态加密的旋转操作：以N=8为例

第一次接触同态加密的旋转操作时，那些抽象的数学符号和概念往往让人望而生畏。作为CKKS方案中最具特色的操作之一，旋转(rotation)允许我们在加密状态下对向量元素进行循环移位，这在隐私保护的数据分析中有着广泛应用。但为什么需要旋转？它背后的数学原理如何转化为可执行的代码？让我们暂时抛开复杂的公式推导，通过一个具体的Python示例来建立直观理解。

1. 环境准备与基础概念

在开始编码之前，我们需要明确几个核心概念。CKKS方案中的旋转操作本质上是对加密向量进行循环移位，类似于Python列表的 rotate() 操作，但关键区别在于所有操作都在加密状态下完成。选择N=8作为示例是因为它足够小以便于可视化，又足够大能展示典型行为。

首先安装必要的Python库：

pip install numpy sympy matplotlib

这些库将帮助我们进行多项式运算和可视化。特别地， sympy 将用于处理多项式代数，而 numpy 提供高效的向量运算支持。

旋转操作的核心数学基础是分圆多项式。对于N=8，分圆多项式为：

X^8 + 1

其根在复数单位圆上均匀分布，具体位置由ω = e^(-2πi/16)的奇数次幂决定。这些根将作为我们编码的"锚点"。

2. 向量编码：从数据到多项式

让我们从一个简单的复数向量开始：

original_vector = [1+2j, 3+4j, 5+6j, 7+8j]  # 长度为N/2=4

在CKKS中，我们需要将这个向量编码为一个实系数多项式。这个过程可以理解为在特定点上进行多项式插值：

import numpy as np
from sympy import symbols, interpolate

X = symbols('X')
points = [(ω**1, original_vector[0]), 
          (ω**3, original_vector[1]),
          (ω**5, original_vector[2]),
          (ω**7, original_vector[3])]

poly = interpolate(points, X)

然而，这种直接插值得到的多项式系数可能是复数。为了确保实系数，我们需要采用共轭约束：

conjugate_points = [(ω**15, np.conj(original_vector[0])),
                    (ω**13, np.conj(original_vector[1])),
                    (ω**11, np.conj(original_vector[2])),
                    (ω**9, np.conj(original_vector[3]))]

all_points = points + conjugate_points
real_poly = interpolate(all_points, X)

注意：实际CKKS实现使用更高效的FFT方法进行编码，这里为了教学目的展示基本原理

3. 旋转操作的数学本质

旋转操作的神奇之处在于，它可以通过简单的代数变换实现。考虑将多项式变量X替换为X^k：

def apply_rotation(poly, k):
    X = poly.free_symbols.pop()
    return poly.subs(X, X**k)

当k=5时（对于N=8的情况），这相当于对原始向量进行一位循环左移。让我们看看具体过程：

rotated_poly = apply_rotation(real_poly, 5)

# 验证旋转效果
rotated_vector = [
    rotated_poly.evalf(subs={X: ω**1}),
    rotated_poly.evalf(subs={X: ω**3}),
    rotated_poly.evalf(subs={X: ω**5}),
    rotated_poly.evalf(subs={X: ω**7})
]

理论上， rotated_vector 应该是 [3+4j, 5+6j, 7+8j, 1+2j] ，即原始向量左移一位的结果。

4. 完整示例与可视化

让我们将上述步骤整合成一个完整的可执行示例，并添加可视化：

import matplotlib.pyplot as plt

def plot_roots_and_values(roots, values, title):
    plt.figure(figsize=(10, 5))
    
    # 绘制单位圆
    circle = plt.Circle((0, 0), 1, fill=False, color='gray', linestyle='--')
    plt.gca().add_patch(circle)
    
    # 绘制根的位置
    root_angles = [np.angle(r) for r in roots]
    plt.polar(root_angles, np.ones_like(roots), 'ro', label='Roots')
    
    # 绘制向量值
    value_angles = root_angles[:len(values)]
    magnitudes = [abs(v) for v in values]
    plt.polar(value_angles, magnitudes, 'bs-', label='Vector Values')
    
    plt.title(title)
    plt.legend()
    plt.show()

# 计算ω和根
omega = np.exp(-2j * np.pi / 16)
roots = [omega**k for k in range(1, 16, 2)]  # ω^1, ω^3,..., ω^15

# 初始向量和旋转后向量
plot_roots_and_values(roots[:4], original_vector, "Original Vector")
plot_roots_and_values(roots[:4], rotated_vector, "Rotated Vector")

通过可视化，我们可以清晰地看到向量元素在单位圆上的位置变化，直观理解旋转操作的效果。

5. 旋转密钥与加密操作

在实际的CKKS实现中，旋转操作需要特殊的"旋转密钥"。这是因为在加密状态下，我们不能直接操作密文多项式。旋转密钥本质上允许我们将 s(X^k) 转换为 s(X) 的形式：

# 伪代码展示旋转密钥的作用
def encrypted_rotation(ciphertext, rotation_key, k):
    # ciphertext = (c0(X), c1(X))
    rotated_c0 = ciphertext[0](X^k)
    rotated_c1 = ciphertext[1](X^k)
    
    # 使用旋转密钥调整s(X^k)到s(X)
    adjusted_ciphertext = apply_rotation_key(rotated_c0, rotated_c1, rotation_key)
    return adjusted_ciphertext

在SEAL等实际库中，通常会预先生成不同步数的旋转密钥以提高效率。例如，可能生成k=1,2,4,...的密钥，然后通过组合实现任意步数的旋转。

6. 性能优化与实际考虑

当实现真正的CKKS旋转时，有几个关键优化点：

1. 批量旋转 ：同时执行多个旋转操作可以减少通信开销
2. 密钥管理 ：根据应用场景预生成最常用的旋转步数密钥
3. 近似计算 ：CKKS本身是近似方案，旋转可能引入额外误差需要考虑

# 性能优化示例：批量旋转
def batch_rotate(ciphertext, rotation_keys, steps):
    results = []
    for step in steps:
        k = 5**step % (2*N)  # 计算对应的k值
        rotated = encrypted_rotation(ciphertext, rotation_keys[step], k)
        results.append(rotated)
    return results

7. 应用场景与扩展思考

旋转操作在隐私保护计算中有着广泛应用：

• 隐私保护的数据库操作 ：实现加密数据的排序和重组
• 机器学习模型 ：在加密状态下重新排列神经网络权重
• 统计分析 ：对加密数据进行滑动窗口计算

尝试修改N值（如N=16）并观察旋转行为的变化，或者实现右旋转操作（相当于使用不同的k值）。这些实践能加深对CKKS方案灵活性的理解。