CryptoDB
Limits on the Power of Prime-Order Groups: Separating Q-Type from Static Assumptions
| Authors: |
|
|---|---|
| Download: |
|
| Presentation: | Slides |
| Conference: | CRYPTO 2024 |
| Abstract: | Subgroup decision techniques on cryptographic groups and pairings have been critical for numerous applications. Originally conceived in the composite-order setting, there is a large body of work showing how to instantiate subgroup decision techniques in the prime-order setting as well. In this work, we demonstrate the first barrier to this research program, by demonstrating an important setting where composite-order techniques cannot be replicated in the prime-order setting. In particular, we focus on the case of q-type assumptions, which are ubiquitous in group- and pairing-based cryptography, but unfortunately are less desirable than the more well-understood static assumptions. Subgroup decision techniques have had great success in removing q-type assumptions, even allowing q-type assumptions to be generically based on static assumptions on composite-order groups. Our main result shows that the same likely does \emph{not} hold in the prime order setting. Namely, we show that a large class of q-type assumptions, including the security definition of a number of cryptosystems, cannot be proven secure in a black box way from any static assumption. |
BibTeX
@inproceedings{crypto-2024-34208,
title={Limits on the Power of Prime-Order Groups: Separating Q-Type from Static Assumptions},
publisher={Springer-Verlag},
doi={10.1007/978-3-031-68388-6_3},
author={George Lu and Mark Zhandry},
year=2024
}