Paper 2007/360 Original: eprint.iacr.org/2007/360 ↗
Sufficient Conditions for Intractability over Black-Box Groups: Generic Lower Bounds for Generalized DL and DH Problems
Abstract
The generic (aka. black-box) group model is a valuable methodology for analyzing the computational hardness of number-theoretic problems used in cryptography. Since the properties ensuring generic hardness have not been well-studied and formalized yet, for each newly proposed problem an entire hardness proof has to be done from scratch. In this work we identify criteria that guarantee the hardness of generalized DL and DH problems in an extended generic group model where algorithms are allowed to perform any operation representable by a polynomial function. Assuming our conditions are satisfied, we are able to provide negligible upper bounds on the success probability of such algorithms. As useful means for the formalization of definitions and conditions we explicitly relate the concepts of generic algorithms and straight-line programs that have only been used independently in cryptography so far.
Metadata
- Available format(s)
PDF- Publication info
- Preprint.
- History
- 2008-08-08: last updated
- 2007-09-13: published
- Short URL
- https://ia.cr/2007/360
- License
- https://creativecommons.org/licenses/by/4.0/
BibTeX
@misc{cryptoeprint:2007/360,
author = {Andy Rupp and Gregor Leander and Endre Bangerter and Ahmad-Reza Sadeghi and Alexander W. Dent},
title = {Sufficient Conditions for Intractability over Black-Box Groups: Generic Lower Bounds for Generalized DL and DH Problems},
howpublished = {Cryptology {ePrint} Archive, Paper 2007/360},
year = {2007},
url = {https://eprint.iacr.org/2007/360}
}