Betongsäkerhet

Inom kryptografi är konkret säkerhet eller exakt säkerhet ett praxisorienterat tillvägagångssätt som syftar till att ge mer exakta uppskattningar av beräkningskomplexiteten för kontradiktoriska uppgifter än vad polynomekvivalens skulle tillåta . ^{[ citat behövs ]} Det kvantifierar säkerheten för ett kryptosystem genom att begränsa sannolikheten för framgång för en motståndare som kör under en bestämd tid. ^{[ bättre källa behövs ]} Säkerhetsbevis med exakta analyser kallas konkreta . ^{[ bättre källa behövs ]}

Traditionellt är bevisbar säkerhet asymptotisk : den klassificerar hårdheten hos beräkningsproblem med hjälp av polynom-tidsreducerbarhet. Säkra scheman definieras som sådana där fördelen med en beräkningsbunden motståndare är försumbar . Även om en sådan teoretisk garanti är viktig, behöver man i praktiken veta exakt hur effektiv en reduktion är på grund av behovet av att instansiera säkerhetsparametern - det räcker inte att veta att "tillräckligt stora" säkerhetsparametrar räcker. En ineffektiv minskning resulterar antingen i att motståndarens framgångssannolikhet eller att systemets resursbehov är större än önskat. ^{[ citat behövs ]}

Konkret säkerhet parametriserar alla resurser som är tillgängliga för motståndaren, såsom körtid och minne, och andra resurser som är specifika för systemet i fråga, såsom antalet klartexter det kan få eller antalet frågor den kan göra till alla tillgängliga orakel . Då är motståndarens fördel övre gräns som en funktion av dessa resurser och av problemets storlek. Det är ofta möjligt att ge en nedre gräns (dvs. en kontradiktorisk strategi) som matchar den övre gränsen, därav namnet exakt säkerhet. ^{[ citat behövs ]}

Exempel

Konkreta säkerhetsuppskattningar har tillämpats på kryptografiska algoritmer:

1996 föreslogs system för digitala signaturer baserade på RSA- och Rabin -kryptosystemen, vilka visade sig vara ungefär lika svåra att bryta som de ursprungliga kryptosystemen.
År 1997 visade sig vissa föreställningar om konkret säkerhet ( vänster- eller högeromöjlighet , verklig-eller-slumpmässig omöjlighet , hitta-sen-gissa säkerhet och semantisk säkerhet ) för symmetriska krypteringsalgoritmer vara ungefär likvärdiga i olika blockchifferfunktioner. såsom CBC, CTR och XOR (en tillståndslös variant av CBC). ^{[ förtydligande behövs ]}
Under 2017 visade en avhandling att gitterpunktsuppräkning och gitterblockreduktionsalgoritmer kunde användas för att attackera gitterbaserad kryptografi .
demonstrerades attacker av typen "gissa-och-bestäm" och "gissa-och-avkoda" [ ^{förtydligande behövs ] mot en föreslagen parametervärden} pseudoslumpgenerator i NC0 , där instanser med som tidigare påståtts ha 128-bitars säkerhet löstes i ungefär $2^{78}$ operationer. ^{[ bättre källa behövs ]}

kan ett mjukvaruverktyg som heter "Foundational Cryptography Framework", som är inbäddat i Coq , formellt verifiera bevis på konkret säkerhet. Till exempel kan den verifiera den konkreta säkerheten för ElGamal-kryptering .

externa länkar