Near Optimal Non malleable Codes and Leakage Resilient Secret Sharing Schemes

Abstract

A well-studied class of attacks on cryptosystems called quotside-channel attacksquot, stems from the additional access that an adversary can get due to the susceptibility of the hardware on which the cryptosystem (e.g., digital signatures, encryption schemes) is implemented. Particularly, such attacks allow the adversary to get some form of side-channel information about the secret, in addition to the actual allowed input-output access to the device on which the cryptosystem is being implemented. Two such classes of side-channel attacks that have received tremendous attention in the literature are quotleakage attacksquot, which give the adversary some extra bits of information about the secret, and quottampering attacksquot, which allow the adversary to tamper with the device storing the secret and observe additional input-output behavior on the tampered secret. It is extremely difficult to create hardware that is immune to such side-channel attacks, and hence, a lot of recent research focuses on building algorithmic defenses against such attacks. Two such important well-studied primitives are: quotnon-malleable codesquot, which help against tampering attacks, and quotleakage resilient secret sharing schemesquot, which help against leakage attacks. In this thesis, we study these two fundamental objects and strive to build them with quotoptimalquot parameters. Dziembowski, Pietrzak, and Wichs introduced non-malleable codes (NMCs) at ITCS 2010, with the intent to secure against tampering attacks. NMCs give a guarantee that adversarial tampering of the encoding of the secret will lead to a tampered secret, which is either same as the original or completely independent of it, thus giving no additional information to the adversary. Secret sharing schemes, introduced by Shamir and Blakely in 1979, help a party, called a dealer, to share his secret message amongst $N$ parties in such a way that any $t$ of these parties can combine their shares to recover the secret, but the secret remains hidden from an adversary corrupting $lt t$ parties to get their c...