- This event has passed.
Paolo Santini — Università Politecnica delle Marche
November 29, 2021 @ 6:15 am - 7:15 am EST
Title: The code equivalence problem and its applications to cryptography
Abstract: The code equivalence problem (CEP) asks, given two linear codes, to find an isometry which maps a code into the other. In this talk we focus on the Hamming metric case, and consider two types of isometries: permutations and monomials. Despite the lack of formal hardness results (e.g., an NP-hardness proof) and the existence of algorithms that efficiently solve CEP in several cases, there are instances which are believed to be hard (namely, permutations of weakly self-dual codes and monomial transformations of codes defined over moderately large finite fields).
In this talk we are going to recall the state-of-the-art solvers for several classes of CEP, focusing on those that are believed to be hard, and then we will see a practical application of CEP in the context of cryptographic identification schemes and digital signatures.