Қателермен сақиналық оқыту - Ring learning with errors key exchange

Жылы криптография, а ашық кілттермен алмасу алгоритмі а криптографиялық алгоритм бұл екі тарапқа құпия кілт құруға және бөлісуге мүмкіндік береді, олар өздері арасында хабарламаларды шифрлау үшін қолдана алады. The қателіктермен сақиналық оқыту кілттермен алмасу (RLWE-KEX) - а-ға ие қарсыласқа қарсы қорғанысқа арналған ашық кілттермен алмасу алгоритмдерінің жаңа класының бірі кванттық компьютер. Бұл өте маңызды, себебі кейбіреулер ашық кілт алгоритмдері қазіргі кезде қолданыста болған кезде және егер мұндай компьютерлер іске асырылатын болса, кванттық компьютер оңай бұзылады. RLWE -KEX - жиынтықтардың бірі кейінгі кванттық криптографиялық байланысты кейбір математикалық есептерді шешудің қиындығына негізделген алгоритмдер торлар. Ескі торға негізделген криптографиялық алгоритмдерден айырмашылығы RLWE -KEX торлардағы белгілі қиын проблемаға дейін төмендетіледі.

Фон

1980 жылдардан бастап криптографиялық қауіпсіздік негізгі алмасулар және ЭЦҚ Интернет арқылы, ең алдымен, аз санға негізделген ашық кілт алгоритмдер. Бұл алгоритмдердің қауіпсіздігі классикалық есептеулердегі есептеулердің дәл осындай аз санына негізделген. Бұл проблемалардың қиындығы мұқият таңдалған екі жай сандардың көбейтіндісін көбейту, есептеу қиын дискретті логарифмдер мұқият таңдалған ақырлы өрісте және мұқият таңдалған дискретті логарифмдерді есептеудің қиындығы эллиптикалық қисық топ. Бұл мәселелерді классикалық компьютерде шешу өте қиын (компьютердің түрі 1940 жылдардан бастап бүгінгі күнге дейін әлемге белгілі), бірақ оларды салыстырмалы түрде аз кванттық компьютер тек 5-тен 10 мыңға дейінгі жадты пайдалану. Компьютерлік индустрияда кең ауқымды кванттық компьютерлердің 2030 жылға жуық қол жетімді болатындығына сенім бар. Егер а кванттық компьютер жеткілікті көлемде салынған, осы үш классикалық қиын мәселелерге негізделген барлық ашық кілт алгоритмдері сенімсіз болар еді. Бұл ашық кілт криптографиясы бүгінде Интернеттегі веб-сайттардың қауіпсіздігін қамтамасыз ету, компьютерге кіру ақпаратын қорғау және біздің компьютерлердің зиянды бағдарламалық жасақтаманы қабылдамау үшін қолданылады.

Кванттық компьютердің шабуылына ұшырамайтын криптография деп аталады кванттық қауіпсіз, немесе кейінгі кванттық криптография. Кванттық төзімді криптографиялық алгоритмдердің бір класы «деп аталатын тұжырымдамаға негізделгенқателіктермен оқыту «енгізген Одед Регев 2005 жылы.[1] Қателері бар оқытудың мамандандырылған түрі жұмыс істейді көпмүшеліктер сақинасы астам ақырлы өріс. Бұл мамандандырылған форма деп аталады қателіктермен сақиналық оқыту немесе RLWE.

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

A кілттермен алмасу алгоритмі байланыс кілтінде екі коммуниканттың ортақ құпия кілтін белгілейтін ашық кілт алгоритмінің түрі. Кілттерді айырбастаудың классикалық мысалы болып табылады Диффи-Хеллман кілттерімен алмасу. Айырбас желінің бір шетінен бір берілуден және сілтеменің екінші шетінен бір берілуден тұрады. Диффи-Хеллман және Эллиптикалық қисық сызық Диффи – Хеллман кілттермен алмасудың ең танымал екі алгоритмі.

RLWE кілттер алмасуы «кванттық қауіпсіз «кеңінен қолданылатынды ауыстыру Диффи-Хеллман және эллиптикалық қисық Diffie – Hellman сенімсіз байланыс арналары бойынша құпия кілттерді орнатуды қамтамасыз ету үшін қолданылатын кілттер алмасуы. Diffie-Hellman және Elliptic Curve Diffie-Hellman сияқты, Ring-LWE кілттері «» деп аталатын криптографиялық қасиетті ұсынадыалға құпия «; оның мақсаты тиімділікті төмендету болып табылады жаппай бақылау бағдарламаларды шешіп, бұқаралық шифрды шешуге мүмкіндік беретін ұзақ мерзімді құпия кілттердің болмауын қамтамасыз етеді.

Кіріспе

Бастап басталады қарапайым бүтін q, the Сақина-LWE кілттермен алмасу жұмыс істейді көпмүшеліктер сақинасы көпмүше модулі бүтін сандар өрісіндегі коэффициенттермен mod q (яғни сақина) ). Көпмүшелерді көбейту және қосу әдеттегідей жұмыс істейді, көбейту нәтижелері төмендетілген режимде болады .

LWE және Ring LWE-ді кілттермен алмасу үшін қолдану идеясын алғаш рет Цинциннати университетінде 2011 жылы Цзинтай Дин ұсынған және ұсынған. Идея матрицалық көбейтудің ассоциативтілігінен туындайды және қателіктер қауіпсіздікті қамтамасыз ету үшін қолданылады. Қағаз[2] 2012 жылы уақытша патенттік өтінім берілгеннен кейін пайда болды. Хаттаманың қауіпсіздігі LWE мәселесін шешудің қаттылығына негізделген.

2014 жылы Peikert кілтті тасымалдау схемасын ұсынды[3] Ding-тің негізгі идеясын ұстану, мұнда Ding конструкциясында дөңгелектеу үшін қосымша 1-биттік сигнал жіберудің жаңа идеясы қолданылады.

«Жаңа үміт» іске асыру[4] Google-дан кейінгі кванттық эксперимент үшін таңдалған,[5] қателіктерді үлестіруде Пейкерт схемасын қолданады.

128-ден біршама үлкен қауіпсіздік биттері, Сингх Пейкерт схемасы үшін 6956 биттік ашық кілттері бар параметрлер жиынтығын ұсынады.[6] Тиісті құпия кілт шамамен 14000 бит болады. Кейінірек Diffie-Hellman кілттер алмасуының классикалық MQV нұсқасының RLWE нұсқасын Чжан және басқалар жариялады. Екі негізгі биржаның қауіпсіздігі идеалды торда шамамен қысқа векторларды табу мәселесімен тікелей байланысты. Бұл мақала Ding-тің RLWE жұмысын «Қателіктермен оқуға негізделген қарапайым қамтамасыз етілген қауіпсіз алмасу схемасы» бойынша мұқият қадағалайды.[2] Осы презентация үшін типтік көпмүше келесі түрде өрнектеледі:

Осы көпмүшенің коэффициенттері, аменs - бұл бүтін сандарq. Көпмүшелік болады циклотомдық көпмүшелік. Қашан n ол 2-ге тең [6][7]

RLWE-KEX «» өлшеміне қатысты «кіші» болып саналатын көпмүшелерді қолданады.шексіздік нормасы. «Көпмүшелік үшін шексіздік нормасы дегеніміз, коэффициенттерді бүтін сан ретінде қабылдаған кезде көпмүшенің ең үлкен коэффициентінің мәні болып табылады. З гөрі (яғни жиынтықтан {- (q − 1)/2,..., 0, ... (q - 1) / 2}). Алгоритмнің қауіпсіздігі шексіздік нормасына қатысты кішігірім кездейсоқ көпмүшелерді құру мүмкіндігіне байланысты. Бұл жай көпмүшеліктер үшін коэффициенттерді кездейсоқ құру арқылы жасаладыn-1, ..., с0) кепілдендірілген немесе өте аз болуы мүмкін. Мұны екі жалпы әдісі бар:

  1. Қолдану Бірыңғай іріктеме - кіші көпмүшенің коэффициенттері кіші коэффициенттер жиынтығынан біркелкі алынады. Келіңіздер б -дан әлдеқайда аз бүтін сан болу керек q. Егер біз кездейсоқ коэффициенттерді жиыннан таңдайтын болсақ: {-б, -B + 1, -b + 2. ... -2, -1, 0, 1, 2, ..., б − 2, б − 1, б} көпмүше (b) шекарасына қатысты аз болады. Сингх b = 5 мәнін қолдануды ұсынады.[6] Осылайша коэффициенттер жиыннан таңдалатын болады {q − 5, q − 4, q − 3, q − 2, q − 1, 0, 1, 2, 3, 4, 5 }.
  2. Қолдану Дискретті Гаусс Іріктеме - q үшін тақ мән үшін коэффициенттер кездейсоқ түрде {- (q - 1) / 2 жиынтығынан іріктеу арқылы таңдалады (q - 1) / 2} орташа 0 және үлестіру параметрі бар дискретті Гаусс үлестіріміне сәйкесσ. Сілтемелер мұны қалай жүзеге асыруға болатындығын толық сипаттайды. Бұл біркелкі іріктеуге қарағанда күрделі, бірақ алгоритмнің қауіпсіздігін дәлелдеуге мүмкіндік береді. Гаусс сынамаларына жалпы шолу Пейкерттің презентациясында келтірілген.[8]

Осы мақаланың қалған бөлігінде кездейсоқ шағын көпмүшеліктер жай ғана көрсетілген үлестірімге сәйкес іріктеліп алынады Д.. Әрі қарай q тақ мән болады, өйткені q 1 модуль 4 пен 1 ​​мод 2н сәйкес келеді. Q және n-ге арналған басқа жағдайлар «Ring-LWE криптографиясы үшін инструмент» және Сингхтің «Торлы криптографияны қолданатын Интернет үшін одан да практикалық кілттермен алмасу» бөлімінде мұқият талқыланды.[9][10] және Сингхтің тағы бір мақаласы. Желінің барлық пайдаланушылары бөлісетін тұрақты көпмүшелік, a (x). Ол криптографиялық қауіпсіз көзден детерминирленген түрде жасалады.

Берілген а(х) айтылғандай, кіші көпмүшелерді кездейсоқ таңдай аламыз с(х) және e(х) ашық кілттермен алмасуда «жеке кілт» болу. Тиісті ашық кілт көпмүшелік болады б(х) = а(х)с(х) + 2e(х).

Кілт алмасу

Кілт алмасу екі құрылғы арасында болады. (I) ретінде тағайындалған кілт алмасу үшін бастамашы және (R) ретінде тағайындалған респондент болады. Мен де, Р да білеміз q, n, а(х), және үлестіріміне сәйкес кіші көпмүшеліктерді құру мүмкіндігі бар параметрімен . Тарату Әдетте бұл сақинадағы дискретті Гаусс таралуы . Төмендегі сипаттамада кілттер алмасуының сілтеменің екі ұшында бірдей кілт пайда болатындығына байланысты ешқандай түсінік жоқ. Керісінше, ол жасалатын қадамдарды қысқаша анықтайды. Неліктен кілт алмасу бастамашы мен жауап берушінің бірдей кілтке ие болатынын толық түсіну үшін оқырман сілтеме жасаған Динг және басқалардың жұмысын қарастыруы керек.[2]

Кілт алмасу бастамашыдан (I) келесі әрекеттерді орындаудан басталады:

Бастама:

  1. Екі көпмүшені құрыңыз және үлестірімнен іріктеу арқылы шағын коэффициенттермен .
  2. Есептеу
  3. Бастамашы көпмүшені жібереді Жауап берушіге.

Жауап:

  1. Екі көпмүшені құрыңыз және үлестірімнен іріктеу арқылы шағын коэффициенттермен .
  2. Есептеу .
  3. Кішкентайын жасаңыз бастап . Есептеу . Содан кейін .
  4. Сигнал функциясын қолданыңыз табу . Бұл қолдану арқылы есептеледі әрбір коэффициенті бойынша функция
  5. Респонденттің негізгі ағыны салыстыру туралы ақпарат негізінде есептеледі және көпмүше .
  6. Респондент жібереді және бастамашыға.

Аяқтау:

  1. Қабылдау және Жауап берушіден.
  2. Үлгі бастап және есептеу .
  1. Бастамашының негізгі ағыны келесідей шығарылады салыстыру туралы ақпараттан және көпмүшелік .

Жоғарыдағы кілттермен алмасу кезінде сигнал функциясы төменде көрсетілген:

Ішкі жиынды анықтаңыз туралы . Мұнда, және сәйкесінше еден мен дөңгелектеуді бүтін санға дейін көрсетеді.

Функция толықтауышына тән қызмет болып табылады E.

:

төмендегідей анықталған қателік шарттарын жоюға арналған 2-модуль операциясы

Мәндерінің екенін ескеріңіз және шамамен тең. Осы шамамен тең мәндерді қолдана отырып, ортақ кілтті шығару үшін салыстыру функциясы қолданылады, оны сигнал функциясы деп те атайды. Бұл функция көпмүшенің әрбір коэффициенті болатын аймақты көрсетеді жылы өтірік айтады және қате терминінің дұрыс екеніне көз жеткізуге көмектеседі және әр түрлі q q операцияларына әкелмейді.

Сәйкестендіру және кілттер тізбегін құру әдістері қарастырылып отырған нақты RLWE-KEX схемасына байланысты. Кейбір әдіс модульдік арифметикаға негізделген, ал басқалары жоғары өлшемді геометрияға негізделген болуы мүмкін.[6][11]

Егер кілттермен алмасу дұрыс жұмыс істесе, бастамашының және респонденттің тізбегі бірдей болады.

Таңдалған параметрлердің ерекшеліктеріне байланысты, бұл кілт алмасу бірдей кілтті жасай алмау ықтималдығы өте аз. Кілттер алмасуының параметрлерін кілт алмасудағы сәтсіздік ықтималдығын өте аз етіп таңдау үшін таңдауға болады; анықталмаған кірпіктер немесе құрылғының істен шығуы ықтималдығынан әлдеқайда аз.

Параметрлерді таңдау

Жоғарыда ұсынылған RLWE-KEX алмасу дәрежелі көпмүшеліктер шеңберінде жұмыс істеді n - 1 немесе одан да көп модуль . Тұсаукесерде $ n $ -ның қуаты, ал $ q $ 1 (mod 2n) -ге сәйкес келетін жай сан болды. Пейкерттің мақаласында келтірілген басшылыққа сүйене отырып, Сингх RLWE-KEX үшін екі параметрлер жиынтығын ұсынды.

128 бит қауіпсіздігі үшін, n = 512, q = 25601, және

256 бит қауіпсіздігі үшін, n = 1024, q = 40961, және

Кілттер алмасу кездейсоқ іріктеуді және белгіленген шектерді қолданатындықтан, кілт алмасу бастамашы мен жауап беруші үшін бірдей кілт жасай алмау ықтималдығы аз. Егер Гаусс параметрі деп есептесек σ 8 / √ құрайды (2π) және біркелкі іріктеме байланысты (б) = 5 (Сингхті қараңыз),[6] онда келісімнің негізгі сәтсіздігінің ықтималдығы Азырақ 2−71 128-биттік қауіпсіз параметрлер үшін және Азырақ 2−91 256-биттік қауіпсіз параметрлер үшін.

Алким, Дюкас, Пёпельманн және Швабе 2015 жылдың қараша айындағы мақаласында келесі параметрлерді ұсынады n = 1024, q = 12289 және = x1024 + 1.[11] Бұл Сингхтің n = 1024 параметрлері бойынша жалпы кілт өлшемінің 70% төмендеуін білдіреді және NIST-ке ұсынылды Кванттықтан кейінгі криптографияны стандарттау атымен жоба NewHope.

Алким, Дюкас, Поппельманн мен Швабе 2015 жылдың қараша айындағы мақаласында кілттермен алмасу үшін базалық көпмүшені (жоғарыда (a)) таңдау кез-келген алмасу үшін қауіпсіз кездейсоқ сандар генераторынан кездейсоқ түрде жасалуы немесе жасалуы керек деп кеңес береді. «ештеңе жоқ» немесе NUMS техникасын қолдана отырып тексерілетін сән.[11] Осындай жолмен жасалынған параметрлердің мысалы, қарапайым санның цифрлық көрінісіне математикалық тұрақты контурының цифрларын енгізетін Internet Key Exchange (RFC 2409) қарапайым сандары болып табылады.[12] Олардың бірінші әдісі көптеген негізгі биржалардағы шабуыл шығындарының амортизациясының алдын алады, себебі Дэн Бернштейн сипаттаған NIST эллиптикалық қисықтарына қарсы жасырын шабуыл жасау мүмкіндігін қалдыру қаупі бар.[13] NUMS тәсілі амортизацияға ашық, бірақ pi және e сияқты жалпы математикалық тұрақтылар қолданылған жағдайда, әдетте Бернштейн шабуылынан аулақ болады.

Негізгі айырбас қауіпсіздігі

Бұл кілт алмасудың қауіпсіздігі оның қаттылығына негізделген қателіктермен сақиналық оқыту ең жаман жағдай шешімі сияқты қиын екендігі дәлелденген проблема ең қысқа векторлық мәселе (SVP) идеалды тор.[1][2] Берілген тор параметрлерінің практикалық қауіпсіздігін өлшеудің ең жақсы әдісі BKZ 2.0 торды азайту алгоритмі болып табылады.[14] BKZ 2.0 алгоритміне сәйкес жоғарыда келтірілген кілттермен алмасу параметрлері сәйкесінше 128 немесе 256 биттен жоғары қауіпсіздікті қамтамасыз етеді.

Іске асыру

2014 жылы Дуглас Стебила жасады патч OpenSSL 1.0.1f үшін. оның жұмысы және басқалары негізінде, «қателіктермен сақинаны оқытудан бастап TLS хаттамасына кванттық пост кілтімен алмасу» жарияланған.[15] Сингхтің жұмысын жүзеге асыратын бағдарламалық жасақтама GitHub сайтында орналасқан https://github.com/vscrypto/ringlwe.[6]

Басқа тәсілдер

Жоғарыда сипатталған тәсілдің нұсқасы Чжан, Чжан, Динг, Снук және Дагделеннің өз жұмыстарындағы түпнұсқалық расталған нұсқасы болып табылады, «Идеал торлардан кванттық аутентификацияланған кілттермен алмасу».[16] Диффи-Геллман тәрізді кілт айырбастау деп аталатынды келісу функциясы бар торларды қолданып құру тұжырымдамасын алғаш рет француз зерттеушілері Агилар, Габорит, Лахарме, Шрек және Земор PQCrypto 2010-да өз баяндамаларында «Шулы Диффи-Хеллман хаттамалары. «[17]

2015 жылдың қараша айында Альким, Дукас, Пёпельманн мен Швабе Пейкерттің алдыңғы жұмысына сүйеніп, параметрлерді ұсыну үшін торлы шабуылдардың консервативті бағасын қолданды.[11] Alkim, Ducas, Pöppelmann және Schabe жұмыстарына негізделген бағдарламалық жасақтама GitHub сайтында орналасқан. https://github.com/tpoeppelmann/newhope[11]

Сондай-ақ қараңыз


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

  1. ^ а б Регев, Одед (2005). «Торлар, қателермен оқыту, кездейсоқ сызықтық кодтар және криптография туралы». Есептеу теориясы бойынша жыл сайынғы ACM отыз жетінші симпозиумының материалдары - STOC '05. Есептеу теориясы бойынша ACM отыз жетінші жылдық симпозиумының материалдары. STOC '05. Нью-Йорк, Нью-Йорк, АҚШ: ACM. 84-93 бет. CiteSeerX  10.1.1.110.4776. дои:10.1145/1060590.1060603. ISBN  978-1-58113-960-0. S2CID  53223958.
  2. ^ а б c г. Дин, Джинтай; Сэ, Сян; Лин, Сяодун (2012). Қателіктермен оқуға негізделген қарапайым қамтамасыз етілген қауіпсіз алмасу схемасы (PDF).
  3. ^ Пейкерт, Крис (2014-01-01). «Интернетке арналған тор криптографиясы». Журналға сілтеме жасау қажет | журнал = (Көмектесіңдер)
  4. ^ Алким, Эрдем; Дукас, Лео; Поппельманн, Томас; Швабе, Питер (2015-01-01). «Кванттықтан кейінгі кілттермен алмасу - жаңа үміт». Журналға сілтеме жасау қажет | журнал = (Көмектесіңдер)
  5. ^ «Кванттықтан кейінгі криптографиямен тәжірибе жасау». Google Онлайн қауіпсіздік блогы. Алынған 2017-02-08.
  6. ^ а б c г. e f Сингх, Викрам (2015). «Торлы криптографияны қолданатын Интернетке арналған практикалық кілттермен алмасу». Журналға сілтеме жасау қажет | журнал = (Көмектесіңдер)
  7. ^ «Криптология ePrint архиві: есеп 2015/1120». eprint.iacr.org. Алынған 2015-12-23.
  8. ^ «Торларға арналған тиімді және параллель Гаусс сынамасы» (PDF). www.cc.gatech.edu. Алынған 2015-05-29.
  9. ^ Любашевский, Вадим; Пейкерт, Крис; Регев, Одед (2013). «Ring-LWE криптографиясы үшін инструмент». Журналға сілтеме жасау қажет | журнал = (Көмектесіңдер)
  10. ^ «Криптология ePrint архиві: есеп 2015/1120». eprint.iacr.org. Алынған 2016-01-17.
  11. ^ а б c г. e «Криптология ePrint архиві: есеп 2015/1092». eprint.iacr.org. Алынған 2015-11-11.
  12. ^ Д., Каррел; Д., Харкинс. «Интернет кілттерімен алмасу (IKE)». tools.ietf.org. Алынған 2017-03-16.
  13. ^ «» Жаңа үміт «торлы кілт алмасу Бернштейн BADA55 шабуылының торлы аналогына осал бола ма?». crypto.stackexchange.com. Алынған 2017-03-16.
  14. ^ Чен, Юанми; Нгуен, Фонг Q. (2011). Ли, Дун Хун; Ван, Сяоюн (ред.) BKZ 2.0: торды қауіпсіз бағалау. Информатика пәнінен дәрістер. Springer Berlin Heidelberg. 1-20 бет. дои:10.1007/978-3-642-25385-0_1. ISBN  978-3-642-25384-3.
  15. ^ Бос, Джоппе В .; Костелло, Крейг; Наериг, Майкл; Стебила, Дуглас (2014-01-01). «Қателіктер туындаған кезде сақиналық оқудан TLS хаттамасына кванттықтан кейінгі кілт алмасу». Журналға сілтеме жасау қажет | журнал = (Көмектесіңдер)
  16. ^ «Кванттықтан кейінгі әлемдегі киберқауіпсіздік туралы семинар». www.nist.gov. 2015-04-02. Алынған 2015-06-06.
  17. ^ «Шулы Диффи-Хеллман хаттамалары» (PDF). pqc2010.cased.de. Алынған 2015-06-06.