TY - GEN
T1 - To Label, or Not To Label (in Generic Groups)
AU - Zhandry, Mark
N1 - Publisher Copyright: © 2022, International Association for Cryptologic Research.
PY - 2022
Y1 - 2022
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85141727867&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85141727867&partnerID=8YFLogxK
U2 - 10.1007/978-3-031-15982-4_3
DO - 10.1007/978-3-031-15982-4_3
M3 - Conference contribution
SN - 9783031159817
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 66
EP - 96
BT - Advances in Cryptology – CRYPTO 2022 - 42nd Annual International Cryptology Conference, CRYPTO 2022, Proceedings
A2 - Dodis, Yevgeniy
A2 - Shrimpton, Thomas
PB - Springer Science and Business Media Deutschland GmbH
T2 - 42nd Annual International Cryptology Conference, CRYPTO 2022
Y2 - 15 August 2022 through 18 August 2022
ER -