On the inherent intractability of certain coding problems (Corresp.)
From MaRDI portal
Publication:4156300
DOI10.1109/TIT.1978.1055873zbMath0377.94018WikidataQ28019921 ScholiaQ28019921MaRDI QIDQ4156300
Elwyn R. Berlekamp, Henk C. A. van Tilborg, Robert J. McEliece
Publication date: 1978
Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)
Related Items
Randomized Decoding of Gabidulin Codes Beyond the Unique Decoding Radius, On the Parameterized Complexity of Girth and Connectivity Problems on Linear Matroids, A Summary of McEliece-Type Cryptosystems and their Security, Improved Information Set Decoding for Code-Based Cryptosystems with Constrained Memory, Basics of Secrecy Coding, Covering Vectors by Spaces: Regular Matroids, Generalization of the Ball-Collision Algorithm, Quantum machine learning: a classical perspective, IND-CCA2 secure McEliece-type modification in the standard model, A Provably Secure Signature and Signcryption Scheme Using the Hardness Assumptions in Coding Theory, ON SOME CRYPTOSYSTEMS BASED ON ALGEBRAIC CODES, Sur la complexité d'un problème de codage, Moderate classical McEliece keys from quasi-centrosymmetric Goppa codes, Attack on a code-based signature scheme from QC-LDPC codes, Security enhancement method using shortened error correcting codes, On Simplifying Expressions with Mixed Boolean-Arithmetic, A new key recovery attack on a code-based signature from the Lyubashevsky framework, The return of the SDitH, On the hardness of the Lee syndrome decoding problem, Assessing and Countering Reaction Attacks Against Post-Quantum Public-Key Cryptosystems Based on QC-LDPC Codes, Entanglement Between Hash Encodings and Signatures from ID Schemes with Non-binary Challenges: A Case Study on Lightweight Code-Based Signatures, Cryptanalysis and repair of a Gabidulin code based cryptosystem from ACISP 2018, Interleaved Prange: a new generic decoder for interleaved codes, An algorithm for generalized syndrome decoding problem, Minimal codewords arising from the incidence of points and hyperplanes in projective spaces, Polynomial-time plaintext recovery attacks on the IKKR code-based cryptosystems, On the (in)security of optimized Stern-like signature schemes, Improved information set decoding algorithms over Galois ring in the Lee metric, Key-recovery fault injection attack on the classic McEliece KEM, McEliece-type encryption based on Gabidulin codes with no hidden structure, Roadmap of post-quantum cryptography standardization: side-channel attacks and countermeasures, Exploring decryption failures of BIKE: new class of weak keys and key recovery attacks, A new key recovery side-channel attack on HQC with chosen ciphertext, Ternary forking lemma and its application to the analysis of one code-based signature, The weight distribution of codes over finite chain rings, On new problems in asymmetric cryptography based on error-resistant coding, Information set decoding for Lee-metric codes using restricted balls, A code-based hybrid signcryption scheme, Key-recovery by side-channel information on the matrix-vector product in code-based cryptosystems, A side-channel attack against \textit{Classic McEliece} when loading the Goppa polynomial, A new McEliece-type cryptosystem using Gabidulin-Kronecker product codes, How to Encrypt with the LPN Problem, Cryptanalysis of Harari's identification scheme, Code-Based Cryptosystems Using Generalized Concatenated Codes, Efficient and effective quantum compiling for entanglement-based machine learning on IBM Q devices, A New Efficient Threshold Ring Signature Scheme Based on Coding Theory, McEliece Cryptosystem Implementation: Theory and Practice, A New Analysis of the McEliece Cryptosystem Based on QC-LDPC Codes, Designing a Public Key Cryptosystem Based on Quasi-cyclic Subspace Subcodes of Reed-Solomon Codes, Parameterized Intractability of Even Set and Shortest Vector Problem from Gap-ETH, A survey on proper codes, TinyKeys: a new approach to efficient multi-party computation, Multisecret-sharing schemes and bounded distance decoding of linear codes, Generalization of BJMM-ISD Using May-Ozerov Nearest Neighbor Algorithm over an Arbitrary Finite Field $$\mathbb {F}_q$$, A NP-Complete Problem in Coding Theory with Application to Code Based Cryptography, A New Dynamic Code-Based Group Signature Scheme, Parallel and Concurrent Security of the HB and HB + Protocols, On the Security of HB# against a Man-in-the-Middle Attack, Parallel and concurrent security of the HB and \(HB^{+}\) protocols, A Secure and Efficient Code-Based Signature Scheme, A CCA2 Secure Public Key Encryption Scheme Based on the McEliece Assumptions in the Standard Model, Counting faces of randomly projected polytopes when the projection radically lowers dimension, Diagnosis of Partially Observed Petri Net Based on Analytical Redundancy Relationships, On quantiles of minimal codeword weights of random linear codes over $\mathbf{F}_p$, A Zero-Knowledge Identification Scheme Based on the q-ary Syndrome Decoding Problem, Weighted counting of solutions to sparse systems of equations, Reducing Key Length of the McEliece Cryptosystem, The solution space geometry of random linear equations, Full Cryptanalysis of the Chen Identification Protocol, Decoding One Out of Many, A new identification algorithm, Ensuring Message Embedding in Wet Paper Steganography, Gallager error-correcting codes for binary asymmetric channels, Oblivious Transfer Based on the McEliece Assumptions, Towards a Concrete Security Proof of Courtois, Finiasz and Sendrier Signature Scheme, Computing coset leaders and leader codewords of binary codes, A Novel Niederreiter-like cryptosystem based on the (u|u + υ)-construction codes, A Practical Group Signature Scheme Based on Rank Metric, The security of the code-based signature scheme based on the Stern identification protocol, An inductive construction of minimal codes, Toward secure implementation of McEliece decryption, Enhanced public key security for the McEliece cryptosystem, On the security of the modified dual-Ouroboros PKE using Gabidulin codes, Cryptography from Learning Parity with Noise, Fast \(\ell _{1}\) minimization by iterative thresholding for multidimensional NMR spectroscopy, Quantum computation vs. firewalls, Low-complexity weak pseudorandom functions in \(\mathtt{AC}0[\mathtt{MOD}2\)], Factorization properties of lattices over the integers, Solving linear equations parameterized by Hamming weight, On finding a cycle basis with a shortest maximal cycle, Improved identification schemes based on error-correcting codes, Structural properties of self-dual monomial codes with application to code-based cryptography, On the ideal associated to a linear code, The hardness of approximate optima in lattices, codes, and systems of linear equations, Minimal linear codes constructed from functions, Decoding of Reed Solomon codes beyond the error-correction bound, The rank-based cryptography library, Security analysis of a cryptosystem based on subspace subcodes, Information-set decoding with hints, Performance bounds for QC-MDPC codes decoders, On the weight distribution of some minimal codes, Using low-density parity-check codes to improve the McEliece cryptosystem, ECC\(^2\): error correcting code and elliptic curve based cryptosystem, Identity based identification from algebraic coding theory, On the hardnesses of several quantum decoding problems, Computing sparse multiples of polynomials, Designing efficient dyadic operations for cryptographic applications, A code-based signature scheme from the Lyubashevsky framework, A post-quantum hybrid encryption based on QC-LDPC codes in the multi-user setting, Monotonic optimization based decoding for linear codes, Cryptanalysis of two McEliece cryptosystems based on quasi-cyclic codes, Fast simplifications for Tarski formulas based on monomial inequalities, On the equivalence of two post-quantum cryptographic families, Efficient authentication from hard learning problems, Cryptanalysis of a code-based one-time signature, A new decryption failure attack against HQC, Side channel information set decoding using iterative chunking. Plaintext recovery from the ``Classic McEliece hardware reference implementation, Sufficient conditions for monotonicity of the undetected error probability for large channel error probabilities, Statistical zero-knowledge and analysis of rank-metric zero-knowledge proofs of knowledge, Decomposition of modular codes for computing test sets and Graver basis, Inner-product functional encryption from random linear codes: trial and challenges, Code-based signatures from new proofs of knowledge for the syndrome decoding problem, Computational fuzzy extractors, Error decodable secret sharing and one-round perfectly secure message transmission for general adversary structures, New approaches to reduced-complexity decoding, Error-correcting codes and cryptography, CPA/CCA2-secure PKE with squared-exponential DFR from low-noise LPN, Cryptanalysis of a code-based full-time signature, On covering problems of codes, Reproducible families of codes and cryptographic applications, Solving systems of linear Boolean equations with noisy right-hand sides over the reals, Efficient computation outsourcing for inverting a class of homomorphic functions, A new secret sharing scheme, A code-based group signature scheme, Secure and practical randomized stream ciphers based on Reed-Solomon codes, DAGS: key encapsulation using dyadic GS codes, The complexity of the weight problem for permutation and matrix groups., Boolean autoencoders and hypercube clustering complexity, Rigid linear binary codes, Practical entanglement distillation scheme using recurrence method and quantum low density parity check codes, Monadic second-order model-checking on decomposable matroids, Minimal linear codes arising from blocking sets, A post-quantum UC-commitment scheme in the global random oracle model from code-based assumptions, Differential Power Analysis of a McEliece Cryptosystem, A modified Dual-Ouroboros public-key encryption using Gabidulin codes, An improved algorithm for learning sparse parities in the presence of noise, A protocol for provably secure authentication of a tiny entity to a high performance computing one, Characteristic vector and weight distribution of a linear code, A method for efficiently computing the number of codewords of fixed weights in linear codes, Masking Large Keys in Hardware: A Masked Implementation of McEliece, Semantic security for the McEliece cryptosystem without random oracles, On the subgroup distance problem., Cryptanalysis of the Wu-Dawson public key cryptosystem, A branch-cut-and-price algorithm for optimal decoding in digital communication systems, Separating models of learning with faulty teachers, Properties of syndrome distribution for blind reconstruction of cyclic codes, Tight and optimal reductions for signatures based on average trapdoor preimage sampleable functions and applications to code-based signatures, Message-recovery laser fault injection attack on the \textit{classic McEliece} cryptosystem, Cryptanalysis of an E0-like combiner with memory, On the number of minimal codewords in codes generated by the adjacency matrix of a graph, Key masking using biometry, Cryptography with Auxiliary Input and Trapdoor from Constant-Noise LPN, Cryptography with constant input locality, On quaternary Goppa codes, Goppa codes over the \(p\)-adic integers and integers modulo \(p^e\), Classification of Griesmer codes and dual transform, Computer algebra tales on Goppa codes and McEliece cryptography, Computing sharp recovery structures for locally recoverable codes, A Survey of the Game “Lights Out!”, Lights Out on graphs, New rank codes based encryption scheme using partial circulant matrices, A gapless code-based hash proof system based on RQC and its applications, A decoding method of an n length binary BCH code through (n + 1)n length binary cyclic code, Cryptanalysis of LEDAcrypt, A new post-quantum multivariate polynomial public key encapsulation algorithm, On the covering radius of cyclic linear codes and arithmetic codes, Hamming codes for wet paper steganography, On the design and security of Lee metric McEliece cryptosystems, Classical and quantum algorithms for generic syndrome decoding problems and applications to the Lee metric
