Есептік айырмашылық - Computational indistinguishability - Wikipedia

Жылы есептеу күрделілігі және криптография, тарату екі отбасы болып табылады есептеу жағынан айырмашылығы жоқ егер ешқандай тиімді алгоритм олардың арасындағы айырмашылықты кішігірім ықтималдылықтан басқа айыра алмаса.

Ресми анықтама

Келіңіздер және екі бол тарату ансамбльдері индекстелген а қауіпсіздік параметрі n (бұл әдетте кіріс ұзындығына қатысты); егер олар бар болса, оларды есептеу мүмкін емес деп айтамыз біркелкі емес ықтималдық көпмүшелік уақыт алгоритм A, келесі шама а елеусіз функция жылы n:

белгіленді .[1] Басқаша айтқанда, әрбір тиімді алгоритм A 'үлгілері сәйкес берілген кезде мінез-құлқы айтарлықтай өзгермейді Д.n немесе En шегінде . Есептеудің ажырамайтындығының тағы бір түсіндірмесі - бұл екі ансамбльдің арасындағы айырмашылықты белсенді түрде анықтауға тырысатын көпмүшелік алгоритмдер мұны істей алмайды: кез-келген осындай алгоритм тек біреуі болжағаннан гөрі жақсы нәтиже береді.

Байланысты түсініктер

Анықтамада айқын емес дегеніміз - алгоритм, , таратылымдардың біреуінен алынған бір үлгіге сүйене отырып шешуі керек. Екі үлестіруді ажыратуға тырысатын алгоритм қажет болғанша көптеген үлгілерге қол жеткізе алатын жағдай туралы ойлауға болады. Сондықтан бірнеше үлгілерді қарастыратын полиномдық уақыт алгоритмімен ажырата алмайтын екі ансамбль деп саналады уақытты полиномиалды іріктеу арқылы ажыратуға болмайды.[2]:107 Егер көпмүшелік уақыт алгоритмі көпмүшелік уақытта үлгілерді құра алса немесе а-ға қол жеткізе алса кездейсоқ оракул ол үшін үлгілерді тудырады, содан кейін полиномдық-уақыттық іріктеу арқылы ажырату есептеудің ажырамайтындығына тең болады.[2]:108

Әдебиеттер тізімі

  1. ^ Дәріс 4 - Есептік айырмашылық, жалған кездейсоқ генераторлар
  2. ^ а б Голдрейх, О. (2003). Криптографияның негіздері. Кембридж, Ұлыбритания: Кембридж университетінің баспасы.

Сыртқы сілтемелер


Бұл мақалаға есептік жағынан айырмашылығы жоқ материал кіреді PlanetMath бойынша лицензияланған Creative Commons Attribution / Share-Alike лицензиясы.