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.

$\endgroup$
1

2 Answers 2

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).

$\endgroup$
4
  • $\begingroup$ I think that should be "non-negligible advantage", not probability. $\endgroup$
    – Guut Boy
    Feb 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 Boy
    Feb 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
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.

$\endgroup$

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.