A Linear Distinguisher and Its Application for Analyzing Privacy-Preserving Transformation Used in Verifiable (Outsourced) Computation

A distinguisher is employed by an adversary to explore the privacy property of a cryptographic primitive. If a cryptographic primitive is said to be private, there is no distinguisher algorithm that can be used by an adversary to distinguish the encodings generated by this primitive with non-negligible advantage. Recently, two privacy-preserving matrix transformations first proposed by Salinas et al. have been widely used to achieve the matrix-related verifiable (outsourced) computation in data protection. Salinas et al. proved that these transformations are private (in terms of indistinguishability). In this paper, we first propose the concept of a linear distinguisher and two constructions of the linear distinguisher algorithms. Then, we take those two matrix transformations (including Salinas et al.\$'\$s original work and Yu et al.\$'\$s modification) as example targets and analyze their privacy property when our linear distinguisher algorithms are employed by the adversaries. The results show that those transformations are not private even against passive eavesdropping.