[{"@context":"http:\/\/schema.org\/","@type":"BlogPosting","@id":"https:\/\/wiki.edu.vn\/jp\/wiki5\/archives\/3023#BlogPosting","mainEntityOfPage":"https:\/\/wiki.edu.vn\/jp\/wiki5\/archives\/3023","headline":"\u30de\u30c3\u30af\u30a8\u30ea\u30b9\u6697\u53f7 – Wikipedia","name":"\u30de\u30c3\u30af\u30a8\u30ea\u30b9\u6697\u53f7 – Wikipedia","description":"\u30de\u30c3\u30af\u30a8\u30ea\u30b9\u6697\u53f7\uff08McEliece_cryptosystem\uff09\u306f\u3001\u6697\u53f7\u7406\u8ad6\u306b\u304a\u3044\u3066\uff0c\u516c\u958b\u9375\u6697\u53f7\u65b9\u5f0f\u306e\u4e00\u3064\u3067\u3042\u308a\uff0c1978\u5e74\u306b\u30ed\u30d0\u30fc\u30c8\u30fb\u30de\u30c3\u30af\u30a8\u30ea\u30b9\uff08Robert McEliece\uff09\u306b\u3088\u3063\u3066\u63d0\u6848\u3055\u308c\u305f[1]\u3002 \u3053\u306e\u6697\u53f7\u65b9\u5f0f\u306f\uff0c\u6700\u521d\u306e\u78ba\u7387\u7684\u306a\u6697\u53f7\u65b9\u5f0f\u3067\u3042\u308a\uff0c\u4e00\u3064\u306e\u5e73\u6587\u304b\u3089\u7570\u306a\u308b\u6697\u53f7\u6587\u304c\u751f\u6210\u3055\u308c\u308b\uff0e\u3053\u306e\u6697\u53f7\u65b9\u5f0f\u306f\u6697\u53f7\u30b3\u30df\u30e5\u30cb\u30c6\u30a3\u306b\u304a\u3044\u3066\u3042\u307e\u308a\u6ce8\u76ee\u3092\u6d74\u3073\u3066\u3053\u306a\u304b\u3063\u305f\u304c\uff0c\u30b7\u30e7\u30a2\u306e\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u3092\u7528\u3044\u305f\u653b\u6483\u3067\u7834\u308b\u3053\u3068\u304c\u3067\u304d\u306a\u3044\u305f\u3081\uff0c\u8010\u91cf\u5b50\u6697\u53f7\u306e\u5019\u88dc\u306e\u4e00\u3064\u3068\u306a\u3063\u3066\u3044\u308b[2]\uff0e \u3053\u306e\u6697\u53f7\u65b9\u5f0f\u306f\uff0c\u7dda\u5f62\u7b26\u53f7\u306e\u5fa9\u53f7\u56f0\u96e3\u6027\uff08\u3053\u308c\u306fNP\u56f0\u96e3\u3067\u3042\u308b\u3053\u3068\u304c\u77e5\u3089\u308c\u3066\u3044\u308b\uff09\u306b\u57fa\u3065\u3044\u3066\u3044\u308b[3]\uff0e\u5fa9\u53f7\u306b\u7528\u3044\u3089\u308c\u308b\u79d8\u5bc6\u9375\u306f\uff0c\u52b9\u7387\u7684\u306b\u5fa9\u53f7\u53ef\u80fd\u3067 t{displaystyle t} \u500b\u306e\u30a8\u30e9\u30fc\u3092\u8a02\u6b63\u53ef\u80fd\u306a\u8aa4\u308a\u8a02\u6b63\u7b26\u53f7\u3067\u3042\u308b\uff0e\u30de\u30c3\u30af\u30a8\u30ea\u30b9\u306b\u3088\u308b\u30aa\u30ea\u30b8\u30ca\u30eb\u306e\u65b9\u5f0f\u306f\uff0c\u4e8c\u5143\u30b4\u30c3\u30d1\u7b26\u53f7\uff08\u6a19\u6570\u304c\uff12\u3067\u3042\u308b\u6709\u9650\u4f53\u4e0a\u306e\u7a2e\u65700\u306e\u66f2\u7dda\u3067\u5b9a\u7fa9\u3055\u308c\u308b\u30b4\u30c3\u30d1\u7b26\u53f7\uff09\u3092\u7528\u3044\u3066\u3044\u308b\uff0e\u3053\u306e\u7b26\u53f7\u306fPatterson\u306b\u3088\u308b\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u306b\u3088\u308a\uff0c\u52b9\u7387\u7684\u306b\u5fa9\u53f7\u3067\u304d\u308b\uff0e[4] \u6697\u53f7\u5316\u306b\u7528\u3044\u308b\u516c\u958b\u9375\u306f\uff0c\u79d8\u5bc6\u9375\u3067\u3042\u308b\u7b26\u53f7\u3092\u4e00\u822c\u7684\u306a\u7dda\u5f62\u7b26\u53f7\u306b\u300c\u507d\u88c5\u300d\u3059\u308b\u3053\u3068\u3067\u5f97\u3089\u308c\u308b\uff0e\u3053\u306e\u305f\u3081\u306b\uff0c\u7b26\u53f7\u306e\u751f\u6210\u884c\u5217 G{displaystyle G} \u3092\uff0c\u4e8c\u3064\u306e\u30e9\u30f3\u30c0\u30e0\u306b\u9078\u3070\u308c\u305f\u53ef\u9006\u884c\u5217 S{displaystyle S} \u3068 P{displaystyle P} \u306b\u3088\u3063\u3066\u652a\u4e71\u3059\u308b\uff0e\uff08\u5177\u4f53\u7684\u306a\u65b9\u6cd5\u306b\u3064\u3044\u3066\u306f\u4e0b\u3092\u53c2\u7167\u306e\u3053\u3068\uff0e\uff09 \u3053\u306e\u6697\u53f7\u5316\u65b9\u5f0f\u306b\u306f\uff0c\u5225\u306e\u7b26\u53f7\u3092\u7528\u3044\u305f\u8907\u6570\u306e\u30d0\u30ea\u30a8\u30fc\u30b7\u30e7\u30f3\u304c\u5b58\u5728\u3059\u308b\u304c\uff0c\u591a\u304f\u306f\u5b89\u5168\u6027\u304c\u4f4e\u304f\uff0c\u69cb\u9020\u7684\u653b\u6483\u306b\u3088\u3063\u3066\u7834\u308b\u3053\u3068\u304c\u3067\u304d\u308b\uff0e \u30b4\u30c3\u30d1\u7b26\u53f7\u3092\u7528\u3044\u305f\u30de\u30c3\u30af\u30a8\u30ea\u30b9\u6697\u53f7\u306f\u73fe\u5728\u306e\u3068\u3053\u308d\u89e3\u8aad\u3055\u308c\u3066\u3044\u306a\u3044\uff0e\u6700\u3082\u52b9\u7387\u306e\u826f\u3044\u653b\u6483\u65b9\u6cd5\u3068\u3057\u3066\u77e5\u3089\u308c\u3066\u3044\u308b\u306e\u306f information-set","datePublished":"2021-12-30","dateModified":"2021-12-30","author":{"@type":"Person","@id":"https:\/\/wiki.edu.vn\/jp\/wiki5\/archives\/author\/lordneo#Person","name":"lordneo","url":"https:\/\/wiki.edu.vn\/jp\/wiki5\/archives\/author\/lordneo","image":{"@type":"ImageObject","@id":"https:\/\/secure.gravatar.com\/avatar\/c9645c498c9701c88b89b8537773dd7c?s=96&d=mm&r=g","url":"https:\/\/secure.gravatar.com\/avatar\/c9645c498c9701c88b89b8537773dd7c?s=96&d=mm&r=g","height":96,"width":96}},"publisher":{"@type":"Organization","name":"Enzyklop\u00e4die","logo":{"@type":"ImageObject","@id":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","url":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","width":600,"height":60}},"image":{"@type":"ImageObject","@id":"https:\/\/wikimedia.org\/api\/rest_v1\/media\/math\/render\/svg\/65658b7b223af9e1acc877d848888ecdb4466560","url":"https:\/\/wikimedia.org\/api\/rest_v1\/media\/math\/render\/svg\/65658b7b223af9e1acc877d848888ecdb4466560","height":"","width":""},"url":"https:\/\/wiki.edu.vn\/jp\/wiki5\/archives\/3023","about":["Wiki"],"wordCount":8891,"articleBody":"\u30de\u30c3\u30af\u30a8\u30ea\u30b9\u6697\u53f7\uff08McEliece_cryptosystem\uff09\u306f\u3001\u6697\u53f7\u7406\u8ad6\u306b\u304a\u3044\u3066\uff0c\u516c\u958b\u9375\u6697\u53f7\u65b9\u5f0f\u306e\u4e00\u3064\u3067\u3042\u308a\uff0c1978\u5e74\u306b\u30ed\u30d0\u30fc\u30c8\u30fb\u30de\u30c3\u30af\u30a8\u30ea\u30b9\uff08Robert McEliece\uff09\u306b\u3088\u3063\u3066\u63d0\u6848\u3055\u308c\u305f[1]\u3002 \u3053\u306e\u6697\u53f7\u65b9\u5f0f\u306f\uff0c\u6700\u521d\u306e\u78ba\u7387\u7684\u306a\u6697\u53f7\u65b9\u5f0f\u3067\u3042\u308a\uff0c\u4e00\u3064\u306e\u5e73\u6587\u304b\u3089\u7570\u306a\u308b\u6697\u53f7\u6587\u304c\u751f\u6210\u3055\u308c\u308b\uff0e\u3053\u306e\u6697\u53f7\u65b9\u5f0f\u306f\u6697\u53f7\u30b3\u30df\u30e5\u30cb\u30c6\u30a3\u306b\u304a\u3044\u3066\u3042\u307e\u308a\u6ce8\u76ee\u3092\u6d74\u3073\u3066\u3053\u306a\u304b\u3063\u305f\u304c\uff0c\u30b7\u30e7\u30a2\u306e\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u3092\u7528\u3044\u305f\u653b\u6483\u3067\u7834\u308b\u3053\u3068\u304c\u3067\u304d\u306a\u3044\u305f\u3081\uff0c\u8010\u91cf\u5b50\u6697\u53f7\u306e\u5019\u88dc\u306e\u4e00\u3064\u3068\u306a\u3063\u3066\u3044\u308b[2]\uff0e\u3053\u306e\u6697\u53f7\u65b9\u5f0f\u306f\uff0c\u7dda\u5f62\u7b26\u53f7\u306e\u5fa9\u53f7\u56f0\u96e3\u6027\uff08\u3053\u308c\u306fNP\u56f0\u96e3\u3067\u3042\u308b\u3053\u3068\u304c\u77e5\u3089\u308c\u3066\u3044\u308b\uff09\u306b\u57fa\u3065\u3044\u3066\u3044\u308b[3]\uff0e\u5fa9\u53f7\u306b\u7528\u3044\u3089\u308c\u308b\u79d8\u5bc6\u9375\u306f\uff0c\u52b9\u7387\u7684\u306b\u5fa9\u53f7\u53ef\u80fd\u3067t{displaystyle t} \u500b\u306e\u30a8\u30e9\u30fc\u3092\u8a02\u6b63\u53ef\u80fd\u306a\u8aa4\u308a\u8a02\u6b63\u7b26\u53f7\u3067\u3042\u308b\uff0e\u30de\u30c3\u30af\u30a8\u30ea\u30b9\u306b\u3088\u308b\u30aa\u30ea\u30b8\u30ca\u30eb\u306e\u65b9\u5f0f\u306f\uff0c\u4e8c\u5143\u30b4\u30c3\u30d1\u7b26\u53f7\uff08\u6a19\u6570\u304c\uff12\u3067\u3042\u308b\u6709\u9650\u4f53\u4e0a\u306e\u7a2e\u65700\u306e\u66f2\u7dda\u3067\u5b9a\u7fa9\u3055\u308c\u308b\u30b4\u30c3\u30d1\u7b26\u53f7\uff09\u3092\u7528\u3044\u3066\u3044\u308b\uff0e\u3053\u306e\u7b26\u53f7\u306fPatterson\u306b\u3088\u308b\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u306b\u3088\u308a\uff0c\u52b9\u7387\u7684\u306b\u5fa9\u53f7\u3067\u304d\u308b\uff0e[4] \u6697\u53f7\u5316\u306b\u7528\u3044\u308b\u516c\u958b\u9375\u306f\uff0c\u79d8\u5bc6\u9375\u3067\u3042\u308b\u7b26\u53f7\u3092\u4e00\u822c\u7684\u306a\u7dda\u5f62\u7b26\u53f7\u306b\u300c\u507d\u88c5\u300d\u3059\u308b\u3053\u3068\u3067\u5f97\u3089\u308c\u308b\uff0e\u3053\u306e\u305f\u3081\u306b\uff0c\u7b26\u53f7\u306e\u751f\u6210\u884c\u5217 G{displaystyle G} \u3092\uff0c\u4e8c\u3064\u306e\u30e9\u30f3\u30c0\u30e0\u306b\u9078\u3070\u308c\u305f\u53ef\u9006\u884c\u5217 S{displaystyle S} \u3068 P{displaystyle P}  \u306b\u3088\u3063\u3066\u652a\u4e71\u3059\u308b\uff0e\uff08\u5177\u4f53\u7684\u306a\u65b9\u6cd5\u306b\u3064\u3044\u3066\u306f\u4e0b\u3092\u53c2\u7167\u306e\u3053\u3068\uff0e\uff09\u3053\u306e\u6697\u53f7\u5316\u65b9\u5f0f\u306b\u306f\uff0c\u5225\u306e\u7b26\u53f7\u3092\u7528\u3044\u305f\u8907\u6570\u306e\u30d0\u30ea\u30a8\u30fc\u30b7\u30e7\u30f3\u304c\u5b58\u5728\u3059\u308b\u304c\uff0c\u591a\u304f\u306f\u5b89\u5168\u6027\u304c\u4f4e\u304f\uff0c\u69cb\u9020\u7684\u653b\u6483\u306b\u3088\u3063\u3066\u7834\u308b\u3053\u3068\u304c\u3067\u304d\u308b\uff0e\u30b4\u30c3\u30d1\u7b26\u53f7\u3092\u7528\u3044\u305f\u30de\u30c3\u30af\u30a8\u30ea\u30b9\u6697\u53f7\u306f\u73fe\u5728\u306e\u3068\u3053\u308d\u89e3\u8aad\u3055\u308c\u3066\u3044\u306a\u3044\uff0e\u6700\u3082\u52b9\u7387\u306e\u826f\u3044\u653b\u6483\u65b9\u6cd5\u3068\u3057\u3066\u77e5\u3089\u308c\u3066\u3044\u308b\u306e\u306f information-set decoding\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u3092\u7528\u3044\u308b\u3082\u306e\u3067\u3042\u308b\uff0e2008\u5e74\u306e\u8ad6\u6587\u306b\u306f\uff0c\u653b\u6483\u624b\u6cd5\u3068\u4fee\u6b63\u65b9\u6cd5\u304c\u793a\u3055\u308c\u3066\u3044\u308b\uff0e[5] \u5225\u306e\u8ad6\u6587\u3067\u306f\uff0c\u91cf\u5b50\u30b3\u30f3\u30d4\u30e5\u30fc\u30bf\u306b\u5bfe\u3057\u3066\u5b89\u5168\u306b\u3059\u308b\u305f\u3081\u306b\u306f\uff0c\u9375\u30b5\u30a4\u30ba\u3092\uff14\u500d\u306b\u5ef6\u3070\u3059\u5fc5\u8981\u304c\u3042\u308b\u3053\u3068\u304c\u793a\u3055\u308c\u3066\u3044\u308b\uff0e\u3053\u308c\u306f\uff0c \u91cf\u5b50\u30b3\u30f3\u30d4\u30e5\u30fc\u30bf\u306b\u3088\u3063\u3066 information set decoding \u304c\u52b9\u7387\u5316\u3067\u304d\u308b\u304b\u3089\u3067\u3042\u308b.[6]\u30de\u30c3\u30af\u30a8\u30ea\u30b9\u6697\u53f7\u306e\u5229\u70b9 — \u4f8b\u3048\u3070RSA\u6697\u53f7\u306a\u3069\u3068\u6bd4\u8f03\u3057\u3066 — \u3068\u3057\u3066\uff0c\u6697\u53f7\u5316\u3068\u5fa9\u53f7\u304c\u901f\u3044\u3053\u3068\u304c\u6319\u3052\u3089\u308c\u308b\uff0e[7] \u9577\u3044\u9593\uff0c\u30de\u30c3\u30af\u30a8\u30ea\u30b9\u6697\u53f7\u3067 \u30c7\u30b8\u30bf\u30eb\u7f72\u540d \u306f\u751f\u6210\u3067\u304d\u306a\u3044\u3060\u308d\u3046\u3068\u8003\u3048\u3089\u308c\u3066\u304d\u305f\uff0e\u3057\u304b\u3057\uff0c\u30de\u30c3\u30af\u30a8\u30ea\u30b9\u6697\u53f7\u306e\u53cc\u5bfe\u7248\u3067\u3042\u308bNiederreiter\u6697\u53f7\u3092\u7528\u3044\u308b\u3068\u7f72\u540d\u65b9\u5f0f\u3092\u69cb\u7bc9\u3059\u308b\u3053\u3068\u304c\u3067\u304d\u308b\uff0e\u30de\u30c3\u30af\u30a8\u30ea\u30b9\u6697\u53f7\u306e\u4e00\u756a\u5927\u304d\u306a\u6b20\u70b9\u306f\uff0c\u516c\u958b\u9375\u3068\u79d8\u5bc6\u9375\u304c\u5927\u304d\u306a\u884c\u5217\u3067\u3042\u308b\u3053\u3068\u3067\u3042\u308b\uff0e\u6a19\u6e96\u7684\u306a\u30d1\u30e9\u30e1\u30fc\u30bf\u306b\u304a\u3044\u3066\u306f\uff0c\u516c\u958b\u9375\u306f512KB\uff08\u30ad\u30ed\u30d0\u30a4\u30c8\uff09\u3067\u3042\u308b\uff0e\u6697\u53f7\u5316\u65b9\u5f0f[\u7de8\u96c6]\u30de\u30c3\u30af\u30a8\u30ea\u30b9\u6697\u53f7\u306f\uff0c\u9375\u3092\u751f\u6210\u3059\u308b\u78ba\u7387\u7684\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\uff0c\u6697\u53f7\u5316\u3092\u3059\u308b\u78ba\u7387\u7684\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\uff0c\u5fa9\u53f7\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u306e\uff0c\uff13\u3064\u306e\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u304b\u3089\u6210\u308b\uff0e\u30de\u30c3\u30af\u30a8\u30ea\u30b9\u6697\u53f7\u3092\u7528\u3044\u308b\u5168\u3066\u306e\u30e6\u30fc\u30b6\u306f\uff0c\u5171\u901a\u306e\u30bb\u30ad\u30e5\u30ea\u30c6\u30a3\u30d1\u30e9\u30e1\u30fc\u30bf n,k,t{displaystyle n,k,t} \u3092\u7528\u3044\u308b\uff0e\u9375\u751f\u6210[\u7de8\u96c6]\u6697\u53f7\u306e\u539f\u7406\u306f\uff0c\u9375\u751f\u6210\u8005\u30a2\u30ea\u30b9\u304c\uff0c\u52b9\u7387\u7684\u306a\u5fa9\u53f7\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u304c\u5206\u304b\u3063\u3066\u3044\u308b\u7b26\u53f7 C{displaystyle C} \u3092\uff08\u4f55\u3089\u304b\u306e\u7dda\u5f62\u7b26\u53f7\u306e\u65cf\u304b\u3089\uff09\u9078\u3073\uff0c\u7b26\u53f7 C{displaystyle C} \u3092\u516c\u958b\u3059\u308b\u304c\u5fa9\u53f7\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u306f\u79d8\u5bc6\u306b\u4fdd\u3064\uff0c\u3068\u3044\u3046\u3082\u306e\u3067\u3042\u308b\uff0e\u7b26\u53f7C{displaystyle C}\u306e\u5fa9\u53f7\u306b\u306f\uff0c\u7b26\u53f7C{displaystyle C}\u306e\u751f\u6210\u884c\u5217\u306e\u77e5\u8b58\u3060\u3051\u3067\u306f\u306a\u304f\uff0c\u7b26\u53f7\u306e\u65cf\u304b\u3089C{displaystyle C}\u3092\u9078\u3073\u51fa\u3057\u305f\u3068\u304d\u306b\u7528\u3044\u305f\u30d1\u30e9\u30e1\u30fc\u30bf\u3092\u5fc5\u8981\u3068\u3059\u308b\uff0e\u4f8b\u3048\u3070\uff0c\u4e8c\u5143\u30b4\u30c3\u30d1\u7b26\u53f7\u306b\u304a\u3044\u3066\u306f\uff0c\u5fa9\u53f7\u306b\u306f\u30b4\u30c3\u30d1\u591a\u9805\u5f0f\u3068code locators\u304c\u5fc5\u8981\u3067\u3042\u308b\uff0e\u3057\u305f\u304c\u3063\u3066\uff0c\u30a2\u30ea\u30b9\u306f\u9069\u5207\u306b\u96e3\u8aad\u5316\u3055\u308c\u305f C{displaystyle C}\u306e\u751f\u6210\u884c\u5217\u3092\u516c\u958b\u3059\u308b\u3053\u3068\u304c\u3067\u304d\u308b\uff0e\u3088\u308a\u5177\u4f53\u7684\u306b\u306f\uff0c\u9375\u306f\u4ee5\u4e0b\u306e\u3088\u3046\u306b\u751f\u6210\u3055\u308c\u308b\uff0e\u30a2\u30ea\u30b9\u306f\uff0c\u4f55\u3089\u304b\u306e\u7b26\u53f7\u306e\u65cf\uff08\u4f8b\u3048\u3070\uff0c\u4e8c\u5143\u30b4\u30c3\u30d1\u7b26\u53f7\uff0e\u3053\u306e\u65cf\u306b\u306f\u591a\u6570\u306e\u7b26\u53f7\u304c\u542b\u307e\u308c\u3066\u3044\u308b\u5fc5\u8981\u304c\u3042\u308b\uff0e\uff09\u304b\u3089\uff0ct{displaystyle t}\u30d3\u30c3\u30c8\u8aa4\u308a\u3092\u52b9\u7387\u7684\u306b\u8a02\u6b63\u53ef\u80fd\u306a\u4e8c\u5143(n,k){displaystyle (n,k)}-\u7b26\u53f7 C{displaystyle C}  \u3092\u9078\u3076\uff0e\u52b9\u7387\u7684\u306a\u5fa9\u53f7\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u3092 A{displaystyle A} \u3068\u3059\u308b\uff0e\u307e\u305f\uff0c\u7b26\u53f7C{displaystyle C} \u306e\u751f\u6210\u884c\u5217\uff08\u306e\u4e00\u3064\uff09\u3092 G{displaystyle G} \u3068\u3059\u308b\uff0e\u7dda\u5f62\u7b26\u53f7\u306f\u591a\u304f\u306e\u751f\u6210\u884c\u5217\u3092\u6301\u3064\u304c\uff0c\u5927\u62b5\u306e\u5834\u5408\uff0c\u81ea\u7136\u306a\u751f\u6210\u884c\u5217\u306e\u9078\u629e\u304c\u5b58\u5728\u3059\u308b\uff0e\u305d\u306e\u3088\u3046\u306a\u751f\u6210\u884c\u5217\u306f A{displaystyle A} \u3092\u660e\u3089\u304b\u306b\u3057\u3066\u3057\u307e\u3046\u5834\u5408\u304c\u3042\u308b\u305f\u3081\uff0c\u79d8\u5bc6\u306b\u3057\u3066\u304a\u304b\u306a\u3051\u308c\u3070\u306a\u3089\u306a\u3044\uff0e\u30a2\u30ea\u30b9\u306f\uff0ck\u00d7k{displaystyle ktimes k} \u306e\u6b63\u5247\u884c\u5217 S{displaystyle S} \u3092\u30e9\u30f3\u30c0\u30e0\u306b\u9078\u3076\uff0e\u30a2\u30ea\u30b9\u306f n\u00d7n{displaystyle ntimes n} \u306e\u7f6e\u63db\u884c\u5217 P{displaystyle P} \u3092\u30e9\u30f3\u30c0\u30e0\u306b\u9078\u3076\uff0e\u30a2\u30ea\u30b9\u306f k\u00d7n{displaystyle ktimes n} \u884c\u5217 G^=SGP{displaystyle {hat {G}}=SGP} \u3092\u8a08\u7b97\u3059\u308b\uff0e\u30a2\u30ea\u30b9\u306e\u516c\u958b\u9375\u306f (G^,t){displaystyle ({hat {G}},t)} \u3067\u3042\u308a\uff0c\u79d8\u5bc6\u9375\u306f (S,P,A){displaystyle (S,P,A)} \u3067\u3042\u308b\uff0e\u306a\u304a\uff0c\u5fa9\u53f7\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0 A{displaystyle A} \u306f\u7b26\u53f7 C{displaystyle C} \u306e\u9078\u629e\u306b\u4f7f\u3063\u305f\u30d1\u30e9\u30e1\u30fc\u30bf\u306b\u3088\u3063\u3066\u5b9a\u307e\u308b\u305f\u3081\uff0c\u3053\u306e\u30d1\u30e9\u30e1\u30fc\u30bf\u306e\u307f\u3092\u8a18\u61b6\u3059\u308c\u3070\u826f\u3044\uff0e\u6697\u53f7\u5316[\u7de8\u96c6]\u30dc\u30d6\u304c\u30e1\u30c3\u30bb\u30fc\u30b8 m{displaystyle m} \u3092\u30a2\u30ea\u30b9\u306b\u9001\u308a\u305f\u3044\u3068\u3057\u3088\u3046\uff0e\u30a2\u30ea\u30b9\u306e\u516c\u958b\u9375\uff1d\u6697\u53f7\u5316\u306e\u305f\u3081\u306e\u9375\u304c (G^,t){displaystyle ({hat {G}},t)} \u3067\u3042\u308b\u306a\u3089\u3070\uff0c\u30dc\u30d6\u306f\u4ee5\u4e0b\u306e\u3088\u3046\u306b m{displaystyle m} \u3092\u6697\u53f7\u5316\u3059\u308b\uff0e\u30dc\u30d6\u306f\u30e1\u30c3\u30bb\u30fc\u30b8 m{displaystyle m} \u3092\u9577\u3055 k{displaystyle k} \u306e\u30d3\u30c3\u30c8\u5217\u3068\u3057\u3066\u8868\u73fe\u3059\u308b\uff0e\u30dc\u30d6\u306f\uff0c\u30d9\u30af\u30c8\u30eb c\u2032=mG^{displaystyle c^{prime }=m{hat {G}}} \u3092\u8a08\u7b97\u3059\u308b\uff0e\u30dc\u30d6\u306f\uff0cn{displaystyle n}\u30d3\u30c3\u30c8\u306e\u30d9\u30af\u30c8\u30eb\u3067\u3042\u308a\uff0c\u3061\u3087\u3046\u3069 t{displaystyle t} \u500b\u306e\u8981\u7d20\u304c\uff11\uff08\u6b8b\u308a\u306f\uff10\uff09\u3067\u3042\u308b\u3088\u3046\u306a\u30d9\u30af\u30c8\u30eb z{displaystyle z} \u3092\u30e9\u30f3\u30c0\u30e0\u306b\u751f\u6210\u3059\u308b\uff0e\uff08\u3064\u307e\u308a\uff0c\u30d9\u30af\u30c8\u30eb z{displaystyle z} \u306e\u9577\u3055\u306f n{displaystyle n} \u3067\u91cd\u307f\u304c t{displaystyle t}\uff0e\uff09[1]\u30dc\u30d6\u306f\u6697\u53f7\u6587\u3068\u3057\u3066 c=c\u2032+z{displaystyle c=c^{prime }+z} \u3092\u8a08\u7b97\u3059\u308b\uff0e\u5fa9\u53f7[\u7de8\u96c6]\u6697\u53f7\u6587 c{displaystyle c} \u3092\u53d7\u3051\u53d6\u3063\u305f\u6642\uff0c\u30a2\u30ea\u30b9\u306f\u6b21\u306e\u3088\u3046\u306b\u3057\u3066\u5fa9\u53f7\u3057\u3066\u5143\u306e\u30e1\u30c3\u30bb\u30fc\u30b8\u3092\u5f97\u308b\uff0e\u30a2\u30ea\u30b9\u306f P{displaystyle P} \u306e\u9006\u884c\u5217 P\u22121{displaystyle P^{-1}} \u3092\u8a08\u7b97\u3059\u308b\uff0e\u30a2\u30ea\u30b9\u306f c^=cP\u22121{displaystyle {hat {c}}=cP^{-1}} \u3092\u8a08\u7b97\u3059\u308b\uff0e\u30a2\u30ea\u30b9\u306f\u5fa9\u53f7\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0 A{displaystyle A} \u3092\u4f7f\u3063\u3066 c^{displaystyle {hat {c}}} \u3092\u5fa9\u53f7\u3057\uff0c\u5fa9\u53f7\u7d50\u679c m^{displaystyle {hat {m}}} \u3092\u5f97\u308b\uff0e\u30a2\u30ea\u30b9\u306f m=m^S\u22121{displaystyle m={hat {m}}S^{-1}} \u3092\u8a08\u7b97\u3059\u308b\uff0em{displaystyle m} \u304c\u5143\u306e\u30e1\u30c3\u30bb\u30fc\u30b8\u3067\u3042\u308b\uff0e\u5fa9\u53f7\u306e\u6b63\u5f53\u6027\u306e\u8a3c\u660e[\u7de8\u96c6]\u6697\u53f7\u5316\u3068\u5fa9\u53f7\u306e\u624b\u9806\u3088\u308a\uff0cc^=cP\u22121=mG^P\u22121+zP\u22121=mSG+zP\u22121{displaystyle {hat {c}}=cP^{-1}=m{hat {G}}P^{-1}+zP^{-1}=mSG+zP^{-1}} \u304c\u6210\u308a\u7acb\u3061\uff0cP{displaystyle P} \u304c\u7f6e\u63db\u884c\u5217\u3067\u3042\u308b\u305f\u3081zP\u22121{displaystyle zP^{-1}} \u306f\u91cd\u307f t{displaystyle t} \u306e\u30d9\u30af\u30c8\u30eb\u3067\u3042\u308b\uff0e\u30b4\u30c3\u30d1\u7b26\u53f7 G{displaystyle G} \u306f\u6700\u5927 t{displaystyle t} \u500b\u306e\u30a8\u30e9\u30fc\u3092\u8a02\u6b63\u3059\u308b\u3053\u3068\u304c\u3067\u304d\uff0c\u30d9\u30af\u30c8\u30eb mSG{displaystyle mSG} \u3068 cP\u22121{displaystyle cP^{-1}} \u3068\u306e\u8ddd\u96e2\u306f\u9ad8\u3005 t{displaystyle t} \u3067\u3042\u308b\uff0e\u3057\u305f\u304c\u3063\u3066\uff0c\u5fa9\u53f7\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u306b\u3088\u3063\u3066\u6b63\u3057\u3044\u7b26\u53f7\u8a9e m^=mS{displaystyle {hat {m}}=mS} \u304c\u5f97\u3089\u308c\u308b\uff0eS{displaystyle S} \u306e\u9006\u884c\u5217\u3092\u304b\u3051\u308b\u3053\u3068\u3067\uff0cm=m^S\u22121=mSS\u22121{displaystyle m={hat {m}}S^{-1}=mSS^{-1}} \u304c\u5f97\u3089\u308c\uff0c\u3053\u308c\u306f\u30dc\u30d6\u304c\u9001\u3063\u305f\u30e1\u30c3\u30bb\u30fc\u30b8\u306b\u7b49\u3057\u3044\uff0e\u9375\u306e\u30b5\u30a4\u30ba[\u7de8\u96c6]\u521d\u3081\u306e\u8ad6\u6587\u3067\u30de\u30c3\u30af\u30a8\u30ea\u30b9\u306f\u30d1\u30e9\u30e1\u30fc\u30bf\u3068\u3057\u3066 n=1024,k=524,t=50{displaystyle n=1024,k=524,t=50} \u3092\u63d0\u6848\u3057\u3066\u3044\u305f\uff0e[1] \u305d\u306e\u5834\u5408\uff0c\u516c\u958b\u9375\u306e\u30b5\u30a4\u30ba\u306f 524*(1024-524) = 262,000 \u30d3\u30c3\u30c8\u3067\u3042\u308b\uff0e  \u6700\u8fd1\u306e\u89e3\u6790\u306b\u3088\u308a\uff0c80\u30d3\u30c3\u30c8\u5b89\u5168\u3092\u9054\u6210\u3059\u308b\u305f\u3081\u306e\u30d1\u30e9\u30e1\u30fc\u30bf\u3068\u3057\u3066\u306f\uff0c\u6a19\u6e96\u7684\u306a\u4ee3\u6570\u7684\u5fa9\u53f7\u3092\u4f7f\u3046\u5834\u5408\u306f n=2048,k=1751,t=27{displaystyle n=2048,k=1751,t=27}\uff0c\u30b4\u30c3\u30d1\u7b26\u53f7\u306b\u5bfe\u3059\u308b\u30ea\u30b9\u30c8\u5fa9\u53f7\u3092\u7528\u3044\u308b\u5834\u5408\u306fn=1632,k=1269,t=34{displaystyle n=1632,k=1269,t=34} \u3068\u3059\u308b\u3053\u3068\u304c\u63d0\u6848\u3055\u308c\u3066\u304a\u308a\uff0c\u516c\u958b\u9375\u9577\u306f\u305d\u308c\u305e\u308c 520,047\u30d3\u30c3\u30c8\uff0c460,647\u30d3\u30c3\u30c8\u3068\u306a\u308b\uff0e[5] \u91cf\u5b50\u30b3\u30f3\u30d4\u30e5\u30fc\u30bf\u3067\u306e\u89e3\u8aad\u306b\u8010\u6027\u3092\u6301\u305f\u305b\u308b\u305f\u3081\u306b\u306f\uff0c\u30b4\u30c3\u30d1\u7b26\u53f7\u3092\u7528\u3044\u308b\u5834\u5408\u306f n=6960,k=5413,t=119{displaystyle n=6960,k=5413,t=119} \u3068\u3059\u308b\u3053\u3068\u304c\u63d0\u6848\u3055\u308c\u3066\u304a\u308a\uff0c\u516c\u958b\u9375\u9577\u306f 8,373,911\u30d3\u30c3\u30c8\u306b\u306a\u308b\uff0e[8]\u653b\u6483\u624b\u6cd5[\u7de8\u96c6]\u653b\u6483\u8005\u306f\u516c\u958b\u9375 (G^,t){displaystyle ({hat {G}},t)} \u3092\u77e5\u3063\u3066\u3044\u308b\u304c\u79d8\u5bc6\u9375\u306f\u77e5\u3089\u305a\uff0c\u624b\u306b\u5165\u308c\u305f\u6697\u53f7\u6587 c\u2208F2n{displaystyle cin mathbb {F} _{2}^{n}} \u304b\u3089\u5e73\u6587\u3092\u5fa9\u5143\u3057\u305f\u3044\uff0e\u3053\u306e\u3088\u3046\u306a\u8a66\u307f\u306f\uff08\u4e8b\u5b9f\u4e0a\uff09\u4e0d\u53ef\u80fd\u3067\u3042\u308b\u3079\u304d\u3067\u3042\u308b\uff0e\u30de\u30c3\u30af\u30a8\u30ea\u30b9\u6697\u53f7\u306b\u5bfe\u3059\u308b\u653b\u6483\u624b\u6cd5\u306f\uff0c\u5927\u304d\u304f\uff12\u7cfb\u7d71\u306b\u5206\u304b\u308c\u308b\uff0e\u7dcf\u5f53\u305f\u308a\u653b\u6483  \/ \u975e\u69cb\u9020\u7684\u306a\u653b\u6483[\u7de8\u96c6]\u653b\u6483\u8005\u306f\uff0c\u516c\u958b\u3055\u308c\u3066\u3044\u308b\u884c\u5217 G^{displaystyle {hat {G}}} \u304c (n,k){displaystyle (n,k)} \u7b26\u53f7 C^{displaystyle {hat {C}}} \u306e\u751f\u6210\u884c\u5217\u3067\u3042\u308a\uff0c\u305d\u306e\u7b26\u53f7\u306f t{displaystyle t} \u500b\u306e\u30a8\u30e9\u30fc\u3092\u8a02\u6b63\u3067\u304d\u308b\uff0c\u3068\u3044\u3046\u4e8b\u5b9f\u3092\u77e5\u3063\u3066\u3044\u308b\uff0e\u7b26\u53f7C^{displaystyle {hat {C}}} \u306f\uff0c\u7279\u5b9a\u306e\u7b26\u53f7\u306e\u65cf\u304b\u3089\u9078\u3070\u308c\u305f\u4f55\u3089\u304b\u306e\u69cb\u9020\u3092\u6301\u3063\u305f\u7b26\u53f7\u3092\u96e3\u8aad\u5316\u3057\u305f\u3082\u306e\u3067\u3042\u308b\u304c\uff0c\u653b\u6483\u8005\u306f\u305d\u306e\u3088\u3046\u306a\u4e8b\u5b9f\u3092\u7121\u8996\u3057\u3066\uff0c\u4efb\u610f\u306e\u7dda\u5f62\u7b26\u53f7\u306b\u5bfe\u3059\u308b\u5fa9\u53f7\u306e\u65b9\u6cd5\u3092\u4f7f\u3046\u3053\u3068\u304c\u3067\u304d\u308b\uff0e\u305d\u306e\u3088\u3046\u306a\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u3068\u3057\u3066\u306f\uff0c\u7b26\u53f7\u306e\u5404\u7b26\u53f7\u8a9e\u3092\u30c1\u30a7\u30c3\u30af\u3059\u308b\u65b9\u6cd5\uff0c\u30b7\u30f3\u30c9\u30ed\u30fc\u30e0\u5fa9\u53f7\u6cd5\uff0cinformation set decoding\u306a\u3069\u304c\u3042\u308b\uff0e\u3057\u304b\u3057\uff0c\u4e00\u822c\u306e\u7dda\u5f62\u7b26\u53f7\u306e\u5fa9\u53f7\u306fNP\u56f0\u96e3\u3067\u3042\u308b\u3053\u3068\u304c\u77e5\u3089\u308c\u3066\u304a\u308a\uff0c[3]\u4e0a\u8ff0\u306e\u65b9\u6cd5\u306f\u3059\u3079\u3066\u6307\u6570\u7684\u306a\u5b9f\u884c\u6642\u9593\u3092\u5fc5\u8981\u3068\u3059\u308b\uff0e2008\u5e74\u306b\uff0cBernstein\u3068Lange\u3068Peters[5]\u306f\uff0c\u30aa\u30ea\u30b8\u30ca\u30eb\u306e\u30de\u30c3\u30af\u30a8\u30ea\u30b9\u6697\u53f7\u306b\u5bfe\u3059\u308b\u5b9f\u7528\u7684\u306a\u653b\u6483\u3092\u4e0e\u3048\u305f\u304c\uff0c\u305d\u308c\u306fStern[9]\u306b\u3088\u308b Information Set Decoding\u3092\u7528\u3044\u305f\u3082\u306e\u3067\u3042\u308b\uff0e \u6700\u521d\u306b\u30de\u30c3\u30af\u30a8\u30ea\u30b9\u304c\u63d0\u6848\u3057\u305f\u30d1\u30e9\u30e1\u30fc\u30bf\u3092\u4f7f\u3063\u305f\u5834\u5408\uff0c\u653b\u6483\u306f 260.55 \u56de\u306e\u30d3\u30c3\u30c8\u6f14\u7b97\u3067\u5b9f\u884c\u3067\u304d\u308b\uff0e\u305d\u306e\u653b\u6483\u306f\u5b8c\u5168\u306b\u4e26\u5217\u5316\u3067\u304d\u308b\u305f\u3081\uff08\u30ce\u30fc\u30c9\u9593\u306e\u901a\u4fe1\u306f\u5fc5\u8981\u306a\u3044\uff09\uff0c\u305d\u3053\u305d\u3053\u306e\u30b3\u30f3\u30d4\u30e5\u30fc\u30bf\u30af\u30e9\u30b9\u30bf\u30fc\u3092\u4f7f\u3048\u3070\u6570\u65e5\u3067\u653b\u6483\u304c\u5b8c\u4e86\u3059\u308b\uff0e\u69cb\u9020\u7684\u653b\u6483[\u7de8\u96c6]\u653b\u6483\u8005\u306f C{displaystyle C} \u306e\u69cb\u9020\u3092\u5fa9\u5143\u3057\uff0c\u305d\u308c\u306b\u3088\u3063\u3066\u52b9\u7387\u7684\u306a\u5fa9\u53f7\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0 A{displaystyle A} \u304b\uff0c\u3042\u308b\u3044\u306f\u4ed6\u306e\u5341\u5206\u52b9\u7387\u7684\u306a\u5fa9\u53f7\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u3092\u898b\u3064\u3051\u3088\u3046\u3068\u3059\u308b\u3053\u3068\u3082\u3067\u304d\u308b\uff0e\u3053\u306e\u3088\u3046\u306a\u3053\u3068\u304c\u653b\u6483\u8005\u306b\u3067\u304d\u308b\u304b\u3069\u3046\u304b\u306f\uff0cC{displaystyle C}\u3092\u3069\u306e\u3088\u3046\u306a\u7b26\u53f7\u306e\u65cf\u304b\u3089\u9078\u3076\u304b\u3067\u6c7a\u307e\u308b\uff0e\u30de\u30c3\u30af\u30a8\u30ea\u30b9\u6697\u53f7\u3067\u5229\u7528\u3059\u308b\u7b26\u53f7\u65cf\u3068\u3057\u3066\u591a\u304f\u306e\u7b26\u53f7\u65cf\u304c\u63d0\u6848\u3055\u308c\uff0c\u305d\u306e\u3046\u3061\u306e\u307b\u3068\u3093\u3069\u306e\u3082\u306e\uff08\u4f8b\u3048\u3070\u30ea\u30fc\u30c9\u30fb\u30bd\u30ed\u30e2\u30f3\u7b26\u53f7\uff09\u306b\u5bfe\u3057\u3066\u306f\uff0c\u52b9\u7387\u7684\u306a\u5fa9\u53f7\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u304c\u898b\u3064\u304b\u3063\u3066\u304a\u308a\uff0c\u5168\u304f\u5b89\u5168\u3067\u306f\u306a\u3044\uff0e\u6700\u521d\u306b\u63d0\u6848\u3055\u308c\u305f\u4e8c\u5143\u30b4\u30c3\u30d1\u7b26\u53f7\u306f\uff0c\u69cb\u9020\u7684\u653b\u6483\u306b\u3088\u3063\u3066\u672a\u3060\u7834\u3089\u308c\u3066\u3044\u306a\u3044\u6570\u5c11\u306a\u3044\u7b26\u53f7\u65cf\u306e\u4e00\u3064\u3067\u3042\u308b\uff0e\u53c2\u8003\u6587\u732e[\u7de8\u96c6]^ a b c McEliece, Robert J. (1978). \u201cA Public-Key Cryptosystem Based On Algebraic Coding Theory\u201d. DSN Progress Report 44:  114-116. Bibcode:\u00a01978DSNPR..44..114M. https:\/\/ipnpr.jpl.nasa.gov\/progress_report2\/42-44\/44N.PDF.\u00a0^ Dinh, Hang; Moore, Cristopher; Russell, Alexander (2011). \u201cMcEliece and Niederreiter cryptosystems that resist quantum Fourier sampling attacks\u201d. In Rogaway, Philip. Lecture Notes in Computer Science. 6841. Advances in cryptology — CRYPTO 2011. Heidelberg: Springer. pp.\u00a0761-779. doi:10.1007\/978-3-642-22792-9_43. ISBN\u00a0978-3-642-22791-2\u00a0^ a b Berlekamp, Elwyn R.; McEliece, Robert J.; Van Tilborg, Henk C.A. (1978). \u201cOn the Inherent Intractability of Certain Coding Problems\u201d. IEEE Transactions on Information Theory IT-24 (3):  384-386. doi:10.1109\/TIT.1978.1055873. MR0495180.\u00a0^ N. J. Patterson (1975). \u201cThe algebraic decoding of Goppa codes\u201d. IEEE Transactions on Information Theory IT-21 (2):  203-207. doi:10.1109\/TIT.1975.1055350.\u00a0^ a b c Bernstein, Daniel J.; Lange, Tanja; Peters, Christiane (8 August 2008). Attacking and defending the McEliece cryptosystem. Lecture Notes in Computer Science. 5299. 31-46. doi:10.1007\/978-3-540-88403-3_3. ISBN\u00a0978-3-540-88402-6. https:\/\/eprint.iacr.org\/2008\/318\u00a0^ Bernstein, Daniel J. (2010). \u201cGrover vs. McEliece\u201d. In Sendrier, Nicolas. Lecture Notes in Computer Science. 6061. Post-quantum cryptography 2010. Berlin: Springer. pp.\u00a073-80. doi:10.1007\/978-3-642-12929-2_6. ISBN\u00a0978-3-642-12928-5. https:\/\/cr.yp.to\/codes\/grovercode-20091123.pdf\u00a0^ \u201ceBATS: ECRYPT Benchmarking of Asymmetric Systems\u201d. bench.cr.yp.to (2018\u5e748\u670825\u65e5). 2020\u5e745\u67081\u65e5\u95b2\u89a7\u3002^ Daniel Augot (2015\u5e749\u67087\u65e5). \u201cInitial recommendations of long-term secure post-quantum systems\u201d. PQCRYPTO: Post-Quantum Cryptography for Long-Term Security. 2020\u5e747\u670830\u65e5\u95b2\u89a7\u3002^ Jacques Stern (1989). A method for finding codewords of small weight. Lecture Notes in Computer Science. 388. Springer Verlag. 106-113. doi:10.1007\/BFb0019850. ISBN\u00a0978-3-540-51643-9\u00a0\u5916\u90e8\u30ea\u30f3\u30af[\u7de8\u96c6]"},{"@context":"http:\/\/schema.org\/","@type":"BreadcrumbList","itemListElement":[{"@type":"ListItem","position":1,"item":{"@id":"https:\/\/wiki.edu.vn\/jp\/wiki5\/#breadcrumbitem","name":"Enzyklop\u00e4die"}},{"@type":"ListItem","position":2,"item":{"@id":"https:\/\/wiki.edu.vn\/jp\/wiki5\/archives\/3023#breadcrumbitem","name":"\u30de\u30c3\u30af\u30a8\u30ea\u30b9\u6697\u53f7 – Wikipedia"}}]}]