2-wise Independent Bits uniform independent bits: (random source) X1,X2,.,Xm∈{0,1} Goal:2-wise independent uniform bits: Yi,Y2,.,Yn∈{0,1} n> m C b ⊕b a nonempty subsets: 0 0 0≠S1,S2,,S2m-1C{1,2,.,m} 0 1 1 1 0 1 y=⊕X 1 1 0 iESj2-wise Independent Bits uniform & independent bits: X1, X2,...,Xm 2 {0, 1} (random source) Goal: 2-wise independent uniform bits: Y1, Y2,...,Yn 2 {0, 1} n ￾ m 0 0 0 0 1 1 1 0 1 1 1 0 a b a ￾ b S1, S2,...,S2m￾1 ✓ {1, 2,...,m} nonempty subsets: ; 6= Yj = M i2Sj Xi