On two windows multivariate cryptosystem depending on random parameters

Urszula Romańczuk-Polubiec ; Vasyl Ustimenko

Algebra and discrete mathematics, Tome 19 (2015) no. 1, pp. 101-129.

Résumé

The concept of multivariate bijective map of an affine space $K^n$ over commutative Ring $K$ was already used in Cryptography. We consider the idea of nonbijective multivariate polynomial map $F_n$ of $K^n$ into $K^n$ represented as “partially invertible decomposition” $F^{(1)}_nF^{(2)}_n \dots F^{(k)}_n$, $k=k(n)$, such that knowledge on the decomposition and given value $u=F(v)$ allow to restore a special part $v'$ of reimage $v$. We combine an idea of "oil and vinegar signatures cryptosystem" with the idea of linguistic graph based map with partially invertible decomposition to introduce a new cryptosystem. The decomposition will be induced by pseudorandom walk on the linguistic graph and its special quotient (homomorphic image). We estimate the complexity of such general algorithm in case of special family of graphs with quotients, where both graphs form known families of Extremal Graph Theory. The map created by key holder (Alice) corresponds to pseudorandom sequence of ring elements. The postquantum version of the algorithm can be obtained simply by the usage of random strings instead of pseudorandom.

Détail

Keywords: cryptosystem, multivariate cryptography, postquantum cryptography, algebraic incidence structure, pseudorandom sequences, pseudorandom walk in graph.

Bibliographie

[1] Bollobás B., Extremal Graph Theory, Academic Press, London, 1978 | MR | Zbl

[2] Braeken A., Wolf C., Prenel B., A study of the security of Unbalanced Oil and Vinegar Signature Schemes, ESAT-COSIC, 2004

[3] Bulygin S., Petzoldt A., Buchmann J., “Towards provable security of the unbalanced oil and vinegar signature scheme under direct attacks”, Progress in Cryptology, INDOCRYPT 2010, eds. Guang Gong and Kishan Chand Gupta ; Lecture Notes in Computer Science, 6498, 2010, 17–32 | MR | DOI | Zbl

[4] Ding J., Gower J. E., Schmidt D. S., Multivariate Public Key Cryptosystems, Advances in Information Security, 25, Springer, 2006, 260 pp. | MR | Zbl

[5] Kipnis A., Shamir A., “Cryptanalisis of the Oil and Vinegar Signature Scheme”, Advances in Cryptology, Crypto 96; Lecture Notes in Computer Science, 1462, 1996, 257–266 | DOI | MR

[6] Kipnis A., “Unbalanced Oil and Vinegar Signature Scheme — extended version”, Euro-Crypt, 1999

[7] Klisowski M., Ustimenko V., “On the Comparison of Cryptographical Properties of Two Different Families of Graphs with Large Cycle Indicator”, Mathematics in Computer Science, 6:2 (2012), 181–198 | DOI | MR | Zbl

[8] Klisowski M., Romańczuk U., Ustimenko V., “On the implementation of cubic public keys based on new family of algebraic graphs”, Annales UMCS Informatica, XI:2 (2011), 127–14 | MR

[9] Koblitz N., Algebraic aspects of cryptography, Algorithms and Computation in Mathematics, 3, Springer, 1998 | DOI | MR | Zbl

[10] Kotorowicz J. S., Ustimenko V., “On the properties of stream ciphers based on extremal directed graphs”, Cryptography Research Perspective, ed. Roland E. Chen, Nova Science Publishers, 2009, 125–141 | MR

[11] Kotorowicz S., Ustimenko V., “On the implementation of cryptoalgorithms based on algebraic graphs over some commutative rings”, Condens. Matter Phys., 11:2(54) (2008), 347–360 | DOI

[12] Kotorowicz J. S., Romańczuk U., Ustimenko V., “On the implementation of stream ciphers based on a new family of algebraic graphs”, Proceedings of the Conference CANA, FedSCIS, IEEE Computer Society Press, 2011, 485–490

[13] Lazebnik F., Ustimenko V., “Explicit construction of graphs with an arbitrary large girth and of large size”, Discrete Appl. Math., 60 (1995), 275–284 | DOI | MR | Zbl

[14] Lazebnik F., Ustimenko V. A., Woldar A. J., “New Series of Dense Graphs of High Girth”, Bull (New Series) of AMS, 32:1 (1995), 73–79 | DOI | MR | Zbl

[15] Lazebnik F., Ustimenko V. A., Woldar A. J., “A Characterization of the Components of the graphs $D(k,q)$”, Discrete Mathematics, 157 (1996), 271–283 | DOI | MR | Zbl

[16] Patarin J., The Oil i Vinegar digital signatures, Presented at Dagstuhl Workshop on Cryptography, 1997

[17] Petzoldt A., Bulygin S., Buchmann J., “Cyclicrainbow — a multivariate signature scheme with a partially cyclic public key”, Progress in Cryptology, INDOCRYPT 2010, ed. Guang Gong and KishanChand Gupta ; Lecture Notes in Computer Science, 6498, 2010, 33–48 | MR | DOI | Zbl

[18] Petzoldt A., Bulygin S., Buchmann J., “Fast verification for improved versions of the uov and rainbow signature schemes”, Post-Quantum Cryptography, ed. Philippe Gaborit; Lecture Notes in Computer Science, 7932, 2014, 188–202 | DOI

[19] Romańczuk U., Ustimenko V., “On the key exchange with matrices of large order and graph based nonlinear maps” (Vlora), Albanian Journal of Mathematics, 4, Special Issue. Proceedings of the conference Applications of Computer Algebra:4 (2010), 203–211 | MR | Zbl

[20] Romańczuk U., Ustimenko V., “On the family of cubical multivariate cryptosystems based on the algebraic graph over finite commutative rings of characteristic 2”, Annales UMCS Informatica, XII:3 (2012), 89–106 | MR | Zbl

[21] Romańczuk U., Ustimenko V., “On the key exchange with new cubical maps based on graphs”, Annales UMCS Informatica, 4:11 (2011), 11–19 | MR | Zbl

[22] Romańczuk U., Ustimenko V., “On regular forests given in terms of algebraic geometry, new families of expanding graphs with large girth and Multivariate cryptographical algorithms”, Proceedings of International conference “Applications of Computer Algebra” (Malaga), 2013, 144–147

[23] Romańczuk U., Ustimenko V. A., “On the family of cubical multivariate cryptosystemsbased on exceptional extremal graphs”, Third International Conference on Symbolic Computations and Cryptography, Castro Urdiales, Extended Abstracts, 2012, 169–175

[24] Romańczuk U., Ustimenko V., “On families of large cycle matroids, matrices of large order and key exchange protocols with nonlinear polynomial maps of small degree”, Mathematics in Computer Science, 6:2 (2012), 167–180 | DOI | MR | Zbl

[25] Romańczuk-Polubiec U., Ustimenko V., “On new key exchange multivariate protocols based on pseudorandom walks on incidence structures”, Dopovidi National Academy of Sciences of Ukraine, 2015, 41–49 | Zbl

[26] Ustimenko V., “On Multivariate Cryptosystems Based on Computable Maps with Invertible Decomposition”, Annales UMCS, Informatica, 14:1 (2014), 7–17 | DOI | MR

[27] Ustimenko V., “Linear interpretations for flag geometries of Chevalley groups”, Ukr. Math. J., 42:3 (1990), 383–387 (Russian) | DOI | MR | Zbl

[28] Ustimenko V., “Small Schubert cells as subsets in Lie algebras”, Functional Analysis and Applications, 25:4 (1991), 81–83 | MR | Zbl

[29] Ustimenko V., “Coordinatisation of Trees and their Quotients”, The “Voronoj's Impact on Modern Science”, v. 2, Institute of Mathematics, Kiev, 1998, 125–152 | Zbl

[30] Ustimenko V., “On the varieties of parabolic subgroups, their generalisations and combinatorial applications”, Acta Applicandae Mathematicae, 52 (1998), 223–238 | DOI | MR | Zbl

[31] Ustimenko V., “CRYPTIM: Graphs as Tools for Symmetric Encryption”, Lecture Notes in Computer Science, 2227, Springer, 2001, 278–287 | DOI | MR

[32] Ustimenko V., “Graphs with Special Arcs and Cryptography”, Acta Applicandae Mathematicae, 74:2 (2002), 117–153 | DOI | MR | Zbl

[33] Ustimenko V., “Maximality of affine group and hidden graph cryptosystems”, J. Algebra Discrete Math., 3:1 (2005), 133–150 | MR

[34] Ustimenko V., “On the cryptographical properties of extreme algebraic graphs”, Algebraic Aspects of Digital Communications, Lectures of Advanced NATO Institute, NATO Science for Peace and Security Series — Information and Communication Security, 24, July, IOS Press, 2009, 296 pp. | MR | Zbl

[35] Ustimenko V., “Schubert cells in Lie geometries and key exchange via symbolic computations” (Vlora), Albanian Journal of Mathematics, 4:4, Special Issue. Proceedings of the International Conference “Applications of Computer Algebra” (2010), 135–145 | MR | Zbl

[36] Ustimenko V., “On the extremal graph theory for directed graphs and its cryptographical applications”, Advances in Coding Theory and Cryptography, Series on Coding and Cryptology, 3, eds. T. Shaska, W. C. Huffman, D. Joener and V. Ustimenko, 2007, 181–200 | DOI | MR

[37] Ustimenko V. A., “Linguistic Dynamical Systems, Graphs of Large Girth and Cryptography”, Journal of Mathematical Sciences, 140:3 (2007), 412–434 | DOI | MR | Zbl

[38] Ustimenko V. A., “On the graph based cryptography and symbolic computations”, ACA-2006 (Varna), Serdica Journal of Computing, Proceedings of International Conference on Application of Computer Algebra, no. 1, 2007 | MR

[39] Ustimenko V. A., “Algebraic groups and small world graphs of high girth”, Albanian J. Math., 3:1 (2009), 25–33 | MR | Zbl

[40] Ustimenko V. A., “On extremal graph theory and symbolic computations”, Dopovidi National Academy of Sciences of Ukraine, 2013, no. 2, 42–49 (Russian) | Zbl

[41] Ustimenko V. A., “On $K$-theory of dynamical system, corresponding to graphs and its applications”, Dopovidi National Academy of Sciences of Ukraine, 2013, no. 8, 44–51 (Russian) | Zbl

[42] Ustimenko V., “On walks of variable length in the Schubert systems and multivariate stream ciphers”, Dopovidi National Academy of Sciences of Ukraine, 2014, no. 3, 55–63 | Zbl

[43] Ustimenko V., Romańczuk U., “On Dynamical Systems of Large Girth or Cycle Indicator and their applications to Multivariate Cryptography”, Artificial Intelligence, Evolutionary Computing and Metaheuristics. In the footsteps of Alan Turing Series, Studies in Computational Intelligence, 427, Springer, 2013, 257–285 | DOI | Zbl

[44] Ustimenko V., Romańczuk U., “On Extremal Graph Theory, Explicit Algebraic Constructions of Extremal Graphs and Corresponding Turing Encryption Machines”, Artificial Intelligence, Evolutionary Computing and Metaheuristics. In the footsteps of Alan Turing Series, Studies in Computational Intelligence, 427, Springer, 2013, 231–256 | DOI | Zbl

[45] Ustimenko V., Wróblewska A., “On the key exchange with nonlinear polynomial maps of stable degree”, Annalles UMCS Informatica, X1:2 (2011), 81–93 | Zbl

[46] Wróblewska A., “On some properties of graph based public keys”, Albanian Journal of Mathematics, 2:3, NATO Advanced Studies Institute: New challenges in digital communications (2008), 229–234 | MR | Zbl