Paper 2014/1006

Simple composition theorems of one-way functions -- proofs and presentations

Jaime Gaspar and Eerke Boiten


One-way functions are both central to cryptographic theory and a clear example of its complexity as a theory. From the aim to understand theories, proofs, and communicability of proofs in the area better, we study some small theorems on one-way functions, namely: composition theorems of one-way functions of the form "if $f$ (or $h$) is well-behaved in some sense and $g$ is a one-way function, then $f \circ g$ (respectively, $g \circ h$) is a one-way function". We present two basic composition theorems, and generalisations of them which may well be folklore. Then we experiment with different proof presentations, including using the Coq theorem prover, using one of the theorems as a case study.

Note: Intending to further expand our thoughts on proof presentation for submission to a conference later, we would like to invite comment from the cryptology community first. We could not find these theorems anywhere, not even as "folklore" or as "an obvious homework exercise". Any such pointers or further suggestions would be much appreciated. The same goes for thoughts on definitions of collision-freeness: the transition to "families" to solve a technical problem seems to be broadly resented in the literature, is our alternative felt to be sensible?

Available format(s)
Publication info
Preprint. MINOR revision.
one-way functionsproof presentationCoq
Contact author(s)
e a boiten @ kent ac uk
2014-12-25: revised
2014-12-25: received
See all versions
Short URL
Creative Commons Attribution


      author = {Jaime Gaspar and Eerke Boiten},
      title = {Simple composition theorems of one-way functions -- proofs and presentations},
      howpublished = {Cryptology ePrint Archive, Paper 2014/1006},
      year = {2014},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.