基于Nonce重用的ACORN v3状态恢复攻击

基于差分代数方法,利用猜测确定技术给出了Nonce重用两次情况下ACORN v3的状态恢复攻击,攻击所需的计算复杂度为2122.5c,数据复杂度和存储复杂度可忽略不计,其中c是求解线性方程组的复杂度。针对Nonce多次重用时的情形进行了分析,发现ACORN v3较复杂的滤波函数,使由密钥流直接提取关于内部状态线性方程的方法变得不可行,从而有效规避了通过增加Nonce重用次数来显著降低攻击复杂度的安全风险。

DCCS:A General-Purpose Distributed Cryptographic Computing System

Distributed cryptographic computing system plays an important role since cryptographic computing is extremely computation sensitive. However, no general cryptographic computing system is available. Grid technology can give an efficient computational support for cryptographic applications. Therefore, a general-purpose grid-based distributed computing system called DCCS is put forward in this paper. The architecture of DCCS is simply described at first. The policy of task division adapted in DCCS is then presented. The method to manage subtask is further discussed in detail. Furthermore, the building and execution process of a computing job is revealed. Finally, the details of DCCS implementation under Globus Toolkit 4 are illustrated.

Linearization of Multi-Valued Nonlinear Feedback Shift Registers

Nonlinear feedback shift registers(NFSRs) have been used in many stream ciphers for cryptographic security. The linearization of NFSRs is to describe their state transitions using some matrices. Such matrices are called their state transition matrices. Compared to extensive work on binary NFSRs, much less work has been done on multi-valued NFSRs. This paper uses a semi-tensor product approach to investigate the linearization of multi-valued NFSRs, by viewing them as logical networks. A new state transition matrix is found for a multi-valued NFSR, which can be simply computed from the truth table of its feedback function. The new state transition matrix is easier to compute and is more explicit than the existing results. Some properties of the state transition matrix are provided as well, which are helpful to theoretically analyze multi-valued NFSRs.

On Implementing the Symbolic Preprocessing Function over Boolean Polynomial Rings in Gr?bner Basis Algorithms Using Linear Algebra

Some techniques using linear algebra was introduced by Faugère in F4 to speed up the reduction process during Gr?bner basis computations.These techniques can also be used in fast implementations of F5 and some other signature-based Gr?bner basis algorithms.When these techniques are applied,a very important step is constructing matrices from critical pairs and existing polynomials by the Symbolic Preprocessing function(given in F4).Since multiplications of monomials and polynomials are involved in the Symbolic Preprocessing function,this step can be very costly when the number of involved polynomials/monomials is huge.In this paper,multiplications of monomials and polynomials for a Boolean polynomial ring are investigated and a specific method of implementing the Symbolic Preprocessing function over Boolean polynomial rings is reported.Many examples have been tested by using this method,and the experimental data shows that the new method is very efficient.

Reflections on the security proofs of Boneh-Franklin identity-based encryption scheme

In this paper, we first review the existing proofs of the Boneh-Franklin identity-based encryption scheme (BF-IBE for short), and show how to admit a new proof by slightly modifying the specifications of the hash functions of the original BF-IBE. Compared with prior proofs, our new proof provides a tighter security reduction and minimizes the use of random oracles, thus indicates BF-IBE has better provable security with our new choices of hash functions. The techniques developed in our proof can also be applied to improving security analysis of some other IBE schemes. As an independent technical contribution, we also give a rigorous proof of the Fujisaki-Okamoto (FO) transformation in the case of CPA-to-CCA, which demonstrates the efficiency of the FO-transformation (CPA-to-CCA), in terms of the tightness of security reduction, has long been underestimated. This result can remarkably benefit the security proofs of encryption schemes using the FO-transformation for CPA-to-CCA enhancement.

Algebraic-Differential Attacks on a Family of Arithmetization-Oriented Symmetric Ciphers

Motivated by applications in advanced cryptographic protocols,research on arithmetizationoriented symmetric primitives has been rising in the field of symmetric cryptography in recent years.In this paper,the authors focus on on the collision attacks for a family of arithmetization-oriented symmetric ciphers GMiMCHash.The authors firstly enhance the algebraically controlled differential attacks proposed by introducing more variables.Then,combining algebraic attacks and differential attacks,the authors propose algebraic-differential attacks on GMi MCHash.This attack method is shown to be effective by experiments on toy versions of GMi MCHash.The authors further introduce some tricks to reduce the complexities of algebraic-differential attacks and improve the success probability of finding collisions.

RECTANGLE: a bit-slice lightweight block cipher suitable for multiple platforms

In this paper, we propose a new lightweight block cipher named RECTANGLE. The main idea of the design of RECTANGLE is to allow lightweight and fast implementations using bit-slice techniques. RECTANGLE uses an SP-network. The substitution layer consists of 16 4 × 4 S-boxes in parallel. The permutation layer is composed of 3 rotations. As shown in this paper, RECTANGLE offers great performance in both hardware and software environment, which provides enough flexibility for different application scenario. The following are3 main advantages of RECTANGLE. First, RECTANGLE is extremely hardware-friendly. For the 80-bit key version, a one-cycle-per-round parallel implementation only needs 1600 gates for a throughput of 246 Kbits/s at100 k Hz clock and an energy efficiency of 3.0 p J/bit. Second, RECTANGLE achieves a very competitive software speed among the existing lightweight block ciphers due to its bit-slice style. Using 128-bit SSE instructions,a bit-slice implementation of RECTANGLE reaches an average encryption speed of about 3.9 cycles/byte for messages around 3000 bytes. Last but not least, we propose new design criteria for the RECTANGLE S-box.Due to our careful selection of the S-box and the asymmetric design of the permutation layer, RECTANGLE achieves a very good security-performance tradeoff. Our extensive and deep security analysis shows that the highest number of rounds that we can attack, is 18(out of 25).

A Note on Rotation Symmetric S-boxes

This paper is twofold. The first is devoted to study a class of quadratic rotation symmetric S-boxes(RSSBs) which was presented by Gao G, et al., Constructions of quadratic and cubic rotation symmetric bent functions, IEEE Transactions on Information Theory, vol. 58, no. 7, pp. 4908 –4913, 2012, by decomposing a class of cubic rotation symmetric bent functions. The authors obtain its nonlinearity and differential uniformity of such class of S-boxes. In particular, the compositional inversion of the class of rotation symmetric S-boxes is also presented. Then the authors introduce a steepest-descent-like search algorithm for the generation of RSSBs. The algorithm finds 5,6,7,8-bit RSSBs with very good cryptographic properties which can be applied in designing cryptographical algorithms.

Speeding Up the GVW Algorithm via a Substituting Method

The GVW algorithm is an effcient signature-based algorithm for computing Gr?bner bases.In this paper, the authors consider the implementation of the GVW algorithm by using linear algebra,and speed up GVW via a substituting method. As it is well known that, most of the computing time of a Gr?bner basis is spent on reductions of polynomials. Thus, linear algebraic techniques, such as matrix operations, have been used extensively to speed up the implementations. Particularly, one-direction(also called signature-safe) reduction is used in signature-based algorithms, because polynomials(or rows in matrices) with larger signatures can only be reduced by polynomials(rows) with smaller signatures. The authors propose a new method to construct sparser matrices for signature-based algorithms via a substituting method. Speci?cally, instead of only storing the original polynomials in GVW, the authors also record many equivalent but sparser polynomials at the same time. In matrix construction, denser polynomials are substituted by sparser equivalent ones. As the matrices get sparser, they can be eliminated more effciently. Two speci?cal algorithms, Block-GVW and LMGVW, are presented, and their combination is the Sub-GVW algorithm. The correctness of the new proposed method is proved, and the experimental results demonstrate the effciency of this new method.

Constructing parallel long-message signcryption scheme from trapdoor permutation

A highly practical parallel signcrypUon scheme named PLSC from trapdoor permutations （TDPs for short） was built to perform long messages directly. The new scheme follows the Idea ＂scramble all, and encrypt small＂, using some scrambling operation on message m along with the user＇s Identities, and then passing, In paraliel, small parts of the scrambling result through corresponding TOPs. This design enables the scheme to flexibly perform long messages of arbitrary length while avoid repeatedly invoking TDP operations such as the CBC mode, or verbosely black-box composing symmetric encryption and slgncryption, resulting in noticeable practical sevlngs in both message bandwidth and efficiency. Concretely, the signcryptlon scheme requires exactly one computation of the ＂receiver＇s TDP＂ （for ＂encryptlon＂） and one Inverse computation of the ＂sender＇s TDP＂ （for ＂authentication＂）, which Is of great practical significance in directly performing long messages, since the major bottleneck for many public encryptlon schemes is the excessive computational overhead of performing TDP operations. Cutting out the verbosely repeated padding, the newly proposed scheme Is more efficient than a black-box hybrid scheme. Most importantly, the proposed scheme has been proven to be tightly semanUcaiiy secure under adaptive chosen clphertext attacks （iND-CCA2） and to provide integrity of clphertext （INT-CTXT） as well as non-repudiation in the random oracle model. All of these security guarantees are provided in the full multi-user, insider-security setting. Moreover, though the scheme is designed to perform long messages, it may also be appropriate for settings where It is Impractical to perform large block of messages （i.e. extremely low memory environments such as smart cards）.

A New Upper Bound on the Order of Affine Sub-families of NFSRs

Nonlinear feedback shift registers(NFSRs)are widely used as building blocks in the design of stream ciphers.Let NFSR(f)be an NFSR with the characteristic function f and let G(f)be the set of output sequences of NFSR(f).For a given NFSR(f),if there exists an affine Boolean function l such that G(l)?G(f),then G(l)is called an affine sub-family of NFSR(f).In this paper,by skillfully combining previous ideas,the authors give a new upper bound on the order of affine sub-families of NFSR(f).Compared with the four known bounds,the bound is better than three of them,and in some cases is also better than the rest one.

On enumeration of polynomial equivalence classes

The isomorphism of polynomials(IP),one of the hard problems in multivariate public key cryptography induces an equivalence relation on a set of systems of polynomials.Then the enumeration problem of IP consists of counting the numbers of different classes and counting the cardinality of each class that is highly related to the scale of key space for a multivariate public key cryptosystem.In this paper we show the enumeration of the equivalence classes containing ∑n-1 i=0 aiX2qi when char(Fq) = 2,which implies that these polynomials are all weak IP instances.Moreover,we study the cardinality of an equivalence class containing the binomial aX 2q i + bX 2qj(i=j) over Fqn without the restriction that char(Fq) = 2,which gives us a deeper understanding of finite geometry as a tool to investigate the enumeration problem of IP.

Analyzing Boolean Functions via Solving Parametric Polynomial Systems

In this paper,a new method to analyze Boolean functions is proposed.By this method,one can analyze the balancedness,the nonlinearity,and the input-output correlation of vectorial Boolean functions.The basic idea of this method is to compute the refined covers of some parametric Boolean polynomial systems which are equivalent to these problems.By a refined cover,the parameter space is divided into several disjoint components,and on each component,the parametric Boolean polynomial system has a fixed number of solutions.An efficient algorithm based on the characteristic set method to compute refined covers of parametric Boolean polynomial systems is presented.The experimental results about some instances generated from cryptanalysis show that this new method is efficient and can solve some instances which can not be solved in reasonable time by other methods.

Novel Ω-protocols for NP

Ω-protocols, introduced by Garay, Mackenzie and Yang, is a variant of S-protocols with online extractor which is a useful tool to overcome the nest effect in concurrent scenario. In this work, we construct an Ω-protocol for Hamiltonian cycle problem, and therefore, it allows us to present Ω-protocol for any NP relation. For most general NP relations, our construction of Ω-protocols is much more efficient than the informal one described by Garay et ah and we believe that the method for our construction may be of independent interest.