?
Automata Under Effective Observation
A trapdoor cipher is a cipher whose algorithm contains some hidden structure (a trapdoor) providing the existence of a subliminal information channel. In cryptographic practice, there could be situations when a constructed cipher may contain some critical defect (a trapdoor) whose identification can significantly weaken the cryptographic strength of this cipher. In this paper, we propose and analyze one of such defects in terms of automata-theoretic approach. An operation of the cipher with this defect is modeled by a finite automaton under the so-called effective observation. The existence of effective observation for a finite automaton qualitatively reflects the presence of a trapdoor which allows one to determine the information on automaton input words by observations over the corresponding output words. We prove the criterion of finding an automaton under effective observation and specify the classes of automata under effective observation and the classes of automata for which there is no effective observation. Possible applications of the results for protecting ciphers from side channel attacks are formulated.