Editing Undeniable signature

An '''undeniable signature''' is a [[digital signature]] scheme which allows the signer to be selective to whom they allow to verify signatures. The scheme adds explicit signature repudiation, preventing a signer later refusing to verify a signature by omission; a situation that would devalue the signature in the eyes of the verifier. It was invented by [[David Chaum]] and Hans van Antwerpen in 1989.<ref>{{cite book|last1=Chaum|first1=David|last2=van Antwerpen|first2=Hans |title=Advances in Cryptology — CRYPTO' 89 Proceedings |chapter=Undeniable Signatures |series=Lecture Notes in Computer Science |date=1990|volume=435|pages=212–216 |doi=10.1007/0-387-34805-0_20|isbn=978-0-387-97317-3 }}</ref>

== Overview ==
In this scheme, a signer possessing a private key can publish a signature of a message. However, the signature reveals nothing to a recipient/verifier of the message and signature without taking part in either of two interactive protocols:
* Confirmation protocol, which confirms that a candidate is a valid signature of the message issued by the signer, identified by the public key.
* Disavowal protocol, which confirms that a candidate is not a valid signature of the message issued by the signer.

The motivation for the scheme is to allow the signer to choose to whom signatures are verified. However, that the signer might claim the signature is invalid at any later point, by refusing to take part in verification, would devalue signatures to verifiers. The disavowal protocol distinguishes these cases removing the signer's [[plausible deniability]].

It is important that the confirmation and disavowal exchanges are not transferable. They achieve this by having the property of zero-knowledge; both parties can create transcripts of both confirmation and disavowal that are indistinguishable, to a third-party, of correct exchanges.

The [[designated verifier signature]] scheme improves upon deniable signatures by allowing, for each signature, the interactive portion of the scheme to be offloaded onto another party, a designated verifier, reducing the burden on the signer.

== Zero-knowledge protocol ==
The following protocol was suggested by [[David Chaum]].<ref>{{cite book|last1=Chaum|first1=David |title=Advances in Cryptology — EUROCRYPT '90 |chapter=Zero-Knowledge Undeniable Signatures (Extended abstract) |series=Lecture Notes in Computer Science |date=1991|volume=473 |pages=458–462|doi=10.1007/3-540-46877-3_41|isbn=978-3-540-53587-4 |doi-access=free}}</ref>

A group, ''G'', is chosen in which the [[discrete logarithm problem]] is intractable, and all operation in the scheme take place in this group. Commonly, this will be the finite cyclic group of order ''p'' contained in '''Z'''/''n'''''Z''', with ''p'' being a large [[prime number]]; this group is equipped with the group operation of integer multiplication modulo ''n''. An arbitrary [[primitive element (finite field)|primitive element]] (or generator), ''g'', of ''G'' is chosen; computed powers of ''g'' then combine obeying fixed axioms.

Alice generates a key pair, randomly chooses a private key, ''x'', and then derives and publishes the public key, ''y = g<sup>x</sup>''.

=== Message signing ===
# Alice signs the message, ''m'', by computing and publishing the signature, ''z = m<sup>x</sup>''.

=== Confirmation (i.e., avowal) protocol ===
Bob wishes to verify the signature, ''z'', of ''m'' by Alice under the key, ''y''.
# Bob picks two random numbers: ''a'' and ''b'', and uses them to blind the message, sending to Alice: {{glossary}}{{defn|''c {{=}} m<sup>a</sup>g<sup>b</sup>''.}}{{glossary end}}
# Alice picks a random number, ''q'', uses it to blind, ''c'', and then signing this using her private key, ''x'', sending to Bob: {{glossary}}{{defn|''s<sub>1</sub> {{=}} cg<sup>q</sup>'' and}}{{defn|''s<sub>2</sub>'' {{=}} ''s<sub>1</sub><sup>x</sup>''.}}{{glossary end}} Note that {{glossary}}{{defn|''s<sub>1</sub><sup>x</sup>'' {{=}} ''(cg<sup>q</sup>){{sup|x}}'' {{=}} ''(m<sup>a</sup>g<sup>b</sup>'')''{{sup|x}}g<sup>qx</sup>'' {{=}} ''(m{{sup|x}}){{sup|a}}(g{{sup|x}}){{sup|b+q}}'' {{=}} ''z{{sup|a}}y{{sup|b+q}}''.}}{{glossary end}}
# Bob reveals ''a'' and ''b''.
# Alice verifies that ''a'' and ''b'' are the correct blind values, then, if so, reveals ''q''. Revealing these blinds makes the exchange zero knowledge.
# Bob verifies ''s<sub>1</sub>'' = ''cg<sup>q</sup>'', proving ''q'' has not been chosen dishonestly, and {{glossary}}{{defn|''s<sub>2</sub>'' {{=}} ''z<sup>a</sup>y<sup>b+q</sup>'',}}{{glossary end}} proving z is valid signature issued by Alice's key. Note that {{glossary}}{{defn|''z<sup>a</sup>y<sup>b+q</sup>'' {{=}} ''(m{{sup|x}})<sup>a</sup>(g<sup>x</sup>)<sup>b+q</sup>''.}}{{glossary end}}

Alice can cheat at step 2 by attempting to randomly guess ''s<sub>2</sub>''.

=== Disavowal protocol ===
Alice wishes to convince Bob that ''z'' is not a valid signature of ''m'' under the key, ''g<sup>x</sup>''; i.e., ''z ≠ m<sup>x</sup>''. Alice and Bob have agreed an integer, ''k'', which sets the computational burden on Alice and the likelihood that she should succeed by chance.
# Bob picks random values, ''s ∈ {0, 1, ..., k}'' and ''a'', and sends: {{glossary}}{{defn|''v{{sub|1}} {{=}} m{{sup|s}}g{{sup|a}}'' and }}{{defn|''v{{sub|2}}'' {{=}} ''z{{sup|s}}y{{sup|a}}'',}}{{glossary end}} where  exponentiating by ''a'' is used to blind the sent values. Note that {{glossary}}{{defn|''v{{sub|2}}'' {{=}} ''z{{sup|s}}y{{sup|a}}'' {{=}} ''(m{{sup|x}}){{sup|s}}(g{{sup|x}}){{sup|a}}'' {{=}} ''v{{sub|1}}{{sup|x}}''.}}{{glossary end}}
# Alice, using her private key, computes ''v{{sub|1}}{{sup|x}}'' and then the quotient, {{glossary}}{{defn|''v{{sub|1}}{{sup|x}}v{{sub|2}}{{sup|−1}}'' {{=}} ''(m{{sup|s}}g{{sup|a}}){{sup|x}}(z<sup>s</sup>g<sup>xa</sup>){{sup|−1}}'' {{=}} ''m{{sup|sx}}z{{sup|−s}}'' {{=}} ''(m{{sup|x}}z{{sup|−1}}){{sup|s}}''.}}{{glossary end}} Thus, ''v{{sub|1}}{{sup|x}}v{{sub|2}}{{sup|−1}}'' = 1, unless ''z'' ≠ ''m{{sup|x}}''.
# Alice then tests ''v{{sub|1}}{{sup|x}}v{{sub|2}}{{sup|−1}}'' for equality against the values: {{glossary}}{{defn|''(m{{sup|x}}z{{sup|−1}}){{sup|i}}'' for ''i ∈ {0, 1, …, k}'';}}{{glossary end}} which are calculated by repeated multiplication of ''m{{sup|x}}z{{sup|−1}}'' (rather than exponentiating for each ''i''). If the test succeeds, Alice conjectures the relevant ''i'' to be ''s''; otherwise, she conjectures random value. Where ''z'' = ''m{{sup|x}}'', ''(m{{sup|x}}z{{sup|−1}}){{sup|i}}'' = ''v{{sub|1}}<sup>x</sup>v{{sub|2}}{{sup|−1}}'' = 1 for all ''i'', ''s'' is unrecoverable.
# Alice commits to ''i'': she picks a random ''r'' and sends ''hash(r, i)'' to Bob.
# Bob reveals ''a''.
# Alice confirms that ''a'' is the correct blind (i.e., ''v{{sub|1}}'' and ''v{{sub|2}}'' can be generated using it), then, if so, reveals ''r''. Revealing these blinds makes the exchange zero knowledge.
# Bob checks ''hash(r, i)'' = ''hash(r, s)'', proving Alice knows ''s'', hence ''z'' ≠ ''m{{sup|x}}''.

If Alice attempts to cheat at step 3 by guessing ''s'' at random, the probability of succeeding is ''1/(k + 1)''. So, if ''k = 1023'' and the protocol is conducted ten times, her chances are 1 to 2<sup>100</sup>.

== See also ==
* [[Non-repudiation]]
* [[Designated verifier signature]]
* [[Topics in cryptography]]

== References ==
{{Reflist}}

[[Category:Cryptography]]
[[Category:Digital signature schemes]]