7
$\begingroup$

I've often been reading about (polynomially bounded) distinguishers in books or papers. Although by name and intuition it is somewhat clear what a distinguisher is and does, but i am asking myself whether there is a concrete formal definition. Despite the concept being used frequently, i wasn't able to find one.

Improve this question
$\endgroup$
1
10
$\begingroup$

A distinguisher is an arbitrary algorithm. In fact, we do NOT want to formalize anything about the distinguisher (except that its output is a single bit, although we don't even really need to do this). In definitions, we require that no distinguisher should succeed with non-negligible probability. So, this should hold for any algorithm.

Of course, we do specify the complexity class of the distinguisher (either probabilistic polynomial-time or non-uniform polynomial-time).

Improve this answer
$\endgroup$
4
  • $\begingroup$ I think that should be "non-negligible advantage", not probability. $\endgroup$ – Guut Boy Feb 25 '16 at 10:24
  • $\begingroup$ Well, it just depends on what you mean by "succeed". But, yes, this is the intention. $\endgroup$ – Yehuda Lindell Feb 25 '16 at 15:03
  • $\begingroup$ How would you define "succeed" to fit in this case? I can't think of a natural definition. $\endgroup$ – Guut Boy Feb 25 '16 at 15:27
  • $\begingroup$ Formally, I meant what you meant. I wouldn't define it differently... $\endgroup$ – Yehuda Lindell Feb 28 '16 at 11:13
0
$\begingroup$

If you need further reading I strongly recommend you having a look at the paper "On the Role of Definitions in and Beyond Cryptography", by Rogaway. There he explains clearly the concept of distinguisher.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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