Skip to main content
Kent Academic Repository

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

Gaspar, Jaime and Boiten, Eerke Albert (2014) Simple composition theorems of one-way functions -- proofs and presentations. Technical report. IACR EPrints (The full text of this publication is not currently available from this repository. You may be able to access a copy if URLs are provided) (KAR id:52889)

The full text of this publication is not currently available from this repository. You may be able to access a copy if URLs are provided.
Official URL:
https://eprint.iacr.org/2014/1006

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.

Item Type: Reports and Papers (Technical report)
Uncontrolled keywords: foundations/one-way functions, proof presentation, Coq
Subjects: Q Science > QA Mathematics (inc Computing science)
Divisions: Divisions > Division of Computing, Engineering and Mathematical Sciences > School of Computing
University-wide institutes > Institute of Cyber Security for Society
Depositing User: Eerke Boiten
Date Deposited: 07 Dec 2015 17:45 UTC
Last Modified: 17 Aug 2022 10:59 UTC
Resource URI: https://kar.kent.ac.uk/id/eprint/52889 (The current URI for this page, for reference purposes)

University of Kent Author Information

Gaspar, Jaime.

Creator's ORCID:
CReDIT Contributor Roles:

Boiten, Eerke Albert.

Creator's ORCID: https://orcid.org/0000-0002-9184-8968
CReDIT Contributor Roles:
  • Depositors only (login required):

Total unique views for this document in KAR since July 2020. For more details click on the image.