Security Against Subversion in a Multi-surveillant Setting

Mass surveillance attracts much of attentions nowadays. Evidences showed that some intelligence agencies try to monitor public’s communication by unconventional methods, for example, providing users subverted cryptographic algorithms and compelling them to use. To address this new situation, researchers proposed a series of formal analyses and security definitions. However, current researches are restrictive as they only considered a single surveillant setting. In reality, there may exist multiple surveillants for different governments or manufacturers. This paper initializes the analysis of security against subversion in a multi-surveillant setting. We consider the case where users could only use subverted algorithms from different sources to achieve a subliminal communication. We introduce a new security notion that the transmission of a real message is “undetectable”, which means all surveillants either think the users execute the subverted algorithms honestly to transmit an innocuous message, or consider users are using non-subverted algorithms. We present a concrete design and prove that it satisfies our security definition.