TY - GEN

T1 - Limits to non-malleability

AU - Ball, Marshall

AU - Dachman-Soled, Dana

AU - Kulkarni, Mukul

AU - Malkin, Tal

N1 - Funding Information:
Funding 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. Marshall Ball: M. Ball is supported by an IBM Research PhD Fellowship. This research 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. Dana Dachman-Soled: This work is supported in part by NSF grants #CNS-1933033, #CNS-1840893,
Funding Information:
#CNS-1453045 (CAREER), by a research partnership award from Cisco and by financial assistance award 70NANB15H328 from the U.S. Department of Commerce, National Institute of Standards and Technology. Tal Malkin: This research 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.
Publisher Copyright:
© Marshall Ball, Dana Dachman-Soled, Mukul Kulkarni, and Tal Malkin.

PY - 2020/1

Y1 - 2020/1

N2 - There have been many successes in constructing explicit non-malleable codes for various classes of tampering functions in recent years, and strong existential results are also known. In this work we ask the following question: When can we rule out the existence of a non-malleable code for a tampering class F? First, we start with some classes where positive results are well-known, and show that when these classes are extended in a natural way, non-malleable codes are no longer possible. Specifically, we show that no non-malleable codes exist for any of the following tampering classes: Functions that change d/2 symbols, where d is the distance of the code; Functions where each input symbol affects only a single output symbol; Functions where each of the n output bits is a function of n − log n input bits. Furthermore, we rule out constructions of non-malleable codes for certain classes F via reductions to the assumption that a distributional problem is hard for F, that make black-box use of the tampering functions in the proof. In particular, this yields concrete obstacles for the construction of efficient codes for NC, even assuming average-case variants of P 6⊆ NC.

AB - There have been many successes in constructing explicit non-malleable codes for various classes of tampering functions in recent years, and strong existential results are also known. In this work we ask the following question: When can we rule out the existence of a non-malleable code for a tampering class F? First, we start with some classes where positive results are well-known, and show that when these classes are extended in a natural way, non-malleable codes are no longer possible. Specifically, we show that no non-malleable codes exist for any of the following tampering classes: Functions that change d/2 symbols, where d is the distance of the code; Functions where each input symbol affects only a single output symbol; Functions where each of the n output bits is a function of n − log n input bits. Furthermore, we rule out constructions of non-malleable codes for certain classes F via reductions to the assumption that a distributional problem is hard for F, that make black-box use of the tampering functions in the proof. In particular, this yields concrete obstacles for the construction of efficient codes for NC, even assuming average-case variants of P 6⊆ NC.

KW - Average-case hardness

KW - Black-box impossibility

KW - Non-malleable codes

KW - Tamper-resilient cryptogtaphy

UR - http://www.scopus.com/inward/record.url?scp=85078052827&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85078052827&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.ITCS.2020.80

DO - 10.4230/LIPIcs.ITCS.2020.80

M3 - Conference contribution

AN - SCOPUS:85078052827

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 11th Innovations in Theoretical Computer Science Conference, ITCS 2020

A2 - Vidick, Thomas

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 11th Innovations in Theoretical Computer Science Conference, ITCS 2020

Y2 - 12 January 2020 through 14 January 2020

ER -