DROPS

Document

DOI: 10.4230/LIPIcs.ITC.2026.1

Tighter Bounds for the Oblivious Bit-Fixing Inner Product Extractor on Biased Seeds

Authors: Jack Doerner and Lawrence Roy

Published in: LIPIcs, Volume 385, 7th Conference on Information-Theoretic Cryptography (ITC 2026)

Abstract

The Inner Product Extractor (IPE) of Impagliazzo, Levin, and Luby (STOC'89) takes a seed h ∈ 𝔽^γ and a source x ∈ {0,1}^γ for some γ ∈ ℕ and produces ⟨h,x⟩ with error ε = SD((⟨ℋ,𝒳⟩,ℋ),(𝒴,ℋ)) such that ε ≤ 1/2√{|𝔽|^{γ}/2^{H_∞(ℋ)}} √{|𝔽|/2^{H_∞(𝒳)}} where 𝒴 is the uniform distribution over 𝔽, and ℋ and 𝒳 are the independent but possibly non-uniform distributions from which h and x are drawn, respectively. In other words, the IPE’s error grows with the square root of seed bias, at most. This square root arises because prior works bound the squared error using the 2-universality of the IPE. The analysis requires an even power of the error, and the IPE is not 4-universal. Motivated by applications to multiparty computation, we revisit the problem of the IPE with biased seeds and prove far tighter bounds on the influence of seed bias by bypassing universal hashing. We first prove an Elevated General Leftover Hash Lemma, which yields an n^th root bound for functions that are almost n-universal. Bounding number of inputs on which the IPE is not 4-universal yields ε = SD((⟨ℋ,𝒲⟩,ℋ),(𝒴,ℋ)) where ε ≲ 2.1/2 (|𝔽|^γ/2^{H_∞(ℋ)}) ^{1/4} √{|𝔽|/2^{H_∞(𝒲)}} for any oblivious bit-fixing source 𝒲 with 2^{0.585 H_∞(𝒲)} ≤ |𝔽| ≤ 2^{H_∞(𝒲)}. Next, we use matroid theory to directly analyze the n-way multicollision probability of the IPE, yielding an asymptotic bound for any even n. For n ≥ 4, 0 < ε ≤ 0.83/(n - 2), and |𝔽| ≤ 2^{(1 - ε)⋅ H_∞(𝒲)}, as |𝔽| → ∞, ε ≤ (n - 1)/2 (|𝔽|^γ/2^{H_∞(ℋ)})^(1/n) √{2^{-ε⋅ H_∞(𝒲)}} (1 + o(1)). Computing a concrete version of this bound requires time exponential in n. We compute concrete {4,6,8}^th-root bounds and demonstrate that no one choice of n is optimal. Finally, we introduce a new class of seed-adaptive oblivious bit-fixing sources, extend our results to such sources, and use this extension to fix a bug that we identify in the proof of the oblivious linear evaluation protocol of Doerner et al. (SP'24).

Cite as

Jack Doerner and Lawrence Roy. Tighter Bounds for the Oblivious Bit-Fixing Inner Product Extractor on Biased Seeds. In 7th Conference on Information-Theoretic Cryptography (ITC 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 385, pp. 1:1-1:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{doerner_et_al:LIPIcs.ITC.2026.1,
  author =	{Doerner, Jack and Roy, Lawrence},
  title =	{{Tighter Bounds for the Oblivious Bit-Fixing Inner Product Extractor on Biased Seeds}},
  booktitle =	{7th Conference on Information-Theoretic Cryptography (ITC 2026)},
  pages =	{1:1--1:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-426-0},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{385},
  editor =	{Dodis, Yevgeniy},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2026.1},
  URN =		{urn:nbn:de:0030-drops-270946},
  doi =		{10.4230/LIPIcs.ITC.2026.1},
  annote =	{Keywords: Leftover hash lemma, Inner product extractor, Randomness extraction, Oblivious linear evaluation}
}

Document

DOI: 10.4230/LIPIcs.ITC.2025.5

Information-Theoretic Random-Index PIR

Authors: Sebastian Kolby, Lawrence Roy, Jure Sternad, and Sophia Yakoubov

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

Abstract

A Private Information Retrieval (PIR) protocol allows a client to learn the ith row of a database held by one or more servers, without revealing i to the servers. A Random-Index PIR (RPIR) protocol, introduced by Gentry et al. (TCC 2021), is a PIR protocol where, instead of being chosen by the client, i is random. This has applications in e.g. anonymous committee selection. Both PIR and RPIR protocols are interesting only if the communication complexity is smaller than the database size; otherwise, the trivial solution where the servers send the entire database suffices. Unlike PIR, where the client must send at least one message (to encode information about i), RPIR can be executed in a single round of server-to-client communication. In this paper, we study such one-round, information-theoretic RPIR protocols. The only known construction in this setting is SimpleMSRPIR (Gentry et al.), which requires the servers to communicate approximately N/2 bits, N being the database size. We show an Ω(√N) lower bound on communication complexity for one-round two-server information-theoretic RPIR, and a sublinear upper bound. Finally, we show how to use a sublinear amount of database-independent correlated randomness among multiple servers to get near-optimal online communication complexity (the size of one row plus the size of one index description per server).

Cite as

Sebastian Kolby, Lawrence Roy, Jure Sternad, and Sophia Yakoubov. Information-Theoretic Random-Index PIR. In 6th Conference on Information-Theoretic Cryptography (ITC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 343, pp. 5:1-5:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kolby_et_al:LIPIcs.ITC.2025.5,
  author =	{Kolby, Sebastian and Roy, Lawrence and Sternad, Jure and Yakoubov, Sophia},
  title =	{{Information-Theoretic Random-Index PIR}},
  booktitle =	{6th Conference on Information-Theoretic Cryptography (ITC 2025)},
  pages =	{5:1--5:15},
  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.5},
  URN =		{urn:nbn:de:0030-drops-243559},
  doi =		{10.4230/LIPIcs.ITC.2025.5},
  annote =	{Keywords: Private information retrieval, Multi-server, Lower bounds}
}

Search Results

Documents authored by Roy, Lawrence

Tighter Bounds for the Oblivious Bit-Fixing Inner Product Extractor on Biased Seeds

Abstract

Cite as

Information-Theoretic Random-Index PIR

Abstract

Cite as

Thanks for your feedback!

Could not send message