Paper 2022/226

To Label, or Not To Label (in Generic Groups)

Mark Zhandry

Abstract

Generic groups are an important tool for analyzing the feasibility and in-feasibility of group-based cryptosystems. There are two distinct wide-spread versions of generic groups, Shoup's and Maurer's, the main difference being whether or not group elements are given explicit labels. The two models are often treated as equivalent. In this work, however, we demonstrate that the models are in fact quite different, and care is needed when stating generic group results: - We show that numerous textbook constructions are *not* captured by Maurer, but are captured by Shoup. In the other direction, any construction captured by Maurer *is* captured by Shoup. - For constructions that exist in both models, we show that security is equivalent for "single stage" games, but Shoup security is strictly stronger than Maurer security for some "multi-stage" games. - The existing generic group un-instantiability results do not apply to Maurer. We fill this gap with a new un-instantiability result. - We explain how the known black box separations between generic groups and identity-based encryption do not fully apply to Shoup, and resolve this by providing such a separation. - We give a new un-instantiability result for the *algebraic* group model.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. Minor revision.
Keywords
generic group modelalgebraic group model
Contact author(s)
mzhandry @ gmail com
History
2022-02-25: revised
2022-02-25: received
See all versions
Short URL
https://ia.cr/2022/226
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/226,
      author = {Mark Zhandry},
      title = {To Label, or Not To Label (in Generic Groups)},
      howpublished = {Cryptology ePrint Archive, Paper 2022/226},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/226}},
      url = {https://eprint.iacr.org/2022/226}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.