Editing Undeniable signature (section)

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