patternMinor
Is it possible to have high compression but low predictability?
Viewed 0 times
predictabilitylowcompressionbuthighpossiblehave
Problem
Can you have a process that generates a binary sequence with high compression rate (low entropy) but impossible to predict next symbol?
'impossible to predict' - sequence cannot be predicted theoretically. But I was also asking about the real life example (no polynomial algorithm).
'impossible to predict' - sequence cannot be predicted theoretically. But I was also asking about the real life example (no polynomial algorithm).
Solution
Yes. A cryptographic stream cipher can generate an incredibly long string (e.g. ChaCha20 can generate $256 \times 2^{128}$ bits) from a single small key (e.g. 256 bits).
If you do not know the key that was used this stream is impossible to predict.
If you do not know the key that was used this stream is impossible to predict.
Context
StackExchange Computer Science Q#114673, answer score: 3
Revisions (0)
No revisions yet.