Paillier-based publicly verifiable (non-interactive) secret sharing

A verifiable secret sharing is a secret sharing scheme with an untrusted dealer that allows participants to verify validity of their own shares. A publicly verifiable secret sharing (PVSS) scheme is a verifiable secret sharing scheme that allows a third party to verify correctness of the distributed shares. We propose an efficient non-interactive PVSS scheme using Paillier additively homomorphic encryption system, and analyze its security in a model that we define in line with the classic semantic-security definition and offering stronger security compared to the previous models. We reduce security of our PVSS scheme to the well studied decisional composite residuosity assumption in this model.     

Error linear complexity measures for multisequences

Complexity measures for sequences over finite fields, such as the linear complexity and the k-error linear complexity, play an important role in cryptology. Recent developments in stream ciphers point towards an interest in word-based stream ciphers, which require the study of the complexity of multisequences. We introduce various options for error linear complexity measures for multisequences. For finite multisequences as well as for periodic multisequences with prime period, we present formulas for the number of multisequences with given error linear complexity for several cases, and we present lower bounds for the expected error linear complexity.     

Periodic multisequences with large error linear complexity

Generalizing the theory of k-error linear complexity for single sequences over a finite field, Meidl et al. (J. Complexity 23(2), 169–192 (2007)) introduced three possibilities of defining error linear complexity measures for multisequences. A good keystream sequence must possess a large linear complexity and a large k-error linear complexity simultaneously for suitable values of k. In this direction several results on the existence, and lower bounds on the number, of single sequences with large k-error linear complexity were proved in Meidl and Niederreiter (Appl. Algebra Eng. Commun. Comput. 14(4), 273–286 (2003)), Niederreiter (IEEE Trans. Inform. Theory 49(2), 501–505 (2003)) and Niederreiter and Shparlinski (In: Paterson (ed.) 9th IMA International Conference on Cryptography and Coding (2003)). In this paper we discuss analogous results for the case of multisequences. We also present improved bounds on the error linear complexity and on the number of sequences satisfying such bounds for the case of single sequences.     

On the direct construction of recursive MDS matrices

MDS matrices allow to build optimal linear diffusion layers in the design of block ciphers and hash functions. There has been a lot of study in designing efficient MDS matrices suitable for software and/or hardware implementations. In particular recursive MDS matrices are considered for resource constrained environments. Such matrices can be expressed as a power of simple companion matrices, i.e., an MDS matrix \(M = C_g^k\) for some companion matrix corresponding to a monic polynomial \(g(X) \in \mathbb {F}_q[X]\) of degree k. In this paper, we first show that for a monic polynomial g(X) of degree \(k\ge 2\), the matrix \(M = C_g^k\) is MDS if and only if g(X) has no nonzero multiple of degree \(\le 2k-1\) and weight \(\le k\). This characterization answers the issues raised by Augot et al. in FSE-2014 paper to some extent. We then revisit the algorithm given by Augot et al. to find all recursive MDS matrices that can be obtained from a class of BCH codes (which are also MDS) and propose an improved algorithm. We identify exactly what candidates in this class of BCH codes yield recursive MDS matrices. So the computation can be confined to only those potential candidate polynomials, and thus greatly reducing the complexity. As a consequence we are able to provide formulae for the number of such recursive MDS matrices, whereas in FSE-2014 paper, the same numbers are provided by exhaustively searching for some small parameter choices. We also present a few ideas making the search faster for finding efficient recursive MDS matrices in this class. Using our approach, it is possible to exhaustively search this class for larger parameter choices which was not possible earlier. We also present our search results for the case \(k=8\) and \(q=2^{16}\).     

Unimodular polynomial matrices over finite fields

Journal of Algebraic Combinatorics - We consider some combinatorial problems on matrix polynomials over finite fields. Using results from control theory, we give a proof of a result of Lieb, Jordan...     

Revisiting (nested) Roos bias in RC4 key scheduling algorithm

RC4 is one of the most popular stream cipher with wide industrial applications, it has received serious attention in cryptology literature in the last 2 decades. In 1995, Roos pointed out that the elements \(S_N[y]\) of the permutation \(S_N\) after the key scheduling algorithm for the first few values of y are biased to certain combinations of secret key bytes. These correlations were theoretically studied by Paul and Maitra (SAC, 2007). The formula for the correlation probabilities provided by them gives a wrong impression that the probabilities decrease as the value of y becomes larger, which is not true. In this paper, we point out some gaps in their analysis and present a detailed analysis of Roos bias. We provide a more accurate formula for the correlation probabilities. We further study nested Roos type biases and present comparison results. These types of biases are used to reconstruct key from the permutation \(S_N\) for better success probability.     

Remarks on the <Emphasis Type="Italic">k</Emphasis>-error linear complexity of <Emphasis Type="Italic">p</Emphasis><Superscript><Emphasis Type="Italic">n</Emphasis></Superscript>-periodic sequences

Recently the first author presented exact formulas for the number of 2 ⁿ -periodic binary sequences with given 1-error linear complexity, and an exact formula for the expected 1-error linear complexity and upper and lower bounds for the expected k-error linear complexity, k ≥ 2, of a random 2 ⁿ -periodic binary sequence. A crucial role for the analysis played the Chan–Games algorithm. We use a more sophisticated generalization of the Chan–Games algorithm by Ding et al. to obtain exact formulas for the counting function and the expected value for the 1-error linear complexity for p ⁿ -periodic sequences over prime. Additionally we discuss the calculation of lower and upper bounds on the k-error linear complexity of p ⁿ -periodic sequences over .