3 ms·
It says you either have to use exponential time or quadratic storage. Schemes based on high memory requirements have actually been sought for a while, since (ap
by thomasahle 11y ago
It says you either have to use exponential time or quadratic storage. Schemes based on high memory requirements have actually been sought for a while, since (apparently) memory is considered less scalable than computation.
- swordswinger12 11y agoNo, I mean your original comment is inaccurate. The paper presents a time-space lower bound for parity learning, but the encryption scheme based on this result is only 'unconditionally secure' in a model where the adversary is restricted to having at most (n^2)/25 bits of storage. This isn't a general-purpose unconditionally secure encryption scheme, which is what your original comment implied.