  Quantum correlations provide dramatic advantage over the corresponding
classical resources in several communication tasks. However a broad class of
probabilistic theories exists that attributes greater success than quantum
theory in many of these tasks by allowing supra-quantum correlations in
`space-like' and/or `time-like' paradigms. In this letter we propose a
communication task involving three spatially separated parties where one party
(verifier) aims to verify whether the bit strings possessed by the other two
parties (terminals) are equal or not. We call this task {\it authentication
with limited communication}, the restrictions on communication being: (i) the
terminals cannot communicate with each other, but (ii) each of them can
communicate with the verifier through single use of channels with limited
capacity. Manifestly, classical resources are not sufficient for perfect
success of this task. Moreover, it is also not possible to perform this task
with certainty in several non-classical theories although they might possess
stronger `space-like' and/or `time-like' correlations. Surprisingly quantum
resources can achieve the perfect winning strategy. The proposed task thus
stands apart from all previously known communication tasks as it exhibits
quantum advantage over other non-classical strategies.
