Is code equivalence easy to decide?
From MaRDI portal
Publication:4371902
DOI10.1109/18.623157zbMath0884.94025MaRDI QIDQ4371902
Publication date: 13 April 1998
Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/5c1624d163a4fb426f8dbf4929628031a1575c08
NP-complete; interactive proofs; code equivalence; graph isomorphism problem; equivalent linear codes
68Q25: Analysis of algorithms and problem complexity
94B05: Linear codes (general theory)
05C60: Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
Related Items
Unnamed Item, Unnamed Item, Minimum Circuit Size, Graph Isomorphism, and Related Problems, Computing an Invariant of a Linear Code, LESS is More: Code-Based Signatures Without Syndromes, Algorithms for Group Isomorphism via Group Extensions and Cohomology, A NP-Complete Problem in Coding Theory with Application to Code Based Cryptography, On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials I: Tensor Isomorphism-Completeness, Tensor Codes and Their Invariants, On the computational hardness of the code equivalence problem in cryptography, A new algorithm for equivalence of cyclic codes and its applications, Galois hulls of constacyclic codes over finite fields, Semantic security for the McEliece cryptosystem without random oracles, Hulls of cyclic and negacyclic codes over finite fields, Hermitian hulls of constacyclic codes and their applications to quantum codes, Computing normalisers of intransitive groups, General linear group action on tensors: a candidate for post-quantum cryptography, On equivalence of cyclic codes, generalization of a quasi-twisted search algorithm, and new linear codes, Determining whether a given cryptographic function is a permutation of another given cryptographic function -- a problem in intellectual property, On isomorphism testing of groups with normal Hall subgroups, Hulls of cyclic serial codes over a finite chain ring, New binary and ternary quasi-cyclic codes with good properties, A generalization of cyclic code equivalence algorithm to constacyclic codes, Quantum algorithms for algebraic problems, Minimum Circuit Size, Graph Isomorphism, and Related Problems, A Provably Secure Signature and Signcryption Scheme Using the Hardness Assumptions in Coding Theory, Zero-Knowledge Interactive Proof Systems for New Lattice Problems, On a Gröbner bases structure associated to linear codes
