Editing Undeniable signature (section)

== 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>.