RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 General information Latest issue Archive Impact factor Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Algebra Discrete Math.: Year: Volume: Issue: Page: Find

 Algebra Discrete Math., 2015, Volume 19, Issue 1, Pages 101–129 (Mi adm511)

RESEARCH ARTICLE

On two windows multivariate cryptosystem depending on random parameters

Urszula Romańczuk-Polubiec, Vasyl Ustimenkoa

a Maria Curie-Sklodowska University, Lublin

Abstract: 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 …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.

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

Full text: PDF file (446 kB)
References: PDF file   HTML file

Bibliographic databases:
MSC: 12Y05, 12Y99, 05C81, 05C85, 05C90, 94A60, 14G50
Revised: 12.03.2015
Language:

Citation: Urszula Romańczuk-Polubiec, Vasyl Ustimenko, “On two windows multivariate cryptosystem depending on random parameters”, Algebra Discrete Math., 19:1 (2015), 101–129

Citation in format AMSBIB
\Bibitem{RomUst15} \by Urszula~Roma{\'n}czuk-Polubiec, Vasyl~Ustimenko \paper On two windows multivariate cryptosystem depending on random parameters \jour Algebra Discrete Math. \yr 2015 \vol 19 \issue 1 \pages 101--129 \mathnet{http://mi.mathnet.ru/adm511} \mathscinet{http://www.ams.org/mathscinet-getitem?mr=3376344} \isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000209846200011} 

 SHARE:

Citing articles on Google Scholar: Russian citations, English citations
Related articles on Google Scholar: Russian articles, English articles

This publication is cited in the following articles:
1. Ustimenko V., “Explicit Constructions of Extremal Graphs and New Multivariate Cryptosystems”, Stud. Sci. Math. Hung., 52:2 (2015), 185–204
2. V. A. Ustimenko, “On Schubert cells in Grassmanians and new algorithms of multivariate cryptography”, Tr. In-ta matem., 23:2 (2015), 137–148
3. Vasyl Ustimenko, “On algebraic graph theory and non-bijective multivariate maps in cryptography”, Algebra Discrete Math., 20:1 (2015), 152–170
4. Vasyl Ustimenko, “On new multivariate cryptosystems with nonlinearity gap”, Algebra Discrete Math., 23:2 (2017), 331–348
5. V. Ustymenko, A. Wroblewska, U. Romanczuk-Polubiec, E. Zhupa, M. Polak, “On the implementation of new symmetric ciphers based on non-bijective multivariate maps”, Proceedings of the 2018 Federated Conference on Computer Science and Information Systems (FedCSIS), eds. M. Ganzha, L. Maciaszek, M. Paprzycki, IEEE, 2018, 397–405
•  Number of views: This page: 120 Full text: 52 References: 60