# 研究成果

#### 学術論文誌

• ##### Key-Updatable Public-Key Encryption with Keyword Search (Or: How to Realize PEKS with Efficient Key Updates for IoT Environments)
著者
H. Anada, A. Kanaoka, N. Matsuzaki, and Y. Watanabe
雑誌名
International Journal of Information Security
19
ページ
15–38
出版社
Springer
発行年
2020
###### Abstract

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.

• ##### Multi-Party Computation for Modular Exponentiation Based on Replicated Secret Sharing
著者
K. Ohara, Y. Watanabe, M. Iwamoto, and K. Ohta
雑誌名
IEICE Transactions
102-A
9
ページ
1079–1090
出版社
IEICE
発行年
2019
###### Abstract

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.

#### 国際会議

• ##### Card-Based Secure Ranking Computations
著者
K. Takashima, Y. Abe, T. Sasaki, D. Miyahara, K. Shinagawa, T. Mizuki, and H. Sone
会議名
COCOA 2019
LNCS 11949
ページ
461–472
出版社
Springer
発行年
2019
発表日
2019/12/14
###### Abstract

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.

• ##### Efficient Private PEZ Protocols for Symmetric Functions
著者
Y. Abe, M. Iwamoto, and K. Ohta
会議名
TCC 2019
LNCS 11891
ページ
372–392
出版社
Springer
発行年
2019
発表日
2019/12/3
###### Abstract

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.

• ##### Identity-Based Encryption with Security against the KGC: A Formal Model and Its Instantiation from Lattices
著者
K. Emura, S. Katsumata, and Y. Watanabe
会議名
ESORICS 2019
LNCS 11736
ページ
113–133
出版社
Springer
発行年
2019
発表日
2019/9/25
###### Abstract

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).

• ##### Optimal Multiple Assignment Schemes Using Ideal Multipartite Secret Sharing Schemes
著者
R. Eriguchi, N. Kunihiro, and M. Iwamoto
会議名
ISIT 2019
ページ
3047–3051
出版社
IEEE
発行年
2019
発表日
2019/7/12
###### Abstract

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.

• ##### Light Cryptography
著者
P. Lafourcade, T. Mizuki, A. Nagao, and K. Shinagawa
会議名
WISE 2019
Proceedings of WISE
552
ページ
89–101
出版社
Springer
発行年
2019
発表日
2019/6/26
###### Abstract

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.

• ##### Secure Computation of Any Boolean Function Based on Any Deck of Cards
著者
K. Shinagawa and T. Mizuki
会議名
FAW 2019
LNCS 11458
ページ
63–75
出版社
Springer
発行年
2019
発表日
2019/5/1
###### Abstract

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.

• ##### Card-Based Cryptography with Invisible Ink
著者
K. Shinagawa
会議名
TAMC 2019
LNCS 11436
ページ
566–577
出版社
Springer
発行年
2019
発表日
2019/4/16
###### Abstract

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.

• ##### Key-updatable Public-key Encryption with Keyword Search: Models and Generic Constructions
著者
H. Anada, A. Kanaoka, N. Matsuzaki, and Y. Watanabe
会議名
ACISP 2018
LNCS 10946
ページ
341–359
出版社
Springer
発行年
2018
###### Abstract

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.

• ##### Four Cards Are Sufficient for a Card-Based Three-Input Voting Protocol Utilizing Private Permutations
著者
T. Nakai, S. Shirouchi, M. Iwamoto, and K. Ohta
会議名
ICITS 2017
LNCS 10681
ページ
153-165
出版社
Springer
発行年
2017
発表日
2017/12/2
###### Abstract

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.

• ##### Efficient Card-based Cryptographic Protocols for Millionaires’ Problem Utilizing Private Permutations
著者
T. Nakai, Y. Misawa, Y. Tokushige, M. Iwamoto, and K. Ohta
会議名
CANS 2016
LNCS 10052
ページ
350–364
出版社
Springer
発行年
2016
発表日
2016/11/15
###### Abstract

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”.

• ##### An Automated Evaluation Tool for Improved Rebound Attack: New Distinguishers and Proposals of ShiftBytes Parameters for Grøstl
著者
Y. Sasaki, Y. Tokushige, L. Wang, M. Iwamoto, and K. Ohta
LNCS 8366
ページ
424–443
出版社
Springer
発行年
2014
###### Abstract

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.

#### 国内会議

• ##### 気泡検出器を用いたゼロ知識非破壊検査
著者
品川 和雅, 三浦 典之, 岩本 貢, 崎山 一男, 太田 和夫
会議名
SCIS 2020
ページ
2E2-3
発行年
2020
発表日
2020/1/29
• ##### 鍵のランダムな漏洩に対するAES鍵スケジュール復元アルゴリズム
著者
植村 友紀, 李 陽, 三浦 典之, 岩本 貢, 崎山 一男, 太田 和夫
会議名
SCIS 2020
ページ
2B1-1
発行年
2020
発表日
2020/1/29
• ##### 任意の始集合を持つ関数を計算するprivate PEZプロトコル
著者
安部 芳紀, 岩本 貢, 太田 和夫
会議名
SCIS 2020
ページ
3C1-5
発行年
2020
発表日
2020/1/30
著者
渡邉 洋平
会議名
SCIS 2020
ページ
3B3-2
発行年
2020
発表日
2020/1/30
• ##### 任意の関数を計算するprivate PEZプロトコルの改善
著者
安部 芳紀, 岩本 貢, 太田 和夫
会議名
CSS 2019
ページ
894–901
発行年
2019
発表日
2019/10/22
• ##### (強)フォワード安全な動的検索可能暗号の効率的な構成
著者
渡邉 洋平, 大原 一真, 岩本 貢, 太田 和夫
会議名
CSS 2019
ページ
1203–1210
発行年
2019
発表日
2019/10/23
• ##### 検索可能暗号における最小漏洩情報に関する考察
著者
中井雄士, 野島拓也, 岩本 貢, 太田 和夫
会議名
IT・ISEC・WBS合同研究会
ページ
187–192
発行年
2017
発表日
2017/3/10

#### 口頭発表

• ##### How to improve the private PEZ protocol for general functions
著者
Y. Abe, M. Iwamoto, and K. Ohta
発表者
Y. Abe
会議名
IWSEC 2019
開催地
Tokyo, Japan
種別
Poster
発表日
2019/8/28
• ##### Comparison of Security on Coded Signs with Public/Private Code Book
著者
Y. Misawa, Y. Tokushige, M. Iwamoto, and K. Ohta
発表者
Y. Misawa
会議名
IWSEC 2015
開催地
Nara, Japan
種別
Poster
• ##### Toward Reducing Shuffling in Card-based Cryptographic Protocol for Millionaire Problem
著者
T. Nakai, Y. Tokushige, M. Iwamoto, and K. Ohta
発表者
T. Nakai
会議名
IWSEC 2015
開催地
Nara, Japan
種別
Poster

#### 招待講演

• ##### 対称関数を効率的に計算するPrivate PEZ プロトコル (from TCC 2019)
発表者
安部 芳紀
会議名
電子情報通信学会ISEC研究会
開催地
オンライン開催
発表日
2020/5/20
予稿集   安部 芳紀, 岩本 貢, 太田 和夫, “[招待講演] 対称関数を効率的に計算するPrivate PEZ プロトコル (from TCC 2019),” 信学技報, ISEC2020-4, p.23, 2020.
• ##### Recent Progress on Private PEZ Protocols
発表者
Y. Abe
会議名
Workshop on Cryptography Using Physical Tools
開催地
Tokyo, Japan
発表日
2019/12/17
発表者
中井　雄士
会議名
SITA 2016
開催地
岐阜県
発表日
2016/12/15