<?xml version='1.0' encoding='UTF-8'?><?xml-stylesheet href='static/style.xsl' type='text/xsl'?><OAI-PMH xmlns="http://www.openarchives.org/OAI/2.0/" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.openarchives.org/OAI/2.0/ http://www.openarchives.org/OAI/2.0/OAI-PMH.xsd"><responseDate>2026-11-22T10:24:22Z</responseDate><request verb="GetRecord" identifier="oai:ecommons.cornell.edu:1813/120888" metadataPrefix="dim">https://ecommons.cornell.edu/server/oai/request</request><GetRecord><record><header><identifier>oai:ecommons.cornell.edu:1813/120888</identifier><datestamp>2026-05-15T17:52:49Z</datestamp><setSpec>com_1813_35</setSpec><setSpec>col_1813_47</setSpec></header><metadata><dim:dim xmlns:dim="http://www.dspace.org/xmlns/dspace/dim" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:doc="http://www.lyncode.com/xoai" xsi:schemaLocation="http://www.dspace.org/xmlns/dspace/dim http://www.dspace.org/schema/dim.xsd">
   <dim:field mdschema="dc" element="contributor" qualifier="author">Liu, Yanyi</dim:field>
   <dim:field mdschema="dc" element="contributor" qualifier="chair" lang="en_US">Pass, Rafael</dim:field>
   <dim:field mdschema="dc" element="contributor" qualifier="committeeMember" lang="en_US">Shi, Runting</dim:field>
   <dim:field mdschema="dc" element="contributor" qualifier="committeeMember" lang="en_US">Kozen, Dexter</dim:field>
   <dim:field mdschema="dc" element="contributor" qualifier="committeeMember" lang="en_US">Chattopadhyay, Eshan</dim:field>
   <dim:field mdschema="dc" element="contributor" qualifier="committeeMember" lang="en_US">Stephens-Davidowitz, Noah</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="accessioned">2026-04-02T18:51:41Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="available">2026-04-02T18:51:41Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="issued">2025-08</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="other">ProQuest Submission ID: 15256</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="other">ProQuest Publication ID: 32171526</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="uri">https://hdl.handle.net/1813/120888</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="doi">https://doi.org/10.7298/jmys-0423</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="bibid">17422438</dim:field>
   <dim:field mdschema="dc" element="description" lang="en_US">606 pages</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="abstract" lang="en_US">Whether secure Cryptography exists is one of the most importantopen problems in Computer Science; consequently, cryptographic schemes today rely on unproven computational hardness assumptions. We will survey a recent thread of work showing equivalences betweenthe existence of some of the most basic cryptographic primitives, and the hardness of various computational problems related to the notion of time-bounded Kolmogorov Complexity (dating back to the 1960s). These results yield the first natural computational problemscharacterizing the feasibility of central primitives and protocols in Cryptography, as well as the first unstructured computational problems enabling public-key cryptography.</dim:field>
   <dim:field mdschema="dc" element="language" qualifier="iso">en</dim:field>
   <dim:field mdschema="dc" element="rights">Attribution 4.0 International</dim:field>
   <dim:field mdschema="dc" element="rights" qualifier="uri">https://creativecommons.org/licenses/by/4.0/</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en_US">Cryptography</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en_US">Kolmogorov Complexity</dim:field>
   <dim:field mdschema="dc" element="title" lang="en_US">On Cryptography and Kolmogorov Complexity</dim:field>
   <dim:field mdschema="dc" element="type" lang="en_US">dissertation or thesis</dim:field>
   <dim:field mdschema="dc" element="format" qualifier="mimetype">application/pdf</dim:field>
   <dim:field mdschema="thesis" element="degree" qualifier="discipline">Computer Science</dim:field>
   <dim:field mdschema="thesis" element="degree" qualifier="grantor">Cornell University</dim:field>
   <dim:field mdschema="thesis" element="degree" qualifier="level">Doctor of Philosophy</dim:field>
   <dim:field mdschema="thesis" element="degree" qualifier="name">Ph. D., Computer Science</dim:field>
   <dim:field mdschema="dcterms" element="license">https://hdl.handle.net/1813/59810.2</dim:field>
   <dim:field mdschema="dspace" element="entity" qualifier="type">Publication</dim:field>
   <dim:field mdschema="cris" element="virtual" qualifier="collection" authority="https://ecommons.cornell.edu/handle/1813/47" confidence="600">Cornell Theses and Dissertations</dim:field>
   <dim:field mdschema="cris" element="virtual" qualifier="author">Liu, Yanyi</dim:field>
   <dim:field mdschema="cris" element="virtualsource" qualifier="collection">5893a6ea-7af3-41d7-abc6-04bcd26ab5df</dim:field>
   <dim:field mdschema="others" element="access-status">open.access</dim:field>
   <dim:field mdschema="others" element="access-status">open.access</dim:field>
   <dim:field mdschema="cerif" element="openaire" authority="" confidence="-1">&lt;Publication xmlns="https://www.openaire.eu/cerif-profile/1.1/" id="c1155843-9e1b-4a30-a642-87ee2ec0fef0">
	&lt;Type xmlns="https://www.openaire.eu/cerif-profile/vocab/COAR_Publication_Types">http://purl.org/coar/resource_type/c_1843&lt;/Type>
	&lt;Language>en&lt;/Language>
   	&lt;Title>On Cryptography and Kolmogorov Complexity&lt;/Title>
   	&lt;PublishedIn>
    	&lt;Publication>
      	&lt;/Publication>
   	&lt;/PublishedIn>
   	&lt;PublicationDate>2025-08&lt;/PublicationDate>
   	&lt;DOI>https://doi.org/10.7298/jmys-0423&lt;/DOI>
   	&lt;Authors>
      	&lt;Author>
        	&lt;DisplayName>Liu, Yanyi&lt;/DisplayName>
         	&lt;Affiliation>
         		&lt;OrgUnit>
         		&lt;/OrgUnit>
         	&lt;/Affiliation>
      	&lt;/Author>
	&lt;/Authors>
   	&lt;Editors>
	&lt;/Editors>
    &lt;Publishers>
        &lt;Publisher>
            &lt;OrgUnit />
        &lt;/Publisher>
    &lt;/Publishers>
    &lt;License>https://creativecommons.org/licenses/by/4.0/&lt;/License>
    &lt;Keyword>Cryptography&lt;/Keyword>
    &lt;Keyword>Kolmogorov Complexity&lt;/Keyword>
   	&lt;Abstract>Whether secure Cryptography exists is one of the most importantopen problems in Computer Science; consequently, cryptographic schemes today rely on unproven computational hardness assumptions. We will survey a recent thread of work showing equivalences betweenthe existence of some of the most basic cryptographic primitives, and the hardness of various computational problems related to the notion of time-bounded Kolmogorov Complexity (dating back to the 1960s). These results yield the first natural computational problemscharacterizing the feasibility of central primitives and protocols in Cryptography, as well as the first unstructured computational problems enabling public-key cryptography.&lt;/Abstract>
	&lt;Access xmlns="http://purl.org/coar/access_right" 
    >
    &lt;/Access>
&lt;/Publication>
</dim:field>
</dim:dim>
</metadata></record></GetRecord></OAI-PMH>