A modification proposal for the reconciliation mechanism of the key exchange algorithm NewHope

V Gayoso Martínez, L Hernández Encinas, A Martín Muñoz
Logic Journal of the IGPL, 2022;, jzac011

The latest advances in quantum computing forced the National Institute of Standards and Technology (NIST) to launch an initiative for selecting quantum-resistant cryptographic algorithms. One of the best-known proposals is NewHope, an algorithm that was initially designed as a key exchange algorithm. In its original design, NewHope presented a reconciliation mechanism that is complex and represents an entry barrier for potential implementers. This contribution presents equivalent schemes in one, two and three dimensions, which allow anyone to make the transition to the 4D NewHope algorithm easier to undertake. In addition to that, the effect of modifying some of the parameters associated to NewHope’s reconciliation mechanism is studied, which has allowed us to propose different sets of parameters that could increase the security of NewHope implementations.


This work was supported in part by the Spanish State Research Agency (AEI) of the Ministry of Science and Innovation (MCIN), project P2QProMeTe (PID2020-112586RB-I00/AEI/10.13039/501100011033), co-funded by the European Regional Development Fund (ERDF, EU) and in part by ORACLE Project, with reference PCI2020-120691-2, funded by MCIN/AEI/10.13039/501100011033 and European Union ‘NextGenerationEU/PRTR’. Víctor Gayoso Martínez would like to thank CSIC Project CASP2/201850E114 for its support.