# In "Lecture Notes on Cryptography" what does "PTM" mean?

I came across a handbook named "Lecture Notes on Cryptography" from Shafi Goldwasser and Mihir Bellare and I read their definition 3.1 about poly-time indistinguishability:

Let $X_n,Y_n$ be probability distributions on $\{0,1\}^n$ (That is, by $t\in X_n$ we mean that $t\in\{0,1\}^n$ and it is selected according to the distribution $X_n$).

We say that $\{X_n\}$ is poly-time indistinguishable from $\{Y_n\}$ if $\forall \text{PTM } A, \forall \text{polynomial } Q, \exists n_0, \text{s.t. } \forall n>n_0$,

$$\left|\Pr_{t\in X_n}(A(t)=1)-\Pr_{t\in Y_n}(A(t)=1)\right|<\frac1{Q(n)}$$

What I don't understand is what "PTM" means, can you please explain it to me?

• It means Probabilistic Turing Machine, see Section B.2.1. Jul 9, 2018 at 16:09

Let $M$ denote a probabilistic Turing machine (PTM). $M(x)$ will denote a probability space of the outcome of $M$ during its run on $x$. The statement $z\in M(x)$ indicates that $z$ was output by $M$ when running on input $x$. $\Pr[M(x) = z]$ is the probability of $z$ being the output of $M$ on input $x$ (where the probability is taken over the possible internal coin tosses made by $M$ during its execution). $M(x; y)$ will denote the outcome of $M$ on input $x$ when internal coin tosses are $y$.