University of Notre Dame
Browse
- No file added yet -

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

Download (558.68 kB)
thesis
posted on 2005-11-04, 00:00 authored by Jose Carmelo Interlando
One 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(2n) 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

    Dissertations

    Categories

    No categories selected

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC