Cryptographic commmitment: emulates an envelope.

Syntax

a commitment scheme is two algorithms: commit and verify

commit(msg, r) -> com

r: secret randomness in R, also called bliding factor com : commitment string
verify(msg, com, r) -> accept or reject

anyone can verify that commmitment was opened correctly

security properties

binding: Bob cannot produce two valid openings for com

More procisely: no efficient adversary can produce com, (m1, r1), (m2, r1), such that verify(m1, com, r1) = verify(m2, com, r2)=accept and m1!=m2
hiding: com reveals nothing about committed data

commit(m, r)->com, and r is sampled uniformly in R, then com is statistically indenpent of m.

离散对数假设

根据参与方计算能力的不同，承诺方案一般分为两类：schemes with computationally hiding, perfect binding and schemes with computationally binding, perfect hiding

Example 1: hash-based commitment

Fix a hash function: H: M x R->C (e.g., SHA256), (M:hash space, R: randomness space, C: commitment space), where H is collision resistant, and |R| >> |C|(Randomness space is much large than commitment space)

\[comit(m \in M, r \gets R)\]: com = H(m, r)

sample a random string r from set R
verify(m, com, r): accpet if com = H(m, r)
binding: follows from coll ision resistance of H
hiding: follows from a mild assumption on H assume function H behaves sort of like a random function, then the fact that the randomness space is so much bigger than the commitment means that given the commitment value h(m, r) is actually independent of m

Example 2: Pedersen Commitment

Pederson 承诺,于 1992 年被 Pedersen 在 “Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing” 一文中提出。

该 paper 的 section 对 Pedersen Commitment 讲述极为简洁易懂,可以读读

Pedersen 承诺是一个满足完美隐藏、计算绑定的同态承诺协议，其完美隐藏性不依赖与任何困难性假设(randomness <- algebraic hash function)，计算绑定依赖于离散对数假设(DLA). 该以指数运算的形式提出(基于离散对数难题), 而目前 Pedersen Commitment 主要搭配椭圆曲线密码学使用(基于椭圆曲线的离散对数问题）,具有基于离散对数困难问题的强绑定性和同态加法特性的密文形式。下面分别介绍该承诺的两种形式.

基于离散对数的 Pedersen Commitment

Core: The committer commits himself to an \[s \in Z_q\] by choosing \[t \in 2_q\], at random and computing: \[com = g^s * h^t\]

初始化阶段 setup:

选择阶为大素数 q 的乘法群 G, 生成元，\[G=<g>=<h>\]，公开三元组:(g，h，q)；

chosing a prime-order group \(G\) = finite cyclic group = \[{1, g, g^2, ..., g^{q-1}}\] where \[g^i * g^j = g^{i+j \mod q}\](note: element generated by generator is in the group). \[q = |G|\]

Fix g,h in G and let R = {0, 1, 2, q-1}.

由于 r 为随机数，Pedersen commitment 具有完美隐藏性（unconditionally hiding）特性，以及基于离散对数假设的完美隐藏性（computationally binding）特性。
承诺阶段 com

承诺方选择随机数 r 作为盲因子，计算承诺值，然后发送 com 给接收者； prepare secret value m, choose blinding factor \[r \in R\], and commmit

\[commit(m \in R, r \gets R) = H(m, r) = g^m * h^r\]

Fact: For a cryptograpic group G, this H is collision resistant, this called discrete logs problem.
打开阶段 open

承诺方发送 (m，r) 给接收者，接收者验证 com 是否等于 \[H(m, r) = g^m * h^r\]，如果相等则接受，否则拒绝承诺。

homomorphic property

\[commit(m \in R, r \gets R) = H(m, r) = g^m * h^r\]

Suppose: \[commit(m1 \in R, r_1 \gets R) \to com_1\] and \[commit(m2 \in R, r_2 \gets R) \to com_2\]

Then \[com_1 \times com_2 = g^{m_1+m_2} \times h^{r_1+r_2} = commmit(m_1 + m_2, r_1 + r_2)\]

anyone can sum commmited value. This is the homomorphic property which lets you compute uncommited values(m1+m2) without knowing what the commited values actually are.

基于椭圆曲线的 Pedersen Commitmentt

Core: \[C = r * G + m * H\]

上述公式中，C 为生成的承诺值，G、H 为特定椭圆曲线上的生成点，r 代表着盲因子（Blinding factor），m 则代表着原始信息。由于 G、H 为特定椭圆曲线上的生成点，所以 r _ G、v _ H 可以看作是相应曲线上的公钥（r、v 同理也可以视为私钥）。

由于引入了随机盲因子 r，对于同一个 m 会就能产生不同的承诺 c，即便敏感隐私数据 m 不变，最终的承诺 C 也会随着 r 的变化而变化，因此提供了信息论安全的隐匿性.

Commitment C(x, a) ) is information-theoretically private because there are many possible combinations of m and r that would output the same C. If r is truly random, an attacker would have literally no way to figure out m.

Pedersen Commitment 应用

数值隐藏

承诺方随机选择 blinding factor, 然后通过构造关于数值 value 的承诺.
恒等关系验证/隐秘交易

主要利用其加性同态的特性

只要第一个数等于后两个数之和，验证者不会看到交易量具体值，但是又不得不承认 A 真的分了一部分钱给 B，然后还有一部分钱又退回给了 A。这样既隐藏了数据本身，又证明了数据的关系。虽然 Pederson 承诺证明了数字之间的关系，但是并没有限制任何数字的取值区间，因此还需要对隐藏的数值进行范围证明！

ref: USENIX2018: zkLedger

编程参考

Pedersen commitment (with elliptic curves) - Findora

两个 Python 源码(密码学库: PyCryptodome)

Cryptographic Commitment and pedersen commitment