Commitment scheme

承诺机制的应用很广泛，比如零知识证明、数字签名、安全计算等。

0x00 What is commitment scheme?

A commitment scheme is a cryptographic primitive that allows one to commit to a chosen value (or chosen statement) while keeping it hidden to others, with the ability to reveal the committed value later.Commitment schemes are designed so that a party cannot change the value or statement after they have committed to it: that is, commitment schemes are binding. Commitment schemes have important applications in a number of cryptographic protocols including secure coin flipping, zero-knowledge proofs, and secure computation.

A way to visualize a commitment scheme is to think of a sender as putting a message in a locked box, and giving the box to a receiver. The message in the box is hidden from the receiver, who cannot open the lock themselves. Since the receiver has the box, the message inside cannot be changed—merely revealed if the sender chooses to give them the key at some later time.

可以看维基百科给出这个直观的例子。

0x01 Demo

Suppose Alice and Bob want to resolve some dispute via coin flipping. If they are physically in the same place, a typical procedure might be:

1
2
3

1. Alice "calls" the coin flip
2. Bob flips the coin
3. If Alice's call is correct, she wins, otherwise Bob wins

If Alice and Bob are not in the same place a problem arises. Once Alice has “called” the coin flip, Bob can stipulate the flip “results” to be whatever is most desirable for him. Similarly, if Alice doesn’t announce her “call” to Bob, after Bob flips the coin and announces the result, Alice can report that she called whatever result is most desirable for her. Alice and Bob can use commitments in a procedure that will allow both to trust the outcome:

1. Alice "calls" the coin flip but only tells Bob a *commitment* to her call,
2. Bob flips the coin and reports the result,
3. Alice reveals what she committed to,
4. Bob verifies that Alice's call matches her commitment,
5. If Alice's revelation matches the coin result Bob reported, Alice wins

For Bob to be able to skew the results to his favor, he must be able to understand the call hidden in Alice’s commitment. If the commitment scheme is a good one, Bob cannot skew the results. Similarly, Alice cannot affect the result if she cannot change the value she commits to.

A real-life application of this problem exists, when people (often in media) commit to a decision or give an answer in a “sealed envelope”, which is then opened later. “Let’s find out if that’s what the candidate answered”, for example on a game show, can serve as a model of this system.

通过这个简单的Demo就能对承诺机制有进一步的了解，简单来说就是防止抵赖的，这个属性和数字签名一样，

0x02 Main Phases

Interactions in a commitment scheme take place in two phases:

the commit phase during which a value is chosen and specified
the reveal phase during which the value is revealed and checked

0x03 Tow properties

In simple protocols, the commit phase consists of a single message from the sender to the receiver. This message is called the commitment. It is essential that the specific value chosen cannot be known by the receiver at that time (this is called the hiding property). A simple reveal phase would consist of a single message, the opening, from the sender to the receiver, followed by a check performed by the receiver. The value chosen during the commit phase must be the only one that the sender can compute and that validates during the reveal phase (this is called the binding property).

0x04 Conclusion

承诺机制的目的或应用场景是什么？

在不泄露明文的前提下，对隐私数据的内容进行承诺。一旦做出承诺就无法对承诺进行更改。
需要怎样实现两个主要属性

Hiding：任何接收者，很难根据承诺值推断出初始值

Binding：任何发送者，很难构造两个不同的初始值，使得它们的承诺值相同（即接收者被欺骗）
Hash方式为什么不能成为真正的承诺机制:

hash固有特性，即使哈希函数抗碰撞，只能实现 computationally binding，并不能实现perfect hiding

In general, a scheme can not be both perfectly hiding and perfectly binding, because they are opposing principles: If Alice was computationally unbound, hiding means she can decomit ANY value, and binding means she could still decomit ONLY the original value

0x05 Pedersen Commitment

基于离散对数困难假设的承诺机制，具有完美隐藏unconditionally hiding 和计算绑定 computationally binding的特性。

有基于离散对数的模式，多半就有基于椭圆曲线的模型（离散对数和椭圆曲线本质是一样的，只是体现在的空间不同）

具有同态性

setup:

选择素数 $q$ 的乘法群 $\mathbb{G}$ , $g,h$ 为其生成元，公开 $(g,h,q)$

commit:

发送者选择随机数 $r$ 作为盲因子，计算承诺值 $y=g^xh^r(modq)$ ，将其发送给接收者

reveal:

发送者将 $(x,r)$ 发送给接收者，接收者验证 $g^{x'}h^{r'}(modq)=y?$ ,如果相等就接受，否则拒绝承诺。