File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: One-Way Functions in Reversible Computations

TitleOne-Way Functions in Reversible Computations
Authors
Issue Date1997
PublisherTaylor & Francis Ltd. The Journal's web site is located at http://www.tandf.co.uk/journals/titles/01611194.asp
Citation
Cryptologia, 1997, v. 21 n. 2, p. 139-148 How to Cite?
AbstractOne-way functions are used in modern crypto-systems as doortraps because their inverse functions are supposed to be difficult to compute. Nonetheless with the discovery of reversible computation, it seems that one may break a one-way function by running a reversible computer backward. Here, we argue that reversible computation alone poses no threat to the existence of one-way functions because of the generation of “garbage bits” during computations. Consequently, we prove a necessary and sufficient condition for a one-to-one function to be one-way in terms of the growth rate of the total number of possible garbage bit configurations with the input size.
Persistent Identifierhttp://hdl.handle.net/10722/81057
ISSN
2015 Impact Factor: 0.213
2015 SCImago Journal Rankings: 0.160

 

DC FieldValueLanguage
dc.contributor.authorChau, HFen_HK
dc.contributor.authorLo, HKen_HK
dc.date.accessioned2010-09-06T08:13:16Z-
dc.date.available2010-09-06T08:13:16Z-
dc.date.issued1997en_HK
dc.identifier.citationCryptologia, 1997, v. 21 n. 2, p. 139-148en_HK
dc.identifier.issn0161-1194en_HK
dc.identifier.urihttp://hdl.handle.net/10722/81057-
dc.description.abstractOne-way functions are used in modern crypto-systems as doortraps because their inverse functions are supposed to be difficult to compute. Nonetheless with the discovery of reversible computation, it seems that one may break a one-way function by running a reversible computer backward. Here, we argue that reversible computation alone poses no threat to the existence of one-way functions because of the generation of “garbage bits” during computations. Consequently, we prove a necessary and sufficient condition for a one-to-one function to be one-way in terms of the growth rate of the total number of possible garbage bit configurations with the input size.-
dc.languageengen_HK
dc.publisherTaylor & Francis Ltd. The Journal's web site is located at http://www.tandf.co.uk/journals/titles/01611194.aspen_HK
dc.relation.ispartofCryptologiaen_HK
dc.titleOne-Way Functions in Reversible Computationsen_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=0161-1194&volume=21&spage=139&epage=148&date=1997&atitle=One-Way+Functions+in+Reversible+Computationsen_HK
dc.identifier.emailChau, HF: hfchau@hkusua.hku.hken_HK
dc.identifier.authorityChau, HF=rp00669en_HK
dc.identifier.doi10.1080/0161-119791885869-
dc.identifier.hkuros22658en_HK

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats