Let G be a group of prime order q, and let g_1,...,g_n be random elements of G. We say that a vector x = (x_1,...,x_n) ∈ Z_q~n is a discrete log representation of some some element y ∈ G (with respect to g_1,..., g_n) if g_1~(x_1) … g_n~(x_n) = y. Any element y has many discrete log representations, forming an affine subspace of Z_q~n. We show that these representations have a nice continuous leakage-resilience property as follows. Assume some attacker A(g_1,...,g_n, y) can repeatedly learn L bits of information on arbitrarily many random representations of y. That is, A adaptively chooses polynomially many leakage functions f_i:Z_q~n → {0, 1}~L, and learns the value f_i(x_i), where x_i is a fresh and random discrete log representation of y. A wins the game if it eventually outputs a valid discrete log representation x~* of y. We show that if the discrete log assumption holds in G, then no polynomially bounded A can win this game with non-negligible probability, as long as the leakage on each representation is bounded by L ≈ (n - 2) log q = (1 - 2/n) · |x|. As direct extensions of this property, we design very simple continuous leakage-resilient (CLR) one-way function (OWF) and public-key encryption (PKE) schemes in the so called "invisible key update" model introduced by Alwen et al. at CRYPTO'09. Our CLR-OWF is based on the standard Discrete Log assumption and our CLR-PKE is based on the standard Decisional Diffie-Hellman assumption. Prior to our work, such schemes could only be constructed in groups with a bilinear pairing. As another surprising application, we show how to design the first leakage-resilient traitor tracing scheme, where no attacker, getting the secret keys of a small subset of decoders (called "traitors") and bounded leakage on the secret keys of all other decoders, can create a valid decryption key which will not be traced back to at least one of the traitors.
展开▼
