Paper 2014/1006 Original: eprint.iacr.org/2014/1006 ↗
Simple composition theorems of one-way functions -- proofs and presentations
Abstract
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.
Metadata
- Available format(s)
PDF- Category
- Foundations
- Publication info
- Preprint.
- History
- 2014-12-25: last updated
- 2014-12-25: published
- Short URL
- https://ia.cr/2014/1006
- License
- https://creativecommons.org/licenses/by/4.0/
BibTeX
@misc{cryptoeprint:2014/1006,
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},
url = {https://eprint.iacr.org/2014/1006}
}