Како би докази са „ефикасним нултим знањем“ могли да трансформишу криптографију
Нова алатка проширује начине на које људи могу доказати да су решили проблем без откривања решења
У математици, докази се могу записивати и делити. У криптографији, када људи покушавају да избегну откривање својих тајни, докази нису увек тако једноставни — али нови резултат значајно затвара овај јаз.
Докази без знања су најближи што криптографија може да дође до магије. Обећавају да ће дозволити једној особи да убеди другу у истинитост неке чињенице — рецимо да зна решење судоку загонетке — без давања било какве информације о томе. Такви докази могу помоћи људима да виртуелно аутентификују идентитете, изврше онлајн банкарске трансакције, изграде блокове и још много тога.
Криптографи су, међутим, дуго разумео да се докази без знања не могу безбедно записати као типичан математички доказ. Уместо тога, доказивач мора да комуницира са особом коју убеђује. У ретким случајевима, доказивач такође може некога да убеди у нешто неистинито (као што је да је судоку загонетка довршена када нема решење).
О подршци научном новинарству
Ако уживате у овом чланку, размислите о томе да подржите наше награђивано новинарство претплата. Куповином претплате помажете да се обезбеди будућност упечатљивих прича о открићима и идејама које данас обликују наш свет.
Рачунарски научник Рахул Иланго схватио је да постоји јаз између тога како се дефинише нулто знање и како се оно користи. Типични докази без знања захтевају демонстрацију како да се направи оно што се зове симулатор, који може поново да креира кораке доказа без да се заправо зна тајно решење. Постојање овог симулатора показује да процес доказивања не открива ништа о самом решењу. Али Иланго је открио да у неким случајевима може бити довољно да се једноставно покаже да се постојање симулатора не може искључити. Он представљено резултат на ИЕЕЕ симпозијуму о основама рачунарских наука 2025. у Сиднеју.
„Можете замислити неки заиста чудан сценарио у којем је криптографски систем несигуран (и открива нешто о информацијама које су закључане унутра), али је немогуће доказати да је несигуран“, каже Иланго, који се налази на Институту за напредне студије у Принстону, Њ. „То значи да је у основи безбедан за све практичне сврхе.
Пошто је овај нови критеријум само мало лакши за задовољити од нултог знања, Иланго би могао да направи протоколе који не захтевају интеракцију страна и који спречавају доказивача да буде у стању да убеди лажним одговорима.
Да би конструисао нови систем доказа, назван ефективни доказ без знања, Иланго је преузео идеје из теореме о непотпуности математичара Курта Гедела из 1931. године, која у основи каже да многи скупови претпоставки имају неке чињенице које не могу ни доказати ни оповргнути. Иланго је показао да може да конструише систем доказа у коме су такве претпоставке, укључујући скуп познат као ЗФЦ који лежи у основи већег дела математике, не може оповргнути постојање симулатора чак и када не постоји.
Универзитет Калифорније у Лос Анђелесу, компјутерски научник Амит Сахаи, који није био укључен у рад, каже да се ова парадигма већ показала кориснијом него што је у почетку очекивао. „Тако је лепо“, каже Сахаи. „(Иланго)ов рад је, по мом мишљењу, најкреативнији и најконсеквентнији рад у области доказа без знања барем у последњој деценији.
Време је да се заузмемо за науку
Ако вам се допао овај чланак, замолио бих вас за подршку. Сциентифиц Америцан служио је као заговорник науке и индустрије 180 година, а управо сада је можда најкритичнији тренутак у тој двовековној историји.
Био сам а Сциентифиц Америцан претплатник од моје 12 година, и то је помогло у обликовању начина на који гледам на свет. СциАм увек ме образује и одушевљава, и изазива осећај страхопоштовања према нашем огромном, предивном универзуму. Надам се да ће то учинити и за вас.
Ако ти претплатите се на Сциентифиц Америцанпомажете да осигурамо да је наша покривеност усредсређена на смислена истраживања и открића; да имамо ресурсе да извештавамо о одлукама које прете лабораторијама широм САД; и да подржавамо и надобудне и запослене научнике у време када вредност саме науке пречесто остане непризната.
Заузврат, добијате важне вести, задивљујући подкасти, бриљантна инфографика, не могу пропустити билтене, видео снимке које морате погледати, изазовне игре и најбоље писање и извештавање у свету науке. Можете чак поклонити некоме претплату.
Никада није било важнијег тренутка да устанемо и покажемо зашто је наука важна. Надам се да ћете нас подржати у тој мисији.
