סוג האירוע

בחר הכל

הרצאות פומביות

קולוקוויום

סמינרים

כנסים וימי עיון

מועדון IAP

Cryptography from the Hardness of Kolmogorov Complexity

Prof. Rafael Pass (Cornell)

07 בנובמבר 2021, 11:00 - 12:30 
Check Point 420 
קולוקוויום במדעי המחשב

Abstract

 

Whether one-way functions (OWFs) exist is the most important outstanding problem in Cryptography. We will survey a recent thread of work (Liu-Pass, FOCS'20, Liu-Pass, STOC'21, Liu-Pass, Crypto'21) showing the equivalence of the existence of OWFs and (mild) average-case hardness of various problems related to time-bounded Kolmogorov complexity that date back to the 1960s.
 

These result yield the first natural, and well-studied, computational problems characterizing the feasibility of the central private-key primitives and protocols in Cryptography. Based on joint works with Yanyi Liu.

 

אוניברסיטת תל אביב עושה כל מאמץ לכבד זכויות יוצרים. אם בבעלותך זכויות יוצרים בתכנים שנמצאים פה ו/או השימוש
שנעשה בתכנים אלה לדעתך מפר זכויות, נא לפנות בהקדם לכתובת שכאן >>