On pg. 5 of this paper the author does a section on the "Idea of the proof" using a technique known as dimension reduction. The actual proof is on pg. 13 Section 3.1 of the same paper. However, I am already struggling with the more simpler "idea of proof" section on pg. 5. The author tries to show that attacking a particular public key encryption scheme with secret key length $N=n log q = O(n log n)$ is semantically secure against non-adaptive memory attack.
Following is my understanding:
- $s$ is the secret key vector and $h(s)$ outputs some (not all) bits of secret key $s$
- $m$ LWE samples are taken ($a_i, <a_i,s> + x_i mod q$). I think this means $m$ is an approximation of $A$.
- $a_i$ represents the $i^{th}$ row of $A$
- Mental experiment: Let matrix $A$ = $BC$
- Two observations are made
- $h(s)$ is small but $s$ still has considerable min-entropy
- matrix multiplication is a strong randomness extractor
- Putting two observations above together author says $t=Cs$ is random.
- The resulting expression now looks like $Bt+x$
I understand steps 1-4 above but I'm completely lost in 5-7. I do not understand how the two observations made in step 5 are helpful or lead to step 7. I would appreciate it if someone could shed some light on 5-7.
Also, I'm not sure how step 7 proves anything? Somehow it shows that non-adaptive attack will not work with this particular public key encryption scheme?