Cryptography Asked by Steven Yue on October 24, 2021
It seems like that the construction of the LWE problem: $As + e = b$ resembles how neural nets work: $Ax + b = y$.
In LWE, we are given the problem instance $A$, and the product with errors $b$ and are challenged to produce the secret vector $s$. Is it similar to the problem in ML where we are given the coefficient matrix $A$ and the expected label $y$, can we produce a valid sample $x$?
Also, I’m wondering whether techniques we use in ML such as backpropagation can be applied to LWE as well?
This seems quite unlikely. A recent paper has suggested a Continuous LWE problem. This problem is structurally quite similar to the standard LWE problem --- it has (quantum) worst-case to average-case reductions to hard lattice problems.
In that paper they also show that a standard problem in ML (learning mixtures of Gaussians) reduces to the continuous LWE problem. This gives you a more concrete ML problem to attack. If you could learn mixtures of Gaussians, you could reduce this to solving continuous LWE, which you could then reduce to solving worst-case lattice problems. If you can solve worst-case lattice problems, then we do not believe LWE is hard anymore.
There have also been some results showing that a broad class of learning algorithms (ones which fit into the "Statistical Query model") cannot solve certain learning problems. The LPN problem (which you can vaguely think of as "LWE with $q = 2$) has such bounds (see for example this problem). I don't know if specific ML techniques such as backpropagation fit into the SQ model though.
Answered by Mark on October 24, 2021
Well, they can be applied, but are probably unlikely to succeed, otherwise you would have a breakthrough, so maybe go for it if you have a concrete idea you can implement.
The reason is this kind of discrete problem (lattice or finite field) is chosen to be very difficult on average, and many hardness results tied to famous problems usually exist.
The ML problems are non adversarial in nature, so apples and oranges, really.
Answered by kodlu on October 24, 2021
Get help from others!
Recent Answers
Recent Questions
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP