A Memory-Tight Reduction for the Twin Hashed ElGamal

Abstract

I denne oppgaven ser vi på minnetetthet som en betingelse for sikkerhet i reduksjonsbaserte sikkerhetsbeviser. Minneeffektivitet er en viktig kompleksitetsparameter for black-box-reduksjoner når det aktuelle kryptografiske primitivet er minnesensitivt. Bhattacharyya har nylig introdusert en teknikk for å simulere tilfeldige orakler i sikkerhetsbeviset til Cramer-Shoup-versjonen av Hashed ElGamal-chifferet i IND-CCA-sikkerhetsspillet. I oppgaven bruker vi denne teknikken på Twin Hashed ElGamal-chifferet og oppnår et minnetett reduksjonsbevis med sikkerhet tilsvarende CDH-problemet i den tilfeldige orakelmodellen. Videre forsøker vi også å generalisere teknikken for alle KEM basert på avtrykksikre systemer, men klarer ikke å gjøre dette for ElGamal tilfellet. Vi klarer likevel å vise at den er minnetett.

Memory efficiency has been proven to be an important complexity parameter for black-box reductions when the cryptographic primitive in question is memory sensitive. New techniques for achieving memory-tight implementations have recently been introduced, most notably the injectively-map then prf technique of Bhattacharyya. This technique is used for simulating random oracles in the security proof of the Cramer-Shoup version of the Hashed ElGamal scheme in the IND-CCA security game. In this thesis we take this technique and apply it to the Twin Hashed ElGamal scheme achieving a memory-tight proof with security equivalent to the CDH problem in the random oracle model with only a small efficiency penalty. Furthermore we also attempt to generalize the technique for any Key Encapsulation Mechanisms based on Hash Proof Systems, but are unable to do this for the ElGamal case. We do however in our attempt show that this scheme implemented with the ElGamal HPS is memory-tight, albeit much less efficient than the Cramer-Shoup equivalent.