Paper 2016/1039

A Fiat-Shamir Implementation Note

Simon Cogliani, Rémi Géraud, and David Naccache

Abstract

In the Micali-Shamir paper improving the efficiency of the original Fiat-Shamir protocol, the authors state that "(...) not all of the $v_i$'s will be quadratic residues mod $n$. We overcome this technical difficulty with an appropriate perturbation technique (...)" This perturbation technique is made more explicit in the associated patent application: "Each entity is allowed to modify the standard $v_j$ which are QNRs. A particularly simple way to achieve this is to pick a modulus $n=pq$ where $p=3 \bmod 8$ and $q=7 \bmod 8$, since then exactly one of $v_j,-v_j,2v_j,-2v_j$ is a QR mod $n$ for any $v_j$. The appropriate variant of each $v_j$ can be (...) deduced by the verifier himself during the verification of given signatures." In this short note we clarify the way in which the verifier can infer by himself the appropriate variant of each $v_j$ during verification.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Preprint. MINOR revision.
Keywords
fiat-shamirarithmetics
Contact author(s)
remi geraud @ ens fr
History
2016-11-03: received
Short URL
https://ia.cr/2016/1039
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/1039,
      author = {Simon Cogliani and Rémi Géraud and David Naccache},
      title = {A Fiat-Shamir Implementation Note},
      howpublished = {Cryptology ePrint Archive, Paper 2016/1039},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/1039}},
      url = {https://eprint.iacr.org/2016/1039}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.