Dissertation and Thesis
Permanent URI for this communityhttp://164.52.219.250:4000/handle/10263/2146
Browse
10 results
Search Results
Item Mirror Theory and its Applications in Cryptography(Indian Statistical Institute, Kolkata, 2024-07) Saha, AbishankaThe indistinguishability security of a cryptographic construction refers to the maximum advantage of an interactive adversary to distinguish between the real and ideal world, where in the real world it interacts with the construction, and in the ideal world it interacts with its idealized counterpart. In the field of information-theoretic provable security, we bound this indistinguishability advantage by the statistical distance between the random variables representing the transcript of interaction in the real and ideal worlds, respectively. One of the most popular techniques in bounding the statistical distance is the H-Coefficient Technique introduced by J. Patarin, for which a set of transcripts is identified as good, and the probability of realizing such a good transcript in the real world is lower-bounded. For numerous constructions in practice, lower-bounding this real-world interpolation probability reduces to lower-bounding the number of solutions to a system of equations and non-equations over a field. The theory of achieving optimum lower bounds to a system of equations and non-equations is termed Mirror Theory by J. Patarin. Although several Mirror Theory statements have been conjectured and profusely used in beyond-birthday bound analysis of a multitude of constructions, the proofs of such statements are either non-existent or at least have significant non-verifiable gaps. In this thesis, we have presented the first simple verifiable proofs of several variants of Mirror Theory and applied them to security analyses of various cryptographic schemes. As our first contribution, we proved that the number of pairwise disjoint solutions to a system of bivariate equations over n-bit variables, such that no two equations share any common variable, is at least the average number of such solutions. This translates via the H-coefficient technique to the n-bit security for the sum of permutations PRF constructions. As our second contribution, we show that the number of pairwise disjoint solutions to a system of bivariate equations over n-bit variables, which even has quite a large block-maximality, is at least the average number of such solutions. Here block-maximality of a system of equations refers to the maximum number of variables that get determined when one variable is assigned a particular value. Note that, in our previous simpler result the block-maximality was just two. This translates via the H-coefficient technique to the n-bit security for several PRF constructions, like XORP[w], 2k-HtmB-p2, and the PRP construction, six-round Feistel network. As our third contribution, we have used a Mirror Theory statement in the tweakable permutation setting, where the variables are partitioned into two sets and solutions need to be pairwise disjoint within the two sets only, to prove 3n/4-bit security of the tweakable blockcipher construction paradigm, LRW+, proposed by us, that includes as subcases the CLRW2 and 4LRW1 constructions proposed in the seminal paper of Liskov, Rivest, and Wagner. The LRW+ paradigm was proposed to achieve beyond-birthday-bound security, as we have given a birthday-bound attack on the TNT or 3LRW1 construction, disproving the long-held belief that the latter is beyond-birthday-bound tweakable blockcipher. Finally, as our fourth contribution, we have given a lower bound to the number of solutions (which are pairwise disjoint within a partition of the variables) to a system of equations (need not be bivariate) where the solutions are not allowed to take values in certain forbidden sets. We have used this variant of Mirror Theory to prove optimal 3n/4-security of single key variants of double-block-hash-then-sum MAC constructions, like 1k-LightMAC+, 1k-PMAC+, and the PRF construction, sum of k Even-Mansour. Several of the security proofs mentioned above are indeed tight.Item Optimal Eavesdropping in Quantum Cryptography(Indian Statistical Institute,Kolkata, 2021-09) Acharyya, AtanuQuantum key distribution (QKD) has raised some promise for more secured communica- tion than its classical counterpart. It allows the legitimate parties to detect eavesdropping which introduces error in the channel. If disturbed, there are ways to distill a secure key within some threshold error-rate. The amount of information gained by an attacker is generally quantified by (Shannon) mutual information. Knowing the maximum amount of information that an intruder can gain is important for post-processing purposes, and we mainly focus on that side in the thesis. Rényi information is also useful especially when post-processing is considered. The scope of this thesis is to first describe some relevant ingredients for QKD and then study some open-ended issues. We mostly focus on the BB84 protocol and some issues relating optimal eavesdropping on it when each information-carrying particles are attacked individually. However, our results and techniques can also be applied for other protocols and different eavesdropping strategies. We felt a few other eavesdropping tech- niques worthy to analyze in that line, despite limitations to achieve newer results. First we study the optimal eavesdropping technique on the BB84 protocol and show that the optimal information can be achieved in infinitely many different ways to interact and measure the information-carriers. Although they are mathematically equivalent in some sense, that variety may help when designing the eavesdropping setup. However, it was not clear whether more such optimal interactions exist or not. This has lead us to derive them through a chain of necessary and sufficient conditions (NSC), which are shown to be in a one-to-one correspondence with the earlier interactions. In this process we arrive at a new NSC restricting attackers particles to a specific orienta- tion, establishing the geometry of the attack more explicitly than earlier. Some explicit connections are shown with other modes of gleaning information like cloning. Nevertheless, for practical purposes all an attacker requires is the evolution that en- tangles her ancilla with the senders particle, and the corresponding measurement that will lead her to optimal information gain. This is generally neglected in the literature as they exhibit a specific interaction. In our case, having infinitely many options to interact, we felt it better to address the issue of findings optimal evolutions. Overall, we have added more mathematical structures in the framework of optimal eavesdropping. We wanted to analyse the more generalized ways to attack, where a whole chunk of information-carrying particles can be evolved and then measured at a go. The process becomes complex to tackle when the chunks go bigger. Yet, we have explained the mathematical details of some of the existing results to point out the difficulties.Item Aspects of Index Calculus Algorithms for Discrete Logarithm and Class Group Computations(Indian Statistical Institute,Kolkata, 2021-09) Mukhopadhyay, MadhurimaThe thesis focuses on two problems: The discrete logarithm problem(DLP) and the class group com- putation problem. Besides the inherent mathematical appeal, both of these problems have strong cryp- tographical interest. Discrete Logarithm Problem The computation of discrete logarithms is known to be a hard problem in general. The intractability of the discrete logarithm problem has lead to schemes that revolutionized cryptography. The known algo- rithms for DLP can be categorised into two major categories, namely, generic algorithms which work in any group and index calculus algorithms which work in a special class of groups. It is known that Pollard's rho algorithm is the best generic algorithm to compute discrete logarithm. The complete discrete logarithm in a nite eld is found by applying Pollard's rho in subproblems that may arise when index calculus algorithms are applied. The tag tracing variant of Pollard's rho is a highly e cient algorithm. We have intertwined the technique of Montgomery multiplication with tag tracing in elds of prime order. As a result, the expensive modular reductions are completely replaced by divisions by a suitable power of two. The implementation of these divisions is a cakewalk as it is just right shift operations. In doing this, we do not compromise with any advantage that tag tracing o ered. The essential di erence is instead of doing eld multiplication after a certain number of steps we just do a Montgomery multiplication after the same number of steps. The net result of our work is that the speedup is huge without any additional costs of memory or time. We next focus on general medium prime elds. We perform a record discrete log computation for a eld with 22-bit characteristic and 1051-bit size. It successfully combats the challenge to perform a larger discrete logarithm computation for a medium prime case eld than what had been reported earlier with- out losing generality. The work also reports progress in discrete logarithm computation for the general medium prime case using the function eld sieve algorithm. Fields considered earlier with large sizes en- joyed the advantage o ered by the Kummer extension property. This made the factor base size small and 2 1 descent which is one of the last steps of the index calculus technique easier. In our case, the factor base is larger than what has been considered earlier. The di culty of 21 descent is also clearly visible. An increase in the size of the eld makes various steps of the function eld sieve more complicated. Our study delves into these di culties. The linear algebra step along with descent form the main stumbling blocks. Some previously known techniques have been analysed and implemented e ciently. The manner in which the various methods are used in our work is equally applicable for any general medium prime eld for performing future record computations, provided suitable computational resources are present. We next consider the problem of computing discrete logarithms with function eld sieve in Fpn for a small characteristic p and composite n. The last phase of the function eld sieve, namely the individual logarithm step itself again consist of two sub-steps of initial splitting and descent. The focus in this work is on the initial splitting phase. We have proposed a new algorithm for initial splitting in small characteristic elds of composite extension degree. It has been shown to be better than the other existing algorithms like Waterloo algorithm and Guillevic's initial splitting algorithm. Implementation of the new algorithm has also been done. Our algorithm reduces the cost of generation of polynomials which are to be tested for smoothness. Additionally, our algorithm is completely parallelizable compared to some sort of semi-parallelism possible for Guillevic's algorithm. The usage of this algorithm is appropriate when attempting record discrete logarithm computations over such elds. Class Group Computation The class group computation problem is quite important and relevant as it provides information about the structure of multiplication in the eld. However, computationally it remains a di cult problem to date. Class group computation is one of the four major problems in computational algebraic number theory postulated by Zassenhaus (the others being computation of unit group, ring of integers, Galois group). Class groups are important both mathematically as well as cryptographically. We have introduced a technique to obtain practical speed up for relation collection in class group computations. We have done Magma implementations of both the new algorithm as well as the previous one given by G elin. Timing results con rm that there is indeed a substantial practical speed-up in relation collection by the new algorithm over G elin's algorithm.Item Optimal Eavesdropping in Quantum Cryptography(Indian Statistical Institute,Kolkata, 2021) Acharyya, AtanuItem Some studies on selected stream cipher, analysis, fault attack & related results(Indian Statistical Institute, Kolkata, 2015-02) Banik, SubhadeepItem Efficient and adaptively secure constructions of identity-based cyrptographic primitives(Indian Statistical Institute, Kolkata, 2015) Ramanna, Somindu ChayaItem A study on cryptographic key exchange protocols(Indian Statistical Institute, Kolkata, 2016) Singha, SubhadipItem Studies on verifiable secret sharing(Indian Statistical Institute, Kolkata, 2011) Singh, YograjItem Studies on public key and identity-based cryptographic primitives(Indian Statistical Institute, Kolkata, 2010) Jhanwar, Mahabir PrasadItem Blackbox reduction of some cryptographic constructions(Indian Statistical Institute, Kolkata, 2011-10) Bhattacharyya, Rishiraj