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?

  • 1
    $\begingroup$ It means Probabilistic Turing Machine, see Section B.2.1. $\endgroup$
    – hakoja
    Commented Jul 9, 2018 at 16:09

1 Answer 1


As pointed out by hakoja in the comments:

It means Probabilistic Turing Machine, see Section B.2.1.

where the following is written (emphasis mine, this is the full section B.2.1):

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.