- No file added yet -

# Toward a Theory of One-Way Functions via Gate Complexity of Boolean Functions.

thesis

posted on 2005-11-04, 00:00 authored by Jose Carmelo InterlandoOne of the most important properties of a cryptographic system is a proof of its security. There are two types of security: information (or theoretical) security and computational (or practical) security. The focus of this work is on provable computational security via gate (or circuit) complexity of Boolean functions. The computational security of public-key cryptographic systems depends

*fundamentally*on trapdoor one-way functions. However, the existence of such functions has yet to be proved. Informally speaking, a trapdoor one-way function is an efficiently-computable function such that there are no efficient algorithms for inverting it unless some extra information, known as trapdoor information, is available. It is important to realize that the so-called 'trapdoor one-way functions' used in modern cryptographic systems (to perform financial transactions over the internet, for example) are good*candidates*, at best. There is no formal proof that these candidates are de*facto*trapdoor one-way functions. For example, security proofs for one of the most widely used public-key cryptographic systems, namely, the RSA, are based on the*unproven*assumption that large numbers cannot be factored efficiently. Therefore, it is not safe to base the security of large economic systems on such assumptions. Thus, from a cryptographical point of view, the crucial problem in gate complexity theory is to prove nontrivial lower bounds on the complexity of breaking practical cryptographic systems, for example, one-way functions. In this work we argue that the theory of circuit complexity of Boolean functions provides the mathematical background to achieve provable computational security. Among computational models, the circuit model has an especially simple definition and may be more amenable to combinatorial analysis. The gate complexity of permutations of GF(2^{n}) and of linear and quadratic Boolean functions is studied by deriving bounds on the number of modulo-two additions and multiplications necessary to realize them.## History

## Date Created

2005-11-04## Date Modified

2018-10-30## Defense Date

2005-10-12## Research Director(s)

Joachim Rosenthal## Committee Members

Albert Miller Andrew Sommese Julia F. Knight Claudia Polini## Degree

- Doctor of Philosophy

## Degree Level

- Doctoral Dissertation

## Language

- English

## Alternate Identifier

etd-11042005-133727## Publisher

University of Notre Dame## Program Name

- Mathematics

## Usage metrics

## Categories

No categories selected## Licence

## Exports

RefWorks

BibTeX

Ref. manager

Endnote

DataCite

NLM

DC