🔢 mathematics

On (Im)possibility of Network Oblivious Transfer via Noisy Channels and Non-Signaling Correlations

Dit artikel stelt vast dat perfecte oblivious transfer fundamenteel onmogelijk is over ruisgevoelige kanalen aangevuld met algemene tripartiete non-signaling correlaties, aangezien herhaald gebruik onvermijdelijk de lekkage van berichten naar de ontvanger(s) versterkt, hoewel de privacy van de ontvanger(s) zelf theoretisch haalbaar blijft.

Oorspronkelijke auteurs: Hadi Aghaee, Christian Deppe, Holger Boche

Gepubliceerd 2026-02-04

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Hadi Aghaee, Christian Deppe, Holger Boche

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je een beveiligde digitale kluis probeert te bouwen waar twee mensen (laten we ze Alice-1 en Alice-2 noemen) geheime berichten naar een derde persoon (Bob) willen sturen. De regels van het spel zijn streng:

De Kluis: Bob moet één specifiek bericht van elke Alice kunnen kiezen en dit perfect kunnen lezen.
De Blinddoek: Bob mag niet kunnen achterhalen welk bericht hij niet heeft gekozen.
De Ruis: De berichten reizen via een "ruisig" kanaal, zoals een walkie-talkie met statische elektriciteit, wat zaken meestal door elkaar husselt.

Decennialang hebben wetenschappers zich afgevraagd: Kunnen we "superkrachtige" verbindingen (genaamd Non-Signaling correlaties) gebruiken om de ruis te herstellen en deze kluis perfect veilig te maken? Deze verbindingen zijn als magische telepathie die mensen in staat stelt om hun acties direct te coördineren zonder signalen te verzenden, vergelijkbaar met het beroemde "kwantumverstrengeling", maar dan nog sterker.

Dit artikel zegt: Nee. Het is onmogelijk.

Hier is de uitsplitsing van hun bevindingen met behulp van eenvoudige analogieën:

1. De "Magische Doos" versus de "Ruisende Walkie-Talkie"

De onderzoekers stelden zich een scenario voor waarin Alice-1, Alice-2 en Bob allemaal een speciale "Magische Doos" (een Non-Signaling box) delen. Deze doos laat hen hun antwoorden perfect coördineren, zelfs als ze ver uit elkaar zijn, zonder de wetten van de fysica te schenden (specifiek: ze kunnen het niet gebruiken om geheime signalen sneller dan het licht te verzenden).

Ze vroegen zich af: Als we deze Magische Doos gebruiken om over een ruisende walkie-talkie te praten, kunnen we dan eindelijk een perfect Oblivious Transfer (OT) systeem bouwen?

De Resultaat: Nee. Zelfs met deze superkrachtige Magische Doos faalt het systeem.

2. De "Lekkage"-analogie: De Versterkende Echo

Waarom faalt het? Het paper legt uit dat de Magische Doos een subtiele "echo" of correlatie creëert tussen de zenders en de ontvanger.

Het Probleem: In een perfect OT-systeem zou Bob alleen informatie moeten krijgen over het bericht dat hij heeft gekozen. Maar omdat van de Magische Doos, wordt de manier waarop Bob het bericht ontvangt, licht beïnvloed door het bericht dat hij niet heeft gekozen.
De Versterking: Denk hierbij aan een fluistering in een kloof. Als je een geheim fluistert, kan de echo misschien een klein hint geven van wat je zei. In een normaal ruisig kanaal gaat zo'n hint verloren in de statische elektriciteit. Maar met de Magische Doos wordt de "hint" versterkt.
Het Resultaat: Als Bob het kanaal genoeg keer beluistert (het proces herhaalt), worden de kleine hints over de ongewenste berichten steeds luider en luider. Uiteindelijk kan Bob de berichten die hij niet heeft gekozen perfect onderscheiden. De "Blinddoek" valt af.

3. De "Causaliteit"-paradox: Het Dilemma van de Tijdreiziger

Het paper duikt dieper in waarom dit gebeurt met behulp van een concept genaamd Causaliteit (oorzaak en gevolg).

De Regel van OT: Bobs keuze (bijv. "Ik wil Bericht A") moet de oorzaak zijn dat hij Bericht A krijgt. Hij zou Bericht A niet moeten krijgen, tenzij hij er specifiek om heeft gevraagd.
De Regel van de Magische Doos: De Magische Doos is "Non-Signaling". Dit betekent dat de output van de doos niet afhankelijk kan zijn van wat de andere persoon later beslist. De doos moet direct klaar zijn, ongeacht wat anderen doen.
De Botsing: De onderzoekers ontdekten dat deze twee regels met elkaar in strijd zijn. Om de Magische Doos te laten werken, moet deze Bobs keuze negeren totdat na het verzenden van de berichten. Maar om OT te laten werken, moet Bobs keuze het bericht bepalen voordat het volledig onthuld is.
De Metafoor: Stel je een ober voor die een bestelling opneemt.
- OT-regel: De ober moet wachten tot je zegt "Ik neem de burger" voordat hij de burger brengt.
- Magische Doos-regel: De keuken moet de burger bereiden voordat je überhaupt gaat zitten, omdat de keuken "non-signaling" is en niet kan wachten op je bestelling.
- Het Conflict: Als de keuken de burger bereidt voordat je bestelt, kunnen ze je de burger brengen, zelfs als je eigenlijk een salade wilde. Het systeem breekt omdat de "oorzaak" (jouw bestelling) losgekoppeld is van het "gevolg" (het eten).

4. Wat als er slechts twee mensen zijn?

Het paper keek ook naar een simpelere versie: Wat als alleen de twee zenders de Magische Doos delen, maar de ontvanger (Bob) niet?

De Bevinding: In dit specifieke geval zegt het paper dat we nog niet kunnen bewijzen dat het onmogelijk is. Het is een open vraag. Het is alsof men zegt: "We weten dat het hele team niet kan winnen met deze strategie, maar misschien kunnen twee teamgenoten nog steeds winnen als ze alleen een geheime handdruk delen."

5. Wat betreft de privacy van Bob?

Het paper controleerde ook of de privacy van Bob (het geheim houden van zijn keuze voor de zenders) veilig is.

De Bevinding: In tegen tegenstelling tot de privacy van de zenders, is de privacy van Bob niet automatisch gedoemd. Dit hangt volledig af van hoe het protocol is ontworpen. Als het protocol zorgvuldig is gebouwd, kan Bob zijn keuze geheim houden. Als het slecht is gebouwd, kan hij het lekken. Er is geen universele "ondergang" voor Bob, alleen voor de zenders.

Samenvatting

Het paper concludeert dat je geen perfect, veilig "Oblivious Transfer" systeem kunt bouwen over een gedeeld ruisig netwerk, zelfs als je toegang hebt tot de meest krachtige "super-kwantum" correlaties (Non-Signaling boxes) die je je kunt voorstellen.

De fundamentele reden is dat deze super-correlaties de noodzakelijke "oorzaak-en-gevolg"-link verbreken tussen de keuze van een gebruiker en het bericht dat hij ontvangt. Hoe meer je deze correlaties probeert te gebruiken om de ruis te herstellen, hoe meer je per ongeluk de geheimen lekt die je juist probeerde te beschermen.

Kortom: Je kunt niet je taart eten (perfecte beveiliging) én tegelijkertijd de taart opeten (super-correlaties gebruiken om ruis te herstellen) wanneer het gaat om dit specifieke type netwerkcommunicatie. De wetten van de informatietheorie zeggen "Nee".

Technische Samenvatting: Over de (on)mogelijkheid van Netwerk Oblivious Transfer via Ruisende Kanalen en Non-Signaling Correlaties

1. Probleemstelling

Dit werk onderzoekt de fundamentele limieten voor het implementeren van netwerk oblivious transfer (OT) over gedeelde ruisende communicatiekanalen wanneer partijen toegang hebben tot algemene tripartiete non-signaling (NS) correlaties. De studie richt zich op twee primaire netwerktopologieën:

Discrete Memoryless Multiple-Access Channels (DM-MAC): Twee zenders (Alice-1, Alice-2) die communiceren met een enkele ontvanger (Bob).
Discrete Memoryless Broadcast Channels (DM-BC): Eén zender die communiceert met twee ontvangers (Bob-1, Bob-2).

De centrale onderzoeksvraag is of de aanwezigheid van krachtige non-signaling bronnen (die klassieke correlaties, kwantumverstrengeling en super-kwantum correlaties zoals Popescu-Rohrlich-boxen omvatten) de bekende informatie-theoretische onmogelijkheidsresultaten voor OT over ruisende kanalen kan overwinnen. Specifiek vraagt de tekst of dergelijke correlaties het volgende kunnen mogelijk maken:

Perfecte OT: Foutloze transmissie met nul lekkage.
Asymptotische OT: Verwaarloosbare fout en lekkage naarmate de bloklengte toeneemt.

De auteurs beschouwen een scenario waarin de NS-bron wordt gedeeld door alle partijen (tripartiet) of, in specifieke subgevallen, tussen subsets van partijen (bipartiet).

2. Methodologie en Systeemmodel

Het artikel hanteert een verenigd informatie-theoretisch kader om zowel het gedrag van het fysieke kanaal als de gedeelde correlatiebronnen te modelleren.

Tripartiete NS-box: De gedeelde bron wordt gemodelleerd als een willekeurige tripartiete non-signaling box gedefinieerd door een conditionele waarschijnlijkheidsverdeling $P(x_1, x_2, (j_1, j_2) \mid i_1, i_2, y)$ voor het MAC-geval (en analoog voor BC). De NS-eigenschap dwingt af dat de marginale verdeling van een subset van partijen onafhankelijk is van de inputs van de anderen. Dit zorgt ervoor dat er geen signaling plaatsvindt via de correlatiebron zelf.
Protocolstructuur: Het protocol omvat deterministische codering van berichten naar NS-box inputs en kanaal-inputs, transmissie over het ruisende kanaal, en decodering met behulp van kanaaloutputs en NS-box outputs. Publieke communicatie is toegestaan, maar moet voldoen aan non-collusie aannames.
Beveiligingsdefinities:
- Correctheid (Correctness): De ontvanger moet het geselecteerde bericht met hoge waarschijnlijkheid decoderen (asymptotisch perfect).
- Zenderbeveiliging (SfA): De ontvanger mag niets leren over de niet-geselecteerde berichten (nul wederzijdse informatie in de limiet).
- Ontvangerbeveiliging (SfB): De zenders mogen niets leren over de keuze-bits van de ontvanger.
Triviale versus Niet-Triviale Boxen: De auteurs maken onderscheid tussen "triviale" NS-boxen (waar outputs statistisch onafhankelijk zijn van inputs, afgezien van lokale willekeurigheid) en "niet-triviale" boxen (waar inputs de outputs beïnvloeden).

3. Belangrijkste Bijdragen en Resultaten

A. Onmogelijkheid van Perfecte en Asymptotische OT met Tripartiete NS-Assistentie

De primaire bijdrage van het artikel is een rigoureus bewijs dat perfecte OT onmogelijk is over DM-MAC's en DM-BC's wanneer alle partijen een tripartiete NS-correlatie delen, ongeacht of de correlatie triviaal of niet-triviaal is.

Onmogelijkheid van Perfecte OT (Theorem 1 & 6):
- Voor een niet-triviale NS-box wordt het zicht van de ontvanger op de kanaaloutput statistisch afhankelijk van de inputs van de zenders op een manier die de zenderprivacy schendt. Specifiek is de decoderingwet afhankelijk van de gezamenlijke inputs van beide zenders, waardoor de ontvanger informatie kan afleiden over niet-geselecteerde berichten.
- Voor een triviale NS-box biedt de bron geen correlatie die nuttig is voor het onderscheiden van inputs, wat betrouwbare communicatie (correctheid) onmogelijk maakt.
- Het bewijs maakt gebruik van entropie-ongelijkheden en de dataverwerkingsongelijkheid om aan te tonen dat de NS-restricties tot een tegenstrijdigheid leiden tussen de eis dat de ontvanger het geselecteerde bericht decodeert en de eis om onwetend te blijven over het niet-geselecteerde bericht.
Onmogelijkheid van Asymptotische OT (Theorem 4):
- Zelfs in het asymptotische regime waar fout en lekkage mogen verdwijnen, kan verwaarloosbare lekkage niet worden bereikt met niet-triviale tripartiete NS-boxen.
- De auteurs demonstreren dat herhaaldelijk gebruik van een met een niet-triviale NS-box geassisteerd kanaal het vermogen van de ontvanger versterkt om tussen verschillende encoder-inputs te onderscheiden. Via een hypothesetest-argument laten ze zien dat de totale variatieafstand tussen de visies van de ontvanger voor twee bericht-tuples (die alleen verschillen in een niet-geselecteerd bestand) exponentieel snel naar 1 nadert.
- Bij consequentie komt de wederzijdse informatie tussen de niet-geselecteerde berichten en de visie van de ontvanger niet tot nul, wat de zenderbeveiliging schendt.

B. Ontvangerbeveiliging (SfB) is Niet Universeel Onmogelijk

In contrast met de zenderbeveiliging, stelt het artikel vast dat er geen universeel onmogelijkheidsresultaat bestaat voor ontvangerbeveiliging (Theorem 5).

Of de keuze-bits van de ontvanger lekken, hangt af van het specifieke protocolontwerp (bijv. hoe publieke transcripten worden gegenereerd en of de zender zich aanpast aan de ontvanger).
Als het protocol zodanig is ontworpen dat publieke berichten en NS-box inputs niet afhankelijk zijn van de keuze-bits van de ontvanger, kan SfB worden gehandhaafd. Daarom is SfB een protocol-afhankelijke eigenschap en geen inherente beperking van het NS-geassisteerde kanaalmodel.

C. Bipartiete NS-Correlaties

Het artikel behandelt kort de situatie waarin NS-correlaties alleen worden gedeeld tussen de twee zenders (in MAC) of de twee ontvangers (in BC), maar niet met de derde partij.

Theorem 7: Voor een bipartite NS-box die exclusief wordt gedeeld tussen de twee zenders (waarbij de ontvanger geen toegang heeft), tonen de auteurs aan dat geen universele informatie-theoretische onmogelijkheid voor perfecte OT kan worden afgeleid.
De Markov-ketens die nodig zijn om lekkage in het tripartiete geval af te dwingen, kunnen niet worden vastgesteld omdat de ontvanger noch de NS-box outputs, noch de zender-zijde variabelen direct waarneemt. Het artikel merkt echter op dat als partijen mogen samenwerken (collude), OT instort.

D. Causale Analyse en Vergelijking met PR-Box Equivalentie

Het artikel biedt een diepe causale analyse die uitlegt waarom NS-correlaties falen om OT te ondersteunen in netwerksituaties, in contrast met de bekende equivalentie tussen OT en PR-boxen in abstracte settings (Wolf en Wullschleger [39]).

Causale Ineenstorting: OT vereist een "positieve, functionele" causaliteit waarbij de private keuze van de ontvanger causaal bepaalt welke boodschap wordt gereconstrueerd. NS-restricties dwingen een "negatieve, structurele" causaliteit af (no signaling), wat voorkomt dat de keuze van de ontvanger de input van de zender beïnvloedt.
Operationele Volgorde: In het netwerkmodel moet informatie door een fysiek kanaal stromen (Encoding $\to$ Kanaal $\to$ Decoding). De NS-box fungeert slechts als een hulp-correlatie. De non-signaling restrictie impliceert dat de keuze van de ontvanger de inputs van de zender of de kanaaltransmissie niet causaal kan beïnvloeden. Dit verbreekt de causale keten die vereist is voor OT.
Resolutie van de Spanning: De auteurs lossen de schijnbare tegenstrijdigheid met de PR-box equivalentie-resultaten op door onderscheid te maken tussen stand-alone cryptografische primitieven (waar de PR-box de functionaliteit is) en hulpbronnen in communicatienetwerken (waar de PR-box een ruisend kanaal assisteert). In dat laatste geval voorkomt de operationele causaliteit van het kanaal dat de NS-bron de noodzakelijke causale onomkeerbaarheid afdwingt.

4. Betekenis en Claims

Het artikel claimt een sterk no-go resultaat vast te stellen voor netwerk OT in de aanwezigheid van tripartiete non-signaling correlaties.

Universaliteit: De onmogelijkheid geldt voor elke vorm van ruis en elk type NS-correlatie (klassiek, kwantum of super-kwantum).
Implicatie voor Quantum/6G: Omdat klassieke en kwantum correlaties subsets zijn van NS-correlaties, impliceert dit resultaat dat tripartiete verstrengeling gedeeld tussen zenders en ontvangers in een netwerksituatie inherent leidt tot informatielekkage, wat de OT-geheimhouding schendt. Dit suggereert dat het simpelweg toevoegen van kwantumbronnen aan gedeelde ruisende kanalen niet automatisch informatie-theoretische OT mogelijk maakt.
Onderscheid met vorig werk: Dit werk verheldert dat hoewel NS-correlaties OT-distributies kunnen simuleren in abstracte, ruisvrije, stand-alone settings, ze de OT-beveiliging niet kunnen garanderen wanneer ze zijn ingebed in een causaal geordend communicatieprotocol met fysieke ruisende kanalen.

De auteurs concluderen dat hoewel bipartite NS-correlaties (beperkt tot zenders of ontvangers) een potentiële weg blijven voor OT, het gebruik van tripartiete NS-bronnen de beveiliging van netwerk oblivious transfer fundamenteel ondermijnt.