Search Results

Documents authored by Nuida, Koji

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/LIPIcs.ITC.2023.18
Exponential Correlated Randomness Is Necessary in Communication-Optimal Perfectly Secure Two-Party Computation

Authors: Keitaro Hiwatashi and Koji Nuida

Published in: LIPIcs, Volume 267, 4th Conference on Information-Theoretic Cryptography (ITC 2023)

Abstract
Secure two-party computation is a cryptographic technique that enables two parties to compute a function jointly while keeping each input secret. It is known that most functions cannot be realized by information-theoretically secure two-party computation, but any function can be realized in the correlated randomness (CR) model, where a trusted dealer distributes input-independent CR to the parties beforehand. In the CR model, three kinds of complexities are mainly considered; the size of CR, the number of rounds, and the communication complexity. Ishai et al. (TCC 2013) showed that any function can be securely computed with optimal online communication cost, i.e., the number of rounds is one round and the communication complexity is the same as the input length, at the price of exponentially large CR. In this paper, we prove that exponentially large CR is necessary to achieve perfect security and online optimality for a general function and that the protocol by Ishai et al. is asymptotically optimal in terms of the size of CR. Furthermore, we also prove that exponentially large CR is still necessary even when we allow multiple rounds while keeping the optimality of communication complexity.
Cite as

Keitaro Hiwatashi and Koji Nuida. Exponential Correlated Randomness Is Necessary in Communication-Optimal Perfectly Secure Two-Party Computation. In 4th Conference on Information-Theoretic Cryptography (ITC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 267, pp. 18:1-18:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{hiwatashi_et_al:LIPIcs.ITC.2023.18,
  author =	{Hiwatashi, Keitaro and Nuida, Koji},
  title =	{{Exponential Correlated Randomness Is Necessary in Communication-Optimal Perfectly Secure Two-Party Computation}},
  booktitle =	{4th Conference on Information-Theoretic Cryptography (ITC 2023)},
  pages =	{18:1--18:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-271-6},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{267},
  editor =	{Chung, Kai-Min},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2023.18},
  URN =		{urn:nbn:de:0030-drops-183462},
  doi =		{10.4230/LIPIcs.ITC.2023.18},
  annote =	{Keywords: Secure Computation, Correlated Randomness, Lower Bound}
}
Document
DOI: 10.4230/LIPIcs.ITC.2022.1
Multi-Server PIR with Full Error Detection and Limited Error Correction

Authors: Reo Eriguchi, Kaoru Kurosawa, and Koji Nuida

Published in: LIPIcs, Volume 230, 3rd Conference on Information-Theoretic Cryptography (ITC 2022)

Abstract
An 𝓁-server Private Information Retrieval (PIR) scheme allows a client to retrieve the τ-th element a_τ from a database a = (a₁,…,a_n) which is replicated among 𝓁 servers. It is called t-private if any coalition of t servers learns no information on τ, and b-error correcting if a client can correctly compute a_τ from 𝓁 answers containing b errors. This paper concerns the following problems: Is there a t-private 𝓁-server PIR scheme with communication complexity o(n) such that a client can detect errors with probability 1-ε even if 𝓁-1 servers return false answers? Is it possible to add error correction capability to it? We first formalize a notion of (1-ε)-fully error detecting PIR in such a way that an answer returned by any malicious server depends on at most t queries, which reflects t-privacy. We then prove an impossibility result that there exists no 1-fully error detecting (i.e., ε = 0) PIR scheme with o(n) communication. Next, for ε > 0, we construct 1-private (1-ε)-fully error detecting and (𝓁/2-O(1))-error correcting PIR schemes which have n^{o(1)} communication, and a t-private one which has O(n^{c}) communication for any t ≥ 2 and some constant c < 1. Technically, we show generic transformation methods to add error correction capability to a basic fully error detecting PIR scheme. We also construct such basic schemes by modifying certain existing PIR schemes which have no error detection capability.
Cite as

Reo Eriguchi, Kaoru Kurosawa, and Koji Nuida. Multi-Server PIR with Full Error Detection and Limited Error Correction. In 3rd Conference on Information-Theoretic Cryptography (ITC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 230, pp. 1:1-1:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{eriguchi_et_al:LIPIcs.ITC.2022.1,
  author =	{Eriguchi, Reo and Kurosawa, Kaoru and Nuida, Koji},
  title =	{{Multi-Server PIR with Full Error Detection and Limited Error Correction}},
  booktitle =	{3rd Conference on Information-Theoretic Cryptography (ITC 2022)},
  pages =	{1:1--1:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-238-9},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{230},
  editor =	{Dachman-Soled, Dana},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2022.1},
  URN =		{urn:nbn:de:0030-drops-164796},
  doi =		{10.4230/LIPIcs.ITC.2022.1},
  annote =	{Keywords: Private Information Retrieval, Error Detection, Error Correction}
}
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