Key Points and Methodology in Constructions and Security Proofs of Public-key Cryptosysems Hot!
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.
Differential Fault Attack on Lightweight Block Cipher LBlock Hot!
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 219.
Meet-in-the-middle Attack on Type-3 Feistel Structure Hot!
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 2n/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.
Multi-verifiable Reversible Watermarking Scheme for Relational Data Hot!
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.
Design and Applications of Efficient Protocol of Millionaires' Problem Based on 1 - r Encoding Hot!
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.
Dynamic Searchable Encryption Scheme on Cloud Storage with Multi-level Access Hot!
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.
New Lattice Reduction Algorithm Based on Block Random Sampling Method Hot!
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(n3(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.
Preface of Rational Cryptographic Protocol Column Hot!
Progress in Research on Game Theory and Cryptographic Protocols Hot!
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.
Applications of Game Theory in Blockchain Hot!
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.
Game-theoretic Mechanism of Rational Outsourcing Computation Hot!
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.
Rational Secure Multiparty Sum Protocol Based on Circuit Computing Hot!
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.