Cryptology ePrint Archive: Report 2020/147

Non-Malleability against Polynomial Tampering

Marshall Ball and Eshan Chattopadhyay and Jyun-Jie Liao and Tal Malkin and Li-Yang Tan

Abstract: We present the first explicit construction of a non-malleable code that can handle tampering functions that are bounded-degree polynomials.

Prior to our work, this was only known for degree-1 polynomials (affine tampering functions), due to Chattopadhyay and Li (STOC 2017). As a direct corollary, we obtain an explicit non-malleable code that is secure against tampering by bounded-size arithmetic circuits.

We show applications of our non-malleable code in constructing non-malleable secret sharing schemes that are robust against bounded-degree polynomial tampering. In fact our result is stronger: we can handle adversaries that can adaptively choose the polynomial tampering function based on initial leakage of a bounded number of shares.

Our results are derived from explicit constructions of seedless non-malleable extractors that can handle bounded-degree polynomial tampering functions. Prior to our work, no such result was known even for degree-2 (quadratic) polynomials.

Category / Keywords: foundations / non-malleable codes, non-malleable extractors, secret-sharing schemes, explicit constructions

Date: received 10 Feb 2020

Contact author: eshan c at gmail com,marshall@cs columbia edu,jl3825@cornell edu,tal@cs columbia edu,liyang@cs stanford edu

Available format(s): PDF | BibTeX Citation

Version: 20200210:194410 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]