I'd like to invite cryptanalysis of a minimal permutation proposed as a sequential delay function:
```c
uint64_t slow_hash_64(uint64_t seed, uint64_t n) {
while (n--) {
seed *= 0xD1342543DE82EF95;
seed ^= seed >> 32;
}
return seed;
}
```
The intended security property is **sequential hardness**: computing fⁿ(x) should require Ω(n) work, with no shortcut significantly faster than iterating.
### Why shortcuts seem unlikely
Pure multiplication over ℤ/2⁶⁴ℤ admits O(log n) evaluation via fast exponentiation. The XOR-shift breaks the pure ring structure: `seed ^= seed >> 32` mixes high and low halves in a way that is linear over GF(2)⁶⁴ but nonlinear over ℤ/2⁶⁴ℤ. The composition of these two operations across iterations should prevent reduction to either structure alone.
This resembles SplitMix64's mixing step, but used iteratively as a delay function rather than as a one-shot finalizer. The constant `0xD1342543DE82EF95` is from SplitMix's literature.
### Open questions
1. **Algebraic decomposition**: Can the MUL-then-XOR-shift composition be represented in a unified algebraic framework (e.g., affine over some extension, or as a matrix in a mixed representation)? The 64-bit state is small enough for structural analysis.
2. **Iterated structure**: Does repeating the same operation n times introduce periodicity or invariant subspaces that don't exist in a single application? SplitMix uses this step once; using it iteratively may expose different weaknesses.
3. **Constant sensitivity**: Is `0xD1342543DE82EF95` specifically safe for iterated use, or could other constants from the same family create short cycles or fixed points under iteration?
4. **PRF vs. sequential hardness**: Even if this is a strong PRF per iteration, does that imply anything about the hardness of fⁿ? Are there known counterexamples where a secure permutation admits efficient iterated evaluation?
5. **Relation to PCG/SplitMix literature**: These generators have been extensively analyzed for statistical quality, but I'm unaware of sequential hardness analysis. Has anyone studied iterated SplitMix-style mixing as a VDF candidate?
I'm not claiming security — I'm asking what's wrong with it. References to cryptanalysis of similar iterated MUL-XOR-shift constructions would be especially appreciated.