Stack Exchange network consists of 183 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.
I answered a very similar question here. If simplicity is the goal, I think this candidate is considerably better than the lightweight block ciphers and stream ciphers from D.W.'s answer, which are optimized for speed on embedded systems and small key size (none of that has anything to do with simplicity)
Yes, ideally I would want that (the same way that Raz's lower bound is average case). But a worst case (conjectured) lower bound would be an excellent starting point (hopefully together with some intuition about what could be a candidate hard distribution for M and x).
This paper was actually my starting point, so it's indeed relevant, but it does not solve my problem! I'm editing the question to clarify this point. Thanks :)
Interesting! This is stronger than what I knew, but unfortunately in the $S \approx n$ regime, it still only gives $T = \Omega(n^2)$, which as Joshua observed should be relatively straightforward. My hope is that a larger polynomial gap can be reasonably conjectured, even if we don't have a provable time-space tradeoff.
Of course! But I'm actually wondering whether you have to query more than all entries: because of the $C\cdot n$ space restriction, you cannot just "download the full matrix", so it's very likely that, to compute the solution $x$, you will have to re-query some entries many times. My hope is actually that a number of queries significantly larger than $n^2$ is required given this space restriction.
I would suggest to add the detailed answer to your answer for the community to see them. You are making an "extraordinary claim", and skeptism of the TCS community is expected and healthy. It would be nice to give the community the opportunity to react to your claims and ask clarifications on the subtleties of this proof. Right now, most people will expect that there is likely a subtle mistake somewhere, and this looks like a natural reaction (I did not downvote, but I would'nt believe the result until it gets accepted at a strong peer reviewed venue and experts indicate it seems to work).
Though the proof is done for a random permutation oracle, there is a standard method that applies the Borel-Cantelli lemma to extract a single "hard to invert" oracle from the distribution; see for example Impagliazzo-Rudich 1989 which introduced this technique in the context of providing an oracle separation between one way functions and public key encryption.
You are welcome. I just edited by answer to mention a very recent result that shows PPAD hardness under a much, much better assumption, the subexponential hardness of LWE, which is widely believed to hold against quantum computers. This essentially resolves the main open problem from the paper I discussed in my answer, of basing PPAD hardness on some of the most well-studied plausibly quantum-secure cryptographic assumption (the previous paper was more of a win-win result, showing that quantum attacks on PPAD hardness would provide non-trivial speedups for attacking important crypto schemes).
