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.
2 Answers
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).
-
$\begingroup$ I think that should be "non-negligible advantage", not probability. $\endgroup$– Guut BoyFeb 25, 2016 at 10:24
-
$\begingroup$ Well, it just depends on what you mean by "succeed". But, yes, this is the intention. $\endgroup$ Feb 25, 2016 at 15:03
-
$\begingroup$ How would you define "succeed" to fit in this case? I can't think of a natural definition. $\endgroup$– Guut BoyFeb 25, 2016 at 15:27
-
$\begingroup$ Formally, I meant what you meant. I wouldn't define it differently... $\endgroup$ Feb 28, 2016 at 11:13
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.