Near Optimal Non-malleable Codes and Leakage Resilient Secret Sharing Schemes

Abstract

A well-studied class of attacks on cryptosystems called "side-channel attacks", 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 "leakage attacks", which give the adversary some extra bits of information about the secret, and "tampering attacks", 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: "non-malleable codes", which help against tampering attacks, and "leakage resilient secret sharing schemes", which help against leakage attacks. In this thesis, we study these two fundamental objects and strive to build them with "optimal" 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 $< t$ parties to get their complete shares. To secure against leakage attacks, which allow the adversary to get some bounded bits of leakage from the shares of the remaining parties, in addition to the complete shares, Dziembowski and Pietrzak introduced the notion of leakage resilient secret sharing schemes (LRSS), at FOCS 2007.

Whether we consider using NMCs and storing the non-malleable encoding of the message on a tamper-prone system, or we use an LRSS to generate shares of a secret to be stored on a leakage-prone system, it is important to build schemes that output codewords/shares that are of optimal length and do not introduce too much redundancy into the codewords/shares. This is, in particular, captured by the rate of the schemes, which is the ratio of the message length to the codeword length/largest share length. The research goal of this thesis is to improve the state of art on rates of these schemes and get near-optimal/optimal rates. We elaborate on the results below.

1) In the first part of our thesis, we look at NMCs in a natural and well-studied model of tampering called the "2-split-state" model, where the codeword consists of two independently tamperable states. In this model, Cheraghchi and Guruswami (ITCS 2014) showed that one cannot build NMCs with a rate better than $1/2$. Since its inception, this area has witnessed huge strides leading to the construction of a constant-rate NMC in the $2$-split state model due to Aggarwal and Obremski at FOCS 2020. However, the rate of this construction -- roughly $1/1,500,000$ -- is nowhere close to the best achievable rate of $1/2$! In this thesis, we dramatically improve this status quo by building an NMC in the $2$-split-state model with a near-optimal rate of $1/3$. As a stepping stone, we also show how one can get a rate of $1/2$, if one relaxes the non-malleability requirement from NMCs to only uniform random messages.

2) In the second part of our thesis, we study LRSS schemes, where on the one hand, a huge line of prior works focus on improving the leakage model but suffer from poor rate-- in the strongest leakage model, called "adaptive and joint", the best-known rate of $O(1/N)$ (where $N$ is the number of parties) is achieved by the LRSS scheme of Chattopadhyay, Goodman, Goyal, Kumar, Li, Meka, Zuckerman from FOCS 2020 -- on the other hand, a line of works focus on improving the rate of the LRSS, which come at the expense of the leakage model-- in the weakest leakage model, called "non-adaptive and independent", the work of Srinivasan and Vasudevan from CRYPTO 2019 achieves a rate of $1/3$. In this thesis, we strive to bridge this gap, and build an LRSS scheme in the strong "adaptive and joint" leakage model, while still getting a much better rate of $O(1)$. Further, we also improve the "non-adaptive and independent" LRSS scheme of Srinivasan and Vasudevan and show how to get an optimal rate of $1$.