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 ...
- 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 "...
- 21.2k
Only top scored, non community-wiki answers of a minimum length are eligible