Code-based Cryptography with Restricted Errors

Code-based Cryptography with Restricted Errors

Cybersecurity Seminars Online seminar
Monday, 26 April 2021
5 pm - 6 pm (AEST)

The general Syndrome Decoding Problem (SDP) is the main foundation of code-based cryptography. We introduce a variant of the SDP, in which the entries of the sought-after error vector are defined over a subset of the finite field over which the parity check matrix and the syndrome are defined. We call this new problem R-SDP (Restricted Syndrome Decoding Problem) and prove that it is NP-complete via a reduction from the classical SDP. We then derive some coding theoretic results for this restricted error setting, including the restricted minimum distance of a randomly chosen linear code. In the end we consider a specific setting for this new problem, in which the error vector has full support, and assess the complexity of solving random instances of R-SDP.

Finally, to show a concrete application, we replace SDP with R-SDP in the CVE zero-knowledge code-based identification scheme. This can then be used to create a digital signature. In the end of the talk we will show some limitations of the CVE scheme and all its variants in the construction of digital signatures.

About the speaker

Anna-Lena Horlemann
Associate Professor, University of St. Gallen

Anna-Lena Horlemann-Trautmann received the Ph.D. degree in mathematics from the University of Zurich, Switzerland, in 2013. She then spent 1.5 years as a research fellow at the Department of Electrical and Electronic Engineering at the University of Melbourne and at the Department of Electrical and Computer Systems Engineering at Monash University, Australia. She was a Postdoctoral fellow at the EPF Lausanne, Switzerland, from 2015 until 2017. Afterwards she was an assistant professor for mathematics and information technology at the University of St. Gallen in Switzerland, before she recently joint the School of Computer Science as an associate professor at the same university.


Event contact

Share this event