Cryptography using multiple one-dimensional chaotic maps

Recently, Pareek et al. [Phys. Lett. A 309 (2003) 75] have developed a symmetric key block cipher algorithm using a one-dimensional chaotic map. In this paper, we propose a symmetric key block cipher algorithm in which multiple one-dimensional chaotic maps are used instead of a one-dimensional chaotic map. However, we also use an external secret key of variable length (maximum 128-bits) as used by Pareek et al. In the present cryptosystem, plaintext is divided into groups of variable length (i.e. number of blocks in each group is different) and these are encrypted sequentially by using randomly chosen chaotic map from a set of chaotic maps. For block-by-block encryption of variable length group, number of iterations and initial condition for the chaotic maps depend on the randomly chosen session key and encryption of previous block of plaintext, respectively. The whole process of encryption/decryption is governed by two dynamic tables, which are updated time to time during the encryption/decryption process. Simulation results show that the proposed cryptosystem requires less time to encrypt the plaintext as compared to the existing chaotic cryptosystems and further produces the ciphertext having flat distribution of same size as the plaintext.     

Group theoretic properties of Rijndael-like ciphers

We provide conditions for which the round functions of an ?-bit Rijndael-like block cipher generate the alternating group on the set {0,1}^?. These conditions show that the class of Rijndael-like ciphers whose round functions generate the alternating group on their message space is large, and includes both the actual Rijndael and the block cipher used by the compression function of the Whirlpool hash function. The result indicates that there is no trapdoor design for a Rijndael-like cipher based on the imprimitivity of the group action of its proper round functions which is difficult to detect.     

A new counting method to bound the number of active S-boxes in Rijndael and 3D

Security against differential and linear cryptanalysis is an essential requirement for modern block ciphers. This measure is usually evaluated by finding a lower bound for the minimum number of active S-boxes. The 128-bit block cipher AES which was adopted by National Institute of Standards and Technology (NIST) as a symmetric encryption standard in 2001 is a member of Rijndael family of block ciphers. For Rijndael, the block length and the key length can be independently specified to 128, 192 or 256 bits. It has been proved that for all variants of Rijndael the lower bound of the number of active S-boxes for any 4-round differential or linear trail is 25, and for 4r (\(r \ge 1\)) rounds 25r active S-boxes is a tight bound only for Rijndael with block length 128. In this paper, a new counting method is introduced to find tighter lower bounds for the minimum number of active S-boxes for several consecutive rounds of Rijndael with larger block lengths. The new method shows that 12 and 14 rounds of Rijndael with 192-bit block length have at least 87 and 103 active S-boxes, respectively. Also the corresponding bounds for Rijndael with 256-bit block are 105 and 120, respectively. Additionally, a modified version of Rijndael-192 is proposed for which the minimum number of active S-boxes is more than that of Rijndael-192. Moreover, we extend the method to obtain a better lower bound for the number of active S-boxes for the block cipher 3D. Our counting method shows that, for example, 20 and 22 rounds of 3D have at least 185 and 205 active S-boxes, respectively.     

A chaotic block cipher algorithm for image cryptosystems

Recently, many scholars have proposed chaotic cryptosystems in order to promote communication security. However, there are a number of major problems detected in some of those schemes such as weakness against differential attack, slow performance speed, and unacceptable data expansion. In this paper, we introduce a new chaotic block cipher scheme for image cryptosystems that encrypts block of bits rather than block of pixels. It encrypts 256-bits of plainimage to 256-bits of cipherimage within eight 32-bit registers. The scheme employs the cryptographic primitive operations and a non-linear transformation function within encryption operation, and adopts round keys for encryption using a chaotic system. The new scheme is able to encrypt large size of images with superior performance speed than other schemes. The security analysis of the new scheme confirms a high security level and fairly uniform distribution.     

On complexity of round transformations

A modern block cipher consists of round transformations, which are obtained by alternatively applying permutations (P-boxes) and substitutions (S-boxes). Clearly, the most important attribute of a block cipher is its security. However, with respect to the hardware implementation, a good block cipher has to have a reasonable complexity as well. In this paper, we study complexity of round transformations satisfying some basic security criteria. There are several ways to define the complexity of a round transformation, and to choose “necessary” security criteria. It turns out, that for our purpose, it is suitable to view a round transformation as a single Boolean function, not separating it into S-boxes and P-boxes. We require that the Boolean function F possesses some fundamental properties imposed on each block cipher for security reasons; namely, we require that the function is a strictly non-linear bijection and that it has a good diffusion. The total number of variables in the normal algebraic form of the component functions of F is taken as its complexity. We find the minimum complexity of such functions, and this way we establish a lower bound on complexity of all round transformations. To show that the lower bound is the best possible, we construct a round transformation F^′ attaining the bound. We stress that it is not an aspiration of this paper to construct a round transformation which would be of practical use; F^′ is useful only from the theoretical point of view.     

Some observations on HC-128

In this paper, we study HC-128 in detail from cryptanalytic point of view. First, we use linear approximation of the addition modulo 2 ⁿ of three n-bit integers to identify linear approximations of g ₁, g ₂, the feedback functions of HC-128. This, in turn, shows that the process of keystream output generation of HC-128 can be well approximated by linear functions. In this direction, we show that the ??least significant bit?? based distinguisher (presented by the designer himself) of HC-128 works for the complete 32-bit word. Using the above linear approximations of g ₁, g ₂, we present a new distinguisher for HC-128 which is slightly weaker than Wu??s distinguisher. Finally, in the line of Dunkelman??s observation, we also study how HC-128 keystream words leak secret state information of the cipher due to the properties of the functions h ₁, h ₂ and present improved results.     

Tame Kernels of Quaternion Number Fields

Let E/F be a Galois extension of number fields with the quaternion Galois group Q ₈. In this paper, we prove some relations connecting orders of the odd part of the kernel of the transfer map of the tame kernel of E with the same orders of some of its subfields. Let E/? be a Galois extension of number fields with the Galois group Q ₈ and p an odd prime such that p ≡ 3 (mod 4). We prove that if there is at most one quadratic subfield such that the p-Sylow subgroup of the tame kernel is nontrivial, then p ^r -rank(K ₂(E/K)) is even, i.e., 2|p ^r -rank(K ₂(𝒪 _E )) ? p ^r -rank(K ₂(𝒪 _K )), where K is the quartic subfield of E.     

A one-way coupled chaotic map lattice based self-synchronizing stream cipher

Self-synchronizing stream cipher (SSSC) has the advantage that the receiver can automatically synchronize with the sender after receiving previously transmitted ciphertext. However, it has also serious difficulty to keep security due to its self-synchronizing structure. In this paper, a new SSSC based on one-way coupled chaotic map lattice is proposed. By combining floating-point chaotic computations with algebraic operations, the cipher has high bit confusion and diffusion rates. It has both advantages of robustness of synchronization and strong security. The cipher can serve as a new type of SSSC candidate in software implementation.     

The smallest degree sum that yields potentially Kr,r-graphic sequences

We consider a variation of a classical Turán-type extremal problem as follows: Determine the smallest even integer σ(K_r,r,n) such that every n-term graphic sequence π = (d₁,d₂,...,d_n) with term sum σ(π) = d₁ + d₂ + ... + d_n ≥ σ(K_r,r,n) is potentially K_r,r-graphic, where K_r,r is an r × r complete bipartite graph, i.e. π has a realization G containing K_r,r as its subgraph. In this paper, the values σ(K_r,r,n) for even r and n ≥ 4r² - r - 6 and for odd r and n ≥ 4r² + 3r - 8 are determined.     

One-way hash function construction based on chaotic map network

A novel chaotic hash algorithm based on a network structure formed by 16 chaotic maps is proposed. The original message is first padded with zeros to make the length a multiple of four. Then it is divided into a number of blocks each contains 4 bytes. In the hashing process, the blocks are mixed together by the chaotic map network since the initial value and the control parameter of each tent map are dynamically determined by the output of its neighbors. To enhance the confusion and diffusion effect, the cipher block chaining (CBC) mode is adopted in the algorithm. Theoretic analyses and numerical simulations both show that the proposed hash algorithm possesses good statistical properties, strong collision resistance and high flexibility, as required by practical keyed hash functions.     

An elementary approach to gap theorems

Using elementary comparison geometry, we prove: Let (M, g) be a simply-connected complete Riemannian manifold of dimension ≥ 3. Suppose that the sectional curvature K satisfies −1 − s(r) ≤ K ≤ −1, where r denotes distance to a fixed point in M. If lim _{r → ∞} e^2r s(r) = 0, then (M, g) has to be isometric to ℍ ⁿ . The same proof also yields that if K satisfies −s(r) ≤ K ≤ 0 where lim _{r → ∞} r ² s(r) = 0, then (M, g) is isometric to ℝ ⁿ , a result due to Greene and Wu. Our second result is a local one: Let (M, g) be any Riemannian manifold. For a ∈ ℝ, if K ≤ a on a geodesic ball B _p (R) in M and K = a on ∂B _p (R), then K = a on B _p (R).     

Generating Sets of Finite Transformation Semigroups PK(n,r) and K (n,r)

Let P _n and T _n be the partial transformation and the full transformation semigroups on the set {1,…, n}, respectively. In this paper we find necessary and sufficient conditions for any set of partial transformations of height r in the subsemigroup PK(n, r) = {α ∈P _n : |im (α)| ≤r} of P _n to be a (minimal) generating set of PK(n, r); and similarly, for any set of full transformations of height r in the subsemigroup K(n, r) = {α ∈T _n : |im (α)| ≤r} of T _n to be a (minimal) generating set of K(n, r) for 2 ≤ r ≤ n ? 1.     

Filtrations of Simplicial Functors and the Novikov Conjecture

We show that the Strong Novikov Conjecture for the maximal C^*-algebra C^*(π) of a discrete group π is equivalent to a statement in topological K-theory for which the corresponding statement in algebraic K-theory is always true. We also show that for any group π, rational injectivity of the full assembly map for K_*^t(C^*(π)) follows from rational injectivity of the restricted assembly map. (Received: February 2006)     

Integral Schur algebras forGL 2

The structure of Schur algebrasS(2,r) over the integral domainZ is intensively studied from the quasi-hereditary algebra point of view. We introduce certain new bases forS(2,r) and show that the Schur algebraS(2,r) modulo any ideal in the defining sequence is still such a Schur algebra of lower degree inr. A Wedderburn-Artin decomposition ofS _K (2,r) over a fieldK of characteristic 0 is described. Finally, we investigate the extension groups between two Weyl modules and classify the indecomposable Weyl-filtered modules for the Schur algebrasS _Zp(2,r) withr<p ² . Research supported by ARC Large Grant L20.24210     

Using the Hill cipher to teach cryptographic principles

The Hill cipher is the simplest example of a block cipher, which takes a block of plaintext as input, and returns a block of ciphertext as output. Although it is insecure by modern standards, its simplicity means that it is well suited for the teaching of such concepts as encryption modes, and properties of cryptographic hash functions. Although these topics are central to modern cryptography, it is hard to find good simple examples of their use. The conceptual and computational simplicity of the Hill cipher means that students can experiment with these topics, see them in action, and obtain a better understanding that would be possible from a theoretical discussion alone. In this article, we define the Hill cipher and demonstrate its use with different modes of encryption, and also show how cryptographic hash functions can be both designed and broken. Finally, we look at some pedagogical considerations.     

Optimal collision security in double block length hashing with single length key

The idea of double block length hashing is to construct a compression function on 2n bits using a block cipher with an n-bit block size. All optimally secure double block length hash functions known in the literature employ a cipher with a key space of double block size, 2n-bit. On the other hand, no optimally secure compression functions built from a cipher with an n-bit key space are known. Our work deals with this problem. Firstly, we prove that for a wide class of compression functions with two calls to its underlying n-bit keyed block cipher collisions can be found in about \(2^{n/2}\) queries. This attack applies, among others, to functions where the output is derived from the block cipher outputs in a linear way. This observation demonstrates that all security results of designs using a cipher with 2n-bit key space crucially rely on the presence of these extra n key bits. The main contribution of this work is a proof that this issue can be resolved by allowing the compression function to make one extra call to the cipher. We propose a family of compression functions making three block cipher calls that asymptotically achieves optimal collision resistance up to \(2^{n(1-\varepsilon )}\) queries and preimage resistance up to \(2^{3n(1-\varepsilon )/2}\) queries, for any \(\varepsilon >0\). To our knowledge, this is the first optimally collision secure double block length construction using a block cipher with single length key space. We additionally prove this class of functions indifferentiable from random functions in about \(2^{n/2}\) queries, and demonstrate that no other function in this direction achieves a bound of similar kind.     

The K-theory of fields in characteristic p

We show that for a field k of characteristic p, H ⁱ (k,ℤ(n)) is uniquely p-divisible for i≠n (we use higher Chow groups as our definition of motivic cohomology). This implies that the natural map K _n ^M (k)?K _n (k) from Milnor K-theory to Quillen K-theory is an isomorphism up to uniquely p-divisible groups, and that K _n ^M (k) and K _n (k) are p-torsion free. As a consequence, one can calculate the K-theory mod p of smooth varieties over perfect fields of characteristic p in terms of cohomology of logarithmic de Rham Witt sheaves, for example K _n (X,ℤ/p ^r )=0 for n>dimX. Another consequence is Gersten’s conjecture with finite coefficients for smooth varieties over discrete valuation rings with residue characteristic p. As the last consequence, Bloch’s cycle complexes localized at p satisfy all Beilinson-Lichtenbaum-Milne axioms for motivic complexes, except possibly the vanishing conjecture. Oblatum 21-I-1998 & 26-VII-1999 / Published online: 18 October 1999     

On Liouville’s theorem for locally quasiregular mappings inR n

Letf:R ⁿ→Rⁿ be locally quasiregular in the sense that the restriction off to any ball |x|<r has finite inner dilatationK ₁(r). Suppose that the growth condition ∫^∞r^-1K₁(r)^1/(1-n) holds. Then Liouville’s theorem is valid:If f is bounded, f is a constant. An example shows that this growth condition is relatively sharp.     

Ramsey numbers for local colorings

The concept of a localk-coloring of a graphG is introduced and the corresponding localk-Ramsey numberr _loc ^k (G) is considered. A localk-coloring ofG is a coloring of its edges in such a way that the edges incident to any vertex ofG are colored with at mostk colors. The numberr _loc ^k (G) is the minimumm for whichK _m contains a monochromatic copy ofG for every localk-coloring ofK _m . The numberr _loc ^k (G) is a natural generalization of the usual Ramsey numberr ^k (G) defined for usualk-colorings. The results reflect the relationship betweenr ^k (G) andr _loc ^k (G) for certain classes of graphs.This research was done while under an IREX grant.     

On the essential dimension of cyclic <Emphasis Type="Italic">p</Emphasis>-groups

Let p be a prime number, let K be a field of characteristic not p, containing the p-th roots of unity, and let r≥1 be an integer. We compute the essential dimension of ℤ/p ^r ℤ over K (Theorem 4.1). In particular, i) We have ed_ℚ(ℤ/8ℤ)=4, a result which was conjectured by Buhler and Reichstein in 1995 (unpublished). ii) We have ed_ℚ(ℤ/p ^r ℤ)≥p ^r-1.