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.

Intro
A memoryless Meet-in-the-Middle
Folklore Algorithm
The Representation Technique
The memoryless BCJ Algorithm
Discrete Logarithms
Use of Carry Bits
Increase the Weight
The new Algorithm
Updated low-weight DLP Landscape
Achieving the Square-Root Bound
Back to Subset Sum
Nested Rhos