3 votes

Learning the LWE secret with advice

This would be very bad. Assuming that you're calculating $\mod q$ for some $q$, the learner can recover $s$ with at most $3n$ queries even while ignoring the samples. I'll assume that $q$ is even, but ...
Daniel S's user avatar
  • 21.9k
1 vote

How to prove that an algorithm is the time optimal algorithm for implementing a problem?

Since you stated interest in how to prove an algorithm is time-optimal, a telescopic summary: This requires proving lower bounds on complexity, which is very difficult in general. I will use "...
kodlu's user avatar
  • 21.2k

Only top scored, non community-wiki answers of a minimum length are eligible