  LWE-based cryptosystems are an attractive alternative to traditional ones in
the post-quantum era. To minimize the storage cost of part of its public key -
a $256 \times 640$ integer matrix, $\textbf{T}$ - a binary version of
$\textbf{T}$ has been proposed. One component of its ciphertext,
$\textbf{c}_{1}$ is computed as $\textbf{c}_{1} = \textbf{Tu}$ where
$\textbf{u}$ is an ephemeral secret. Knowing $\textbf{u}$, the plaintext can be
deduced. Given $\textbf{c}_{1}$ and $\textbf{T}$, Galbraith's challenge is to
compute $\textbf{u}$ with existing computing resources in 1 year. Our hybrid
approach guesses and removes some bits of the solution vector and maps the
problem of solving the resulting sub-instance to the Closest Vector Problem in
Lattice Theory. The lattice-based approach reduces the number of bits to be
guessed while the initial guess based on LP relaxation reduces the number of
subsequent guesses to polynomial rather than exponential in the number of
guessed bits. Further enhancements partition the set of guessed bits and use a
2-step application of LP. Given the constraint of processor cores and time, a
one-time training algorithm learns the optimal combination of partitions
yielding a success rate of 9\% - 23\% with 1000 - 100,000 cores in 1 year. This
compares favourably with earlier work that yielded 2\% success with 3000 cores.
