Search Results

Documents authored by Eriguchi, Reo

Document
DOI: 10.4230/LIPIcs.ITC.2024.10
Secure Multiparty Computation of Symmetric Functions with Polylogarithmic Bottleneck Complexity and Correlated Randomness

Authors: Reo Eriguchi

Published in: LIPIcs, Volume 304, 5th Conference on Information-Theoretic Cryptography (ITC 2024)

Abstract
Bottleneck complexity is an efficiency measure of secure multiparty computation (MPC) protocols introduced to achieve load-balancing in large-scale networks, which is defined as the maximum communication complexity required by any one player within the protocol execution. Towards the goal of achieving low bottleneck complexity, prior works proposed MPC protocols for computing symmetric functions in the correlated randomness model, where players are given input-independent correlated randomness in advance. However, the previous protocols with polylogarithmic bottleneck complexity in the number n of players require a large amount of correlated randomness that is linear in n, which limits the per-party efficiency as receiving and storing correlated randomness are the bottleneck for efficiency. In this work, we present for the first time MPC protocols for symmetric functions such that bottleneck complexity and the amount of correlated randomness are both polylogarithmic in n, assuming semi-honest adversaries colluding with at most n-o(n) players. Furthermore, one of our protocols is even computationally efficient in that each player performs only polylog(n) arithmetic operations while the computational complexity of the previous protocols is O(n). Technically, our efficiency improvements come from novel protocols based on ramp secret sharing to realize basic functionalities with low bottleneck complexity, which we believe may be of interest beyond their applications to secure computation of symmetric functions.
Cite as

Reo Eriguchi. Secure Multiparty Computation of Symmetric Functions with Polylogarithmic Bottleneck Complexity and Correlated Randomness. In 5th Conference on Information-Theoretic Cryptography (ITC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 304, pp. 10:1-10:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{eriguchi:LIPIcs.ITC.2024.10,
  author =	{Eriguchi, Reo},
  title =	{{Secure Multiparty Computation of Symmetric Functions with Polylogarithmic Bottleneck Complexity and Correlated Randomness}},
  booktitle =	{5th Conference on Information-Theoretic Cryptography (ITC 2024)},
  pages =	{10:1--10:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-333-1},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{304},
  editor =	{Aggarwal, Divesh},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2024.10},
  URN =		{urn:nbn:de:0030-drops-205182},
  doi =		{10.4230/LIPIcs.ITC.2024.10},
  annote =	{Keywords: Secure multiparty computation, Bottleneck complexity, Secret sharing}
}
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.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}
}
Document
DOI: 10.4230/LIPIcs.ITC.2020.2
d-Multiplicative Secret Sharing for Multipartite Adversary Structures

Authors: Reo Eriguchi and Noboru Kunihiro

Published in: LIPIcs, Volume 163, 1st Conference on Information-Theoretic Cryptography (ITC 2020)

Abstract
Secret sharing schemes are said to be d-multiplicative if the i-th shares of any d secrets s^(j), j∈[d] can be converted into an additive share of the product ∏_{j∈[d]}s^(j). d-Multiplicative secret sharing is a central building block of multiparty computation protocols with minimum number of rounds which are unconditionally secure against possibly non-threshold adversaries. It is known that d-multiplicative secret sharing is possible if and only if no d forbidden subsets covers the set of all the n players or, equivalently, it is private with respect to an adversary structure of type Q_d. However, the only known method to achieve d-multiplicativity for any adversary structure of type Q_d is based on CNF secret sharing schemes, which are not efficient in general in that the information ratios are exponential in n. In this paper, we explicitly construct a d-multiplicative secret sharing scheme for any 𝓁-partite adversary structure of type Q_d whose information ratio is O(n^{𝓁+1}). Our schemes are applicable to the class of all the 𝓁-partite adversary structures, which is much wider than that of the threshold ones. Furthermore, our schemes achieve information ratios which are polynomial in n if 𝓁 is constant and hence are more efficient than CNF schemes. In addition, based on the standard embedding of 𝓁-partite adversary structures into ℝ^𝓁, we introduce a class of 𝓁-partite adversary structures of type Q_d with good geometric properties and show that there exist more efficient d-multiplicative secret sharing schemes for adversary structures in that family than the above general construction. The family of adversary structures is a natural generalization of that of the threshold ones and includes some adversary structures which arise in real-world scenarios.
Cite as

Reo Eriguchi and Noboru Kunihiro. d-Multiplicative Secret Sharing for Multipartite Adversary Structures. In 1st Conference on Information-Theoretic Cryptography (ITC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 163, pp. 2:1-2:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{eriguchi_et_al:LIPIcs.ITC.2020.2,
  author =	{Eriguchi, Reo and Kunihiro, Noboru},
  title =	{{d-Multiplicative Secret Sharing for Multipartite Adversary Structures}},
  booktitle =	{1st Conference on Information-Theoretic Cryptography (ITC 2020)},
  pages =	{2:1--2:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-151-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{163},
  editor =	{Tauman Kalai, Yael and Smith, Adam D. and Wichs, Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2020.2},
  URN =		{urn:nbn:de:0030-drops-121079},
  doi =		{10.4230/LIPIcs.ITC.2020.2},
  annote =	{Keywords: Secret sharing scheme, multiplicative secret sharing scheme, multipartite adversary structure}
}
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 About DROPS Imprint Privacy Contact