Search Results

Documents authored by Gilboa, Niv

Document
DOI: 10.4230/LIPIcs.ITCS.2026.71
Lower Bounds on FSS from Dynamic Data Structures

Authors: Niv Gilboa and Daniel Weber

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
In Function Secret Sharing (FSS), a dealer with a given function f: {0,1}ⁿ → 𝔾 from n bits to a commutative group 𝔾 such that f is in a function class ℱ shares succinct keys with two properties. Evaluating each key separately on a common input x results in additive shares of f(x) and any subset of the keys does not provide information on f. Two-party FSS schemes which are reducible to One-way Functions (OWF) have applications in cryptography, complexity, and in practical data security systems. We establish a two-way transformation between a two-party FSS scheme for a function class ℱ, which is black-box reducible to an OWF, or even black-box reducible to a family of Pseudo-Random Functions (PRF) and a dynamic data structure that supports range queries on ℱ. A data structure of this type enables dynamically adding functions to a multiset of functions F ⊆ ℱ, and answering range queries on the output of F, i.e., returning ∑_{f ∈ F} f(x) for a query x. The data structures are defined in one of several models which abstract RAM. The correspondence together with known lower bounds on the update time and the query time in data structures leads to the first non-trivial lower bounds on FSS schemes which are black-box reducible to PRF. These lower bounds apply to FSS schemes with polynomial key size and include: - For ℱ^d_{box}, the class of all functions which assign a constant group element β ∈ 𝔾 to any input in a specified d-dimensional box and 0 to all other inputs: if the key sharing function, Gen, runs in time polynomial in n and the evaluation function is Eval then: - If d ≥ 2 and 𝔾 = ℤ₂ then Eval’s running time is Ω ((n^{3/2})/(log³ n)). - If d ≥ 2 and 𝔾 is cyclic such that log |𝔾| = (1 + ε) n then Eval’s running time is Ω ((n/(log n)) ²). - If d > 2 is a constant and further, Gen and Eval correspond to operations on data structures in the Oblivious Group Model (this includes all known FSS from OWF techniques), then the product of Eval’s time and the key size is Ω(n^{d-1}). - For ℱ_{mono}, the class of all monomials ax^b ∈ 𝔽_{2ⁿ}[X] such that b ≤ B, assuming n^{ω(1)} ≤ B ≤ 2^{n/4}: if Gen runs in polynomial time, then Eval’s running time is Ω ((n √{log B})/(log² n)).
Cite as

Niv Gilboa and Daniel Weber. Lower Bounds on FSS from Dynamic Data Structures. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 71:1-71:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{gilboa_et_al:LIPIcs.ITCS.2026.71,
  author =	{Gilboa, Niv and Weber, Daniel},
  title =	{{Lower Bounds on FSS from Dynamic Data Structures}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{71:1--71:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.71},
  URN =		{urn:nbn:de:0030-drops-253585},
  doi =		{10.4230/LIPIcs.ITCS.2026.71},
  annote =	{Keywords: FSS, Data Structures, Lower Bounds, Black-Box Reductions}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.ITC.2025
LIPIcs, Volume 343, ITC 2025, Complete Volume

Authors: Niv Gilboa

Published in: LIPIcs, Volume 343, 6th Conference on Information-Theoretic Cryptography (ITC 2025)

Abstract
LIPIcs, Volume 343, ITC 2025, Complete Volume
Cite as

6th Conference on Information-Theoretic Cryptography (ITC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 343, pp. 1-258, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@Proceedings{gilboa:LIPIcs.ITC.2025,
  title =	{{LIPIcs, Volume 343, ITC 2025, Complete Volume}},
  booktitle =	{6th Conference on Information-Theoretic Cryptography (ITC 2025)},
  pages =	{1--258},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-385-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{343},
  editor =	{Gilboa, Niv},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2025},
  URN =		{urn:nbn:de:0030-drops-246585},
  doi =		{10.4230/LIPIcs.ITC.2025},
  annote =	{Keywords: LIPIcs, Volume 343, ITC 2025, Complete Volume}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.ITC.2025.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Niv Gilboa

Published in: LIPIcs, Volume 343, 6th Conference on Information-Theoretic Cryptography (ITC 2025)

Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as

6th Conference on Information-Theoretic Cryptography (ITC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 343, pp. 0:i-0:xii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{gilboa:LIPIcs.ITC.2025.0,
  author =	{Gilboa, Niv},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{6th Conference on Information-Theoretic Cryptography (ITC 2025)},
  pages =	{0:i--0:xii},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-385-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{343},
  editor =	{Gilboa, Niv},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2025.0},
  URN =		{urn:nbn:de:0030-drops-246579},
  doi =		{10.4230/LIPIcs.ITC.2025.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
DOI: 10.4230/LIPIcs.ITC.2022.17
Information-Theoretic Distributed Point Functions

Authors: Elette Boyle, Niv Gilboa, Yuval Ishai, and Victor I. Kolobov

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

Abstract
A distributed point function (DPF) (Gilboa-Ishai, Eurocrypt 2014) is a cryptographic primitive that enables compressed additive secret-sharing of a secret weight-1 vector across two or more servers. DPFs support a wide range of cryptographic applications, including efficient private information retrieval, secure aggregation, and more. Up to now, the study of DPFs was restricted to the computational security setting, relying on one-way functions. This assumption is necessary in the case of a dishonest majority. We present the first statistically private 3-server DPF for domain size N with subpolynomial key size N^{o(1)}. We also present a similar perfectly private 4-server DPF. Our constructions offer benefits over their computationally secure counterparts, beyond the superior security guarantee, including better computational complexity and better protocols for distributed key generation, all while having comparable communication complexity for moderate-sized parameters.
Cite as

Elette Boyle, Niv Gilboa, Yuval Ishai, and Victor I. Kolobov. Information-Theoretic Distributed Point Functions. In 3rd Conference on Information-Theoretic Cryptography (ITC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 230, pp. 17:1-17:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{boyle_et_al:LIPIcs.ITC.2022.17,
  author =	{Boyle, Elette and Gilboa, Niv and Ishai, Yuval and Kolobov, Victor I.},
  title =	{{Information-Theoretic Distributed Point Functions}},
  booktitle =	{3rd Conference on Information-Theoretic Cryptography (ITC 2022)},
  pages =	{17:1--17:14},
  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.17},
  URN =		{urn:nbn:de:0030-drops-164957},
  doi =		{10.4230/LIPIcs.ITC.2022.17},
  annote =	{Keywords: Information-theoretic cryptography, homomorphic secret sharing, private information retrieval, secure multiparty computation}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2022.27
Locality-Preserving Hashing for Shifts with Connections to Cryptography

Authors: Elette Boyle, Itai Dinur, Niv Gilboa, Yuval Ishai, Nathan Keller, and Ohad Klein

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

Abstract
Can we sense our location in an unfamiliar environment by taking a sublinear-size sample of our surroundings? Can we efficiently encrypt a message that only someone physically close to us can decrypt? To solve this kind of problems, we introduce and study a new type of hash functions for finding shifts in sublinear time. A function h:{0,1}ⁿ → ℤ_n is a (d,δ) locality-preserving hash function for shifts (LPHS) if: (1) h can be computed by (adaptively) querying d bits of its input, and (2) Pr[h(x) ≠ h(x ≪ 1) + 1] ≤ δ, where x is random and ≪ 1 denotes a cyclic shift by one bit to the left. We make the following contributions. - Near-optimal LPHS via Distributed Discrete Log. We establish a general two-way connection between LPHS and algorithms for distributed discrete logarithm in the generic group model. Using such an algorithm of Dinur et al. (Crypto 2018), we get LPHS with near-optimal error of δ = Õ(1/d²). This gives an unusual example for the usefulness of group-based cryptography in a post-quantum world. We extend the positive result to non-cyclic and worst-case variants of LPHS. - Multidimensional LPHS. We obtain positive and negative results for a multidimensional extension of LPHS, making progress towards an optimal 2-dimensional LPHS. - Applications. We demonstrate the usefulness of LPHS by presenting cryptographic and algorithmic applications. In particular, we apply multidimensional LPHS to obtain an efficient "packed" implementation of homomorphic secret sharing and a sublinear-time implementation of location-sensitive encryption whose decryption requires a significantly overlapping view.
Cite as

Elette Boyle, Itai Dinur, Niv Gilboa, Yuval Ishai, Nathan Keller, and Ohad Klein. Locality-Preserving Hashing for Shifts with Connections to Cryptography. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 27:1-27:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{boyle_et_al:LIPIcs.ITCS.2022.27,
  author =	{Boyle, Elette and Dinur, Itai and Gilboa, Niv and Ishai, Yuval and Keller, Nathan and Klein, Ohad},
  title =	{{Locality-Preserving Hashing for Shifts with Connections to Cryptography}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{27:1--27:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.27},
  URN =		{urn:nbn:de:0030-drops-156231},
  doi =		{10.4230/LIPIcs.ITCS.2022.27},
  annote =	{Keywords: Sublinear algorithms, metric embeddings, shift finding, discrete logarithm, homomorphic secret sharing}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2018.21
Foundations of Homomorphic Secret Sharing

Authors: Elette Boyle, Niv Gilboa, Yuval Ishai, Huijia Lin, and Stefano Tessaro

Published in: LIPIcs, Volume 94, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018)

Abstract
Homomorphic secret sharing (HSS) is the secret sharing analogue of homomorphic encryption. An HSS scheme supports a local evaluation of functions on shares of one or more secret inputs, such that the resulting shares of the output are short. Some applications require the stronger notion of additive HSS, where the shares of the output add up to the output over some finite Abelian group. While some strong positive results for HSS are known under specific cryptographic assumptions, many natural questions remain open. We initiate a systematic study of HSS, making the following contributions. - A definitional framework. We present a general framework for defining HSS schemes that unifies and extends several previous notions from the literature, and cast known results within this framework. - Limitations. We establish limitations on information-theoretic multi-input HSS with short output shares via a relation with communication complexity. We also show that additive HSS for non-trivial functions, even the AND of two input bits, implies non-interactive key exchange, and is therefore unlikely to be implied by public-key encryption or even oblivious transfer. - Applications. We present two types of applications of HSS. First, we construct 2-round protocols for secure multiparty computation from a simple constant-size instance of HSS. As a corollary, we obtain 2-round protocols with attractive asymptotic efficiency features under the Decision Diffie Hellman (DDH) assumption. Second, we use HSS to obtain nearly optimal worst-case to average-case reductions in P. This in turn has applications to fine-grained average-case hardness and verifiable computation.
Cite as

Elette Boyle, Niv Gilboa, Yuval Ishai, Huijia Lin, and Stefano Tessaro. Foundations of Homomorphic Secret Sharing. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 21:1-21:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{boyle_et_al:LIPIcs.ITCS.2018.21,
  author =	{Boyle, Elette and Gilboa, Niv and Ishai, Yuval and Lin, Huijia and Tessaro, Stefano},
  title =	{{Foundations of Homomorphic Secret Sharing}},
  booktitle =	{9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
  pages =	{21:1--21:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-060-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{94},
  editor =	{Karlin, Anna R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.21},
  URN =		{urn:nbn:de:0030-drops-83659},
  doi =		{10.4230/LIPIcs.ITCS.2018.21},
  annote =	{Keywords: Cryptography, homomorphic secret sharing, secure computation, communication complexity, worst-case to average case reductions.}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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