eprint.iacr.orgpaperA Memory-efficient Implementation of Wiedemann XL
A Memory-efficient Implementation of Wiedemann XL is an ePrint paper (2026/2641) giving the first efficient on-the-fly implementation of XL with block Wiedemann for the multivariate quadratic problem. It builds on the CCNY SSE implementation, removes column-index tables, and computes column indices with O(n^2) instead of O(n^3) look-ups. It runs in comparable BW1 time with up to five times less memory, and an AVX2 port covers F256, the main field of UOV.
TL;DR Presents an on-the-fly XL/block Wiedemann MQ solver that matches the running time of the prior implementation with up to 5x less memory.
Organisations named here
- block Wiedemann
- CCNY
- Macaulay matrix
- MQOM
- multivariate quadratic problem
- XL
Technologies named here
- XL with block Wiedemann
- MQOM
- CCNY implementation by Cheng, Chou, Niederhagen, and Yang
- SNOVA
- MAYO
- UOV
- NIST
Related in other
eprint.iacr.orgpaperRerandomizable Garbling for Arithmetic Circuits
aseemshrey.inarticle