Vi introducerar idén om ett databassystem som teoretiskt sett är säkert mellan accesses-a databassystem med de egenskaper som 1) användare effektivt kan få tillgång till sina data, och 2) medan en användare inte har tillgång till sina data, användarens information är teoretiskt säker för skadliga agenter, förutsatt att vissa krav på underhåll av databasen realiseras. Vi betonar att säkerhetsgarantin är informationsteoretisk och evig: den bygger varken på obevisade hårdhetsantaganden eller på antagandet att motståndaren är beräknande eller lagring begränsad. Vi föreslår ett förverkligande av ett sådant databassystem och bevisar att en användares lagrade information, mellan tider då den är legitimt åtkomlig, är information teoretiskt säker både för motståndare som interagerar med databasen på föreskrivet sätt, samt för motståndare som har installerat ett virus som har tillgång till hela databasen och kommunicerar med motståndaren. Den centrala idén bakom vår design av ett teoretiskt säkert databassystem är byggandet av en "omrandomizing databas" som regelbundet ändrar den interna representationen av den information som lagras. För att säkerställa säkerheten måste dessa omdaningar av datarepresentationen göras tillräckligt ofta i jämförelse med den mängd information som förmedlas från databasen mellan omdaningar och den mängd lokalt minne i databasen som ett virus kan bevara under omdaningarna. Även om denna förändrade representation på ett tydligt sätt kullkastar en motståndares förmåga att inhämta information, kan det åstadkommas på ett sätt som är öppet för de legitima användarna, vilket bevarar hur databasanvändare får tillgång till sina uppgifter. Kärnan i beviset på säkerhetsgarantin är följande kommunikations-/dataavräkning för problemet med att lära sig sparsamma pariteter från enhetligt slumpmässiga n-bitars exempel. Rätta en uppsättning S  till {1,..., n} i storlek k: givet tillgång till exempel x 1,. ..., x t där x i  till {0, 1} n väljs enhetligt på måfå, beroende på XOR av komponenterna i x indexerade med S lika med 0, alla algoritmer som lär sig uppsättningen S med sannolikhet minst p och extraherar som mest r bitar av information från varje exempel, måste se minst p · n r k/2 c k exempel, för c k ≥ 1 4 · (2e) k k+3. De r bitar av information som extraheras från varje exempel kan vara en godtycklig (adaptivt vald) funktion av hela exemplet, och behöver inte bara vara en delmängd av bitarna i exemplet.
Valiants och Valiants främsta motiv var att bygga teoretiskt säkra databaser REF.
Information Theoretically Secure Databases
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}