New version page

# UVA CS 588 - Security through complexity

Pages: 36
Documents in this Course

## This preview shows page 1-2-17-18-19-35-36 out of 36 pages.

View Full Document
Do you want full access? Go Premium and unlock all 36 pages.
Do you want full access? Go Premium and unlock all 36 pages.
Do you want full access? Go Premium and unlock all 36 pages.
Do you want full access? Go Premium and unlock all 36 pages.
Do you want full access? Go Premium and unlock all 36 pages.
Do you want full access? Go Premium and unlock all 36 pages.
Do you want full access? Go Premium and unlock all 36 pages.

Unformatted text preview:

Security through complexity Ana Nora SovarelProjectsTuring MachineDefinitionNondeterministic Turing MachineSlide 6More Power?Complexity ClassesReductionMore definitions …How do we prove a problem is hard?Cook’s Theorem (‘71)Subset SumSlide 14Subset Sum is in NPSlide 161. Algorithm1. Algorithm (cont.)Slide 192. Reduction ‘’3. Reduction ‘’4. PolynomialBack to cryptology Knapsack CipherDecryptionLinear Time DecryptionHow to build the keys?Slide 28Trade offsEvaluationKnapsack Cipher - SummaryShamir’s break (’82)Shamir’s break (cont.)Slide 34A little bit of historyConclusion1Security through complexityAna Nora Sovarel2ProjectsPlease fill one slot on the signup sheet.One meeting for each group.All members must agree.3Turing MachineFinite Control0 0 1 1 0 0 1 0 0 04DefinitionA Turing Machine is a 7-tuple (Q, ∑, Γ, δ, q0, qaccept, qreject) where Q, ∑, Γ are finite sets and1. Q is the set of states2. ∑ is the input alphabet3. Γ is the tape alphabet4. δ : Q X Γ  Q X Γ X {L,R} is the transition function5. q0 is the start state6. qaccept is the accept state7. qreject is the reject state, where qaccept ≠ qreject5Nondeterministic Turing MachineFinite Control0 0 1 1 0 0 1 0 0 0Finite Control0 0 1 1 0 0 1 0 00Finite Control0 0 0 1 0 0 1 0 006DefinitionA Turing Machine is a 7-tuple (Q, ∑, Γ, δ, q0, qaccept, qreject) where Q, ∑, Γ are finite sets and1. Q is the set of states2. ∑ is the input alphabet3. Γ is the tape alphabet4. δ : Q X Γ P(Q X Γ X {L,R}) is the transition function5. q0 is the start state6. qaccept is the accept state7. qreject is the reject state, where qaccept ≠ qreject7More Power?Does nondeterminism affect the power of Turing Machine?NO – more power means it recognizes more languagesBut, maybe it can do things faster …8Complexity Classes•P = decidable in polynomial time by a deterministic TM•NP = decidable in polynomial time by a nondeterministic TM9Reductionf – polynomial time transformation What we know about A and B?A is at most as hard as B ( can be easier if we find another way to solve it )B is at least as hard as A.A’s Inputf(A) BYes/NoB’s Input10More definitions …•NP-Hard = the set of problems Q such that any problem Q’ in NP is polynomial reducible to it.•NP-complete = the problems Q such that Q is in NP-Hard and Q is in NP11How do we prove a problem is hard?•Let A be a known hard problem•Find a polynomial transformation from A’s input to your problem’s input•Why it works? –If your problem is easy ( P ) then we can solve A easy ( P ).–So A is not hard. Contradiction•Need a hard problem to start with ….12Cook’s Theorem (‘71)SAT is NP-complete. ( SAT = given a boolean formula, is it satisfiable? )3SAT is NP-complete.Example: Ф(x1,x2,x3,x4)=(x1+x2+x3)(x’1+x3+x4)13Subset SumGiven a set {x1,x2,…,xn} of integers and an integer t, find {y1,y2,…,yk} a subset of {x1,x2,…,xn} such that:kiiyt114Subset SumTo prove NP-complete:1. Prove is in NP•Verifiable in polynomial time•Give a nondeterministic algorithm 2. Reduction from a known NP-complete problem to subset sum•Reduction from 3SAT to subset sum15Subset Sum is in NPsum = 0A = {x1,x2,…,xn}for each x in Ay  choice(A)sum = sum + yif ( sum = t ) then successA  A – {y}donefail16ReductionGoal: Reduce 3SAT to SUBSET-SUM.How: Let Ф be a 3 conjunctive normal formformula. Build an instance of SUBSET-SUMproblem (S, t) such that Ф is satisfiable if and only if there is a subset T of S whoseelements sum to t.Prove the reduction is polynomial.171. AlgorithmInput: Ф - 3 conjunctive normal form formulaVariables: x1, x2, …, xlClauses: c1,c2,…,ck.Output: S, t such that Ф is satisfiable iff there is T subset of Swhich sums to t.181. Algorithm (cont.)x1x2…. xlc1c2…. cky11 0 0 1 0 0z11 0 0 0 1 0y21 0 0 0 1z21 0 0 0 0…yl1 0 0 0zl1 0 0 0g11 0 0h11 0 0g21 0h21 0…gk1hk1t 1 1 … 1 3 3 … 3191. Algorithm (cont.)(yi,xj), (zi,xj) – 1 if i=j, 0 otherwise (yi,cj) – 1 if cj contains variable xi, 0 otherwise(zi,cj) – 1 if cj contains variable x’i, 0 otherwise(gi,xj), (hi,xj) – 0(gi,cj), (hi,cj) – 1 if i=j, 0 otherwiseEach row represents a decimal number.S={y1,z1,..,yl,zl,g1,h1,…,gk,hk}t is the last row in the table.202. Reduction ‘’Given a variable assignment which satisfiesФ, find T.1. If xi is true then yi is in T, else zi is in T2. Add gi and/or hi to T such all last k digits of T to be 3.213. Reduction ‘’Given T a subset of S which sums to t, find avariable assignment which satisfies Ф.1. If yi is in T then xi is true2. If zi is in T then xi is false224. PolynomialTable size is (k+l)2O(n2)23Back to cryptology •P=NP is still an open question•factorization is not known to be NP-complete•cipher based on a known NP-complete problem24Knapsack Cipher•Public Key: {a1,a2,…,an} set of integers•Plain Text: x1…xn•Cipher Text: [Merkle and Hellman, ’78]niiiaxs125Decryption•Based on an easier problem•{a1,a2,…,an} is a superincreasing sequence11ijjiaa26Linear Time Decryption•xn = 1 iff •Solve it recursively on {a1,a2,…,an-1} and s - xnanniias127How to build the keys?•Modular multiplication (Merkle and Hellman)•Starts with superincreasing sequence {b1,b2,…,bn} •Choose M and W such that•Compute {a1,a2,…,an} such that1),(,1WMGCDaMniiMWbaiimod)(28Decryption•C = (s W-1) mod M, where (W-1W) mod M = 1•Solve subset sum problem with superincreasing sequence {b1,b2,…,bn} and sum c.29Trade offs•bi large  M large  n bits encoded with log2M bits•bi small  easy to break–If bi = 1  aj = W.–Break O(n)•Merkle and Hellman recommended: b1 ≈ 2n, , bn ≈ 22n 12,11nibbijji30Evaluation+ speed ( 100 times faster than RSA )-needs twice the communication capacity (m bits encoded into approximate 2m bits)-larger public key(2n2 bits, 20,000 for n=100, RSA - 500)? security31Knapsack Cipher - Summary•Secret –superincreasing sequence {b1,b2,…,bn}–M–W•Public–{a1,a2,…,an}Remember:MWba ii mod)(32Shamir’s break (’82)•based on the choice of superincreasing sequence• linear transformation to generate public key•What do we need to guess ?(Only one of W and M is enough)33Shamir’s break (cont.)Given the public key {a1,a2,…,an} find M and W such that (ai W) mod M is a superincreasing sequence.b1 = (ai W) mod M  b1 = ai W + k1Mb1/(Mai) =

View Full Document Unlocking...