研究成果

Card-based cryptography, introduced by den Boer aims to realize multiparty computation (MPC) by using physical cards. We propose several efficient card-based protocols for the millionaires’ problem by introducing a new operation called Private Permutation (PP) instead of the shuffle used in most of existing card-based cryptography. Shuffle is a useful randomization technique by exploiting the property of card shuffling, but it requires a strong assumption from the viewpoint of arithmetic MPC because shuffle assumes that public randomization is possible. On the other hand, private randomness can be used in PPs, which enables us to design card-based protocols taking ideas of arithmetic MPCs into account. Actually, we show that Yao’s millionaires’ protocol can be easily transformed into a card-based protocol by using PPs, which is not straightforward by using shuffles because Yao’s protocol uses private randomness. Furthermore, we propose entirely novel and efficient card-based millionaire protocols based on PPs by securely updating bitwise comparisons between two numbers, which unveil a power of PPs. As another interest of these protocols, we point out they have a deep connection to the well-known logical puzzle known as “The fork in the road.”

We propose several efficient card-based cryptographic protocols for the millionaires’ problem by introducing a new operation called Private Permutation (PP) instead of the shuffle used in existing card-based cryptographic protocols. Shuffles are useful randomization techniques for designing card-based cryptographic protocols for logical gates, and this approach seems to be almost optimal. This fact, however, implies that there is room for improvements if we do not use logical gates as building blocks for secure computing, and we show that such an improvement is actually possible for the millionaires’ problem. Our key technique, PP, is a natural randomization operation for permuting a set of cards behind the player’s back, and hence, a shuffle can be decomposed into two PPs with one communication between them. Thus PP not only allows us to transform Yao’s seminal protocol into a card-based cryptographic protocol, but also enables us to propose entirely novel and efficient protocols by securely updating bitwise comparisons between two numbers. Furthermore, it is interesting to remark that one of the proposed protocols has a remarkably deep connection to the well-known logical puzzle known as “The fork in the road”.

In this paper, we study the security of AES-like permutations against the improved rebound attack proposed by Jean et al. at FSE 2012 which covers three full-active rounds in the inbound phase. The attack is very complicated and hard to verify its optimality when the state size is large and rectangle, namely the numbers of rows and columns are different. In the inbound phase of the improved rebound attack, several SuperSBoxes are generated for each of forward analysis and backward analysis. The attack searches for paired values that are consistent with all SuperSBoxes. The attack complexity depends on the order of the SuperSBoxes to be analyzed, and detecting the best order is hard. In this paper, we develop an automated complexity evaluation tool with several fast implementation techniques. The tool enables us to examine all the possible orders of the SuperSBoxes, and provides the best analysis order and complexity. We apply the tool to large block Rijndael in the known-key setting and the Grøstl-512 permutation. As a result, we obtain the first 9-round distinguisher for Rijndael-192 and Rijndael-224. It also shows the impossibility of the improved rebound attack against 9-round Rijndael-160 and 10-round Rijndael-256, and the optimality of the previous distinguisher against the 10-round Grøstl-512 permutation. Moreover, the efficiency of the improved rebound attack depends on the parameter of the ShiftRows operation. Our tool can exhaustively examine all the possible ShiftRows parameters to search for the ones that can resist the attack. We show new parameters for the Grøstl-512 permutation obtained by our tool, which can resist a 10-round improved rebound attack while the specification parameter cannot resist it.