Semantisk uthållighet

Ett semantiskt säkert kryptosystem inom kryptografi är ett kryptosystem som inte tillåter något läckage av meningsfull information om den ursprungliga klartexten från chiffertexten . Låt oss ta vilken probabilistisk algoritm som helst av klass PP , vars indata i det första fallet är chiffertexten för något slumpmässigt meddelande och längden på detta meddelande, och i det andra fallet endast meddelandets längd. Om skillnaden mellan sannolikheterna att erhålla viss tillförlitlig information om det ursprungliga meddelandet i det första och andra fallet är försumbar, anses kryptosystemet som producerade denna kryptering som semantiskt säkert. [1] När det gäller beräkningskomplexitet , detta koncept är analogt med det absolut säkra Shannon -chifferet . Ett helt säkert chiffer innebär att ingen information om det ursprungliga meddelandet kan erhållas alls, medan semantisk säkerhet innebär att ingen information om det ursprungliga meddelandet som finns i chiffertexten kan användas för att dekryptera något fragment av meddelandet. [2] [3] :378–381

Historik

Begreppet semantisk styrka introducerades i kryptografi av Goldwasser och Micali 1982. [1] Definitionen som de ursprungligen föreslog gav dock ingen uppskattning av styrkan hos riktiga kryptosystem. Senare visade Goldwasser och Micali att semantisk säkerhet är likvärdig med chiffertext som inte kan särskiljas för matchade klartextattacker . [4] Denna definition av semantisk styrka är vanligare, eftersom den hjälper till att bedöma styrkan hos de kryptosystem som används.

Symmetrisk kryptografi

När det gäller symmetriska kryptosystem bör motståndaren inte kunna lära sig någon information om klartexten från chiffertexten. Det betyder att motståndaren, som har två klartexter och två motsvarande chiffertexter, inte kan avgöra exakt vilken chiffertext som motsvarar vilken klartext.

Offentlig nyckelkryptering

Ett kryptosystem med offentlig nyckel sägs vara semantiskt säkert om en motståndare, i besittning av chiffertexten och den offentliga nyckeln, inte kan få någon meningsfull information om den ursprungliga klartexten. Semantisk säkerhet tar bara hänsyn till fall av passiva kryptoattacker, till exempel när en kryptoanalytiker bara kan observera överförda chiffertexter och generera sina egna chiffertexter med hjälp av den publika nyckeln. Till skillnad från andra föreställningar om säkerhet, tar semantisk säkerhet inte hänsyn till valda chiffertextattacker , där kryptoanalytikern kan dekryptera vissa valda chiffertexter, och många semantiskt starka krypteringsscheman visar sig vara svaga mot dessa typer av attacker. Därför kan semantisk styrka inte anses vara ett tillräckligt villkor för styrkan hos ett allmänt krypteringsschema.

Ciphertext omöjlig att särskilja för attacker baserade på vald klartext bestäms vanligtvis av följande experiment: [5]

  1. Ett slumpmässigt nyckelpar genereras .
  2. En motståndare, polynom tidsgräns, ges en offentlig nyckel som han kan använda för att generera valfritt antal chiffertexter (inom polynomets tidsgränser).
  3. Motståndaren genererar två meddelanden av samma längd och skickar dem till avsändaren tillsammans med den publika nyckeln.
  4. Avsändaren väljer ett av meddelandena slumpmässigt, krypterar det med den mottagna publika nyckeln och skickar den resulterande chiffertexten till motståndaren.

Kryptosystemet som övervägs har egenskapen chiffertext omöjlig att särskilja (och är således semantiskt resistent mot attacker med vald klartext) om motståndaren inte kan avgöra vilket av de två meddelandena som valdes av avsändaren med en sannolikhet som är betydligt större än (sannolikhet för slumpmässig gissning) .

Eftersom motståndaren har den publika nyckeln måste ett semantiskt säkert schema, per definition, vara probabilistiskt, det vill säga ha en slumpmässig komponent. Annars kan motståndaren, med hjälp av den publika nyckeln , helt enkelt beräkna meddelandenas chiffertexter och jämföra dem med den returnerade chiffertexten och framgångsrikt avgöra avsändarens val.

Exempel på semantiskt säkra algoritmer är Goldwasser-Micali-kryptosystemet , ElGamal-schemat och Peye-kryptosystemet . Dessa scheman anses vara bevisligen säkra , eftersom beviset för semantisk säkerhet i varje fall kan reduceras till ett svårlöst matematiskt problem. Semantiskt ömtåliga algoritmer som RSA kan göras semantiskt säkra med utfyllnadsscheman (t.ex. OAEP ).

Anteckningar

  1. ↑ 1 2 S. Goldwasser och S. Micali , Probabilistisk kryptering och hur man spelar mental poker genom att hålla all delinformation hemlig Arkiverad 31 mars 2020 på Wayback Machine , Annual ACM Symposium on Theory of Computing, 1982.
  2. ↑ Shannon, Claude. Communication Theory of Secrecy Systems  // Bell System Technical  Journal : journal. - 1949. - Vol. 28 , nr. 4 . - P. 656-715 . - doi : 10.1002/j.1538-7305.1949.tb00928.x .
  3. ↑ Goldreich, Oded. Fundamenten för kryptografi: Volym 2, grundläggande applikationer. Vol. 2. Cambridge University Press, 2004.
  4. ↑ S. Goldwasser och S. Micali , Probabilistisk kryptering . Journal of Computer and System Sciences, 28:270-299, 1984.
  5. ↑ Katz, Jonathan; Lindell, Yehuda. Introduktion till modern kryptografi : principer och protokoll  . — Chapman och Hall/CRC, 2007. Arkiverad 8 mars 2017 på Wayback Machine