研究成果

学術論文誌

  • 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

受賞等