The classical and quantum complexity of the Goldreich-Levin problem with applications to bit commitment

Simple item page
dc.contributor.advisorCleve, Richard E.
dc.contributor.authorAdcock, Mark R.A.
dc.date.accessioned2005-08-16T17:34:38Z
dc.date.available2005-08-16T17:34:38Z
dc.date.issued2004
dc.descriptionBibliography: p. 125-127en
dc.description.abstractThe classical Goldreich-Levin (G-L) theorem is presented as a block-box query prob­lem, referred to herein as the G-L problem. The query complexity of this problem is bounded in both classical and quantum settings. The well-known upper bound of the classical G-L problem is analyzed in a pedagogical manner. A proof of the lower bound of the classical G-L problem is given using the techniques of classical information theory. This classical analysis is then extended to the realm of quantum computin g by noting the similarity of the noiseless G-L problem to the inner-product query problem solved by the quantum circuit defined by Bernstein and Vazirani (B-V) . An upper bound of the query complexity of the quantum G-L problem is proven by extension of the B-V circuit to incorporate noisy inner-product queries. The lower bound of the query complexity of the quantum G-L problem is proven by adapting the proof of the optimaliy of the quantum search algorithm to include modified inner-product queries. Both the classical and quantum versions of the Goldreich-Levi n theorem have cryptographic applications in the area of bit commitment. A discussion of the im­possibility of unconditional quantum bit commitment is followed by the presentation of both classical and quantum bit commitment protocols that are based on the as­sumption of the existence of classical and quantum one-way permutations. The relative security of the classical and quant m protocols are compared where it is shown that the quantum version is quantitatively more secure.en
dc.format.extentix, 127 leaves : ill. ; 30 cm.en
dc.identifier.citationAdcock, M. R. (2004). The classical and quantum complexity of the Goldreich-Levin problem with applications to bit commitment (Master's thesis, University of Calgary, Calgary, Canada). Retrieved from https://prism.ucalgary.ca. doi:10.11575/PRISM/12092en_US
dc.identifier.doihttp://dx.doi.org/10.11575/PRISM/12092
dc.identifier.isbn061293344Xen
dc.identifier.lccAC1 .T484 2004 A39en
dc.identifier.urihttp://hdl.handle.net/1880/42149
dc.language.isoeng
dc.publisher.facultyGraduate Studies
dc.publisher.facultyScience
dc.publisher.institutionUniversity of Calgaryen
dc.publisher.placeCalgaryen
dc.rightsUniversity of Calgary graduate students retain copyright ownership and moral rights for their thesis. You may use this material in any way that is permitted by the Copyright Act or through licensing that has been assigned to the document. For uses that are not allowable under copyright legislation or licensing, you are required to seek permission.
dc.titleThe classical and quantum complexity of the Goldreich-Levin problem with applications to bit commitment
dc.typemaster thesis
thesis.degree.disciplineComputer Science
thesis.degree.grantorUniversity of Calgary
thesis.degree.nameMaster of Science (MSc)
ucalgary.item.requestcopytrue
ucalgary.thesis.accessionTheses Collection 58.002:Box 1484 520492001
ucalgary.thesis.notesUARCen
ucalgary.thesis.uarcreleaseyen
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
2004_Adcock.pdf
Size:
15.31 MB
Format:
Adobe Portable Document Format
Description:
Download
Collections
Legacy Theses