格密码学基础（五）（完结篇）：基于Σ-协议构造数字签名

❝

原文：https://eprint.iacr.org/2024/1287

作者：Vadim Lyubashevsky

译者：Kurt Pan

格密码学基础（一）：前言

格密码学基础（二）：加密

格密码学基础（三）：LWE和其他格问题的难度

格密码学基础（四）：多项式环上的加密

在本节中,我们将努力构造一个基于格的数字签名方案,其高层结构类似于经典的基于离散对数的Schnorr签名方案[Sch89]。在Schnorr数字签名方案中,公钥由有限域中的两个元素组成,签名是指数满足的非交互式零知识知识证明(ZKPoK)。非交互式证明通过两步获得。首先,构造一个3轮交互式-协议,它是满足的的诚实验证者ZKPoK。其次,使用Fiat-Shamir变换将交互式证明转换为非交互式证明。

5.1 陈述和见证

我们现在想遵循类似的路线图,从和问题构造签名方案。可以从实例开始,其中,将作为公钥,并希望能够创建一个零知识证明来证明对适当范围内的的知识。

❝

回忆第4.2节中的记号：对于多项式，意味着的所有系数从集合中均匀随机选择，而意味着多项式向量中的所有个多项式的系数都从集合中均匀选择。

创建这样的证明结果不如在离散对数设置中那么直接和高效。原因是除了证明满足的代数关系外,我们还需要证明的系数落在特定范围内(理想情况下是,但对于某个稍大于的,也可以)。

源自-协议的最高效签名绕过了证明满足

的小的知识的需要,而是证明方程的"松弛"解的知识。特别地,我们将给出允许拥有满足上述方程的的证明者证明的知识的协议,其系数在比稍大的区间内,以及另一个系数很小的元素,满足

下面的简单证明表明证明这样的知识仍然证明了一些有意义的东西。特别地,它将使我们可以得出结论:能够产生这样的和意味着可以求解与矩阵相关的环LWE或环SIS。

❝

引理9. 假设存在一个算法,当给定,其中,能够得出和使得。那么存在另一个算法,运行时间相同,成功概率相同,能够求解或问题。

证明. 令为假设中的算法,假设我们被给定均匀随机矩阵,这是问题的一个实例。我们将给。根据假设,这在计算上与期望的分布不可区分(所以如果不成功,我们可以用它来求解)。如果产生系数至多为的满足,那么我们有实例的解。□

5.1.1 挑战空间

(以及和)中系数的大小将取决于ZKPoK的挑战空间。由于我们希望这些很小,我们想定义挑战空间,使其由范数很小的多项式组成。

如果在环上工作,其中的次数为,那么定义为使的最小整数(假设足够大以使这样的存在)。然后定义挑战集为

所有(非零)差的集合为

因此由中所有恰好有个非零系数取自集合的多项式组成。根据的定义,的大小恰好是。注意我们可以定义也包括少于个非零系数的多项式,但这会增加在中采样随机元素的复杂性,同时不会大幅增加其大小。

❝

对长度为 d、包含 η 个 ±1 的随机向量进行采样可以通过以下方式完成：初始化一个 d 维向量，其中包含 η 个 1，然后执行一次洗牌（例如 Fisher-Yates 洗牌）以获得该向量的随机排列，最后随机地对每个 1 进行取反（或不取反）。

5.2 基本-协议

我们现在描述图5中给出的基本方案,它在[Lyu09]中提出。该协议的一个不寻常特征是它没有完美完备性。为了保持输出系数的小,在-协议的最后一轮执行拒绝采样步骤,以确保分布独立于秘密。在本教程的所有协议中,拒绝采样步骤将相当简单——只是检查所有系数是否在某个范围内。可以执行稍微复杂一些的拒绝采样步骤,需要根据离散高斯分布进行采样和拒绝,这会导致稍小的输出[Lyu12, DDLL13]。后一种算法的主要缺点是拒绝采样步骤更复杂,稍微不正确的实现可能最终泄露私钥——防御侧信道攻击也可能更复杂。因此,对于像数字签名这样广泛使用的原语,在实践中更简单的算法可能更可取。

私有信息:公开信息:

图5: 基本零知识证明系统,其中证明者知道,并给出和满足知识的ZKPoK。值在引理10中定义,的值影响协议的完备性(即不发送的概率),如引理10中所述。

拒绝采样步骤的主要后果是签名算法的运行时间将是一个随机变量(但独立于),而不是固定的。除此之外,熟悉Schnorr型证明的读者会在该协议中发现很多相似之处。协议的第一阶段包括创建掩蔽变量和,第二步是挑战,最后一步包括将掩蔽添加到挑战和秘密的乘积上。然后执行拒绝采样步骤,如果证明者发送,他中止并需要重新启动协议。该协议到签名方案的转换将使用通常的Fiat-Shamir变换,其中挑战被创建为消息和证明者的第一条消息的哈希。

在交互式方案中保持通信大小紧凑的一个常见技巧是发送第一条消息的哈希而不是消息本身。因为未哈希的第一条消息可以从下一轮发送的那些中恢复,验证者能够在验证期间计算该消息的哈希。在使用拒绝采样的格设置中,这个技巧还有一个额外的优势,即它将允许我们模拟发生拒绝的脚本。然而,这种哈希对于证明签名方案的安全性是不必要的,因为签名者看不到中止的签名尝试。因此,我们将呈现不带哈希的交互式方案,并仅在没有中止(即没有发送)的情况下证明零知识。

5.2.1 诚实验证者零知识

我们现在将证明图5中的协议是HVZK的。即,我们将展示如何在不知道秘密的情况下创建有效的脚本。证明的关键是下面的引理,它表明对于所有系数有界的,的概率相同,并且的分布独立于。

❝

引理10. 如果使得对于所有多项式,都有,那么对于图5中协议的所有

❝

当  ，  时，我们可以简单的定义 .

证明. 考虑作为整数向量的和,用4.1.1节的记号写为

的第个系数(对于任何)是中特定系数的概率恰好是。原因如下:假设中的第个系数是,那么向量的第个系数需要恰好是。注意且意味着,这恰好是选择系数的范围。因此将是这个值的概率恰好是。因此

由于有个可能的有效可以被发送,我们得到引理第一部分的断言。

要获得引理的第二部分,我们观察到该概率= 上式/第一部分概率。□

证明者不发送的概率是

因此设置会导致协议在发送非值之前需要期望次重复。当然可以将设置得更小,代价是更高的期望重复次数。

我们现在使用引理10来展示如何以正确的概率模拟非中止脚本,这将表明图5中的协议在不发送的情况下是诚实验证者零知识的。

模拟器选择随机,设置并输出。这个分布完美模拟非中止脚本,因为是均匀的,根据引理10,的值是均匀随机的(对于任何);而由其他变量唯一确定。这完成了图5中协议在不发送时是HVZK的证明。

在继续之前,我们想指出诚实证明者发送(从而必须重复协议)的概率独立于秘密(引理10)。这在实际应用中很重要,因为运行时间对秘密的任何依赖都会导致侧信道攻击,其中敌手试图通过观察证明者的运行时间来推断关于秘密的一些信息。因此图5中的协议对这种特定攻击免疫。

5.2.2 知识证明

为证明该协议是PoK,使用通常的回绕（rewinding）论证(见图6),其中证明者发送,然后成功回复两个挑战,分别为和。如果我们能提取满足验证方程的两个这样的脚本和,那么我们有。前面的式子简化为

这恰好是所证陈述,其中。

公开信息:

图6: 提取程序。

5.2.3 综合考虑

诚实验证者零知识性质意味着敌手从看到非中止脚本中不获得任何信息。知识证明性质意味着能够模拟证明者的敌手可以产生如上的解,这通过引理9意味着他可以求解环LWE或环SIS问题。两个性质一起意味着(假设环SIS和环LWE是困难的)即使敌手观察到先前的非中止有效交互,他也无法在图5的协议中模拟证明者。这使得我们可以使用Fiat-Shamir变换,在随机预言机模型中,基于环SIS和环LWE的难度构造数字签名方案。

5.2.4 参数设置

本节开头的知识证明论证意味着可以提取系数在中的和使得,满足条件。然后引理9指出如果是困难的,那么上述提取意味着求解。因此最优参数设置是当这两个问题同样困难时——即这些问题在图2中的同一垂直位置。选择参数由引理10决定。应设置为约,其中使得对于所有,。因此如果选择使得,那么可以设置为。因此比大约倍。

5.3 与离散对数方案的类比:Schnorr、Okamoto和Katz-Wang

在本节中,我们将深入探讨图5中基于格的协议与基于离散对数的协议之间的类比。

❝

本部分对于后续章节并非必需，如果只想直接阅读基于格的签名方案的最终构造，则可以跳过本部分。

如前所述,格协议及其Fiat-Shamir转换的签名方案与Schnorr识别和签名方案[Sch89]非常类似。我们将在下面看到,通过简单地改变参数(以及从它派生的),可以获得具有略微不同安全特性的方案,这些方案类似于文献中其他基于离散对数的方案。最终,事实证明Schnorr实例化(可以自由设置而没有任何约束)是最有效的变体;但我们仍然相信看到其他变体有助于更直观地了解如何构造和实例化基于格的协议是有益的。实际上,理解参数如何影响格方案的性质是设计格密码学协议的重要组成部分。

Schnorr

Schnorr协议中的公钥由随机和组成,其中是私钥。在第一步中,证明者选择随机掩蔽变量,计算,并将发送给验证者。验证者发送随机挑战,证明者用回复,验证者检查。

为了证明模拟(在诚实验证者设置中)意味着破解离散对数,在收到离散对数挑战后,我们将其设置为公钥。不知道使的,可以通过首先选择随机,然后设置来模拟诚实生成的脚本。此后,可以证明如果敌手能够模拟,那么通常的回绕论证获得两个脚本和使得和。由此,我们得到和满足。从后者可以得到有效的离散对数解。

图5中的基于格的类比将公钥设置为,私钥为。在格情况下,我们提取满足(74)的,然后使用引理9表明这意味着实例的环SIS的解。一个小差别是在Schnorr签名的情况下,公钥是随机的,而在格情况下,我们需要环LWE假设来论证引理9中的公钥看起来是随机的。

应该观察到,在代数上,基于格的方案和基于离散对数的方案非常相似。在两种情况下,都有某个同态单向函数族,公钥由组成,其中是该族的随机选择成员,是随机选择的私钥。第一步包括选择随机掩蔽并发送。在挑战上,证明者用响应。离散对数协议的不同性质是通过改变的域和值域的大小之间的关系来实现的——格类比使用相同的蓝图获得,正如我们现在将看到的。

Okamoto

Okamoto协议[Oka92]在精神上与Schnorr协议相似,其主要区别特征是可以证明Okamoto识别方案对主动敌手安全——即即使验证者对抗性地选择挑战,它也可以被证明是安全的。由于Fiat-Shamir转换只需要HVZK,Okamoto签名的这种更强性质在实践中对于构造数字签名方案并不真正需要。

Okamoto方案中的公钥由随机和组成。在第一步中,证明者选择随机并输出。收到挑战后,证明者对输出。验证者检查。为了证明Schnorr方案的安全性,我们需要通过首先选择随机并从中导出来模拟脚本。在Okamoto方案中,不需要模拟——所需要做的就是诚实地运行方案。从离散对数问题的归约如下进行:给定离散对数实例,其中对于某个未知的,提取器选择有效的私钥并将公钥设置为。因此他可以通过诚实运行协议来诚实回答敌手的所有查询。如果敌手之后成功模拟证明者,那么通常的回绕论证导致两个脚本使得

可以重写为

其中且。通过进一步将重写为,得到

现在观察到只要不都是0,我们就可以获得离散对数问题的解——即找到使得。

表明以很高的概率不会等于0,我们注意到给定,存在许多可能的使得——实际上,如果,那么任何满足的都是有效的。这些对中的任何一个被选为原始私钥的可能性都是相等的。然后我们需要证明Okamoto协议中脚本的分布(即)是相同的,无论选择了哪个有效私钥(即使敌手控制)。

❝

这源于  均匀分布，因为  均匀分布，所以  是  和  的确定性函数。

一旦确立了这一点,就可以看到如果模拟证明者的算法可以发送使得,那么他知道值。但这些是信息论隐藏的,因此(即使是全能的)模拟器能够输出这样的的概率并不压倒性。因此模拟器可以用来求解离散对数。注意相同的证明在Schnorr协议中不起作用的原因是公钥是,并且只有一个可能的私钥。

在格设置中,在Schnorr型和Okamoto型方案之间移动所需要做的就是设置私钥使得公钥以很高的概率不唯一确定私钥。这只需要我们选择更大的。特别地,如果我们选择使得,那么任何(全能)算法能够恢复确切的的概率只有。

❝

为了理解这一点，观察当给定值  时，猜测原像 (  ) 的最优策略是确定性地猜测最可能的原像。由于  的定义域大小为 ，最优猜测器最多输出  个可能的原像。由于总共有  个原像，每个原像被选中的概率均等，因此最优猜测器只会输出其中  个原像。

脚本不泄露关于的任何信息的事实在引理10中得到证明。

但就像Okamoto签名方案不如Schnorr方案高效一样,对的附加要求将使这种基于格的实例化不太优化。我们将在介绍下一个Schnorr变体后更详细地讨论这一点。

Katz-Wang

另一个具有略微不同安全性质的Schnorr型协议是Katz-Wang协议[KW03, 第3节]。该方案的区别特征是它完全基于DDH问题,其安全性证明不需要回绕。不进行回绕的优势是安全性归约更紧。

❝

在使用回绕的归约方法中，随机预言机查询次数会损失一个倍数因子。

因此,理论上,[KW03]方案与离散对数型问题的联系更紧密。在格设置中,如果想在量子随机预言机模型(QROM)中证明方案的安全性,其中敌手被假定为量子的并且不能直接回绕(因为量子态不能被复制),那么回绕使安全性归约更不紧密。然而,无论在经典还是格设置中,从离散对数或格问题的归约的紧密性似乎都不影响签名方案的安全性,因此Okamoto和Katz-Wang方案及其格版本仍然主要只具有理论兴趣。

Katz-Wang方案中的公钥由随机和组成,对于随机秘密。要签名,首先创建随机掩蔽,然后计算,并将发送给验证者。收到挑战后,证明者计算。然后验证者检查是否。