2015/01/16 by André Luiz Barbosa, Barbosa, André Luiz
Biochemistry, Genetics and Molecular Biology · Computer Science · #94A60 (Primary) #94A62 (Secondary) #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #Cryptography and Data Security #Cryptography and Security (cs.CR) #DNA and Biological Computing #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.1501.03872
openalex publication_date 2015/01/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
This paper defines The Dead Cryptographers Society Problem - DCS (where several great cryptographers created many polynomial-time Deterministic Turing Machines (DTMs) of a specific type, ran them on their proper descriptions concatenated with some arbitrary strings, deleted them and left only the results from those running, after they died: if those DTMs only permute and sometimes invert the bits on input, is it possible to decide the language formed by such resulting strings within polynomial time?), proves some facts about its computational complexity, and discusses some possible uses on Cryptography, such as into distance keys distribution, online reverse auction and secure communication.