基于同质连续带误差学习（hCLWE）的公钥加密技术解析

### 基于同质连续带误差学习（hCLWE）的公钥加密技术解析 在当今信息安全领域，公钥加密技术是保障数据传输安全的重要手段。而基于同质连续带误差学习（hCLWE）的公钥加密方案，为我们提供了新的思路和方法。本文将详细介绍hCLWE相关概念、四种公钥加密方案以及其与统计零知识（SZK）的关系。 #### 1. hCLWE相关背景与问题定义 学习高斯混合分布问题在不同假设下有不同的复杂度。在有足够样本时，已知一些算法，但一般情况下，统计查询算法解决该学习问题是困难的。Bruna等人证明了在格中短向量和短基问题（GapSVP和GapSIVP问题）困难的假设下，区分高斯混合样本和标准正态样本是困难的。Gupte等人进一步表明这种困难性可以基于带误差学习（LWE）问题。 hCLWE分布是一种特殊的高斯混合分布。在Rn空间中，hCLWE样本在垂直于秘密方向w的每个方向上具有标准正态分布，而在w方向上是有噪声的离散高斯分布，可看作“高斯煎饼”的混合，标准差约为β/γ，间距约为1/γ。hCLWE决策问题就是区分hCLWE样本和纯正态样本。 #### 2. 研究贡献 - **构建公钥加密方案**：构建了至少与hCLWE一样难破解的公钥加密方案。hCLWE不仅继承了LWE的优点，如可归约到最坏情况复杂度和抵抗已知量子攻击，而且可能更安全。 - **提出四种公钥加密方案**：这四种方案在解密误差和安全误差之间提供了不同的权衡，并在离散化连续值时使用了不同的技术。 - **“Pancake”方案**：基于hCLWE问题，有逆多项式解密误差和常数安全误差。该方案可证明hCLWE能在统计零知识（SZK）中解决，因此属于coAM类。 - **“Bimodal”方案**：基于(0, 1/2)-hCLWE问题，通过发布(0, 1/2)-hCLWE样本作为公钥，实现了完美的解密误差。 - **“Discretized”方案**：利用Ajtai和Dwork的平行六面体技术，将样本映射到由hCLWE样本张成的平行六面体中，实现了可忽略的安全误差。 - **“Baguette”方案**：基于hCLWE(ℓ)问题，通过修改第一个方案，实现了可忽略的解密误差。 四种方案的具体比较如下表所示： | 方案 | 假设 | 解密误差 | 安全误差 | 公钥大小 | 私钥大小 | | --- | --- | --- | --- | --- | --- | | Pancake | hCLWE | O(1/n) | 1/4 | ˜O(n3) | n | | Bimodal | (0, 1/2)-hCLWE | 0 | 1/2 | ˜O(n3) | n | | Discretized | (0, 1/2)-hCLWE | 0 | 2−n+2 | ˜O(n2) | n | | Baguette | hCLWE(ℓ) | O(1/nℓ) | 1/4 | ˜O(n3) | nℓ | #### 3. 相关工作 Bruna等人展示了从离散高斯采样（DGS）到hCLWE的最坏情况到平均情况的归约，该归约通过一个中间问题——连续LWE（CLWE）进行。CLWE样本形式为(a, z)，其中a是Rn中的向量，其每个元素独立地从标准正态分布N(0, 1)中采样，z := γ⟨a, w⟩ + e mod 1，e是从均值为0、方差为β2的高斯分布中抽取的噪声。CLWE问题是区分多个CLWE样本和相同数量的形式为(a, u)的样本，其中u在[0, 1)上均匀分布且与a独立。hCLWE样本是z = 0条件下的CLWE样本。 Gupte等人最近展示了从LWE到CLWE的归约，表明LWE与CLWE的一个变体在硬度上等价，且CLWE至少和这个变体一样难。 #### 4. CLWE、SZK和统计 - 计算差距 在统计推断中，假设检验任务往往存在统计 - 计算差距，即在一定的样本复杂度范围内，假设检验是可行的，但没有已知的高效算法。hCLWE问题的一个显著特点是，即使样本复杂度无界，它也可能是难解的。当样本数量m ≥ ˜O(n2)时，hCLWE可以在SZK中解决。因此，在SZK = BPP的世界中，hCLWE的计算阈值mcomp最多为˜O(n2)。而CLWE的统计阈值为mstat = O(n)。是否存在hCLWE的统计 - 计算差距是一个有趣的开放问题。 通过Bruna等人从CLWE到hCLWE的归约，我们的结果也意味着CLWE属于SZK。但由于该归约不保留样本复杂度，因此用于CLWE的SZK算法需要更多的样本。 #### 5. 技术概述 我们的加密方案中的消息是单比特。零和一的加密分布在有秘密密钥时可以有效区分，但在没有密钥时则不能。公钥是hCLWE或(0, 1/2)-hCLWE分布的独立样本，私钥是相应“是”实例的隐藏方向w。 hCLWE样本在秘密方向w上具有周期性离散结构。加密设计旨在使密文保留这种离散结构，即使发送者不知道它。解密则计算秘密密钥w和密文之间的相关性，对于零的加密，该相关性接近周期的整数倍，而对于一的加密，通常远离该整数倍。 #### 6. 四种加密方案详细介绍 - **“Pancake”加密方案** - **密钥生成**：秘密密钥是随机单位向量w，公钥是n × m矩阵A，由m个基于秘密方向w的hCLWE样本组成。 - **加密过程**：加密0时，采样均匀向量t ← {1/√m, -1/√m}m并计算At；加密1时，采样标准正态向量。密文c是通过一个将实数线划分为等高斯测度区间（“桶”）的舍入