英语原文共 11 页，剩余内容已隐藏，支付完成后下载完整资料

---

论离散对数的严谨性

1. W. Schrift 和 A. Shamir著

舒浩浩译

摘要

本文主要研究的是单向方程 ，其中N表示的是一个Blum整数。我们证明了在常用假设下分解Blum整数非常棘手，几乎它的每一位都是单独的硬盘位，有一半是同时的硬盘位。因此， 可以被用于高效伪随机比特发生器和多比特承诺方案，其中信息可以根据任意概率分布得出。

1. 简介

函数是单向的如果它很容易计算但很难反过来得出。单向函数在公共密钥加密、伪随机位的产生、承诺方案等方面有众多应用。有几个具有明确结构的单向函数已经在有理数假设下被提出了，幂函数就是其中一个，其中P是一个素数，g是中的一个元素，它的逆问题是一个还没有发现有效解决算法的离散对数问题。另一个很棘手的问题是将一个整数分解成两个大素数相乘的问题，其中基于分解复杂度的单向函数有RSA / Rabin函数、二次剩余问题及其衍生问题。

单向函数的一个有趣特性是在一个不能由任何有着1/2 1/poly成功概率的多项式环计算出来的问题中的硬盘位的存在性。这一概念在1980年代早期被广泛研究，最终证明了在数论函数中一些具体的数位（通常是n位数问题中最重要的或最不重要的O（log n）位数）是单独的硬盘位，并且这些O（log n）位数也是同时的，所有后来为证明这些数论函数在O（n）的独立安全性或同时安全性方面所作出的努力都失败了。

Goldreich和Levin[GL]已经证明，每一个单向函数具有至少一个对数数硬盘位。延伸其结果可证明，更多位是硬盘位而不强加任何假设的单向函数的推测是不可能的，因为一个函数可能是单向的，仍然仅仅依赖在其位的一小部分。单向函数确切的贡献在于其中所有位是安全确实存在，但他们依靠的硬盘位是由许多单向函数组成的（而不是仅依赖一个自然函数的应用，例如单独应用 在[GM] ， [BG]里面的概率加密函数）。

除了它的理论意义外，证明一个单向函数有许多同时的硬盘位可以提高许多加密方案的效率。最近Impagliazzo和NAOR（[IN]）在对应的组合的单向函数与子集和问题中引进了一个高效的伪随机位发生器基。他们的论文成果使得来自每个函数的随机输入都可能有O（n）位的伪随机输出位，，但并不一定意味着该函数的输入位是单独或同时的硬盘位，这使得构造一个有着O（n）个安全位的自然函数问题明朗起来。

在这篇论文里，我们主要研究的是单向方程 ，其中N表示的是一个Blum整数。我们证明了在常用假设下分解Blum整数非常棘手，几乎它的每一位都是单独的硬盘位，有一半是同时的硬盘位。因此， 可以被用于高效伪随机比特发生器和多比特承诺方案，其中信息可以根据任意概率分布得出。我们还引用了Johan Hastad [Ha]最近的改进成果，他扩展了我们的技术，以证明确实的所有位都是硬盘位，以及半数以上的位也是同时的硬盘位。

本文结构如下：第2节给出使用的各种定义和假设， 第3节我们解决的独立硬盘位的安全性，第4节解决同时位的安全性，第5节我们提出一些我们增强的安全位的应用，并在第6节中讨论几个我们的扩展工作。

1. 预备知识

假设，其中P、Q是不同的奇素数，n是N的二进制数，表示的是所有与素数N互素的数组成的乘法群，表示的是中使得的阶数最小的元素。我们在上定义，显然：

我们是指任何一个g都可以作为生成元，尽管g不能生成中的所有元素。

定义：对于一个给定的g，假设是g所生成的一个集合，即

这里G的元素个数等于。

定义：若k为一个常数，g是一个高阶元素，其中：

我们很感激Noga Alon，他提出的一个严谨的计数问题，显示了中相当大一部分元素有着更高的阶。

命题1：

假设P和Q相等是大小的随机选择的素数，，且g是中的任意一个元素，那么：

证明将出现在本文的完整版本。

定义：假设，幂模复合函数可被定义为：

它的逆，离散对数模复合只由下列函数决定，其中且只由唯一的

请注意，虽然值的范围从1到N，但是仅输出大于的值，它是严格小于N的。

以下是文章所使用的假设的的列表，除非另有说明，我们假定所有这些假设成立，即使我们的一些成果没有它们也可以得出。

假设a.1: P和Q是相同大小的。

这种假设是在密码学中被常用且被认为强化了分解的困难性。

假设a.2: .

如果假设成立，中每个平方有且只有一个平方根，这也是一个平方。因此，平方是二次残基的置换。数字基于这两个假设被称为Blum整数。

假设a.3：g是一个二次剩余

我们指任何基于假设a.3的g都可作为生成元。需要注意的是命题1依然成立即使我们严格要求N是Blum整数，g是生成元。

假设[Y]:没有多项式布林环能把Blum整数的多项式分数部分作为分解因子。

定义： 一个可容三重函数(g,N,Z)满足以下条件：

1. N是一个Blum整数。
2. g是一个可容生成元。

可容三重函数的集合可以有效采样，即可以利用多项式量（时间，随机比特）选择一个随机可容三重函数。

一个众所周知的结果([Ba],[Ch])是：

定理2：

根据假设[Y],以Blum整数为幂模的是一个单向函数。

证明：

我们给出了这个定理的简单证明，并展示了一些对我们的结果至关重要的基本技术。我们认为要在的问题中种下一个简短却困难的秘密和在续集中广泛使用这个事实是可能的。

定义，假设，这里d是的最大倍数，且S非负。令|S|表示S的二进制大小，下面的关键引理证明S是极小值：

引理2.1：

证明：众所周知，对任意的，|，因此|。

假定，很容易得到是的最大倍数，同时它仍然比N要小，即，但是

，因此根据定义。因为，我们得到，即完成了引理的证明。

假设不是一个单向函数，可以得到存在一个多项式布林环C，它可以在不可忽略的Blum整数N、生成元、和元素上成功计算，我们使用C把一个不可忽略的部分的Blum整数分解成因子，于是与假设相矛盾。

假设B是包含Blum整数的多项式部分的集合，且C可以在不可忽略的Blum整数N、生成元、和元素上成功计算。给定，我们通过采用标准的随机化技术用C计算S，并在随后用S在下列方法之一中分解N的因子：

方法1：假设，，通过解决方程和，我们可以得到N的全部因子。

方法2：假设是中的任意一个元素，且让，k是满足的最大整数。若g是一个可容生成元，并且，则是以N为模的1的一个平方根，同时有1/2的概率，这使得N因式分解。注意这里方法1对几乎所有都可用，方法2对每个以任意高概率可用，但必须知道g的一个平方根。

3.的硬盘位

对整数U，假设是U的二进制表示，是它的最高位，是它的最低位，注意最高位总是二进制表示中的第n位，即使U的值可能覆盖了一个很小的间隔。的一个子链用表示。

定义 H.1:函数的第i位是硬盘位，如果随机给定一个可容三重函数(g,N,Z)，当成功的概率大于1/2 1/poly(n)时，不存在多项式布林环可以计算出的第i位。

注意，我们使用硬度的直接定义（跟[BM]中一样），而不是根据它的近似值是否跟计算一样难定义一个位是硬盘位(跟[LW]中一样).

定理3：

对每一个，的第i为是硬盘位，其中是一个极小的常数。

我们的结果留下了独立位的安全问题，尤其是左边的比特位的安全（）。这是由Johan Hastad [ TTA ]最近证明解决的。

定理4:

对每一个i，若，则的第i为是硬盘位。

证明O（log n）的的最重要的比特位的独立（同时）的安全性，需要对比特位的安全有一个新的定义（因此可以平凡的预测概率大于1 / 2）。在[SS]的工作中，我们可以定义这个概念并证明所有位的位安全。

假设x是函数的第i位输入位，并用b(i)表示其对偏置。注意只要

对于的偏差是显著超过1/2，我们给出的定义适用于任何偏压

定义 H.2: x是硬盘位如果任意一个多项式布林环都有一个随机的可容三重函数(g,N,Z),且对任意的多项式poly(n),都有：

定理5：

的O(log n)最高位是硬盘位。

我们现在给出定理3的完整证明，它包含了大部分新技术和方法。

定理3的证明：

假设存在一个i，第i位不是硬盘位。然后，存在一个多项式大小的环C：

，其中(g,N,Z)是一个预测第i位的成功率为1/2 的可容三重函数。像在定理2中一样，假设，我们通过计算的所有位并且根据定理2的一个简化版用环来分解N。

直观地说，我们可以把环看作一个窗口在长未知序列的第i个位置的比特。通过移动该窗口下面序列，我们可以看到它的一切。因此，我们需要一种方法来对未知的S通过已知的操作Y让其到右侧和左侧.我们应该注意不要造成一个环绕（即，移位的S减少以未知的为模），通过清空S的一些已知位同时在Y上操作.向左移动的结果必须来自Y的自乘.我们无法通过提取Y的平方根实现向右转移，因为当N的因子分解是未知时，该操作不能在多项式时间内完成。相反，我们采取了特殊的技术，即右移由更改幂函数的基数g，并利用该模平方以一个Blum整数为模的自乘是（随机选择的）可容生成元的置换这一事实引起的。

由于环可能出错，一是透过窗户看里面没有足够的数量。我们通过查询环在多项式中很多原始输入结果的随机倍数收对第i位的值投票，并用最大的票数决定它的值。为了实现这种随机化，我们必须对未知的猜测一个估计值，作为一个结合更好的随机选择，从而防止了包含关系的发生。由于乘法涉及到加入随机的已知指数的与的未知参数值，我们应该从加入的最低的i-1位中小心处理未知的进位第i位。我们通过猜测第i位右边的O（log n）位的值来解决问题。为每一位的值进行猜测这个策略的直接实现导致了指数算法的产生，但更精心实施可以确保只有一个多项式数是S的值的存在性。

证明时，我们首先详细的说明位置零，移位和随机化技术，这为我们提供了必要的提取S的工具.然后，我们分别证明三种可能的情况，并得出：

1. 中间位是硬盘位（命题3.1）。
2. 中间位右边的每一位都是硬盘位（命题3.2）。
3. 中间位左边的每个非极端位是硬盘位(命题3.3).

S在这个定理中的实际提取包括基本的正向提取过程，其中未知的S位被从最低位计算到最高位。在证明这个命题时，我们详细的描述了该程序其使用。在附录中，我们提出了一个更复杂的向后提取程序，其中该位从最高位到最低位被发现。向后提取程序对于定理4和5（及后面的8）的证明是必不可少的。 它也可以在命题3.1和3.3中用来代替前向提取过程，但在这方面，它没有任何的优势。

今后我们假设随机选择的g是高阶的，并相应地进行分析。g是高阶的小概率情况（命题1）不考虑到我们最终导出的用于S不正确的值的误差估计。

主要技术：

假设，且，若m表示的是的二进制表示中最左边的非0位的位置，则当时，，但。注意对于高阶g，，同时要注意仅仅时，

零位技术：

使一个U的已知的第j位变成0的技术是用表示的，很容易看到：

位移技术：

左移：假设我们已知，且我们知道，我们将比特链中的一位向左移动，当使移动之后的U的第m位为0时，利用m和将V变成。我们撤销了以防止移动之后的U的值变得比大，从而造成溢出，这将会使U的值从中减去已知完全改变U的值。当和m是未知的时，我们必须猜测m的值。

右移：我们能够将比特链中的一位沿着已知的低位下降的方向向右移动，从而将V变成。然而以N为模的平方根在不知道N的分解因子的情况下不能被有效计算出来，所以我们必须用一种间接的方法来计算它。

假设g不是任意选择的，而是以N为模自乘另一个可容生成元得到的。若，利用和U的最低位我们可以得到：

其中取决于U，如果U是未知的，那么也是未知的。然而，我们只能利用该技术得到当时，移动后的，很容易通过

得到。

命题3.1

对每个满足的i，的第i位是硬盘位。

证明：

为了简化这个陈述，假定我们已经被给出了第n/2位的数据，显然同样的推理适用于所有的i：。我们使用以下方法提取半个大小的秘密S：

正向提取程序：

1. 向左移动S的位，这将不会造成高阶g的一个包含关系。
2. 猜测S的个最低位不会通过环的位置，然后使这些猜测的位变为0以防止随机化过程中任何移动位进入环的位置。
3. 假设在之前的变化之后表示Y，是当前环的位置的所在位，通过在足够多的随机倍数中查询oracle来演绎并让它变为0.
4. 移动S的一位回到右边，在oracle的位置放置，无论什么时候S被放到它初始位置的左边，右移都会直接出现。
5. 重复步骤3-4，直到提取出所有的位，，。
6. 为之前在步骤2中的初始猜测的多项式数重复之前的步骤。

S在中的正确值是通过试图分解N的因子和每个输出的S来选择的。

命题3.2

对满足的每个i，都有的第i位是硬盘位。

证明

假定存在满足的i，的

剩余内容已隐藏，支付完成后下载完整资料

---

资料编号：[146346]，资料为PDF文档或Word文档，PDF文档可免费转换为Word