Public-key cryptography (PKC) is an important branch of cryptography. The diversity of PKC scheme constructions and security proofs make the research in PKC a challenging task. This paper first summarizes the fundamental knowledge, which is required for provable security in the PKC settings, including basic concepts, mathematical foundation, easy and hard problems, algorithms, security models, and security reduction. Such knowledge is essential for the study of PKC scheme constructions and security proofs. This paper then presents the studies of methods for constructing a provably secure PKC schemes, including how to construct such a scheme, how to present security proofs, and how to construct such a scheme with provable security. 30 such schemes and their proofs for practices are illustrated. It also gives a summary of the way of thinking when studying PKC, which is helpful to further understand the techniques. This paper is expected to be helpful for the reader to understand how to construct provably secure public-key cryptographic schemes, especially for those with a weak cryptographic background.

Firstly, this paper analyzes the fault model and principle of differential fault attack. By using the differential inhomogeneity of S-boxes, this paper gives an optimization of differential fault analysis by establishing the corresponding relationship between input differentials, output differentials, and possible input values to improve the efficiency of differential fault attack. In this paper, the corresponding relationship for LBlock algorithm is established, which can be used to effectively reduce the value space of input values, and then quickly determine the corresponding extended key. For different fault values (input differentials), the corresponding output differences, and possible input values are not the same, there exists a set of binary relationships. Since the lightweight S-boxes are mostly 4*4 S boxes, there are fewer elements in the set and a small number of different false values are injected. By looking up the table, the only possible input value can be quickly identified by taking the intersection of possible input values. The optimization scheme is applied to the LBlock lightweight block cipher algorithm. In the last round of input, two 16-bit wide faults are recoverable to the last round key, and then the state is pushed one round back. In the second last round, by injecting 2 faults in 16-bit width, the second last round key can be recovered. According to the key expansion scheme, the recovery of two-round key reduces the computational complexity of recovering master key to 2^{19}.

Feistel structure is a widely used structure in iteration block cipher design, whose security attracts much research interests. Based on Feistel structure, there are various kinds of generalized constructions. Zheng et al. present three kinds of generalized Feistel structures in 1989, called Type-1, Type-2, and Type-3 Feistel structure respectively, which have the same advantage as the original Feistel structure, while having their own features. Dong Le et al. analyzed Type-1 Feistel structure with 3 sub-blocks by the meet-in-the-middle technique. At Inscrypt 2017, Deng Yuanhao et al. present a meet-in-the-middle attack on Type-1 Feistel structure with d(d>=4) sub-blocks. However, there is no generic key-recovery attack on Type-2 and Type-3 Feistel structure. This paper presents a special difference of this structure, and it is found that the possible number of differential characteristics is less than that in theory, which leads to a d+1 rounds distinguisher. Then this paper presents key recovery attacks on Type-3 Feistel structure based on this finding. For Type-3 Feistel structure with n bits blocks and d sub-blocks, a d+1 rounds distinguisher is launched. By prepending one round at the top of the distinguisher, a d+2 rounds key-recovery attack on Type-3 Feistel structure can be made possible. Moreover, all of the d-1 distinct subkeys in the first round can be recovered. The data complexity is 2^{n/2} chosen plaintexts, the memory complexity is 2^{(d-1)n/d} blocks, each block is n bits, and the time complexity is 2^{(d-1)n/d} times that of encryptions, which is the best known generic key recovery attack on Type-3 Feistel structure. The attack is valid if k>=n.

As an important branch of information hiding, digital watermarking has many characteristics, including security, robustness, concealment, etc. It is an effective method to protect copyright of relational data. When a data owner suspects that someone else is using the data without his authorization, the watermark can be extracted from the data to prove the copyright. However, most of those watermarking schemes for relational data have limitation on usage times of the watermark. In other words, the watermark can be used to claim copyright only once due to the exposure of the key and other secret parameters during the watermark detection process. In order to solve this problem, this study proposes a multi-verifiable reversible watermarking scheme for relational data. Watermark embedding algorithm, watermark detection algorithm, and data recovery algorithm are designed. The watermark detection process is controlled by relevant parameters to achieve multiple verifications. Difference expansion is used to achieve watermark reversibility. The relationship between the hidden ratio of the watermark and the ability to resist attacks are analyzed through experiment on the hidden ratio. Experiments on performance and various attacks show that the proposed scheme is feasible and robust.

Secure multi-party computation is a research hotspot in cryptography in recent years, and has become an important research direction. A millionaires' problem studied in this work is the most basic and important problem of secure multi-party computation, and its essence is a comparison issue about the size of two encrypted data. However, so far existing solutions are inefficient, and do not suit practical applications. Meanwhile, most existing schemes do not distinguish whether the two numbers are equal. Aiming at these issues, this study proposes a new $1-r$ encoding. A vector was constructed by applying this method and a given total ordered set to encode the confidential data, which guaranteed a one-to-one mapping between the confidential data and the vector. Based on this, the Millionaires’ problem can be transformed into product problem between two elements in the vector. The problem can be solved by computing the product to distinguish the size of two encrypted values. In addition, since the privacy of both parties needs to be protected, a new efficient protocol is designed to solve the Millionaires' problem by taking advantage of a homomorphic encryption algorithm; the security of the protocol, in the semi-honest model, is proven by using the method of simulation paradigm. The analysis indicated that, compared with the existing schemes, the new scheme is simple and efficient, and the comparison was more fine-grained. Furthermore, a new millionaires' problem protocol is designed providing authentication mechanism, and a protocol is designed which can query the data ranking in an ordered set.

Cloud storage of private data is an important branch of the Internet recently. Nevertheless, for private data, encrypting it before uploading can guarantee its privacy, while it will reduce the search efficiency. If the data is uploaded in plaintext, it will lose the security of data. The emergence of symmetric searchable encryption has driven the cloud storage to make a balance between security and efficiency, and users can upload their data safely without compromising searchability. However, the current symmetric searchable encryption is not impeccable, for example, it does not define the access-level for the data and has a single mode for users' permissions. This study combines symmetric searchable encryption with attribute-based encryption and proposes a scheme which possesses the functionalities of cipher storage, key-word searching, multi-level access, attribute-based decryption, and dynamic update. Experiment results show that the designed scheme has high efficiency, which can meet the requirements for application.

Lattice-based cryptography is a very hot research topic, it has the potential to resist quantum computer attacks, and has been in a repaid development. The security of this kind of schemes is based on the hard problems in Lattice, and to solve those problems requires efficient reduction algorithms. Researchers have developed various algorithms, such as LLL, BKZ, and the random sampling (RS) algorithm. This study mainly focuses on the random sampling algorithm and a number of its shortcomings and improves the RS algorithm. This paper presents a new local random sampling algorithm, called I-RS, which applies blocking and insert index. This algorithm improves the output by optimizing the qualities of Lattice bases, and is able to improve the length quality in O(n^{3}(k/6)^{k/4}) polynomial time, where the block size is 2k. Experiments suggest that this algorithm is better than the RS algorithm and the BKZ algorithm in terms of efficiency and stability. The smallest length of reduced basis is 80% of that of BKZ. And the approximation factor is below 0.95 of that of BKZ.

Rational cryptographic protocol is a new research direction of cryptology and game theory. It expands the research field of cryptographic protocol and game theory, and has become a research hotspot in the field of cryptography. In secure communication based on cryptography, whether the participants are honest or malicious, they will take a cost when they achieve the purpose of communication. The rational participants in cryptographic protocols are just like the rational players in game theory. Cryptographic protocol is a protocol that uses cryptography to accomplish a specific task and satisfies the security requirements. It focuses on the design and implementation of the protocol, security, and efficiency of the protocol. Game theory focuses on game strategy and rules design, and the players in the game are more concerned about their final payoffs. Therefore, rational cryptographic protocols provide a new idea for the design of cryptographic protocols from the perspective of benefits of participants, especially in the context of cloud computing and big data.

In 2006, Anderson and Moore published ``The economics of information security" in \textit{Science}, which discussed the problems of information security from the perspective of economics. In the field of cryptography, many scholars research this issue. Especially since 2010, many important conferences in the field of computer, such as STOC, FOCS, CRYPTO, EUROCRYPT, ASIACRYPT, TCC, etc., have paid attention to the international research progress of rational cryptographic protocols for many years. Two aspects are focused on mainly. One is the use of cryptographic protocols to solve some problems in game theory, such as the use of secure multi-party computing protocol to achieve the natural person in game theory. The other one is the game mechanism applied to cryptography, such as introducing rational participants into cryptographic protocols, using game equilibrium theory to construct cryptographic protocols satisfying different equilibrium results. There are many game methods that are applied to network attack and defense, security routing protocol, etc. In recent years, researchers in China have also paid greatly attention to this area, including the Chinese Academy of Sciences, the State Key Laboratory of Information Security, Xidian University, Shanghai Jiao Tong University, Shandong University, Beijing Jiaotong University, Central University of Finance and Economics, Beijing University of Technology, Fujian Normal University, Yunnan University, Henan Normal University, Guizhou University, etc. The authors of the above affiliations completed a lot of meaningful work in this respect.

However, in the research of cryptographic protocols, most of the traditional information security assume that the participants are honest or malicious, but in reality the participants are usually rational and selfish. Many scholars focus on the research of rational secret sharing, rational secure multi-party computation, rational exchange protocol, rational authentication protocol, rational threshold signature, rational delegating computation, etc. In the research of information security attack and defense game, the analysis of information security attack and defense strategy is the application of game theory, including intrusion detection system, information warfare, intrusion tolerance system, etc. In addition, the researchers use game theory and cryptographic protocol to study the mechanism design of incentive layer in block chain, to improve the efficiency and practicability of block chain, and uses the thought of game theory to design smart contracts to resist collusion for the client in cloud computing. Under the frame of game theory, the utility function is applied to ensure the completeness of calculation results in outsourcing calculation, reduce the verification process of outsourcing calculation, and improve the efficiency of outsourcing calculation. Through the analysis and design of participants' strategies in cryptographic protocols, the circuit calculation probability model is constructed to ensure the security of communication networks. Although some research results have been obtained on rational cryptographic protocols, the development of rational cryptographic protocols is still in its infancy, and some important problems need to be further studied.

This special column has collected four high-quality papers, which reflect the main research directions of rational cryptographic protocols recently. Hoping to enlighten the researchers who research rational cryptographic protocols in China.

The first paper is ``Progress in Research on Game Theory and Cryptographic Protocols'', which explains the application of game theory in the research of cryptographic protocols, and respectively introduces the application of complete information static game, complete information dynamic game, incomplete information static game, incomplete information dynamic game, random game, and evolutionary game in the research of information security. It briefly introduces the game theory modeling methods of attack and defense confrontation, defensive strategy selection, quantitative security investment, the defensors' mutual dependence, and social optimal achievement in information security issues such as cryptographic protocols, and demonstrates the influences of action order, incomplete information, system state, and bounded rationality on game analysis.

The second paper is ``Applications of Game Theory in Blockchain'', which analyzes the cross-research fields of game theory, secure multi-party computing, and Bitcoin (blockchain 1.0), including rational secure multiparty computing, secure multi-party computing based on Bitcoin and the Bitcoin protocol based on game theory. Applying smart contracts (blockchain 2.0) to verifiable cloud computing, using game theory to design smart contract for client in cloud computing, this smart contract can effectively prevent cloud server from collusion. Random parameters are introduced into in the criminal smart contract and Random-PublicLeaks are constructed. By verifying the validity of the smart contract, it is found that the introduction of randomness reduces the success probability of criminal smart contracts.

The third paper is ``Game-theoretic Mechanism for Rational Outsourcing Computation''. Under the frame of game theory, we design the strategy rule of integrity of outsourcing computing results based on Nash equilibrium. Firstly analyzed is the preference of the users and the servers in outsourcing computing, and an extended game model of outsourcing computing is proposed. Under this model it defines a new payoff matrix and the utility function. Secondly, according to the Nash equilibrium of game theory, the formal definition of rational outsourcing computing model is given. Finally, the conditions of selecting the linear function in the rational outsourcing computing model are analyzed by experimental simulation to ensure that the users do not verify the outsourcing computing results when the participants reach the Nash equilibrium. It also ensures that the server's honest calculation is its optimal strategy. Most importantly, this model can minimize the user's outsourcing fee.

The fourth paper is entitled ``Rational Secure Multiparty Sum Protocol Based on Circuit Computing''. Combining game theory and cryptographic algorithm, a rational secure multiparty sum protocol is proposed based on circuit computing. Firstly, the strategies of the participants in the summation process are analyzed and designed, and the probability utility model of circuit calculation is constructed. Then the result is hidden by using the coin-operated protocol which is biased towards 0. Finally, the participants reveal the final result by the method of gradual release. The designed protocol can eliminate the motivation of members' collusion and ensure that each member can obtain the sum result fairly in the standard point-to-point communication network.

Game theory and cryptographic protocols are both concerned with the interaction among distrustful participants. Game theory deepens the hypothetical conditions of cryptographic protocols, extending from the study of honest or malicious participants to the study of rational participants, which can provide significant help for solving cryptographic protocols such as secret sharing and secure multi-party computation. Game theory has become one of the important theories and tools in the field of cryptographic protocols. This paper explains the application of game theory in cryptographic protocol research. On the basis of introducing the basic concepts of game theory, the existing literatures are classified and summarized mainly according to different game methods. This paper respectively introduces the application of complete information static game, complete information dynamic game, incomplete information static game, incomplete information dynamic game, stochastic game, and evolutionary game in the study of information security, briefly introduces the game theoretic modeling methods of problems in information security such as cryptographic protocols including the conflicts between attacks and defenses, defense strategy selection, quantitative security investment, interdependence among defenders, and social optimization achievement, and shows the effects of action sequences, incomplete information, system states, limited rationality, and other factors in game theoretic analyses. This paper demonstrates the significant value of the introduction of game theory to cryptographic protocol research, points out the limitations of game theory itself and other existing research deficiencies, and provides suggestions for possible future research directions.

As one of the underlying technics of Bitcoin, Blockchain is a distributed database recording the history of transactions. Each block includes several transactions and a new block is added to the Blockchain by miners. The data of transactions cannot be forged by utilizing cryptographic techniques. Economic factors are integrated into incentive level of Blockchain, which consist of issue and distribution of economic incentives to maintain normal operation of the system. Therefore, it is a crux in Blockchain to design efficient and practical incentive mechanisms. Game theory, as an important branch of modern mathematics, is one of standard tools to analyze economic theory, which can be utilized to solve such problems. This paper first takes a historic overview on game theory, secure multi-party computation and Bitcoin (Blockchain 1.0), including rational secure multi-party computation, secure multi-party computation based on Bitcoin and Bitcoin protocols based on game theory. Then the techniques of smart contracts (Blockchain 2.0) is used in verification of cloud computing, which can be collusion free. Finally, the construction of smart contract are highlighted: Random-PublicLeaks, a randomized criminal smart contract. It shows that the maximum probability of Random-PublicLeaks is rather low by introducing random parameters.

Rational outsourcing computation is a combination of game theory and outsourcing computation, which is an extension of rational cryptography. The rational outsourcing calculation mainly aims to ensure the integrity and reliability of the computation results through the utility function by setting incentives and self-interest of participants. Currently, there is only a small variety of the structures of the traditional outsourcing computing, and the security risk of outsourcing computing tasks is insufficient for the outsourced computing model due to the different behaviors and preferences of the participants, and the verification process is complex and the communication overhead is high. However, the existing rational outsourcing computing protocols all require users to perform verification to guarantee the integrity of the outsourced computing results. In view of the above issues, this study designs the outsourcing strategy based on Nash equilibrium in the framework of game theory. Firstly, the preference of the user and the server in outsourcing computation is analyzed, and an outsourced computing extended game model is proposed. The model defines a new payoff matrix and the utility function. Secondly, a formal definition of rational outsourcing computation model is given according to the Nash equilibrium of game. Finally, experimental simulation is used to analyze the selection conditions of the linear function in the rational outsourcing computation model to ensure that the user does not verify the outsourced computation results when the participant achieves the Nash equilibrium, and also ensures that the honest calculation is the server's optimal strategy. This model minimizes the user's costs.

The secure sum protocol is given as an example of secure multiparty computation, which has numerous applications such as data mining, statistical analysis, and electronic election. However, traditional secure sum protocols cannot guarantee the fairness. To address this problem, this study proposes a rational secure sum protocol based on circuit evaluation, combining game theory, and cryptography. To begin with, strategies of participants are designed and the model of probabilistic payoffs for circuit computation is developed. Besides, a random string generated by the improved coin flips protocol biased to 0 is used to mask the result. Finally, participants reveal the output by using a method of gradual release. Meanwhile, this method will not reveal participants' private inputs. The protocol does not need to have the strong conditions of most honest participants, and can effectively verify the members' deceit. Therefore, every participant has no incentive to conspire, and the protocol can guarantee that every participant can obtain the correct sum in standard point-to-point communication networks.