Generic Error SDP and Generic Error CVE

Felice Manganiello; Freeman Slaughter

Paper 2023/717

Generic Error SDP and Generic Error CVE

Felice Manganiello

, Clemson University

Freeman Slaughter, Clemson University

Abstract

This paper introduces a new family of CVE schemes built from generic errors (GE-CVE) and identifies a vulnerability therein. To introduce the problem, 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 GE-CVE. We prove that these schemes are complete, sound, and zero-knowledge. Finally, we identify a vulnerability of the GE-SDP for codes defined over large extension fields and without a very high rate. We show that certain GE-CVE parameters suffer from this vulnerability, notably the restricted CVE scheme.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Preprint.
Keywords: Code-based cryptography Syndrome Decoding Problem generic error set zero-knowledge scheme CVE
Contact author(s): manganm @ clemson edu
fslaugh @ g clemson edu
History: 2023-05-22: approved; 2023-05-18: received; See all versions
Short URL: https://ia.cr/2023/717
License: CC BY

BibTeX

@misc{cryptoeprint:2023/717,
      author = {Felice Manganiello and Freeman Slaughter},
      title = {Generic Error SDP and Generic Error CVE},
      howpublished = {Cryptology ePrint Archive, Paper 2023/717},
      year = {2023},
      note = {\url{https://eprint.iacr.org/2023/717}},
      url = {https://eprint.iacr.org/2023/717}
}