研究成果

Security and privacy are the key issues for the Internet of Things (IoT) systems. Especially, secure search is an important functionality for cooperation among users’ devices and non-trusted servers. Public-key encryption with keyword search (PEKS) enables us to search encrypted data and is expected to be used between a cloud server and users’ mobile devices or IoT devices. However, those mobile devices might be lost or stolen. For IoT devices, it might be difficult to store keys in a tamper-proof manner due to prohibitive costs. In this paper, we deal with such a key-exposure problem on PEKS and introduce the concept of PEKS with key-updating functionality, which we call key-updatable PEKS (KU-PEKS). Specifically, we propose two models of KU-PEKS: the key-evolution model and the key-insulation model. In the key-evolution model, a pair of public and secret keys can be updated if needed (e.g., the secret key is exposed). In the key-insulation model, the public key remains fixed while the secret key can be updated if needed. The former model makes a construction simple and more efficient than the latter. On the other hand, the latter model is preferable for practical use since a user never updates their public key. We show constructions in each model in a black-box manner. We also give implementation results on Raspberry Pi 3, which can be regarded as a reasonable platform of IoT devices.

In recent years, multi-party computation (MPC) frameworks based on replicated secret sharing schemes (RSSS) have attracted the attention as a method to achieve high efficiency among known MPCs. However, the RSSS-based MPCs are still inefficient for several heavy computations like algebraic operations, as they require a large amount and number of communication proportional to the number of multiplications in the operations (which is not the case with other secret sharing-based MPCs). In this paper, we propose RSSS-based three-party computation protocols for modular exponentiation, which is one of the most popular algebraic operations, on the case where the base is public and the exponent is private. Our proposed schemes are simple and efficient in both of the asymptotic and practical sense. On the asymptotic efficiency, the proposed schemes require O(n)-bit communication and O(1) rounds,where n is the secret-value size, in the best setting, whereas the previous scheme requires O(n2)-bit communication and O(n) rounds. On the practical efficiency, we show the performance of our protocol by experiments on the scenario for distributed signatures, which is useful for secure key management on the distributed environment (e.g., distributed ledgers). As one of the cases, our implementation performs a modular exponentiation on a 3,072-bit discrete-log group and 256-bit exponent with roughly 300ms, which is an acceptable parameter for 128-bit security, even in the WAN setting.

A key recovery algorithm using parts of the key schedules is proposed for evaluating the threat of probing attack. Suppose that we have an information leakage sensor, and we can detect a leak (attacked) point where an attacker makes electrical/physical contact with a laser, a probe, etc. We assume that the attacked bits (leaked bits) are completely known to the attacker, whereas the other non-attacked bits are not leaked at all. We also assume that each bit leaks with a constant probability. Our key recovery algorithm is constructed by modifying the pruning phase that for cold boot attacks proposed by Tsow. Experimental result shows that, using our algorithm, more than 15% leakage recovers the key with almost probability 1, whereas less than 10% is recovered with small probability close to 0.

Signcryption (SC) achieves the goal with lower computational costs than simply combining public-key encryption (PKE) and digital signatures (DS). Meanwhile, at SCN 2014, Dodis and Fiore formalized interactive PKE and DS. In particular, in the interactive setting, they showed a CCA-secure PKE scheme can be constructed assuming only CPA-secure PKE schemes in a black-box manner. In this paper, we focus on SC schemes in the interactive setting (ISC for short). Specifically, we newly define a model and security notions for ISC schemes. We then propose generic constructions of ISC schemes by using CPA-secure PKE schemes rather than CCA-secure ones, whereas such a realization is unknown in the context of non-interactive SC schemes. We show that two rounds are sufficient to construct an ISC scheme from only CPA-secure PKE schemes. Furthermore, we also show the first SC scheme that can be efficiently instantiated from simple assumptions in the standard model without pairings or lattices by allowing interaction.

Consider a group of people who want to know the “rich list” among them, namely the ranking in terms of their total assets, without revealing any information about the actual value of their assets. This can be achieved by a “secure ranking computation,” which was first considered by Jiang and Gong (CT-RSA 2006); they constructed a secure ranking computation protocol based on a public-key cryptosystem. In this paper, instead of using a public-key cryptosystem, we use a deck of physical cards to provide secure ranking computation protocols. Therefore, our card-based protocols do not rely on computers, and they are simple and easy for humans to implement. Specifically, we design four protocols considering tradeoffs between the number of cards and the number of shuffles required to execute protocols. We also present a guide to choose an appropriate protocol according to the number of people participating in the protocol and the size of the input range.

Physical cryptography provides cryptographic protocols using physical objects like cards and envelopes instead of using computers. In this paper, we introduce a new model for physical cryptography, called light cryptography. It uses transparent sheets and some properties of light and shadows. We design several secure light cryptographic protocols: one for set-intersection (which can solve the scheduling problem), one for maximum (which can solve the Yao's Millionaires' problem), one for computing the sum of integers. We believe that our protocols using light cryptography are a powerful tool for information security education because they are fairly simple and fun to use.

It is established that secure computation can be achieved by using a deck of physical cards. Almost all existing card-based protocols are based on a specific deck of cards. In this study, we design card-based protocols that are executable using any deck of cards (e.g., playing cards, UNO, and trading cards). Specifically, we construct a card-based protocol for any Boolean function based on any deck of cards. As corollaries of our result, a standard deck of playing cards (having 52 cards) enables secure computation of any 22-variable Boolean function, and UNO (having 112 cards) enables secure computation of any 53-variable Boolean function.

It is known that secure computation can be done by using a deck of physical cards; card-based cryptography makes people understand the correctness and security of secure computation, even for people who are not familiar with mathematics. In this paper, we propose a new type of cards, layered polygon cards, based on the use of invisible ink. A deck of cards with invisible ink naturally hides the contents of cards and allows to open some pieces of contents, which we referred to it as partial opening. Based on them, we construct novel protocols for various interesting functions such as carry of addition, equality, and greater-than.

The key escrow problem is one of the main barriers to the widespread real-world use of identity-based encryption (IBE). Specifically, a key generation center (KGC), which generates secret keys for a given identity, has the power to decrypt all ciphertexts. At PKC 2009, Chow defined a notion of security against the KGC, that relies on assuming that it cannot discover the underlying identities behind ciphertexts. However, this is not a realistic assumption since, in practice, the KGC manages an identity list and hence it can easily guess the identities corresponding to given ciphertexts. Chow later closed the gap between theory and practice by introducing a new entity called an identity-certifying authority (ICA) and proposed an anonymous key-issuing protocol. Essentially, this allows the users, KGC, and ICA to interactively generate secret keys without users ever having to reveal their identities to the KGC. Unfortunately, the proposed protocol did not include a concrete security definition, meaning that all of the subsequent works following Chow lack the formal proofs needed to determine whether or not it delivers a secure solution to the key escrow problem.
In this paper, based on Chow’s work, we formally define an IBE scheme that resolves the key escrow problem and provide formal definitions of security against corrupted users, KGC, and ICA. Along the way, we observe that if we are allowed to assume a fully trusted ICA, as in Chow’s work, then we can construct a trivial (and meaningless) IBE scheme that is secure against the KGC. Finally, we present a lattice-based construction in our new security model based on the Gentry–Peikert–Vaikuntanathan (GPV) IBE scheme (STOC 2008) and Rückert’s lattice-based blind signature scheme (ASIACRYPT 2010).

Public-key encryption with keyword search (PEKS) enables us to search over encrypted data, and is expected to be used between a cloud server and users’ devices such as laptops or smartphones. However, those devices might be lost accidentally or be stolen. In this paper, we deal with such a key-exposure problem on PEKS, and introduce a concept of PEKS with key-updating functionality, which we call key-updatable PEKS (KU-PEKS). Specifically, we propose two models of KU-PEKS: The key-evolution model and the key-insulation model. In the key-evolution model, a pair of public and secret keys can be updated if needed (e.g., the secret key is exposed). In the key-insulation model, a public key remains fixed while a secret key can be updated if needed. The former model makes a construction simple and more efficient than the latter model. On the other hand, the latter model is preferable for practical use since a user never updates his/her public key. We show constructions of a KU-PEKS scheme in each model in a black-box manner. We also give an experimental result for the most efficient instantiation, and show our proposal is practical.

A private PEZ protocol is a variant of secure multi-party computation performed using a (long) PEZ dispenser. The original paper by Balogh et al. presented a private PEZ protocol for computing an arbitrary function with n inputs. This result is interesting, but no follow-up work has been presented since then, to the best of our knowledge. We show herein that it is possible to shorten the initial string (the sequence of candies filled in a PEZ dispenser) and the number of moves (a player pops out a specified number of candies in each move) drastically if the function is symmetric. Concretely, it turns out that the length of the initial string is reduced from $O(2^{n}!)$ for general functions in Balogh et al.’s results to $O(n \cdot n!)$ for symmetric functions, and $2^n$ moves for general functions are reduced to $n^2$ moves for symmetric functions. Our main idea is to utilize the recursive structure of symmetric functions to construct the protocol recursively. This idea originates from a new initial string we found for a private PEZ protocol for the three-input majority function, which is different from the one with the same length given by Balogh et al. without describing how they derived it.

A multiple assignment scheme (MAS) is a method to construct secret sharing schemes (SSSs) for general access structures. There are MASs using threshold and ramp SSSs. The paper proposes new MASs using ideal SSSs realizing compartmented access structures and those using SSSs realizing multi-level access structures. Since the ideal SSSs realizing compartmented access structures and SSSs realizing multi-level access structures are natural generalizations of threshold and ramp SSSs, respectively, the new MASs cannot be less efficient than those using threshold or ramp SSSs.

The card-based cryptographic protocol is a variant of multi-party computation that enables us to compute a certain function securely by using playing cards. In existing card-based cryptographic protocols, a special operation of cards called a shuffle is used to achieve the information-theoretic security. Recently, card-based cryptographic protocols have been reconsidered from the viewpoint of multi-party computations. In this direction, a new model of card-based cryptographic protocol including a new assumption called Private Permutations (PP, for short) is introduced and succeeds in constructing efficient protocols for the millionaires’ protocol. In this paper, we construct efficient card-based cryptographic OR and XOR protocols based on the existing AND protocol. Furthermore, by unifying AND and OR protocols, it is shown that a majority voting protocol with three inputs is efficiently obtained. Our construction requires only four cards thanks to PPs, whereas the previous work requires eight cards.

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.

中井らとMarcedoneらは独立に，背面処理を用いるカードプロトコルを考案した． 背面処理とは，プレーヤが自分の背面などでプライベートに行うカード操作である。 背面処理を許すと，カードシャッフルを用いる従来のモデルより，カード枚数や通信回数が減る利点がある一方で，シャッフルを用いるモデルでは考慮する必要のなかった，不正検知の問題を考える必要がある． 本研究では，背面処理を行う人を監視するプレーヤ（番人）を導入し，ラウンド毎に番人を交代しながらプロトコルを実行する方法を提案する． このアイデアによって，監視により不正を検知しつつ，番人の交代により参加者全員にとってカード列がランダムに見えるようにできる． 我々のアイデアの実行例として，渡邉らが提案した，背面処理を用いたsemi-honestなモデルの多数決カードプロトコルを，maliciousモデルで実行できるように改良する．

Baloghらは, PEZと呼ばれるお菓子を用いて, 任意の関数を計算するマルチパーティ計算プロトコル（PEZプロトコル）を提案した. PEZプロトコルでは, 各プレーヤが入力にあわせてPEZ dispenser内のキャンディを一定個数食べることで計算を行う． 従来のPEZプロトコルは任意の関数が計算できる代わりに, 参加人数が増えると大量のキャンディが必要であった． 例えば4人で多数決計算を行う場合は6941個のキャンディが必要となる. 本研究では, 4入力多数決を107個のキャンディで実現するPEZプロトコルを示す.

A Private Set Operation (PSO) protocol is a secure multi-party computation protocol (MPC) that allows participants to know the result of set operations (union, intersection, difference etc.) of their inputs but learn nothing else. Although PSO protocols have many applications, previous work on PSO protocols mainly focused on the Private Set Intersection (PSI) protocols. One exception would be the work by Blanton and Aguiar, which is inefficient since it consists of consecutive PSO protocols for two sets. On the other hand, a PSI protocol based on polynomials is known to be efficient due to the homomorphic encryption for two parties. However, the computation cost becomes heavier if it is extended for three parties due to the cost of homomorphic encryption. In this work, we propose a new PSO protocol for three parties by combining polynomials with the Oblivious Programmable PRF (OPPRF) proposed by Kolesnikov et al. The proposed scheme is efficient even if three-party cases since OPPRF is constructed by a symmetric key encryption combining with polynomials.