A NP-Complete Problem in Coding Theory with Application to Code Based Cryptography

被引：8

作者：

Berger, Thierry P. ^{[1
]}

Gueye, Cheikh Thiecoumba ^{[2
]}

Klamti, Jean Belo ^{[2
]}

机构：

[1] Univ Limoges, UMR CNRS 6172, XLIM MATHIS, 123 Ave A Thomas, F-87060 Limoges, France

[2] Univ Cheikh Anta Diop, Fac Sci & Tech, DMI, LACGAA, Dakar, Senegal

来源：

CODES, CRYPTOLOGY AND INFORMATION SECURITY, C2SI 2017 | 2017年 / 10194卷

关键词：

Code-based cryptography; Equivalence Subcode; Identification scheme; INTRACTABILITY; PROTOCOL; SCHEME;

D O I：

10.1007/978-3-319-55589-8_15

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

It is easy to determine if a given code C is a subcode of another known code D. For most of occurrences, it is easy to determine if two codes C and D are equivalent by permutation. In this paper, we show that determining if a code C is equivalent to a subcode of D is a NP-complete problem. We give also some arguments to show why this problem seems much harder to solve in practice than the Equivalence Punctured Code problem or the Punctured Code problem proposed by Wieschebrink [21]. For one application of this problem we propose an improvement of the three-pass identification scheme of Girault and discuss on its performance.

引用

页码：230 / 237

页数：8

共 25 条

[1]

[Anonymous], 1992, DISCRETE MATH

[2]

[Anonymous], 1978, DSN PROGR REPORT

[3]

Barg S., 1994, Problems of Information Transmission, V30, P209

[4]

Berger T. P, 2006, CODES LATTICES CRYPT

[5]

Berger TP, 2009, LECT NOTES COMPUT SC, V5580, P77, DOI 10.1007/978-3-642-02384-2_6

[6] How to mask the structure of codes for a cryptographic use [J].

Berger, TP ;

Loidreau, P .

DESIGNS CODES AND CRYPTOGRAPHY, 2005, 35 (01) :63-79

[7] INHERENT INTRACTABILITY OF CERTAIN CODING PROBLEMS [J].

BERLEKAMP, ER ;

MCELIECE, RJ ;

VANTILBORG, HCA .

IEEE TRANSACTIONS ON INFORMATION THEORY, 1978, 24 (03) :384-386

[8]

Cayrel P. L., 2015, INT C COD THEOR CRYP

[9]

Cayrel PL, 2011, LECT NOTES COMPUT SC, V6544, P171, DOI 10.1007/978-3-642-19574-7_12

[10]

Gaborit P., 2007, ISIT

← 1 2 3 →