Constant-size commitments to polynomials and their applications
发表信息
作者
- Aniket Kate
- Gregory M Zaverucha
- Ian Goldberg
笔记
We introduce and formally define polynomial commitment schemes, and provide two efficient constructions. A polynomial commitment scheme allows a committer to commit to a polynomial with a short string that can be used by a verifier to confirm claimed evaluations of the committed polynomial. Although the homomorphic commitment schemes in the literature can be used to achieve this goal, the sizes of their commitments are linear in the degree of the committed polynomial. On the other hand, polynomial commitments in our schemes are of constant size (single elements). The overhead of opening a commitment is also constant; even opening multiple evaluations requires only a constant amount of communication overhead. Therefore, our schemes are useful tools to reduce the communication cost in cryptographic protocols. On that front, we apply our polynomial commitment schemes to four problems in cryptography: verifiable secret sharing, zero-knowledge sets, credentials and content extraction signatures.
我们介绍并正式定义了多项式承诺方案，同时提供了两种高效的构建方法。多项式承诺方案允许承诺者通过一个简短字符串对多项式进行承诺，验证者可以利用该字符串确认所声称的多项式求值结果。尽管现有文献中的同态承诺方案也能实现这一目标，但其承诺大小与所承诺多项式的次数呈线性关系。相比之下，我们方案中的多项式承诺具有恒定大小（单个元素）。打开承诺的开销同样是恒定的；即便是打开多个求值结果，也仅需恒定的通信开销。因此，我们的方案是降低密码协议中通信成本的有力工具。基于此，我们将多项式承诺方案应用于密码学中的四个问题：可验证秘密共享、零知识集合、凭证以及内容提取签名。
An extended version of this paper is available [24]. This research