FHE输出的最短密文大小是多少？

Question

假设在全同态加密(FHE)中，我们使用分批和模数切换技术来减小密文的大小。

问:最有效的完全同态加密的最短密文位大小输出是什么？

备注:我知道有不同的FHE计划。我想看看什么是最短的密文，我们可以得到(即使使用上述技术)从一个有效的FHE输出最短的密文。

Answer 1

这取决于您是要加密一个位，还是要加密多个位。

如果您想加密一个位，我想(免责声明:我可能遗漏了其他方案)，最短的密文是由基于TLWE的本论文实现的(也请参阅它所基于的本论文 )。根据他们的说法，密文扩展是“只有”10000位(即加密一位需要10000位)。这是因为它们可以简单地处理类似LWE的密文，然后在需要时将它们转换为GSW密文(它支持完全同态操作)。

但是，如果您想加密多个比特，那么任何FHE方案都可以使用标准的混合加密来实现1+o(1)的最佳速率：n比特明文m_1, \cdots, m_n的加密是(\mathsf{FHE}(K), \mathsf{SymEnc}_K(m_1, \cdots m_n))，其中\mathsf{SymEnc}_K是一个具有秘密密钥K的密钥加密方案。要在此密文上计算同态函数，只需首先将以下电路C应用于\mathsf{FHE}(K)：C在其描述中有E = \mathsf{SymEnc}_K(m_1, \cdots m_n)硬编码，并在输入K上输出\mathsf{SymDec}_K(E)。因此，这个步骤为您提供了\mathsf{FHE}(C(K)) = \mathsf{FHE}(\mathsf{SymDec}_K(E)) = \mathsf{FHE}(m_1, \cdots m_n)，然后您可以从中评估您选择的任何函数。然后，密文大小为n + O(\lambda)，其中\lambda是一个安全参数，假设\mathsf{SymEnc}_K有速率1+o(1) (对于每种现代对称加密方案，例如AES)都是如此。