Register synthesis for multi-sequences has significance for the security of word-oriented stream ciphers. Feedback with carry shift registers (FCSRs) are promising alternatives to linear feedback shift registers for t...
详细信息
Register synthesis for multi-sequences has significance for the security of word-oriented stream ciphers. Feedback with carry shift registers (FCSRs) are promising alternatives to linear feedback shift registers for the design of stream ciphers. In this paper, we solve the FCSR synthesis problem for multi-sequences by two rational approximation algorithms using lattice theory. One is based on the latticereduction greedy algorithm proposed by Nguyen and Stehl, (ACM Trans algorithms (TALG) 5(4):46, 2009). The other is based on the LLL algorithm which is a polynomial time latticereductionalgorithm. Both of these rational approximation algorithms can find the smallest common FCSR for a given multi-sequence but with different numbers of known terms. When the number of sequences within the multi-sequence is less than or equal to 3, the former is suggested because it has better time complexity and fewer terms are needed. Otherwise, the latter will have better time complexity.
In this paper. we will report practical modifications of the side-channel analysis to (EQDSA [1], [2], [5], [34] that Leadbitter et al. have proposed in [16]. To apply the analyses, we assume that the window method is...
详细信息
In this paper. we will report practical modifications of the side-channel analysis to (EQDSA [1], [2], [5], [34] that Leadbitter et al. have proposed in [16]. To apply the analyses, we assume that the window method is used in the exponentiation or elliptic curve (EC) scalar multiplication and the side-channel information described in Sect. 3.2 can be collected. So far, the method in [16] hasn't been effective when the size q of a cyclic group used in (EQDSA is 160 bit long and the window size w < 9. We show that the modified method we propose in this paper is effective even when q is 160 bit long and w = 4. This shows that our method is effective for various practical implementations, e.g., that in resource restricted environment like IC card devises. First, we estimate the window size w necessary for the proposed analyses (attacks) to succeed. Then by experiment of the new method, we show that private keys of (EQDSA can be obtained under the above assumptions, in practical time and with sufficient success rate. The result raises the necessity of countermeasures against the analyses (attacks) in the window method based implementation of (EC)DSA.
In this paper we develop a new multi-dimensional continued fraction algorithm and three known multi-dimensional continued fraction algorithms from the latticebasisreduction multisequence synthesis (LBRMS) algorithm ...
详细信息
In this paper we develop a new multi-dimensional continued fraction algorithm and three known multi-dimensional continued fraction algorithms from the latticebasisreduction multisequence synthesis (LBRMS) algorithm with respect to the different choice of a parameter and so a continued fraction expansion is associated with a basis transformation. The new algorithm is similar to Dai's continued fraction algorithm [Z.D. Dai, K.P. Wang, D.F. Ye, m-Continued fraction algorithm on multi-Laurent series, Acta Arith. (2006) 1-21] but improves the latter effectively. (C) 2008 Elsevier Inc. All rights reserved.
Recent developments in stream ciphers point towards an interest in word-based or vectorized stream ciphers. Such stream ciphers suggest the study of the joint linear complexity of multisequences. In this paper, using ...
详细信息
Recent developments in stream ciphers point towards an interest in word-based or vectorized stream ciphers. Such stream ciphers suggest the study of the joint linear complexity of multisequences. In this paper, using the first author's multisequence linear feedback shift-register synthesis algorithm based on a lattice basis reduction algorithm in function fields, we present a method to determine the value of N-n((m)) (L), the number of in-fold multisequences of length n over a finite field F-q with nth joint linear complexity L. Furthermore, a closed-form expression for N-n((m)) (L) and formulas for the expected value of the joint linear complexity and its variance are given when m = 2. (c) 2005 Elsevier Inc. All rights reserved.
In this paper, we will report practical modifications of the side-channel analysis to (EC)DSA [1,2,4,31] that Leadbitter et al. have proposed in [12]. To apply the analyses, we assume that the window method is used in...
详细信息
ISBN:
(纸本)3540310126
In this paper, we will report practical modifications of the side-channel analysis to (EC)DSA [1,2,4,31] that Leadbitter et al. have proposed in [12]. To apply the analyses, we assume that the window method is used in the exponentiation (EC scalar multiplication) calculation and the side-channel information described in Section 2 can be collected. So far, the method in [121 haven't been effective when q is 160 bit long and the window size w < 9. We show that the modified method we propose in this paper is effective even when q is 160 bit long and w = 4, that is, in the case of frequent implementation. First, we estimate the window size w necessary for the proposed analyses (attacks) to succeed, Then by experiment of the new method, we show that private keys of (EC)DSA can be obtained under the above assumptions, in practical time and with sufficient success rate. The result raises the necessity of countermeasures against the analyses (attacks) in the window method based implementation of (EC)DSA.
A latticebasisreduction multisequence synthesis (LBRMS) algorithm was presented with a new, intuitive and vector-form model. In this correspondence, a refined version of the LBRMS algorithm is deduced, from which Ma...
详细信息
A latticebasisreduction multisequence synthesis (LBRMS) algorithm was presented with a new, intuitive and vector-form model. In this correspondence, a refined version of the LBRMS algorithm is deduced, from which Massey's conjectured algorithm can be derived. Moreover, if we modify the lattice basis reduction algorithm used in the LBRMS algorithm, a new synthesis algorithm is deduced, which is equivalent to the generalization of the Berlekamp-Massey algorithm proposed by Feng and Tzeng. Therefore, the LBRMS algorithm provides a unified approach to the multisequence shift-register synthesis problem.
We propose a general polynomial time algorithm to find small integer solutions to systems of linear congruences. We use this algorithm to obtain two polynomial time algorithms for reconstructing the values of variable...
详细信息
暂无评论