|
|
Type of Document Dissertation Author Interlando, Jose Carmelo Author's Email Address carmelo.interlando@sdsu.edu URN etd-11042005-133727 Title Toward a Theory of One-Way Functions via Gate Complexity of Boolean Functions. Degree Doctor of Philosophy Department Mathematics Advisory Committee
Advisor Name Title Joachim Rosenthal Committee Chair Albert Miller Committee Member Andrew Sommese Committee Member Claudia Polini Committee Member Julia F. Knight Committee Member Keywords
- gate complexity of Boolean functions.
- computational security
- one-way functions
- cryptography
Date of Defense 2005-10-12 Availability unrestricted Abstract 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 viagate (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.
Files
Filename Size Approximate Download Time (Hours:Minutes:Seconds)
28.8 Modem 56K Modem ISDN (64 Kb) ISDN (128 Kb) Higher-speed Access InterlandoJC112005.pdf 572.09 Kb 00:02:38 00:01:21 00:01:11 00:00:35 00:00:03