Better Sample -- Random Subset Sum in $2^{0.255n}$ and its Impact on Decoding Random Linear Codes

Andre Esser, Alexander May

We propose a new heuristic algorithm for solving random subset sum instances $a_1,\dots ,a_n,t\in {\mathbb{Z}}_{2^n}$, which play a crucial role in cryptographic constructions. O…