More Practical Provable-Security Theory In Symmetric Cryptography

For a practical symmetric cryptosystem or cryptographic structure,we want to determine how much security it can provides.In general,there are two different technical methods,namely cryptanalysis and provable-security analysis.These two different technical methods will give the upper and lower security bounds of the research object respectively.Cryptanalysis can be further subdivided into specific attacks and general attacks.More concretely,specific attack usually analyzes the real ciphers whose details of implementations and algorithms should be considered during the attack.While generic attack is closely related to the provable-security analysis,and its research object is generally an abstract cryptographic structure.In such a structure,we do not consider too much details of its implementation.Correspondingly,the provable security analysis in symmetric cryptography aims to explain the inherent security of a cryptosystem or cryptographic structure from a theoretical perspective.A commonly used research method is to abstract the actual cryptosystem or structure into a reasonable theoretical model,and then analyze the security of such a theoretical model.Generally,this kind of theoretical model is defined under some cryptographic assumptions,such as assuming that its underlying components are independent random functions/permutations and so on.Unfortunately,these cryptographic assumptions are often too idealistic,which leads to a huge gap with the real situation.Particularly,there are two kinds of common problems:one is that the underlying components are independent of each other,and this assumption is seriously out of line with the actual ciphers.The other is that some important provable-security results in symmetric cryptography are only obtained under the information-theoretic model,which are of little significance to the actual ciphers.In order to develop more theories and technologies for overcoming the above two kinds of problems,this paper studies in-depth the following two subjects:1.Tight security analyasis of 3KACSP construction.In this subject,we systematically study the key-alternation cipher construction in which all round permutations are the same(named KACSP).It is actually a common method to construct block cipher in reality.In order to analyze such construction,we propose a new representation to better describe its inherent mathematical problems.Based on the new representation,we abstract a new type of combinatorial problems.Actually,the security of the construction can be reduced to solving such type of combinatorial problems.Of course,we also propose a general solution framework,which can theoretically solve all instances of such type of combinatorial problems.Finally,through using the general framework,we successfully obtain the tight security bound of 3-round KACSP construction under the random permutation model.This is the first tight security bound on a more than 2-round KAC construction with dependency.2.Constructing the counter-examples of Feistel-type constructions with respect to nCPA-to-CPA security-amplification problem.In this subject,we systematically study the security amplification of nCPA-to-CPA problem in the computational setting,and successfully give two negative results about the Feistel-type networks.Firstly,we review and analyze the existing counter-example results,and find that they lack common ideas and technologies to connect.Therefore,we and refine new concepts and a new way of thinking to characterize such counter-example results.Based on them,we propose a high-level framework for constructing counter-examples of nCPA-to-CPA security amplification problem.Such a framework greatly simplifies and extends the theory of constructing such kind of counter-examples.Using the above framework and some new findings of Feistel-type networks,we successfully construct a counterexample for a construction which is more complex than the existing results.Following the new concepts and techniques mentioned above,as well as the experience of constructing counterexamples for more complex structure,we study in-depth the construction of two existing counterexamples,and explain the underlying design-philosophy of the counter-example constructed by Maurer et al.(EUROCRYPT 2006)for the first time.All above work is of great significance for understanding adaptive security in the computational setting.