Charles E. Schmidt College of Science

Crypto Café

Speaker: Paolo Santini, Universita Polotecnica Delle Marche, Italy

Title: A New Formulation of the Linear Equivalence Problem and Shorter LESS Signatures

Abstract: The problem of determining whether two linear codes are equivalent is called Code Equivalence Problem. When codes are endowed with the Hamming metric (which is the most studied case), the equivalence is mainly considered with respect to monomial transformations (permutations with scaling factors) and the problem is known as the Linear Equivalence Problem (LEP). Code equivalence can be described as a transitive, non-commutative group action and, as such, finds a natural application in cryptography: for example, it is possible to design zero-knowledge proofs, and hence signature schemes. In recent works, it has been shown that LEP can be reformulated using notions such as information sets (arguably, ubiquitous objects in coding theory) and canonical forms. This unlocks some new features, such as the possibility of communicating the equivalence map in a very compact way (which leads to much shorter signatures), as well as opening new attack avenues. In this talk, we recall the basics of code equivalence and then focus on these recent results, aiming to describe how they can be applied to boost the performance of cryptographic schemes.

Zoom (click here)

Meeting ID: 878 9825 0483 Passcode: gHJF6g

All are cordially invited.