NDLI: Non-malleable Coding Against Bit-Wise and Split-State Tampering

Please wait, while we are loading the content...

Non-malleable Coding Against Bit-Wise and Split-State Tampering

Content Provider	Springer Nature Link
Author	Cheraghchi, Mahdi Guruswami, Venkatesan
Copyright Year	2015
Abstract	Non-malleable coding, introduced by Dziembowski et al. (ICS 2010), aims for protecting the integrity of information against tampering attacks in situations where error detection is impossible. Intuitively, information encoded by a non-malleable code either decodes to the original message or, in presence of any tampering, to an unrelated message. Non-malleable coding is possible against any class of adversaries of bounded size. In particular, Dziembowski et al. show that such codes exist and may achieve positive rates for any class of tampering functions of size at most $$2^{2^{\alpha n}}$$ , for any constant $$\alpha \in [0, 1)$$ . However, this result is existential and has thus attracted a great deal of subsequent research on explicit constructions of non-malleable codes against natural classes of adversaries. In this work, we consider constructions of coding schemes against two well-studied classes of tampering functions; namely, bit-wise tampering functions (where the adversary tampers each bit of the encoding independently) and the much more general class of split-state adversaries (where two independent adversaries arbitrarily tamper each half of the encoded sequence). We obtain the following results for these models. (1) For bit-tampering adversaries, we obtain explicit and efficiently encodable and decodable non-malleable codes of length n achieving rate $$1-o(1)$$ and error (also known as “exact security”) $$\exp (-\tilde{\varOmega }(n^{1/7}))$$ . Alternatively, it is possible to improve the error to $$\exp (-\tilde{\varOmega }(n))$$ at the cost of making the construction Monte Carlo with success probability $$1-\exp (-\varOmega (n))$$ (while still allowing a compact description of the code). Previously, the best known construction of bit-tampering coding schemes was due to Dziembowski et al. (ICS 2010), which is a Monte Carlo construction achieving rate close to .1887. (2) We initiate the study of seedless non-malleable extractors as a natural variation of the notion of non-malleable extractors introduced by Dodis and Wichs (STOC 2009). We show that construction of non-malleable codes for the split-state model reduces to construction of non-malleable two-source extractors. We prove a general result on existence of seedless non-malleable extractors, which implies that codes obtained from our reduction can achieve rates arbitrarily close to 1 / 5 and exponentially small error. In a separate recent work, the authors show that the optimal rate in this model is 1 / 2. Currently, the best known explicit construction of split-state coding schemes is due to Aggarwal, Dodis and Lovett (ECCC TR13-081) which only achieves vanishing (polynomially small) rate.
Starting Page	191
Ending Page	241
Page Count	51
File Format	PDF
ISSN	09332790
Journal	Journal of Cryptology
Volume Number	30
Issue Number	1
e-ISSN	14321378
Language	English
Publisher	Springer US
Publisher Date	2015-10-06
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Information theory Tamper-resilient cryptography Coding theory Error detection Randomness extractors Coding and Information Theory Computational Mathematics and Numerical Analysis Combinatorics Probability Theory and Stochastic Processes Communications Engineering, Networks
Content Type	Text
Resource Type	Article
Subject	Applied Mathematics Computer Science Applications Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Non-malleable coding against bit-wise and split-state tampering.

Non-Malleable Coding Against Bit-wise and Split-State Tampering

Non-Malleable Coding Against Bit-wise and Split-State Tampering

Non-malleable Codes against Constant Split-State Tampering

Capacity of non-malleable codes

Fully Leakage-Resilient Signatures

Leakage-Resilient Cryptography from Minimal Assumptions

Non-malleable Reductions and Applications

Non-interactive Timestamping in the Bounded-Storage Model

Non-malleable Coding Against Bit-Wise and Split-State Tampering

Similar Documents

Non-malleable coding against bit-wise and split-state tampering.

Non-Malleable Coding Against Bit-wise and Split-State Tampering

Non-Malleable Coding Against Bit-wise and Split-State Tampering

Non-malleable Codes against Constant Split-State Tampering

Capacity of non-malleable codes

Fully Leakage-Resilient Signatures

Leakage-Resilient Cryptography from Minimal Assumptions

Non-malleable Reductions and Applications

Non-interactive Timestamping in the Bounded-Storage Model

Non-malleable Coding Against Bit-Wise and Split-State Tampering