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.