#### Milestone Year

### 1991

#### Commitment Schemes: Hiding, Binding, and Non-Malleability

A commitment scheme is a method to commit to a value so that
at the committal time the value remain hidden, and yet the
information sent binds the sender to a unique value,
which it may reveal at a later stage.

The definition of a commitment scheme contain a conflict
between the binding and the hiding requirements, and this conflict
can be resolved only if one of the terms is understood in terms
of infeasibility (i.e., difficulty) rather than impossibility.

For example, in 1989, a WIS scientist showed how to construct
a commitment scheme in which binding holds in an information
theoretic sense whereas hiding holds only with respect
to computationally bounded observers.
Unlike prior schemes,
his scheme uses the minimal possible hardness assumption.

A dual scheme, in which hiding is information theoretic while
binding hold only with respect to computationally bounded parties,
was presented by a WIS scientist and his collaborators in 2007, improving
over a prior work by a WIS scientist and his collaborators from 1992.
This scheme too uses the minimal possible hardness assumption.

In 1991, a WIS scientist and his collaborators noted that in some
settings the above notions of hiding and binding are insuffient.
Consider bidding where in the first round each party publicly
commits to a bid. In such a setting, given commitment to a value,
it should infeasible to create a commitment to a related value
(say, the original value plus 1).
Addressing this concern, they proposed a scheme in which
such an "tampering" with the commited value is infeasible;
that is, it is infeasible for a party seeing the commitment,
not only to learn the committed value,
but also to generate a commitment to a related value.
This feature is called non-malleability
and a general study of this notion, which is related to
the preservation of security under concurrent executions,was initiated in the same work.