Warning : Undefined variable $type in /home/users/1/sub.jp-asate/web/wiki/extensions/HeadScript/HeadScript.php on line 3 Warning : "continue" targeting switch is equivalent to "break". Did you mean to use "continue 2"? in /home/users/1/sub.jp-asate/web/wiki/includes/json/FormatJson.php on line 297 Warning : Trying to access array offset on value of type bool in /home/users/1/sub.jp-asate/web/wiki/includes/Setup.php on line 660 Warning : session_name(): Session name cannot be changed after headers have already been sent in /home/users/1/sub.jp-asate/web/wiki/includes/Setup.php on line 834 Warning : ini_set(): Session ini settings cannot be changed after headers have already been sent in /home/users/1/sub.jp-asate/web/wiki/includes/session/PHPSessionHandler.php on line 126 Warning : ini_set(): Session ini settings cannot be changed after headers have already been sent in /home/users/1/sub.jp-asate/web/wiki/includes/session/PHPSessionHandler.php on line 127 Warning : session_cache_limiter(): Session cache limiter cannot be changed after headers have already been sent in /home/users/1/sub.jp-asate/web/wiki/includes/session/PHPSessionHandler.php on line 133 Warning : session_set_save_handler(): Session save handler cannot be changed after headers have already been sent in /home/users/1/sub.jp-asate/web/wiki/includes/session/PHPSessionHandler.php on line 140 Warning : "continue" targeting switch is equivalent to "break". Did you mean to use "continue 2"? in /home/users/1/sub.jp-asate/web/wiki/languages/LanguageConverter.php on line 773 Warning : Cannot modify header information - headers already sent by (output started at /home/users/1/sub.jp-asate/web/wiki/extensions/HeadScript/HeadScript.php:3) in /home/users/1/sub.jp-asate/web/wiki/includes/Feed.php on line 294 Warning : Cannot modify header information - headers already sent by (output started at /home/users/1/sub.jp-asate/web/wiki/extensions/HeadScript/HeadScript.php:3) in /home/users/1/sub.jp-asate/web/wiki/includes/Feed.php on line 300 Warning : Cannot modify header information - headers already sent by (output started at /home/users/1/sub.jp-asate/web/wiki/extensions/HeadScript/HeadScript.php:3) in /home/users/1/sub.jp-asate/web/wiki/includes/WebResponse.php on line 46 Warning : Cannot modify header information - headers already sent by (output started at /home/users/1/sub.jp-asate/web/wiki/extensions/HeadScript/HeadScript.php:3) in /home/users/1/sub.jp-asate/web/wiki/includes/WebResponse.php on line 46 Warning : Cannot modify header information - headers already sent by (output started at /home/users/1/sub.jp-asate/web/wiki/extensions/HeadScript/HeadScript.php:3) in /home/users/1/sub.jp-asate/web/wiki/includes/WebResponse.php on line 46
http:///mymemo.xyz/wiki/api.php?action=feedcontributions&user=49.236.225.67&feedformat=atom
miniwiki - 利用者の投稿記録 [ja]
2024-05-15T05:55:52Z
利用者の投稿記録
MediaWiki 1.31.0
暗号理論
2018-08-07T01:23:59Z
<p>49.236.225.67: /* プロトコル */</p>
<hr />
<div>'''暗号理論'''（あんごうりろん）の記事では[[暗号]]、特に'''暗号学'''に関係する理論について扱う。[[:Category:暗号技術]]も参照。<br />
<br />
== 概要 ==<br />
英語では、'''暗号学'''を cryptography, cryptology という。また、日本ではもっぱら暗号と総称されるが「[[コード (暗号)|コード]]」と「サイファー」（[[:en:Cipher]]）という分類がある。<br />
<br />
暗号の理論（暗号理論）は、暗号学の一分野である。<br />
<br />
暗号の理論の主な分野には、以下のようなものがある。<br />
* 暗号系 (cryptosystem) 、すなわち暗号化と復号、といった手続きの構成方法や性能・安全性などに関する[[研究]]<br />
* 暗号や[[電子署名]]といった守秘 (confidentiality) や完全性 (integrity) を実現する、暗号[[アルゴリズム]]や暗号プロトコルの研究<!--する学問]]--><br />
* [[暗号解読]]（cryptanalysis）<br />
暗号理論は暗号学の一分野と前述したように、暗号学の全ては理論ではカバーしきれない。歴史的な暗号に比べれば現代の暗号（現代暗号）は理詰めで構成されていることは確かだが、それでも、暗号学としては、その運用や関与する人間の不注意といったヒューマンファクタ等も考慮されねばならない（「暗号の連鎖（chain）の強さは、最も弱い環（link）の強さしかない」）ということは変わっていない。<br />
<br />
[[コンピュータセキュリティ]]や[[ネットワークセキュリティ]]、より総合的には[[情報セキュリティ]]と暗号や暗号理論とは密接な関わりがある。例えば、（論理的な）[[アクセス制御]]は、「ユーザが誰であるか」という認証（authentication<ref>「承認: authorization」とまぎらわしいので注意</ref>）に従ってOSの機能などにより制御されるわけだが、認証自体には、例えばユーザ本人のみが知り得る秘密情報（パスワード等）を使う等といった暗号的な手法が必要であるし、無線や公衆網を通してコンピュータを利用する場合には、そのパスワードを直接やりとりしてしまうようなことは避けなければならない。そういったプロトコルの設計には暗号理論に従った裏付けが必要である。<br />
<br />
前述のように暗号学には総合の学であるという面がある。暗号理論にもそれは言えて、[[情報理論]]や[[符号理論]]、[[計算複雑性理論]]といった[[理論計算機科学]]、[[数論]]や[[代数幾何]]、[[離散数学]]といった[[数学]]<!--、時には[[力学系]]などの[[物理学]]の知見が用いられることもある。--><!-- ← カオス暗号あたりのことを指してる？ それを「力学系」と言うのは流石に漠然とし過ぎていると思う-->、などが広く関係する。<br />
<br />
=== 用語 ===<br />
暗号理論で使われる用語。<br />
{{seealso|暗号#用語}}<br />
* 暗号理論 - 暗号や暗号解読を扱う理論。本ページの記事名。<br />
* 暗号技術 (cryptographic techniques) - 暗号に関する技術。暗号プリミティブや暗号プロトコルを駆使して、機密 (confidentiality) ・完全性 (integrity) ・認証 (authentication) ・否認防止 (non-repudiation) などのセキュリティ機能を実現することを目的とする。鍵管理などの暗号を利用するために必要な技術も含む。<br />
* 暗号学 (cryptology) - 暗号に関する学問<br />
** 暗号[法] (cryptography) - 暗号方式（とその応用）の構成法や性能、安全性などに関する研究。暗号術ということもある。<br />
** 暗号解読[法] (cryptanalysis) - 暗号方式（とその応用）の解読法に関する研究。暗号分析、暗号解析ということもある。<br />
* 暗号学者 (cryptologist)<br />
** 暗号研究者 (cryptographer) - 暗号を専門的に研究する人（[[暗号研究者の一覧]]）。まれに平文を暗号文に変換する作業に従事する人（暗号師）を指すことがある。<br />
** 暗号解読者 (cryptanalyst) - 復号鍵を用いずに、[[暗号文]]を[[平文]]に戻したり、暗号文と平文を区別したり、暗号文から別の暗号文を生成することを試みる人。または、暗号文と平文の組から鍵を推定する人。まれに暗号文を復号する作業に従事する人を指すことがあるが、復号と解読は区別すべきである。<br />
* '''暗号プロトコル'''/'''暗号化プロトコル''' (cryptographic protocol/encryption protocol) - 暗号化と復号の手順<br />
* '''暗号プリミティブ''' (cryprographic primitive) - 暗号方式を、元々の目的であった秘匿だけではなく、署名・認証などの基本的ツールに適応したもののこと。cipher, signature, hash などがある。別の用法として、主に公開鍵暗号方式で、要となるトラップドア関数と、パディング等の周辺部分に分けて、前者を暗号プリミティブと称することがある（後者は'''暗号スキーム'''という）。<br />
* '''暗号方式''' / 暗号システム / 暗号系 (cryptographic scheme, cryptographic system, cryptosystem) - 暗号化鍵 (encryption key) を用いて、平文 (plaintext) を暗号文 (cryptogram) に変換する暗号化 (encryption) アルゴリズムと、復号鍵 (decryption key) を用いて、暗号文を平文に変換する復号 (decryption) アルゴリズム、鍵、平文、暗号文などからなるシステムのことである。<br />
** '''暗号アルゴリズム''' (cryptographic algorithm) / 暗号関数 - 暗号方式における暗号化および復号のアルゴリズム。<br />
*** 暗号化 (encryption)<br />
*** 復号 (decryption)<br />
*** 鍵生成 (key generation)<br />
** 暗号データ<br />
*** 暗号鍵 / [[鍵 (暗号)|鍵]] (key)<br />
**** 暗号化鍵 (encryption key)<br />
**** 復号鍵 (decryption key)<br />
*** メッセージ (message)<br />
**** 平文 (plain text) / [[クリアテキスト|明文 (clear text)]]<br />
**** 暗号文 (cryptogram)<br />
* 暗号方式の実現手段に関する用語<br />
** 共通鍵暗号方式 / 対称鍵暗号方式 - 暗号化鍵 (encryption key) と復号鍵 (decryption key) が同じ、あるいは片方の鍵から他方の鍵を容易に求めることができる暗号方式。<br />
*** 共通鍵 (common key) / [[秘密鍵]] (secret key) / 共有鍵 (shared key)<br />
** 公開鍵暗号方式 / 非対称鍵暗号方式 - 暗号化鍵から復号鍵を求めること、または復号鍵から暗号化鍵を求めることが難しい暗号方式。<br />
*** 鍵ペア (key pair) - 公開鍵と秘密鍵の組。<br />
**** 公開鍵 (public key) - 公開鍵暗号方式における暗号化鍵（または復号鍵）。<br />
**** 秘密鍵 / 私有鍵 / 私用鍵 / プライベート鍵 (private key) - 公開鍵暗号方式における復号鍵（または暗号化鍵）。<!--個人鍵と訳すこともある。-->過去にはprivate keyの意味でsecret keyと記述することもあった。共通鍵暗号方式における共通鍵を秘密鍵と呼ぶこともあった。<br />
*** 公開鍵演算 (public-key operation) - 公開鍵を用いた演算。暗号 (cipher) の場合は暗号化 (encipherment) であり、署名 (signature) の場合は、検証 (verify) になる。<br />
*** 秘密鍵演算 (private-key operaion) - 秘密鍵を用いた演算。暗号 (cipher) の場合は復号 (decipherment) であり、署名 (signature) の場合は、署名 (sign) になる。<br />
* 暗号方式を応用した場合の用語<br />
** 暗号 (cipher)<br />
*** サイファ化 (encipherment)<br />
*** デサイファ化 (decipherment)<br />
*** 暗号化アルゴリズム (enciphering algorithm)<br />
*** 復号アルゴリズム (deciphering algorithm)<br />
*** 暗号化鍵 (enciphering key)<br />
*** 復号鍵 (deciphering key)<br />
*** 暗号文 (cipher text)<br />
** 署名 (signature)<br />
*** 署名 (sign)<br />
*** 検証（verify）<br />
*** 署名鍵（signature key)<br />
*** 検証鍵（verification key)<br />
*** メッセージ / 文書<br />
*** 署名データ / 署名<br />
** ハッシュ関数 (hash function) / メッセージダイジェスト (message digest)<br />
*** メッセージ / プレイメージ (pre-image)<br />
*** ハッシュ値 / フィンガープリント / ハッシュ<br />
* 暗号方式の主な用途<br />
** [[秘匿通信]] (secret communication)<br />
** 認証 (authentication) / ディジタル署名 (digital signature)<br />
<br />
注1) 「暗号アルゴリズム (cryptographic algorithm) は、暗号方式 (cipher) のことである」という定義もあるが、ここでは、暗号アルゴリズムとは、暗号方式 (cryptosystem) を定義する一つの要素であり、暗号方式には、暗号 (cipher) を始めとする幾つかの暗号プリミティブがあるという解釈で分類している。<br />
<!-- とりあえず、後回し、暗号の用途に関する言葉、だけどあまり使われていない気がする。<br />
* 暗号メカニズム<br />
** ビルディングブロック --><br />
<br />
=== 展開 ===<br />
暗号自体は古代エジプトの時代から存在したが、その理論的研究は1949年の[[クロード・シャノン|シャノン]] (Shannon) の研究に始まる。<br />
シャノン以前には、9世紀にキンディ (Al-Kindi) 、15〜16世紀に [[レオーネ・バッティスタ・アルベルティ|アルベルティ]] (Alberti) 、トリテミウス (Trithemius) 、[[ジャンバッティスタ・デッラ・ポルタ|ポルタ]] (Porta) が執筆した[[暗号関係の書籍|暗号の書籍]]が残されているが、多くは秘密であった。<br />
<br />
シャノンは、攻撃者が無限の計算能力をもっているという仮定の下で、平文に関する[[情報量]]がどの程度攻撃者に漏れるかを研究し（[[情報理論的安全性]]）、この意味で安全な暗号方式は[[ワンタイムパッド]]を用いる暗号方式だけであることを示した。<br />
<br />
暗号法や暗号解読法は、利用できる道具によって大きく影響を受ける。特に1940年代前後から始まった[[コンピュータ|電子計算機]]によって、暗号解読可能な範囲が飛躍的に広がり、また、電子回路によって暗号がより効率的に実装できるようになった。<br />
<br />
このような計算機の発展を背景にして、1970年代の後半に誕生した[[Data Encryption Standard|DES]]と[[RSA暗号|RSA]]が現代暗号の代表である。共に、アルゴリズムが公開されていて、暗号鍵が秘密であることが安全性の前提となっている（[[計算量的安全性を持つ暗号|計算量的安全性]]）。<br />
<br />
これ以前にも、暗号アルゴリズムと暗号鍵が分離されていて、暗号アルゴリズム(暗号器)が漏洩しても、暗号鍵がないと暗号文を復号できないことをねらった暗号も存在したが、解読の手間（計算量）の点で、DES以前と以後では一線を引くことができよう。<br />
何よりも、従来、秘匿することが前提であったアルゴリズムの詳細を公開し、誰でも暗号の安全性を検討できる点が現代暗号の特徴である。<br />
それ以前の[[シーザー暗号]]から[[エニグマ (暗号機)|エニグマ]]までをまとめて古典暗号という。<br />
紙と鉛筆と多少の道具のみを使用していた暗号とエニグマなどの機械式暗号を区別して、後者を近代暗号とすることもある。また1949年の暗号理論を現代暗号の始まりと考える人もいる。<br />
<br />
1990年代後半から、計算量理論的アプローチによる、暗号アルゴリズムの安全性証明の手法やモデル化の研究がなされ、計算量的に困難と仮定されている問題 (IFPやDLP) と等価であることを証明可能な暗号アルゴリズムが提案された。あるいは既知の暗号解読法では解読できないことを証明できる暗号アルゴリズムが提案された。これらを「現代暗号の第2期」ということがある（[[証明可能安全性を持つ暗号|証明可能安全性]]<!--、[[最近の暗号規格]]-->）。安全性証明は、[[Rabin暗号]]やゼロ知識対話証明のように90年以前から研究があり、それらの成果の集積である。<br />
<br />
2000年代前半には、[[ゼロ知識対話証明]]やマルチパーティ計算などの暗号プロトコルの安全性証明を統一的に扱うフレームワークの研究が進んだ。<br />
{{節スタブ}}<br />
* 古典暗号 <!-- / 前近代的な暗号 --><br />
** 筆記と道具ベース<br />
** 秘匿による安全性、{{仮リンク|難解さに基づくセキュリティ|en|Security through obscurity}} - アルゴリズムは非公開<br />
* 近代暗号 <!-- / 情報理論的な暗号 --><br />
** 機械式暗号<br />
* 現代暗号 <!-- / [[計算量的安全性を持つ暗号]] --><br />
** 電子計算機ベース<br />
** [[情報理論的安全性]] information theoretic security<br />
** [[計算量的安全性を持つ暗号|計算量的安全性]] computational security<br />
*** 経験則による安全性 - アルゴリズムは公開、安全性の根拠は非公開または未知<br />
*** [[証明可能安全性を持つ暗号|証明可能な安全性]] provable security<br />
* 物理暗号<br />
** 物理的理論にもとづく暗号 <!-- 要整理 --><br />
<br />
=== 解読 ===<br />
換字や転置を組み合わせた単純な古典暗号は、頻度分析で解読可能であることが9世紀頃には知られていて、15世紀から16世紀にかけて、より複雑な多表式暗号がいくつか提案されていた。しかし、多表式暗号は手作業で行うには暗号化・復号の作業が煩雑であった為、あまり使用されず、換字や転置とコード式と組み合わせるなどして複雑さを増した暗号法が長い間使われていた。<br />
<br />
それらの方式は、沢山の暗号文を時間をかけて分析・推定することでいつ解読されるか分からないもので、実際に解読された例もいくつか知られている。<br />
入手した暗号文を分析して、（平文の）言語の統計的性質を手がかりとして、使用された暗号法（の逆変換）を推測して平文を求めるという、パズルを解くような暗号解読が行われた。<br />
19世紀には100以上の暗号法が既知のものとなっていたようである（17世紀に使用された[[ルイ14世の大暗号]]も19世紀になって解読された）。<br />
ここでは、言語に関する知識やセンス（アルファベットの出現頻度や[[アナグラム]]を解くセンス）が中心であった。<!-- 多表式も解読された --><br />
<br />
機械式暗号の登場（20世紀）は、速くて強い暗号が必要とされたことが背景にある。<br />
{{節スタブ}}<!-- 無線とかモールス信号とか、外交とか戦争とか、暗号が必要とされた説明を少し --><br />
<br />
機械式暗号の解読には、多数の組合せから解を見つけることが必要になり、カンや閃きだけでは解読できなくなった。暗号解読は、暗号機を入手して分析することの他に、いかに容易な解読方法を見つけるかということが問題になった。ここでは言語学ではなく数学が中心となる。<!-- 戦争中にはコードブックを入手することで解読することも行われた；理論ではないので略 --><br />
<br />
現代暗号では、暗号法の推測や逆変換の困難さではなく、暗号化・復号のアルゴリズムは既知として、暗号鍵の推測が困難であるような暗号方式の実現を目標とする。参照：[[ケルクホフスの原理]]<br />
<br />
現代暗号での暗号解読は、敵の暗号文を解読するという行為ではなく、公開された暗号法を分析し、平文や鍵を求める（数学の問題を解くのと同様な）アルゴリズムを見つけたり、隠れた問題を指摘するという研究となった。ここでの暗号法と暗号解読法の関わりは、大まかに次のように進展している。<br />
<br />
:S-1 ある暗号研究者が提案した暗号を別の暗号研究者が分析して解読方法を見つけ、さらに改良された暗号が提案されたり、さらに解読方法も改良されたりした。ここでは、暗号の問題点を見つけるために暗号解読が必要とされ、暗号法の発表と同様にそれらの解読に関する発表が行われた。<br />
<br />
:S-2 既存の暗号解読法に対して安全であることを主張&証明する暗号が提案され、さらに、それ以外の暗号解読法の発見が望まれた。実際に安全と思われていた暗号に暗号解読法が発表されたりした。<br />
<br />
:S-3 理想的な暗号を定義し、実際の暗号が理想的暗号と計算量的識別不能であることの証明を行うことが目的となった（暗号文が乱数と区別できない、あるいは、暗号関数が擬似ランダム置換族と区別できないような暗号方式等）。<br />
<br />
S-3のような安全性証明可能な暗号方式が完成すると、暗号の安全性は根拠となる問題（素因数分解アルゴリズムの改良や量子コンピュータの実現等）や暗号以外（平文や鍵、装置の運用等）の問題に帰着されて、計算量的な制約やモデルの仮定、証明の不備などを除くと暗号解読は不可能であることを意味する。ここでは暗号解読法はもはや不要なのかは分からないが、少なくとも設計&解読の繰り返しで強い暗号を作る時代ではなくなることを意味すると考えられる。<br />
{{main|暗号解読}}<br />
<br />
* [[信頼性の低い暗号アルゴリズム|信頼性の低い暗号]] <br />
** アルゴリズムが既知となった古典暗号<br />
** 計算量的安全性の低い現代暗号<br />
** 鍵の全数探索よりも効率的な解読法が存在する現代暗号<br />
** 安全性の証明に不備がある現代暗号（第2期）<br />
<br />
=== 拡張 ===<br />
1976年に提案された公開鍵暗号は、従来、秘匿用途であった暗号を認証(署名)に用いることを可能にした。秘匿と認証以外にも、様々な特殊な機能（メカニズム）の暗号が研究されている。<br />
{{節スタブ}}<br />
<br />
== 研究対象 ==<br />
=== 暗号プリミティブ ===<br />
==== 暗号 ====<br />
主要なものは「コード」と「サイファー」であるが（[[コード (暗号)]] と [[:en:Cipher]] を参照）、他にも多数の分類などがある。最古の文字といわれる[[ヒエログリフ]]でも暗号と推測される文字が見つかっていて、長い歴史を持つ。ここでは歴史的なものの含めて主な暗号を分類・一覧する。<br />
{{main|暗号}}<br />
* 筆記・道具ベースの暗号<br />
** [[換字式暗号]] ([[:en:Substitution cipher]])<br />
*** 単表式換字暗号 / 単アルファベット換字式暗号 (monoalphabetic cipher)<br />
**** [[単一換字式暗号]] / 単文字換字暗号 / 単純換字暗号 (simple substitution cipher)<br />
***** アトバシュ ([[:en:Atbash]]) / albam <br />
***** [[ポリュビオスの暗号表]]（換字表）([[:en:Polybius square]]) / [[忍びいろは]] / 字変四八<br />
***** シフト暗号 (shift cipher)<br />
****** [[シーザー暗号]] ([[:en:Caesar cipher]]) / [[ROT13]] ([[:en:ROT13]])<br />
****** 鍵付きシーザー暗号<!-- 16世紀法王庁で使用 --><br />
***** アフィン暗号（[[:en:affine cipher]]）<!-- ブーフマンから --><br />
***** ピッグ・ペン or フリーメーソンの暗号 ([[:en:Pigpen cipher]])<br />
***** 同音異綴暗号 / ホモフォニック換字式暗号 (homophonic substitution cipher)<br />
****** ブック暗号 ([[:en:book cipher]])<br />
**** 綴字換字暗号 / 多重音字換字暗号 (polygraphic substitution cipher)<br />
***** ノーメンクラタ (Nomenclator)<br />
****** （ルイ14世の）大暗号 ([[:en:Great Cipher]])<br />
***** プレイフェア暗号 ([[:en:Playfair cipher]])<br />
***** ヒル暗号 ([[:en:Hill cipher]]) <!-- 1929 Lester S. Hillが考案--><br />
***** ドッペルカステン<br />
*** 多表式換字暗号 / 多アルファベット換字式暗号 ([[:en:Polyalphabetic cipher]])<br />
**** 正方形の[換字]表 (トリテミスの多表） ([[:en:tabula recta]])<br />
**** [[ヴィジュネル暗号]] (ビジネル暗号ということもある） ([[:en:Vigenère cipher]])<br />
**** ボーフォート暗号 (Beaufort cipher)<br />
**** 連続鍵暗号 / 進行鍵暗号 ([[:en:running key cipher]]) / <br />
*** 自己鍵暗号 / 自動鍵暗号 ([[:en:autokey cipher]]) <!-- デニングから。ヴィジュネルが考案したストリーム暗号 --><br />
** [[転置式暗号]] / 転字式（[[:en:transposition cipher]]）<br />
*** 図形転置暗号<br />
**** スキュタレー ([[:en:Scytale]])<br />
**** レールフェンス暗号 ([[:en:Rail Fence cipher]])<br />
*** 回転グリル型暗号<!-- カルダン・グリルは分置式、Eduard B. Fleissner --><br />
*** 鍵式転置暗号<!-- 諸説あり、整理必要 ([[:en:permutation cipher]]) ブーフマンでは、置換暗号と訳している！--><br />
** 分置式暗号 / 挿入式暗号 / 隠字式 (acrostic,折句) <!-- *** 約束語 --><!-- *** 隠文式 --><br />
*** [[カルダングリル]] ([[:en:Cardan grille]]、あるいはカルダーノグリル、Cardano grille)<br />
** 混合式暗号<!-- いろいろあって省略 --><br />
*** [[ADFGVX暗号]] ([[:en:ADFGVX cipher]]) <!-- 換字と転字の組合せ --> / VIC暗号 ([[:en:VIC cipher]])<br />
** 暗号円盤<!-- 一枚の円盤だけのものと、数十枚のセットのがある --><br />
<!-- アルベルティの円盤、ホイーストン暗号円盤 (Wheatstone) --><br />
*** ホィール暗号機 (wheel) 、シリンダー (cylinder) <!-- ジェファーソンの輪（ホイール）、バゼリのシリンダ --><br />
*** M-94 ([[:en:M-94]]) 、ストリップ多表暗号M-138A<br />
* [[機械式暗号]]（ロータマシン（[[:en:rotor machine]]）等）<br />
** （円盤式）<br />
*** クリハ暗号機 ([[:en:Kryha]]) / 九一式暗号機<br />
** (ロータ式)<br />
*** ヒーバン暗号機 ([[:en:Hebern rotor machine]])<br />
*** [[エニグマ (暗号機)|エニグマ暗号機]] ([[:en:Enigma machine]])<br />
*** [[パープル暗号|パープル暗号機]]（九七式欧文印字機） ([[:en:PURPLE]])<br />
*** ハゲリン暗号機（Hagelin） / [[M-209]] ([[:en:M-209]])<br />
*** シガバ ([[:en:SIGABA]] or ECM MarkII)<br />
*** タイペックス ([[:en:Typex]]) or タイプX (Type X)<br />
** （テープ式）<br />
*** [[バーナム暗号]]（ヴァーナム暗号ということもある） ([[:en:Vernam cipher]])<br />
* 計算機ベースの暗号<br />
** [[共通鍵暗号]]<br />
*** [[ブロック暗号]]<br />
**** 64bitブロック<br />
***** [[Data Encryption Standard|DES]] / [[トリプルDES]] / CIPHERUNICORN-E / [[FEAL]] / [[MISTY1]] / [[Blowfish]] / [[CAST-128]] / IDEA / [[KASUMI]] / GOST / [[RC2]] / TEA / [[MULTI2]]<br />
**** 128bitブロック<br />
***** [[Lucifer (暗号)|Lucifer]] / [[Advanced Encryption Standard|AES]] / [[Camellia]] / CIPHERUNICORN-A / [[RC6]] / MARS / [[CAST-256]] / [[Twofish]] / MISTY2 / MAGENTA / [[SEED_(暗号)|SEED]] / LOKI97 / Serpent<br />
**** 256bitブロック<br />
***** SHACAL-2<br />
**** other block size<br />
***** [[RC5]] (variable)<br />
*** [[ストリーム暗号]] / 逐次暗号<br />
**** / [[ワンタイムパッド]] one time pad<br />
**** [[RC4]] / MULTI-SO1 / FISH / WAKE / A5/1 / A5/2 / SORFR / SNOW<br />
** [[公開鍵暗号]]<br />
*** （[[素因数分解]]問題）<br />
**** [[RSA暗号]] / RSA-OAEP / RSA-KEM / [[Rabin暗号]] / HIME(R) / [[Paillier暗号]]<br />
**** EPOC<br />
*** （[[離散対数]]問題）<br />
**** [[ElGamal暗号]] / ACE Encrypt<br />
**** [[楕円曲線暗号]] / PSEC-KEM / ECIES<br />
*** （[[ナップサック問題]]） / ナップサック暗号<br />
**** [[Merkle-Hellmanナップサック暗号]] / Chor-Rivestナップサック暗号<br />
*** （ラティス問題） / ラティス暗号<br />
**** [[NTRU暗号]]<br />
*** （多次[元]多変数、多変数多項式問題）<br />
**** <br />
* その他<br />
** 物理暗号<br />
*** [[量子暗号]] / 量子鍵配送 / 量子[[秘匿通信]]<br />
*** 視覚復号型暗号<br />
** カオス暗号<br />
<br />
==== デジタル署名 ====<br />
{{main|デジタル署名}}<br />
[[電子署名]]を実現する一番有力な方法がディジタル署名である。一般的に言って原理上、公開鍵暗号の発見によりディジタル署名が可能になった。<br />
* 通常の署名<br />
** 添付型署名<br />
*** '''（素因数分解問題）'''<br />
**** [[RSA暗号#RSA署名|RSA署名]] / RSA-PSS ([[:en:RSA-PSS]]) / ACE Sign<br />
**** ESIGN<br />
*** '''(離散対数問題)'''<br />
**** [[ElGamal署名]] / [[Schnorr署名]] / [[Digital Signature Algorithm|DSA]] <br />
*** '''（行列分解問題）'''<br />
**** FLASH / SFLASH<br />
*** '''（格子問題）'''<br />
**** NSS / NTRU-SIGN<br />
*** '''（楕円離散対数問題）'''<br />
**** <!-- 楕円曲線署名 ;これは外しておく --> / [[楕円曲線DSA|ECDSA]]<br />
** メッセージリカバリ署名<br />
*** RSA-PSS-R<br />
* 特殊機能な署名<br />
** ブラインド署名 (blind signature)<br />
** 否認不可署名 (undeniable signature)<br />
** フェイルストップ署名 (fail-stop signature)<br />
** 多重署名<br />
** リング署名<br />
** グループ署名<br />
** 代理署名<br />
** 検証者指定可能署名 designated verifier signature<br />
** オブリビアス署名<br />
<br />
==== ハッシュ関数 ====<br />
{{main|暗号学的ハッシュ関数}}<br />
* [[暗号学的ハッシュ関数]]<br />
** [[MD2]] / [[MD4]] / [[MD5]] /<br />
** [[Secure Hash Algorithm]] (SHA)<br />
*** [[SHA-0]] /<br />
*** [[SHA-1]] / <br />
*** [[SHA-2]] (SHA-224, SHA-256, SHA-384, SHA-512) /<br />
** [[SHA-3]]<br />
<br />
==== 乱数 ====<br />
* [[暗号論的擬似乱数生成器]]<br />
* pseudorandom function（[[:en:Pseudorandom function family]] を参照。「乱数列」（random numbers）ではないことに注意<ref name="PRF">暗号学徒ならば、英語版の「Pseudorandom functions are not to be confused with pseudorandom generators (PRGs).」から始まる記述を最後まで読んできちんと把握すること。両者の間には重要な特性の違いがある。</ref>）<br />
<br />
=== プロトコル ===<br />
暗号プロトコルは、暗号化に関係する[[プロトコル]]（暗号化プロトコル）などから成る。または、より広い[[情報セキュリティ]]一般に関係するセキュリティプロトコルなど。<br />
* [[認証]]<br />
** 相手認証 / 相互認証 / 片側認証 / ユーザ認証<br />
*** Diffie-Hellman認証<!-- 何だろう? --> / Schnorr認証<br />
** メッセージ認証 / [[メッセージ認証子]]<br />
*** DES-MAC / [[HMAC]] / 鍵付きハッシュ関数<br />
** チャレンジ・レスポンス<br />
** [[公開鍵証明書]] (→ [[公開鍵基盤|PKI]])<br />
* 鍵共有<br />
** [[Diffie-Hellman鍵共有]]<br />
* [[ビットコミットメント]]<br />
* マルチパーティ計算 / 共同計算<br />
** コイン投げ<br />
** メンタルポーカー<br />
** [[ビザンチン将軍問題]]<br />
** [[紛失通信プロトコル|紛失通信]] / 忘却通信路 / ([[:en:oblivious transfer]])<br />
* [[ゼロ知識証明]] / ゼロ知識対話証明 (ZKIP) ([[:en:Zero-knowledge proof]])<br />
* 暗号プロトコル応用<br />
** 時刻証明 / タイムスタンプ<br />
** [[電子投票]]<br />
** [[電子入札]]<br />
** [[電子マネー]]<br />
** 電子公証 <!-- これは? --><br />
* 依頼計算 server-aid computation <!-- server-aidだと形容詞用法なので計算をつけました --><br />
* 同時交換 fair exchange<br />
* ミックスネット mix net<br />
* [[秘密分散法|秘密分散]] ([[:en:Secret sharing]])<br />
** 検証可能秘密分散 ([[:en:verifiable secret sharing]])<br />
* 閾値暗号 (threshold cryptosystem)<br />
* 汎用的結合可能性 (universal composability)<br />
** UCコミットメント<br />
** UCゼロ知識証明<br />
<br />
== 研究内容 ==<br />
=== 暗号の構成要素・構成法 ===<br />
{{節スタブ}}<br />
<br />
==== ブロック暗号の構成 ====<br />
[[ブロック暗号]]は、データスクランブル部と、鍵スケジュール部の2つを主な要素とし、データスクランブル部は、ラウンドの繰返し構造になっているものが多い（product cipherという）。Product cipherの基本的な構成法に、[[Feistel構造]]と[[SPN構造]]の2つがある。<br />
<br />
* Product cihper<br />
* [[Feistel構造]] / フェイステル・ネットワーク Feistel network<br />
* [[SPN構造]] (substitution-permutation network)<br />
* F関数 / [[Sボックス]] S-box<br />
* 鍵拡大 / キースケジュール / ラウンド鍵<br />
* 初期変換 / 最終変換<br />
* [[暗号利用モード]] <br />
<br />
==== ストリーム暗号の構成 ====<br />
{{節スタブ}}<br />
* 鍵系列 <br />
* 線形フィードバックシフトレジスタ<br />
<br />
==== 公開鍵暗号の構成 ====<br />
[[公開鍵暗号]]の要はトラップドア関数であり、安全なトラップドア関数の存在を仮定して、安全な公開鍵暗号方式を構成する方法が研究されている。<br />
トラップドア関数は、まだ数個しか発見されておらず、新しいトラップドア関数の発見もテーマの一つである。<br />
<br />
* [[一方向性関数]] one way function <br />
* トラップドア関数 / 落し戸付き一方向性関数<br />
* [[ハードコア述語]] / ハードコア関数 (hardcore predicate)<br />
* [[RSAモジュラス]] (N=P* Q)<br />
* ESIGNモジュラス (N=P* P* Q)<br />
* [[Fiat-Shamirヒューリスティック]]<br />
<br />
==== ハッシュ関数の構成 ====<br />
ハッシュ関数（正確には、暗号論的ハッシュ関数）は、可変長入力、固定長出力の関数で、入力から出力を求めることは容易であるが、出力から入力（あるいは出力が同じになる入力の一つ）を求めること、出力が同一になるような2個の入力を求めることが計算量的に困難である等の性質を満たすものである。<br />
<br />
ほとんどのハッシュ関数は、可変長の入力メッセージ m をブロック単位に分割（最初のブロックをm_1、最後のブロックをm_nとする。m_0は所定の初期値）し、圧縮関数 H を h_i = H(h_{i-1}, m_i) のように繰り返し使って、出力 h_n を求める構成になっている。<br />
<br />
* 基本構造（全体構造）<br />
** 反復型 iterated<br />
*** [[:en:Merkle-Damgård construction]]<br />
*** Enveloped MD<br />
*** MD-Strengthening (パディング)<br />
<br />
圧縮関数については、ハッシュ専用の関数を開発することの他に、ブロック暗号を利用した構成法が研究されている。ブロック暗号ベースの構成法では、構成可能な種類の数え上げや理想暗号モデル E を用いた安全性証明、構成法としての最適性などが検討されている。<br />
<br />
* 圧縮関数の構成 [[:en:one-way compression function]]<br />
** ハッシュ専用関数<br />
*** MDx 等<br />
*** 代数的関数（法剰余）<br />
** ブロック暗号ベース<br />
*** 単ブロック長<br />
**** Davies-Meyer法 h' = h xor E(m,h)<br />
**** Matyas-Meyer-Oseas法 h' = m xor E(g(h),m), ISO/IEC 1-118-2<br />
**** Miyaguchi-Preneel法 h' = m xor E(g(h),m) xor h<br />
*** 倍ブロック長<br />
**** MDC-2、MDC-4<br />
<br />
==== その他 ====<br />
{{節スタブ}}<br />
* [[鍵 (暗号)]]<br />
* ハイブリッド暗号 / KEM / DEM<br />
* 多重暗号<br />
<br />
=== 暗号の性能・効率 ===<br />
{{節スタブ}}<br />
暗号化・復号に必要な演算量や、ハード・ソフト実装時の処理速度などについて、実測値の測定、暗号方式間の比較や実装方法の効率化などが研究されている。<br />
<br />
また、安全性の指標ともなる様々な特性値や、その求め方（上限や下限、近似計算）も研究されている。暗号にとって重要な特性値には、暗号解読によって発見されたものがある。<br />
<br />
共通鍵暗号は、公開鍵暗号で代用できる場合があるため、スピードや鍵サイズ、実装コストなどで公開鍵暗号よりもメリットがあることが求められる。<br />
<br />
ストリーム暗号は、ブロック暗号の一つの利用モードとして実現できるため、ストリーム暗号の存在理由として、スピードが速いこと等が求められる。<br />
<br />
* データ量<br />
* ラウンド数<br />
* ビット演算量<br />
* 有効鍵<br />
* 線形・差分特性<br />
* ビットバランス性<br />
<br />
=== 暗号の安全性 ===<br />
一般に、'''安全性の目標'''と'''攻撃条件'''をモデル化することで暗号を攻撃する問題を定義し、それが誰もが難しいと想定している問題（安全性の'''根拠となる問題'''）と等価であることを示すことで、安全性の評価とする。その際、攻撃条件だけではなく'''攻撃アルゴリズム'''も限定して「その範囲」で安全である（目標が達成されている）ということもある。証明の際にさらに仮定やモデルを導入することもある（問題が等価であることの定義など）。また、現代暗号では、計算量的安全性（解読に要する計算量が膨大であること、例：指数時間要する）があることを'''安全性の前提'''としているものが多い。このことは計算機の進歩や時間の経過により安全性が低下していくことを意味する。<br />
<br />
安全性の表現の例：「○○○暗号は、ROM仮定の下、DLPが困難であれば、IND-CCA2 の安全性証明がある（計算量的安全性）」<br />
<br />
暗号の安全性では、上記のような安全性に影響する事項を見出して、より厳密な定義を構築していくことと、その定義を満たす暗号の性質が研究されている。<br />
<br />
その他、実際の暗号の安全性は、暗号方式の理論的安全性よりも、実装上、運用上の問題の有無によってより大きく影響を受けることがある。安全とされる暗号方式や暗号製品を採用するだけではなく、平文の管理（例えば個人情報の扱い）や鍵の管理などにも注意が必要である。<br />
<!-- この辺に図を入れたい：<br />
安全性の帰着関係について、下記のことが判明している。<br />
<br />
IND-CPA < ----- IND-CCA1 --/-- > IND-CCA2<br />
↑↓<br />
NM-CCA2<br />
というの。<br />
--><br />
* 安全性の目標（ゴール）<br />
** 完全秘匿 perfect secrecy<br />
** 強秘匿 / セマンティックセキュア (SS) semantic secure [[:en:Semantic security]]<br />
** 頑強性 / 非展性 (NM) non-malleable [[:en:Malleability (cryptography)]]<br />
*** 平文非展性<br />
*** 鍵非展性 → 暗号と群も参照<br />
** 識別不能性 (IND) indistinguishable<br />
*** 平文識別不能性 [[:en:ciphertext indistinguishability]]<br />
*** 鍵識別不能性<br />
<!-- おさまりが悪いので見直し<br />
** 完全解読 / 部分解読 / ビットセキュリティ<br />
--><br />
* 攻撃条件<br />
** 既知暗号文攻撃 (COA) [[:en:ciphertext-only attack]]<br />
** [[既知平文攻撃]] (KPA) [[:en:known-plaintext attack]]<br />
** 既知平文差分攻撃<br />
** [[選択平文攻撃]] (CPA) [[:en:chosen plaintext attack]]<br />
** [[選択暗号文攻撃]] (CCA) [[:en:chosen ciphertext attack]]<br />
** 適応的選択暗号文攻撃 (CCA2) [[:en:adaptive chosen ciphertext attack]]<br />
** [[関連鍵攻撃]] [[:en:related-key attack]] <!-- 攻撃条件に移動しました --><br />
* 攻撃アルゴリズム<br />
** （汎用的攻撃）<br />
*** [[総当たり攻撃]] / [[全数探索]] / [[:en:Brute force attack]] exhaustive key search<br />
*** [[誕生日攻撃]] [[:en:birthday attack]]<br />
*** [[タイムメモリトレードオフ|タイム・メモリ・トレードオフ]]<br />
*** [[中間一致攻撃]] [[:en:meet-in-the-middle attack]]<br />
** （古典暗号）<br />
*** [[頻度分析 (暗号)]] [[:en:frequency analysis (cryptanalysis)]]<br />
**** カシスキ・テスト [[:en:Kasiski examination]]<br />
**** 一致反復率 [[:en:index of coincidence]]<br />
** (現代暗号)<br />
*** [[差分解読法]]（差分暗号解読） [[:en:differential cryptanalysis]] (Biham,1989)<br />
**** 不能差分暗号解読<br />
**** [[切詰差分解読法|切詰差分解読]]（丸め差分攻撃）(truncated differential attack)<br />
**** [[高階差分解読法|高階差分解読]]<br />
***** Square攻撃<br />
**** ブーメラン攻撃 [[:en:boomerang attack]]<br />
**** 補間攻撃 (Jakobsen, Knudsen, 1997)<br />
***** 線形和攻撃<br />
*** [[線形解読法]]（線形暗号解読） [[:en:linear cryptanalysis]] (Matsui,1993)<br />
**** 差分線形攻撃 [[:en:differential-linear attack]]<br />
**** 丸め線形攻撃<br />
*** スライド攻撃 [[:en:slide attack]] (David Wagner, Alex Biryukov, 1999)<br />
*** カイ2乗攻撃<br />
*** mod n攻撃 [[:en:mod n cryptanalysis]]<br />
*** XSL攻撃 [[:en:XSL attack]]<br />
** （暗号プロトコル）<br />
*** リプレイ攻撃 [[:en:replay attack]]<br />
*** ビット反転攻撃 [[:en:bit-flipping attack]]<br />
*** 中継攻撃 [[:en:man in the middle attack]]<br />
** （その他）<br />
*** [[辞書アタック]] / [[辞書攻撃]] [[:en:dictionary attack]]<br />
*** [[素因数分解]] [[:en:integer factorization]]<br />
*** 格子基底縮小 lattice reduction, LLL [[:en:Lenstra-Lenstra-Lovász lattice reduction algorithm]]<br />
* 根拠となる問題 / それに関する仮定<br />
** 素因数分解問題 (IFP)<br />
*** RSA問題 / RSA仮定 [[:en:RSA problem]]<br />
*** flexible RSA問題 / [[強RSA仮定]] [[:en:strong RSA assumption]]<br />
** 離散対数問題 (DLP)<br />
*** DH問題 / Diffie-Hellman仮定<br />
*** DDH問題 / Decision-Diffie-Hellman仮定 [[:en:decisional Diffie-Hellman assumption]]<br />
** [[ナップサック問題]] [[:en:knapsack problem]]<br />
*** [[部分和問題]] [[:en:subset sum problem]]<br />
** ラティス問題<br />
*** SVP / CVP<br />
** [[巡回セールスマン問題]] [[:en:traveling salesman problem]]<br />
* 証明に関する手法 / 仮定 / モデル<br />
** 確率的証明 probabilistically cheacable proofs<br />
** [[ランダムオラクル]]モデル (ROM) / ランダムオラクル仮定<br />
** シミュレーション手法<br />
** ハイブリッドアーギュメント<br />
** [[形式的手法]] formal method<br />
** 帰着の効率<br />
** [[識別不能]]<br />
*** [[negligible]]（無視できる） / [[overwhelming]]（圧倒的）<br />
* 安全性の前提<br />
** [[情報理論的安全性]]<br />
** [[計算量的安全性]]<br />
*** [[指数関数時間]]<br />
*** [[準指数関数時間]]<br />
*** [[多項式時間]]<br />
* そのほか<br />
** [[サイドチャネル攻撃]] [[:en:side channel attack]]<br />
*** 故障利用攻撃<br />
*** タイミング攻撃 [[:en:timing attack]]<br />
**** [[キャッシュ攻撃]]<br />
*** 音響解析攻撃 [[:en:acoustic cryptanalysis]]<br />
*** 電力解析攻撃 [[:en:power analysis]]<br />
**** [[単純電力解析]]攻撃 [[:en:simple power analysis]]<br />
**** [[差分電力解析]]攻撃 [[:en:differential power analysis]]<br />
*** 電磁波解析攻撃（[[テンペスト]] [[:en:TEMPEST]]）<br />
** [[締め上げ暗号分析]] [[:en:rubber-hose cryptanalysis]]<br />
<br />
暗号 (Cipher) 以外の暗号プリミティブについても、同様な安全性の研究がなされている。<br />
* 署名<br />
** 安全条件<br />
*** 全面的解読<br />
*** 一般的偽造<br />
*** 選択的偽造<br />
*** 存在的偽装 [[:en:existential forgery]]<br />
** 攻撃条件<br />
*** 直接攻撃<br />
*** 既知文書攻撃<br />
*** 一般的選択文書攻撃<br />
*** 指向的選択文書攻撃<br />
*** 適応的選択文書攻撃<br />
* ハッシュ関数<br />
** プレイメージ (preimage)<br />
** 2ndプレイメージ<br />
** コリジョン (collision)<br />
* 乱数 - 暗号の観点からの要請<br />
** [[暗号論的擬似乱数生成器|暗号論的擬似乱数列生成器]]<br />
** pseudorandom function（[[:en:Pseudorandom function family]]、「乱数列」（random numbers）ではないことに注意<ref name="PRF" />）<br />
<br />
=== 暗号理論に使用する数学 ===<br />
* [[素数判定]]<br />
* [[素体]]<br />
* [[群 (数学)|群]]<br />
* [[数論]]<br />
** [[:en:Modular arithmetic]]<br />
** [[:en:Modular multiplicative inverse]]<br />
** [[素数]]<br />
** [[ブラム数]]<br />
** [[フェルマーの小定理]]<br />
** [[オイラーのφ関数|オイラーのトーティエント関数]]<br />
** [[中国の剰余定理]]<br />
** 平方剰余 ([[:en:Quadratic residue]])<br />
** [[ガロア体]]（有限体）<br />
** 有限体内の[[離散対数]]<br />
<br />
== 歴史 ==<br />
{{see|暗号史}}<br />
<br />
== 参考文献 ==<br />
* Claude Elwood Shannon, "Communication theory of secrecy system", Bell System Technial Journal, Vol.28-4, pp.656-715, Oct. 1949.<br />
* [[ホイットフィールド・ディフィー|Whitfield Diffie]], Martin E. Hellman, "New directions in cryptography", IEEE Trans. Information Theory, IT-22,6, pp.644-654, Nov. 1976.<br />
* Ron L. Rivest, A. Shamir, Leonard M. Adleman, "A method for obtaining digital signatures and public-key cryptosystems", Communications of the ACM, Vol.21, pp.120-126, Feb. 1978. (最初の発表は1977だが論文公開は78年になった)<br />
* US National Bureau of Standards (NBS, 現NIST) , "Data Encryption Standard", Federal Information Processing Standards Publication 46 (FIPS-46), 1977. <!-- ...おつかれさまでした --><br />
* Ran Canetti, "Universally Composable Security: A New Paradigm for Cryptographic Protocols", Proceeding s IEEE Symposium on Foundations of Computer Science, FOCS 2001, pp.136-145, Oct. 2001.<br />
<!-- :（これらの文献はPDF化されてWEBにて公開されている） // Canetti のは公開されていないようなので削除 --><br />
<br />
== 注 ==<br />
<references/><br />
<br />
== 関連項目 ==<br />
* [[暗号関係の書籍]] / [[暗号研究者の一覧]]<br />
* 暗号評価プロジェクト ---- [[CRYPTREC]] / [[NESSIE]]<br />
* 暗号アルゴリズム標準化 -- [[ISO/IEC_18033]]<br />
* 暗号アプリケーション ---- [[Pretty Good Privacy|PGP]] / [[GNU Privacy Guard|GnuPG]] / [[Transport Layer Security|TLS]] / [[Secure Shell|SSH]]<br />
<br />
== 外部リンク ==<br />
* [http://www.iacr.org/ 暗号学会 International Association for Cryptologic Research]<br />
<br />
{{デフォルトソート:あんこうりろん}}<br />
[[Category:暗号]]<br />
[[Category:暗号技術]]<br />
[[Category:理論]]<br />
<!-- [[Category:応用数学]] --><br />
[[Category:数学に関する記事]]</div>
49.236.225.67
Paillier暗号
2018-08-07T01:23:36Z
<p>49.236.225.67: /* 応用 */</p>
<hr />
<div>{{参照方法|date=2016年10月}}<br />
'''Paillier暗号'''<!-- カナ表記は無出典に記すと独自研究です! -->とは [[Pascal Paillier]] が1999年に提案した[[公開鍵暗号]]方式で、{{math|''m''{{sub|1}}}} の[[暗号文]]と {{math|''m''{{sub|2}}}} の暗号文から {{math|''m''{{sub|1}} + ''m''{{sub|2}}}} の暗号文を計算出来る（'''加法準同型性'''）という性質を満たす。<br />
<br />
[[RSA暗号]]や[[ElGamal暗号]]など、{{math|''m''{{sub|1}}}} の暗号文と {{math|''m''{{sub|2}}}} の暗号文から積 {{math|''m''{{sub|1}}''m''{{sub|2}}}} の暗号文を計算できる（'''乗法準同型性'''）方式は数多いが、加法準同型性を満たす方式はPaillier暗号などごく少数しか知られていない。<br />
<br />
{{mvar|N}} 次の冪乗剰余性を計算することは困難である（合成数剰余仮定）と信じられており、Paillier暗号の安全性はこの仮定に基づいている。<br />
<br />
== 概要 ==<br />
{{math|''p'', ''q''}} を[[素数]]とし、{{math|''N'' {{=}} ''pq''}} とする。<br />
<br />
Paillier暗号は、次の性質が成り立つ事を利用している（証明は後述）。<br />
<br />
{{Indent|<math>(1+N)^M = 1+MN \bmod N^2\,</math> …(1)}}<br />
<br />
上の式で、右辺から {{math|1}} を引いて {{mvar|N}} で割れば {{mvar|M}} が求まる<ref>通常[[離散対数問題]]は困難であるが、以上の事実は、底が {{math|1 + ''N''}} である場合には離散対数問題のインスタンス {{math|(1 + ''N''){{sup|''M''}}}} が容易に解ける事を意味している</ref>｡<br />
<br />
そこで {{math|(1 + ''N''){{sup|''M''}}}} を乱数 {{mvar|R}} で[[マスク (情報工学)|マスク]]したデータ<br />
<br />
{{Indent|<math>C=(1+N)^MR \bmod N^2\,</math>}}<br />
<br />
を {{mvar|M}} の暗号文とみなせば、2つの暗号文 {{math|''C'' {{=}} (1 + ''N''){{sup|''M''}}''R'', ''C''&prime; {{=}} (1 + ''N''){{sup|''M''&prime;}}''R''&prime;}} の積は、<br />
<br />
{{Indent|<math>CC'=\left((1+N)^MR\right)\cdot\left((1+N)^{M'}R'\right)<br />
= (1+N)^{M+M'}R'' \bmod N^2\,</math>}}<br />
<br />
となり、{{math|''M'' + ''M''&prime;}} の暗号文と一致する。 ここで {{math|1=''R''&prime;&prime; = ''RR''&prime;}}。<br />
<br />
すなわち、{{mvar|M}} の暗号文と {{math|''M''&prime;}} の暗号文から {{math|''M'' + ''M''&prime;}} の暗号文が求まった事になるので、加法準同型性が成り立つ。<br />
<br />
しかし上の「暗号」は復号できないので、方式を改良する必要がある。ここで次の事実を使う（証明は後述）。<br />
<br />
{{Indent|{{mvar|N}} の素因数 {{math|''p'', ''q''}} から求まる {{mvar|λ}} が存在し、任意の {{mvar|r}} に対し、{{math|1=(''r''{{sup|''N''}}){{sup|''&lambda;''}} = 1 mod ''N''{{sup|2}}}} …(2)}}<br />
<br />
そこで前述の「暗号」の {{mvar|R}} を {{mvar|r{{sup|N}}}} に置き換えてできる暗号<br />
<br />
{{Indent|<math>C=(1+N)^Mr^N \bmod N^2\,</math>}}<br />
<br />
を考え、これをPaillier暗号と呼ぶ。この暗号が加法準同型性を満たす事は前述と同様の方法で示せる。また {{mvar|N}} の[[素因数]] {{math|''p'', ''q''}}を知っていれば、{{math|''p'', ''q''}} から {{mvar|λ}} を計算し、<br />
<br />
{{Indent|<math>C^{\lambda}=(1+N)^{M\lambda}(r^N)^\lambda = (1+N)^{M\lambda} \bmod N^2\,</math>}}<br />
<br />
を求める事ができる。右辺に式 (1) を適用する事で {{mvar|Mλ}} が求まるので、{{mvar|Mλ}} を {{mvar|λ}} で割る事で平文 {{mvar|M}} が復号できる。<br />
<br />
Paillier暗号の安全性は以下の仮定（'''DCR仮定'''）のもと成り立つ。<br />
<br />
{{Indent|{{math|''p'', ''q''}} を知らない場合、{{math|''r{{sup|N}}'' mod ''N''{{sup|2}}}} は {{math|'''Z'''{{sub|''N''{{sup|2}}}}}} 上の一様乱数と区別がつかない。}}<br />
<br />
実際 {{math|''r{{sup|N}}'' mod ''N''{{sup|2}}}} が一様乱数と区別がつかないのであれば、{{math|''r{{sup|N}}'' mod ''N''{{sup|2}}}} によってマスクされている暗号文 {{math|1=''C'' = (1 + ''N''){{sup|''M''}}''r''{{sup|''N''}} mod ''N''{{sup|2}}}} も一様乱数と区別がつかず、{{mvar|M}} に関するいかなる情報も知る事はできない。<br />
<br />
上では {{math|1 + ''N''}} をベースにして方式を作ったが、{{math|1 + ''N''}} の代わりに {{math|1 + ''kN''}} を使っても同様の方式を実現できる（{{mvar|k}} は {{mvar|N}} と[[互いに素]]な任意の定数）。この方式もPaillier暗号と呼ぶ。<br />
<br />
===<math>\mathbb{Z}^{*}_{n^{2}}</math>の構造===<br />
Paillier暗号は[[群 (数学)|群]] <math>\mathbb{Z}^{*}_{n^{2}}</math> を利用するので、群 <math>\mathbb{Z}^{*}_{n^{2}}</math> の構造を調べる。<math>\mathbb{Z}^{*}_{n^{2}}</math> の位数 {{math|''φ''(''n''<sup>2</sup>)}} は、<br />
: {{math|''φ''(''n''<sup>2</sup>) {{=}} ''n''{{sup|2}}(1 − 1/''p'')(1 − 1/''q'') {{=}} ''n''(''p'' − 1)(''q'' − 1)}}<br />
である。（[[オイラーのφ関数]]参照。）{{mvar|n}} と {{math|(''p'' − 1)(''q'' − 1)}} は互いに素なので、<math>\mathbb{Z}^{*}_{n^{2}}</math> には位数 {{mvar|n}} の部分群 {{mvar|G}} と位数 {{math|(''p'' − 1)(''q'' − 1)}} の部分群 {{mvar|H}} が存在し、<math>\mathbb{Z}^{*}_{n^{2}}=G\times H</math> である（[[アーベル群の基本定理]]より）。<br />
<br />
{{math|''λ'' {{=}} lcm(''p'' − 1, ''q'' − 1)}} とすると、{{mvar|n}} と互いに素な任意の {{mvar|a}} に対し、<br />
:{{math|''a''{{sup|''λ''}} {{=}} 1 mod ''n'',}}<br />
:{{math|''a''{{sup|''nλ''}} {{=}} 1 mod ''n''{{sup|2}}}}<br />
が成立する（[[フェルマーの小定理|カーマイケルの定理]]）。すなわち、群 <math>\mathbb{Z}^{*}_{n},\,\mathbb{Z}^{*}_{n^{2}}</math> の各元の位数はそれぞれ {{math|''λ'', ''nλ''}} である。<br />
<br />
<math>y,z\in\mathbb{Z}^{*}_{n^{2}}</math> が {{math|1=''z'' = ''y{{sup|n}}'' mod ''n''{{sup|2}}}} を満たしているとき、{{mvar|y}} を {{mvar|z}} の '''{{mvar|n}} 乗根'''という。またある <math>y\in\mathbb{Z}^{*}_{n^{2}}</math> が存在して {{math|1=''z'' = ''y{{sup|n}}'' mod ''n''{{sup|2}}}} となっているとき、<math>z\in\mathbb{Z}^{*}_{n^{2}}</math> は '''{{mvar|n}} 乗剰余'''であるという。<br />
<br />
次の定理が成立する:<br />
<br />
'''定理1'''<br />
{{mvar|G}} は {{math|1}} の {{mvar|n}} 乗根全体の集合である。一方 {{mvar|H}} は {{mvar|n}} 乗剰余全体の集合と一致し、{{mvar|H}} の各元の位数は {{mvar|λ}} の[[約数]]である。<br />
<br />
'''証明'''<br />
{{mvar|G}} の位数は {{mvar|n}} なので、{{mvar|G}} の[[元 (数学)|元]]を {{mvar|n}} 乗すると {{math|1}} になる。したがって {{mvar|G}} の元はいずれも {{math|1}} の {{mvar|n}} 乗根である。また <math>\mathbb{Z}^{*}_{n^{2}}=G\times H</math> で {{mvar|H}} の位数は {{mvar|n}} と互いに素なので、{{mvar|G}} 以外の元を {{mvar|n}} 乗しても {{math|1}} にならない。したがって {{mvar|G}} は {{math|1}} の {{mvar|n}} 乗根全体の集合と一致する。<br />
<br />
{{mvar|b}} を {{mvar|H}} の任意の元とする。[[カーマイケルの定理]]より {{math|''b{{sup|nλ}}'' {{=}} 1 mod ''n''{{sup|2}}}} なので、{{mvar|b}} の位数は {{mvar|nλ}} の約数である。また {{mvar|b}} は {{mvar|H}} の元であり、しかも {{mvar|H}} の位数は {{math|(''p'' − 1)(''q'' − 1)}} なので、{{mvar|b}} の位数は {{math|(''p'' − 1)(''q'' − 1)}} の約数でもある。よって {{mvar|b}} の位数は {{mvar|nλ}} と {{math|(''p'' − 1)(''q'' − 1)}} の公約数である。{{mvar|n}} と {{math|(''p'' − 1)(''q'' − 1)}} は互いに素であり、しかも {{mvar|λ}} は {{math|(''p'' − 1)(''q'' − 1)}} の約数なので、{{mvar|nλ}} と {{math|(''p'' − 1)(''q'' − 1)}} の最大公約数は {{mvar|λ}} である。以上の議論より {{mvar|H}} の任意の元の位数は {{mvar|λ}} の約数である。<br />
<br />
{{mvar|y}} を <math>\mathbb{Z}^{*}_{n^{2}}</math> の任意の元とするとき、<math>\mathbb{Z}^{*}_{n^{2}}=G\times H</math> なので、ある {{mvar|G}} の元 {{mvar|a}} とある {{mvar|H}} の元 {{mvar|b}} が存在し、{{math|''y'' {{=}} ''ab''}} となる。{{mvar|G}} の位数は {{mvar|n}} なので、{{math|1=''y''{{sup|''n''}} = (''ab''){{sup|''n''}} = ''b''{{sup|''n''}} &isin; ''H''}} となる。よって {{mvar|n}} 乗剰余は必ず {{mvar|H}} に属する。<br />
<br />
次に {{mvar|b}} を {{mvar|H}} の任意の元とする。{{mvar|λ}} と {{mvar|n}} は互いに素なので、{{math|''m'' {{=}} ''n''{{sup|−1}} mod ''λ''}} が存在する。{{mvar|b}} の位数は {{mvar|λ}} の約数なので、{{math|(''b''{{sup|''m''}}){{sup|''n''}} {{=}} ''b''{{sup|''kλ''}} {{=}} 1 mod ''n''{{sup|2}} (''k'' ∈ '''R''')}}。よって {{mvar|H}} の任意の元 {{mvar|b}} は {{mvar|n}} 乗根 {{mvar|b{{sup|m}}}} を持つ。すなわち {{mvar|H}} の各元は {{mvar|n}} 乗剰余である。以上の議論より {{mvar|H}} は {{mvar|n}} 乗剰余全体の集合と一致する。<br />
<br />
=== {{mvar|G}} の構造===<br />
{{mvar|k}} を任意の整数とするとき、<br />
<br />
: <math>(1+n)^k = 1 + kn + \frac{k(k-1)}{2}n^2 + \cdots<br />
= 1 + kn + n^2\left(\frac{k(k-1)}{2}+\cdots\right) = 1+kn \mod n^2</math><br />
が成立する。同様の議論で、<br />
:<math>(1+ln)^k = 1+kln \mod n^2</math><br />
が成立する事もわかる。<br />
<br />
この事実から、次の定理が分かる。<br />
<br />
'''定理2'''<br />
{{mvar|G}} は {{math|1 + ''n''}} を生成元とする位数 {{mvar|n}} の巡回群である。<br />
<br />
'''証明'''<br />
{{mvar|G}} の位数が {{mvar|n}} であるのはすでに証明済みである。各 {{math|''k'' {{=}} 0, ..., ''n'' − 1}} に対し、{{math|(1 + ''kn''){{sup|''n''}} {{=}} 1 + ''kn''{{sup|2}} {{=}} 1 mod ''n''{{sup|2}}}} なので、{{math|1 + ''kn''}} は {{math|1}} の {{mvar|n}} 乗根である。しかも {{mvar|n}} 個の元 {{math|1 + 0''n'', ..., 1 + (''n'' − 1)''n''}} はいずれも相異なる。{{mvar|G}} の元の個数は {{mvar|n}} だったので、以上の議論より、{{math|1=''G'' = {1 + ''kn'' {{!}} ''k'' = 0, ..., ''n'' − 1}}} である。しかも {{math|(1 + ''n''){{sup|''k''}} {{=}} (1 + ''kn'') mod ''n''{{sup|2}}}} なので、{{math|1 + ''n''}} は {{mvar|G}} の生成元である。<br />
<br />
各 {{math|''k'' {{=}} 0, ..., ''n'' − 1}} に対し、{{math|(1 + ''kn''){{sup|''n''}} {{=}} 1 + ''kn''{{sup|2}} {{=}} 1 mod ''n''{{sup|2}}}} なので、{{math|1 + ''kn''}} は {{math|1}} の {{mvar|n}} 乗根である。しかも {{mvar|n}} 個の元 {{math|1 + 0''n'', ..., 1 + (''n'' − 1)''n''}} はいずれも相異なる。したがって {{math|''G'' {{=}} {1 + ''kn'' {{!}} ''k'' {{=}} 0, ..., ''n'' − 1{{)}}}} である。しかも {{math|(1 + ''n''){{sup|''k''}} {{=}} (1 + ''kn'') mod ''n''{{sup|2}}}} なので、{{math|1 + ''n''}} は {{mvar|G}} の生成元である。<br />
<br />
{{mvar|G}} の任意の元 {{mvar|g}} はある {{math|''k'' &isin; {{mset|0, ..., ''n'' &minus; 1}}}} を用いて {{math|''g'' {{=}} 1 + ''kn'' mod ''n''{{sup|2}}}} と表現できる。そこで関数 {{math|''L'': ''G'' → '''Z'''{{sub|''n''}}}} を<br />
: <math>L \colon u \mapsto (u-1)/n</math><br />
により定義すると、{{math|1=''L''(''g'') = ''k''}} であり、{{mvar|L}} が乗法群 {{mvar|G}} から加法群 {{math|'''Z'''{{sub|''n''}}}} への同型写像である事が分かる。<br />
<br />
==Paillier暗号==<br />
===アイディア===<br />
{{mvar|G}} の任意の元 {{math|''g'' {{=}} 1 + ''kn'' mod ''n''{{sup|2}}}} をひとつ固定し、{{math|''m'' &isin; '''Z'''{{sub|''n''}}}} の暗号文を<br />
: <math>c=g^mr^n \bmod n^2</math><br />
で定義する。ここで {{mvar|r}} は <math>\mathbb{Z}^{*}_{n^{2}}</math> から選ばれた乱数である。<br />
<br />
{{mvar|r{{sup|n}}}} は {{mvar|n}} 乗剰余であるので、{{mvar|H}} の元である。したがって {{mvar|r{{sup|n}}}} の位数は {{mvar|λ}} の約数である。そこで復号の際には秘密の情報 {{mvar|λ}} を用い、{{mvar|c{{sup|&lambda;}}}} を計算すると、<br />
<br />
:<math>c^{\lambda}=(g^mr^n)^{\lambda} =g^{\lambda m}=(1+kn)^{\lambda m} =<br />
1+k \lambda mn \mod n^2\,</math><br />
<br />
となる。よって {{math|''L''(''c''{{sup|''λ''}}) {{=}} ''λkm''}} である。同様の議論により {{math|''L''(''g''{{sup|''λ''}}) {{=}} ''λk''}} も示せるので、{{math|''L''(''c''{{sup|''λ''}})/''L''(''m''{{sup|''λ''}})}} により、平文 {{mvar|m}} を計算できる。<br />
<br />
=== 方式 ===<br />
==== 鍵生成 ====<br />
# 二つの大きな[[素数]] {{math|''p'', ''q''}} をランダムに選び、{{math|''n'' {{=}} ''pq''}} とする。<br />
# {{math|''k'' &isin; '''Z'''{{sub|''n''}}}} を任意に選び、{{math|1=''g'' = 1 + ''kn'' mod ''n''{{sup|2}}}} とする。<br />
# [[公開鍵]] {{math|1=''pk'' = (''n'', ''g'')}} と[[秘密鍵]] {{math|1=''sk'' = (''p'', ''q'')}} を出力する。<br />
<br />
==== 暗号化 ====<br />
{{math|'''Z'''{{sub|''n''}}}} の元 {{mvar|m}} を暗号化するには以下のようにする。<br />
<br />
# <math>\mathbb{Z}^{*}_{n^2}</math> からランダムに {{mvar|r}} を選ぶ。<br />
# <math>c=g^m \cdot r^n \bmod n^2 </math> が暗号文である。<br />
<br />
==== 復号 ====<br />
暗号文 <math>c\in \mathbb{Z}^{*}_{n^{2}} </math> を復号するには {{math|1=''λ'' = lcm(''p'' − 1, ''q'' − 1)}} とし、<br />
<br />
* <math>m = L(c^{\lambda} \mod n^{2}) / L(g^{\lambda} \mod n^{2}) \bmod n</math> <br />
<br />
を出力する。<br />
<br />
=== 備考 ===<br />
{{math|''λ'' {{=}} lcm(''p'' − 1, ''q'' − 1)}} および {{math|1=''L''(''g''{{sup|''&lambda;''}} mod ''n''{{sup|2}})}} は事前計算可能であるので、[http://www.gemplus.com/smart/rd/publications/pdf/Pai99pai.pdf 元論文 (PDF)] に書かれているとおり、復号は[[法 (数学)|法]] {{math|''n''{{sup|2}}}} の元で1回の冪乗演算である。<br />
<br />
=== 準同型性 ===<br />
Paillier暗号の特筆すべき点はその準同型性である。暗号化関数は加法的準同型性を持つ。公開鍵 {{mvar|pk}} と乱数 {{mvar|r}} を使って {{mvar|m}} を暗号化した暗号文を {{math|''E{{sub|pk}}''(''m''; ''r'')}} と表記する。<br />
<br />
*'''平文の加法準同型性'''<br />
:二つの暗号文の積は、それらの平文の和の暗号文になる<br />
:: <math>E_{pk}(m_1;r_1)\cdot E(m_2;r_2)\mod n^2 = E_{pk}(m_1 + m_2;r_1r_2) \mod n^2. \, </math><br />
<br />
また以下の性質を満たす：<br />
:: <math>E_{pk}(m_1;r)\cdot g^{m_2} \mod n^2 = E_{pk}(m_1 + m_2;r) \mod n^2, \, </math><br />
:: <math>E_{pk}(m, r)^{k}\mod n^2 = E_{pk}(km;r^k) \mod n^2. \, </math><br />
<br />
しかし、2つの暗号文だけを与えられた場合に、秘密鍵無しで平文の積の暗号文を計算する方法は知られていない。<br />
<br />
=== 安全性 ===<br />
ランダムに選んだ {{mvar|n}} 乗剰余の分布が <math>\mathbb{Z}^{*}_{n^{2}}</math> 上の一様分布と計算量的識別不能である、という仮定を合成数剰余判定仮定 (DCRA) という。厳密には以下のとおり。<br />
<br />
;'''合成数剰余判定仮定 (DCRA)''':<br />
:任意の多項式時間機械Aに対し<br />
: <math>|Pr[y\gets\mathbb{Z}^{*}_{n^{2}}, z\gets y^n, b\gets A(z,n):b=1]-Pr[z\gets\mathbb{Z}^{*}_{n^{2}}, b\gets A(z,n):b=1]|</math><br />
:は negligible である。<br />
<br />
合成数剰余判定仮定 (DCRA) のもとでは、暗号文 {{math|1=''c'' = ''g{{sup|m}}'' &sdot; ''r{{sup|n}}'' mod ''n''{{sup|2}}}} 中にでてくる {{mvar|n}} 乗剰余 {{math|''r{{sup|n}}'' mod ''n''{{sup|2}}}} は乱数と区別がつかない。よって {{math|1=''c'' = ''g{{sup|m}}'' &sdot; ''r{{sup|n}}'' mod ''n''{{sup|2}}}} から {{mvar|m}} に関する情報を得る事はできず、Paillier暗号が[[IND-CPA]]安全である事が分かる。<br />
<br />
Paillier暗号は加法準同型性を満たすので頑強性を持たず、従って[[IND-CCA2]]安全ではないという欠点を持つ。しかし加法準同型性は電子投票や閾値暗号系のような暗号プロトコルを構築するのに有益である。[[ランダムオラクル|ランダムオラクルモデル]]ではPaillier暗号に藤崎岡本パディングを用いる事でIND-CCA2安全性を達成できるが、パディングを適用した方式は加法準同型性を満たさない。<!--PaillierとPointchevalは平文 {{mvar|m}} と乱数 {{mvar|r}} を組み合わせたハッシュ値を用いてより安全性の高い暗号方式を提案している（パディング方式）。[[Cramer-Shoup暗号]]と同様に、[[ハッシュ関数]]を通すことで、{{mvar|c}} だけを与えられた攻撃者は {{mvar|m}} を意味あるように変更することが出来ない。--><br />
<br />
=== 応用 ===<br />
;電子投票<br />
:可展性が必要とされる状況もある。上記の準同型性は安全な電子投票に役立つ。<br />
:単純な賛成・反対の投票を考えよう。{{mvar|m}} を投票者の数とし、{{math|1}} で賛成の票を、{{math|0}} で反対の票を表すものとする。各投票者は各々の票を暗号化する。集票者は、投票者から集めた暗号化された {{mvar|m}} 個の票をすべて掛けあわせた後、復号する。その結果の値を {{mvar|n}} とすると、これは票に対応する数の和になっている。よって、集票者は {{mvar|n}} 人が賛成票を入れ、{{math|''m'' − ''n''}} 人が反対票を入れたことが分かる。<br />
;電子マネー<br />
:自己ブラインド性（論文で名付けられた）を持つ。これは、平文を変えることなくある暗号文を別の暗号文に作り替えることができることを指す。これは David Chaum によって提唱された電子マネー方式を構成する際に用いられる。<br />
<br />
電子マネーおよび電子投票の目標は、誰のものであるかを明かすことなく紙幣や票が正規のものであることを保障することにある。<br />
<br />
== 脚注 ==<br />
{{reflist}}<br />
<br />
== 参考文献 ==<br />
*[[岡本–内山暗号]]はPaillier暗号に先立って加法的準同型性を達成している。<br />
*[[Damgaard-Jurik暗号]]はPaillier暗号の一般化である。<br />
*[http://security.hsr.ch/msevote/paillier Paillier cryptosystem interactive simulator]では電子投票のデモを行っている。<br />
* Pascal Paillier, [http://www.gemplus.com/smart/rd/publications/pdf/Pai99pai.pdf Public-Key Cryptosystems Based on Composite Degree Residuosity Classes], EUROCRYPT 1999, pp.&nbsp;223–238.<br />
* Pascal Paillier, David Pointcheval, [http://www.gemplus.com/smart/rd/publications/pdf/PP99cca2.pdf Efficient Public-Key Cryptosystems Provably Secure Against Active Adversaries], ASIACRYPT 1999.<br />
* Pascal Paillier, [http://www.gemplus.com/smart/rd/publications/pdf/Pai99phd.pdf PhD Thesis], 1999.<br />
* Pascal Paillier, [http://www.rsasecurity.com/rsalabs/cryptobytes/CryptoBytes_January_2002_final.pdf Composite-Residuosity Based Cryptography: An Overview], CryptoBytes Vol. 5 No. 1, 2002.<br />
<br />
== 関連項目 ==<br />
* [[暗号理論]]<br />
* [[公開鍵暗号]]<br />
<br />
{{cryptography navbox|public-key}}<br />
[[Category:暗号技術]]<br />
[[Category:関数]]<br />
[[Category:数学に関する記事]]</div>
49.236.225.67
内閣官房副長官
2018-07-31T14:41:06Z
<p>49.236.225.67: /* 呼称 */</p>
<hr />
<div>{{政治の役職<br />
|国名 = {{JPN}}<br />
|正式名称 = 内閣官房副長官<br />
|公用語名 = ないかくかんぼうふくちょうかん<br />
|紋章 = Go-shichi no kiri crest.svg<br />
|紋章名 = 国<br />
|現職画像 = <!-- 職に複数就任している可能性がある場合は、掲載しない --><br />
|現職氏名 = [[西村康稔]]（政務・衆）<br />[[野上浩太郎]]（政務・参）<br />[[杉田和博]]（事務）<br />
|現職代数 = <br />
|現職就任日 = <br />
|職務代行者役職 = <br />
|職務代行者氏名 = <br />
|担当官庁 = [[内閣官房]]<br />
|任命者 = [[安倍晋三]]<br />
|任命者役職 = [[内閣総理大臣]]<br />
|任期 = <br />
|初代就任者 = [[周東英雄]]<br />
|設置年月日 = [[1947年]][[5月3日]]<br />
|公式サイト = [http://www.cas.go.jp/ 内閣官房]<br />
|その他 = <br />
}}<br />
'''内閣官房副長官'''（ないかくかんぼうふくちょうかん、Deputy Chief Cabinet Secretary）は、[[内閣官房長官]]を補佐する[[特別職]]の[[国家公務員]]。1998年7月より定員は3人（[[内閣法]]規定）。<br />
<br />
==任免==<br />
内閣官房副長官は[[認証官]]であるが、任命対象の資格要件や副長官相互間の職務分担は[[内閣法]]など法令上は明確には規定されておらず、政務担当として[[衆議院議員]]と[[参議院議員]]から1人ずつの計2人が、事務担当として[[事務次官]]経験者等の[[キャリア (国家公務員)|キャリア]][[官僚]]から1人が、それぞれ任命されるのが慣例となっている。<br />
<br />
== 概要 ==<br />
[[ファイル:Kosei Ueno Yasuo Fukuda Junichiro Koizumi Shinzo Abe and Teijiro Furukawa 20020426.jpg|thumb|left|200px|[[総理大臣官邸]]執務室にて[[内閣総理大臣]][[小泉純一郎]]（中央）や[[内閣官房長官]][[福田康夫]]（左から2人目）と打ち合わせする3名の内閣官房副長官（福田の隣より反時計回りに、[[上野公成]]、[[古川貞二郎]]、[[安倍晋三]]）（[[2002年]][[4月26日]]）]]<br />
内閣官房副長官は内閣官房長官の職務を助け、命を受けて[[内閣官房]]の事務をつかさどり、及びあらかじめ内閣官房長官の定めるところにより内閣官房長官不在の場合その職務を代行する（[[内閣法]]14条第3項）。待遇としては[[副大臣]]と同等（中央省庁改編前は[[政務次官]]待遇）であるが、組閣後の閣僚による記念撮影に同席するなど、他の副大臣とは扱いが異なることが多い。<br />
<br />
政務担当の副長官は当選回数が少なく首相[[派閥]]から首相に近い側近政治家が任命されることが多い。重要性から閣僚経験者が就任する例も少なくなく、これは他の政務次官・副大臣には見られない特徴である。当職経験後に重要な役職を歴任することも多く、若手政治家の登竜門ポスト<ref>読売新聞2011年1月14日</ref>とされている（のちに首相になった官房副長官は2011年現在で[[竹下登]]、[[海部俊樹]]、[[森喜朗]]、[[安倍晋三]]、[[鳩山由紀夫]]の5人）。2011年には、[[財務大臣#日本|大蔵大臣]]・[[財務大臣#日本|財務大臣]]を歴任したベテラン政治家である[[藤井裕久]]、官房長官経験者である[[仙谷由人]]が就任するなど、官邸の機能強化の観点から異例の起用が相次いだ。<br />
<br />
事務担当の副長官は、[[戦前]]の[[内閣書記官長]]の実質的な後継であり、[[中央省庁再編]]以前は旧[[内務省 (日本)|内務省]]系官庁のうち[[警察庁]]、旧[[自治省]]、旧[[厚生省]]の出身者で次官級のポストを経験した者から任命されるのが慣例となっており、省庁再編後も概ね踏襲されてきた<ref>旧内務省系官庁の中で、建設省だけが除外されてきたのは、[[公共事業]]などで直接[[ゼネコン]]と交渉を持つ機会が多く、利権にからみやすい体質があるからだとされている。</ref><ref>高山文彦 『霞が関影の権力者たち』 講談社 p319</ref>。一方で[[第1次安倍内閣]]では[[的場順三]]（旧[[大蔵省]]出身で[[国土庁|国土事務次官]]経験者）が、[[野田内閣]]では[[竹歳誠]]（旧[[建設省]]出身で[[国土交通事務次官]]経験者）が就任するなど近年では慣例にとらわれない起用もなされている。[[事務次官等会議]]（現・次官連絡会議）を運営するなど各省間の調整を主な職務としており、官僚機構の頂点とみなされている。内閣を超えて長期間在任する例も多く、例えば[[石原信雄]]は自民党政権、非自民連立政権、自社さ政権にまたがって在任した。<br />
<br />
[[内閣人事局|内閣人事局長]]は内閣官房副長官の中から指名する者をもって充てられる（内閣法第21条）。<br />
<br />
== 来歴 ==<br />
*[[1945年]]（昭和20年）9月19日 - [[内閣書記官長]]の下に'''内閣副書記官長'''（定数1人）が新設される。<br />
*[[1947年]]（昭和22年）5月3日 - 日本国憲法の施行に伴い、内閣副書記官長を廃して'''内閣官房次長'''（定数1人）が設置される。内閣法でなく「内閣官房及び法制局職員等設置制（昭和22年[[政令]]第2号）」で定められたいわゆる「政令職」。<br />
*[[1947年]]（昭和22年）6月17日 - 内閣官房及び法制局職員等設置制の改正により、定数が2人となる。<br />
<!--この政令の題名は昭和24年2月15日に「内閣官房職員設置制」に改正されますが、この時点では法制局を含むこの題名が正しいので、訂正しないで下さい。--><br />
*[[1949年]]（昭和24年）[[6月1日]] - 内閣官房職員設置制の廃止と[[内閣法]]の一部改正により、政令職の内閣官房次長を廃して法定職の'''内閣官房副長官'''（定数2人）が設置される。<br />
*[[1984年]]（昭和59年）7月1日 - [[総務庁]]の設置に伴い、内閣官房に加えて[[総理府]]（大臣庁等を除く）の総括整理の補佐をも担当する。<br />
*[[1998年]]（平成10年）7月1日 - 内閣法の一部改正により、定数が2人（政務担当、事務担当1人ずつ）から3人（政務担当2人、事務担当1人）に増員される。なお、実際に初めて3人任命されたのは同月31日。<br />
*[[2001年]]（平成13年）1月6日 - 内閣法の一部改正により、いわゆる[[認証官]]になり、その任免は[[天皇]]から認証される。中央省庁再編に伴い、総理府に引き続き[[内閣府]]（大臣庁等を除く）の総括整理の補佐を担当する。<br />
<br />
== 内閣官房副長官一覧 ==<br />
{{Main|歴代の内閣官房副長官}}<br />
{| class="wikitable" border="1"<br />
|+内閣官房副長官（認証官）<br />
|-<br />
! colspan="2"|政務・衆 !! colspan="2"|政務・参 !! 事務 !! 内閣 !! 就任日<br />
|-<br />
| rowspan="2"|'''[[安倍晋三]]''' || rowspan="2"|[[自由民主党 (日本)|自由民主党]] || rowspan="2"|[[上野公成]] || rowspan="2"|自由民主党 || rowspan="2"|[[古川貞二郎]] || [[第2次森内閣 (改造 中央省庁再編後)|第2次森改造内閣]] || [[2001年]]（平成13年）[[1月6日]]<br />
|-<br />
| [[第1次小泉内閣]] || 2001年（平成13年）[[4月26日]]<br />
|-<br />
| [[細田博之]] || 自由民主党 || rowspan="2"|[[山崎正昭]] || rowspan="2"|自由民主党 || rowspan="3"|[[二橋正弘]] || [[第1次小泉内閣 (第2次改造)|第1次小泉第2次改造内閣]] || [[2003年]]（平成15年）[[9月22日]]<br />
|-<br />
| [[杉浦正健]] || 自由民主党 || [[第2次小泉内閣]] || [[2004年]]（平成16年）[[5月7日]]<br />
|-<br />
| [[長勢甚遠]] || 自由民主党 || rowspan="2"|[[鈴木政二]] || rowspan="2"|自由民主党 || [[第3次小泉内閣 (改造)|第3次小泉改造内閣]] || [[2005年]]（平成17年）[[10月31日]]<br />
|-<br />
| [[下村博文]] || 自由民主党 || rowspan="2"|[[的場順三]] || [[第1次安倍内閣]] || [[2006年]]（平成18年）[[9月26日]]<br />
|-<br />
| rowspan="2"|[[大野松茂]] || rowspan="2"|自由民主党 || rowspan="3"|[[岩城光英]] || rowspan="3"|自由民主党 || [[第1次安倍内閣 (改造)|第1次安倍改造内閣]] || [[2007年]]（平成19年）[[8月27日]]<br />
|-<br />
| rowspan="2"|二橋正弘 || [[福田康夫内閣]] || 2007年（平成19年）[[9月26日]]<br />
|-<br />
| [[塩谷立]] || 自由民主党 || [[福田康夫内閣 (改造)|福田康夫改造内閣]] || [[2008年]]（平成20年）[[8月2日]]<br />
|-<br />
| rowspan="2"|[[松本純]] || rowspan="2"|自由民主党 || [[鴻池祥肇]] || 自由民主党 || rowspan="2"|[[漆間巌]] || rowspan="2"|[[麻生内閣]] || 2008年（平成20年）[[9月24日]]<br />
|-<br />
| [[浅野勝人]] || 自由民主党 || [[2009年]]（平成21年）[[5月13日]]<br />
|-<br />
| [[松野頼久]] || [[民主党 (日本 1998-2016)|民主党]] || [[松井孝治]] || 民主党 || rowspan="4"| [[瀧野欣彌]] || [[鳩山由紀夫内閣]] || 2009年（平成21年）[[9月16日]]<br />
|-<br />
| [[古川元久]] || 民主党 || rowspan="3"|[[福山哲郎]] || rowspan="3"|民主党 || [[菅内閣]]<br />[[菅内閣 (第1次改造)|菅第1次改造内閣]] || [[2010年]]（平成22年）[[6月8日]]<br />
|-<br />
| [[藤井裕久]] || 民主党 || [[菅内閣 (第2次改造)|菅第2次改造内閣]] || [[2011年]]（平成23年）[[1月14日]]<br />
|-<br />
| [[仙谷由人]] || 民主党 || [[菅内閣 (第2次改造)|菅第2次改造内閣]] || 2011年（平成23年）[[3月17日]]<br />
|-<br />
| rowspan="2"|[[斎藤勁]] ||rowspan="2"| 民主党 || [[長浜博行]] || 民主党 ||rowspan="2"|[[竹歳誠]] || [[野田内閣]] || 2011年（平成23年）[[9月2日]]<br />
|-<br />
| [[芝博一]] || 民主党 || [[野田内閣 (第3次改造)|野田第3次改造内閣]] || [[2012年]]（平成24年）[[10月1日]]<br />
|-<br />
| [[加藤勝信]] || 自由民主党 ||rowspan="2"| [[世耕弘成]] ||rowspan="2"| 自由民主党 ||rowspan="4"| [[杉田和博]] || [[第2次安倍内閣]]<br/>[[第2次安倍内閣 (改造)|第2次安倍内閣改造内閣]]<br/>[[第3次安倍内閣]] || 2012年（平成24年）[[12月26日]]<br />
|-<br />
| rowspan="2"|[[萩生田光一]] || rowspan="2"|自由民主党 || [[第3次安倍内閣 (第1次改造)|第3次安倍第1次改造内閣]] || [[2015年]]（平成27年）[[10月7日]]<br />
|-<br />
| rowspan="2"|[[野上浩太郎]] || rowspan="2"|自由民主党 || [[第3次安倍内閣 (第2次改造)|第3次安倍第2次改造内閣]] || [[2016年]] (平成28年) [[8月3日]]<br />
|-<br />
| [[西村康稔]] || 自由民主党 || [[第3次安倍内閣 (第3次改造)|第3次安倍第3次改造内閣]]<br />[[第4次安倍内閣]] || [[2017年]] (平成29年) [[8月3日]]<br />
|-<br />
|}<br />
* 内閣官房副長官は国務大臣である内閣官房長官と異なり、日本国憲法第71条の規定が適用されず、新内閣総理大臣の任命と同時に自動失職とはならず在職し続ける官職であるため、新首相の組閣時に自ら辞職願を出し後任のために席を空ける。このため、新副長官任命まで辞職願を出さず形式上在職する（空席を生じさせない）場合と、新副長官任命を待たず即座に辞職する（空席が生ずる）場合があり、後者の場合には後任者任命までの数時間から数日にわたり副長官職は完全な空席になる（長官と副長官補が事実上の職務代行はするが、正式な「副長官事務代理」は置かれない。）。<br />
* 副長官の交代が同時とならず空席を生じた例は次のとおり。<br />
** 前任者の辞職と後任者の任命が同日ながら同時でなく空席を生じたもの<br />
*** 羽田内閣：北村・石川の副長官2名<br />
** 後任者の任命が前任者の辞職の翌日以降まで遅延し空席を生じたもの<br />
*** 小渕内閣：鈴木・上杉・古川の副長官3名は前任者辞職翌日の平成10年7月31日任命（連続再任の古川副長官も辞令上は前日一旦辞職しているので任命まで空席とみなされる）<br />
<br />
== 呼称 ==<br />
[[報道]]でたびたび見られる「'''政府筋'''」とは、「内閣官房副長官の内の誰か」を指す。当該の副長官が[[オフレコ#オフレコにおける肩書き|オフレコ]]で発言したときに使われる。報道において[[内閣官房長官]]を「政府首脳」というのに対して、内閣官房副長官は「政府高官」と置き換えられることが慣習である。<br />
<br />
==脚注==<br />
<references/><br />
<br />
== 関連項目 ==<br />
*[[内閣書記官長]]<br />
*[[内閣官房長官]]<br />
*[[内閣官房副長官補]]<br />
*[[オフレコ#オフレコにおける肩書き|オフレコ]]<br />
*[[副大臣]]<br />
*[[大臣政務官]]<br />
*[[事務次官]]<br />
*[[政務次官]]（廃止）<br />
<br />
{{内閣府}}<br />
{{DEFAULTSORT:ないかくかんほうふくちようかん}}<br />
[[Category:日本の内閣官房]]<br />
[[Category:日本の行政官職]]</div>
49.236.225.67
Warning : Cannot modify header information - headers already sent by (output started at /home/users/1/sub.jp-asate/web/wiki/extensions/HeadScript/HeadScript.php:3) in /home/users/1/sub.jp-asate/web/wiki/includes/WebResponse.php on line 46