学術論文誌
-
A Computationally Efficient Card-Based Majority Voting Protocol with Fewer Cards in the Private Model
- 著者
- Y. Abe, T. Nakai, Y. Watanabe, M. Iwamoto, and K. Ohta
- 雑誌名
- IEICE Transactions on Fundamentals
- 巻
- E106-A
- 号
- 3
- ページ
- 315–324
- 出版社
- IEICE
- 発行年
- 2023
Abstract
Card-based cryptography realizes secure multiparty computation using physical cards. In 2018, Watanabe et al. proposed a card-based three-input majority voting protocol using three cards. In a card-based cryptographic protocol with n-bit inputs, it is known that a protocol using shuffles requires at least 2n cards. In contrast, as Watanabe et al.'s protocol, a protocol using private permutations can be constructed with fewer cards than the lower bounds above. Moreover, an n-input protocol using private permutations would not even require n cards in principle since a private permutation depending on an input can represent the input without using additional cards. However, there are only a few protocols with fewer than n cards. Recently, Abe et al. extended Watanabe et al.'s protocol and proposed an n-input majority voting protocol with n cards and n + \floor{n/2} + 1 private permutations. This paper proposes an n-input majority voting protocol with \ceil{n/2}+1 cards and 2n-1 private permutations, which is also obtained by extending Watanabe et al.'s protocol. Compared with Abe et al.'s protocol, although the number of private permutations increases by about n/2, the number of cards is reduced by about n/2. In addition, unlike Abe et al.'s protocol, our protocol includes Watanabe et al.'s protocol as a special case where n=3.
-
How to Make a Secure Index for Searchable Symmetric Encryption, Revisited
- 著者
- Y. Watanabe, T. Nakai, K. Ohara, T. Nojima, Y. Liu, M. Iwamoto, and K. Ohta
- 雑誌名
- IEICE Transactions on Fundamentals
- 巻
- E105-A
- 号
- 12
- ページ
- 1559–1579
- 出版社
- IEICE
- 発行年
- 2022
Abstract
Searchable symmetric encryption (SSE) enables clients to search encrypted data. Curtmola et al. (ACM CCS 2006) formalized a model and security notions of SSE and proposed two concrete constructions called SSE-1 and SSE-2. After the seminal work by Curtmola et al., SSE becomes an active area of encrypted search. In this paper, we focus on two unnoticed problems in the seminal paper by Curtmola et al. First, we show that SSE-2 does not appropriately implement Curtmola et al.'s construction idea for dummy addition. We refine SSE-2's (and its variants') dummy-adding procedure to keep the number of dummies sufficiently many but as small as possible. We then show how to extend it to the dynamic setting while keeping the dummy-adding procedure work well and implement our scheme to show its practical efficiency. Second, we point out that the SSE-1 can cause a search error when a searched keyword is not contained in any document file stored at a server and show how to fix it.
-
Efficient Card-Based Majority Voting Protocols
- 著者
- Y. Abe, T. Nakai, Y. Kuroki, S. Suzuki, Y. Koga, Y. Watanabe, M. Iwamoto, and K. Ohta
- 雑誌名
- New Generation Computing
- 巻
- 40
- ページ
- 173–198
- 出版社
- Springer
- 発行年
- 2022
Open AccessAbstract
Card-based cryptography is a variety of secure multiparty computation (MPC). Recently, a new technique called private operations was introduced because the protocol can be implemented with fewer cards than that by using the conventional technique called the shuffle. For example, Nakai et al. showed that if the private operations are available, secure computations of AND and OR operations for two inputs can be realized simultaneously by using four cards, and the protocol is applied to a four-card majority voting protocol with three inputs. This paper shows that only three cards are sufficient to construct a majority voting protocol with three inputs. Specifically, we propose two constructions of three-input majority voting protocols. One is a protocol assuming that players can announce their output, and the other is not allowed. Compared to Nakai et al.'s protocol, the protocol with the announcement is realized without any additional private operations and communications. On the other hand, the second construction requires two more private operations and communications because it removes the assumption on the announcement from the first construction. More importantly, the idea of the second protocol can be extended to an n-input majority voting protocol with n cards, which is the main result of this paper.
-
Secure Computation for Threshold Functions with Physical Cards: Power of Private Permutations
- 著者
- T. Nakai, S. Shirouchi, Y. Tokushige, M. Iwamoto, and K. Ohta
- 雑誌名
- New Generation Computing
- 巻
- 40
- 号
- 95–113
- 出版社
- Ohmsha and Springer
- 発行年
- 2022
Open AccessAbstract
Card-based cryptography is a variant of multi-party computation by using physical cards like playing cards. There are two models on card-based cryptography, called public and private models. The public model assumes that all operations are executed publicly, while the private model allows the players private operations called private permutations (PP, for short). Much of the existing card-based protocols were developed under the public model. Under the public model, 2n cards are necessary for every protocol with n-bit input since at least two cards are required to express a bit. In this paper, we propose n-bit input protocols with fewer than 2n cards by utilizing PP, which shows the power of PP. In particular, we show that a protocol for (n-bit input) threshold function can be realized with only n+1 cards by reducing the threshold function to the majority voting. Toward this end, we first offer that two-bit input protocols for logic gates can be realized with fewer than four cards. Furthermore, we construct a new protocol for three-input majority voting with only four cards by observing the relationship between AND/OR operations. This protocol can be easily extended to more participants, and to the protocol for threshold functions.
-
How to Solve Millionaires’ Problem with Two Kinds of Cards
- 著者
- T. Nakai, Y. Misawa, Y. Tokushige, M. Iwamoto, and K. Ohta
- 雑誌名
- New Generation Computing
- 巻
- 39
- ページ
- 73–96
- 出版社
- Springer
- 発行年
- 2021
Open AccessAbstract
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.”