Search Results

Documents authored by Shinagawa, Kazumasa

Document
DOI: 10.4230/LIPIcs.FUN.2024.12
Card-Based Cryptography Meets Differential Privacy

Authors: Reo Eriguchi, Kazumasa Shinagawa, and Takao Murakami

Published in: LIPIcs, Volume 291, 12th International Conference on Fun with Algorithms (FUN 2024)

Abstract
Card-based cryptography studies the problem of implementing cryptographic algorithms in a visual way using physical cards to demonstrate their security properties for those who are unfamiliar with cryptography. In this paper, we initiate the study of card-based implementations of differentially private mechanisms, which are a standard privacy-enhancing technique to publish statistics of databases while protecting the privacy of any particular individual. We start with giving the definition of differential privacy of card-based protocols. As a feasibility result, we present three kinds of protocols using standard binary cards for computing the sum of parties' binary inputs, f(x₁,…,x_n) = ∑ⁿ_{i=1} x_i for x_i ∈ {0,1}, under differential privacy. Our first protocol follows the framework of output perturbation, which provides differential privacy by adding noise to exact aggregation results. The protocol needs only two shuffles, and the overheads in the number of cards and the error bound are independent of the number n of parties. Our second and third protocols are based on Randomized Response, which adds noise to each input before aggregation. Compared to the first protocol, they improve the overheads in the number of cards and the error bound in terms of differential privacy parameters at the cost of incurring a multiplicative factor of n. To address a technical challenge of generating non-uniform noise using a finite number of cards, we propose a novel differentially private mechanism based on the hypergeometric distribution, which we believe may be of independent interest beyond applications to card-based cryptography.
Cite as

Reo Eriguchi, Kazumasa Shinagawa, and Takao Murakami. Card-Based Cryptography Meets Differential Privacy. In 12th International Conference on Fun with Algorithms (FUN 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 291, pp. 12:1-12:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{eriguchi_et_al:LIPIcs.FUN.2024.12,
  author =	{Eriguchi, Reo and Shinagawa, Kazumasa and Murakami, Takao},
  title =	{{Card-Based Cryptography Meets Differential Privacy}},
  booktitle =	{12th International Conference on Fun with Algorithms (FUN 2024)},
  pages =	{12:1--12:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-314-0},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{291},
  editor =	{Broder, Andrei Z. and Tamir, Tami},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2024.12},
  URN =		{urn:nbn:de:0030-drops-199206},
  doi =		{10.4230/LIPIcs.FUN.2024.12},
  annote =	{Keywords: Card-based cryptography, Differential privacy, Secure computation}
}
Document
DOI: 10.4230/LIPIcs.FUN.2024.30
How to Covertly and Uniformly Scramble the 15 Puzzle and Rubik’s Cube

Authors: Kazumasa Shinagawa, Kazuki Kanai, Kengo Miyamoto, and Koji Nuida

Published in: LIPIcs, Volume 291, 12th International Conference on Fun with Algorithms (FUN 2024)

Abstract
A combination puzzle is a puzzle consisting of a set of pieces that can be rearranged into various combinations, such as the 15 Puzzle and Rubik’s Cube. Suppose a speedsolving competition for a combination puzzle is to be held. To make the competition fair, we need to generate an instance (i.e., a state having a solution) that is chosen uniformly at random and unknown to anyone. We call this problem a secure random instance generation of the puzzle. In this paper, we construct secure random instance generation protocols for the 15 Puzzle and for Rubik’s Cube. Our method is based on uniform cyclic group factorizations for finite groups, which is recently introduced by the same authors, applied to permutation groups for the puzzle instances. Specifically, our protocols require 19 shuffles for the 15 Puzzle and 43 shuffles for Rubik’s Cube.
Cite as

Kazumasa Shinagawa, Kazuki Kanai, Kengo Miyamoto, and Koji Nuida. How to Covertly and Uniformly Scramble the 15 Puzzle and Rubik’s Cube. In 12th International Conference on Fun with Algorithms (FUN 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 291, pp. 30:1-30:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{shinagawa_et_al:LIPIcs.FUN.2024.30,
  author =	{Shinagawa, Kazumasa and Kanai, Kazuki and Miyamoto, Kengo and Nuida, Koji},
  title =	{{How to Covertly and Uniformly Scramble the 15 Puzzle and Rubik’s Cube}},
  booktitle =	{12th International Conference on Fun with Algorithms (FUN 2024)},
  pages =	{30:1--30:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-314-0},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{291},
  editor =	{Broder, Andrei Z. and Tamir, Tami},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2024.30},
  URN =		{urn:nbn:de:0030-drops-199385},
  doi =		{10.4230/LIPIcs.FUN.2024.30},
  annote =	{Keywords: Card-based cryptography, Uniform cyclic group factorization, Secure random instance generation, The 15 Puzzle, Rubik’s Cube}
}
Document
DOI: 10.4230/OASIcs.Tokenomics.2021.5
Secure Computation with Non-Equivalent Penalties in Constant Rounds

Authors: Takeshi Nakai and Kazumasa Shinagawa

Published in: OASIcs, Volume 97, 3rd International Conference on Blockchain Economics, Security and Protocols (Tokenomics 2021)

Abstract
It is known that Bitcoin enables to achieve fairness in secure computation by imposing a monetary penalty on adversarial parties. This functionality is called secure computation with penalties. Bentov and Kumaresan (Crypto 2014) showed that it could be realized with O(n) rounds and O(n) broadcasts for any function, where n is the number of parties. Kumaresan and Bentov (CCS 2014) posed an open question: "Is it possible to design secure computation with penalties that needs only O(1) rounds and O(n) broadcasts?" In this work, we introduce secure computation with non-equivalent penalties, and design a protocol achieving this functionality with O(1) rounds and O(n) broadcasts only. The new functionality is the same as secure computation with penalties except that every honest party receives more than a predetermined amount of compensation while the previous one requires that every honest party receives the same amount of compensation. In particular, both are the same if all parties behave honestly. Thus, our result gives a partial answer to the open problem with a slight and natural modification of functionality.
Cite as

Takeshi Nakai and Kazumasa Shinagawa. Secure Computation with Non-Equivalent Penalties in Constant Rounds. In 3rd International Conference on Blockchain Economics, Security and Protocols (Tokenomics 2021). Open Access Series in Informatics (OASIcs), Volume 97, pp. 5:1-5:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{nakai_et_al:OASIcs.Tokenomics.2021.5,
  author =	{Nakai, Takeshi and Shinagawa, Kazumasa},
  title =	{{Secure Computation with Non-Equivalent Penalties in Constant Rounds}},
  booktitle =	{3rd International Conference on Blockchain Economics, Security and Protocols (Tokenomics 2021)},
  pages =	{5:1--5:16},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-220-4},
  ISSN =	{2190-6807},
  year =	{2022},
  volume =	{97},
  editor =	{Gramoli, Vincent and Halaburda, Hanna and Pass, Rafael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Tokenomics.2021.5},
  URN =		{urn:nbn:de:0030-drops-159026},
  doi =		{10.4230/OASIcs.Tokenomics.2021.5},
  annote =	{Keywords: Secure computation, Fairness, Bitcoin}
}
Document
DOI: 10.4230/LIPIcs.FUN.2021.20
Card-Based ZKP Protocols for Takuzu and Juosan

Authors: Daiki Miyahara, Léo Robert, Pascal Lafourcade, So Takeshige, Takaaki Mizuki, Kazumasa Shinagawa, Atsuki Nagao, and Hideaki Sone

Published in: LIPIcs, Volume 157, 10th International Conference on Fun with Algorithms (FUN 2021) (2020)

Abstract
Takuzu and Juosan are logical Nikoli games in the spirit of Sudoku. In Takuzu, a grid must be filled with 0’s and 1’s under specific constraints. In Juosan, the grid must be filled with vertical and horizontal dashes with specific constraints. We give physical algorithms using cards to realize zero-knowledge proofs for those games. The goal is to allow a player to show that he/she has the solution without revealing it. Previous work on Takuzu showed a protocol with multiple instances needed. We propose two improvements: only one instance needed and a soundness proof. We also propose a similar proof for Juosan game.
Cite as

Daiki Miyahara, Léo Robert, Pascal Lafourcade, So Takeshige, Takaaki Mizuki, Kazumasa Shinagawa, Atsuki Nagao, and Hideaki Sone. Card-Based ZKP Protocols for Takuzu and Juosan. In 10th International Conference on Fun with Algorithms (FUN 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 157, pp. 20:1-20:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{miyahara_et_al:LIPIcs.FUN.2021.20,
  author =	{Miyahara, Daiki and Robert, L\'{e}o and Lafourcade, Pascal and Takeshige, So and Mizuki, Takaaki and Shinagawa, Kazumasa and Nagao, Atsuki and Sone, Hideaki},
  title =	{{Card-Based ZKP Protocols for Takuzu and Juosan}},
  booktitle =	{10th International Conference on Fun with Algorithms (FUN 2021)},
  pages =	{20:1--20:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-145-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{157},
  editor =	{Farach-Colton, Martin and Prencipe, Giuseppe and Uehara, Ryuhei},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2021.20},
  URN =		{urn:nbn:de:0030-drops-127817},
  doi =		{10.4230/LIPIcs.FUN.2021.20},
  annote =	{Keywords: Zero-knowledge proof, Card-based cryptography, Takuzu, Juosan}
}
Document
DOI: 10.4230/LIPIcs.FUN.2018.31
Card-based Protocols Using Triangle Cards

Authors: Kazumasa Shinagawa and Takaaki Mizuki

Published in: LIPIcs, Volume 100, 9th International Conference on Fun with Algorithms (FUN 2018)

Abstract
Suppose that three boys and three girls attend a party. Each boy and girl have a crush on exactly one of the three girls and three boys, respectively. The following dilemma arises: On one hand, each person thinks that if there is a mutual affection between a girl and boy, the couple should go on a date the next day. On the other hand, everyone wants to avoid the possible embarrassing situation in which their heart is broken "publicly." In this paper, we solve the dilemma using novel cards called triangle cards. The number of cards required is only six, which is minimal in the case where each player commits their input at the beginning of the protocol. We also construct multiplication and addition protocols based on triangle cards. Combining these protocols, we can securely compute any function f: {0,1,2}^n --> {0,1,2}.
Cite as

Kazumasa Shinagawa and Takaaki Mizuki. Card-based Protocols Using Triangle Cards. In 9th International Conference on Fun with Algorithms (FUN 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 100, pp. 31:1-31:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{shinagawa_et_al:LIPIcs.FUN.2018.31,
  author =	{Shinagawa, Kazumasa and Mizuki, Takaaki},
  title =	{{Card-based Protocols Using Triangle Cards}},
  booktitle =	{9th International Conference on Fun with Algorithms (FUN 2018)},
  pages =	{31:1--31:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-067-5},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{100},
  editor =	{Ito, Hiro and Leonardi, Stefano and Pagli, Linda and Prencipe, Giuseppe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2018.31},
  URN =		{urn:nbn:de:0030-drops-88228},
  doi =		{10.4230/LIPIcs.FUN.2018.31},
  annote =	{Keywords: Cryptography without computer, Secure computation, Card-based protocols, Triangle cards, Three-valued computation, Secure matching problem}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact