Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Designs, Codes and Cryptography
Erschienen in: Designs, Codes and Cryptography 2-3/2019

21.12.2018

Identifying an unknown code by partial Gaussian elimination

verfasst von: Kevin Carrier, Jean-Pierre Tillich

Erschienen in: Designs, Codes and Cryptography | Ausgabe 2-3/2019

Einloggen, um Zugang zu erhalten

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

We consider in this paper the problem of reconstructing a linear code from a set of noisy codewords. We revisit the algorithms that have been devised for solving this problem and show that by generalizing and mixing two approaches that have been proposed in this setting, we obtain a significantly better algorithm. It basically consists in setting up a matrix whose rows are the noisy codewords, then running a partial Gaussian algorithm on it and detecting a small set of columns outside the echelon part of the matrix whose sum is sparse. We view the last task of the algorithm as an instance of the well known close neighbors search problem and we use an algorithm due to Dubiner to solve it more efficiently than the naive projection method which is generally invoked in this case. We analyze the complexity of our algorithm by focusing on an important practical case, namely when the code is an LDPC code. In doing so, we also obtain a result of independent interest, namely a tight upper-bound on the expected weight distribution of the dual of an LDPC code in a form that allows to derive an asymptotic formula.
Vorheriger Artikel A new lower bound for the smallest complete (k, n)-arc in
Fußnoten
1
Gaussian elimination is actually performed there with column operations, but this is not essential: the complexity is actually of the same order.
 
Literatur
1.
Andoni A., Indyk P.: Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions. Commun. ACM 51(1), 117–122 (2008).CrossRef
2.
Andoni A., Indyk P.: Nearest neighbors in high-dimensional spaces. In: Goodman J.E., O’Rourke J., Tóth C.D. (eds.) Handbook of Discrete and Computational Geometry, 3rd edn, ch. 43. CRC Press, Boca Ratin (2017).
3.
Andoni A., Indyk P., Nguyen H.L., Razenshteyn I.: Beyond locality-sensitive hashing. In: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (Philadelphia, PA, USA), SODA ’14, Society for Industrial and Applied Mathematics, pp. 1018–1028 (2014).
4.
Andoni A., Razenshteyn I.P.: Optimal data-dependent hashing for approximate near neighbors. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, ACM, pp. 793–801 (2015).
5.
Barbero Á.I., Ytrehus Ø.: Modifications of the rao-nam cryptosystem. In: Buchmann J., Høholdt T., Stichtenoth H., Tapia-Recillas H., (eds.) Coding Theory, Cryptography and Related Areas: Proceedings of an International Conference on Coding Theory, Cryptography and Related Areas, held in Guanajuato, Mexico, in April 1998. Springer, Berlin, pp. 1–12 (2000).
6.
Barbier J.: Reconstruction of turbo-code encoders. In: Proceedings of SPIE, vol. 5819, pp. 463–473 (2005).
7.
Barbier J.: Analyse de canaux de communication dans un contexte non coopératif. PhD thesis, École Polytechnique (2007).
8.
Barbier J., Sicot G., Houcke S.: Algebraic approach of the reconstruction of linear and convolutional error correcting codes. In: World Academy of Science, Engineering and Technology, vol. 16, pp. 66–71 (2006).
9.
10.
Bellard M., Tillich J.-P.: Detecting and reconstructing an unknown convolutional code by counting collisions. In: Proceedings of IEEE International Symposium on Information Theory—ISIT (Honolulu, Hawaii, USA), pp. 2967–2971 (2014).
11.
12.
Both L., May A.: Decoding linear codes with high error rate and its impact for LPN security. In: Lange T., Steinwandt R. (eds.) Post-quantum cryptography 2018 (Fort Lauderdale, FL, USA), vol. 10786, pp. 25–46. LNCS. Springer, Berlin (2018).
13.
Bringer J., Chabanne H.: Code reverse engineering problem for identification codes. IEEE Trans. Inf. Theory 58(4), 2406–2412 (2012).MathSciNetCrossRefMATH
14.
Burshtein D., Miller G.: Asymptotic enumeration methods for analyzing LDPC codes. IEEE Trans. Inf. Theory 50(6), 1115–1131 (2004).MathSciNetCrossRefMATH
15.
Chabot C.: Reconstruction of families of codes. application to cyclic codes. In: Workshop on Coding and Cryptography (WCC) (Ullensvang, Norway) (2009).
16.
Cluzeau M., Finiasz M.: Reconstruction of punctured convolutional codes. In: IEEE Information Theory Workshop (ITW) (Taormina, Italy) (2009).
17.
Cluzeau M., Finiasz M.: Recovering a code’s length and synchronization from a noisy intercepted bitstream. In: Proceedings of IEEE International Symposium Information Theory—ISIT (Seoul, Korea), pp. 2737–2741 (2009).
18.
Cluzeau M., Tillich J.-P.: On the code reverse engineering problem. In Proceedings of IEEE International Symposium Information Theory—ISIT (Toronto, Canada), pp. 634–638 (2008).
19.
Cluzeau M., Finiasz M., Tillich J.-P.: Methods for the Reconstruction of Parallel Turbo Codes. In: Proceedings of IEEE International Symposium Information Theory—ISIT (Austin, Texas, USA), pp. 2008–2012 (2010).
20.
Côte M., Sendrier,N.: Reconstruction of convolutional codes from noisy observation. In Proceedings of IEEE International Symposium Information Theory—ISIT (Seoul, Korea), pp. 546–550 (2009).
21.
Côte M., Sendrier N.: Reconstruction of a turbo-code interleaver from noisy observation. In: Proceedings of IEEE International Symposium Information Theory—ISIT (Austin, Texas, USA), pp. 2003–2007 (2010).
22.
Deshpande A.J.: Sampling-based algorithms for dimension reduction. PhD thesis, Massachusetts Institute of Technology (2007).
23.
Di C., Richardson T., Urbanke R.: Weight distribution of low-density parity-check codes. IEEE Trans. Inf. Theory 52(11), 4839–4855 (2006).MathSciNetCrossRefMATH
24.
Dingel J., Hagenauer J.: Parameter estimation of a convolutional encoder from noisy observation. In: Proceedings of IEEE International Symposium on Information Theory—ISIT (Nice, France, June 2007), pp. 1776–1780 (2007).
25.
Dubiner M.: Bucketing coding and information theory for the statistical high-dimensional nearest-neighbor problem. IEEE Trans. Inf. Theory 56(8), 4166–4179 (2010).MathSciNetCrossRefMATH
26.
Dumer I.: On minimum distance decoding of linear codes. In: Proceedings of 5th Joint Soviet-Swedish International Workshop Information Theory (Moscow), pp. 50–52 (1991).
27.
Esmaeili M., Dakhilalian M., Gulliver T.A.: New secure channel coding scheme based on randomly punctured quasi-cyclic-low density parity check codes. IET Commun. 8(14), 2556–2562 (2014).CrossRef
28.
Filiol E.: Reconstruction of convolutional encoders over \(GF(q)\). In: Cryptography and Coding: 6th IMA International Conference, pp. 101–109 (1997).
29.
Filiol E.: Reconstruction of punctured convolutional encoders. In: Proceedings of IEEE International Symposium on Information Theory and Applications (ISITA) (2000).
30.
31.
Gallager R.G.: Low Density Parity Check Codes. M.I.T. Press, Cambridge, Massachusetts (1963).CrossRefMATH
32.
Gionis A., Indyk P., Motwani R.: Similarity search in high dimensions via hashing. In: Proceedings of the 25th VLDB Conference, pp. 518–529 (1999).
33.
Gordon D.M., Miller V.S., Ostapenko P.: Optimal hash functions for approximate matches on the \(n\)-cube. IEEE Trans. Inf. Theory 56(3), 984–991 (2010).MathSciNetCrossRefMATH
34.
Har-Peled S., Indyk P., Motwani R.: Approximate nearest neighbor: towards removing the curse of dimensionality. Theory Comput. 8(14), 321–350 (2012).MathSciNetCrossRefMATH
35.
Indyk P., Motwani R.: Approximate nearest neighbors: towards removing the curse of dimensionality. In: Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing (New York, NY, USA), STOC ’98, ACM, pp. 604–613 (1998).
36.
Lu P., Shen L., Luo X., Zou Y.: Blind recognition of punctured convolutional codes. In: Proceedings of IEEE International Symposium on Information Theory—ISIT (Chicago, USA), p. 457 (2004).
37.
MacWilliams F.J., Sloane N.J.A.: The Theory of Error-Correcting Codes, 5th edn. North-Holland, Amsterdam (1986).MATH
38.
Mafakheri B., Eghlidos T., Pilaram H.: An efficient secure channel coding scheme based on polar codes. ISC Int. J. Inf. Secur. 9(2), 13–20 (2017).
39.
Marazin M.: Reconnaissance en aveugle de codeur à base de code convolutif: contribution à la mise en oeuvre d’un récepteur intelligent. PhD thesis, Université de Bretagne Occidentale (2009).
40.
Marazin M., Gautier R., Burel G.: Algebraic method for blind recovery of punctured convolutional encoders from an erroneous bitstream. IET Signal Process. 6(2), 122–131 (2012).MathSciNetCrossRef
41.
Matsui M.: Linear cryptanalysis method for DES cipher. In: Proceedings of Advances in Cryptology—EUROCRYPT ’93, Workshop on the Theory and Application of of Cryptographic Techniques, Lofthus, Norway, May 23–27, 1993, vol. 765. Lecture Notes in Computer Science. Springer, pp. 386–397 (1993).
42.
May A., Ozerov I.: On computing nearest neighbors with applications to decoding of binary linear codes. In: Oswald E., Fischlin M. (eds.) Advances in Cryptology—EUROCRYPT 2015, vol. 9056, pp. 203–228. LNCS. Springer, Berlin (2015).
43.
Naseri A., Azmoon O., Fazeli S.: Blind recognition algorithm of turbo codes for communication intelligence systems. Int. J. Comput. Sci. Issues 8(1), 68–72 (2011).
44.
Rao T.R.N., Nam K.: Private-key algebraic-coded cryptosystems. In: Advances in cryptology—CRYPTO’86, vol. 263, pp. 35–48. LNCS. Springer, Berlin (1986).
45.
Rathi V.: On the asymptotic weight distribution of regular LDPC ensembles. In: IEEE Proceedings of International Symposium on Information Theory, 2005 (ISIT 2005), pp. 2161–2165 (2005).
46.
Rice B.: Determining the parameters of a rate \(\frac{1}{n}\) convolutional encoder over \({GF}(q)\). In: Third International Conference on Finite Fields and Applications (Glasgow, 1995).
47.
Richardson T., Urbanke R.: Modern Coding Theory. Cambridge University Press, Cambridge (2008).CrossRefMATH
48.
Rosen G.L.: Examining coding structure and redundancy in DNA. IEEE Eng. Med. Biol. 25(1), 62–68 (2006).CrossRef
49.
Sicot G., Houcke S., Barbier J.: Blind detection of interleaver parameters. Signal Process. 89(4), 450–462 (2009).CrossRefMATH
50.
Sobhi Afshar A.A., Eghlidos T., Aref M.R.: Efficient secure channel coding based on quasi-cyclic low-density parity-check codes. IET Commun. 3(2), 279–292 (2009).MathSciNetCrossRefMATH
51.
Struik R., Tilburg J.V.: The Rao-Nam scheme is insecure against a chosen-plaintext attack. In: Advances in Cryptology—CRYPTO’87, vol. 293, pp. 445–457. LNCS. Springer, Berlin (1987).
52.
Tillich, J.-P., Tixier, A., Sendrier, N.: Recovering the interleaver of an unknown turbo-code. In: Proceedings of IEEE International Symposium Information Theory—ISIT (Honolulu, Hawaii, USA), pp. 2784–2788 (2014).
53.
Tixier A.: Blind identification of an unknown interleaved convolutional code. In: IEEE International Symposium on Information Theory, ISIT 2015, Hong Kong, China, June 14–19, 2015, pp. 71–75 (2015).
54.
55.
Tixier A.: Reconnaissance de codes correcteurs (Blind identification of error correcting codes). PhD thesis, Pierre and Marie Curie University, Paris, France (2015).
56.
57.
Valiant L.G.: Graph-theoretic arguments in low-level complexity. In: Proceedings of Mathematical Foundations of Computer Science 1977, 6th Symposium, Tatranska Lomnica, Czechoslovakia, September 5–9, 1977, vol. 53, pp. 162–176. LNCS. Springer, Berlin (1977).
58.
Wang J., Yue Y., Yao J.: A method of blind recognition of cyclic code generator polynomial. In: IEEE 6th International Conference on Wireless Communications Networking and Mobile Computing (WiCOM) (2010).
59.
Wang L., Hu Y., Hao S., Qi L.: The method of estimating the length of linear cyclic code based on the distribution of code weight. In: IEEE 2nd International Conference on Information Science and Engineering (ICISE), pp. 2459–2462 (2010).
60.
Wang Z.H.F., Zhou Y.: A method for blind recognition of convolution code based on Euclidean algorithm. In: International Conference on Wireless Communications, Networking and Mobile Computing (Shanghai, China), pp. 1414–1417 (2007).
61.
Wilf H.: Generatingfunctioology, 2nd edn. Academic Press, Cambridge (1994).
62.
Yardi A.-D., Vijayakumaran S., Kumar A.: Blind reconstruction of binary cyclic codes. In: Proceedings of the European Wireless 2014 (2014).
63.
Zhou J., Huang Z., Su S., Yang S.: Blind recognition of binary cyclic codes. In: EURASIP Journal on Wireless Communications and Networking (2013).
Metadaten
Titel
Identifying an unknown code by partial Gaussian elimination
verfasst von
Kevin Carrier
Jean-Pierre Tillich
Publikationsdatum
21.12.2018
Verlag
Springer US
Erschienen in
Designs, Codes and Cryptography / Ausgabe 2-3/2019
Print ISSN: 0925-1022
Elektronische ISSN: 1573-7586
DOI
https://doi.org/10.1007/s10623-018-00593-7

Weitere Artikel der Ausgabe 2-3/2019

Designs, Codes and Cryptography 2-3/2019 Zur Ausgabe

OriginalPaper

A new lower bound for the smallest complete (k, n)-arc in

OriginalPaper

Local distributions for eigenfunctions and perfect colorings of q-ary Hamming graph

OriginalPaper

The covering radii of a class of binary cyclic codes and some BCH codes

OriginalPaper

On circulant involutory MDS matrices

OriginalPaper

The functional graph of linear maps over finite fields and applications

OriginalPaper

Improved decoding and error floor analysis of staircase codes