Santanu Sarkar

An acyclic edge-coloring of a graph is a proper edge-coloring without bichromatic (2-colored) cycles. The acyclic chromatic index of a graph G, denoted by a′(G), is the least integer k such that G admits an acyclic edge-coloring using k colors. Let Δ=Δ(G) denote the maximum degree of a vertex in a graph G. A complete bipartite graph with n vertices on each side is denoted by Kn,n. Basavaraju, Chandran and Kummini proved that a′(Kn,n)≥n+2=Δ+2 when n is odd. Basavaraju and Chandran provided an acyclic edge-coloring of Kp,p using p+2 colors and thus establishing a′(Kp,p)=p+2=Δ+2 when p is an odd prime. The main tool in their approach is perfect 1-factorization of Kp,p. Recently, following their approach, Venkateswarlu and Sarkar have shown that K2p−1,2p−1 admits an acyclic edge-coloring using 2p+1 colors which implies that a′(K2p−1,2p−1)=2p+1=Δ+2, where p is an odd prime. In this paper, we generalize this approach and present a general framework to possibly get an acyclic edge-coloring of Kn,n which possesses a perfect 1-factorization using n+2=Δ+2 colors. In this general framework, using number theoretic techniques, we show that Kp2,p2 admits an acyclic edge-coloring with p2+2 colors and thus establishing a′(Kp2,p2)=p2+2=Δ+2 when p is an odd prime.

MDS matrices are used in the design of diffusion layers in many block ciphers and hash functions due to their optimal branch number. But MDS matrices, in general, have costly implementations. So in search for efficiently implementable MDS matrices, there have been many proposals. In particular, circulant, Hadamard, and recursive MDS matrices from companion matrices have been widely studied. In a recent work, recursive MDS matrices from sparse DSI matrices are studied, which are of interest due to their low fixed cost in hardware implementation. In this paper, we present results on the exhaustive search for (recursive) MDS matrices over GL(4, F2). Specifically, circulant MDS matrices of order 4, 5, 6, 7, 8; Hadamard MDS matrices of order 4, 8; recursive MDS matrices from companion matrices of order 4; recursive MDS matrices from sparse DSI matrices of order 4, 5, 6, 7, 8 are considered. It is to be noted that the exhaustive search is impractical with a naive approach. We first use some linear algebra tools to restrict the search to a smaller domain and then apply some space-time trade-off techniques to get the solutions. From the set of solutions in the restricted domain, one can easily generate all the solutions in the full domain. From the experimental results, we can see the (non) existence of (involutory) MDS matrices for the choices mentioned above. In particular, over GL(4, F2), we provide companion matrices of order 4 that yield involutory MDS matrices, circulant MDS matrices of order 8, and establish the nonexistence of involutory circulant MDS matrices of order 6, 8, circulant MDS matrices of order 7, sparse DSI matrices of order 4 that yield involutory MDS matrices, and sparse DSI matrices of order 5, 6, 7, 8 that yield MDS matrices. To the best of our knowledge, these results were not known before. For the choices mentioned above, if such MDS matrices exist, we provide base sets of MDS matrices, from which all the MDS matrices with the least cost (with respect to d-XOR and s-XOR counts) can be obtained. We also take this opportunity to present some results on the search for sparse DSI matrices over finite fields that yield MDS matrices. We establish that there is no sparse DSI matrix S of order 8 over F<>2<>8 such that S<>8<> is MDS.

In FSE 2015, Armknecht et al. proposed a new technique to design stream ciphers, which involves repeated use of keybits in each round of the keystream bit generation. This technique showed the possibility to design stream ciphers where the internal state size is significantly lower than twice the key size. They proposed a new cipher based on this idea, named Sprout. But soon Sprout was proved to be insecure. In Crypto 2015, Lallemand et al. proposed an attack which was 2 10 times faster than the exhaustive search. But the new idea used in Sprout showed a new direction in the design of stream cipher, which led to the proposal of several new ciphers with small size of internal state. Fruit is a recently proposed cipher where both the key size and the state size are 80. In this paper, we attack full round Fruit by a divide-and-conquer method. Our attack is equivalent to 2 74.95 many Fruit encryptions, which is around 16.95 times faster than the average exhaustive key search. Our idea also works for the second version of Fruit.

In Crypto 1996, the Hidden Number Problem was introduced by Boneh and Venkatesan. Howgrave-Graham, Nguyen and Shparlinski (Mathematics of Computation 2003) generalized this problem and called it Hidden Number Problem with Hidden Multiplier (HNPHM). It has application in security analysis of timed-release crypto. They proposed a polynomial time algorithm to solve HNPHM. They showed that one can solve it if absolute error is less than m0.20 for some positive integer m. They improved this bound up to m0.25 heuristically. It was also proved that one can not solve HNPHM if error is larger than m0.5. In this paper, we show that one can solve HNPHM in polynomial time heuristically if error is bounded by m0.5.

Differential Fault Attack (DFA) considers injection of faults and the most general set-up should take care of faults at random location and random time. Then one should be able to identify the exact location as well as the exact timing of the fault (including the multi bit ones) with the help of fault signatures. In this paper we solve the problem of DFA under a general frame-work, introducing the idea of probabilistic signatures. The method considers the Maximum Likelihood approach related to probability distributions. Our techniques subsume all the existing DFAs against the Grain family, MICKEY 2.0 and Trivium. In the process we provide improved fault attacks for all the versions of Grain family and also for MICKEY 2.0. Our generalized method successfully takes care of the cases where certain parts of the keystream bits are missing (this situation may arise for authentication purpose). In particular, we show that the unsolved problem of identifying the faults in random time for Grain 128a can be solved in this manner. Moreover, for MICKEY 2.0, our method not only provides improvement in fault identification probability but also reduces the required faults by 60 %, compared to the best known result.

One generic model of stream cipher considers updating the states and then combining the state bits to produce the key-stream. In case there are biases in the state bits, that may be reflected on the key-stream bits resulting certain weaknesses (distinguisher and/or key recovery) of the cipher. In this context, we study the state biases as well as key-stream biases with great details. We first experiment with cube testers and heuristically obtain several distinguishers for Trivium running more than 800 rounds (maximum 829) with cube sizes not exceeding 27. Further, we apply our techniques to analyze Trivia-SC (the stream cipher used in TriviA-ck AEAD scheme, selected in second round of CAESAR competition) and obtain distinguishers till 950 rounds with a cube size of 25 only. On Trivia-SC, our results refute certain claims made by the designers against both cube and slide attacks. Our detailed empirical analysis provides new results in reduced-round cryptanalysis of Trivium and Trivia-SC.

Recently Sarkar (DCC 2014) has proposed a new attack on small decryption exponent when RSA Modulus is of the form N=prq for r≥2. This variant is known as Prime Power RSA. The work of Sarkar improves the result of May (PKC 2004) when r≤5. In this paper, we improve the work of Sarkar when 2

Salsa and ChaCha are well known names in the family of stream ciphers. In this paper, we first revisit the existing attacks on these ciphers. We first perform an accurate computation of the attack complexities of the existing technique instead of the estimation used in previous works. This improves the complexity by some margin. The differential attacks using probabilistic neutral bits against ChaCha and Salsa involve two probability biases: Forward probability bias (ϵd) and backward probability bias (ϵa). In the second part of the paper, we suggest a method to increase the backward probability bias, which helps reduce the attack complexity. Finally, we focus on the design principle of ChaCha. We suggest a slight modification in the design of this cipher as a countermeasure of the differential attacks against it. We show that the key recovery attacks proposed against ChaCha will not be effective on this modified version.

RC4 has attracted many cryptologists due to its simple structure. In [9], Paterson, Poettering and Schuldt reported the results of a large scale computation of RC4 biases. Among the biases reported by them, we try to theoretically analyze a few which show very interesting visual patterns. We first study the bias which relates the key stream byte, where k is the first byte of the secret key. We then present a generalization of the Roos bias. In 1995, Roos observed the bias of initial bytes S of the permutation after KSA towards f. Here we study the probability of S. Our generalization provides a complete correlation between z i. We also analyze the key-keystream relation z i = f i - 1 which was studied by Maitra and Paul [6] in FSE 2008. We provide more accurate formulas for the probability of both z i = i - f i {z-{i}=i-f-{i}} and z i = f i - 1 {z-{i}=f-{i-1}} for different i's than the existing works.

An acyclic edge-coloring of a graph is a proper edge-coloring without bichromatic (2-colored) cycles. The acyclic chromatic index of a graph G, denoted by a′(G), is the least integer k such that G admits an acyclic edge-coloring using k colors. Let Δ=Δ(G) denote the maximum degree of a vertex in a graph G. A complete bipartite graph with n vertices on each side is denoted by Kn,n. Basavaraju, Chandran and Kummini proved that a′(Kn,n)≥ n+2=Δ+2 when n is odd. Basavaraju and Chandran showed that a′(Kp,p) ≤p+2 which implies a′(Kp,p)=p+2=Δ+2 when p is an odd prime, and the main tool in their proof is perfect 1-factorization of Kp,p. In this paper we study the case of K2p-1,2p-1 which also possess perfect 1-factorization, where p is odd prime. We show that K2p-1,2p-1 admits an acyclic edge-coloring using 2p+1 colors and so we get a′(K2p-1,2p-1)=2p+1=Δ+2 when p is an odd prime.