Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top

2012 | Book

Introduction Read chapter Read first chapter

Black-Box Models of Computation in Cryptology

Author: Tibor Jager

Publisher: Vieweg+Teubner Verlag

Part of: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Login to get access
insite
SEARCH

About this book

Generic group algorithms solve computational problems defined over algebraic groups without exploiting properties of a particular representation of group elements. This is modeled by treating the group as a black-box. The fact that a computational problem cannot be solved by a reasonably restricted class of algorithms may be seen as support towards the conjecture that the problem is also hard in the classical Turing machine model. Moreover, a lower complexity bound for certain algorithms is a helpful insight for the search for cryptanalytic algorithms.

Tibor Jager addresses several fundamental questions concerning algebraic black-box models of computation: Are the generic group model and its variants a reasonable abstraction? What are the limitations of these models? Can we relax these models to bring them closer to the reality?

Table of Contents

Frontmatter
1. Introduction
Abstract
The security of many cryptosystems relies on assumptions that certain computational problems, mostly from number theory and algebra, are intractable. Therefore it is important to study the validity of these assumptions. Ideally, we would like to show that these assumptions hold in a standard model of computation, e.g. where algorithms intending to solve a computational problem are modeled as Turing machines with reasonably restricted running time. Unfortunately, proving useful lower complexity bounds in the standard model seems to be impossible with currently available techniques.
Tibor Jager
2. Black-Box Models of Computation
Abstract
Several abstract models of computation have been proposed in the literature to capture the notion of “generic groups” or their extensions [BS84, Nec94, Sho97, Mau05]. The black-box model we are going to describe in the sequel is a generalization of the model introduced by Maurer in [Mau05], which in turn can be seen as a generalization of the model of [Sho97]. While Maurer's model captures only the case where a generic algorithm operates on elements of a single algebraic structure, like a group or a ring, we extend this model in order to be able to describe settings where more than one algebraic structure is considered, as in pairing-based cryptography [DBS04], for instance.
Tibor Jager
3. On Black-Box Ring Extraction and Integer Factorization
Abstract
The black-box ring extraction (BBRE) problem is the problem of extracting a secret ring element from a black-box which may be queried to perform the ring operations and equality tests on internally stored ring elements. This problem has at least two important applications to cryptography (see Section 3.1 for details).
Tibor Jager
4. Analysis of Cryptographic Assumptions in the Generic Ring Model
Abstract
One goal of the generic group model is to provide a reasonable abstraction for certain groups, such as elliptic curve groups, for which not many properties beyond the abstractly defined properties of a group are known.
Tibor Jager
5. The Generic Composite Residuosity Problem
Tibor Jager
6. Semi-Generic Groups and Their Applications
Abstract
The generic group model (GGM) is used frequently to provide evidence towards newly introduced hardness assumptions. In particular in the area of pairing-based cryptography numerous novel assumptions have been introduced over the last decade. Unfortunately, the GGM does not reflect many known properties of bilinear group settings. Not at least currently known algorithms for solving computational problems over bilinear groups are captured, and thus hardness results in this model are of limited significance.
Tibor Jager
Backmatter
Metadata
Title
Black-Box Models of Computation in Cryptology
Author
Tibor Jager
Copyright Year
2012
Publisher
Vieweg+Teubner Verlag
Electronic ISBN
978-3-8348-1990-1
Print ISBN
978-3-8348-1989-5
DOI
https://doi.org/10.1007/978-3-8348-1990-1

Premium Partner

    Image Credits