nach oben

Cryptography and Communications

Erschienen in:

14.01.2019

An iterative method for linear decomposition of index generating functions

verfasst von: S. Hodžić, E. Pasalic, A. Chattopadhyay

Erschienen in: Cryptography and Communications | Ausgabe 5/2019

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

Various methods for reducing hardware implementation cost of incompletely specified index generating functions have been proposed lately. Considering the methods based on linear decomposition, for the first time in this work, we provide necessary and sufficient conditions which describe the linear decomposition of these functions in general. These conditions are derived using the concept of functional degeneracy, and we show that the problem of linear decomposition can be translated into the problem of constructing suitable coordinate Boolean functions (which represent the generating functions) such that the linear decomposition is possible. In this context, we propose several design methods of such Boolean functions and furthermore we employ one particular design method to derive a new iterative semi-deterministic algorithm for linear decomposition. In addition, we provide a general result which describes all incompletely specified index generating functions for which the linear decomposition is (not) possible. Consequently, our results indicate that the functional degeneracy is a promising approach in derivation of new deterministic-like algorithms for linear decomposition of incompletely specified index generating functions.

Vorheriger Artikel Integer codes correcting sparse byte errors

Nächster Artikel A concatenated construction of linear complementary pair of codes

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Nur mit Berechtigung zugänglich

From the point of cryptographic applications, this term was introduced by Mitchell [10].

Algorithm 1 was implemented in Wolfram Mathematica 9, on the machine with the following characteristics: Lenovo ThinkPad E540, OS Windows 7 (64-bit), Intel Core i5-4200M-2.5GHz, RAM 4Gb.

Astola, J., Astola, P., Stanković, R., Tabus, I.: An algebraic approach to reducing the number of variables of incompletely defined discrete functions. In: 46th International Symposium on Multiple-Valued Logic, pp. 107–112 (2016)

Astola, J., Astola, P., Stanković, R., Tabus, I.: Index generation functions based on linear and polynomial transformations. In: 46th International Symposium on Multiple-Valued Logic, pp. 102–106 (2016)

Bhattacharyya, A., Indyk, P., Woodruff, D.P., Xie, N.: The complexity of linear dependence problems in vector spaces. Innovations Comput. Sci., 496–508. ISBN 978-7-302-24517-9 (2011)

Crama, Y., Hammer, P.L.: Boolean Functions: Theory, Algorithms, and Applications. Encyclopedia of Mathematics and its Applications. Cambridge University Press, Cambridge (2011)CrossRefMATH

Een, N., Sorensson, N.: An extensible SAT-solver. In: Giunchiglia, E., Tacchella, A. (eds.) Theory and Applications of Satisfiability Testing. Lecture Notes in Computer Science, SAT 2003, vol. 2919, pp 502–518. Springer, Berlin (2003)

Karpovsky, M.G., Stankovic, R.S., Astola, J.T.: Spectral Logic and Its Applications for the Design of Digital Devices. Wiley, Hoboken (2007)

Kolomeec, N., Pavlov, A.: Bent functions on the minimal distance. IEEE Region 8, SIBIRCON, Irkutsk Listvyanka, Russia (2010)

Lechner, R.J.: Harmonic analysis of switching functions. Recent Developments in Switching Theory, New York, Edited by: Amar Mukhopadhyay, pp. 121–228 (1971)

Luba, T., Borowik, G., Jankowski, C.: Gate-based decomposition of index generation functions. Photonics Applications in Astronomy, Communications, Industry, and High-Energy Physics Experiments, vol. 10031 (2016)

10.

Mitchell, C.: Enumerating Boolean functions of cryptographic significance. J. Cryptol. 2(3), 155–170 (1990)MathSciNetCrossRefMATH

11.

Nagayama, S., Sasao, T., Butler, J.T.: An efficient heuristic for linear decomposition of index generation functions. In: 46nd International Symposium on Multiple-Valued Logic, pp. 96–101. Japan (2016)

12.

Nagayama, S., Sasao, T., Butler, J.T.: A balanced decision tree based heuristic for linear decomposition of index generation functions. IEICE Trans. Inf. Syst. E100.D (8), 1583–1591 (2017)CrossRef

13.

Nečiporuk, E.I.: Network synthesis by using linear transformation of variables. Dokladi Akademii Nauk SSSR 123(4), 610–612 (1958)

14.

Pagiamtzis, K., Sheikholeslami, A.: Content-addressable memory (CAM) circuits and architectures: A tutorial and survey. IEEE J. Solid State Circuits 41(3), 712–727 (2006)CrossRef

15.

Sasao, T.: Index generation functions: tutorial. J. Multiple-Valued Logic Soft Comput. 23(3–4), 235–263 (2014)

16.

Sasao, T.: Multiple-valued input index generation functions: optimization by linear transformation. In: 42nd International Symposium on Multiple-Valued Logic, pp. 185–190. Canada (2012)

17.

Sasao, T.: A reduction method for the number of variables to represent index generation functions: s-Min method. In: 45nd International Symposium on Multiple-Valued Logic, pp. 164–169. Canada (2015)

18.

Sasao, T.: Index generation functions: theory and applications. In: International Symposium on Communications and Information Technologies, pp. 585–590. Japan (2010)

19.

Sasao, T.: Linear transformations for variable reduction. ReedMuller Workshop (2011)

20.

Sasao, T.: On the numbers of variables to represent multi-valued incompletely specified functions. In: 13th Euromicro Conference on Digital System Design: Architectures, Methods and Tools. France (2010)

21.

Sasao, T.: On the numbers of variables to represent sparse logic functions. In: IEEE/ACM International Conference on Computer-Aided Design, pp. 45–51. San Jose, USA (2008)

22.

Sasao, T.: Index generation functions: recent developments. In: 41st IEEE International Symposium on Multiple-Valued Logic, pp. 235–263. Finland (2011)

23.

Sasao, T.: Memory-Based Logic Synthesis. Springer-Verlag, New York (2011)CrossRef

24.

Sasao, T.: Linear decomposition of index generation functions. In: 17th Asia and South Pacific Design Automation Conference, pp. 781–788 (2012)

25.

Sasao, T.: Index generation functions: Minimization methods. In: 47th International Symposium on Multiple-Valued Logic, pp. 197–206 (2017)

26.

Sasao, T.: An application of autocorrelation functions to find linear decompositions for incompletely specified index generation functions. In: 43rd International Symposium on Multiple-Valued Logic, pp. 96–102 (2013)

27.

Sasao, T.: A linear decomposition of index generation functions: optimization using autocorrelation functions. J. Multiple-Valued Logic Soft Comput. 28(1), 105–127 (2017)MathSciNetMATH

28.

Sasao, T., Fumishi, I., Iguch, Y.: A method to minimize variables for incompletely specified index generation functions using a SAT solver. In: International Workshop on Logic and Synthesis, Mountain View, pp. 161–167 (2015)

29.

Sasao, T., Nakamura, T., Matsuura, M.: Representation of incompletely specified index generation functions using minimal number of compound variables. In: 12th Euromicro Conference on Digital System Design / Architectures, Methods and Tools, pp 765–772 (2009)

30.

Sasao, T., Matsuura, M., Nakahara, H.: A realization of Index generation functions using modules of uniform sizes. In: International Workshop on Logic and Synthesis, pp. 201–208. California (2010)

31.

Sasao, T., Urano, Y., Iguchi, Y.: A method to find linear decompositions for incompletely specified index generation functions using difference matrix. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. E97.A(12), 2427–2433 (2014)CrossRef

32.

Sasao, T., Urano, Y., Iguchi, Y.: A lower bound on the number of variables to represent incompletely specified index generation functions. In: 44th International Symposium on Multiple-Valued Logic, pp. 7–12. Germany (2014)

33.

Abboud, A., Lewi, K., Williams, R.: Losing weight by gaining edges. In: 22th Annual European Symposium on Algorithms, Lecture Notes in Computer Science, vol. 8737, pp. 1–12. Poland (2014)

34.

Simovici, D.A., Zimand, M., Pletea, D.: Several remarks on index generation functions. In: 42nd IEEE International Symposium on Multiple-Valued Logic, pp. 179–184. Canada (2012)

35.

Stanković, M., Stanković, R.: Variable reduction of index generating functions in Walsh-Hadamard domain. In: Proceedings Reed-Muller Workshop, pp. 80–85. Japan (2013)

36.

Troy Nagle, H., Carroll, B.D., David Irwin, J.: : An Introduction to Computer Logic (Prentice-Hall computer applications in electrical engineering series), 1st edn. Prentice-Hall, Englewood Cliffs (1975)

37.

Varma, D., Trachtenberg, E.: Design automation tools for efficient implementation of logic functions by decomposition. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 8(8), 901–916 (1989)CrossRef

38.

Wu, C.-K., Feng, D.: Boolean functions and their applications in cryptography. Advances in Computer Science and Technology (2016)

Titel: An iterative method for linear decomposition of index generating functions
verfasst von: S. Hodžić
E. Pasalic
A. Chattopadhyay
Publikationsdatum: 14.01.2019
Verlag: Springer US
Erschienen in: Cryptography and Communications / Ausgabe 5/2019
Print ISSN: 1936-2447
Elektronische ISSN: 1936-2455
DOI: https://doi.org/10.1007/s12095-019-0351-8

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 5/2019

The separation of binary relative three-weight codes and its applications

A construction of Abelian non-cyclic orbit codes

Absorbing sets of codes from finite geometries

New linear codes over non-prime fields

On Boolean functions with several flat spectra

r-th order nonlinearity, correlation measure and least significant bit of the discrete logarithm

Premium Partner