TY - GEN
T1 - Non-malleability against polynomial tampering
AU - Ball, Marshall
AU - Chattopadhyay, Eshan
AU - Liao, Jyun Jie
AU - Malkin, Tal
AU - Tan, Li Yang
N1 - Funding Information:
Eshan Chattopadhyay and Jyun-Jie Liao are supported by NSF grant CCF-1849899. Li-Yang Tan is supported by NSF grant CCF-1921795.
Funding Information:
Acknowledgements. Marshall Ball is supported by an IBM Research PhD Fellowship. Tal Malkin and Marshall Ball: This work is based upon work supported in part by the Office of the Director of National Intelligence (ODNI), Intelligence Advanced Research Projects Activity (IARPA) via Contract No. 2019-1902070006. The views and conclusions contained herein are those of the authors and should not be interpreted as necessarily representing the official policies, either express or implied, of ODNI, IARPA, or the U.S. Government. The U.S. Government is authorized to reproduce and distribute reprints for governmental purposes notwithstanding any copyright annotation therein.
Publisher Copyright:
© International Association for Cryptologic Research 2020.
PY - 2020
Y1 - 2020
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85089716362&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85089716362&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-56877-1_4
DO - 10.1007/978-3-030-56877-1_4
M3 - Conference contribution
AN - SCOPUS:85089716362
SN - 9783030568764
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 97
EP - 126
BT - Advances in Cryptology - CRYPTO 2020 - 40th Annual International Cryptology Conference, Proceedings
A2 - Micciancio, Daniele
A2 - Ristenpart, Thomas
PB - Springer
T2 - 40th Annual International Cryptology Conference, CRYPTO 2020
Y2 - 17 August 2020 through 21 August 2020
ER -