Algebraic properties of the operations used in block cipher idea

Yıldırım, Hamdi Murat
In this thesis we obtain several interesting algebraic properties of the operations used in the block cipher IDEA which are important for cryptographic analyzes. We view each of these operations as a function from $\mathbb Z_{2}^n \times \mathbb Z_{2}^n \to \mathbb Z_{2}^n$. By fixing one of variables $v(z)=\mathbf Z$ in $\mathbb Z_{2}^n \times \mathbb Z_{2}^n$, we define functions $\mathbf {f}_z$ and $\mathbf {g}_z$ from $\mathbb Z_{2}^n$ to $\mathbb Z_{2}^n$ for the addition $\BIGboxplus$ and the multiplication $\BIGodot$ operations, respectively. We first show that the nonlinearity of $\mathbf {g}_z$ remains the same under some transformations of $z$. We give an upper bound for the nonlinearity of $\mathbf {g}_{2^k}$, where $2\leq k < n-1$. We list all linear relations which make the nonlinearity of $\mathbf {f}_z$ and $\mathbf {g}_z$ zero and furthermore, we present all linear relations for $\mathbf {g}_z$ having a high probability. We use these linear relations to derive many more linear relations for 1-round IDEA. We also devise also a new algorithm to find a set of new linear relations for 1-round IDEA based on known linear relations. Moreover, we extend the largest known linear class of weak keys with cardinality $2^{23}$ to two classes with cardinality $2^{24}$ and $2^{27}$. Finally, we obtain several interesting properties of the set $ \{ ({\mathbf X},{\mathbf X} \BIGoplus {\mathbf A}) \in \mathbb Z_2^n \times \mathbb Z_2^n \,I\, (\mathbf {X}\BJoin {\mathbf Z})\BIGoplus( ({\mathbf X} \BIGoplus {\mathbf A} ) \BJoin \mathbf {Z} ) = {\mathbf B} \}$ for varying ${\mathbf A}, {\mathbf B}$ and ${\mathbf Z}$ in $\mathbb Z_2^n$, where $\BJoin \in \{ \BIGodot,\BIGboxplus \}$. By using some of these properties, we present impossible differentials for 1-round IDEA and Pseudo-Hadamard Transform.


Efficient interleaved Montgomery modular multiplication for lattice-based cryptography
AKLEYLEK, SEDAT; Tok, Zaliha Yuce (2014-01-01)
In this paper, we give modified version of interleaved Montgomery modular multiplication method for lattice-based cryptography. With the proposed algorithms, we improve the multiplication complexity and embed the conversion operation into the algorithm with almost free cost. We implement the proposed methods for the quotient ring (Z/qZ)[x]/(x(n) - 1) and (Z/pZ)[x]/(x(n) + 1) on the GPU (NVIDIA Quadro 600) using the CUDA platform. NTRUEncrypt is accelerated approximately 35% on the GPU by using the proposed ...
Sparse polynomial multiplication for lattice-based cryptography with small complexity
Akleylek, Sedat; Alkim, Erdem; Tok, Zaliha Yuce (2016-02-01)
In this paper, we propose efficient modular polynomial multiplication methods with applications in lattice-based cryptography. We provide a sparse polynomial multiplication to be used in the quotient ring (Z/pZ)[x]/(x(n) + 1). Then, we modify this algorithm with sliding window method for sparse polynomial multiplication. Moreover, the proposed methods are independent of the choice of reduction polynomial. We also implement the proposed algorithms on the Core i5-3210M CPU platform and compare them with numbe...
Descriptive complexity of subsets of the space of finitely generated groups
Benli, Mustafa Gökhan; Kaya, Burak (2022-12-01)
© 2022 Elsevier GmbHIn this paper, we determine the descriptive complexity of subsets of the Polish space of marked groups defined by various group theoretic properties. In particular, using Grigorchuk groups, we establish that the sets of solvable groups, groups of exponential growth and groups with decidable word problem are Σ20-complete and that the sets of periodic groups and groups of intermediate growth are Π20-complete. We also provide bounds for the descriptive complexity of simplicity, amenability,...
Generalized Joint Linear Complexity of Linear Recurring Multisequences
MEİDL, WİLFRİED; Özbudak, Ferruh (2008-09-18)
The joint linear complexity of multisequences is an important security measure for vectorized stream cipher systems. Extensive research has been carried out on the joint linear complexity of N-periodic multisequences using tools from Discrete Fourier transform. Each N-periodic multisequence can be identified with a single N-periodic sequence over an appropriate extension field. It has been demonstrated that the linear complexity of this sequence, the so called generalized joint linear complexity of the mult...
Algebraic Nahm transform for parabolic Higgs bundles on P-1
Aker, Kursat; Szabo, Szilard (2014-01-01)
We formulate the Nahm transform in the context of parabolic Higgs bundles on P-1 and extend its scope in completely algebraic terms. This transform requires parabolic Higgs bundles to satisfy an admissibility condition and allows Higgs fields to have poles of arbitrary order and arbitrary behavior. Our methods are constructive in nature and examples are provided. The extended Nahm transform is established as an algebraic duality between moduli spaces of parabolic Higgs bundles. The guiding principle behind ...
Citation Formats
H. M. Yıldırım, “Algebraic properties of the operations used in block cipher idea,” Ph.D. - Doctoral Program, Middle East Technical University, 2007.