Modul:   MAT076  Neuchatel - St.Gallen - Zurich Seminar in Coding Theory and Cryptography

Generic Error SDP and Generic Error CVE

Vortrag von Prof. Dr. Felice Manganiello

Datum: 06.12.23  Zeit: 16.00 - 17.00  Raum:

In this talk we generalize the concept of error sets beyond those defined by a metric and use the set-theoretic difference operator to characterize when these error sets are detectable or correctable by codes. We prove the existence of a general, metric-less form of the Gilbert-Varshamov bound, and show that - like in the Hamming setting - a random code corrects a generic error set with overwhelming probability. We define the generic error SDP (GE-SDP), which is contained in the complexity class of NP-hard problems, and use its hardness to demonstrate the security of generic error CVE (GE-CVE). This is a joint work with Freeman Slaughter.