{"id":314748,"date":"2020-12-12T15:00:43","date_gmt":"2020-12-12T15:00:43","guid":{"rendered":"http:\/\/savepearlharbor.com\/?p=314748"},"modified":"-0001-11-30T00:00:00","modified_gmt":"-0001-11-29T21:00:00","slug":"","status":"publish","type":"post","link":"https:\/\/savepearlharbor.com\/?p=314748","title":{"rendered":"\u041f\u043e\u0441\u0442\u043a\u0432\u0430\u043d\u0442\u043e\u0432\u0430\u044f \u043a\u0440\u0438\u043f\u0442\u043e\u0433\u0440\u0430\u0444\u0438\u044f. \u041e\u0431\u0437\u043e\u0440 \u043f\u0440\u043e\u0442\u043e\u043a\u043e\u043b\u0430 \u0432\u044b\u0440\u0430\u0431\u043e\u0442\u043a\u0438 \u043a\u043b\u044e\u0447\u0435\u0439 NewHope"},"content":{"rendered":"\n<div class=\"post__text post__text_v2\" id=\"post-content-body\">\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/603\/c65\/120\/603c6512061b1fcd73519783b53b7773.png\" width=\"1721\" height=\"972\"><figcaption><\/figcaption><\/figure>\n<p>\u0414\u043e\u0431\u0440\u043e\u0433\u043e \u0432\u0440\u0435\u043c\u0435\u043d\u0438 \u0441\u0443\u0442\u043e\u043a!    <\/p>\n<p>\u0412 \u0441\u043e\u0432\u0440\u0435\u043c\u0435\u043d\u043d\u043e\u043c \u043c\u0438\u0440\u0435 \u0432\u0441\u0451 \u0431\u043e\u043b\u044c\u0448\u0435 \u043f\u043e\u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0437\u0430\u044f\u0432\u043b\u0435\u043d\u0438\u0439 \u043e \u043f\u043e\u0442\u0435\u043d\u0446\u0438\u0430\u043b\u044c\u043d\u043e\u0439 \u0443\u0433\u0440\u043e\u0437\u0435 \u0441\u043e \u0441\u0442\u043e\u0440\u043e\u043d\u044b \u043a\u0432\u0430\u043d\u0442\u043e\u0432\u044b\u0445 \u043a\u043e\u043c\u043f\u044c\u044e\u0442\u0435\u0440\u043e\u0432 \u043f\u043e \u043e\u0442\u043d\u043e\u0448\u0435\u043d\u0438\u044e \u043a \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u043c\u044b\u043c \u043f\u0440\u043e\u0442\u043e\u043a\u043e\u043b\u0430\u043c \u043a\u0440\u0438\u043f\u0442\u043e\u0433\u0440\u0430\u0444\u0438\u0438. \u041a\u0432\u0430\u043d\u0442\u043e\u0432\u044b\u0439 \u043a\u043e\u043c\u043f\u044c\u044e\u0442\u0435\u0440 \u0443\u0436\u0435 \u0441\u043f\u043e\u0441\u043e\u0431\u0435\u043d \u0440\u0435\u0448\u0430\u0442\u044c \u0437\u0430\u0434\u0430\u0447\u0438 \u0434\u0438\u0441\u043a\u0440\u0435\u0442\u043d\u043e\u0433\u043e \u043b\u043e\u0433\u0430\u0440\u0438\u0444\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f \u0438 \u0440\u0430\u0437\u043b\u043e\u0436\u0435\u043d\u0438\u044f \u0447\u0438\u0441\u043b\u0430 \u043d\u0430 \u043c\u043d\u043e\u0436\u0438\u0442\u0435\u043b\u0438, \u0447\u0442\u043e \u0441\u0442\u0430\u0432\u0438\u0442 \u043f\u043e\u0434 \u0443\u0433\u0440\u043e\u0437\u0443 \u0432\u0441\u0435 \u043f\u0440\u043e\u0442\u043e\u043a\u043e\u043b\u044b \u043d\u0430 \u0438\u0445 \u043e\u0441\u043d\u043e\u0432\u0435. <\/p>\n<p>\u0421\u0435\u0433\u043e\u0434\u043d\u044f \u0440\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u043f\u0440\u043e\u0442\u043e\u043a\u043e\u043b NewHope, \u0432 \u043e\u0441\u043d\u043e\u0432\u0435 \u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u043b\u0435\u0436\u0438\u0442 \u0434\u0440\u0443\u0433\u0430\u044f \u0441\u043b\u043e\u0436\u043d\u0430\u044f \u0437\u0430\u0434\u0430\u0447\u0430 &#8212; \u0437\u0430\u0434\u0430\u0447\u0430 \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u044f \u0441 \u043e\u0448\u0438\u0431\u043a\u0430\u043c\u0438 \u0432 \u043a\u043e\u043b\u044c\u0446\u0435 (Ring-LWE).<\/p>\n<p>\u041f\u0440\u043e\u0442\u043e\u043a\u043e\u043b NewHope \u2013 \u044d\u0442\u043e \u043f\u0440\u043e\u0442\u043e\u043a\u043e\u043b \u0441\u043e\u0432\u043c\u0435\u0441\u0442\u043d\u043e\u0439 \u0432\u044b\u0440\u0430\u0431\u043e\u0442\u043a\u0438 \u043a\u043b\u044e\u0447\u0430, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0431\u044b\u043b \u0440\u0430\u0437\u0440\u0430\u0431\u043e\u0442\u0430\u043d \u0441\u043f\u0435\u0446\u0438\u0430\u043b\u044c\u043d\u043e, \u0447\u0442\u043e\u0431\u044b \u043f\u0440\u043e\u0442\u0438\u0432\u043e\u0441\u0442\u043e\u044f\u0442\u044c \u0430\u0442\u0430\u043a\u0430\u043c \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u043a\u0432\u0430\u043d\u0442\u043e\u0432\u044b\u0445 \u043a\u043e\u043c\u043f\u044c\u044e\u0442\u0435\u0440\u043e\u0432. \u041f\u0440\u0435\u0436\u0434\u0435 \u0447\u0435\u043c \u043f\u0435\u0440\u0435\u0445\u043e\u0434\u0438\u0442\u044c \u043d\u0435\u043f\u043e\u0441\u0440\u0435\u0434\u0441\u0442\u0432\u0435\u043d\u043d\u043e \u043a \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0443 \u0440\u0430\u0431\u043e\u0442\u044b, \u0440\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u0437\u0430\u0434\u0430\u0447\u0438 SIS, LWE \u0438 Ring-LWE:<\/p>\n<h2>1. SIS \u043a\u0430\u043a \u0437\u0430\u0434\u0430\u0447\u0430 \u043d\u0430 \u0440\u0435\u0448\u0451\u0442\u043a\u0430\u0445<\/h2>\n<p><strong>SIS (Short integer solution problem)<\/strong> \u2013 \u0437\u0430\u0434\u0430\u0447\u0430 \u043f\u043e\u0438\u0441\u043a\u0430 \u043a\u043e\u0440\u043e\u0442\u043a\u043e\u0433\u043e \u0432\u0435\u043a\u0442\u043e\u0440\u0430 \u043d\u0430 \u0440\u0435\u0448\u0451\u0442\u043a\u0435 \u0432 \u043e\u043a\u0440\u0435\u0441\u0442\u043d\u043e\u0441\u0442\u0438 \u0442\u043e\u0447\u043a\u0438.<\/p>\n<p>\u0418\u043c\u0435\u0435\u0442\u0441\u044f \u043c\u0430\u0442\u0440\u0438\u0446\u0430 \u0410, \u0441\u0442\u043e\u043b\u0431\u0446\u044b \u043a\u043e\u0442\u043e\u0440\u043e\u0439 \u0441\u043e\u0441\u0442\u043e\u044f\u0442 \u0438\u0437 \u0446\u0435\u043b\u043e\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u044b\u0445 \u0432\u0435\u043a\u0442\u043e\u0440\u043e\u0432 \u0434\u043b\u0438\u043d\u044b n \u043f\u043e \u043c\u043e\u0434\u0443\u043b\u044e q (\u0432\u0435\u043a\u0442\u043e\u0440\u0430 \u0432\u044b\u0431\u0438\u0440\u0430\u044e\u0442\u0441\u044f \u0441\u043b\u0443\u0447\u0430\u0439\u043d\u043e):<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"A = (\\overrightarrow{a_1}, \\overrightarrow{a_2}, \\dots, \\overrightarrow{a_m}) \\in \\mathbb {Z}^{n \\times m}_q\" alt=\"A = (\\overrightarrow{a_1}, \\overrightarrow{a_2}, \\dots, \\overrightarrow{a_m}) \\in \\mathbb {Z}^{n \\times m}_q\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/3fa\/ad6\/9fe\/3faad69fe3ea75e5f1a6ac5c2494c537.svg\" width=\"202\" height=\"28\"><\/p>\n<p>\u0422\u0430\u043a\u0436\u0435 \u0432\u0432\u0435\u0434\u0435\u043c \u0441\u0438\u043c\u0432\u043e\u043b  <img decoding=\"async\" class=\"formula inline\" source=\"L^{\\perp}\" alt=\"L^{\\perp}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/f26\/a20\/3bf\/f26a203bfd9b84f6e369e4d10f01cb96.svg\">\u0438\u043b\u0438 \u0436\u0435 \u043e\u0440\u0442\u043e\u0433\u043e\u043d\u0430\u043b\u044c\u043d\u0443\u044e \u0440\u0435\u0448\u0451\u0442\u043a\u0443 \u043e\u0442 A:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"L^{\\perp}(A) = \\{ z \\in \\mathbb {Z}^m : Az = 0\\}\" alt=\"L^{\\perp}(A) = \\{ z \\in \\mathbb {Z}^m : Az = 0\\}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/452\/961\/af1\/452961af174c5ea9c1330ff106426328.svg\" width=\"198\" height=\"22\"><\/p>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/d06\/2fb\/36f\/d062fb36f3d82790c18cb6f9fb41a068.png\" width=\"1811\" height=\"1811\"><figcaption><\/figcaption><\/figure>\n<p>\u041d\u0430 \u0440\u0438\u0441\u0443\u043d\u043a\u0435 \u043f\u043e\u043a\u0430\u0437\u0430\u043d\u0430 \u0440\u0435\u0448\u0451\u0442\u043a\u0430 \u0441 \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u043c \u0431\u0430\u0437\u0438\u0441\u043e\u043c (\u043d\u0435 \u043e\u0431\u044f\u0437\u0430\u0442\u0435\u043b\u044c\u043d\u043e \u043a\u0440\u0430\u0442\u0447\u0430\u0439\u0448\u0438\u043c) \u0438 \u0432\u044b\u0434\u0435\u043b\u0435\u043d\u043d\u044b\u0439 \u043a\u0432\u0430\u0434\u0440\u0430\u0442, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0438 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0438\u0432\u0430\u0435\u0442 \u043f\u043e \u043c\u043e\u0434\u0443\u043b\u044e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u0442\u043e\u0447\u0435\u043a \u0440\u0435\u0448\u0451\u0442\u043a\u0438.<\/p>\n<p>\u0417\u0430\u0434\u0430\u0447\u0430 \u0441\u043e\u0441\u0442\u043e\u0438\u0442 \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e\u0431\u044b \u043f\u0440\u0438 \u0437\u0430\u0434\u0430\u043d\u043d\u043e\u0439 \u043c\u0430\u0442\u0440\u0438\u0446\u0435 \u0410 \u043d\u0430\u0439\u0442\u0438 \u043d\u0435\u043d\u0443\u043b\u0435\u0432\u043e\u0439 \u0432\u0435\u043a\u0442\u043e\u0440 <img decoding=\"async\" class=\"formula inline\" source=\"x \\in \\mathbb{Z}^m\" alt=\"x \\in \\mathbb{Z}^m\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/43e\/48b\/bd4\/43e48bbd4d1af10eec037ced6e5e661d.svg\">\u0440\u0435\u0448\u0451\u0442\u043a\u0435                                                   &nbsp;\u0442\u0430\u043a\u043e\u0439, \u0447\u0442\u043e <img decoding=\"async\" class=\"formula inline\" source=\"Ax=0\" alt=\"Ax=0\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/4d0\/02c\/a08\/4d002ca08b4eb102bd636ddede645400.svg\">. \u0417\u0430\u0434\u0430\u0447\u0430 \u0440\u0435\u0448\u0430\u0435\u0442\u0441\u044f \u043c\u0435\u0442\u043e\u0434\u043e\u043c \u0413\u0430\u0443\u0441\u0441\u0430 \u0438, \u043e\u0442\u0447\u0430\u0441\u0442\u0438, \u043d\u0438\u0447\u0435\u0433\u043e \u0441\u043b\u043e\u0436\u043d\u043e\u0433\u043e \u0432 \u043d\u0435\u0439 \u043d\u0435\u0442.<\/p>\n<p>\u0412\u0432\u0435\u0434\u0435\u043c \u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440 <img decoding=\"async\" class=\"formula inline\" source=\"\\beta \\ll q\" alt=\"\\beta \\ll q\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/111\/edc\/7b1\/111edc7b1abb0f1c739fe4dbd61e73d5.svg\">\u0438 \u043f\u043e\u0441\u0442\u0430\u0432\u0438\u043c \u0443\u0441\u043b\u043e\u0432\u0438\u0435, \u0447\u0442\u043e \u043c\u044b \u0438\u0449\u0435\u043c \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u043a\u043e\u0440\u043e\u0442\u043a\u0438\u0439 \u0432\u0435\u043a\u0442\u043e\u0440 z, \u0442\u0430\u043a\u043e\u0439 \u0447\u0442\u043e <img decoding=\"async\" class=\"formula inline\" source=\"||z|| \\leq \\beta \\ll q\" alt=\"||z|| \\leq \\beta \\ll q\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/c0e\/3af\/e99\/c0e3afe99a73fab7ca0bc95d0c67aa0a.svg\">. \u042d\u0442\u043e \u0443\u0441\u043b\u043e\u0432\u0438\u0435 \u0434\u043e\u043b\u0436\u043d\u043e \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0442\u044c\u0441\u044f \u0434\u043b\u044f \u043b\u044e\u0431\u043e\u0433\u043e \u043f\u043e\u043b\u043e\u0436\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0433\u043e \u0432\u0435\u043a\u0442\u043e\u0440\u0430 z (\u043e\u043d\u0438 \u0446\u0435\u043b\u043e\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u044b\u0435 \u043f\u043e \u043c\u043e\u0434\u0443\u043b\u044e q). \u0410\u043d\u0430\u043b\u043e\u0433\u0438\u0447\u043d\u043e \u0437\u0430\u0434\u0430\u0447\u0443 \u043c\u043e\u0436\u043d\u043e \u043f\u0435\u0440\u0435\u0444\u0440\u0430\u0437\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0442\u0430\u043a, \u0447\u0442\u043e \u043c\u044b \u0438\u0449\u0435\u043c \u0432\u0435\u043a\u0442\u043e\u0440, \u043f\u0440\u0438\u043d\u0430\u0434\u043b\u0435\u0436\u0430\u0449\u0438\u0439 \u043e\u043a\u0440\u0435\u0441\u0442\u043d\u043e\u0441\u0442\u0438 \u0442\u043e\u0447\u043a\u0438 \u0440\u0435\u0448\u0451\u0442\u043a\u0438. \u0422\u0430\u043a \u043a\u0430\u043a \u043c\u044b \u043c\u0430\u0442\u0440\u0438\u0446\u0443 \u0410 \u0432\u044b\u0431\u0438\u0440\u0430\u043b\u0438 \u0441\u043b\u0443\u0447\u0430\u0439\u043d\u044b\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c, \u0442\u043e \u043c\u044b \u043f\u043e\u0441\u0442\u0430\u0432\u0438\u043b\u0438 \u0437\u0430\u0434\u0430\u0447\u0443 \u0432 \u043e\u0431\u0449\u0435\u043c \u0441\u043b\u0443\u0447\u0430\u0435.<\/p>\n<p>\u041a\u0430\u043a \u043c\u043e\u0436\u043d\u043e \u0443\u0441\u043b\u043e\u0436\u043d\u0438\u0442\u044c \u0437\u0430\u0434\u0430\u0447\u0443? \u0421\u0434\u0432\u0438\u043d\u0435\u043c \u0440\u0435\u0448\u0451\u0442\u043a\u0443 \u043d\u0430 \u043d\u0435\u0431\u043e\u043b\u044c\u0448\u043e\u0435 \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0435, \u044d\u0442\u043e \u043f\u0440\u0438\u0432\u043d\u0435\u0441\u0435\u0442 \u0432 \u043d\u0435\u0435 \u0448\u0443\u043c (\u0433\u043b\u0430\u0432\u043d\u043e\u0435 \u043d\u0435 \u0441\u0434\u0432\u0438\u0433\u0430\u0442\u044c \u0441\u043b\u0438\u0448\u043a\u043e\u043c \u0441\u0438\u043b\u044c\u043d\u043e). <\/p>\n<p>\u041f\u0440\u0435\u0434\u043b\u0430\u0433\u0430\u0435\u0442\u0441\u044f \u0432\u044b\u0431\u0438\u0440\u0430\u0442\u044c \u0441\u0434\u0432\u0438\u0433 <img decoding=\"async\" class=\"formula inline\" source=\"t \\ll T\" alt=\"t \\ll T\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/33a\/a4a\/dbc\/33aa4adbc4277daa755263f618123d5c.svg\">&#8212; \u043f\u0435\u0440\u0438\u043e\u0434\u0430 \u0440\u0435\u0448\u0451\u0442\u043a\u0438. \u0418\u043d\u0430\u0447\u0435 \u0432\u043e\u0437\u043d\u0438\u043a\u043d\u0435\u0442 \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u0430 \u0441 \u0432\u043e\u0441\u0441\u0442\u0430\u043d\u043e\u0432\u043b\u0435\u043d\u0438\u0435\u043c \u0432\u0435\u043a\u0442\u043e\u0440\u0430 z.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"L_u^{\\perp}(A) = \\{z: Az=u\\} = t + L^{\\perp}(A)\" alt=\"L_u^{\\perp}(A) = \\{z: Az=u\\} = t + L^{\\perp}(A)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/51d\/d16\/858\/51dd168584d4656f3b54bff21942c06e.svg\" width=\"250\" height=\"22\"><\/p>\n<p>\u0422\u0435\u043f\u0435\u0440\u044c \u043f\u043e\u0441\u043b\u0435 \u0432\u043d\u0435\u0441\u0435\u043d\u0438\u044f \u0448\u0443\u043c\u0430, \u0438\u0441\u043a\u0430\u0442\u044c \u043a\u043e\u0440\u043e\u0442\u043a\u0438\u0439 \u0432\u0435\u043a\u0442\u043e\u0440 z \u043f\u043e \u0437\u0430\u0434\u0430\u043d\u043d\u043e\u043c\u0443 A \u0441\u0442\u0430\u043d\u043e\u0432\u0438\u0442\u0441\u044f \u043e\u0447\u0435\u043d\u044c \u0441\u043b\u043e\u0436\u043d\u043e\u0439 \u0437\u0430\u0434\u0430\u0447\u0435\u0439. <\/p>\n<p>\u0415\u0441\u043b\u0438 \u043c\u044b \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u043c \u0432 \u0435\u0432\u043a\u043b\u0438\u0434\u043e\u0432\u043e\u0439 \u043d\u043e\u0440\u043c\u0435, \u0442\u043e \u043c\u043e\u0436\u0435\u043c \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c \u0430\u0441\u0438\u043c\u043f\u0442\u043e\u0442\u0438\u0447\u0435\u0441\u043a\u0443\u044e \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u0432 <img decoding=\"async\" class=\"formula inline\" source=\"2^{\\theta(n)}\" alt=\"2^{\\theta(n)}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/3d4\/d13\/5c3\/3d4d135c3870b8add43078713fd7db75.svg\">, \u0433\u0434\u0435 n &#8212; \u0440\u0430\u0437\u043c\u0435\u0440\u043d\u043e\u0441\u0442\u044c \u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0441\u0442\u0432\u0430.<\/p>\n<h2>2. LWE ( Learning with errors)<\/h2>\n<p>\u0420\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u0437\u0430\u0434\u0430\u0447\u0443 \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u044f \u0441 \u043e\u0448\u0438\u0431\u043a\u0430\u043c\u0438:<\/p>\n<p>\u041f\u0430\u0440\u0430\u043c\u0435\u0442\u0440\u044b \u0437\u0430\u0434\u0430\u0447\u0438: <\/p>\n<p>n \u2013 \u0440\u0430\u0437\u043c\u0435\u0440\u043d\u043e\u0441\u0442\u044c \u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0441\u0442\u0432\u0430;<\/p>\n<p>q \u2013 \u0447\u0438\u0441\u043b\u043e, \u043a\u0430\u043a \u0438 \u0432 \u043f\u0440\u043e\u0448\u043b\u043e\u0439 \u0437\u0430\u0434\u0430\u0447\u0435. \u0417\u0434\u0435\u0441\u044c \u043e\u043d\u043e \u0431\u0435\u0440\u0435\u0442\u0441\u044f \u0441 \u043f\u043e\u043b\u0438\u043d\u043e\u043c\u0438\u0430\u043b\u044c\u043d\u043e\u0439 \u0437\u0430\u0432\u0438\u0441\u0438\u043c\u043e\u0441\u0442\u044c\u044e \u043e\u0442 n, \u043f\u043e\u0440\u044f\u0434\u043a\u0430 <img decoding=\"async\" class=\"formula inline\" source=\"q \\approx n^2\" alt=\"q \\approx n^2\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/f58\/495\/9a5\/f584959a5d1147406babc7825bd860be.svg\">;<\/p>\n<p>\u0410 \u0442\u0430\u043a\u0436\u0435 \u0444\u0443\u043d\u043a\u0446\u0438\u044f \u0440\u0430\u0441\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u044f \u043e\u0448\u0438\u0431\u043e\u043a <img decoding=\"async\" class=\"formula inline\" source=\"\\chi\" alt=\"\\chi\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/b6f\/f20\/a94\/b6ff20a949cc796b3a2c26c41a93a922.svg\">\u0431\u0435\u0440\u0435\u0442\u0441\u044f \u043d\u043e\u0440\u043c\u0430\u043b\u044c\u043d\u043e\u0435 \u0440\u0430\u0441\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u0435, \u0434\u043b\u044f \u043a\u0440\u0430\u0441\u0438\u0432\u044b\u0445 \u0444\u043e\u0440\u043c\u0443\u043b \u0432 \u0434\u043e\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044c\u0441\u0442\u0432\u0430\u0445);<\/p>\n<p>\u041a\u0430\u043a \u0438 \u0432 \u043f\u0440\u043e\u0448\u043b\u043e\u0439 \u0437\u0430\u0434\u0430\u0447\u0435 \u0437\u0430\u0434\u0430\u0434\u0438\u043c \u0441\u043b\u0443\u0447\u0430\u0439\u043d\u0443\u044e \u043c\u0430\u0442\u0440\u0438\u0446\u0443 <img decoding=\"async\" class=\"formula inline\" source=\"A \\in \\mathbb{Z}^{n \\times m}_q\" alt=\"A \\in \\mathbb{Z}^{n \\times m}_q\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/3b4\/4e0\/c9e\/3b44e0c9e7a85ec0cf318cdcb76ace95.svg\">\u0441\u0442\u043e\u043b\u0431\u0446\u044b \u043a\u043e\u0442\u043e\u0440\u043e\u0439 \u0432\u0435\u043a\u0442\u043e\u0440\u0430 <img decoding=\"async\" class=\"formula inline\" source=\"a_i \\in \\mathbb{Z}^n_q\" alt=\"a_i \\in \\mathbb{Z}^n_q\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/52b\/9fe\/50f\/52b9fe50f7d8b2c246d86ede3542fcba.svg\">;<\/p>\n<p>\u0418 \u0432\u0435\u043a\u0442\u043e\u0440 k, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0431\u0443\u0434\u0435\u0442 \u043e\u0442\u0432\u0435\u0447\u0430\u0442\u044c \u0437\u0430 \u0448\u0443\u043c \u0438\u0437 \u0440\u0430\u0441\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u044f <img decoding=\"async\" class=\"formula inline\" source=\"\\chi\" alt=\"\\chi\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/000\/224\/93b\/00022493b9a4c1b71e6f8a2356a478d5.svg\">.<\/p>\n<p>\u0417\u0430\u0434\u0430\u0447\u0430 \u0441\u043e\u0441\u0442\u043e\u0438\u0442 \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e \u0437\u043b\u043e\u0443\u043c\u044b\u0448\u043b\u0435\u043d\u043d\u0438\u043a\u0443 \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u043d\u0430\u0439\u0442\u0438 \u0441\u0435\u043a\u0440\u0435\u0442\u043d\u044b\u0439 \u0432\u0435\u043a\u0442\u043e\u0440 <img decoding=\"async\" class=\"formula inline\" source=\"s \\in \\mathbb{Z}^n_q\" alt=\"s \\in \\mathbb{Z}^n_q\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/339\/a6c\/d36\/339a6cd36d0e1f68f88f7a647bd8c779.svg\">, \u043a\u043e\u0433\u0434\u0430 \u0435\u043c\u0443 \u0438\u0437\u0432\u0435\u0441\u0442\u043d\u044b \u0432\u0441\u0435\u0432\u043e\u0437\u043c\u043e\u0436\u043d\u044b\u0435 \u0437\u0430\u0448\u0443\u043c\u043b\u0435\u043d\u043d\u044b\u0435 \u0441\u043a\u0430\u043b\u044f\u0440\u043d\u044b\u0435 \u043f\u0440\u043e\u0438\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u044f s \u0441 \u0432\u0435\u043a\u0442\u043e\u0440\u0430\u043c\u0438 <img decoding=\"async\" class=\"formula inline\" source=\"a_i\" alt=\"a_i\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/573\/89d\/122\/57389d1228f806f500d30394dea7d185.svg\">. (\u0412\u0441\u0435 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438 \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u044e\u0442\u0441\u044f \u043f\u043e \u043c\u043e\u0434\u0443\u043b\u044e q):<\/p>\n<p><img class=\"formula\" source=\"a_1 \\gets \\mathbb{Z}^n_q ,\\: b_1 \\approx\\: <s, a_1> \\: mod \\: q&#187; alt=&#187;a_1 \\gets \\mathbb{Z}^n_q ,\\: b_1 \\approx\\: <s, a_1> \\: mod \\: q&#187; src=&#187;https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/07e\/f95\/b54\/07ef95b542787bc2cfd760843409cf01.svg&#187; width=&#187;222&#8243; height=&#187;21&#8243;><img class=\"formula\" source=\"a_2 \\gets \\mathbb{Z}^n_q ,\\: b_2 \\approx\\: <s, a_2> \\: mod \\: q&#187; alt=&#187;a_2 \\gets \\mathbb{Z}^n_q ,\\: b_2 \\approx\\: <s, a_2> \\: mod \\: q&#187; src=&#187;https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/b2c\/8fb\/880\/b2c8fb880c920079ed105f44ae30d2c4.svg&#187; width=&#187;222&#8243; height=&#187;21&#8243;><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"\\dots\" alt=\"\\dots\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/c0a\/038\/cea\/c0a038ceae0e43e24d8ec4cf4a072d2b.svg\" width=\"19\" height=\"5\"><\/p>\n<p>\u0418\u043b\u0438 \u0442\u043e\u0447\u043d\u0435\u0435<\/p>\n<p><img class=\"formula\" source=\"b_1=<s,a_1>+k_1\\in \\mathbb{Z}_q&#187; alt=&#187;b_1=<s,a_1>+k_1\\in \\mathbb{Z}_q&#187; src=&#187;https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/ac1\/9c8\/1b9\/ac19c81b9cfb7880fd3baa2d21a1e315.svg&#187; width=&#187;167&#8243; height=&#187;19&#8243;><\/p>\n<p>\u0413\u0434\u0435 <img decoding=\"async\" class=\"formula inline\" source=\"k_1\" alt=\"k_1\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/36a\/130\/b2c\/36a130b2c4f87e386c65440632a1286a.svg\">\u043f\u0435\u0440\u0432\u0430\u044f \u043a\u043e\u043c\u043f\u043e\u043d\u0435\u043d\u0442\u0430 \u0432\u0435\u043a\u0442\u043e\u0440\u0430 <img decoding=\"async\" class=\"formula inline\" source=\"k\" alt=\"k\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/870\/941\/59f\/87094159fbe932c71a39cdb5dff7ae68.svg\">. <\/p>\n<p>\u041e\u0434\u043d\u0430\u043a\u043e \u043d\u0430\u0441 \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u0443\u0435\u0442 \u043c\u043e\u0434\u0438\u0444\u0438\u043a\u0430\u0446\u0438\u044f \u0437\u0430\u0434\u0430\u0447\u0438, \u0442\u0430\u043a \u043d\u0430\u0437\u044b\u0432\u0430\u0435\u043c\u043e\u0435 \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u0435 \u0441 \u043e\u0448\u0438\u0431\u043a\u0430\u043c\u0438 \u043d\u0430 \u0440\u0435\u0448\u0451\u0442\u043a\u0430\u0445 (LWE on lattices).<\/p>\n<p>\u0417\u0430\u0434\u0430\u0434\u0438\u043c \u0440\u0435\u0448\u0451\u0442\u043a\u0443:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"L\\left(A\\right)=\\{z\\in \\mathbb{Z}^m:z^T\\equiv s^TA\\ mod\\ q\\}=q\\left(L^\\bot\\left(A\\right)\\right)\" alt=\"L\\left(A\\right)=\\{z\\in \\mathbb{Z}^m:z^T\\equiv s^TA\\ mod\\ q\\}=q\\left(L^\\bot\\left(A\\right)\\right)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/39f\/b18\/032\/39fb1803232ac7cb825729cc87f3ab30.svg\" width=\"351\" height=\"23\"><\/p>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/d1b\/b1f\/63b\/d1bb1f63be81a87a17344f6ed412fa7a.png\" width=\"1811\" height=\"1811\"><figcaption><\/figcaption><\/figure>\n<p>\u0417\u0430\u0434\u0430\u0447\u0430 \u0443\u0436\u0435 \u043f\u043e\u0434\u043c\u0435\u043d\u044f\u0435\u0442\u0441\u044f \u0434\u0440\u0443\u0433\u043e\u0439 \u2013 \u0434\u0435\u043a\u043e\u0434\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435 \u0441 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u043d\u044b\u043c \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0435\u043c.     <\/p>\n<p>\u0417\u0430\u0434\u0430\u043d\u0430 \u0440\u0435\u0448\u0451\u0442\u043a\u0430, \u0438 \u0434\u0430\u043d\u0430 \u0442\u043e\u0447\u043a\u0430 q. \u041d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u0432 \u0435\u0451 \u043e\u043a\u0440\u0435\u0441\u0442\u043d\u043e\u0441\u0442\u0438 \u043d\u0430\u0439\u0442\u0438 \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0443\u044e \u043a \u043d\u0435\u0439 \u0442\u043e\u0447\u043a\u0443 \u0440\u0435\u0448\u0451\u0442\u043a\u0438. <\/p>\n<p>\u0422\u0430\u043a \u0436\u0435, \u043a\u0430\u043a \u0438 \u0432 \u043f\u0440\u043e\u0448\u043b\u044b\u0445 \u0437\u0430\u0434\u0430\u0447\u0430\u0445 \u0432\u043d\u043e\u0441\u0438\u043c \u0448\u0443\u043c \u0432 \u0440\u0435\u0448\u0451\u0442\u043a\u0443, \u0442\u043e\u0433\u0434\u0430 \u0437\u0430\u0434\u0430\u0447\u0430 \u043d\u0430\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u044f \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0435\u0433\u043e \u0432\u0435\u043a\u0442\u043e\u0440\u0430 \u0441\u0442\u0430\u043d\u043e\u0432\u0438\u0442\u0441\u044f \u043e\u0447\u0435\u043d\u044c \u0441\u043b\u043e\u0436\u043d\u043e\u0439:<\/p>\n<p>\u0414\u0430\u043d\u043e: <img decoding=\"async\" class=\"formula inline\" source=\"b^T\\approx v^T=s^TA\\in L(A)\\ \" alt=\"b^T\\approx v^T=s^TA\\in L(A)\\ \" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/9cb\/56c\/b8b\/9cb56cb8bfdd33cd16e8b3e4825edaa6.svg\">\u043d\u0430\u0439\u0442\u0438 <img decoding=\"async\" class=\"formula inline\" source=\"v\" alt=\"v\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/7fb\/b82\/c0f\/7fbb82c0f171ac087cf555f8de801cba.svg\">.<\/p>\n<h2>3. \u041f\u0440\u0438\u043c\u0435\u0440\u044b<\/h2>\n<p>\u0420\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u0441\u043e\u0437\u0434\u0430\u043d\u0438\u0435 \u043a\u0440\u0438\u043f\u0442\u043e\u0433\u0440\u0430\u0444\u0438\u0447\u0435\u0441\u043a\u043e\u0439 \u0441\u0438\u0441\u0442\u0435\u043c\u044b \u0441 \u043e\u0442\u043a\u0440\u044b\u0442\u044b\u043c \u043a\u043b\u044e\u0447\u043e\u043c \u043d\u0430 LWE, \u0430 \u0442\u0430\u043a\u0436\u0435 \u0445\u0435\u0448-\u0444\u0443\u043d\u043a\u0446\u0438\u044e \u043d\u0430 SIS:<\/p>\n<p><strong>Public key encryption (LWE):<\/strong><\/p>\n<p>\u0411\u043e\u0431 \u0445\u043e\u0447\u0435\u0442 \u043e\u0442\u043f\u0440\u0430\u0432\u0438\u0442\u044c \u0441\u043e\u043e\u0431\u0449\u0435\u043d\u0438\u0435 \u0410\u043b\u0438\u0441\u0435, \u0437\u0430\u0448\u0438\u0444\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0435 \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u0435\u0451 \u043e\u0442\u043a\u0440\u044b\u0442\u043e\u0433\u043e \u043a\u043b\u044e\u0447\u0430. \u0421\u043e\u043e\u0431\u0449\u0435\u043d\u0438\u0435 \u0432 \u0434\u0430\u043d\u043d\u043e\u043c \u043f\u0440\u0438\u043c\u0435\u0440\u0435 \u2013 \u0431\u0438\u0442 \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0446\u0438\u0438.<\/p>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/58a\/a94\/7d1\/58aa947d1f9bf7e76310eefb1b6cd0fe.png\" width=\"1788\" height=\"1032\"><figcaption><\/figcaption><\/figure>\n<p>\u0412 \u0434\u0430\u043d\u043d\u043e\u0439 \u0441\u0445\u0435\u043c\u0435 \u043d\u0430\u0434\u043e \u0443\u0447\u0435\u0441\u0442\u044c, \u0447\u0442\u043e \u0440\u0430\u0437\u043d\u043e\u0441\u0442\u044c \u043e\u0448\u0438\u0431\u043e\u043a <img decoding=\"async\" class=\"formula inline\" source=\"e^\\prime-ex\\ll\\ \\frac{q}{2}.\" alt=\"e^\\prime-ex\\ll\\ \\frac{q}{2}.\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/1af\/d73\/348\/1afd73348aeb6b304835210bfd8a153f.svg\"><\/p>\n<p>\u0415\u0441\u043b\u0438 \u043f\u043e\u043b\u0443\u0447\u0438\u0432\u0448\u0430\u044f\u0441\u044f \u0440\u0430\u0437\u043d\u043e\u0441\u0442\u044c \u0431\u043b\u0438\u0436\u0435 \u043a 0, \u0442\u043e \u0434\u0435\u043a\u043e\u0434\u0438\u0440\u043e\u0432\u0430\u043d 0, \u0438 \u0435\u0441\u043b\u0438 \u043a <img decoding=\"async\" class=\"formula inline\" source=\"\\frac{q}{2}\" alt=\"\\frac{q}{2}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/9f6\/8a1\/cbf\/9f68a1cbf05846dfcbf0eefceedffd3c.svg\">\u0442\u043e 1.<\/p>\n<p>\u0427\u0442\u043e \u0443 \u043d\u0430\u0441 \u0437\u043d\u0430\u0435\u0442 \u0445\u0430\u043a\u0435\u0440? <img decoding=\"async\" class=\"formula inline\" source=\"(A, u)\" alt=\"(A, u)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/bfe\/83a\/755\/bfe83a755659be7e9081d19ecbf26820.svg\"> \u0438 <img decoding=\"async\" class=\"formula inline\" source=\"(b, b\u2019)\" alt=\"(b, b\u2019)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/b4b\/33d\/1ad\/b4b33d1adaa8dabbdb165a8ca7f694ce.svg\">. \u0422\u0430\u043a \u043a\u0430\u043a \u0432 \u043d\u0438\u0445 \u0437\u0430\u043c\u0435\u0448\u0430\u043d\u043e \u0443\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u0435 \u043d\u0430 \u0441\u043b\u0443\u0447\u0430\u0439\u043d\u0443\u044e \u043c\u0430\u0442\u0440\u0438\u0446\u0443 <img decoding=\"async\" class=\"formula inline\" source=\"A\" alt=\"A\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/bef\/033\/8c8\/bef0338c8b8d451b4ec0649b3e065d72.svg\">\u0441 \u043f\u0440\u0438\u043c\u0435\u0441\u044c\u044e \u0448\u0443\u043c\u0430, \u0442\u043e \u0432\u044b\u0445\u043e\u0434\u0438\u0442, \u0447\u0442\u043e \u043d\u0430 \u0440\u0443\u043a\u0430\u0445 \u0443 \u043d\u0435\u0433\u043e 4 \u0441\u043b\u0443\u0447\u0430\u0439\u043d\u044b\u0445 \u0432\u0435\u043b\u0438\u0447\u0438\u043d\u044b, \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u0443\u0437\u043d\u0430\u0442\u044c \u0441\u043e\u043e\u0431\u0449\u0435\u043d\u0438\u0435 \u043d\u0435 \u0432\u044b\u0439\u0434\u0435\u0442.<\/p>\n<p><strong>One-way function (SIS):<\/strong><\/p>\n<p>\u041f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u0435 \u0445\u0435\u0448-\u0444\u0443\u043d\u043a\u0446\u0438\u0438 \u043f\u0440\u0435\u0434\u043b\u0430\u0433\u0430\u0435\u0442\u0441\u044f \u043e\u0441\u0443\u0449\u0435\u0441\u0442\u0432\u043b\u044f\u0442\u044c \u043f\u043e \u0441\u0445\u0435\u043c\u0435 \u041c\u0435\u0440\u043a\u043b\u0430-\u0414\u0430\u043c\u0433\u043e\u0440\u0430:<\/p>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/846\/383\/264\/84638326432aa6501b9764bbee777a58.png\" alt=\"\u041f\u0435\u0440\u0435\u0440\u0438\u0441\u043e\u0432\u0430\u043d\u043e \u0441 https:\/\/www.di.ens.fr\/chloe.hebant\/presentation\/SISproblem.pdf\" title=\"\u041f\u0435\u0440\u0435\u0440\u0438\u0441\u043e\u0432\u0430\u043d\u043e \u0441 https:\/\/www.di.ens.fr\/chloe.hebant\/presentation\/SISproblem.pdf\" width=\"1946\" height=\"483\"><figcaption>\u041f\u0435\u0440\u0435\u0440\u0438\u0441\u043e\u0432\u0430\u043d\u043e \u0441 https:\/\/www.di.ens.fr\/chloe.hebant\/presentation\/SISproblem.pdf<\/figcaption><\/figure>\n<p>\u041f\u0440\u043e\u0438\u0441\u0445\u043e\u0434\u0438\u0442 \u0440\u0430\u0437\u0431\u0438\u0435\u043d\u0438\u0435 \u0438\u0437\u043d\u0430\u0447\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u0441\u043e\u043e\u0431\u0449\u0435\u043d\u0438\u044f \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u043b\u044c\u043d\u043e\u0439 \u0434\u043b\u0438\u043d\u044b \u043d\u0430 \u0431\u043b\u043e\u043a\u0438 \u043e\u0434\u0438\u043d\u0430\u043a\u043e\u0432\u043e\u0439 \u0434\u043b\u0438\u043d\u044b, \u0430 \u0432 \u0434\u0430\u043b\u044c\u043d\u0435\u0439\u0448\u0435\u043c \u043f\u043e\u0442\u043e\u043a\u043e\u0432\u0430\u044f \u043e\u0431\u0440\u0430\u0431\u043e\u0442\u043a\u0430 \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u0444\u0443\u043d\u043a\u0446\u0438\u0438 \u0441\u0436\u0430\u0442\u0438\u044f. \u0412 \u043a\u0430\u0436\u0434\u043e\u0439 \u0438\u0442\u0435\u0440\u0430\u0446\u0438\u0438 \u043a\u043e\u043d\u0432\u0435\u0439\u0435\u0440\u0430 \u043f\u0440\u0438\u043d\u0438\u043c\u0430\u0435\u0442\u0441\u044f \u0432\u0445\u043e\u0434\u043d\u043e\u0439 \u0431\u043b\u043e\u043a \u0438 \u0431\u043b\u043e\u043a \u043e\u0442 \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0435\u0433\u043e \u0441\u043e\u043e\u0431\u0449\u0435\u043d\u0438\u044f. \u0412 \u043d\u0430\u0447\u0430\u043b\u0435 \u0432\u0441\u0435 \u0438\u043d\u0438\u0446\u0438\u0430\u043b\u0438\u0437\u0438\u0440\u0443\u0435\u0442\u0441\u044f \u0432\u0435\u043a\u0442\u043e\u0440\u043e\u043c \u0438\u043d\u0438\u0446\u0438\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438 (IV).<\/p>\n<p>\u0414\u0430\u043c\u0433\u043e\u0440 \u0438 \u041c\u0435\u0440\u043a\u043b \u043d\u0435\u0437\u0430\u0432\u0438\u0441\u0438\u043c\u043e \u043f\u043e\u043a\u0430\u0437\u0430\u043b\u0438, \u0447\u0442\u043e \u0435\u0441\u043b\u0438 <img decoding=\"async\" class=\"formula inline\" source=\"f\" alt=\"f\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/539\/259\/1d6\/5392591d69586597aa3a2f13b9b2ae0c.svg\"> \u0431\u0443\u0434\u0435\u0442 \u0443\u0441\u0442\u043e\u0439\u0447\u0438\u0432\u043e\u0439 \u043a \u043a\u043e\u043b\u043b\u0438\u0437\u0438\u044f\u043c, \u0442\u043e \u0438 <img decoding=\"async\" class=\"formula inline\" source=\"H(m)\" alt=\"H(m)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/170\/2ac\/b9e\/1702acb9e43cfab2a1e78b3122424876.svg\"> \u0431\u0443\u0434\u0435\u0442 \u0443\u0441\u0442\u043e\u0439\u0447\u0438\u0432\u0430.<\/p>\n<p>\u041d\u0430\u0448\u0430 \u0437\u0430\u0434\u0430\u0447\u0430 \u043f\u043e\u0441\u0442\u0440\u043e\u0438\u0442\u044c \u0444\u0443\u043d\u043a\u0446\u0438\u044e <img decoding=\"async\" class=\"formula inline\" source=\"f\" alt=\"f\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/c32\/cb8\/326\/c32cb83267393866713fab516df72aaa.svg\">&#8212; \u0443\u0441\u0442\u043e\u0439\u0447\u0438\u0432\u0443\u044e \u043a \u043a\u043e\u043b\u043b\u0438\u0437\u0438\u044f\u043c (One-way function):<\/p>\n<p>\u0422\u0430\u043a \u0436\u0435, \u043a\u0430\u043a \u0438 \u0440\u0430\u043d\u0435\u0435 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u043c: <\/p>\n<p><img decoding=\"async\" class=\"formula inline\" source=\"n \\in \\mathbb{N}\" alt=\"n \\in \\mathbb{N}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/f5a\/17e\/3e3\/f5a17e3e3075d3a908c0b138f9c051b1.svg\">\u0437\u0430\u0444\u0438\u043a\u0441\u0438\u0440\u0443\u0435\u043c <img decoding=\"async\" class=\"formula inline\" source=\"q = poly(n)\" alt=\"q = poly(n)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/1c7\/f1a\/082\/1c7f1a0823edb6a824a11dcd8b9420ee.svg\">\u0438 <img decoding=\"async\" class=\"formula inline\" source=\"m = m(n)\" alt=\"m = m(n)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/f19\/72e\/ca2\/f1972eca2f1c9a48da91d02ba204f63a.svg\">.<\/p>\n<p>\u041e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u043c <img decoding=\"async\" class=\"formula inline\" source=\"H_n\" alt=\"H_n\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/9ac\/44d\/3f2\/9ac44d3f2e0ea56f16ed888050a4a7ba.svg\">&#8212; \u0441\u0435\u043c\u0435\u0439\u0441\u0442\u0432\u043e \u0444\u0443\u043d\u043a\u0446\u0438\u0439 <img decoding=\"async\" class=\"formula inline\" source=\"\\{f_A\\}_{A\\in Z^{n\\times m}}\" alt=\"\\{f_A\\}_{A\\in Z^{n\\times m}}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/dd9\/7cb\/52d\/dd97cb52d886e0758b192c85192e07fa.svg\"> \u0442\u0430\u043a\u0438\u0435 \u0447\u0442\u043e <img decoding=\"async\" class=\"formula inline\" source=\"f_A:\\{0,1\\}^m\\rightarrow Z_n^m\" alt=\"f_A:\\{0,1\\}^m\\rightarrow Z_n^m\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/4ec\/6c0\/71b\/4ec6c071b70dc12ec798428c5c4ff27f.svg\"><\/p>\n<p>\u0418 \u0434\u043b\u044f \u0431\u0438\u0442\u043e\u0432\u043e\u0433\u043e \u0432\u0435\u043a\u0442\u043e\u0440\u0430 <img decoding=\"async\" class=\"formula inline\" source=\"e\\in{\\{0,1\\}}^n\" alt=\"e\\in{\\{0,1\\}}^n\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/b46\/18c\/5f5\/b4618c5f5be7d79a05bbefb2b00babbb.svg\">\u0444\u0443\u043d\u043a\u0446\u0438\u044f \u0431\u0443\u0434\u0435\u0442 \u0437\u0430\u0434\u0430\u0432\u0430\u0442\u044c\u0441\u044f \u043a\u0430\u043a: <\/p>\n<p><img class=\"formula\" source=\"f_A\\left(e\\right)=A \\times e\\>\\ mod\\>\\ q&#187; alt=&#187;f_A\\left(e\\right)=A \\times e\\>\\ mod\\>\\ q&#187; src=&#187;https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/aeb\/ed9\/41d\/aebed941dd29f3f5dec1a70674a0a246.svg&#187; width=&#187;156&#8243; height=&#187;20&#8243;><\/p>\n<p>\u041e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u0435 \u0434\u043e\u0432\u043e\u043b\u044c\u043d\u043e \u0435\u0441\u0442\u0435\u0441\u0442\u0432\u0435\u043d\u043d\u043e\u0435 \u0432 \u043a\u043e\u043d\u0442\u0435\u043a\u0441\u0442\u0435 \u0437\u0430\u0434\u0430\u0447\u0438 SIS.<\/p>\n<p>\u0427\u0442\u043e \u043d\u0430\u0441\u0447\u0435\u0442 \u043a\u043e\u043b\u043b\u0438\u0437\u0438\u0439? \u0411\u044b\u043b\u0430 \u0434\u043e\u043a\u0430\u0437\u0430\u043d\u0430 \u043b\u0435\u043c\u043c\u0430, \u0447\u0442\u043e \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u043d\u0430\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u044f \u043a\u043e\u043b\u043b\u0438\u0437\u0438\u0438 \u0432 \u0443\u043a\u0430\u0437\u0430\u043d\u043d\u043e\u0439 \u0432\u044b\u0448\u0435 \u0437\u0430\u0434\u0430\u0447\u0438 \u0441 \u0432\u0435\u0440\u043e\u044f\u0442\u043d\u043e\u0441\u0442\u044c\u044e <img decoding=\"async\" class=\"formula inline\" source=\"P\" alt=\"P\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/cdf\/4b9\/380\/cdf4b93809e8ba0cfe6dd53ce5ea918e.svg\"> \u0430\u043d\u0430\u043b\u043e\u0433\u0438\u0447\u043d\u0430 \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u0438 \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u0437\u0430\u0434\u0430\u0447\u0438 SIS \u0441 \u0442\u043e\u0439 \u0436\u0435 \u0432\u0435\u0440\u043e\u044f\u0442\u043d\u043e\u0441\u0442\u044c\u044e.<\/p>\n<h2>4. \u041f\u0440\u043e\u0431\u043b\u0435\u043c\u044b \u0441 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u0435\u043c \u044d\u0442\u0438\u0445 \u0437\u0430\u0434\u0430\u0447 \u0432 \u0440\u0435\u0430\u043b\u044c\u043d\u044b\u0445 \u043a\u0440\u0438\u043f\u0442\u043e\u0441\u0438\u0441\u0442\u0435\u043c\u0430\u0445<\/h2>\n<p>\u041f\u0440\u0438 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u0438 \u0432 \u0440\u0435\u0430\u043b\u044c\u043d\u044b\u0445 \u043a\u0440\u0438\u043f\u0442\u043e\u0441\u0438\u0441\u0442\u0435\u043c\u0430\u0445 \u0432\u043e\u0437\u043d\u0438\u043a\u0430\u0435\u0442 \u0440\u044f\u0434 \u043f\u0440\u043e\u0431\u043b\u0435\u043c:<\/p>\n<p>\u041d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e\u0441\u0442\u044c \u043f\u0435\u0440\u0435\u0441\u044b\u043b\u043a\u0438 \u043e\u0447\u0435\u043d\u044c \u0431\u043e\u043b\u044c\u0448\u043e\u0433\u043e \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0430 \u0434\u0430\u043d\u043d\u044b\u0445. \u041d\u0430 \u0441\u043b\u0430\u0439\u0434\u0435 \u043f\u0440\u0438\u0432\u0435\u0434\u0435\u043d\u0430 \u043c\u0430\u0442\u0440\u0438\u0446\u0430 <img decoding=\"async\" class=\"formula inline\" source=\"A\" alt=\"A\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/bdf\/0d6\/c92\/bdf0d6c9224392e210adc73d4d58558a.svg\"> \u0434\u043b\u044f \u0440\u0430\u0437\u043c\u0435\u0440\u043d\u043e\u0441\u0442\u0438  <img decoding=\"async\" class=\"formula inline\" source=\"640 \\times 8\" alt=\"640 \\times 8\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/ab8\/c6f\/aec\/ab8c6faece4d90caf87eff78377b0ead.svg\"> \u0438 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0435\u043c 15 \u0431\u0438\u0442 \u043d\u0430 \u0447\u0438\u0441\u043b\u043e:<\/p>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/84b\/592\/ffe\/84b592ffe5b15f7fa9979001cc7fd01e.png\" alt=\"\u0418\u0441\u0442\u043e\u0447\u043d\u0438\u043a: https:\/\/summerschool-croatia.cs.ru.nl\/2018\/\" title=\"\u0418\u0441\u0442\u043e\u0447\u043d\u0438\u043a: https:\/\/summerschool-croatia.cs.ru.nl\/2018\/\" width=\"1920\" height=\"1080\"><figcaption>\u0418\u0441\u0442\u043e\u0447\u043d\u0438\u043a: https:\/\/summerschool-croatia.cs.ru.nl\/2018\/<\/figcaption><\/figure>\n<p>2) \u0412\u0441\u0435 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438 \u0448\u0438\u0444\u0440\u043e\u0432\u0430\u043d\u0438\u044f\/\u0434\u0435\u0448\u0438\u0444\u0440\u043e\u0432\u0430\u043d\u0438\u044f \u043f\u0440\u043e\u0438\u0441\u0445\u043e\u0434\u044f\u0442 \u0441 \u0430\u0441\u0438\u043c\u043f\u0442\u043e\u0442\u0438\u0447\u0435\u0441\u043a\u043e\u0439 \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c\u044e <img decoding=\"async\" class=\"formula inline\" source=\"O(n^2)\" alt=\"O(n^2)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/55f\/d95\/81a\/55fd9581a48b40886516225f53622a9f.svg\">, \u0447\u0442\u043e \u0434\u043e\u0432\u043e\u043b\u044c\u043d\u043e \u043c\u0435\u0434\u043b\u0435\u043d\u043d\u043e.<\/p>\n<p>\u041a\u0430\u043a\u043e\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u0443 \u044d\u0442\u0438\u0445 \u043f\u0440\u043e\u0431\u043b\u0435\u043c?<\/p>\n<h2>5. Ring-LWE<\/h2>\n<p>\u041e\u0431\u0443\u0447\u0435\u043d\u0438\u0435 \u0441 \u043e\u0448\u0438\u0431\u043a\u0430\u043c\u0438 \u0432 \u043a\u043e\u043b\u044c\u0446\u0435 \u0440\u0435\u0448\u0430\u0435\u0442 \u0441\u0440\u0430\u0437\u0443 \u043e\u0431\u0435 \u0432\u044b\u0448\u0435\u043e\u043f\u0438\u0441\u0430\u043d\u043d\u044b\u0435 \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u044b.<\/p>\n<p>\u041a\u0430\u043a\u0430\u044f \u0438\u0434\u0435\u044f \u0431\u044b\u043b\u0430 \u0443 \u0441\u043e\u0437\u0434\u0430\u0442\u0435\u043b\u0435\u0439? \u0412\u0441\u043f\u043e\u043c\u043d\u0438\u043c, \u0447\u0442\u043e \u0432 LWE \u0437\u0430\u0434\u0430\u0447\u0435 \u043c\u044b \u0438\u043c\u0435\u0435\u043c \u043c\u043d\u043e\u0433\u043e \u0440\u0430\u0437\u043d\u044b\u0445 \u0441\u043a\u0430\u043b\u044f\u0440\u043d\u044b\u0445 \u043f\u0440\u043e\u0438\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u0439. \u0427\u0442\u043e \u0435\u0441\u043b\u0438 \u0437\u0430\u0434\u0430\u0442\u044c \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u044e \u0441\u043a\u0430\u043b\u044f\u0440\u043d\u043e\u0433\u043e \u043f\u0440\u043e\u0438\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u044f \u0442\u0430\u043a, \u0447\u0442\u043e\u0431\u044b \u043c\u044b \u043c\u043e\u0433\u043b\u0438 \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c n \u043f\u0441\u0435\u0432\u0434\u043e\u0441\u043b\u0443\u0447\u0430\u0439\u043d\u044b\u0445 \u0441\u043a\u0430\u043b\u044f\u0440\u043e\u0432 \u0438\u0437 \u043e\u0434\u043d\u043e\u0433\u043e?<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"\\left(\\begin{matrix}\\begin{matrix}\\vdots\\\\a_i\\\\\\end{matrix}\\\\\\vdots\\\\\\end{matrix}\\right)\\widetilde{\\ast}\\left(\\begin{matrix}\\begin{matrix}\\vdots\\\\s\\\\\\end{matrix}\\\\\\vdots\\\\\\end{matrix}\\right)+\\left(\\begin{matrix}\\begin{matrix}\\vdots\\\\e_i\\\\\\end{matrix}\\\\\\vdots\\\\\\end{matrix}\\right)=\\left(\\begin{matrix}\\begin{matrix}\\vdots\\\\b_i\\\\\\end{matrix}\\\\\\vdots\\\\\\end{matrix}\\right)\\in \\mathbb{Z}_q^n\" alt=\"\\left(\\begin{matrix}\\begin{matrix}\\vdots\\\\a_i\\\\\\end{matrix}\\\\\\vdots\\\\\\end{matrix}\\right)\\widetilde{\\ast}\\left(\\begin{matrix}\\begin{matrix}\\vdots\\\\s\\\\\\end{matrix}\\\\\\vdots\\\\\\end{matrix}\\right)+\\left(\\begin{matrix}\\begin{matrix}\\vdots\\\\e_i\\\\\\end{matrix}\\\\\\vdots\\\\\\end{matrix}\\right)=\\left(\\begin{matrix}\\begin{matrix}\\vdots\\\\b_i\\\\\\end{matrix}\\\\\\vdots\\\\\\end{matrix}\\right)\\in \\mathbb{Z}_q^n\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/cda\/709\/2e1\/cda7092e17f70d4e29fb1a8c5fdb7099.svg\" width=\"298\" height=\"81\"><\/p>\n<p>\u041a\u0430\u043a \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u0442\u044c \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u044e <img decoding=\"async\" class=\"formula inline\" source=\"\\widetilde{\\ast}\" alt=\"\\widetilde{\\ast}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/499\/08f\/e8d\/49908fe8de72a2acff7e741fffe6d0f2.svg\">?<\/p>\n<p>\u041d\u0430\u0438\u043b\u0443\u0447\u0448\u0438\u0439 \u0441\u043f\u043e\u0441\u043e\u0431 \u2013 \u0443\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u0435 \u0432 \u043a\u043e\u043b\u044c\u0446\u0435 \u043c\u043d\u043e\u0433\u043e\u0447\u043b\u0435\u043d\u043e\u0432 <img decoding=\"async\" class=\"formula inline\" source=\"R_q=R\/qR\" alt=\"R_q=R\/qR\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/b24\/7e6\/494\/b247e6494173af1d0d3c1e68c164b291.svg\">, \u0433\u0434\u0435 <img decoding=\"async\" class=\"formula inline\" source=\"R = \\mathbb{Z}_q\\left[X\\right]\/\\left(X^n+1\\right)\" alt=\"R = \\mathbb{Z}_q\\left[X\\right]\/\\left(X^n+1\\right)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/c6f\/fdd\/565\/c6ffdd5653f9b15012335b3e2d643a57.svg\">, n \u2013 \u0441\u0442\u0435\u043f\u0435\u043d\u044c \u0434\u0432\u043e\u0439\u043a\u0438. <\/p>\n<p>\u042d\u043b\u0435\u043c\u0435\u043d\u0442\u044b <img decoding=\"async\" class=\"formula inline\" source=\"R_q\" alt=\"R_q\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/289\/02a\/366\/28902a366b0780c83fc89a3412d79057.svg\">\u0438\u043c\u0435\u044e\u0442 \u0441\u0442\u0435\u043f\u0435\u043d\u044c <img decoding=\"async\" class=\"formula inline\" source=\"{deg(R}_q)<n\" alt=\"{deg(R}_q)<n\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/cd0\/dd8\/eb2\/cd0dd8eb241391eb30a6d89d92a10d5b.svg\">c \u043a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442\u0430\u043c\u0438 \u043f\u043e \u043c\u043e\u0434\u0443\u043b\u044e q.<\/p>\n<p>\u041f\u043e\u0447\u0435\u043c\u0443 \u0438\u043c\u0435\u043d\u043d\u043e \u0442\u0430\u043a\u043e\u0439 \u0441\u043f\u043e\u0441\u043e\u0431? \u041d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e\u0441\u0442\u044c \u043f\u0435\u0440\u0435\u0434\u0430\u0432\u0430\u0442\u044c \u0431\u043e\u043b\u044c\u0448\u0438\u0435 \u043c\u0430\u0442\u0440\u0438\u0446\u044b \u043e\u0442\u043f\u0430\u0434\u0430\u0435\u0442. \u0412 \u0441\u0430\u043c\u043e\u043c \u0434\u0435\u043b\u0435, \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u043f\u0435\u0440\u0435\u0434\u0430\u0442\u044c \u043e\u0434\u0438\u043d \u043f\u043e\u043b\u0438\u043d\u043e\u043c, \u043e\u0441\u0442\u0430\u043b\u044c\u043d\u044b\u0435 \u043c\u043e\u0436\u043d\u043e \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c \u0446\u0438\u043a\u043b\u0438\u0447\u0435\u0441\u043a\u0438\u043c \u0441\u0434\u0432\u0438\u0433\u043e\u043c \u043f\u043e \u043f\u0440\u0430\u0432\u0438\u043b\u0443: <img decoding=\"async\" class=\"formula inline\" source=\"x\\ \\rightarrow\\ -x\\ mod\\ q\" alt=\"x\\ \\rightarrow\\ -x\\ mod\\ q\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/e65\/a4a\/394\/e65a4a394c463b4fa06f06045caffd7f.svg\">. \u0412 \u0438\u0442\u043e\u0433\u0435 \u043f\u043e\u043b\u0443\u0447\u0430\u0435\u043c \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u0441\u043b\u0443\u0447\u0430\u0439\u043d\u0443\u044e \u043c\u0430\u0442\u0440\u0438\u0446\u0443.<\/p>\n<p>\u0427\u0442\u043e \u043d\u0430\u0441\u0447\u0435\u0442 \u0448\u0438\u0444\u0440\u043e\u0432\u0430\u043d\u0438\u044f\/\u0434\u0435\u0448\u0438\u0444\u0440\u043e\u0432\u0430\u043d\u0438\u044f? \u0421 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u0431\u044b\u0441\u0442\u0440\u043e\u0433\u043e \u043f\u0440\u0435\u043e\u0431\u0440\u0430\u0437\u043e\u0432\u0430\u043d\u0438\u044f \u0424\u0443\u0440\u044c\u0435, \u043c\u043e\u0436\u043d\u043e \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c \u043f\u0435\u0440\u0435\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u0435 2 \u043f\u043e\u043b\u0438\u043d\u043e\u043c\u043e\u0432 \u0437\u0430 <img decoding=\"async\" class=\"formula inline\" source=\"O\\left(n\\ logn\\right)\" alt=\"O\\left(n\\ logn\\right)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/21a\/593\/687\/21a593687236c7ad79c570f9f8f1624e.svg\">, \u0447\u0442\u043e \u0437\u043d\u0430\u0447\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u0431\u044b\u0441\u0442\u0440\u0435\u0435 <img decoding=\"async\" class=\"formula inline\" source=\"O\\left(n^2\\right).\" alt=\"O\\left(n^2\\right).\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/eb4\/a3c\/244\/eb4a3c2449bceccc7700c5102e805029.svg\"><\/p>\n<p>\u0417\u0430\u0434\u0430\u0447\u0430 \u043f\u043e\u043b\u0443\u0447\u0430\u0435\u0442\u0441\u044f \u0430\u043d\u0430\u043b\u043e\u0433\u0438\u0447\u043d\u043e\u0439 LWE \u0437\u0430 \u0438\u0441\u043a\u043b\u044e\u0447\u0435\u043d\u0438\u0435\u043c \u0442\u043e\u0433\u043e, \u0447\u0442\u043e <img decoding=\"async\" class=\"formula inline\" source=\"a_i, s, k\" alt=\"a_i, s, k\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/965\/0b3\/d6d\/9650b3d6d16157ba91d74454008b67b7.svg\">\u0443\u0436\u0435 \u044f\u0432\u043b\u044f\u044e\u0442\u0441\u044f \u043f\u043e\u043b\u0438\u043d\u043e\u043c\u0430\u043c\u0438, \u0430 \u043d\u0435 \u043f\u0440\u043e\u0441\u0442\u043e \u0432\u0435\u043a\u0442\u043e\u0440\u0430\u043c\u0438. <\/p>\n<h2>6. \u041f\u0440\u043e\u0442\u043e\u043a\u043e\u043b NewHope<\/h2>\n<p>\u0415\u0441\u043b\u0438 \u043a\u0440\u0430\u0442\u043a\u043e \u0433\u043e\u0432\u043e\u0440\u0438\u0442\u044c, \u0442\u043e \u043f\u0440\u043e\u0442\u043e\u043a\u043e\u043b NewHope \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043c\u043e\u0434\u0438\u0444\u0438\u043a\u0430\u0446\u0438\u0435\u0439 \u043f\u0440\u043e\u0442\u043e\u043a\u043e\u043b\u0430 \u043e\u0431\u043c\u0435\u043d\u0430 \u043a\u043b\u044e\u0447\u0430\u043c\u0438, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u043e\u043f\u0438\u0441\u0430\u043b\u0438 \u0432 \u0441\u0432\u043e\u0435\u0439 \u0441\u0442\u0430\u0442\u044c\u0435 Bos, Castello, Naehrig \u0438 Stebila. \u041e\u043d\u0438 \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u043b\u0438 \u043e\u0431\u043c\u0435\u043d \u043a\u043b\u044e\u0447\u0430\u043c\u0438 \u0432 TLS \u0438\u0437 Ring-LWE.<\/p>\n<p>\u042f \u043d\u0435 \u0431\u0443\u0434\u0443 \u043f\u0440\u0438\u0432\u043e\u0434\u0438\u0442\u044c \u0434\u0435\u0442\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u044f \u0438\u0437\u043c\u0435\u043d\u0435\u043d\u0438\u0439 \u043c\u0435\u0436\u0434\u0443 \u044d\u0442\u0438\u043c\u0438 \u043f\u0440\u043e\u0442\u043e\u043a\u043e\u043b\u0430\u043c\u0438, \u0430 \u043e\u043f\u0438\u0448\u0443 \u043e\u0431\u0449\u0438\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0440\u0430\u0431\u043e\u0442\u044b \u0438 \u043c\u043e\u0442\u0438\u0432\u0430\u0446\u0438\u044e \u0432 \u0432\u044b\u0431\u043e\u0440\u0435 \u0442\u0435\u0445 \u0438\u043b\u0438 \u0438\u043d\u044b\u0445 \u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440\u043e\u0432 \u0432 \u043f\u0440\u043e\u0442\u043e\u043a\u043e\u043b\u0435 NewHope.<\/p>\n<p>\u0412 \u0434\u0430\u043d\u043d\u043e\u0439 \u0441\u0445\u0435\u043c\u0435 \u044f \u0431\u0443\u0434\u0443 \u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c\u0441\u044f \u043e\u0431\u043e\u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f\u043c\u0438, \u0432\u0432\u0435\u0434\u0451\u043d\u043d\u044b\u043c\u0438 \u0430\u0432\u0442\u043e\u0440\u0430\u043c\u0438 \u0441\u0442\u0430\u0442\u044c\u0438.<\/p>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/ea4\/1ca\/1b0\/ea41ca1b0484a84f9ac6aaff443432f2.png\" width=\"2360\" height=\"2248\"><figcaption><\/figcaption><\/figure>\n<p>\u0420\u0430\u0437\u0431\u0435\u0440\u0451\u043c \u0441\u0442\u0430\u0434\u0438\u0438 \u0438 \u0444\u0443\u043d\u043a\u0446\u0438\u0438 \u043f\u043e\u0434\u0440\u043e\u0431\u043d\u0435\u0435:<\/p>\n<p>\u0417\u0434\u0435\u0441\u044c \u0410\u043b\u0438\u0441\u0430 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0441\u0435\u0440\u0432\u0435\u0440\u043e\u043c, \u0430 \u0411\u043e\u0431 \u043a\u043b\u0438\u0435\u043d\u0442\u043e\u043c.<\/p>\n<ol>\n<li>\n<p>\u0412 \u043a\u0430\u0447\u0435\u0441\u0442\u0432\u0435 \u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440\u043e\u0432 \u0441\u0438\u0441\u0442\u0435\u043c\u044b n = 1024, q = 12289 (\u043d\u0430\u0438\u043c\u0435\u043d\u044c\u0448\u0435\u0435 \u043f\u0440\u043e\u0441\u0442\u043e\u0435, \u0434\u043b\u044f \u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e <img decoding=\"async\" class=\"formula inline\" source=\"q\\equiv1\\ mod\\ 2n\" alt=\"q\\equiv1\\ mod\\ 2n\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/187\/d16\/b86\/187d16b868149ea9c6ce5ba43a96d3e7.svg\">). \u042d\u0442\u043e \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u0434\u043b\u044f \u0431\u044b\u0441\u0442\u0440\u043e\u0439 \u0440\u0430\u0431\u043e\u0442\u044b NTT (\u0432\u0430\u0440\u0438\u0430\u0446\u0438\u044f \u0434\u0438\u0441\u043a\u0440\u0435\u0442\u043d\u043e\u0433\u043e \u043f\u0440\u0435\u043e\u0431\u0440\u0430\u0437\u043e\u0432\u0430\u043d\u0438\u044f \u0424\u0443\u0440\u044c\u0435 \u0434\u043b\u044f \u043f\u043e\u043b\u0438\u043d\u043e\u043c\u043e\u0432), \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0442\u0440\u0435\u0431\u0443\u0435\u0442 n \u2013 \u0441\u0442\u0435\u043f\u0435\u043d\u0438 \u0434\u0432\u043e\u0439\u043a\u0438, q \u2013 \u043f\u0440\u043e\u0441\u0442\u043e\u0435 \u0447\u0438\u0441\u043b\u043e, \u043a\u043e\u0442\u043e\u0440\u043e\u0435 \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u0435\u0442 \u0443\u043a\u0430\u0437\u0430\u043d\u043d\u043e\u043c\u0443 \u0432\u044b\u0448\u0435 \u0442\u0440\u0435\u0431\u043e\u0432\u0430\u043d\u0438\u044e. \u0418\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442\u0441\u044f \u0440\u0435\u0448\u0451\u0442\u043a\u0430 <img class=\"formula inline\" source=\"D_4.\" alt=\"D_4.\"><\/p>\n<\/li>\n<li>\n<p>\u0412 \u043d\u0430\u0447\u0430\u043b\u0435 \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u0441\u0433\u0435\u043d\u0435\u0440\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0441\u043b\u0443\u0447\u0430\u0439\u043d\u044b\u0439 \u043f\u043e\u043b\u0438\u043d\u043e\u043c <strong>a<\/strong>. \u041f\u0440\u043e\u0438\u0441\u0445\u043e\u0434\u0438\u0442 \u044d\u0442\u043e \u0442\u0430\u043a: \u0433\u0435\u043d\u0435\u0440\u0438\u0440\u0443\u0435\u0442\u0441\u044f seed \u2013 \u043f\u0441\u0435\u0432\u0434\u043e\u0441\u043b\u0443\u0447\u0430\u0439\u043d\u043e\u0435 \u0447\u0438\u0441\u043b\u043e \u0434\u043b\u0438\u043d\u043e\u0439 256 \u0431\u0438\u0442, \u0434\u0430\u043b\u0435\u0435 \u044d\u0442\u043e \u0447\u0438\u0441\u043b\u043e \u043f\u0440\u043e\u043f\u0443\u0441\u043a\u0430\u0435\u0442\u0441\u044f \u0447\u0435\u0440\u0435\u0437 \u0444\u0443\u043d\u043a\u0446\u0438\u044e SHAKE-128 (\u0432 \u0440\u0430\u0431\u043e\u0442\u0435 \u0430\u0432\u0442\u043e\u0440\u043e\u0432 \u0432 \u043a\u0430\u0447\u0435\u0441\u0442\u0432\u0435 \u0434\u0430\u043d\u043d\u043e\u0439 \u0444\u0443\u043d\u043a\u0446\u0438\u0438 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442\u0441\u044f SHA3). &nbsp;\u0417\u0430\u0442\u0435\u043c \u043d\u0430\u0447\u0438\u043d\u0430\u0435\u0442 \u0440\u0430\u0431\u043e\u0442\u0430\u0442\u044c \u043f\u0430\u0440\u0441\u0435\u0440, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0432\u044b\u0431\u0435\u0440\u0435\u0442 1024 \u043a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442\u0430 \u0432 \u043f\u043e\u043b\u0438\u043d\u043e\u043c <strong>a<\/strong>. \u041d\u0435\u0431\u043e\u043b\u044c\u0448\u0430\u044f \u0440\u0435\u043c\u0430\u0440\u043a\u0430: \u043d\u0435\u0441\u043c\u043e\u0442\u0440\u044f \u043d\u0430 \u0442\u043e, \u0447\u0442\u043e TLS \u0438\u043c\u0435\u0435\u0442 \u043a\u044d\u0448\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435 \u043a\u043b\u044e\u0447\u0435\u0439 \u043d\u0430 \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u043e\u0435 \u0432\u0440\u0435\u043c\u044f (\u0432 \u0440\u0430\u0439\u043e\u043d\u0435 2 \u0447\u0430\u0441\u043e\u0432), \u0430\u0432\u0442\u043e\u0440\u044b \u043f\u0440\u043e\u0442\u043e\u043a\u043e\u043b\u0430 NewHope \u0432\u044b\u0441\u0442\u0443\u043f\u0438\u043b\u0438 \u043f\u0440\u043e\u0442\u0438\u0432 \u044d\u0442\u043e\u0433\u043e, \u0438 \u043f\u043e \u0443\u043c\u043e\u043b\u0447\u0430\u043d\u0438\u044e \u0434\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u043d\u043e\u0432\u043e\u0433\u043e \u0441\u043e\u0435\u0434\u0438\u043d\u0435\u043d\u0438\u044f \u0433\u0435\u043d\u0435\u0440\u0438\u0440\u0443\u0435\u0442\u0441\u044f \u0441\u0432\u043e\u0439 \u043f\u043e\u043b\u0438\u043d\u043e\u043c <strong>a<\/strong>. \u041f\u043e \u0438\u0445 \u043c\u043d\u0435\u043d\u0438\u044e, \u044d\u0442\u043e \u0443\u043c\u0435\u043d\u044c\u0448\u0430\u0435\u0442 \u0448\u0430\u043d\u0441 \u043d\u0430 backdoor \u0438 \u0432\u043e\u0437\u043d\u0438\u043a\u043d\u043e\u0432\u0435\u043d\u0438\u044f \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u044b, \u0447\u0442\u043e \u0432\u0441\u0435 \u0441\u043e\u0435\u0434\u0438\u043d\u0435\u043d\u0438\u044f \u0431\u0443\u0434\u0443\u0442 \u043f\u043e\u043b\u0430\u0433\u0430\u0442\u044c\u0441\u044f \u043d\u0430 \u0435\u0434\u0438\u043d\u0441\u0442\u0432\u0435\u043d\u043d\u044b\u0439 \u201c\u044d\u043a\u0437\u0435\u043c\u043f\u043b\u044f\u0440\u201d \u0437\u0430\u0434\u0430\u0447\u0438 \u0432 \u0440\u0435\u0448\u0451\u0442\u043a\u0430\u0445.<\/p>\n<\/li>\n<li>\n<p>\u0424\u0443\u043d\u043a\u0446\u0438\u044f \u0440\u0430\u0441\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u0435 \u043e\u0448\u0438\u0431\u043e\u043a \u2013 \u0431\u0438\u043d\u043e\u043c\u0438\u043d\u0430\u043b\u044c\u043d\u043e\u0435, \u0446\u0435\u043d\u0442\u0440\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0435. \u042d\u0442\u043e \u0441\u0434\u0435\u043b\u0430\u043d\u043e \u0438\u0437-\u0437\u0430 \u0442\u043e\u0433\u043e, \u0447\u0442\u043e \u043c\u043e\u0434\u0435\u043b\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u043d\u043e\u0440\u043c\u0430\u043b\u044c\u043d\u043e\u0435 \u0440\u0430\u0441\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u0435 \u0434\u043e\u0432\u043e\u043b\u044c\u043d\u043e \u0437\u0430\u0442\u0440\u0430\u0442\u043d\u043e \u0438 \u043d\u0435 \u043d\u0443\u0436\u043d\u043e \u0445\u0440\u0430\u043d\u0438\u0442\u044c \u0442\u0430\u0431\u043b\u0438\u0446\u044b \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u044b\u0445 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439 (\u0447\u0442\u043e \u0438\u0441\u043a\u043b\u044e\u0447\u0430\u0435\u0442 \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0442\u0438\u043f\u044b \u0430\u0442\u0430\u043a). \u0417\u0434\u0435\u0441\u044c \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d \u043f\u0441\u0435\u0432\u0434\u043e\u0441\u043b\u0443\u0447\u0430\u0439\u043d\u044b\u0439 \u0433\u0435\u043d\u0435\u0440\u0430\u0442\u043e\u0440 \u0441 seed \u0438\u0437 \/dev\/urandom \u0441 \u043f\u043e\u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u043c \u0431\u044b\u0441\u0442\u0440\u044b\u043c \u0441\u0443\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435\u043c 16-\u0431\u0438\u0442\u043e\u0432\u044b\u0445 \u0431\u043b\u043e\u043a\u043e\u0432 \u0432\u044b\u0432\u043e\u0434\u0430. \u0412\u044b\u0431\u043e\u0440\u043a\u043e\u0439 \u0438\u0437 \u043d\u0435\u0435 \u043f\u043e\u043b\u0443\u0447\u0430\u0435\u043c \u043a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442\u044b \u0434\u043b\u044f \u0441\u0435\u043a\u0440\u0435\u0442\u043d\u043e\u0433\u043e \u043f\u043e\u043b\u0438\u043d\u043e\u043c\u0430 s \u0438 \u043f\u043e\u043b\u0438\u043d\u043e\u043c\u0430 \u043e\u0448\u0438\u0431\u043e\u043a e.<\/p>\n<\/li>\n<li>\n<p>\u041f\u0435\u0440\u0435\u0441\u044b\u043b\u0430\u0435\u0442\u0441\u044f \u043f\u0430\u0440\u0430 (\u043e\u0442\u043a\u0440\u044b\u0442\u044b\u0439 \u043a\u043b\u044e\u0447 b, seed).<\/p>\n<\/li>\n<li>\n<p>\u041d\u0430 \u0441\u0442\u043e\u0440\u043e\u043d\u0435 \u043a\u043b\u0438\u0435\u043d\u0442\u0430 \u0442\u0430\u043a\u0436\u0435 \u0433\u0435\u043d\u0435\u0440\u0438\u0440\u0443\u0435\u0442\u0441\u044f \u043f\u043e\u043b\u0438\u043d\u043e\u043c a, \u043f\u043e\u043b\u0438\u043d\u043e\u043c\u044b s\u2019, e\u2019, e\u201d, \u0432\u044b\u0447\u0438\u0441\u043b\u044f\u0435\u0442\u0441\u044f \u043e\u0442\u043a\u0440\u044b\u0442\u044b\u0439 \u043a\u043b\u044e\u0447 u.<\/p>\n<\/li>\n<li>\n<p>\u0414\u0430\u043b\u044c\u0448\u0435 \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c \u043f\u043e\u043b\u0438\u043d\u043e\u043c v, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0434\u043e\u043b\u0436\u0435\u043d \u0431\u044b\u0442\u044c \u043e\u0434\u0438\u043d\u0430\u043a\u043e\u0432\u044b\u043c \u0438 \u0434\u043b\u044f \u043a\u043b\u0438\u0435\u043d\u0442\u0430, \u0438 \u0434\u043b\u044f \u0441\u0435\u0440\u0432\u0435\u0440\u0430. \u041e\u0434\u043d\u0430\u043a\u043e \u0441 \u044d\u0442\u0438\u043c \u0432\u043e\u0437\u043d\u0438\u043a\u0430\u044e\u0442 \u0442\u0440\u0443\u0434\u043d\u043e\u0441\u0442\u0438. \u041d\u0430 \u0441\u0442\u043e\u0440\u043e\u043d\u0435 \u043a\u043b\u0438\u0435\u043d\u0442\u0430 \u043f\u043e\u043b\u0443\u0447\u0430\u0435\u0442\u0441\u044f <img decoding=\"async\" class=\"formula inline\" source=\"v = bs\u2019+e\u201d = ass\u2019+es\u2019+e\u201d\" alt=\"v = bs\u2019+e\u201d = ass\u2019+es\u2019+e\u201d\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/838\/57e\/d79\/83857ed794c50a942054dbbbb4a4db50.svg\">, \u043d\u0430 \u0441\u0442\u043e\u0440\u043e\u043d\u0435 \u0441\u0435\u0440\u0432\u0435\u0440\u0430 <img decoding=\"async\" class=\"formula inline\" source=\"v'= us = ass\u2019+e\u2019s\" alt=\"v'= us = ass\u2019+e\u2019s\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/4a6\/873\/d1c\/4a6873d1ca936036a75baf8f6e9d33ec.svg\">, \u0432 \u0438\u0442\u043e\u0433\u0435 \u043d\u0430\u043a\u0430\u043f\u043b\u0438\u0432\u0430\u0435\u0442\u0441\u044f \u043f\u043e\u0433\u0440\u0435\u0448\u043d\u043e\u0441\u0442\u044c \u043c\u0435\u0436\u0434\u0443 \u043f\u043e\u043b\u0438\u043d\u043e\u043c\u0430\u043c\u0438, \u043a\u043e\u0442\u043e\u0440\u0443\u044e \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u0438\u0441\u043f\u0440\u0430\u0432\u0438\u0442\u044c. \u0415\u0441\u043b\u0438 \u043f\u043e\u043c\u043d\u0438\u0442\u0435, \u0440\u0430\u0437\u043b\u0438\u0447\u0435\u043d\u0438\u0435 \u043f\u0435\u0440\u0435\u0434\u0430\u043d\u043d\u043e\u0433\u043e \u0431\u0438\u0442\u0430 \u2013 \u044d\u0442\u043e \u0442\u043e, \u043d\u0430\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u0431\u043b\u0438\u0437\u043a\u043e \u043a 0 \u0438\u043b\u0438 <img decoding=\"async\" class=\"formula inline\" source=\"\\frac{q}{2}\" alt=\"\\frac{q}{2}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/b9c\/1c1\/827\/b9c1c182792035677069a3a8f375a0d8.svg\">. \u0421\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0435\u043d\u043d\u043e, \u0431\u043e\u043b\u044c\u0448\u0430\u044f \u043f\u043e\u0433\u0440\u0435\u0448\u043d\u043e\u0441\u0442\u044c \u043c\u043e\u0436\u0435\u0442 \u043f\u0440\u0438\u0432\u0435\u0441\u0442\u0438 \u043a \u0438\u0441\u043a\u0430\u0436\u0435\u043d\u0438\u044e \u0441\u043e\u043e\u0431\u0449\u0435\u043d\u0438\u044f. <\/p>\n<\/li>\n<li>\n<p>\u0412\u044b\u043f\u043e\u043b\u043d\u0438\u043c \u043a\u043e\u0440\u0440\u0435\u043a\u0446\u0438\u044e \u043e\u0448\u0438\u0431\u043a\u0438. \u0414\u043b\u044f \u043d\u0430\u0447\u0430\u043b\u0430 \u0432\u0435\u0440\u043d\u0435\u043c\u0441\u044f \u043e\u0442 \u043f\u043e\u043b\u0438\u043d\u043e\u043c\u043e\u0432 \u043a \u0432\u0435\u043a\u0442\u043e\u0440\u0430\u043c: \u043a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442\u044b \u043f\u043e\u043b\u0438\u043d\u043e\u043c\u0430 \u0431\u0443\u0434\u0443\u0442 \u043a\u043e\u043e\u0440\u0434\u0438\u043d\u0430\u0442\u0430\u043c\u0438 \u0432\u0435\u043a\u0442\u043e\u0440\u0430. \u0420\u0430\u0437\u0434\u0435\u043b\u0438\u043c \u0438\u0445 \u043d\u0430 q \u0438 \u0442\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c, \u043e\u0442\u043e\u0431\u0440\u0430\u0437\u0438\u043c \u0438\u0445 \u043d\u0430 <img decoding=\"async\" class=\"formula inline\" source=\"\\left[0,1\\right)\" alt=\"\\left[0,1\\right)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/bb6\/f84\/12d\/bb6f8412d9ee92c125edad11944a8a1e.svg\">. \u0422\u0430\u043a \u043a\u0430\u043a \u043c\u044b \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u043c \u0432 \u0440\u0435\u0448\u0451\u0442\u043a\u0435 <img decoding=\"async\" class=\"formula inline\" source=\"D_4\" alt=\"D_4\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/870\/8ed\/93e\/8708ed93e526d07ddeb60187e4d31f92.svg\">\u0442\u043e \u0434\u043b\u044f \u043f\u0440\u0438\u043c\u0435\u0440\u043e\u0432 \u043f\u0435\u0440\u0435\u0439\u0434\u0435\u043c \u0432 <img decoding=\"async\" class=\"formula inline\" source=\"D_2\" alt=\"D_2\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/1e8\/7a3\/6d8\/1e87a36d8d6b70f41657509faab20e89.svg\">(\u0432 \u0447\u0435\u0442\u044b\u0440\u0451\u0445\u043c\u0435\u0440\u043d\u043e\u043c \u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0441\u0442\u0432\u0435 \u0440\u0438\u0441\u043e\u0432\u0430\u0442\u044c \u0442\u044f\u0436\u0435\u043b\u043e). \u0414\u043b\u044f \u043d\u0430\u0447\u0430\u043b\u0430 \u043d\u0435\u043c\u043d\u043e\u0433\u043e \u0438\u0437\u043c\u0435\u043d\u0438\u043c \u043d\u0430\u0448\u0443 \u0440\u0435\u0448\u0435\u0442\u043a\u0443 \u0438 \u043f\u0435\u0440\u0435\u0439\u0434\u0435\u043c \u043a \u0431\u0430\u0437\u0438\u0441\u0443 <img decoding=\"async\" class=\"formula inline\" source=\"\\{ \\left(0,\\ 1\\right),\\left(1\/2,\\ 1\/2\\right) \\}\" alt=\"\\{ \\left(0,\\ 1\\right),\\left(1\/2,\\ 1\/2\\right) \\}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/6bd\/1a2\/a79\/6bd1a2a79edc32f1657487e36e94302d.svg\">. \u041d\u0430 \u0434\u0432\u0443\u043c\u0435\u0440\u043d\u043e\u0439 \u0440\u0435\u0448\u0451\u0442\u043a\u0435 \u043d\u0443\u0436\u043d\u043e \u043d\u0430\u0440\u0438\u0441\u043e\u0432\u0430\u0442\u044c \u0434\u0438\u0430\u0433\u0440\u0430\u043c\u043c\u0443 \u0412\u043e\u0440\u043e\u043d\u043e\u0433\u043e. <\/p>\n<\/li>\n<\/ol>\n<figure class=\"float full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/6fe\/36e\/1a3\/6fe36e1a3debdd503234e8b3414251cf.png\" alt=\"\u0438\u0441\u0442\u043e\u0447\u043d\u0438\u043a https:\/\/eprint.iacr.org\/2015\/1092.pdf\" title=\"\u0438\u0441\u0442\u043e\u0447\u043d\u0438\u043a https:\/\/eprint.iacr.org\/2015\/1092.pdf\" width=\"1023\" height=\"887\"><figcaption>\u0438\u0441\u0442\u043e\u0447\u043d\u0438\u043a https:\/\/eprint.iacr.org\/2015\/1092.pdf<\/figcaption><\/figure>\n<p>\u0418 \u043d\u0430\u0448\u0430 \u0437\u0430\u0434\u0430\u0447\u0430 \u043e\u0442\u043e\u0431\u0440\u0430\u0437\u0438\u0442\u044c \u0432\u0435\u043a\u0442\u043e\u0440 \u0432 \u0431\u0438\u0442 \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0446\u0438\u0438 \u043e\u0434\u043d\u043e\u0437\u043d\u0430\u0447\u043d\u043e. \u0414\u043e\u043f\u0443\u0441\u0442\u0438\u043c, \u0447\u0442\u043e \u043a\u043b\u0438\u0435\u043d\u0442 \u0438 \u0441\u0435\u0440\u0432\u0435\u0440 \u0438\u043c\u0435\u044e\u0442 \u043e\u0434\u0438\u043d \u0438 \u0442\u043e\u0442 \u0436\u0435 \u0432\u0435\u043a\u0442\u043e\u0440, \u0442\u043e\u0433\u0434\u0430 \u043e\u0442\u043e\u0431\u0440\u0430\u0436\u0435\u043d\u0438\u0435 \u0432\u0435\u043a\u0442\u043e\u0440\u0430 \u0432 \u0431\u0438\u0442 \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0446\u0438\u0438 \u0434\u043e\u0432\u043e\u043b\u044c\u043d\u043e \u043f\u0440\u043e\u0441\u0442\u043e\u0435: \u0435\u0441\u043b\u0438 \u0432\u0435\u043a\u0442\u043e\u0440 \u043f\u043e\u043f\u0430\u043b \u0432 \u0441\u0435\u0440\u0443\u044e \u043e\u0431\u043b\u0430\u0441\u0442\u044c \u044f\u0447\u0435\u0439\u043a\u0438 \u0412\u043e\u0440\u043e\u043d\u043e\u0433\u043e, \u0442\u043e \u043e\u043d 1, \u0435\u0441\u043b\u0438 \u0432\u043d\u0435 \u0435\u0451, \u0442\u043e 0. \u041e\u0434\u043d\u0430\u043a\u043e \u0432\u0441\u0435 \u0443\u0441\u043b\u043e\u0436\u043d\u044f\u0435\u0442\u0441\u044f \u0442\u0435\u043c, \u0447\u0442\u043e \u0443 \u043a\u043b\u0438\u0435\u043d\u0442\u0430 \u0438 \u0441\u0435\u0440\u0432\u0435\u0440\u0430 \u0435\u0441\u0442\u044c \u0442\u043e\u043b\u044c\u043a\u043e \u0437\u0430\u0448\u0443\u043c\u043b\u0435\u043d\u043d\u044b\u0435 \u0432\u0430\u0440\u0438\u0430\u043d\u0442\u044b \u0432\u0435\u043a\u0442\u043e\u0440\u043e\u0432, \u0442\u0430\u043a \u0447\u0442\u043e \u043c\u043e\u0436\u043d\u043e \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c \u0440\u0430\u0437\u043d\u044b\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f. \u0414\u043b\u044f \u0438\u0441\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u0438\u044f \u044d\u0442\u043e\u0433\u043e \u0432\u0432\u043e\u0434\u0438\u0442\u0441\u044f \u0444\u0443\u043d\u043a\u0446\u0438\u044f HelpRec, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u043d\u0430\u0445\u043e\u0434\u0438\u0442 \u0441\u0434\u0432\u0438\u0433 \u0434\u043e \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0435\u0439 \u0442\u043e\u0447\u043a\u0438 \u0440\u0435\u0448\u0451\u0442\u043a\u0438. \u0415\u0451 \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u0432\u044b\u043f\u043e\u043b\u043d\u0438\u0442\u044c \u043d\u0430 \u043e\u0434\u043d\u043e\u0439 \u0438\u0437 \u0441\u0442\u043e\u0440\u043e\u043d \u0438 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442 \u043f\u0435\u0440\u0435\u0441\u043b\u0430\u0442\u044c \u0432\u0442\u043e\u0440\u043e\u0439 \u0441\u0442\u043e\u0440\u043e\u043d\u0435. \u0412\u0430\u0436\u043d\u043e \u0442\u043e, \u0447\u0442\u043e \u043e\u043d\u0430 \u0441\u043e\u043e\u0431\u0449\u0430\u0435\u0442 \u0441\u0434\u0432\u0438\u0433 \u0434\u043e \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0435\u0439 \u0442\u043e\u0447\u043a\u0438 \u0440\u0435\u0448\u0451\u0442\u043a\u0438, \u0430 \u043d\u0435 \u043a\u0430\u043a\u043e\u0439 \u0431\u0438\u0442 \u0434\u043e\u043b\u0436\u0435\u043d \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c\u0441\u044f.<\/p>\n<p>8.&nbsp;&nbsp;&nbsp; \u0414\u0430\u043b\u0435\u0435 \u0444\u0443\u043d\u043a\u0446\u0438\u044f Rec \u0438\u0449\u0435\u0442 1 \u0431\u0438\u0442 \u043a\u043b\u044e\u0447\u0430 \u0438\u0437 4 \u043a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442\u043e\u0432 \u043f\u043e\u043b\u0438\u043d\u043e\u043c\u0430 (\u0441 \u0443\u0447\u0435\u0442\u043e\u043c \u0441\u0434\u0432\u0438\u0433\u0430).<\/p>\n<p>9.&nbsp;&nbsp;&nbsp; \u041f\u043e\u0441\u043b\u0435 \u0445\u0435\u0448\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f \u043f\u043e\u043b\u0443\u0447\u0430\u0435\u043c \u043a\u043b\u044e\u0447 \u0434\u043b\u0438\u043d\u043e\u0439 256 \u0431\u0438\u0442, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0431\u0443\u0434\u0435\u0442 \u043e\u0434\u0438\u043d\u0430\u043a\u043e\u0432\u044b\u043c \u0438 \u0443 \u043a\u043b\u0438\u0435\u043d\u0442\u0430, \u0438 \u0443 \u0441\u0435\u0440\u0432\u0435\u0440\u0430.<\/p>\n<h2>7. \u041f\u0440\u0438\u043c\u0435\u043d\u0435\u043d\u0438\u0435 \u0438 \u0441\u0442\u0430\u043d\u0434\u0430\u0440\u0442\u0438\u0437\u0430\u0446\u0438\u044f<\/h2>\n<\/p>\n<p>\u041f\u0440\u043e\u0442\u043e\u043a\u043e\u043b \u0431\u044b\u043b \u043f\u0440\u0435\u0434\u043b\u043e\u0436\u0435\u043d \u0432 2019 <a href=\"https:\/\/csrc.nist.gov\/projects\/post-quantum-cryptography\" rel=\"noopener noreferrer nofollow\">NIST post-quantum crypto project<\/a>, \u043f\u0440\u043e\u0448\u0435\u043b \u0432\u043e \u0432\u0442\u043e\u0440\u043e\u0439 \u0440\u0430\u0443\u043d\u0434, \u043d\u043e \u043d\u0435 \u043f\u0440\u043e\u0448\u0435\u043b \u0432 \u0442\u0440\u0435\u0442\u0438\u0439 \u0440\u0430\u0443\u043d\u0434. \u0412 \u043e\u0442\u0447\u0435\u0442\u0435 NIST \u0433\u043e\u0432\u043e\u0440\u0438\u0442\u0441\u044f, \u0447\u0442\u043e \u0431\u043b\u0430\u0433\u043e\u0434\u0430\u0440\u044f \u0441\u0432\u043e\u0435\u0439 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0435 \u043f\u0440\u043e\u0442\u043e\u043a\u043e\u043b \u0438\u043c\u0435\u0435\u0442 \u043e\u0447\u0435\u043d\u044c \u0432\u044b\u0441\u043e\u043a\u0443\u044e \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c, \u043e\u0434\u043d\u0430\u043a\u043e \u043e\u043d \u043d\u0435 \u043f\u0440\u0435\u0432\u0437\u043e\u0448\u0435\u043b \u0441\u0432\u043e\u0435\u0433\u043e \u043a\u043e\u043d\u043a\u0443\u0440\u0435\u043d\u0442\u0430 KYBER (\u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u043e\u0441\u043d\u043e\u0432\u0430\u043d \u043d\u0430 \u0437\u0430\u0434\u0430\u0447\u0435 Module-LWE) \u043f\u043e \u0431\u0435\u0437\u043e\u043f\u0430\u0441\u043d\u043e\u0441\u0442\u0438, \u0430 \u0442\u0430\u043a\u0436\u0435 \u043f\u0440\u043e\u0438\u0433\u0440\u0430\u043b \u0435\u043c\u0443 \u0432 \u0440\u044f\u0434\u0435 \u0431\u0435\u043d\u0447\u043c\u0430\u0440\u043a\u043e\u0432. \u0412 \u0438\u0442\u043e\u0433\u0435 \u0432 3 \u0440\u0430\u0443\u043d\u0434 \u043f\u0440\u043e\u0448\u0435\u043b \u043f\u0440\u043e\u0442\u043e\u043a\u043e\u043b KYBER. <\/p>\n<p>\u0422\u0430\u043a\u0436\u0435, \u043f\u0440\u043e\u0442\u043e\u043a\u043e\u043b \u0442\u0435\u0441\u0442\u0438\u0440\u043e\u0432\u0430\u043b Google \u0432 \u043f\u0440\u043e\u0435\u043a\u0442\u0435 Canary \u0432\u043c\u0435\u0441\u0442\u0435 \u0441\u043e \u0441\u0432\u043e\u0438\u043c CECPQ1 \u0438 CECPQ2.<\/p>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/2c6\/083\/6e1\/2c60836e1cc1ccafe8288b24242489eb.png\" alt=\"\u0418\u0441\u0442\u043e\u0447\u043d\u0438\u043a: https:\/\/security.googleblog.com\/2016\/07\/experimenting-with-post-quantum.html\" title=\"\u0418\u0441\u0442\u043e\u0447\u043d\u0438\u043a: https:\/\/security.googleblog.com\/2016\/07\/experimenting-with-post-quantum.html\" width=\"727\" height=\"416\"><figcaption>\u0418\u0441\u0442\u043e\u0447\u043d\u0438\u043a: https:\/\/security.googleblog.com\/2016\/07\/experimenting-with-post-quantum.html<\/figcaption><\/figure>\n<p>\u0420\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438 \u043f\u0440\u043e\u0442\u043e\u043a\u043e\u043b\u0430:<\/p>\n<ol>\n<li>\n<p><a href=\"https:\/\/newhopecrypto.org\/software.shtml\" rel=\"noopener noreferrer nofollow\">\u041d\u0430 \u044f\u0437\u044b\u043a\u0435 \u0421<\/a><\/p>\n<\/li>\n<li>\n<p><a href=\"https:\/\/hackage.haskell.org\/package\/newhope\" rel=\"noopener noreferrer nofollow\">\u041d\u0430 \u044f\u0437\u044b\u043a\u0435 Haskell<\/a><\/p>\n<\/li>\n<li>\n<p><a href=\"https:\/\/ieeexplore.ieee.org\/document\/8930047\" rel=\"noopener noreferrer nofollow\">\u0421\u0442\u0430\u0442\u044c\u044f \u043e \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438 \u043d\u0430 FPGA<\/a><\/p>\n<\/li>\n<\/ol>\n<p>\u0418\u0441\u0442\u043e\u0447\u043d\u0438\u043a\u0438:<\/p>\n<ol>\n<li>\n<p><a href=\"https:\/\/newhopecrypto.org\/\" rel=\"noopener noreferrer nofollow\">https:\/\/newhopecrypto.org\/<\/a><\/p>\n<\/li>\n<li>\n<p><a href=\"https:\/\/eprint.iacr.org\/2015\/1092.pdf\" rel=\"noopener noreferrer nofollow\">https:\/\/eprint.iacr.org\/2015\/1092.pdf<\/a><\/p>\n<\/li>\n<li>\n<p><a href=\"https:\/\/eprint.iacr.org\/2014\/599.pdf\" rel=\"noopener noreferrer nofollow\">https:\/\/eprint.iacr.org\/2014\/599.pdf<\/a><\/p>\n<\/li>\n<li>\n<p><a href=\"https:\/\/www.di.ens.fr\/chloe.hebant\/presentation\/SISproblem.pdf\" rel=\"noopener noreferrer nofollow\">https:\/\/www.di.ens.fr\/chloe.hebant\/presentation\/SISproblem.pdf<\/a><\/p>\n<\/li>\n<li>\n<p><a href=\"http:\/\/www.ee.cityu.edu.hk\/~twhk05\/achieve\/Wai%20Ho%20Mow.pdf\" rel=\"noopener noreferrer nofollow\">http:\/\/www.ee.cityu.edu.hk\/~twhk05\/achieve\/Wai%20Ho%20Mow.pdf<\/a><\/p>\n<\/li>\n<li>\n<p><a href=\"https:\/\/simons.berkeley.edu\/talks\/lwe-worst-case-average-case-reductions-and-cryptomania\" rel=\"noopener noreferrer nofollow\">https:\/\/simons.berkeley.edu\/talks\/lwe-worst-case-average-case-reductions-and-cryptomania<\/a><br \/><a href=\"https:\/\/simons.berkeley.edu\/talks\/algebraic-lattices-and-ring-lwe\" rel=\"noopener noreferrer nofollow\">https:\/\/simons.berkeley.edu\/talks\/algebraic-lattices-and-ring-lwe<\/a><\/p>\n<\/li>\n<li>\n<p><a href=\"https:\/\/www.ei.ruhr-uni-bochum.de\/media\/sh\/veroeffentlichungen\/2013\/08\/14\/lwe_encrypt.pdf\" rel=\"noopener noreferrer nofollow\">https:\/\/www.ei.ruhr-uni-bochum.de\/media\/sh\/veroeffentlichungen\/2013\/08\/14\/lwe_encrypt.pdf<\/a><\/p>\n<\/li>\n<li>\n<p><a href=\"https:\/\/summerschool-croatia.cs.ru.nl\/2018\/slides\/Introduction%20to%20post-quantum%20cryptography%20and%20learning%20with%20errors.pdf\" rel=\"noopener noreferrer nofollow\">https:\/\/summerschool-croatia.cs.ru.nl\/2018\/slides\/Introduction%20to%20post-quantum%20cryptography%20and%20learning%20with%20errors.pdf<\/a><\/p>\n<\/li>\n<li>\n<p><a href=\"https:\/\/people.csail.mit.edu\/vinodv\/6876-Fall2015\/L12.pdf\" rel=\"noopener noreferrer nofollow\">https:\/\/people.csail.mit.edu\/vinodv\/6876-Fall2015\/L12.pdf<\/a><\/p>\n<\/li>\n<li>\n<p><a href=\"https:\/\/security.googleblog.com\/2016\/07\/experimenting-with-post-quantum.html\" rel=\"noopener noreferrer nofollow\">https:\/\/security.googleblog.com\/2016\/07\/experimenting-with-post-quantum.html<\/a><\/p>\n<\/li>\n<\/ol>\n<\/div>\n<p> \u0441\u0441\u044b\u043b\u043a\u0430 \u043d\u0430 \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b \u0441\u0442\u0430\u0442\u044c\u0438 <a href=\"https:\/\/habr.com\/ru\/post\/532694\/\"> https:\/\/habr.com\/ru\/post\/532694\/<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"\n<div class=\"post__text post__text_v2\" id=\"post-content-body\">\n<figure class=\"full-width\"><figcaption><\/figcaption><\/figure>\n<p>\u0414\u043e\u0431\u0440\u043e\u0433\u043e \u0432\u0440\u0435\u043c\u0435\u043d\u0438 \u0441\u0443\u0442\u043e\u043a!    <\/p>\n<p>\u0412 \u0441\u043e\u0432\u0440\u0435\u043c\u0435\u043d\u043d\u043e\u043c \u043c\u0438\u0440\u0435 \u0432\u0441\u0451 \u0431\u043e\u043b\u044c\u0448\u0435 \u043f\u043e\u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0437\u0430\u044f\u0432\u043b\u0435\u043d\u0438\u0439 \u043e \u043f\u043e\u0442\u0435\u043d\u0446\u0438\u0430\u043b\u044c\u043d\u043e\u0439 \u0443\u0433\u0440\u043e\u0437\u0435 \u0441\u043e \u0441\u0442\u043e\u0440\u043e\u043d\u044b \u043a\u0432\u0430\u043d\u0442\u043e\u0432\u044b\u0445 \u043a\u043e\u043c\u043f\u044c\u044e\u0442\u0435\u0440\u043e\u0432 \u043f\u043e \u043e\u0442\u043d\u043e\u0448\u0435\u043d\u0438\u044e \u043a \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u043c\u044b\u043c \u043f\u0440\u043e\u0442\u043e\u043a\u043e\u043b\u0430\u043c \u043a\u0440\u0438\u043f\u0442\u043e\u0433\u0440\u0430\u0444\u0438\u0438. \u041a\u0432\u0430\u043d\u0442\u043e\u0432\u044b\u0439 \u043a\u043e\u043c\u043f\u044c\u044e\u0442\u0435\u0440 \u0443\u0436\u0435 \u0441\u043f\u043e\u0441\u043e\u0431\u0435\u043d \u0440\u0435\u0448\u0430\u0442\u044c \u0437\u0430\u0434\u0430\u0447\u0438 \u0434\u0438\u0441\u043a\u0440\u0435\u0442\u043d\u043e\u0433\u043e \u043b\u043e\u0433\u0430\u0440\u0438\u0444\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f \u0438 \u0440\u0430\u0437\u043b\u043e\u0436\u0435\u043d\u0438\u044f \u0447\u0438\u0441\u043b\u0430 \u043d\u0430 \u043c\u043d\u043e\u0436\u0438\u0442\u0435\u043b\u0438, \u0447\u0442\u043e \u0441\u0442\u0430\u0432\u0438\u0442 \u043f\u043e\u0434 \u0443\u0433\u0440\u043e\u0437\u0443 \u0432\u0441\u0435 \u043f\u0440\u043e\u0442\u043e\u043a\u043e\u043b\u044b \u043d\u0430 \u0438\u0445 \u043e\u0441\u043d\u043e\u0432\u0435. <\/p>\n<p>\u0421\u0435\u0433\u043e\u0434\u043d\u044f \u0440\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u043f\u0440\u043e\u0442\u043e\u043a\u043e\u043b NewHope, \u0432 \u043e\u0441\u043d\u043e\u0432\u0435 \u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u043b\u0435\u0436\u0438\u0442 \u0434\u0440\u0443\u0433\u0430\u044f \u0441\u043b\u043e\u0436\u043d\u0430\u044f \u0437\u0430\u0434\u0430\u0447\u0430 &#8212; \u0437\u0430\u0434\u0430\u0447\u0430 \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u044f \u0441 \u043e\u0448\u0438\u0431\u043a\u0430\u043c\u0438 \u0432 \u043a\u043e\u043b\u044c\u0446\u0435 (Ring-LWE).<\/p>\n<p>\u041f\u0440\u043e\u0442\u043e\u043a\u043e\u043b NewHope \u2013 \u044d\u0442\u043e \u043f\u0440\u043e\u0442\u043e\u043a\u043e\u043b \u0441\u043e\u0432\u043c\u0435\u0441\u0442\u043d\u043e\u0439 \u0432\u044b\u0440\u0430\u0431\u043e\u0442\u043a\u0438 \u043a\u043b\u044e\u0447\u0430, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0431\u044b\u043b \u0440\u0430\u0437\u0440\u0430\u0431\u043e\u0442\u0430\u043d \u0441\u043f\u0435\u0446\u0438\u0430\u043b\u044c\u043d\u043e, \u0447\u0442\u043e\u0431\u044b \u043f\u0440\u043e\u0442\u0438\u0432\u043e\u0441\u0442\u043e\u044f\u0442\u044c \u0430\u0442\u0430\u043a\u0430\u043c \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u043a\u0432\u0430\u043d\u0442\u043e\u0432\u044b\u0445 \u043a\u043e\u043c\u043f\u044c\u044e\u0442\u0435\u0440\u043e\u0432. \u041f\u0440\u0435\u0436\u0434\u0435 \u0447\u0435\u043c \u043f\u0435\u0440\u0435\u0445\u043e\u0434\u0438\u0442\u044c \u043d\u0435\u043f\u043e\u0441\u0440\u0435\u0434\u0441\u0442\u0432\u0435\u043d\u043d\u043e \u043a \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0443 \u0440\u0430\u0431\u043e\u0442\u044b, \u0440\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u0437\u0430\u0434\u0430\u0447\u0438 SIS, LWE \u0438 Ring-LWE:<\/p>\n<h2>1. SIS \u043a\u0430\u043a \u0437\u0430\u0434\u0430\u0447\u0430 \u043d\u0430 \u0440\u0435\u0448\u0451\u0442\u043a\u0430\u0445<\/h2>\n<p><strong>SIS (Short integer solution problem)<\/strong> \u2013 \u0437\u0430\u0434\u0430\u0447\u0430 \u043f\u043e\u0438\u0441\u043a\u0430 \u043a\u043e\u0440\u043e\u0442\u043a\u043e\u0433\u043e \u0432\u0435\u043a\u0442\u043e\u0440\u0430 \u043d\u0430 \u0440\u0435\u0448\u0451\u0442\u043a\u0435 \u0432 \u043e\u043a\u0440\u0435\u0441\u0442\u043d\u043e\u0441\u0442\u0438 \u0442\u043e\u0447\u043a\u0438.<\/p>\n<p>\u0418\u043c\u0435\u0435\u0442\u0441\u044f \u043c\u0430\u0442\u0440\u0438\u0446\u0430 \u0410, \u0441\u0442\u043e\u043b\u0431\u0446\u044b \u043a\u043e\u0442\u043e\u0440\u043e\u0439 \u0441\u043e\u0441\u0442\u043e\u044f\u0442 \u0438\u0437 \u0446\u0435\u043b\u043e\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u044b\u0445 \u0432\u0435\u043a\u0442\u043e\u0440\u043e\u0432 \u0434\u043b\u0438\u043d\u044b n \u043f\u043e \u043c\u043e\u0434\u0443\u043b\u044e q (\u0432\u0435\u043a\u0442\u043e\u0440\u0430 \u0432\u044b\u0431\u0438\u0440\u0430\u044e\u0442\u0441\u044f \u0441\u043b\u0443\u0447\u0430\u0439\u043d\u043e):<\/p>\n<p>\u0422\u0430\u043a\u0436\u0435 \u0432\u0432\u0435\u0434\u0435\u043c \u0441\u0438\u043c\u0432\u043e\u043b  \u0438\u043b\u0438 \u0436\u0435 \u043e\u0440\u0442\u043e\u0433\u043e\u043d\u0430\u043b\u044c\u043d\u0443\u044e \u0440\u0435\u0448\u0451\u0442\u043a\u0443 \u043e\u0442 A:<\/p>\n<figure class=\"full-width\"><figcaption><\/figcaption><\/figure>\n<p>\u041d\u0430 \u0440\u0438\u0441\u0443\u043d\u043a\u0435 \u043f\u043e\u043a\u0430\u0437\u0430\u043d\u0430 \u0440\u0435\u0448\u0451\u0442\u043a\u0430 \u0441 \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u043c \u0431\u0430\u0437\u0438\u0441\u043e\u043c (\u043d\u0435 \u043e\u0431\u044f\u0437\u0430\u0442\u0435\u043b\u044c\u043d\u043e \u043a\u0440\u0430\u0442\u0447\u0430\u0439\u0448\u0438\u043c) \u0438 \u0432\u044b\u0434\u0435\u043b\u0435\u043d\u043d\u044b\u0439 \u043a\u0432\u0430\u0434\u0440\u0430\u0442, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0438 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0438\u0432\u0430\u0435\u0442 \u043f\u043e \u043c\u043e\u0434\u0443\u043b\u044e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u0442\u043e\u0447\u0435\u043a \u0440\u0435\u0448\u0451\u0442\u043a\u0438.<\/p>\n<p>\u0417\u0430\u0434\u0430\u0447\u0430 \u0441\u043e\u0441\u0442\u043e\u0438\u0442 \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e\u0431\u044b \u043f\u0440\u0438 \u0437\u0430\u0434\u0430\u043d\u043d\u043e\u0439 \u043c\u0430\u0442\u0440\u0438\u0446\u0435 \u0410 \u043d\u0430\u0439\u0442\u0438 \u043d\u0435\u043d\u0443\u043b\u0435\u0432\u043e\u0439 \u0432\u0435\u043a\u0442\u043e\u0440 \u0440\u0435\u0448\u0451\u0442\u043a\u0435                                                   &nbsp;\u0442\u0430\u043a\u043e\u0439, \u0447\u0442\u043e . \u0417\u0430\u0434\u0430\u0447\u0430 \u0440\u0435\u0448\u0430\u0435\u0442\u0441\u044f \u043c\u0435\u0442\u043e\u0434\u043e\u043c \u0413\u0430\u0443\u0441\u0441\u0430 \u0438, \u043e\u0442\u0447\u0430\u0441\u0442\u0438, \u043d\u0438\u0447\u0435\u0433\u043e \u0441\u043b\u043e\u0436\u043d\u043e\u0433\u043e \u0432 \u043d\u0435\u0439 \u043d\u0435\u0442.<\/p>\n<p>\u0412\u0432\u0435\u0434\u0435\u043c \u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440 \u0438 \u043f\u043e\u0441\u0442\u0430\u0432\u0438\u043c \u0443\u0441\u043b\u043e\u0432\u0438\u0435, \u0447\u0442\u043e \u043c\u044b \u0438\u0449\u0435\u043c \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u043a\u043e\u0440\u043e\u0442\u043a\u0438\u0439 \u0432\u0435\u043a\u0442\u043e\u0440 z, \u0442\u0430\u043a\u043e\u0439 \u0447\u0442\u043e . \u042d\u0442\u043e \u0443\u0441\u043b\u043e\u0432\u0438\u0435 \u0434\u043e\u043b\u0436\u043d\u043e \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0442\u044c\u0441\u044f \u0434\u043b\u044f \u043b\u044e\u0431\u043e\u0433\u043e \u043f\u043e\u043b\u043e\u0436\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0433\u043e \u0432\u0435\u043a\u0442\u043e\u0440\u0430 z (\u043e\u043d\u0438 \u0446\u0435\u043b\u043e\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u044b\u0435 \u043f\u043e \u043c\u043e\u0434\u0443\u043b\u044e q). \u0410\u043d\u0430\u043b\u043e\u0433\u0438\u0447\u043d\u043e \u0437\u0430\u0434\u0430\u0447\u0443 \u043c\u043e\u0436\u043d\u043e \u043f\u0435\u0440\u0435\u0444\u0440\u0430\u0437\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0442\u0430\u043a, \u0447\u0442\u043e \u043c\u044b \u0438\u0449\u0435\u043c \u0432\u0435\u043a\u0442\u043e\u0440, \u043f\u0440\u0438\u043d\u0430\u0434\u043b\u0435\u0436\u0430\u0449\u0438\u0439 \u043e\u043a\u0440\u0435\u0441\u0442\u043d\u043e\u0441\u0442\u0438 \u0442\u043e\u0447\u043a\u0438 \u0440\u0435\u0448\u0451\u0442\u043a\u0438. \u0422\u0430\u043a \u043a\u0430\u043a \u043c\u044b \u043c\u0430\u0442\u0440\u0438\u0446\u0443 \u0410 \u0432\u044b\u0431\u0438\u0440\u0430\u043b\u0438 \u0441\u043b\u0443\u0447\u0430\u0439\u043d\u044b\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c, \u0442\u043e \u043c\u044b \u043f\u043e\u0441\u0442\u0430\u0432\u0438\u043b\u0438 \u0437\u0430\u0434\u0430\u0447\u0443 \u0432 \u043e\u0431\u0449\u0435\u043c \u0441\u043b\u0443\u0447\u0430\u0435.<\/p>\n<p>\u041a\u0430\u043a \u043c\u043e\u0436\u043d\u043e \u0443\u0441\u043b\u043e\u0436\u043d\u0438\u0442\u044c \u0437\u0430\u0434\u0430\u0447\u0443? \u0421\u0434\u0432\u0438\u043d\u0435\u043c \u0440\u0435\u0448\u0451\u0442\u043a\u0443 \u043d\u0430 \u043d\u0435\u0431\u043e\u043b\u044c\u0448\u043e\u0435 \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0435, \u044d\u0442\u043e \u043f\u0440\u0438\u0432\u043d\u0435\u0441\u0435\u0442 \u0432 \u043d\u0435\u0435 \u0448\u0443\u043c (\u0433\u043b\u0430\u0432\u043d\u043e\u0435 \u043d\u0435 \u0441\u0434\u0432\u0438\u0433\u0430\u0442\u044c \u0441\u043b\u0438\u0448\u043a\u043e\u043c \u0441\u0438\u043b\u044c\u043d\u043e). <\/p>\n<p>\u041f\u0440\u0435\u0434\u043b\u0430\u0433\u0430\u0435\u0442\u0441\u044f \u0432\u044b\u0431\u0438\u0440\u0430\u0442\u044c \u0441\u0434\u0432\u0438\u0433 &#8212; \u043f\u0435\u0440\u0438\u043e\u0434\u0430 \u0440\u0435\u0448\u0451\u0442\u043a\u0438. \u0418\u043d\u0430\u0447\u0435 \u0432\u043e\u0437\u043d\u0438\u043a\u043d\u0435\u0442 \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u0430 \u0441 \u0432\u043e\u0441\u0441\u0442\u0430\u043d\u043e\u0432\u043b\u0435\u043d\u0438\u0435\u043c \u0432\u0435\u043a\u0442\u043e\u0440\u0430 z.<\/p>\n<p>\u0422\u0435\u043f\u0435\u0440\u044c \u043f\u043e\u0441\u043b\u0435 \u0432\u043d\u0435\u0441\u0435\u043d\u0438\u044f \u0448\u0443\u043c\u0430, \u0438\u0441\u043a\u0430\u0442\u044c \u043a\u043e\u0440\u043e\u0442\u043a\u0438\u0439 \u0432\u0435\u043a\u0442\u043e\u0440 z \u043f\u043e \u0437\u0430\u0434\u0430\u043d\u043d\u043e\u043c\u0443 A \u0441\u0442\u0430\u043d\u043e\u0432\u0438\u0442\u0441\u044f \u043e\u0447\u0435\u043d\u044c \u0441\u043b\u043e\u0436\u043d\u043e\u0439 \u0437\u0430\u0434\u0430\u0447\u0435\u0439. <\/p>\n<p>\u0415\u0441\u043b\u0438 \u043c\u044b \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u043c \u0432 \u0435\u0432\u043a\u043b\u0438\u0434\u043e\u0432\u043e\u0439 \u043d\u043e\u0440\u043c\u0435, \u0442\u043e \u043c\u043e\u0436\u0435\u043c \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c \u0430\u0441\u0438\u043c\u043f\u0442\u043e\u0442\u0438\u0447\u0435\u0441\u043a\u0443\u044e \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u0432 , \u0433\u0434\u0435 n &#8212; \u0440\u0430\u0437\u043c\u0435\u0440\u043d\u043e\u0441\u0442\u044c \u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0441\u0442\u0432\u0430.<\/p>\n<h2>2. LWE ( Learning with errors)<\/h2>\n<p>\u0420\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u0437\u0430\u0434\u0430\u0447\u0443 \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u044f \u0441 \u043e\u0448\u0438\u0431\u043a\u0430\u043c\u0438:<\/p>\n<p>\u041f\u0430\u0440\u0430\u043c\u0435\u0442\u0440\u044b \u0437\u0430\u0434\u0430\u0447\u0438: <\/p>\n<p>n \u2013 \u0440\u0430\u0437\u043c\u0435\u0440\u043d\u043e\u0441\u0442\u044c \u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0441\u0442\u0432\u0430;<\/p>\n<p>q \u2013 \u0447\u0438\u0441\u043b\u043e, \u043a\u0430\u043a \u0438 \u0432 \u043f\u0440\u043e\u0448\u043b\u043e\u0439 \u0437\u0430\u0434\u0430\u0447\u0435. \u0417\u0434\u0435\u0441\u044c \u043e\u043d\u043e \u0431\u0435\u0440\u0435\u0442\u0441\u044f \u0441 \u043f\u043e\u043b\u0438\u043d\u043e\u043c\u0438\u0430\u043b\u044c\u043d\u043e\u0439 \u0437\u0430\u0432\u0438\u0441\u0438\u043c\u043e\u0441\u0442\u044c\u044e \u043e\u0442 n, \u043f\u043e\u0440\u044f\u0434\u043a\u0430 ;<\/p>\n<p>\u0410 \u0442\u0430\u043a\u0436\u0435 \u0444\u0443\u043d\u043a\u0446\u0438\u044f \u0440\u0430\u0441\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u044f \u043e\u0448\u0438\u0431\u043e\u043a \u0431\u0435\u0440\u0435\u0442\u0441\u044f \u043d\u043e\u0440\u043c\u0430\u043b\u044c\u043d\u043e\u0435 \u0440\u0430\u0441\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u0435, \u0434\u043b\u044f \u043a\u0440\u0430\u0441\u0438\u0432\u044b\u0445 \u0444\u043e\u0440\u043c\u0443\u043b \u0432 \u0434\u043e\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044c\u0441\u0442\u0432\u0430\u0445);<\/p>\n<p>\u041a\u0430\u043a \u0438 \u0432 \u043f\u0440\u043e\u0448\u043b\u043e\u0439 \u0437\u0430\u0434\u0430\u0447\u0435 \u0437\u0430\u0434\u0430\u0434\u0438\u043c \u0441\u043b\u0443\u0447\u0430\u0439\u043d\u0443\u044e \u043c\u0430\u0442\u0440\u0438\u0446\u0443 \u0441\u0442\u043e\u043b\u0431\u0446\u044b \u043a\u043e\u0442\u043e\u0440\u043e\u0439 \u0432\u0435\u043a\u0442\u043e\u0440\u0430 ;<\/p>\n<p>\u0418 \u0432\u0435\u043a\u0442\u043e\u0440 k, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0431\u0443\u0434\u0435\u0442 \u043e\u0442\u0432\u0435\u0447\u0430\u0442\u044c \u0437\u0430 \u0448\u0443\u043c \u0438\u0437 \u0440\u0430\u0441\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u044f .<\/p>\n<p>\u0417\u0430\u0434\u0430\u0447\u0430 \u0441\u043e\u0441\u0442\u043e\u0438\u0442 \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e \u0437\u043b\u043e\u0443\u043c\u044b\u0448\u043b\u0435\u043d\u043d\u0438\u043a\u0443 \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u043d\u0430\u0439\u0442\u0438 \u0441\u0435\u043a\u0440\u0435\u0442\u043d\u044b\u0439 \u0432\u0435\u043a\u0442\u043e\u0440 , \u043a\u043e\u0433\u0434\u0430 \u0435\u043c\u0443 \u0438\u0437\u0432\u0435\u0441\u0442\u043d\u044b \u0432\u0441\u0435\u0432\u043e\u0437\u043c\u043e\u0436\u043d\u044b\u0435 \u0437\u0430\u0448\u0443\u043c\u043b\u0435\u043d\u043d\u044b\u0435 \u0441\u043a\u0430\u043b\u044f\u0440\u043d\u044b\u0435 \u043f\u0440\u043e\u0438\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u044f s \u0441 \u0432\u0435\u043a\u0442\u043e\u0440\u0430\u043c\u0438 . (\u0412\u0441\u0435 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438 \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u044e\u0442\u0441\u044f \u043f\u043e \u043c\u043e\u0434\u0443\u043b\u044e q):<\/p>\n<p> \\: mod \\: q&#187; alt=&#187;a_1 \\gets \\mathbb{Z}^n_q ,\\: b_1 \\approx\\: <s, a_1> \\: mod \\: q&#187; src=&#187;https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/07e\/f95\/b54\/07ef95b542787bc2cfd760843409cf01.svg&#187; width=&#187;222&#8243; height=&#187;21&#8243;> \\: mod \\: q&#187; alt=&#187;a_2 \\gets \\mathbb{Z}^n_q ,\\: b_2 \\approx\\: <s, a_2> \\: mod \\: q&#187; src=&#187;https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/b2c\/8fb\/880\/b2c8fb880c920079ed105f44ae30d2c4.svg&#187; width=&#187;222&#8243; height=&#187;21&#8243;><\/p>\n<p>\u0418\u043b\u0438 \u0442\u043e\u0447\u043d\u0435\u0435<\/p>\n<p>+k_1\\in \\mathbb{Z}_q&#187; alt=&#187;b_1=<s,a_1>+k_1\\in \\mathbb{Z}_q&#187; src=&#187;https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/ac1\/9c8\/1b9\/ac19c81b9cfb7880fd3baa2d21a1e315.svg&#187; width=&#187;167&#8243; height=&#187;19&#8243;><\/p>\n<p>\u0413\u0434\u0435 \u043f\u0435\u0440\u0432\u0430\u044f \u043a\u043e\u043c\u043f\u043e\u043d\u0435\u043d\u0442\u0430 \u0432\u0435\u043a\u0442\u043e\u0440\u0430 . <\/p>\n<p>\u041e\u0434\u043d\u0430\u043a\u043e \u043d\u0430\u0441 \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u0443\u0435\u0442 \u043c\u043e\u0434\u0438\u0444\u0438\u043a\u0430\u0446\u0438\u044f \u0437\u0430\u0434\u0430\u0447\u0438, \u0442\u0430\u043a \u043d\u0430\u0437\u044b\u0432\u0430\u0435\u043c\u043e\u0435 \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u0435 \u0441 \u043e\u0448\u0438\u0431\u043a\u0430\u043c\u0438 \u043d\u0430 \u0440\u0435\u0448\u0451\u0442\u043a\u0430\u0445 (LWE on lattices).<\/p>\n<p>\u0417\u0430\u0434\u0430\u0434\u0438\u043c \u0440\u0435\u0448\u0451\u0442\u043a\u0443:<\/p>\n<figure class=\"full-width\"><figcaption><\/figcaption><\/figure>\n<p>\u0417\u0430\u0434\u0430\u0447\u0430 \u0443\u0436\u0435 \u043f\u043e\u0434\u043c\u0435\u043d\u044f\u0435\u0442\u0441\u044f \u0434\u0440\u0443\u0433\u043e\u0439 \u2013 \u0434\u0435\u043a\u043e\u0434\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435 \u0441 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u043d\u044b\u043c \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0435\u043c.     <\/p>\n<p>\u0417\u0430\u0434\u0430\u043d\u0430 \u0440\u0435\u0448\u0451\u0442\u043a\u0430, \u0438 \u0434\u0430\u043d\u0430 \u0442\u043e\u0447\u043a\u0430 q. \u041d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u0432 \u0435\u0451 \u043e\u043a\u0440\u0435\u0441\u0442\u043d\u043e\u0441\u0442\u0438 \u043d\u0430\u0439\u0442\u0438 \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0443\u044e \u043a \u043d\u0435\u0439 \u0442\u043e\u0447\u043a\u0443 \u0440\u0435\u0448\u0451\u0442\u043a\u0438. <\/p>\n<p>\u0422\u0430\u043a \u0436\u0435, \u043a\u0430\u043a \u0438 \u0432 \u043f\u0440\u043e\u0448\u043b\u044b\u0445 \u0437\u0430\u0434\u0430\u0447\u0430\u0445 \u0432\u043d\u043e\u0441\u0438\u043c \u0448\u0443\u043c \u0432 \u0440\u0435\u0448\u0451\u0442\u043a\u0443, \u0442\u043e\u0433\u0434\u0430 \u0437\u0430\u0434\u0430\u0447\u0430 \u043d\u0430\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u044f \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0435\u0433\u043e \u0432\u0435\u043a\u0442\u043e\u0440\u0430 \u0441\u0442\u0430\u043d\u043e\u0432\u0438\u0442\u0441\u044f \u043e\u0447\u0435\u043d\u044c \u0441\u043b\u043e\u0436\u043d\u043e\u0439:<\/p>\n<p>\u0414\u0430\u043d\u043e: \u043d\u0430\u0439\u0442\u0438 .<\/p>\n<h2>3. \u041f\u0440\u0438\u043c\u0435\u0440\u044b<\/h2>\n<p>\u0420\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u0441\u043e\u0437\u0434\u0430\u043d\u0438\u0435 \u043a\u0440\u0438\u043f\u0442\u043e\u0433\u0440\u0430\u0444\u0438\u0447\u0435\u0441\u043a\u043e\u0439 \u0441\u0438\u0441\u0442\u0435\u043c\u044b \u0441 \u043e\u0442\u043a\u0440\u044b\u0442\u044b\u043c \u043a\u043b\u044e\u0447\u043e\u043c \u043d\u0430 LWE, \u0430 \u0442\u0430\u043a\u0436\u0435 \u0445\u0435\u0448-\u0444\u0443\u043d\u043a\u0446\u0438\u044e \u043d\u0430 SIS:<\/p>\n<p><strong>Public key encryption (LWE):<\/strong><\/p>\n<p>\u0411\u043e\u0431 \u0445\u043e\u0447\u0435\u0442 \u043e\u0442\u043f\u0440\u0430\u0432\u0438\u0442\u044c \u0441\u043e\u043e\u0431\u0449\u0435\u043d\u0438\u0435 \u0410\u043b\u0438\u0441\u0435, \u0437\u0430\u0448\u0438\u0444\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0435 \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u0435\u0451 \u043e\u0442\u043a\u0440\u044b\u0442\u043e\u0433\u043e \u043a\u043b\u044e\u0447\u0430. \u0421\u043e\u043e\u0431\u0449\u0435\u043d\u0438\u0435 \u0432 \u0434\u0430\u043d\u043d\u043e\u043c \u043f\u0440\u0438\u043c\u0435\u0440\u0435 \u2013 \u0431\u0438\u0442 \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0446\u0438\u0438.<\/p>\n<figure class=\"full-width\"><figcaption><\/figcaption><\/figure>\n<p>\u0412 \u0434\u0430\u043d\u043d\u043e\u0439 \u0441\u0445\u0435\u043c\u0435 \u043d\u0430\u0434\u043e \u0443\u0447\u0435\u0441\u0442\u044c, \u0447\u0442\u043e \u0440\u0430\u0437\u043d\u043e\u0441\u0442\u044c \u043e\u0448\u0438\u0431\u043e\u043a <\/p>\n<p>\u0415\u0441\u043b\u0438 \u043f\u043e\u043b\u0443\u0447\u0438\u0432\u0448\u0430\u044f\u0441\u044f \u0440\u0430\u0437\u043d\u043e\u0441\u0442\u044c \u0431\u043b\u0438\u0436\u0435 \u043a 0, \u0442\u043e \u0434\u0435\u043a\u043e\u0434\u0438\u0440\u043e\u0432\u0430\u043d 0, \u0438 \u0435\u0441\u043b\u0438 \u043a \u0442\u043e 1.<\/p>\n<p>\u0427\u0442\u043e \u0443 \u043d\u0430\u0441 \u0437\u043d\u0430\u0435\u0442 \u0445\u0430\u043a\u0435\u0440?  \u0438 . \u0422\u0430\u043a \u043a\u0430\u043a \u0432 \u043d\u0438\u0445 \u0437\u0430\u043c\u0435\u0448\u0430\u043d\u043e \u0443\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u0435 \u043d\u0430 \u0441\u043b\u0443\u0447\u0430\u0439\u043d\u0443\u044e \u043c\u0430\u0442\u0440\u0438\u0446\u0443 \u0441 \u043f\u0440\u0438\u043c\u0435\u0441\u044c\u044e \u0448\u0443\u043c\u0430, \u0442\u043e \u0432\u044b\u0445\u043e\u0434\u0438\u0442, \u0447\u0442\u043e \u043d\u0430 \u0440\u0443\u043a\u0430\u0445 \u0443 \u043d\u0435\u0433\u043e 4 \u0441\u043b\u0443\u0447\u0430\u0439\u043d\u044b\u0445 \u0432\u0435\u043b\u0438\u0447\u0438\u043d\u044b, \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u0443\u0437\u043d\u0430\u0442\u044c \u0441\u043e\u043e\u0431\u0449\u0435\u043d\u0438\u0435 \u043d\u0435 \u0432\u044b\u0439\u0434\u0435\u0442.<\/p>\n<p><strong>One-way function (SIS):<\/strong><\/p>\n<p>\u041f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u0435 \u0445\u0435\u0448-\u0444\u0443\u043d\u043a\u0446\u0438\u0438 \u043f\u0440\u0435\u0434\u043b\u0430\u0433\u0430\u0435\u0442\u0441\u044f \u043e\u0441\u0443\u0449\u0435\u0441\u0442\u0432\u043b\u044f\u0442\u044c \u043f\u043e \u0441\u0445\u0435\u043c\u0435 \u041c\u0435\u0440\u043a\u043b\u0430-\u0414\u0430\u043c\u0433\u043e\u0440\u0430:<\/p>\n<figure class=\"full-width\"><figcaption>\u041f\u0435\u0440\u0435\u0440\u0438\u0441\u043e\u0432\u0430\u043d\u043e \u0441 https:\/\/www.di.ens.fr\/chloe.hebant\/presentation\/SISproblem.pdf<\/figcaption><\/figure>\n<p>\u041f\u0440\u043e\u0438\u0441\u0445\u043e\u0434\u0438\u0442 \u0440\u0430\u0437\u0431\u0438\u0435\u043d\u0438\u0435 \u0438\u0437\u043d\u0430\u0447\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u0441\u043e\u043e\u0431\u0449\u0435\u043d\u0438\u044f \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u043b\u044c\u043d\u043e\u0439 \u0434\u043b\u0438\u043d\u044b \u043d\u0430 \u0431\u043b\u043e\u043a\u0438 \u043e\u0434\u0438\u043d\u0430\u043a\u043e\u0432\u043e\u0439 \u0434\u043b\u0438\u043d\u044b, \u0430 \u0432 \u0434\u0430\u043b\u044c\u043d\u0435\u0439\u0448\u0435\u043c \u043f\u043e\u0442\u043e\u043a\u043e\u0432\u0430\u044f \u043e\u0431\u0440\u0430\u0431\u043e\u0442\u043a\u0430 \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u0444\u0443\u043d\u043a\u0446\u0438\u0438 \u0441\u0436\u0430\u0442\u0438\u044f. \u0412 \u043a\u0430\u0436\u0434\u043e\u0439 \u0438\u0442\u0435\u0440\u0430\u0446\u0438\u0438 \u043a\u043e\u043d\u0432\u0435\u0439\u0435\u0440\u0430 \u043f\u0440\u0438\u043d\u0438\u043c\u0430\u0435\u0442\u0441\u044f \u0432\u0445\u043e\u0434\u043d\u043e\u0439 \u0431\u043b\u043e\u043a \u0438 \u0431\u043b\u043e\u043a \u043e\u0442 \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0435\u0433\u043e \u0441\u043e\u043e\u0431\u0449\u0435\u043d\u0438\u044f. \u0412 \u043d\u0430\u0447\u0430\u043b\u0435 \u0432\u0441\u0435 \u0438\u043d\u0438\u0446\u0438\u0430\u043b\u0438\u0437\u0438\u0440\u0443\u0435\u0442\u0441\u044f \u0432\u0435\u043a\u0442\u043e\u0440\u043e\u043c \u0438\u043d\u0438\u0446\u0438\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438 (IV).<\/p>\n<p>\u0414\u0430\u043c\u0433\u043e\u0440 \u0438 \u041c\u0435\u0440\u043a\u043b \u043d\u0435\u0437\u0430\u0432\u0438\u0441\u0438\u043c\u043e \u043f\u043e\u043a\u0430\u0437\u0430\u043b\u0438, \u0447\u0442\u043e \u0435\u0441\u043b\u0438  \u0431\u0443\u0434\u0435\u0442 \u0443\u0441\u0442\u043e\u0439\u0447\u0438\u0432\u043e\u0439 \u043a \u043a\u043e\u043b\u043b\u0438\u0437\u0438\u044f\u043c, \u0442\u043e \u0438  \u0431\u0443\u0434\u0435\u0442 \u0443\u0441\u0442\u043e\u0439\u0447\u0438\u0432\u0430.<\/p>\n<p>\u041d\u0430\u0448\u0430 \u0437\u0430\u0434\u0430\u0447\u0430 \u043f\u043e\u0441\u0442\u0440\u043e\u0438\u0442\u044c \u0444\u0443\u043d\u043a\u0446\u0438\u044e &#8212; \u0443\u0441\u0442\u043e\u0439\u0447\u0438\u0432\u0443\u044e \u043a \u043a\u043e\u043b\u043b\u0438\u0437\u0438\u044f\u043c (One-way function):<\/p>\n<p>\u0422\u0430\u043a \u0436\u0435, \u043a\u0430\u043a \u0438 \u0440\u0430\u043d\u0435\u0435 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u043c: <\/p>\n<p>\u0437\u0430\u0444\u0438\u043a\u0441\u0438\u0440\u0443\u0435\u043c \u0438 .<\/p>\n<p>\u041e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u043c &#8212; \u0441\u0435\u043c\u0435\u0439\u0441\u0442\u0432\u043e \u0444\u0443\u043d\u043a\u0446\u0438\u0439  \u0442\u0430\u043a\u0438\u0435 \u0447\u0442\u043e <\/p>\n<p>\u0418 \u0434\u043b\u044f \u0431\u0438\u0442\u043e\u0432\u043e\u0433\u043e \u0432\u0435\u043a\u0442\u043e\u0440\u0430 \u0444\u0443\u043d\u043a\u0446\u0438\u044f \u0431\u0443\u0434\u0435\u0442 \u0437\u0430\u0434\u0430\u0432\u0430\u0442\u044c\u0441\u044f \u043a\u0430\u043a: <\/p>\n<p>\\ mod\\>\\ q&#187; alt=&#187;f_A\\left(e\\right)=A \\times e\\>\\ mod\\>\\ q&#187; src=&#187;https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/aeb\/ed9\/41d\/aebed941dd29f3f5dec1a70674a0a246.svg&#187; width=&#187;156&#8243; height=&#187;20&#8243;><\/p>\n<p>\u041e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u0435 \u0434\u043e\u0432\u043e\u043b\u044c\u043d\u043e \u0435\u0441\u0442\u0435\u0441\u0442\u0432\u0435\u043d\u043d\u043e\u0435 \u0432 \u043a\u043e\u043d\u0442\u0435\u043a\u0441\u0442\u0435 \u0437\u0430\u0434\u0430\u0447\u0438 SIS.<\/p>\n<p>\u0427\u0442\u043e \u043d\u0430\u0441\u0447\u0435\u0442 \u043a\u043e\u043b\u043b\u0438\u0437\u0438\u0439? \u0411\u044b\u043b\u0430 \u0434\u043e\u043a\u0430\u0437\u0430\u043d\u0430 \u043b\u0435\u043c\u043c\u0430, \u0447\u0442\u043e \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u043d\u0430\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u044f \u043a\u043e\u043b\u043b\u0438\u0437\u0438\u0438 \u0432 \u0443\u043a\u0430\u0437\u0430\u043d\u043d\u043e\u0439 \u0432\u044b\u0448\u0435 \u0437\u0430\u0434\u0430\u0447\u0438 \u0441 \u0432\u0435\u0440\u043e\u044f\u0442\u043d\u043e\u0441\u0442\u044c\u044e  \u0430\u043d\u0430\u043b\u043e\u0433\u0438\u0447\u043d\u0430 \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u0438 \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u0437\u0430\u0434\u0430\u0447\u0438 SIS \u0441 \u0442\u043e\u0439 \u0436\u0435 \u0432\u0435\u0440\u043e\u044f\u0442\u043d\u043e\u0441\u0442\u044c\u044e.<\/p>\n<h2>4. \u041f\u0440\u043e\u0431\u043b\u0435\u043c\u044b \u0441 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u0435\u043c \u044d\u0442\u0438\u0445 \u0437\u0430\u0434\u0430\u0447 \u0432 \u0440\u0435\u0430\u043b\u044c\u043d\u044b\u0445 \u043a\u0440\u0438\u043f\u0442\u043e\u0441\u0438\u0441\u0442\u0435\u043c\u0430\u0445<\/h2>\n<p>\u041f\u0440\u0438 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u0438 \u0432 \u0440\u0435\u0430\u043b\u044c\u043d\u044b\u0445 \u043a\u0440\u0438\u043f\u0442\u043e\u0441\u0438\u0441\u0442\u0435\u043c\u0430\u0445 \u0432\u043e\u0437\u043d\u0438\u043a\u0430\u0435\u0442 \u0440\u044f\u0434 \u043f\u0440\u043e\u0431\u043b\u0435\u043c:<\/p>\n<p>\u041d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e\u0441\u0442\u044c \u043f\u0435\u0440\u0435\u0441\u044b\u043b\u043a\u0438 \u043e\u0447\u0435\u043d\u044c \u0431\u043e\u043b\u044c\u0448\u043e\u0433\u043e \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0430 \u0434\u0430\u043d\u043d\u044b\u0445. \u041d\u0430 \u0441\u043b\u0430\u0439\u0434\u0435 \u043f\u0440\u0438\u0432\u0435\u0434\u0435\u043d\u0430 \u043c\u0430\u0442\u0440\u0438\u0446\u0430  \u0434\u043b\u044f \u0440\u0430\u0437\u043c\u0435\u0440\u043d\u043e\u0441\u0442\u0438   \u0438 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0435\u043c 15 \u0431\u0438\u0442 \u043d\u0430 \u0447\u0438\u0441\u043b\u043e:<\/p>\n<figure class=\"full-width\"><figcaption>\u0418\u0441\u0442\u043e\u0447\u043d\u0438\u043a: https:\/\/summerschool-croatia.cs.ru.nl\/2018\/<\/figcaption><\/figure>\n<p>2) \u0412\u0441\u0435 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438 \u0448\u0438\u0444\u0440\u043e\u0432\u0430\u043d\u0438\u044f\/\u0434\u0435\u0448\u0438\u0444\u0440\u043e\u0432\u0430\u043d\u0438\u044f \u043f\u0440\u043e\u0438\u0441\u0445\u043e\u0434\u044f\u0442 \u0441 \u0430\u0441\u0438\u043c\u043f\u0442\u043e\u0442\u0438\u0447\u0435\u0441\u043a\u043e\u0439 \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c\u044e , \u0447\u0442\u043e \u0434\u043e\u0432\u043e\u043b\u044c\u043d\u043e \u043c\u0435\u0434\u043b\u0435\u043d\u043d\u043e.<\/p>\n<p>\u041a\u0430\u043a\u043e\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u0443 \u044d\u0442\u0438\u0445 \u043f\u0440\u043e\u0431\u043b\u0435\u043c?<\/p>\n<h2>5. Ring-LWE<\/h2>\n<p>\u041e\u0431\u0443\u0447\u0435\u043d\u0438\u0435 \u0441 \u043e\u0448\u0438\u0431\u043a\u0430\u043c\u0438 \u0432 \u043a\u043e\u043b\u044c\u0446\u0435 \u0440\u0435\u0448\u0430\u0435\u0442 \u0441\u0440\u0430\u0437\u0443 \u043e\u0431\u0435 \u0432\u044b\u0448\u0435\u043e\u043f\u0438\u0441\u0430\u043d\u043d\u044b\u0435 \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u044b.<\/p>\n<p>\u041a\u0430\u043a\u0430\u044f \u0438\u0434\u0435\u044f \u0431\u044b\u043b\u0430 \u0443 \u0441\u043e\u0437\u0434\u0430\u0442\u0435\u043b\u0435\u0439? \u0412\u0441\u043f\u043e\u043c\u043d\u0438\u043c, \u0447\u0442\u043e \u0432 LWE \u0437\u0430\u0434\u0430\u0447\u0435 \u043c\u044b \u0438\u043c\u0435\u0435\u043c \u043c\u043d\u043e\u0433\u043e \u0440\u0430\u0437\u043d\u044b\u0445 \u0441\u043a\u0430\u043b\u044f\u0440\u043d\u044b\u0445 \u043f\u0440\u043e\u0438\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u0439. \u0427\u0442\u043e \u0435\u0441\u043b\u0438 \u0437\u0430\u0434\u0430\u0442\u044c \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u044e \u0441\u043a\u0430\u043b\u044f\u0440\u043d\u043e\u0433\u043e \u043f\u0440\u043e\u0438\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u044f \u0442\u0430\u043a, \u0447\u0442\u043e\u0431\u044b \u043c\u044b \u043c\u043e\u0433\u043b\u0438 \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c n \u043f\u0441\u0435\u0432\u0434\u043e\u0441\u043b\u0443\u0447\u0430\u0439\u043d\u044b\u0445 \u0441\u043a\u0430\u043b\u044f\u0440\u043e\u0432 \u0438\u0437 \u043e\u0434\u043d\u043e\u0433\u043e?<\/p>\n<p>\u041a\u0430\u043a \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u0442\u044c \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u044e ?<\/p>\n<p>\u041d\u0430\u0438\u043b\u0443\u0447\u0448\u0438\u0439 \u0441\u043f\u043e\u0441\u043e\u0431 \u2013 \u0443\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u0435 \u0432 \u043a\u043e\u043b\u044c\u0446\u0435 \u043c\u043d\u043e\u0433\u043e\u0447\u043b\u0435\u043d\u043e\u0432 , \u0433\u0434\u0435 , n \u2013 \u0441\u0442\u0435\u043f\u0435\u043d\u044c \u0434\u0432\u043e\u0439\u043a\u0438. <\/p>\n<p>\u042d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u0438\u043c\u0435\u044e\u0442 \u0441\u0442\u0435\u043f\u0435\u043d\u044c c \u043a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442\u0430\u043c\u0438 \u043f\u043e \u043c\u043e\u0434\u0443\u043b\u044e q.<\/p>\n<p>\u041f\u043e\u0447\u0435\u043c\u0443 \u0438\u043c\u0435\u043d\u043d\u043e \u0442\u0430\u043a\u043e\u0439 \u0441\u043f\u043e\u0441\u043e\u0431? \u041d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e\u0441\u0442\u044c \u043f\u0435\u0440\u0435\u0434\u0430\u0432\u0430\u0442\u044c \u0431\u043e\u043b\u044c\u0448\u0438\u0435 \u043c\u0430\u0442\u0440\u0438\u0446\u044b \u043e\u0442\u043f\u0430\u0434\u0430\u0435\u0442. \u0412 \u0441\u0430\u043c\u043e\u043c \u0434\u0435\u043b\u0435, \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u043f\u0435\u0440\u0435\u0434\u0430\u0442\u044c \u043e\u0434\u0438\u043d \u043f\u043e\u043b\u0438\u043d\u043e\u043c, \u043e\u0441\u0442\u0430\u043b\u044c\u043d\u044b\u0435 \u043c\u043e\u0436\u043d\u043e \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c \u0446\u0438\u043a\u043b\u0438\u0447\u0435\u0441\u043a\u0438\u043c \u0441\u0434\u0432\u0438\u0433\u043e\u043c \u043f\u043e \u043f\u0440\u0430\u0432\u0438\u043b\u0443: . \u0412 \u0438\u0442\u043e\u0433\u0435 \u043f\u043e\u043b\u0443\u0447\u0430\u0435\u043c \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u0441\u043b\u0443\u0447\u0430\u0439\u043d\u0443\u044e \u043c\u0430\u0442\u0440\u0438\u0446\u0443.<\/p>\n<p>\u0427\u0442\u043e \u043d\u0430\u0441\u0447\u0435\u0442 \u0448\u0438\u0444\u0440\u043e\u0432\u0430\u043d\u0438\u044f\/\u0434\u0435\u0448\u0438\u0444\u0440\u043e\u0432\u0430\u043d\u0438\u044f? \u0421 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u0431\u044b\u0441\u0442\u0440\u043e\u0433\u043e \u043f\u0440\u0435\u043e\u0431\u0440\u0430\u0437\u043e\u0432\u0430\u043d\u0438\u044f \u0424\u0443\u0440\u044c\u0435, \u043c\u043e\u0436\u043d\u043e \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c \u043f\u0435\u0440\u0435\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u0435 2 \u043f\u043e\u043b\u0438\u043d\u043e\u043c\u043e\u0432 \u0437\u0430 , \u0447\u0442\u043e \u0437\u043d\u0430\u0447\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u0431\u044b\u0441\u0442\u0440\u0435\u0435 <\/p>\n<p>\u0417\u0430\u0434\u0430\u0447\u0430 \u043f\u043e\u043b\u0443\u0447\u0430\u0435\u0442\u0441\u044f \u0430\u043d\u0430\u043b\u043e\u0433\u0438\u0447\u043d\u043e\u0439 LWE \u0437\u0430 \u0438\u0441\u043a\u043b\u044e\u0447\u0435\u043d\u0438\u0435\u043c \u0442\u043e\u0433\u043e, \u0447\u0442\u043e \u0443\u0436\u0435 \u044f\u0432\u043b\u044f\u044e\u0442\u0441\u044f \u043f\u043e\u043b\u0438\u043d\u043e\u043c\u0430\u043c\u0438, \u0430 \u043d\u0435 \u043f\u0440\u043e\u0441\u0442\u043e \u0432\u0435\u043a\u0442\u043e\u0440\u0430\u043c\u0438. <\/p>\n<h2>6. \u041f\u0440\u043e\u0442\u043e\u043a\u043e\u043b NewHope<\/h2>\n<p>\u0415\u0441\u043b\u0438 \u043a\u0440\u0430\u0442\u043a\u043e \u0433\u043e\u0432\u043e\u0440\u0438\u0442\u044c, \u0442\u043e \u043f\u0440\u043e\u0442\u043e\u043a\u043e\u043b NewHope \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043c\u043e\u0434\u0438\u0444\u0438\u043a\u0430\u0446\u0438\u0435\u0439 \u043f\u0440\u043e\u0442\u043e\u043a\u043e\u043b\u0430 \u043e\u0431\u043c\u0435\u043d\u0430 \u043a\u043b\u044e\u0447\u0430\u043c\u0438, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u043e\u043f\u0438\u0441\u0430\u043b\u0438 \u0432 \u0441\u0432\u043e\u0435\u0439 \u0441\u0442\u0430\u0442\u044c\u0435 Bos, Castello, Naehrig \u0438 Stebila. \u041e\u043d\u0438 \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u043b\u0438 \u043e\u0431\u043c\u0435\u043d \u043a\u043b\u044e\u0447\u0430\u043c\u0438 \u0432 TLS \u0438\u0437 Ring-LWE.<\/p>\n<p>\u042f \u043d\u0435 \u0431\u0443\u0434\u0443 \u043f\u0440\u0438\u0432\u043e\u0434\u0438\u0442\u044c \u0434\u0435\u0442\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u044f \u0438\u0437\u043c\u0435\u043d\u0435\u043d\u0438\u0439 \u043c\u0435\u0436\u0434\u0443 \u044d\u0442\u0438\u043c\u0438 \u043f\u0440\u043e\u0442\u043e\u043a\u043e\u043b\u0430\u043c\u0438, \u0430 \u043e\u043f\u0438\u0448\u0443 \u043e\u0431\u0449\u0438\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0440\u0430\u0431\u043e\u0442\u044b \u0438 \u043c\u043e\u0442\u0438\u0432\u0430\u0446\u0438\u044e \u0432 \u0432\u044b\u0431\u043e\u0440\u0435 \u0442\u0435\u0445 \u0438\u043b\u0438 \u0438\u043d\u044b\u0445 \u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440\u043e\u0432 \u0432 \u043f\u0440\u043e\u0442\u043e\u043a\u043e\u043b\u0435 NewHope.<\/p>\n<p>\u0412 \u0434\u0430\u043d\u043d\u043e\u0439 \u0441\u0445\u0435\u043c\u0435 \u044f \u0431\u0443\u0434\u0443 \u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c\u0441\u044f \u043e\u0431\u043e\u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f\u043c\u0438, \u0432\u0432\u0435\u0434\u0451\u043d\u043d\u044b\u043c\u0438 \u0430\u0432\u0442\u043e\u0440\u0430\u043c\u0438 \u0441\u0442\u0430\u0442\u044c\u0438.<\/p>\n<figure class=\"full-width\"><figcaption><\/figcaption><\/figure>\n<p>\u0420\u0430\u0437\u0431\u0435\u0440\u0451\u043c \u0441\u0442\u0430\u0434\u0438\u0438 \u0438 \u0444\u0443\u043d\u043a\u0446\u0438\u0438 \u043f\u043e\u0434\u0440\u043e\u0431\u043d\u0435\u0435:<\/p>\n<p>\u0417\u0434\u0435\u0441\u044c \u0410\u043b\u0438\u0441\u0430 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0441\u0435\u0440\u0432\u0435\u0440\u043e\u043c, \u0430 \u0411\u043e\u0431 \u043a\u043b\u0438\u0435\u043d\u0442\u043e\u043c.<\/p>\n<ol>\n<li>\n<p>\u0412 \u043a\u0430\u0447\u0435\u0441\u0442\u0432\u0435 \u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440\u043e\u0432 \u0441\u0438\u0441\u0442\u0435\u043c\u044b n = 1024, q = 12289 (\u043d\u0430\u0438\u043c\u0435\u043d\u044c\u0448\u0435\u0435 \u043f\u0440\u043e\u0441\u0442\u043e\u0435, \u0434\u043b\u044f \u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e ). \u042d\u0442\u043e \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u0434\u043b\u044f \u0431\u044b\u0441\u0442\u0440\u043e\u0439 \u0440\u0430\u0431\u043e\u0442\u044b NTT (\u0432\u0430\u0440\u0438\u0430\u0446\u0438\u044f \u0434\u0438\u0441\u043a\u0440\u0435\u0442\u043d\u043e\u0433\u043e \u043f\u0440\u0435\u043e\u0431\u0440\u0430\u0437\u043e\u0432\u0430\u043d\u0438\u044f \u0424\u0443\u0440\u044c\u0435 \u0434\u043b\u044f \u043f\u043e\u043b\u0438\u043d\u043e\u043c\u043e\u0432), \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0442\u0440\u0435\u0431\u0443\u0435\u0442 n \u2013 \u0441\u0442\u0435\u043f\u0435\u043d\u0438 \u0434\u0432\u043e\u0439\u043a\u0438, q \u2013 \u043f\u0440\u043e\u0441\u0442\u043e\u0435 \u0447\u0438\u0441\u043b\u043e, \u043a\u043e\u0442\u043e\u0440\u043e\u0435 \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u0435\u0442 \u0443\u043a\u0430\u0437\u0430\u043d\u043d\u043e\u043c\u0443 \u0432\u044b\u0448\u0435 \u0442\u0440\u0435\u0431\u043e\u0432\u0430\u043d\u0438\u044e. \u0418\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442\u0441\u044f \u0440\u0435\u0448\u0451\u0442\u043a\u0430 <\/p>\n<\/li>\n<li>\n<p>\u0412 \u043d\u0430\u0447\u0430\u043b\u0435 \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u0441\u0433\u0435\u043d\u0435\u0440\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0441\u043b\u0443\u0447\u0430\u0439\u043d\u044b\u0439 \u043f\u043e\u043b\u0438\u043d\u043e\u043c <strong>a<\/strong>. \u041f\u0440\u043e\u0438\u0441\u0445\u043e\u0434\u0438\u0442 \u044d\u0442\u043e \u0442\u0430\u043a: \u0433\u0435\u043d\u0435\u0440\u0438\u0440\u0443\u0435\u0442\u0441\u044f seed \u2013 \u043f\u0441\u0435\u0432\u0434\u043e\u0441\u043b\u0443\u0447\u0430\u0439\u043d\u043e\u0435 \u0447\u0438\u0441\u043b\u043e \u0434\u043b\u0438\u043d\u043e\u0439 256 \u0431\u0438\u0442, \u0434\u0430\u043b\u0435\u0435 \u044d\u0442\u043e \u0447\u0438\u0441\u043b\u043e \u043f\u0440\u043e\u043f\u0443\u0441\u043a\u0430\u0435\u0442\u0441\u044f \u0447\u0435\u0440\u0435\u0437 \u0444\u0443\u043d\u043a\u0446\u0438\u044e SHAKE-128 (\u0432 \u0440\u0430\u0431\u043e\u0442\u0435 \u0430\u0432\u0442\u043e\u0440\u043e\u0432 \u0432 \u043a\u0430\u0447\u0435\u0441\u0442\u0432\u0435 \u0434\u0430\u043d\u043d\u043e\u0439 \u0444\u0443\u043d\u043a\u0446\u0438\u0438 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442\u0441\u044f SHA3). &nbsp;\u0417\u0430\u0442\u0435\u043c \u043d\u0430\u0447\u0438\u043d\u0430\u0435\u0442 \u0440\u0430\u0431\u043e\u0442\u0430\u0442\u044c \u043f\u0430\u0440\u0441\u0435\u0440, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0432\u044b\u0431\u0435\u0440\u0435\u0442 1024 \u043a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442\u0430 \u0432 \u043f\u043e\u043b\u0438\u043d\u043e\u043c <strong>a<\/strong>. \u041d\u0435\u0431\u043e\u043b\u044c\u0448\u0430\u044f \u0440\u0435\u043c\u0430\u0440\u043a\u0430: \u043d\u0435\u0441\u043c\u043e\u0442\u0440\u044f \u043d\u0430 \u0442\u043e, \u0447\u0442\u043e TLS \u0438\u043c\u0435\u0435\u0442 \u043a\u044d\u0448\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435 \u043a\u043b\u044e\u0447\u0435\u0439 \u043d\u0430 \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u043e\u0435 \u0432\u0440\u0435\u043c\u044f (\u0432 \u0440\u0430\u0439\u043e\u043d\u0435 2 \u0447\u0430\u0441\u043e\u0432), \u0430\u0432\u0442\u043e\u0440\u044b \u043f\u0440\u043e\u0442\u043e\u043a\u043e\u043b\u0430 NewHope \u0432\u044b\u0441\u0442\u0443\u043f\u0438\u043b\u0438 \u043f\u0440\u043e\u0442\u0438\u0432 \u044d\u0442\u043e\u0433\u043e, \u0438 \u043f\u043e \u0443\u043c\u043e\u043b\u0447\u0430\u043d\u0438\u044e \u0434\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u043d\u043e\u0432\u043e\u0433\u043e \u0441\u043e\u0435\u0434\u0438\u043d\u0435\u043d\u0438\u044f \u0433\u0435\u043d\u0435\u0440\u0438\u0440\u0443\u0435\u0442\u0441\u044f \u0441\u0432\u043e\u0439 \u043f\u043e\u043b\u0438\u043d\u043e\u043c <strong>a<\/strong>. \u041f\u043e \u0438\u0445 \u043c\u043d\u0435\u043d\u0438\u044e, \u044d\u0442\u043e \u0443\u043c\u0435\u043d\u044c\u0448\u0430\u0435\u0442 \u0448\u0430\u043d\u0441 \u043d\u0430 backdoor \u0438 \u0432\u043e\u0437\u043d\u0438\u043a\u043d\u043e\u0432\u0435\u043d\u0438\u044f \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u044b, \u0447\u0442\u043e \u0432\u0441\u0435 \u0441\u043e\u0435\u0434\u0438\u043d\u0435\u043d\u0438\u044f \u0431\u0443\u0434\u0443\u0442 \u043f\u043e\u043b\u0430\u0433\u0430\u0442\u044c\u0441\u044f \u043d\u0430 \u0435\u0434\u0438\u043d\u0441\u0442\u0432\u0435\u043d\u043d\u044b\u0439 \u201c\u044d\u043a\u0437\u0435\u043c\u043f\u043b\u044f\u0440\u201d \u0437\u0430\u0434\u0430\u0447\u0438 \u0432 \u0440\u0435\u0448\u0451\u0442\u043a\u0430\u0445.<\/p>\n<\/li>\n<li>\n<p>\u0424\u0443\u043d\u043a\u0446\u0438\u044f \u0440\u0430\u0441\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u0435 \u043e\u0448\u0438\u0431\u043e\u043a \u2013 \u0431\u0438\u043d\u043e\u043c\u0438\u043d\u0430\u043b\u044c\u043d\u043e\u0435, \u0446\u0435\u043d\u0442\u0440\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0435. \u042d\u0442\u043e \u0441\u0434\u0435\u043b\u0430\u043d\u043e \u0438\u0437-\u0437\u0430 \u0442\u043e\u0433\u043e, \u0447\u0442\u043e \u043c\u043e\u0434\u0435\u043b\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u043d\u043e\u0440\u043c\u0430\u043b\u044c\u043d\u043e\u0435 \u0440\u0430\u0441\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u0435 \u0434\u043e\u0432\u043e\u043b\u044c\u043d\u043e \u0437\u0430\u0442\u0440\u0430\u0442\u043d\u043e \u0438 \u043d\u0435 \u043d\u0443\u0436\u043d\u043e \u0445\u0440\u0430\u043d\u0438\u0442\u044c \u0442\u0430\u0431\u043b\u0438\u0446\u044b \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u044b\u0445 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439 (\u0447\u0442\u043e \u0438\u0441\u043a\u043b\u044e\u0447\u0430\u0435\u0442 \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0442\u0438\u043f\u044b \u0430\u0442\u0430\u043a). \u0417\u0434\u0435\u0441\u044c \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d \u043f\u0441\u0435\u0432\u0434\u043e\u0441\u043b\u0443\u0447\u0430\u0439\u043d\u044b\u0439 \u0433\u0435\u043d\u0435\u0440\u0430\u0442\u043e\u0440 \u0441 seed \u0438\u0437 \/dev\/urandom \u0441 \u043f\u043e\u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u043c \u0431\u044b\u0441\u0442\u0440\u044b\u043c \u0441\u0443\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435\u043c 16-\u0431\u0438\u0442\u043e\u0432\u044b\u0445 \u0431\u043b\u043e\u043a\u043e\u0432 \u0432\u044b\u0432\u043e\u0434\u0430. \u0412\u044b\u0431\u043e\u0440\u043a\u043e\u0439 \u0438\u0437 \u043d\u0435\u0435 \u043f\u043e\u043b\u0443\u0447\u0430\u0435\u043c \u043a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442\u044b \u0434\u043b\u044f \u0441\u0435\u043a\u0440\u0435\u0442\u043d\u043e\u0433\u043e \u043f\u043e\u043b\u0438\u043d\u043e\u043c\u0430 s \u0438 \u043f\u043e\u043b\u0438\u043d\u043e\u043c\u0430 \u043e\u0448\u0438\u0431\u043e\u043a e.<\/p>\n<\/li>\n<li>\n<p>\u041f\u0435\u0440\u0435\u0441\u044b\u043b\u0430\u0435\u0442\u0441\u044f \u043f\u0430\u0440\u0430 (\u043e\u0442\u043a\u0440\u044b\u0442\u044b\u0439 \u043a\u043b\u044e\u0447 b, seed).<\/p>\n<\/li>\n<li>\n<p>\u041d\u0430 \u0441\u0442\u043e\u0440\u043e\u043d\u0435 \u043a\u043b\u0438\u0435\u043d\u0442\u0430 \u0442\u0430\u043a\u0436\u0435 \u0433\u0435\u043d\u0435\u0440\u0438\u0440\u0443\u0435\u0442\u0441\u044f \u043f\u043e\u043b\u0438\u043d\u043e\u043c a, \u043f\u043e\u043b\u0438\u043d\u043e\u043c\u044b s\u2019, e\u2019, e\u201d, \u0432\u044b\u0447\u0438\u0441\u043b\u044f\u0435\u0442\u0441\u044f \u043e\u0442\u043a\u0440\u044b\u0442\u044b\u0439 \u043a\u043b\u044e\u0447 u.<\/p>\n<\/li>\n<li>\n<p>\u0414\u0430\u043b\u044c\u0448\u0435 \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c \u043f\u043e\u043b\u0438\u043d\u043e\u043c v, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0434\u043e\u043b\u0436\u0435\u043d \u0431\u044b\u0442\u044c \u043e\u0434\u0438\u043d\u0430\u043a\u043e\u0432\u044b\u043c \u0438 \u0434\u043b\u044f \u043a\u043b\u0438\u0435\u043d\u0442\u0430, \u0438 \u0434\u043b\u044f \u0441\u0435\u0440\u0432\u0435\u0440\u0430. \u041e\u0434\u043d\u0430\u043a\u043e \u0441 \u044d\u0442\u0438\u043c \u0432\u043e\u0437\u043d\u0438\u043a\u0430\u044e\u0442 \u0442\u0440\u0443\u0434\u043d\u043e\u0441\u0442\u0438. \u041d\u0430 \u0441\u0442\u043e\u0440\u043e\u043d\u0435 \u043a\u043b\u0438\u0435\u043d\u0442\u0430 \u043f\u043e\u043b\u0443\u0447\u0430\u0435\u0442\u0441\u044f , \u043d\u0430 \u0441\u0442\u043e\u0440\u043e\u043d\u0435 \u0441\u0435\u0440\u0432\u0435\u0440\u0430 , \u0432 \u0438\u0442\u043e\u0433\u0435 \u043d\u0430\u043a\u0430\u043f\u043b\u0438\u0432\u0430\u0435\u0442\u0441\u044f \u043f\u043e\u0433\u0440\u0435\u0448\u043d\u043e\u0441\u0442\u044c \u043c\u0435\u0436\u0434\u0443 \u043f\u043e\u043b\u0438\u043d\u043e\u043c\u0430\u043c\u0438, \u043a\u043e\u0442\u043e\u0440\u0443\u044e \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u0438\u0441\u043f\u0440\u0430\u0432\u0438\u0442\u044c. \u0415\u0441\u043b\u0438 \u043f\u043e\u043c\u043d\u0438\u0442\u0435, \u0440\u0430\u0437\u043b\u0438\u0447\u0435\u043d\u0438\u0435 \u043f\u0435\u0440\u0435\u0434\u0430\u043d\u043d\u043e\u0433\u043e \u0431\u0438\u0442\u0430 \u2013 \u044d\u0442\u043e \u0442\u043e, \u043d\u0430\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u0431\u043b\u0438\u0437\u043a\u043e \u043a 0 \u0438\u043b\u0438 . \u0421\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0435\u043d\u043d\u043e, \u0431\u043e\u043b\u044c\u0448\u0430\u044f \u043f\u043e\u0433\u0440\u0435\u0448\u043d\u043e\u0441\u0442\u044c \u043c\u043e\u0436\u0435\u0442 \u043f\u0440\u0438\u0432\u0435\u0441\u0442\u0438 \u043a \u0438\u0441\u043a\u0430\u0436\u0435\u043d\u0438\u044e \u0441\u043e\u043e\u0431\u0449\u0435\u043d\u0438\u044f. <\/p>\n<\/li>\n<li>\n<p>\u0412\u044b\u043f\u043e\u043b\u043d\u0438\u043c \u043a\u043e\u0440\u0440\u0435\u043a\u0446\u0438\u044e \u043e\u0448\u0438\u0431\u043a\u0438. \u0414\u043b\u044f \u043d\u0430\u0447\u0430\u043b\u0430 \u0432\u0435\u0440\u043d\u0435\u043c\u0441\u044f \u043e\u0442 \u043f\u043e\u043b\u0438\u043d\u043e\u043c\u043e\u0432 \u043a \u0432\u0435\u043a\u0442\u043e\u0440\u0430\u043c: \u043a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442\u044b \u043f\u043e\u043b\u0438\u043d\u043e\u043c\u0430 \u0431\u0443\u0434\u0443\u0442 \u043a\u043e\u043e\u0440\u0434\u0438\u043d\u0430\u0442\u0430\u043c\u0438 \u0432\u0435\u043a\u0442\u043e\u0440\u0430. \u0420\u0430\u0437\u0434\u0435\u043b\u0438\u043c \u0438\u0445 \u043d\u0430 q \u0438 \u0442\u0430\u043a\u0438\u043c<\/p>\n<\/li>\n<\/ol>\n<p><\/s><\/s><\/s><\/p>\n<\/p>\n<\/div>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[],"tags":[],"class_list":["post-314748","post","type-post","status-publish","format-standard","hentry"],"_links":{"self":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/314748","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=314748"}],"version-history":[{"count":0,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/314748\/revisions"}],"wp:attachment":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=314748"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=314748"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=314748"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}