## Abstract

Let double-struck G be a group of prime order q, and let g _{1},...,g_{n} be random elements of double-struck G. We say that a vector x = (x_{1},...,x_{2}) ∈ ℤ _{q}^{n} is a discrete log representation of some some element y ∈ double-struck G (with respect to g_{1},...,g_{n}) if g_{1}^{x1}⋯g_{n}^{xn} = y. Any element y has many discrete log representations, forming an affine subspace of ℤ_{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} : ℤ_{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 double-struck 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.

Original language | English (US) |
---|---|

Title of host publication | Advances in Cryptology, ASIACRYPT 2013 - 19th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings |

Pages | 401-420 |

Number of pages | 20 |

Edition | PART 2 |

DOIs | |

State | Published - 2013 |

Event | 19th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2013 - Bengaluru, India Duration: Dec 1 2013 → Dec 5 2013 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Number | PART 2 |

Volume | 8270 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Other

Other | 19th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2013 |
---|---|

Country/Territory | India |

City | Bengaluru |

Period | 12/1/13 → 12/5/13 |

## ASJC Scopus subject areas

- Theoretical Computer Science
- General Computer Science