Low Weight Discrete Logarithms and Subset Sum in - with Polynomial Memory

Explore a groundbreaking algorithm for solving low-weight discrete logarithms and subset sum problems in cryptography. Delve into the presentation by Andre Esser and Alexander May at Eurocrypt 2020, which introduces a novel approach achieving a time complexity of 2^{0.65n} while maintaining polynomial memory usage. Learn about the memoryless Meet-in-the-Middle technique, the Representation Technique, and the memoryless BCJ Algorithm. Discover how the use of carry bits and weight increase contribute to the new algorithm's efficiency. Examine the updated landscape of low-weight Discrete Logarithm Problems and understand how this method approaches the square-root bound. Finally, investigate the application of these concepts to Subset Sum problems and the implementation of nested Rhos.