NDLI: Non-malleable codes from additive combinatorics

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

Fingerprinting codes and the price of approximate differential privacy

Analyze gauss: optimal bounds for privacy-preserving principal component analysis

Private matchings and allocations

Rounding sum-of-squares relaxations

Constant factor approximation for balanced cut in the PIE model

Entropy, optimization and counting

Polynomial bounds for the grid-minor theorem

An excluded half-integral grid theorem for digraphs and the directed disjoint paths problem

Cops, robbers, and threatening skeletons: padded decomposition for minor-free graphs

Deciding first-order properties of nowhere dense graphs

Pseudorandom generators with optimal seed length for non-boolean poly-size circuits

On derandomizing algorithms that err extremely rarely

Super-polynomial lower bounds for depth-4 homogeneous arithmetic formulas

Lower bounds for depth 4 formulas computing iterated matrix multiplication

The limits of depth reduction for arithmetic formulas: it's all about the top fan-in

A super-polynomial lower bound for regular arithmetic formulas

A characterization of locally testable affine-invariant properties via decomposition theorems

$L_{p}-testing$

Turnstile streaming algorithms might as well be linear sketches

Linear time construction of compressed text indices in compact space

New algorithms and lower bounds for circuits with linear threshold gates

Formulas vs. circuits for small distance connectivity

Toward better formula lower bounds: an information complexity approach to the KRW composition conjecture

Breaking the minsky-papert barrier for constant-depth circuits

Economic efficiency requires interaction

The sample complexity of revenue maximization

Optimal competitive auctions

The matching polytope has exponential extension complexity

Homological product codes

Exponential improvement in precision for simulating sparse Hamiltonians

A quantum algorithm for computing the unit group of an arbitrary degree number field

Primal beats dual on online packing LPs in the random-order model

Competitive algorithms from competitive equilibria: non-clairvoyant scheduling under polyhedral constraints

Minimum bisection is fixed parameter tractable

An efficient parallel solver for SDD linear systems

Solving SDD linear systems in nearly $mlog^{1/2}n$ time

Optimal CUR matrix decompositions

From hierarchical partitions to hierarchical covers: optimal fault-tolerant spanners for doubling metrics

Shortest paths on polyhedral surfaces and terrains

Embedding and canonizing graphs of bounded genus in logspace

Testing surface area with arbitrary accuracy

Coin flipping of any constant bias implies one-way functions

An almost-optimally fair three-party coin-flipping protocol

Robust protocols for securely expanding randomness and distributing keys using untrusted quantum devices

Infinite randomness expansion with a constant number of devices

The average sensitivity of an intersection of half spaces

From average case complexity to improper learning complexity

The power of localization for efficiently learning linear separators with noise

Bandits with switching costs: $T^{2/3}$ regret

Online local learning via semidefinite programming

How to use indistinguishability obfuscation: deniable encryption, and more

How to delegate computations: the power of no-signaling proofs

Circuits resilient to additive attacks with applications to secure computation

On the existence of extractable one-way functions

Black-box non-black-box zero knowledge

Dichotomies in equilibrium computation, and complementary pivot algorithms for a new class of non-separable utility functions

Query complexity of approximate nash equilibria

Constant rank bimatrix games are PPAD-hard

Approximation algorithms for bipartite matching with metric and geometric costs

Distributed approximation algorithms for weighted shortest paths

Parallel algorithms for geometric graph problems

Fourier PCA and robust tensor decomposition

Smoothed analysis of tensor decompositions

Efficient density estimation via piecewise polynomial approximation

Super-polylogarithmic hypergraph coloring hardness via low-degree long codes

Analytical approach to parallel repetition

A characterization of strong approximation resistance

A strongly polynomial algorithm for generalized flow maximization

Approximate distance oracles with constant query time

Faster all-pairs shortest paths via circuit complexity

Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs

Zig-zag sort: a simple deterministic data-oblivious sorting algorithm running in O(n log n) time

Community detection thresholds and the weak Ramanujan property

Distributed computability in Byzantine asynchronous systems

Are lock-free concurrent algorithms practically wait-free?

Multiway cut, pairwise realizable distributions, and descending thresholds

Cluster before you hallucinate: approximating node-capacitated network design and energy efficient routing

Approximation algorithms for regret-bounded vehicle routing and applications to distance-constrained vehicle routing

Improved approximation algorithms for degree-bounded network design problems with node connectivity requirements

Every list-decodable code for high noise has abundant near-optimal rate puncturings

Non-malleable codes from additive combinatorics

Breaking the quadratic barrier for 3-LCC's over the reals

Optimal error rates for interactive coding I: adaptivity and other settings

The asymptotic k-SAT threshold

Satisfiability threshold for random regular NAE-SAT

Inapproximability for antiferromagnetic spin systems in the tree non-uniqueness region

Efficient deterministic approximate counting for low-degree polynomial threshold functions

Communication is bounded by root of rank

Communication lower bounds via critical block sensitivity

Computing with a full memory: catalytic space

Hitting sets for multilinear read-once algebraic branching programs, in any order

Non-malleable codes from additive combinatorics

Content Provider	ACM Digital Library
Author	Dodis, Yevgeniy Lovett, Shachar Aggarwal, Divesh
Abstract	Non-malleable codes provide a useful and meaningful security guarantee in situations where traditional errorcorrection (and even error-detection) is impossible; for example, when the attacker can completely overwrite the encoded message. Informally, a code is non-malleable if the message contained in a modified codeword is either the original message, or a completely unrelated value. Although such codes do not exist if the family of "tampering functions" F is completely unrestricted, they are known to exist for many broad tampering families F. One such natural family is the family of tampering functions in the so called split-state model. Here the message m is encoded into two shares L and R, and the attacker is allowed to arbitrarily tamper with L and R individually. The split-state tampering arises in many realistic applications, such as the design of non-malleable secret sharing schemes, motivating the question of designing efficient non-malleable codes in this model. Prior to this work, non-malleable codes in the splitstate model received considerable attention in the literature, but were constructed either (1) in the random oracle model [16], or (2) relied on advanced cryptographic assumptions (such as non-interactive zero-knowledge proofs and leakage-resilient encryption) [26], or (3) could only encode 1-bit messages [14]. As our main result, we build the first efficient, multi-bit, information-theoretically-secure non-malleable code in the split-state model. The heart of our construction uses the following new property of the inner-product function 〈L;R〉 over the vector space $F^{n}_{p}$ (for a prime p and large enough dimension n): if L and R are uniformly random over $F^{n}_{p},$ and f, g: $F^{n}_{p}$ → $F^{n}_{p}$ are two arbitrary functions on L and R, then the joint distribution (〈L;R〉, 〈f(L), g(R)〉) is "close" to the convex combination of "affine distributions" {(U, aU + b) --- a, b ε $F_{p}\},$ where U is uniformly random in $F_{p}.$ In turn, the proof of this surprising property of the inner product function critically relies on some results from additive combinatorics, including the so called Quasi-polynomial Freiman-Ruzsa Theorem which was recently established by Sanders [29] as a step towards resolving the Polynomial Freiman-Ruzsa conjecture [21].
Starting Page	774
Ending Page	783
Page Count	10
File Format	PDF MP4
ISBN	9781450327107
DOI	10.1145/2591796.2591804
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2014-05-31
Publisher Place	New York
Access Restriction	Subscribed
Content Type	Audio Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

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