Seminario: "Expected Number of Solutions to the Permuted Kernel Problem" - Carlo Sanna

Talk at the Genova-Torino-Milano (GTM) Seminars, a series of seminars covering results on Commutative Algebra and Algebraic Geometry, official website: https://sites.google.com/view/ag-genova/seminar/gtm

"Expected Number of Solutions to the Permuted Kernel Problem"

Carlo Sanna - Politecnico di Torino

February 6, 2026 - 9:00 am
Room 509 - Dipartimento di Matematica
Università di Genova, Via Dodecaneso, 35

Abstract: The Permuted Kernel Problem (PKP) is a simple-to-state but hard-to-solve problem in combinatorial linear algebra: given an m x n matrix A and an n x 1 vector b over a finite field, find (if it exists) an n x n permutation matrix P such that APb = 0. This talk explains why the PKP is of interest to cryptographers and shows some results on the expected number of solutions to a "random" instance of the PKP. No prior knowledge of cryptography is required.