阅读此文前，诚邀您点击一下“关注”，方便您随时查阅一系列优质文章，同时便于进行讨论与分享，感谢您的支持~

文|三月十

编辑|hshdhdjehd

引言

向量承诺方案允许用户随后承诺一个值 x ∈ {0, 1}的向量，打开对一组特定位置的承诺。应该简洁（即，大小与向量长度 ℓ 成多对数关系）并且是非交互式的。

最近对矢量承诺的设计和应用产生了巨大的兴趣和进展，甚至出现了“矢量承诺研究日” 。从基于抗碰撞哈希函数的经典向量承诺方案开始，我们现在从基于配对的假设有了广泛的代数构造以及对未知阶组的假设。

重点关注进展有限的矢量承诺研究中的两个主题： (1) 基于格的后量子结构； (2) 功能承诺，支持对承诺值上的各种功能开放的矢量承诺的概括。

这两个方面的进展有限有充分的技术原因。首先，许多为向量承诺开发的技术关键地利用了配对中的代数结构和 RSA/类组，这些组不会自然地扩展到格设置。其次，配对和 RSA/类组仅支持有限的同态能力。

一、技术概述

从格构建向量承诺的新框架，以及我们用来证明硬度的基础增强 SIS 假设系列(BASIS) 。在下面的描述中，对于矩阵 A ∈ Z ，其条目根据 Ax = t 条件下的离散高斯分布。如下图：

在PPS1和MatrixACLMT结构中，目标向量 t 本质上是随机向量。这对于确保 A立即解除绑定很重要。使用结构化目标向量可以实现额外的功能。

在这项工作中采用的方法避免了这些限制，并允许我们构建具有大消息空间的向量承诺，并支持多项式和功能开口等新功能。

从等式中考虑相同的验证关系 c = A v + t 。 (1.1)，但采用完全不同的方法来计算承诺 c 和开口 v：我们对同时满足所有∈ [ℓ]的验证关系的随机元组(v1,vℓ，c)进行采样。

与前面的验证关系一样，我们要求开口v1, , vℓ很短。承诺 c 可以有很大的挑目。在我们的定设置中，我们将 c 写为 c = Gc^ ，其中c^ ∈ Z是一个短向量。

使用小工具矩阵 G 在安全分析中很重要。然后，方程式。 (1.1)对应关系Gc^ = A v + t 或等价地，A v − Gc^ = − t 对于所有∈ [ℓ]。我们可以将这些 ℓ 关系表示为线性系统：

要论证 v 隐藏了除(x) 所揭示信息之外的所有关于 x 的信息，请观察矩阵 D 仅取决于(x)而不是 x。因此，给定 A 的陷门（可以扩展为 D 的陷门）和值 (x)，我们可以对短 v 进行采样，使得 D v = u 的分布在统计上接近真实开口。

后一个过程仅依赖于(x)而不是 x，因此隐藏随之而来。虽然这个结构是隐藏的，但我们不知道如何证明它具有约束力；然而，它确实满足了目标绑定的较弱概念，其中绑定适用于所有诚实生成的承诺。我们提供了完整的细节和分析。如下图：

对于每个方案，我们将 CRS 的大小报告为安全参数和输入长度ℓ 的函数。如果在输入独立的预处理步骤之后，验证运行时间在ℓ中是次线性的，我们就说该方案支持“快速验证” 。在所有方案中，承诺和开口的大小在输入长度 ℓ 中是多对数的。

二、预赛

写poly(来表示一个固定函数，它是对于一些∈ N和negl表示一个函数是( − )对于所有∈ N。对于所有∈ N。如果事件的补集以可忽略的概率发生，我们说该事件以压倒性概率发生。如果算法在其输入长度内以概率多项式时间运算，则该算法是有效的。

我们说两个分部族D1 = {D1, } ∈N和D2 = {D2, } ∈N如果没有有效的算法可以以不可忽略的概率区分它们，则它们在计算上是不可区分的，如果统计距离 Δ(D1, D2)以可忽略的函数 negl为界。

1.格子预备知识

基于格的密码学中的一些标准概念。除非另有说明，否则我们对向量和矩阵使用 ℓ∞‑范数。对于向量 u，我们写∥u∥ := max ，对于矩阵 A，我们写成∥A∥ = max 。对于∈ N，我们写 I ∈ Z来表示逐单位矩阵。短整数解 (SIS) 问题[Ajt96]及其非⻬次变体，

了非⻬次 SIS (ISIS) 假设，其中上述假设中的目标0被均匀随机向量 y ←r Z代替。当 = poly( , log ) 并且对于足够大的 ≥ · poly时，硬度SIS 和 ISIS 问题可以基于将 维晶格上的某些最坏情况晶格问题近似到poly因子内。

B生成的维点阵L为L=L (B) = B ·Z= {Bz:z∈Z } 。对于向量 c ∈ R和格L ⊂ R，我们写 c + L = {c + x : x ∈ L}来表示与 c 相关联的L的陪集。

最后，如果 A ∈ Z对于整数，我们定义L⊥(A) = {x ∈ Z : Ax = 0 mod }。我们还将使用剩余的哈希引理及其一个简单的推论：

三、Vector 承诺与 SIS 的私人开放

如何根据标准 SIS假设构建具有私有开口的矢量承诺。我们首先回顾向量承诺的定义，在消息空间M上具有简洁局部开口的向量承诺方案由具有以下属性的高效算法元组ΠVC = (Setup, Commit, Open, Verify)组成：

如果对于所有多项式 ℓ = ℓ和所有对手 A（分别为有效对手 A），我们说承诺方案在统计上具有约束力（resp，计算绑定），对于向量维度ℓ、对手A 和模拟器S = (S0, S1)。

1.Basis‑Augmented SIS (BASIS)假设

用于构建向量承诺方案的 SIS 假设系列。在高层次上，我们的假设断言，即使给定与 A 相关的矩阵 B 的陷门，SIS 问题对于随机矩阵 A 也是困难的。

我们将我们的假设系列称为“基础增强 SIS”假设。正如我们在下面讨论的， BASIS 假设的某些版本可以简化为标准 SIS 假设。

例如，我们第一个构建带有私有开口的向量承诺依赖于一个简化为标准 SIS 假设的版本。

2.SIS 私下开放的矢量承诺

我们现在展示如何根据假设构建一个具有统计私有开口的矢量承诺方案。根据定理，我们可以反过来将硬度建立在标准 SIS 假设（具有多项式模量）的基础上。

来自 SIS 的矢量承诺为高斯宽度参数。令ℓ为矢量维度。我们为 Z 构造向量承诺方案ΠVC = (Setup, Commit, Open, Verify) 如下：

四、简洁的电路功能承诺

如何从BASISstruct假设获得通用电路的简洁功能承诺。我们考虑参数与布尔电路的深度成比例的方案。Let 是一个安全参数。

令F = {F } ∈N为函数族： {0, 1} → {0, 1}在长度为ℓ = ℓ的输入上，并且可以通过深度最多为布尔电路计算。 F的简洁功能承诺是高效算法的元组ΠFC = (Setup, Commit, Eval, Verify) 具有以下属性：

我们现在在功能承诺方案上定义了几个正确性和安全性属性：对于所有安全参数，所有函数∈F，以及所有输入x∈{0, 1} 。

如果在正确性定义中存在通用多项式poly= poly(log ℓ)，则功能承诺方案是简洁的。10 | = poly(log ℓ) 和这样对于所有 ∈ N, 如下图：

私有开口：对于对手A和模拟器S = (S0, S1)，我们首先定义两个分布，如果对于所有对手A （分别是有效的对手A），存在一个有效的模拟器S = (S0, S1)使得RealA (1 , 1 )是统计上（resp.，计算上）无法区分。

1.对线性函数的开放和对多项式承诺的应用

简洁的功能承诺具有较短的承诺和空缺，但验证算法的运行时间与（以便从 C~ 同态计算C~）成正比。

用于支持快速（而不是）的线性函数的设置，并推广以产生多项式承诺[KZG10]。在预处理模型中进行验证。我们的构造自然支持Z上的线性函数与[ACL+ 22]不同，我们不需要这些值，在承诺向量或线性函数的输出中要小。

支持大值对于获得简洁的多项式承诺是必要的。我们首先描述支持具有小系数的线性函数的结构，然后展示如何将结构扩展到 Z 上的任意线性函数。

结语

为了便于对我们的新假设进行密码分析，我们提供了假设的等效公式，这是我们的功能、多项式和可聚合承诺的基础考虑的变体。

请注意，我们可以假设，其中 T 是B 的Ajtai 陷门（定义 2.9） （即 T ← B在 gadget 陷门和 Ajtai 陷门之间有效转换，直到质量的小多项式损失活板门。

基础的质量会随着维度的增加而降低。对于此参数设置，假设的任何具体攻击，并推测其安全性与SIS的硬度相当，噪声边界 bound = poly( ℓ)随向量的维度缩放，硬度随着维度的增加而降低。

参考文献：

1.米克洛斯·阿杰泰。生成格问题的硬实例（扩展摘要）。在 STOC，1996 年。

2.Joël Alwen 和 Chris Peikert。为硬随机格生成较短的基。在 STACS，2009 年。

3.尼尔·比坦斯基和亚历山德罗·基耶萨，来自多证明者交互式证明的简洁论证及其效率优势。在 CRYPTO 中，2012 年。

4. Dan Boneh、Manu Drijvers 和 Gregory Neven，小型区块链的紧凑型多重签名，在亚数字, 2018年。

5. Dan Boneh、Craig Gentry、Sergey Gorbunov、Shai Halevi、Valeria Nikolaenko、Gil Segev、Vinod Vaikun tanathan 和 Dhinakaran Vinayagamurthy。全密钥同态加密、运算电路ABE和紧致乱码电路，在 EUROCRYPT，2014 年。