Font Size: a A A

Research On Some Algorithms For New-Type Cryptographic Hard Problems

Posted on:2016-10-13Degree:DoctorType:Dissertation
Country:ChinaCandidate:M N WangFull Text:PDF
GTID:1108330482464985Subject:Information security
Abstract/Summary:PDF Full Text Request
Cryptography plays a key role in information security, both theoretically and tech-nically. The analysis and design of modern cryptosystems cannot exist without hard problems and algorithms to solve them.The traditional cryptographic schemes are mainly based on two hard problems:the integer factoring problem and the discrete logarithm problem. These schemes succeeded in pasting the tests with kinds of attacks, however, fail in recent years in the tests with the era of big data and post quantum, as people’s demand on information security is more strong and diverse. Cryptographers then resort to the new type of hard problem, such as the problems of decoding and lattices. New cryptographic schemes are booming, which brings a lot of nice and interesting properties in theory and application. But their security needs to be further considered. Therefore, it is now a hot research topic in the field of cryptography to study these new type problems and algorithms to solve them.In this dissertation, we focus on some algorithms for new-type cryptographic hard problems. Our contributions can be summarized as follows:1. We propose a new algorithm for decoding random linear codes that performs better when the memory is constrained.The decoding of random linear codes is one of the most fundamental problems in both computational complexity theory and algorithmic cryptanalysis. Specifically, the best attacks known against existing code-based cryptosystems, such as McEliece, are un-structural, i.e., these attacks directly use generic decoding algorithms that treat the hidden binary codes as random linear codes. This topic is also attracting increasing interest in a post-quantum context as this area becomes increasingly active. In an attempt to solve this problem, several algorithms and their variants have recently been proposed, with increasingly lower time complexities. However, their memory complexities, which are even more important in practice for real attacks, are neglected.In this dissertation, we consider the performance of information set decoding (ISD) algorithms for the problem of syndrome decoding for random binary linear codes with restricted memory. Using Finiasz and Sendrier’s standard framework for ISD algorithms, we propose an exact algorithm that performs better when the memory is constrained; also this improvement can be mathematically proven.From a practical standpoint, our approach can yield good time complexities for any given space bound, hence providing a good measure of the effectiveness of a cryptanalytic attack on code-based cryptosystems. Moreover, this paper gives better time-memory tradeoff in the code-based problem, which is significant in theoretical computer science.2. We present some useful properties on random integer lattices and one of their applications in cryptanalysis.Algorithms for solving hard lattice problems have been studied extensively as im-portant tools for cryptanalysis of public-key cryptosystems for a long time. Moreover, in recent years, numerous important cryptography applications, such as fully homomorphic encryptions, noisy multilinear maps, etc., have been realized by latticed based cryptosys-tems, making the study of hard lattice problems and their algorithms a more and more trendy topic.In this dissertation, we analyze several properties on random integer lattices which are closely related to the security of cryptosystems. Our research indicates that with high probability, the intersection of random integer lattices keeps the dimension of lattices while enlarging their volumes. And this corresponds to the needs of approximate algo-rithms for hard lattice problems in cryptanalysis, and simultaneously to the condition of broadcast attacks.As an application, we give a further analysis to the broadcast attacks on the GGH cryptosystem by Plantard et al. on ACNS 2009. According to the current approxima-tion factors of algorithms for hard lattice problem, we compute the number of instances needed in the attacks, hence explain the heuristic success of Plantard’s attacks. As many other cutting-edge cryptographic constructions, like some fully homomorphic encryption propositions, are made using the same principle as GGH, our methods and conclusions are valuable in estimating their security and practicability.3. We give a theoretical investigation to the performance of Paar’s algorithm for solving the Shortest Linear Program (SLP) problem in F2.The SLP problem is as follows:Given a set of linear forms E over a field F, which can be represented by a matrix, find the shortest linear program, which does not allow for the multiplication of variables, to compute E. This problem originates in computability logic and theoretical computer science, and has recently in 2012 been proven to be NP-hard by Boyar et al.When the field is F2, finding the shortest linear program is equivalent to finding the circuit that consists of only XOR gates and minimizing the number used. It is also one of the most important and common problems in the design and implementation of com-munication systems. And the most successful algorithm that has been used to address this problem was introduced by Paar in 1999. Engineers and researchers have experi-mentally demonstrated that Paar’s algorithm is capable of providing good performance. However, the algorithm is still considered to be heuristic because there is a lack of theo-retical analysis; such theoretical analysis is recognized as an important and open research problem.In this dissertation, the approximation factors of Paar’s algorithm for important in-stances with row weight parameters d=3 and 4 are obtained in rigorous mathematical terms. In addition, to provide a comparison with trivial implementations that do not use such an optimization, a lower bound on the minimum circuit size is obtained via tech-niques of combinatorics. Our analysis demonstrates in a thorough manner that Paar’s algorithm is substantially superior.
Keywords/Search Tags:decoding of random linear codes, memory constraint, intersection of ran— dom integer lattices, GGH cryptosystem, Shortest Linear Program, Paar’s algorithm
PDF Full Text Request
Related items