Cryptanalysis of WG-7 : a lightweight stream cipher

WG-7 is a stream cipher based on WG stream cipher and has been designed by Luo et al. (2010). This cipher is designed for low cost and lightweight applications (RFID tags and mobile phones, for instance). This paper addresses cryptographic weaknesses of WG-7 stream cipher. We show that the key stream generated by WG-7 can be distinguished from a random sequence after knowing 213.5 keystream bits and with a negligible error probability. Also, we investigate the security of WG-7 against algebraic attacks. An algebraic key recovery attack on this cipher is proposed. The attack allows to recover both the internal state and the secret key with the time complexity about 2/27.

Möbius transforms, coincident Boolean functions and non-coincidence property of Boolean functions

Boolean functions and their Möbius transforms are involved in logical calculation, digital communications, coding theory and modern cryptography. So far, little is known about the relations of Boolean functions and their Möbius transforms. This work is composed of three parts. In the first part, we present relations between a Boolean function and its Möbius transform so as to convert the truth table/algebraic normal form (ANF) to the ANF/truth table of a function in different conditions. In the second part, we focus on the special case when a Boolean function is identical to its Möbius transform. We call such functions coincident. In the third part, we generalize the concept of coincident functions and indicate that any Boolean function has the coincidence property even it is not coincident.

Active security in multiparty computation over black-box groups

Most previous work on unconditionally secure multiparty computation has focused on computing over a finite field (or ring). Multiparty computation over other algebraic structures has not received much attention, but is an interesting topic whose study may provide new and improved tools for certain applications. At CRYPTO 2007, Desmedt et al introduced a construction for a passive-secure multiparty multiplication protocol for black-box groups, reducing it to a certain graph coloring problem, leaving as an open problem to achieve security against active attacks. We present the first n-party protocol for unconditionally secure multiparty computation over a black-box group which is secure under an active attack model, tolerating any adversary structure Δ satisfying the Q 3 property (in which no union of three subsets from Δ covers the whole player set), which is known to be necessary for achieving security in the active setting. Our protocol uses Maurer’s Verifiable Secret Sharing (VSS) but preserves the essential simplicity of the graph-based approach of Desmedt et al, which avoids each shareholder having to rerun the full VSS protocol after each local computation. A corollary of our result is a new active-secure protocol for general multiparty computation of an arbitrary Boolean circuit.

Extensions of the cube attack based on low degree annihilators

At Crypto 2008, Shamir introduced a new algebraic attack called the cube attack, which allows us to solve black-box polynomials if we are able to tweak the inputs by varying an initialization vector. In a stream cipher setting where the filter function is known, we can extend it to the cube attack with annihilators: By applying the cube attack to Boolean functions for which we can find low-degree multiples (equivalently annihilators), the attack complexity can be improved. When the size of the filter function is smaller than the LFSR, we can improve the attack complexity further by considering a sliding window version of the cube attack with annihilators. Finally, we extend the cube attack to vectorial Boolean functions by finding implicit relations with low-degree polynomials.

Cryptanalysis of the LAKE hash family

We analyse the security of the cryptographic hash function LAKE-256 proposed at FSE 2008 by Aumasson, Meier and Phan. By exploiting non-injectivity of some of the building primitives of LAKE, we show three different collision and near-collision attacks on the compression function. The first attack uses differences in the chaining values and the block counter and finds collisions with complexity 233. The second attack utilizes differences in the chaining values and salt and yields collisions with complexity 242. The final attack uses differences only in the chaining values to yield near-collisions with complexity 299. All our attacks are independent of the number of rounds in the compression function. We illustrate the first two attacks by showing examples of collisions and near-collisions.

Energy-based positioning control of underactuated vehicles using manifold regulation

In this paper, we consider the problem of position regulation of a class of underactuated rigid-body vehicles that operate within a gravitational field and have fully-actuated attitude. The control objective is to regulate the vehicle position to a manifold of dimension equal to the underactuation degree. We address the problem using Port-Hamiltonian theory, and reduce the associated matching PDEs to a set of algebraic equations using a kinematic identity. The resulting method for control design is constructive. The point within the manifold to which the position is regulated is determined by the action of the potential field and the geometry of the manifold. We illustrate the performance of the controller for an unmanned aerial vehicle with underactuation degree two-a quadrotor helicopter.

Diophantine equations as a context for technology-enhanced training in conjecturing and proving

Solving indeterminate algebraic equations in integers is a classic topic in the mathematics curricula across grades. At the undergraduate level, the study of solutions of non-linear equations of this kind can be motivated by the use of technology. This article shows how the unity of geometric contextualization and spreadsheet-based amplification of this topic can provide a discovery experience for prospective secondary teachers and information technology students. Such experience can be extended to include a transition from a computationally driven conjecturing to a formal proof based on a number of simple yet useful techniques.

Basic finance made accessible in Excel 2007 : "the big 5, plus 2"

The basic principles and equations are developed for elementary finance, based on the concept of compound interest. The five quantities of interest in such problems are present value, future value, amount of periodic payment, number of periods and the rate of interest per period. We consider three distinct means of computing each of these five quantities in Excel 2007: (i) use of algebraic equations, (ii) by recursive schedule and the Goal Seek facility, and (iii) use of Excel's intrinsic financial functions. The paper is intended to be used as the basis for a lesson plan and contains many examples and solved problems. Comment is made regarding the relative difficulty of each approach, and a prominent theme is the systematic use of more than one method to increase student understanding and build confidence in the answer obtained. Full instructions to build each type of model are given and a complete set of examples and solutions may be downloaded (Examples.xlsx and Solutions.xlsx).

Images inside a reflecting spherical surface with possible application in astronomy

This report studies an algebraic equation whose solution gives the image system of a source of light as seen by an observer inside a reflecting spherical surface. The equation is looked at numerically using GeoGebra. Under the hypothesis that our galaxy is enveloped by a reflecting interface this becomes a possible model for many mysterious extra galactic observations.

Characterisations of extended resiliency and extended immunity of S-boxes

New criteria of extended resiliency and extended immunity of vectorial Boolean functions, such as S-boxes for stream or block ciphers, were recently introduced. They are related to a divide-and-conquer approach to algebraic attacks by conditional or unconditional equations. Classical resiliency turns out to be a special case of extended resiliency and as such requires more conditions to be satisfied. In particular, the algebraic degrees of classically resilient S-boxes are restricted to lower values. In this paper, extended immunity and extended resiliency of S-boxes are studied and many characterisations and properties of such S-boxes are established. The new criteria are shown to be necessary and sufficient for resistance against the divide-and-conquer algebraic attacks by conditional or unconditional equations.

Cryptanalysis of block ciphers with overdefined systems of equations

Several recently proposed ciphers, for example Rijndael and Serpent, are built with layers of small S-boxes interconnected by linear key-dependent layers. Their security relies on the fact, that the classical methods of cryptanalysis (e.g. linear or differential attacks) are based on probabilistic characteristics, which makes their security grow exponentially with the number of rounds N r r. In this paper we study the security of such ciphers under an additional hypothesis: the S-box can be described by an overdefined system of algebraic equations (true with probability 1). We show that this is true for both Serpent (due to a small size of S-boxes) and Rijndael (due to unexpected algebraic properties). We study general methods known for solving overdefined systems of equations, such as XL from Eurocrypt’00, and show their inefficiency. Then we introduce a new method called XSL that uses the sparsity of the equations and their specific structure. The XSL attack uses only relations true with probability 1, and thus the security does not have to grow exponentially in the number of rounds. XSL has a parameter P, and from our estimations is seems that P should be a constant or grow very slowly with the number of rounds. The XSL attack would then be polynomial (or subexponential) in N r> , with a huge constant that is double-exponential in the size of the S-box. The exact complexity of such attacks is not known due to the redundant equations. Though the presented version of the XSL attack always gives always more than the exhaustive search for Rijndael, it seems to (marginally) break 256-bit Serpent. We suggest a new criterion for design of S-boxes in block ciphers: they should not be describable by a system of polynomial equations that is too small or too overdefined.

Reduction of amplitude equations by the renormalization group approach

This article elucidates and analyzes the fundamental underlying structure of the renormalization group (RG) approach as it applies to the solution of any differential equation involving multiple scales. The amplitude equation derived through the elimination of secular terms arising from a naive perturbation expansion of the solution to these equations by the RG approach is reduced to an algebraic equation which is expressed in terms of the Thiele semi-invariants or cumulants of the eliminant sequence { Zi } i=1 . Its use is illustrated through the solution of both linear and nonlinear perturbation problems and certain results from the literature are recovered as special cases. The fundamental structure that emerges from the application of the RG approach is not the amplitude equation but the aforementioned algebraic equation. © 2008 The American Physical Society.

Threshold MACs

The power of sharing computation in a cryptosystem is crucial in several real-life applications of cryptography. Cryptographic primitives and tasks to which threshold cryptosystems have been applied include variants of digital signature, identification, public-key encryption and block ciphers etc. It is desirable to extend the domain of cryptographic primitives which threshold cryptography can be applied to. This paper studies threshold message authentication codes (threshold MACs). Threshold cryptosystems usually use algebraically homomorphic properties of the underlying cryptographic primitives. A typical approach to construct a threshold cryptographic scheme is to combine a (linear) secret sharing scheme with an algebraically homomorphic cryptographic primitive. The lack of algebraic properties of MACs rules out such an approach to share MACs. In this paper, we propose a method of obtaining a threshold MAC using a combinatorial approach. Our method is generic in the sense that it is applicable to any secure conventional MAC by making use of certain combinatorial objects, such as cover-free families and their variants. We discuss the issues of anonymity in threshold cryptography, a subject that has not been addressed previously in the literature in the field, and we show that there are trade-offis between the anonymity and efficiency of threshold MACs.

Language and literacy in mathematics: stepping stones or stumbling blocks in accelerating junior-secondary students

The authors have collaborated in the development and initial evaluation of a curriculum for mathematics acceleration. This paper reports upon the difficulties encountered with documenting student understanding using pen-and-paper assessment tasks. This leads to a discussion of the impact of students’ language and literacy on mathematical performance and the consequences for motivation and engagement as a result of simplifying the language in the tests, and extending student work to algebraic representations. In turn, implications are drawn for revisions to assessment used within the project and the language and literacy focus included within student learning experiences.

An algorithm for constructing Hjelmslev planes

Projective Hjelmslev planes and affine Hjelmslev planes are generalisations of projective planes and affine planes. We present an algorithm for constructing projective Hjelmslev planes and affine Hjelmslev planes that uses projective planes, affine planes and orthogonal arrays. We show that all 2-uniform projective Hjelmslev planes, and all 2-uniform affine Hjelmslev planes can be constructed in this way. As a corollary it is shown that all $2$-uniform affine Hjelmslev planes are sub-geometries of $2$-uniform projective Hjelmslev planes.