RO  EN
IMI/Publicaţii/QRS/Ediţii/QRS v.17, n.1 (21), 2009/

Generating huge quasigroups from small non-linear bijections via extended Feistel function

Authors: S. Markovski and A. Mileva

Abstract

Quasigroups of huge order, like $2^{256},\ 2^{512}, \ 2^{1024}$, that can be effectively constructed, have important applications in designing several cryptographic primitives. We propose an effective method for construction of such huge quasigroups of order $r=2^{s2^{t}}$ for small fixed values of $s$ and arbitrary values of $t$; the complexity of computation of the quasigroup multiplication is $\mathcal{O}(\texttt{log}(\texttt{log}(r)))=\mathcal{O}(t)$. Besides the computational effectiveness, these quasigroups can be constructed in such a way to have other desirable cryptographic properties: do not satisfy the commutative law, the associative law, the idempotent law, to have no proper subquasigroups, to be non-linear, etc. These quasigroups are constructed by complete mappings generated by suitable bijections of order $2^s$ via extended Feistel network functions. Quasigroups of huge order, like 2256, 2512, 21024, that can be effectively constructed, have important applications in designing several cryptographic primitives. We propose an effective method for construction of such huge quasigroups of order r=2s2t for small fixed values of s and arbitrary values of t; the complexity of computation of the quasigroup multiplication is O(log(log(r)))=O(t). Besides the computational effectiveness, these quasigroups can be constructed in such a way to have other desirable cryptographic properties: do not satisfy the commutative law, the associative law, the idempotent law, to have no proper subquasigroups, to be non-linear, etc. These quasigroups are constructed by complete mappings generated by suitable bijections of order 2s via extended Feistel network functions.




Fulltext

Adobe PDF document0.28 Mb