ProofAtlas

Cryptography · private information retrieval · lattices · data structures

Doubly Efficient Private Information Retrieval

Collaboration beta

Known DEPIR constructions use stronger structure; this source asks for an ordinary-LWE construction and maps the barriers any candidate must avoid.

Tserver(N)=N1-δpoly(λ,logN)
Known results and sources
Problem-first open-research thumbnail for Doubly Efficient Private Information Retrieval, showing an unresolved mathematical structure without a completion mark or navigation arrow.
Can ordinary LWE support strongly doubly efficient PIR? The page presents source-reported partial structure without claiming a proof.

Research problem

Exact mathematical statement

Construct stateless, unkeyed, single-server PIR from ordinary decisional LWE with deterministic database-only preprocessing, strong adaptive query privacy, sublinear communication and client work, and worst-case online server work N^(1−δ)·poly(λ, log N) strict bit operations for a constant δ>0 independent of λ.

Tserver(N)=N1-δpoly(λ,logN)T_{\mathrm{server}}(N)=N^{1-\delta}\operatorname{poly}(\lambda,\log N)

This remains open; the source reports partial results and route constraints, not a complete proof.

Problem infographic

Problem at a glance

Three-panel source-bound explainer for Doubly Efficient Private Information Retrieval: exact target, strongest retained result, and the unresolved closing bridge.
The source separates the exact target, retained partial results, and the still-open bridge.

Current mathematical picture

Where work on Doubly Efficient Private Information Retrieval stands

Open problem

Selected route highlights from the mathematical source. This is not yet a complete mathematical inventory.

Useful failureMarginal same-secret hybrid reasoning

Exact one-read AMR transcript import is the highest-value next artifact; joint-channel, replay, adaptive-reuse, parameter, and strict-bit obligations remain.

Route status · Narrowed route
Main reductionCurrent reduction

Import the exact one-read RAM transcript, audit every deterministic equal-output image and same-secret channel, then determine whether the mixed-secret defect is terminal, transparent, annihilated, or database-sensitive.

Evidence posture · Source-reported route statement · dependencies incomplete
Priority open bridgeImport the exact one-read AMR transcript.Task status · Ready to work on
Research-record correctionResearch-record correction

We corrected the cited passages. We updated the highlighted open task or route. The mathematical claims and their status did not change.

Reader-facing record corrected; mathematics unchanged

Work mapped so far

Doubly Efficient Private Information Retrieval in numbers

11.2kretained lines of mathematical investigation11,223 in the current working snapshot
Argument development
9,083 · 81%
Explored or eliminated routes
155 · 1%
Computational analysis
503 · 4%
Open obligations
322 · 3%
Definitions and setup
1,160 · 10%
7selected mapped statements1routes investigated3open questions3contribution-ready tasks
How this is measured

This measures retained mathematical investigation, not proximity to a proof. Code, data, logs, repeated text, operational instructions, and generated presentation copy are excluded.

Status checkedAug 21, 2026
Source recordedAug 21, 2026

Argument map and routes

How the current approaches connect

Claims, reductions, open questions, active routes, and narrowed alternatives in one mathematical map.

Visible working map

Research route map

11 selected steps

Selected claims, active routes, useful failures, and open questions from the current research map. Arrows appear only for explicitly recorded relationships.

11 selected steps

Scroll horizontally to explore the route

Working route overview for Doubly Efficient Private Information RetrievalA selected map of recorded claims, active routes, useful failures, open questions, and their explicit relationships. Search, filter, zoom, or pan within this page.Can ordinary LWE support strongly doubly efficient PIR? — Depends on missing premiseCan ordinary LWE supportstrongly doubly efficientPIR?Approximate capsule route — Depends on missing premiseApproximate capsule routeCurrent reduction — Depends on missing premiseCurrent reductionStrong ordinary-LWE target — Depends on missing premiseStrong ordinary-LWE targetClosing target — Depends on missing premiseClosing targetJoint-channel warning — Depends on missing premiseJoint-channel warningPublic image replay — Depends on missing premisePublic image replayMarginal same-secret hybrid reasoning — stoppedMarginal same-secret hybridreasoningImport the exact one-read AMR transcript. — OpenImport the exact one-readAMR transcript.Prove joint same-secret pseudorandomness or identify a separation. — OpenProve joint same-secretpseudorandomness or identifya…Prove the approximate capsule barrier if the full transcript formulas remain unavailable. — OpenProve the approximatecapsule barrier if the fulltranscript…
Working claimActive routeOpen, active, or blocked questionUseful failure

Working overview, not proof. The map shows selected recorded relationships; more nodes or edges do not establish correctness or completion.

Explored alternatives

Other routes

1 recorded
Narrowed routeMarginal same-secret hybrid reasoning

Exact one-read AMR transcript import is the highest-value next artifact; joint-channel, replay, adaptive-reuse, parameter, and strict-bit obligations remain.

Route status · Narrowed route

More ways to contribute

Open questions

Additional prepared tasks for exploring this research frontier.

3 featured tasks
01
Import the exact one-read AMR transcript.Suggested move: Build the ownership/exposure table.
Ready to work on
02
Prove joint same-secret pseudorandomness or identify a separation.Suggested move: Stop on any replayable deterministic candidate image.
Ready to work on
03
Prove the approximate capsule barrier if the full transcript formulas remain unavailable.Suggested move: Analyze approximate same-coin or candidate-replay statistics for the actual capsule family.
Ready to work on

Sourced mathematical context

The known mathematical landscape

Context collected Aug 21, 2026
Current statusOpen problem

Recent work gives barely doubly-efficient PIR from plain LWE in the CRS model and broad black-box limitations; the current work's stronger stateless, unkeyed, deterministic-preprocessing endpoint remains open.

[1][2]
External progress

What the literature has established

Selected external milestones in reverse chronological order, with their evidence posture.

  1. Peer reviewedBarely Doubly-Efficient SimplePIR supplies a representative external result or boundary relevant to the problem; it is not treated here as a proof of the full packet target.[1]
  2. Peer reviewedBlack Box Crypto is Useless for Doubly Efficient PIR supplies a representative external result or boundary relevant to the problem; it is not treated here as a proof of the full packet target.[2]
2 cited sources1 related results or reductionsReferences

Mathematical neighborhood

Related results and reusable starting points

Current focusDoubly Efficient Private Information Retrieval
Related problemDoubly Efficient Private Information Retrieval

Recent work gives barely doubly-efficient PIR from plain LWE in the CRS model and broad black-box limitations; the packet's stronger stateless, unkeyed, deterministic-preprocessing endpoint remains open.

[1][2]

Formalization opportunities

Lean work can make these reusable foundations precise without being presented as a proof of the core problem.

  • Formalization targetA formal statement matching the exact public target and all quantifiers.
  • Formalization targetFormal libraries for the principal mathematical structures used by the strongest route.
  • Formalization targetA checked closing argument for the source-identified open bridge.

Research-record corrections

What changed in the research record

These notes describe corrections to cited passages, highlighted tasks, or connections between claims. The mathematical claims and their status did not change.

Research-record correctionWe corrected the cited passages. We updated the highlighted open task or route. The mathematical claims and their status did not change.

Corrected the research recordCorrection note

Correction details
Research-record correctionWe corrected the cited passages. We removed a duplicate or outdated task or route step. We updated the highlighted open task or route. The mathematical claims and their status did not change.

Corrected the research recordCorrection note

Correction details
Research-record correctionWe corrected supporting details in the research record. The mathematical claims and their status did not change.

Corrected the research recordCorrection note

Correction details

The initial argument structure appears separately. Uploads, model runs, and presentation changes do not count as mathematical updates.

Detailed research inventory

Claims, milestones, and routes in the current map

This view highlights the mathematical statements most useful for following the current route.

4 standing statements3 proposed statements3 open questions1 narrowed routes
Statements by mathematical role7 selected mapped statements
  • theorem candidate1 of 71
  • reduction2 of 72
  • lemma1 of 71
  • equivalence1 of 71
  • negative result2 of 72
Selected mathematical clusters1 mathematical clusters
Current research mapThe conjecture, retained reductions, explored limitations, and open questions represented in this overview.20 displayed rows · 1 route included
  • retained route statementCan ordinary LWE support strongly doubly efficient PIR?
  • retained route statementCurrent reductionintermediate
  • retained route statementClosing targetintermediate
  • retained route statementStrong ordinary-LWE targetintermediate
  • retained route statementJoint-channel warningintermediate
  • retained route statementPublic image replayintermediate
  • retained route statementApproximate capsule routeintermediate
  • Recorded relationshipThe source reports this as a route toward the conjecture; missing or unaudited premises remain and the reduction does not itself prove the target.supports · reported by source
  • Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
  • Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
  • Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
  • Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
  • DerivationThe source reports that completing the closing target would advance the reduction to the main conjecture; this remains an informal route, not a verified derivation.proposed
  • Useful failureMarginal same-secret hybrid reasoningreported failure
  • Research targetImport the exact one-read AMR transcript.open
  • Research targetProve joint same-secret pseudorandomness or identify a separation.open
  • Research targetProve the approximate capsule barrier if the full transcript formulas remain unavailable.open
  • Research targetExact one-read transcriptsuperseded
  • Research targetOrdinary-LWE reductionsuperseded
  • Narrowed routeMarginal same-secret hybrid reasoningExact one-read AMR transcript import is the highest-value next artifact; joint-channel, replay, adaptive-reuse, parameter, and strict-bit obligations remain.
How to interpret these counts

A statement may be a lemma, conditional reduction, special case, documented limitation, or open target. These counts describe the work's structure; they do not estimate distance to a proof.

Research outlook

Conditions that would advance the current route

Priority open bridgeImport the exact one-read AMR transcript.

The selected overview records one narrowed route. Exact one-read AMR transcript import is the highest-value next artifact; further privacy, assumption, adaptive-reuse, parameter, and strict-bit obligations remain.

Evidence needed nextConcrete conditions for progress

A result can change the outlook by closing the bridge, narrowing its scope, or showing that the route cannot work.

  • Supply a complete argument with every imported premise identified.
  • Survive an independent attempt to falsify the proposed step.

Continue the mathematics

Contribute

ProofAtlas supplies a prepared task with the mathematical statement, current context, known obstacles, and a useful next move. Work directly or pass it to an AI agent, then return whatever moved the problem forward.

Read-only beta · actions unavailable
Prepared starting pointImport the exact one-read AMR transcript.

Doubly Efficient Private Information Retrieval · ready to start

Mathematical updatesFollow this problem

Receive an update when a route advances, an obstacle is clarified, or new evidence changes the mathematical picture.

Research contextPrepared context for any AI agent

Known DEPIR constructions use stronger structure; this source asks for an ordinary-LWE construction and maps the barriers any candidate must avoid.

  • Exact question and boundaries
  • Current routes and known obstacles
  • What a useful result should report
Return mathematical workReturn what you or your agent found

A proof attempt, partial advance, counterexample, useful failure, or corrected dependency can all move the shared frontier forward.

Proof attempt or partial resultSupporting notes or data
Hosted agentRun this task with a hosted agent

A hosted agent can work from the same prepared question, routes, evidence, and suggested next step.

Your own AI agentConnect an outside research agent

Your agent can receive the prepared task and return a proof attempt, objection, computation, or useful failure to the same research frontier.

Sources and references2 cited works · next context review by Nov 21, 2026

The mathematical context was checked on Aug 21, 2026. Status can be refreshed sooner after a material result or claim.

  1. 1
    Barely Doubly-Efficient SimplePIRpeer reviewed result · Keewoo Lee · IACR ePrint; CRYPTO 2026 · 2025 · accessed Aug 21, 2026
  2. 2
    Black Box Crypto is Useless for Doubly Efficient PIRpeer reviewed result · Wei-Kai Lin, Ethan Mook, Daniel Wichs · IACR ePrint; EUROCRYPT 2025 · 2025 · accessed Aug 21, 2026

Important qualifications

  • This was a bounded status and identity check, not an exhaustive bibliography, priority review, or legal review.
  • Private packet claims were not treated as external authority; submitted links and attachments were not executed or actively rendered.
  • No absence claim is inferred from the bounded search, and recent preprints remain subject to ordinary scholarly review.

Continue exploring

Compare another research frontier

See how a different problem changes the proof map, useful lemmas, failed routes, and suggested next tasks.

Explore all research workspaces

Expanded visual

Open original image