New answers tagged pseudo-random-function
3
take the data you want to hide and use it to seed some large but manageable number of Turing Machines with random rulesets.
You let them run for up to 𝑡 steps, and then see which ones have halted by that point. [...] Say you ran 1024 TMs; if you give each an index, and then toggle the corresponding bit depending on whether each one halts, you get a ...
19
The main fundamental issue with this approach, as with approaches that attempt to base cryptography on NP-completeness, is that the hardness you refer to is worst case hardness, and not average case hardness. In particular, the fact that the halting problem is hard merely means that for every algorithm there exists a TM $M$ for with the algorithm fails upon. ...
1
The base conversion proposed by Maarten Bodewes's answer is fine to convert some of the hash into words. But it leaves aside a stated goal:
collision resistance as high as possible considering the reduced keyspace of the passphrase
There is a well-established way to increase collision resistance and premimage resistance: re-hash the hash fingerprint with ...
7
$\newcommand{\str}[1]{\{0,1\}^{#1}}$
Roughly speaking, a pseudo-random function is to a random oracle what computational encryption scheme is to one-time pad -- the former is a computational analogue of the information theoretic latter.
For simplicity, let's fix the domain and co-domain to be the set of all $n$-bit strings. Let's consider the set $\mathcal{...
1
While not reversible, HMAC seem to be a plausible solution.
HMAC is a construct that adds a "key" to the hash digest, your program generates it with a symmetric key that's somewhat hidden in your program. You verify the player's scores by hashing the score with the key and compare the digest - this is a very typical tag comparison of message authentication ...
3
...would it help in any way with the issues discussed here?
No, not really. There's always been a gap between myriad theoretical mathematical extractor constructs and those used in commercial validated TRNGs. I honestly don't know why as that seems like an unlikely dichotomy, yet it demonstrably exists. The two should ideally converge to a common output ...
Top 50 recent answers are included
