On the Undecidability of Quasi-Private-Key-Encryption Statistical Indistinguishability

This paper studies decision problem of secure private-key encryption schemes. That is, whether there is a program to decide whether an arbitrary triple of probabilistic Turing machines (PTMs) (G, E, D) is a secure private-key encryption scheme or not. Main results of this paper contain: 1. We study the halting problem for PTMs. By providing a full proof without applying undecidability of known halting problem for deterministic Turing machines, we prove that the halting problem for PTMs is undecidable. 2. We present the notion of quasi-private-key- encryption statistical indistinguishability for triples of PTMs (G, E, D). That (G, E, D) is quasi-private-key- encryption statistically indistinguishable implies that if (G, E, D) is a private-key encryption scheme indeed, then its security satisfies statistical indistinguishability. However, we prove there is no algorithm to decide whether (G, E, D) is quasi-private-key-encryption statistically indistinguishable or not.