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.
-
$\begingroup$ The Wikipedia article on cryptographic advantage may be of use. $\endgroup$ – Stephen Touset Aug 17 '15 at 18:47
$\begingroup$
$\endgroup$
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).
answered Aug 18 '15 at 5:41
-
$\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
$\begingroup$
$\endgroup$
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.
