。

在很多工作中#xff0c;都可以看到中国剩余定理的影子#xff0c;特别是同态加密提升计算效率的优化工作中#xff0c;将paillier与中国剩余定理进行结合#xff0c;能够实现在加密状态下…1.

背景介绍

本篇主要关注中国剩余定理的原理以及在paillier同态加密系统中的应用。

在很多工作中都可以看到中国剩余定理的影子特别是同态加密提升计算效率的优化工作中将paillier与中国剩余定理进行结合能够实现在加密状态下进行高效计算。

Paillier加密系统

【123】描述了paillier加密系统的原理。

这里做简单的描述。

Paillier加密算法是一种同态加密算法支持加法同态运算。

该算法的安全性基于大整数的分解困难问题具体的加密和解密过程涉及模数

2.1

CRT【45】是数论中的一个经典定理用来解决模数互素时同余方程组的求解问题。

它最早起源于中国古代数学家孙子在《孙子算经》中的研究。

解法步骤

此外也关注到【6】对于中国剩余定理的解释比较清晰这里也贴一下以便参考学习。

3.2

中国剩余定理与Paillier加密算法结合可以有效提升计算效率尤其是在大数模运算的场景中。

通过利用中国剩余定理的性质将涉及大整数的计算拆分为两个较小模数空间中的并行计算从而加快整体的运算速度。

这种结合方式在Paillier加密算法中的典型应用是加速解密过程。

具体地中国剩余定理用于将大整数的计算分解为在较小整数模数下的并行计算。

对于给定的两个模数

对于任何整数

是一个非常大的数。

通过中国剩余定理可以将这些大模数运算分解为在较小模数

4.2

的结果得到最终的解密结果。

在原始论文【2】中其实也列出了相应的说明

远小于

这里根据哥大的材料【7】列出paillier系统相关的定理有兴趣可以看下定理的证明过程。

参考材料