基于概率的加密

提出一种基于概率的数据加密模型。这个模型，在适当的复杂性假设下，可以证明在一般情况下拥有多项式计算资源的敌手难于从密文得到关于明文的任何信息。这个证明对于任何可能的消息空间成立。这个模型的第一个实现被提出，这个实现的安全性基于合数因子分解未知情况下的二次剩余判定。

本文提出了一种加密方案，该方案具有以下性质:在给定密文的情况下，任何对明文有效的计算都可以在没有密文的情况下有效地计算。

“impossible” 意味着计算不可行

动机

Deterministic Encryption: The Trapdoor Function Model ，确定性加密中的陷门函数模型，知道陷门信息则容易从E(m)得到m。指出这种方法的两个缺陷：

1。当x是某些特殊形式时，f是陷门函数并不排除从f(x)计算x的可能性

2。f是陷门函数并不排除“从f(x)计算x的部分信息(甚至是x的部分bit)是容易的” 的可能性

虽然没有人知道如何破解RSA或拉宾方案，但在这些方案中，没有一个被证明在没有对消息空间做任何假设的情况下解码是困难的。

在本文中，我们从确定性框架转换到概率框架。这使我们能够处理由陷门函数模型引起的问题，而不会对我们想要发送的消息施加任何概率结构。

算法

公钥加密和签名方案 - 凯在想peach - 博客园 (cnblogs.com) Goldwasser–Micali cryptosystem

安全模型

We replace the notion of a trapdoor function with the notion of an unapproximable trapdoor predicate.

unapproximable trapdoor predicate (UTP)

我们用不可逼近的陷门谓词的概念来代替陷门函数的概念。简单地说，谓词B是不可逼近陷门，如果任何人都可以选择一个x使B(x) = 0或y使B(y) = 1，但只有那些知道陷门信息的人，在给定z的情况下，才能计算B(z)的值。当陷门信息未知时，多项式敌手不能比随机猜测更好地判定B(z)的值。

我们用单比特的概率加密代替确定性块加密，其中有许多不同的“1”编码和许多不同的“0”编码。为了加密每条信息，我们使用了一枚均匀的硬币。因此，每个消息的编码将取决于消息加上抛硬币序列的结果。

更具体地说，二进制消息将按如下方式逐位加密:“0”通过随机选择x进行编码，使B(x) = 0;“1”通过随机选择x进行编码，使B(x) = 1。因此，每个消息都有许多可能的编码。然而，消息总是唯一可解码的。新模型的两个特性是:

1。对于知道陷门信息的合法接收者，解密是容易的，对于敌手是可证困难的

2。没有关于加密消息的信息可以被敌手获取。

参考资料：Probabilistic Encryption