Publication:514470

DOI10.1007/978-3-642-54242-8_19zbMath1370.94497arXiv1309.1151OpenAlexW2106066551MaRDI QIDQ514470

Venkatesan Guruswami, Mahdi Cheraghchi

Publication date: 2 March 2017

Published in: Journal of Cryptology, Theory of Cryptography (Search for Journal in Brave)

Abstract: Non-malleable coding, introduced by Dziembowski, Pietrzak and Wichs (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. Dziembowski et al. show existence of non-malleable codes for any class of tampering functions of bounded size. We consider constructions of coding schemes against two well-studied classes of tampering functions: bit-wise tampering functions (where the adversary tampers each bit of the encoding independently) and split-state adversaries (where two independent adversaries arbitrarily tamper each half of the encoded sequence). 1. For bit-tampering, we obtain explicit and efficiently encodable and decodable codes of length $n$ achieving rate $1-o(1)$ and error (security) $exp(- ilde{Omega}(n^{1/7}))$. We improve the error to $exp(- ilde{Omega}(n))$ at the cost of making the construction Monte Carlo with success probability $1-exp(-Omega(n))$. Previously, the best known construction of bit-tampering codes was the Monte Carlo construction of Dziembowski et al. (ICS 2010) achieving rate ~.1887. 2. We initiate the study of seedless non-malleable extractors as a variation 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 existence of such extractors, which implies that codes obtained from our reduction can achieve rates arbitrarily close to 1/5 and exponentially small error. 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.

Full work available at URL: https://arxiv.org/abs/1309.1151

zbMATH Keywords

cryptographyinformation theoryerror detectioncoding theoryrandomness extractorstamper-resilient cryptographytamper-resilient storage

Mathematics Subject Classification ID

Cryptography (94A60) Decoding (94B35)

Cites Work

• Unnamed Item
• Non-malleable coding against bit-wise and split-state tampering
• Multilinear formulas, maximal-partition discrepancy and mixed-sources extractors
• 2-source dispersers for \(n^{o(1)}\) entropy, and Ramsey graphs beating the Frankl-Wilson construction
• Derandomized constructions of \(k\)-wise (almost) independent permutations
• Non-malleable Codes from Two-Source Extractors
• Pseudorandomness
• Non-malleable Reductions and Applications
• Capacity of non-malleable codes
• A 2-Source Almost-Extractor for Linear Entropy
• Extractors with weak random seeds
• Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity
• Non-Malleable Codes
• Non-malleable extractors and symmetric key cryptography from weak secrets
• Non-malleable codes from additive combinatorics
• MORE ON THE SUM-PRODUCT PHENOMENON IN PRIME FIELDS AND ITS APPLICATIONS
• Non-malleable extractors and codes, with their many tampered extensions
• Secure Computation from Random Error Correcting Codes
• Detection of Algebraic Manipulation with Applications to Robust Secret Sharing and Fuzzy Extractors
• Class of constructive asymptotically good algebraic codes

Related Items (29)

Improved, black-box, non-malleable encryption from semantic security ⋮ The Chaining Lemma and Its Application ⋮ Algebraic restriction codes and their applications ⋮ Strong continuous non-malleable encoding schemes with tamper-detection ⋮ Extractors: low entropy requirements colliding with non-malleability ⋮ Non-malleable encryption: simpler, shorter, stronger ⋮ Continuously non-malleable codes in the split-state model ⋮ Nonmalleable Extractors and Codes, with Their Many Tampered Extensions ⋮ Codes for Detection of Limited View Algebraic Tampering ⋮ Affine-evasive sets modulo a prime ⋮ Non-Malleable Codes from Additive Combinatorics ⋮ Modeling Random Oracles Under Unpredictable Queries ⋮ A black-box construction of non-malleable encryption from semantically secure encryption ⋮ Bounded tamper resilience: how to go beyond the algebraic barrier ⋮ Non-malleable coding against bit-wise and split-state tampering ⋮ Tight Upper and Lower Bounds for Leakage-Resilient, Locally Decodable and Updatable Non-malleable Codes ⋮ Robustly self-ordered graphs: constructions and applications to property testing ⋮ Tight upper and lower bounds for leakage-resilient, locally decodable and updatable non-malleable codes ⋮ Continuously non-malleable codes with split-state refresh ⋮ Unnamed Item ⋮ Four-state non-malleable codes with explicit constant rate ⋮ Non-Malleable Encryption: Simpler, Shorter, Stronger ⋮ Information-Theoretic Local Non-malleable Codes and Their Applications ⋮ Optimal Computational Split-state Non-malleable Codes ⋮ Non-malleable fuzzy extractors ⋮ Pauli manipulation detection codes and applications to quantum communication over adversarial channels ⋮ Non-malleable codes with optimal rate for poly-size circuits ⋮ Complexity theory. Abstracts from the workshop held June 2--7, 2024 ⋮ Locally decodable and updatable non-malleable codes and their applications

This page was built for publication: Non-malleable coding against bit-wise and split-state tampering