Score:2

What do the "adversary state" and "internal coins" mean?

ru flag

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?

kelalaka avatar
in flag
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.
Score:1
cn flag

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/

YHWang avatar
ru flag
Thanks for your explanation, really helpful :)
cn flag
Turing machines are not stateless at all. The issue you're describing is solved by considering interactive turing machines, not by adding state.
Ievgeni avatar
cn flag
@Maeher -> I'm refering to these definitions of stateless/stateful -> https://www.thegeeksclan.com/stateful-and-stateless-programs/
cn flag
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.
Ievgeni avatar
cn flag
I'm not agree with you on both points (weirdness of the definition, and standard definition of Turing Machine).
Ievgeni avatar
cn flag
@YHWang You're welcome :)
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.