2016/09/06 by Stefan Rass, Stefan Raß, Rass, Stefan · 1 voice
Biochemistry, Genetics and Molecular Biology · Computer Science · #68Q15 #94A60 #Algorithms and Data Compression #Computational Complexity (cs.CC) #DNA and Biological Computing #FOS: Computer and information sciences #cs.CC #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1609.01575
openalex publication_date 2016/09/06 · arxiv published 2016/09/06 · openalex created_date 2016/09/16 · arxiv updated 2023/07/18 · openalex updated_date 2026/07/28
This note is an attempt to unconditionally prove the existence of weak one way functions (OWF). Starting from a provably intractable decision problem LD (whose existence is nonconstructively assured from the well-known discrete time-hierarchy theorem from complexity theory), we construct another intractable decision problem L⊆ \0,1\^* that has its words scattered across \0,1\^ℓ at a relative frequency p(ℓ), for which upper and lower bounds can be worked out. The value p(ℓ) is computed from the density of the language within \0,1\^ℓ divided by the total word count 2^ℓ. It corresponds to the probability of retrieving a yes-instance of a decision problem upon a uniformly random draw from \0,1\^ℓ. The trick to find a language with known bounds on p(ℓ) relies on switching from LD to L0:=LD∩ L', where L' is an easy-to-decide language with a known density across \0,1\^*. In defining L' properly (and upon a suitable Gödel numbering), the hardness of deciding LD∩ L' is inherited from LD, while its density is controlled by that of L'. The lower and upper approximation of p(ℓ) then let us construct an explicit threshold function (as in random graph theory) that can be used to efficiently and intentionally sample yes- or no-instances of the decision problem (language) L0 (however, without any auxiliary information that could ease the decision like a polynomial witness). In turn, this allows to construct a weak OWF that encodes a bit string w∈\0,1\^* by efficiently (in polynomial time) emitting a sequence of randomly constructed intractable decision problems, whose answers correspond to the preimage w.