I was reading papers about searchable symmetric encryption these days and in the security definition part the author mentioned:

where state is a polynomially bounded string that captures A1’s state, and the probability is taken over the internal coins of Keygen, A, and the underlying BuildIndex algorithm.

So what exactly do the "state" and "internal coins" mean?

  • $\begingroup$ Welcome to Cryptograpy.SE. A good question should link to the paper, too. The internal state is clear; the algorithm has memory, if you freeze the algorithm and write them somewhere, you can let it continue later - stream ciphers?. The internal coin is more clear; it has a good random number generator not exposed to the outside. $\endgroup$
    – kelalaka
    Commented Jun 8, 2021 at 11:03

1 Answer 1


In general, when we modelise attack, we have to consider more than one phase.

Problem : In theoretical computer science, we use Turing machines $\mathcal{A}$ (eventually with oracles), which are "one-phase" (takes a string as input, and output another string).

Then to consider this, people choose to use more than one Turing Machine for example $\mathcal{A}_1$, $\mathcal{A}_2$. Thus $\mathcal{A}_1$ will represent the adversary during the first phase, and $\mathcal{A}_2$ during the second phase.

But, it could happen that $\mathcal{A}_2$ needs to use information computed during the first phase.

That's why we use a string (ponyomialy bound, because $\mathcal{A}_1$ is considered as a polynomial-Time Turing Machine), which is output by $\mathcal{A}_1$, and takes as input by $\mathcal{A}_2$. This string is called the state.

About the internal coins, it's just because the $\mathcal{A}$'s are probabilistic Turing machines, thus it uses random coins. (internal means : it doesn't depend of the input).

ps : Sometime, people want to avoid to use more than one Turing-machine, and consider stateful Turing Machine (opposite to the traditional stateless Turing machines).

pps : In this context, stateless doesn't mean there in only one state in the Turing Machine, but it means that each execution is independent of the previous ones, and thus depend only of the inputs, and the random coins. https://www.thegeeksclan.com/stateful-and-stateless-programs/

  • 1
    $\begingroup$ Thanks for your explanation, really helpful :) $\endgroup$
    – YHWang
    Commented Jun 11, 2021 at 2:30
  • $\begingroup$ Turing machines are not stateless at all. The issue you're describing is solved by considering interactive turing machines, not by adding state. $\endgroup$
    – Maeher
    Commented Jun 11, 2021 at 6:36
  • $\begingroup$ @Maeher -> I'm refering to these definitions of stateless/stateful -> thegeeksclan.com/stateful-and-stateless-programs $\endgroup$
    – Ievgeni
    Commented Jun 11, 2021 at 8:25
  • $\begingroup$ Well, that's a somewhat weird definition, but also a Turing machine is not stateless according to that definition. First of all a Turing machine explicitly maintains a state while operating. Second of all, a Turing machine can store arbitrary intermediate data on it's tape and therefore certainly does not fall into the "stateless" category "defined" on that random website. $\endgroup$
    – Maeher
    Commented Jun 11, 2021 at 8:42
  • $\begingroup$ I'm not agree with you on both points (weirdness of the definition, and standard definition of Turing Machine). $\endgroup$
    – Ievgeni
    Commented Jun 11, 2021 at 11:03

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.