We construct a cryptographically-motivated PRNG whose security reduces entirely to the conjectured one-wayness of the Collatz function — following the Håstad–Impagliazzo–Levin–Luby framework step by step, with a complete, auditable security proof under that assumption.
The 3x+1 problem — repeatedly halving even numbers and applying (3x+1)/2 to odd ones — has an unpredictable trajectory that Vuckovac proposed as a one-way function candidate: any algorithm that inverts it without conditional branching must enumerate an exponential number of execution paths. We take that as our security assumption and build the standard HILL pipeline on top of it.
The Collatz one-way function. For a 512-bit input x and 256 iterations, compute the Collatz sequence, record the parity of each step as a path string, split the input and final state into halves, and XOR everything together — producing a 256-bit output where every input bit affects the result.
A Goldreich–Levin hardcore bit. Applying the standard GL construction to the Collatz OWF yields a single bit — the inner product of the input with a random string — that's provably as hard to predict as inverting the function itself.
A one-bit generator, then iteration. That hardcore bit becomes a PRG with stretch 1. Iterating it — feeding each output state back in as the next seed — extends the stretch to any polynomial length k, following the standard HILL construction.
A full security reduction. The main theorem shows that any efficient distinguisher for the generator's output can be converted into an algorithm that inverts the Collatz function — so breaking the PRNG is exactly as hard as breaking the underlying assumption.
Vuckovac's argument shows that any branch-free algorithm implementing the Collatz map must enumerate a table of 2r execution paths — without conditional branching, there's no way to tell which of 2256 composite functions produced a given output. We adopt this as our cryptographic foundation, in the same spirit as the RSA or discrete-log assumptions.
The construction runs this map for r = 256 iterations on a 512-bit input, XORs the input halves with the final-state halves and the recorded parity path, and outputs a 256-bit result — deterministic, fully specified, and dependent on every input bit.
This isn't a mockup — it's a JavaScript port of the same C++ reference implementation below: the Collatz OWF, the Goldreich–Levin hardcore bit, and the iterated PRNG, run step for step. Nothing here is sent anywhere; it all runs client-side, in this page.
The construction was instantiated with n = 512, r = 256 iterations, seeded from /dev/urandom, and evaluated with basic statistical tests plus the full NIST Statistical Test Suite (STS 2.1.2) on 80 bitstreams of 106 bits each — 8 × 107 bits total.
| Basic Statistical Test | Value | Result |
|---|---|---|
| Monobit (bit frequency) | 49.9927% ones | PASS |
| Shannon entropy | 7.999981 bits/byte | PASS |
| Runs test (Z-score) | 0.3635 | PASS |
| Lag-1 autocorrelation | −0.006380 | PASS |
| NIST SP 800-22 Category | Proportion | Result |
|---|---|---|
| Frequency & Block Frequency | 80/80 | PASS |
| Cumulative Sums (fwd/back) | 80/80 | PASS |
| Runs & Longest Run | 79/80 | PASS |
| Non-overlapping Templates (148 variants) | ≥ 76/80 | PASS |
| Random Excursions (8 states) | ≥ 52/53 | PASS |
| Serial, Linear Complexity, Universal, Approx. Entropy | 77–80/80 | PASS |
| Total — all 188 sub-tests | PASS |
Bit balance across all 80 streams: 498,850 to 501,150 ones per 106 bits — a standard deviation of ≈450, consistent with a fair-coin sequence.
Statistical test suites confirm the output looks random. They say nothing about whether the Collatz function is actually hard to invert against every adversary — which is what cryptographic security actually requires.
Vuckovac's theorem establishes that branch-free algorithms need exponential time to invert the Collatz iteration. That's a statement about one class of algorithm, not a proof against every possible adversary.
This is analogous to early RSA: the hardness of factoring was — and still is — an assumption, not a proven fact. The Collatz branching argument offers structural and empirical evidence, which may be enough for exploratory work. It is not yet enough for production cryptography, and we say so plainly rather than overstate it.
Five C++ modules mirror the construction directly: the Collatz OWF, the Goldreich–Levin hardcore bit, the one-bit PRG, the iterated PRNG, and a CLI driver — each using fixed-width 512-bit arithmetic. The live demo above is a faithful JavaScript port of this same reference code.
Hardness figures are under the Collatz Branching Hardness Assumption only — see the honest caveat above.
All 5 C++ modules, headers, and CMakeLists.txt — builds with CMake + a C++17 compiler.
Reference source, the security proof, and the empirical evaluation scripts are available on request.