On using probabilistic Turing machines to model participants in cryptographic protocols

On using probabilistic Turing machines to model participants in cryptographic protocols (Theoretical Computer Science, 2013)
Lee Klingler, Rainer Steinwandt, Dominique Unruh
[ eprint | official ]

To formalize participants in cryptographic protocols, it is common to use probabilistic Turing machines. We point out subtleties in common definitions of probabilistic Turing machines, which imply that the common cryptographic operation of uniform random sampling in a finite set {1,…,s}⊆Z is in general not possible within this model. From a technical point of view, this invalidates in particular a standard proof of the perfect zero knowledge property of the popular graph isomorphism proof system. The observed limitation appears to be relevant for other cryptographic protocol analyses as well, and we suggest one possible tweak of the definition of a probabilistic Turing machine.