Non-Malleable Code and Polynomial Tampering in Cryptography
Explore non-malleability against polynomial tampering and the concept of non-malleable code [DPW10]. Understand the importance of tampering functions, small-depth circuits, and secret sharing in enhancing cryptographic security.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Non-Malleability against Polynomial Tampering Marshall Ball1, Eshan Chattopadhyay2, Jyun-Jie Liao2, Tal Malkin1, Li-Yang Tan3 1Columbia University 2Cornell University 3Stanford University
Non-malleable code [DPW10] ? ? ? ? Enc Dec ? = ?or ? is unrelated to ? Goal: Either destroyed unchanged
Non-malleable code [DPW10] ? ? ? ? Enc Dec ? Correctness: Dec Enc ? Non-malleability: ? , ??s.t. ? ???(?), where ??is a distribution over {id, const} = ? Impossible for arbitrary ? (e.g. ? ? = ???(??? ? + 1))unchanged destroyed
Tampering functions Split-state model [DPW10, LL12, DKO13, ADL14, CG14, CZ14, ADKO15, Agg15, CGL16, KOS17, Li17, GMW18, KOS18, Li19, AO20...] Global tampering functions Permutations and bit flipping [AGMPP15] Local functions [BDKM16, GMW19] Affine functions over ?2[CL17] Small-depth circuits [CL17, BDSGMT18] Small-depth decision trees [BGW19] Polynomials over ?? [This work]
Polynomial tampering ?, where q is a prime Codeword: x = ?1,?2, ,?? ?? ?????,?,? Degree-d polynomial on n variables over ?? ?,?,? (?1,?2, ,?? | ?? ?????,?,?} ? = ?1,?2, ,?? ?1? ,?2(?), ,??(?) ?,?,?
Our result For every ?,?,? and sufficiently large prime ? > ????(?,?,2?,1/?), there exist ???: 0,1? ?? s.t. (???,???) is a non-malleable code against ?,?,?. ?,???:?? ? 0,1? ? 0,1? ? 0,1? Dec Enc ?1? ,?2(?), ,??(?) ? = ?1,?2, ,?? ?,?,?
Arithmetic circuits ?,?,? (?1,?2, ,??}, each ?? is a size-? arithmetic circuit on ? variables over ?? (x1x2+ x3)(x3+ 2x4) + + ?,?,? ?,?,2? ?1 ?2 ?3 ?4 2
Corollary For every ?,?,? and sufficiently large prime ? > ????(?,2?,2?,1/?), there exist ???: 0,1? ?? s.t. (???,???) is a non-malleable code against ?,?,?. ?,???:?? ? 0,1? ? 0,1? ? 0,1? Dec Enc ?1? ,?2(?), ,??(?) ? = ?1,?2, ,?? ?,?,?
Secret sharing [Shamir79,Blakley79] ? 1 ? 2 Rec ? ? Share ? ? t-out-of-n secret sharing Correctness: ? can be reconstructed with any ? shares Secrecy: any ? 1 shares reveal no information about ?
Non-malleable secret sharing [GK18] ? 1 ? 1 ? 2 ? 2 ? Rec ? Share ? ? ? ? t-out-of-n secret sharing Correctness: ? can be reconstructed with any ? shares Secrecy: any ? 1 shares reveal no information about ? Non-malleability: when reconstructed from ? shares, ? is either unchanged or destroyed
Prior work Individual tampering [GK18a, GK18b, BS19, SV19, ADNOPRS19] ? 1 ?1(? 1) ? 2 ?2(? 2) ? ? ??(? ?)
Prior work Individual tampering [GK18a, GK18b, BS19, SV19, ADNOPRS19] Joint tampering [GK18a, GK18b] ? 1 ? 1 ? 2 ? 2 ? ? ? ?
Prior work Individual tampering [GK18a, GK18b, BS19, SV19, ADNOPRS19] Joint tampering [GK18a, GK18b] Global tampering functions Affine tampering [LCGSNW20] Joint tampering + affine function [CL19] Polynomial over ?? [This work] ? 1 ? 1 ? 2 ? 2 ? ? ? ? ?
Our result For every ?,?,?,? and sufficiently large prime ? > ????(?,?,2?,1/?), there exist t-out-of-n non-malleable secret sharing for m-bit secret against ?,?,?. Secure against adaptive choice of tampering function ? 1 ? 1 ? 2 ? 2 ? ? Rec Share f ?,?,? ? ? ? ? (t-1) shares
Corollary For every ?,?,?,? and sufficiently large prime ? > ????(?,2?,2?,1/?), there exist t-out-of-n non-malleable secret sharing for m-bit secret against ?,?,?. Secure against adaptive choice of tampering function ? 1 ? 1 ? 2 ? 2 ? ? Rec Share f ?,?,? ? ? ? ? (t-1) shares
Roadmap Seedless non-malleable extractor [CG14] [LCGSNW20] efficient inverter Non-malleable secret sharing Non-malleable code
Seedless non-malleable extractor [CG14] ?????: 0,1?is a non-malleable extractor against for source ? if for every ? , there exists distribution ?? {??,?????} s.t. unchanged destroyed ????? ? ,????? ? ? (??,??(??)) ????? for uniform distribution non-malleable code: [CG14] ??? ????? 1 ??? ????? (uniformly sample from preimage)
Our result For every ?,?,? and sufficiently large prime ? > ????(?,?,2?,1/?), there exists a seedless non-malleable extractor n????:?? for uniform distribution against ?,?,?. Moreover, n???? 1is efficiently computable. ? 0,1? ? ? ? ? ????? 1 ????? ? ?,?,?
Our result For every ?,?,? and sufficiently large prime ? = ????(?,?,2?,1/?), there exists a seedless non-malleable extractor n????:?? for skew affine source against ?,?,?. Moreover, n???? 1is efficiently computable. ? 0,1? ? ? ? ? ????? 1 ????? ? ?,?,?
Skew affine source ? is a skew affine source if ? = (?1,?2, ,??) ?? ? is uniform over an affine subspace (X is an affine source) For every ? [?], ?? is not a constant Uniform source conditioned on affine leakage which doesn t reveal any ??
NM extractor construction Construction: ????? ?1,?2, ,?? ?( ?1, ,??), where is a low-degree polynomial and ? ? = ? mod 2?. First attempt: [GR08] extractor Linear tampering attack: ? ?1, ,?? = (?1?1, ,????), ? ?? => ? ? ?? ? = ?? ??= ? 1 ? where ?1,?2, ,??are distinct integers. = ? (?)
NM extractor construction Construction: ????? ?1,?2, ,?? ?( ?1, ,??), where is a low-degree polynomial and ? ? = ? mod 2?. ??+?? (??+?)) ? = (?? ??= ?? ??+?= ? 1 ??s.t. ?? => Linear attack doesn t work! ? where gcd ?,? 1 = 1 and ?1,?2, ,??,?1+ ?, ,??+ ? are distinct integers.
NM extractor construction Construction: ????? ?1,?2, ,?? ?( ?1, ,??), where is a low-degree polynomial and ? ? = ? mod 2?. ?2? 1+ ?? ?2?), ?1, ,?? = (?? ? ??= ? 4?? + 1 + ??, gcd ?,? 1 = 1
????? ? = ?( ? ), ?2? 1+ ?? ?2?) ? = (?? Proof ideas ? ? ? = ? mod 2? When is a low-degree polynomial, the only possible correlation between ?( ? ),?( ? ? ) is ? = ? ? ? + ? Proved with Weil bound [Weil48] and generalized XOR lemma [Rao07,DLWZ14] Having two terms for each ??prevents linear tampering. The choice of ?? ? [2?]prevents non-linear tampering. [DGW09] Input source being skew prevents constant tampering.
????? ? = ?( ? ), ?2? 1+ ?? ?2?) ? = (?? Efficient inverter for NMExt ? ? ? = ? mod 2? Rejection sampling adapted from [CS09] [CS09] y x z ? 1 1 ? h ????? 1 ????? Problem: need a uniform pre-image from ? => should sample ? with prob. | 1(?)| Computing | 1(?)| is expensive in our setting. (large n)
NM extractor => NM secret sharing [LCGSNW] scheme: ? 1 ? 1 ? ? ? ? 2 ? 2 ? ????? ????? 1 Dec Enc ? ? ? ? Rec Share (Enc,Dec): erasure code
NMSS against polynomial tampering X is a skew affine source conditioned on the leaked shares ? 1 ? 1 ? ? ? ? 2 ? ? 2 ????? ????? 1 Dec Enc ? ?? 0,1? ? ? ? ? ?? Rec Share (Enc,Dec): systematic MDS code
Open problems Improving the parameters (e.g. information rate and error) Non-malleability against polynomial over ?2 Non-malleability against other global tampering functions (e.g. small- width branching programs, AC circuits with parity gate, etc.) ?
