情報処理学会論文誌

Vol.59 No.9 1557–1569 (Sep. 2018)

計算機援用セキュリティスキームの一般的構成法
神農 泰圭1,a)

土屋 貴史1

大木 哲史1

高橋 健太2

尾形 わかは3

西垣 正勝1

受付日 2017年12月11日, 採録日 2018年6月8日

概要：CPU の計算機能力は日々向上する．計算機を利用した攻撃に耐性を持たせるためには，秘密情報のエントロピーを増加させる必要がある．しかし，CPU の計算機能力の進化は攻撃者だけでなく，正規ユー
ザにも恩恵を与えるものである．実際に，CPU の計算機能力を使用して正規ユーザの秘密情報の安全性を高めるセキュリティスキームが提案されている．本稿では，そのような「CPU の計算機能力を使用して正規ユーザの秘密情報の安全性を高めるセキュリティスキーム」を「計算機援用セキュリティスキーム
CASS」と呼び，それらをメカニズムの違いにより 2 つのタイプに分類する．そして，一方のタイプに対して，一般的構成法を提案し，その安全性証明を行う．そのタイプの CASS の実現可能性について議論する．
キーワード：暗号，計算機援用セキュリティ，一般的構成法，共通鍵暗号，メッセージ認証コード，公開鍵
暗号，デジタル署名，ユーザ認証

General Constructions of Computer-aided Security Schemes
Yasuyoshi Jinno1,a) Takashi Tsuchiya1 Tetsushi Ohki1 Kenta Takahashi2
Wakaha Ogata3 Masakatsu Nishigaki1
Received: December 11, 2017, Accepted: June 8, 2018

Abstract: CPU performance has been increasing continually. To resist attacks in such a technological environment, we must increase the entropy of secrets. However, the progress of CPU performance beneﬁts not
only attackers but also legitimate users. Security schemes speciﬁcally designed to enhance legitimate users’
security by exploiting CPU performance have been proposed. In this paper, we call such schemes “computeraided security schemes”, or CASS, and classify them into two types in terms of the aiding mechanism. We
propose general constructions and provide security proofs of CASS for one type. We discuss the feasibilityof CASS.
Keywords: cryptology, computer-aided security, general construction, symmetric key encryption, message
authentication code, public key encryption, digital signature, user authentication

1. はじめに
情報セキュリティ技術として共通鍵暗号，メッセージ認

ワードといった秘密情報のエントロピーを増加させると，攻撃に必要な計算量が爆発的に大きくなることを安全性の根拠としている．一方で，ムーアの法則で知られるよう

証コード，公開鍵暗号，デジタル署名，ユーザ認証等の暗に CPU の計算能力もまた時代とともに指数関数的に向上

号プリミティブが広く使用されている．これらの多くは計を続けており，このため秘密情報のエントロピーもまた時

算量的安全性を持つように設計されており，秘密鍵やパス代とともに増加させていく必要がある．しかし，以下に示

1
2
3

a)

すように，秘密情報のエントロピーを増加させることが困
静岡大学
Shizuoka University, Hamamatsu, Shizuoka 432–8011, Japan
株式会社日立製作所
Hitachi Ltd., Yokohama, Kanagawa 244–0817, Japan
東京工業大学Tokyo Institute of Technology, Meguro, Tokyo 152–8552,
Japan
yasu05182002@gmail.com

c 2018 Information Processing Society of Japan

難であるセキュリティスキームが存在する．ユーザがパスワードを記憶して，そのパスワードを秘密情報として扱う「パスワードベーススキーム」においては，ユーザの記憶能力に限界があるため，パスワードのエントロピーを増加させることが困難である．同じ機能を持つ回路でも，製造過1557情報処理学会論文誌

Vol.59 No.9 1557–1569 (Sep. 2018)

程における微細な差異を秘密情報のエントロピーとして利秘密情報補完型 CASS と呼ぶ．

用する PUF [1] の出力を秘密情報として用いて暗号スキー

文献 [7] では，秘密情報補完型 CASS の具体的なインスムを構築することができる．また，生体情報を鍵として用タンスとして，ユーザ認証について詳述した．しかし，そいて，暗号スキームを構築しようとする試み（バイオメトのユーザ認証スキームの安全性証明はなされていない．まリック暗号）が存在する [2]．このように，PUF の出力や，た，ユーザ認証以外の暗号システムへの適用については，

生体情報を秘密情報として用いる場合でも，情報源に限り検討されていない．

があるため，秘密情報のエントロピーを増加させることが困難である．
これに対し，「正規ユーザの計算機能力を用いて秘密情報のセキュリティを強化する」というアプローチの研究もされている．これらの研究では，CPU の計算能力の進化は攻撃者のみを有利にするものではなく，正規ユーザにも恩そこで本稿では，ユーザ認証を含む様々なプリミティブに対しての秘密情報補完型 CASS の一般的構成法を提案し，その安全性証明を行う．具体的には，以下のとおりである．
初めに，文献 [7] のユーザ認証スキームを一般化した秘密情報補完型 CASS のモデルを定義する．

恵を与えることに注目し，システムの安全性を高めるため

次に，様々なプリミティブに対して，秘密情報補完型に正規ユーザがその時代の計算能力を活用する方法を提案

CASS の一般的構成法を提案する．より正確には，任意のしている．著者らは，このアプローチによるセキュリティ

共通鍵暗号，メッセージ認証コード，公開鍵暗号，デジタ確保の概念を計算機援用セキュリティと呼ぶ．計算機援用

ル署名，チャレンジ&レスポンス（C&R）型ユーザ認証ス

セキュリティスキーム CASS として，パスワードベース鍵

キームを，秘密情報補完型 CASS へ変形する構成方法を提生成関数 bcrypt [3]，PBKDF2 [4] や，計算機援用ユーザ認

案する．秘密情報拡張型の CASS の安全性は，ランダムオ

証 [7] が提案されている．

ラクルモデルと，用いるプリミティブの安全性をもととしパスワードベース鍵生成関数 f は，ハッシュ関数や鍵スているが，秘密情報補完型 CASS の安全性は，興味深いこ

ケジューリング関数の反復演算によって，入力された短いとに，用いるプリミティブの安全性のみをもととしている．

秘密情報 sshort から，長い秘密情報 slong を生成する．鍵生成に時間を要する分，攻撃者の攻撃試行の速度を減速させることができ，これによって入力値のエントロピー不足を補っている．本稿では，f (sshort ) を秘密情報として使う

最後に，秘密情報補完型 CASS の実現可能性について議論する．

2. 計算機援用セキュリティスキーム：CASS

スキームを秘密情報拡張型 CASS と呼ぶ．f における反暗号スキームにおいては，正規ユーザは秘密鍵や秘密情

復演算回数を L 回とする．文献 [5], [6] では f に関する安報 slong を記憶，もしくは所持する．典型的には，そのス全性が解析されており，文献 [6] では，f (sshort ) を同じ長

キームのセキュリティパラメータ k は slong のビット長でさの一様乱数と識別するためには，sshort を同じ長さの一ある．多くは k = 128 である [8]．

様乱数と識別する場合に比べて，L 倍の計算量が必要なこ

一方で，CASS においては，正規ユーザが「秘密に」記とが証明されている．この結果を用いれば，秘密情報拡張

憶，もしくは所持する情報としては，ku （< k ）ビットの型 CASS の一般的な安全性を解析することが可能であり，sshort のみでよい．すなわち，CASS とは，sshort から slong

log2 L ビット分の安全性が上乗せされることが証明できる．

を生成する，もしくは復元するという計算機援用メカニズ

しかし，文献 [6] では，証明においてランダムオラクルモ

ムを用いて，sshort のセキュリティを強化することが可能

デルを仮定しているため，このような CASS を現実のシスなセキュリティスキームである．

テムとして使用することを考えたときには問題が発生する可能性がある．

秘 密 情 報 補 完 型 CASS に お い て は ，slong は slong =sshort r という 2 つの部分からなり，ユーザは sshort のこの問題に対し著者らは文献 [7] で，短い秘密情報を拡みを秘密に記憶，もしくは所持する．sshort と r は独立であ張するのではなく，十分なエントロピーを持つ情報の一部るため，秘密情報拡張型とは異なり，sshort のみから slong

のみを記憶すればよい CASS を提案した．このユーザ認証を求めることはできない．そのため，ユーザは追加の情報

スキームでは，sshort に，ランダムビット列 r がパディングとして，sshort から r を復元するためのヒントが必要となされる．すなわち，sshort r = slong が秘密情報として登録

る．そのヒントは公開情報であり，攻撃者も知ることがでされ，ユーザは sshort のみを秘密に記憶，所持する．ここきるため，設計には気をつけなければならない．秘密情で，sshort r は sshort と r のビット列の連結を表す．認証

報補完型 CASS の典型的な例は，文献 [7] のユーザ認証ス

フェーズでは，サーバは r のヒント（sshort r の二重ハッキームである．

シュ値 h(h(sshort r))）をユーザに送り，ユーザは sshort とr はシステムが生成した一様乱数である．一方，sshort

ヒントを用いた総当たり探索により，r を復元し，認証されは，ユーザが選んだビット列とすることもできるし，シスる．本稿では，このようなコンセプトに基づく CASS を，テムが生成した一様乱数とすることもできる．

c 2018 Information Processing Society of Japan

1558

情報処理学会論文誌

Vol.59 No.9 1557–1569 (Sep. 2018) short , c, hint) を出力する．すべて入力とし，m = Dec(s3. CASS の一般的構成法

 k , str )，m に 対 し て ，の k ，str ，(sshort , hint) ← Gen(1

本章では，共通鍵暗号，メッセージ認証コード，公開鍵
暗号，デジタル署名，C&R 型ユーザ認証の各プリミティ
ブに対する秘密情報補完型 CASS の一般的な構成法を説明し，その安全性証明を行う．

 short , Enc(s short , m, hint), hint) = m が成り立つ確Dec(s率は 1 に限りなく近いこと（正当性）が要求される．

SKE に対する攻撃ゲームは，ΠSKE に対する攻撃ゲーΠムとほぼ同様に定義できる．異なる部分は，オラクルが Enc,
 Dec)
 を実行し，Gen(Gen, Enc, Dec) ではなく (Gen,
3.1 計算機援用共通鍵暗号において sshort と hint が生成され，hint を攻撃者が知るこ

3.1.1 モデルとができるという点である．たとえば，IND-P2-C2 の攻撃

通 常 の 共 通 鍵 暗 号 ΠSKE は 3 つ の ア ル ゴ リ ズ ム

 k , str ) により (sshort , hint)
ゲームにおいては，初めに，Gen(1(Gen, Enc, Dec) からなる．鍵生成アルゴリズム Gen は，が生成される．攻撃者は，hint を与えられて，適応的に暗k1 を入力とし，一様ランダムに k ビット列 slong を生成し，号化，復号，チャレンジオラクルにクエリを送る．攻撃者

それを秘密鍵として出力する．暗号化アルゴリズム Enc

が mi ，もしくは cj を，それぞれ暗号化オラクル，復号オラ

は slong と平文 m ∈ {0, 1}l(k) を入力とし，暗号文 c を出力l(k)する．ここで，l(k) は k に関する多項式であり，{0, 1}

 short , mi , hint)，
クルに送ると，そのオラクルは ci = Enc(s short , cj , hint) を返す．攻撃者が，(m∗0 , m∗1 ) を
mj = Dec(sは l(k) ビット長のビット列の集合を表す．Enc は確率的チャレンジオラクルに送ると，そのオラクルはランダムにアルゴリズムとなりうる．復号アルゴリズム Dec は slong

 short , m∗ , hint) をチャレンジビット b を選び，c∗b = Enc(sbと c を入力とし，m を出力する．Dec は決定的アルゴリk

計算し，それを返す．最後に，攻撃者は推測ビット b を出ズムである．すべての k ，slong ← Gen(1 )，m に対して，力する．b = b であれば攻撃者の勝ち．

Dec(slong , Enc(slong , m)) = m であること（正当性）が要

3.1.2 一般的構成法

ΠSKE の安全性モデルは，様々な定義が存在する．そのSKE = (Gen, Enc,

ΠSKE = (Gen, Enc, Dec) を用いて，Π を次のように構成できる．我々の構成では，すべてのDec)

中で最も強い安全性は選択平文暗号文攻撃に対する識別不 において一様ランダ
プリミティブにおいて，sshort は Gen

可能性（IND-P2-C2）[9] である．IND-P2-C2 の攻撃ゲー

ムに生成される．

ムでは，初めに，Gen(1k ) により，slong が生成される．攻 k , str )：1k を入力とし，秘密鍵
鍵&ヒント生成 Gen(1

撃者は，暗号化オラクル，復号オラクル，チャレンジオラ

slong = Gen(1k ) を生成する．次に，一様ランダムに N

クルに対して，適応的にクエリを送ることができる．攻撃個の平文 m0 , . . . , mN −1 を選び，それに対応する暗号文

求される．

者が mi ，もしくは cj を，それぞれ暗号化オラクル，復号
オラクルに送ると，そのオラクルは ci = Enc(slong , mi )，c0 = Enc(slong , m0 ), . . . , cN −1 = Enc(slong , mN −1 ) を生成する．N の決め方については後述する．(sshort , hint) を

mj = Dec(slong , cj ) を返す．攻撃者が，(m∗0 , m∗1 ) をチャ出力する．ここで，slong = sshort r，|sshort | = |str | = ku ，

レンジオラクルに送ると，そのオラクルはランダムにチャ

hint = ((m0 , c0 ), . . . , (mN −1 , cN −1 )) である．
 short , m, hint)：初 め に ，Dec((sshort r),
暗 号 化 Enc(sレンジビット b を選び，c∗b = Enc(slong , m∗b ) を計算し，それを返す．最後に，攻撃者は推測ビット b を出力する．

b = b であれば攻撃者の勝ち．攻撃者のアドバンテージは|Pr[b = b ] − 1/2| で定義される．
SKE も，ΠSKE と同様に，3 つ
計算機援用共通鍵暗号 Π Enc,
 Dec)
 からなる．鍵&ヒント生のアルゴリズム (Gen,k は，1 と str ∈ {0, 1}ku を入力とし，成アルゴリズム Gen
 は，str を
sshort ∈ {0, 1}ku とヒント hint を出力する．Gen
そのまま sshort として使うことや，その長さ ku のみを使うこともできる．前者は，ユーザ自身が sshort を選ぶことができることを意味し，後者は，sshort がランダム ku ビット列とな

c0 ) = m0 , . . . , Dec((sshort r), cN −1 ) = mN −1 をすべて満たす r を総当たりで探索し，slong = sshort r を復元する．次に，slong を用いて m を暗号化し，暗号文 c = Enc(slong , m)を出力する．

 short , c, hint)：Enc
 と同様の方法で，sshort と復号 Dec(shint を用いて slong を復元する．次に，c を復号し，平文
m = Dec(slong , c) を出力する．
N の値は，次のように決定する．ランダムに選ばれた
slong = (sshort r), m0 , . . . , mN −1 に対して，ることを意味する．他のプリミティブの CASS における鍵

Dec((sshort r ), Enc((sshort r), m0 )) = m0

（もしくは，秘密情報）&ヒント生成アルゴリズムにおいても..
.

str を入力とするが，その使用方法は上記と同様である．暗 は，秘密鍵 slong の代わりに，sshort ，号化アルゴリズム Enc

 short , m, hint)
平文 m，hint を入力とし，暗号文 c = Enc(s は sshort ，c，hint をを出力する．復号アルゴリズム Dec
c 2018 Information Processing Society of Japan

Dec((sshort r ), Enc((sshort r), mN −1 )) = mN −1

SKEが成り立つ r（= r）が存在する確率を δ(N ) とする．Π
においては，確率（1 − δ(N )）で，ユーザはヒントから正1559

Vol.59 No.9 1557–1569 (Sep. 2018)

情報処理学会論文誌

しい r を復元できる．そこで，δ(N ) が無視できるほど小SKE
Proof. B が，暗号化，復号，チャレンジオラクルと，Π

さくなる N を選ぶ．

に対する IND-P2-C2 ゲームに無視できないアドバンテー

このように N を選択することによって，圧倒的確率

ジ ε で勝利する A を使って（A の勝利確率は 1/2 ± ε），(1 − δ(N )) でヒントから正しい r が復元できるため，正当ΠSKE に対する IND-P2-C2 ゲームに無視できないアドバ性が成り立つ．

ンテージで勝利しようとしている状況を考える．

具 体 的 な N の 値 に つ い て は 方 式 ΠSKE に よ る が ，SKE にここで，ΠSKE に対する IND-P2-C2 ゲームと，ΠΠSKE が 理 想 的 な ラ ン ダ ム 性 を 持 つ と 仮 定 す る と ，

対する IND-P2-C2 ゲームは，攻撃の際に hint を入手でき−(N l(k)−k+ku )δ = 2が十分小さくなるように N を選べ

ば よ い ．こ の と き ，r = r な ら ば 任 意 の m に 対 し てSKE に対する IND-P2-C2 ゲーム）否か（ΠSKE にるか（Π対する IND-P2-C2 ゲーム）が異なるのみである．そのたPr[Dec((sshort r ), Enc((sshort r), m)) = m] = 1/2l(k) がめ，B はオラクルとのやりとりを通して，A に入力するた成り立つので，δ(N ) は，

めの hint を生成し，A に入力する．それ以降は，B は A
からのクエリをそのままオラクルに送り，オラクルからのδ(N ) = Pr[∃r (= r)∀i ∈ {0, . . . , N − 1}

返答をそのまま A に返してやるだけでよい．B は，A に: Dec((sshort r ), Enc((sshort r), mi ))入力するための hint を生成するために，クエリ回数が A= mi ]

よりも N 回多くなる．
具体的には，次のような手順となる．初めに，Gen(1k )= 1 − Pr[∀r (= r)∃i ∈ {0, . . . , N − 1}
: Dec((sshort r ), Enc((sshort r), mi ))= mi ]


=1−

1−


≈1− 1−

1
2l(k)

k−ku

2
2N l(k)

ランダムに平文 m0 , . . . , mN −1 を生成し，m0 , . . . , mN −1

N 2k−ku −1 k−ku2
2N l(k)よ り ，秘 密 鍵 slong が 生 成 さ れ る ．B は ，A に hint で
あ る 平 文 と 暗 号 文 の N ペ ア を 入 力 す る た め に ，一 様
を 暗 号 化 オ ラ ク ル へ と 送 る ．暗 号 化 オ ラ ク ル は c0 =


1 より

= 2−N l(k)+k−ku = δとなる．たとえば，l(k) = k = 128，ku = 102 であるとき，

δ < 2−128 としたいならば N = 2 とすればよい．
実際に利用される ΠSKE は理想的なランダム性を持たな
いため，さらに大きな N を使う必要がある．なお，平文空間が非常に小さい場合には，δ(N ) を無視できるほど小さくすることが困難であるため，我々の構成によって計算機
援用共通鍵暗号は構成できない．

3.1.3 安全性証明

 において一様ランダムに
我々の構成では，sshort は Gen生成されるため，slong は一様乱数となる．それにより，ランダムオラクル仮定を必要とせず，次のことが証明できる．
他のプリミティブに対しても同様である．

SKE は，
上記の構成法を用いて ΠSKE から構成された Π
ΠSKE とほとんど同じ安全性を持つことを証明する．ここSKEでは，もし ΠSKE が最も強い安全性を持っていたら，Πも最も強い安全性を持つことを証明する．

Enc(slong , m0 ), . . . , cN −1 = Enc(slong , mN −1 ) を B に返す．B は ((m0 , c0 ), . . . , (mN −1 , cN −1 )) を hint として A に入力する．この時点で B は A を起動する．A は，B に miもしくは cj を適応的に送ってくる．B は，mi が送られてきたら，暗号化オラクルに mi を送り，ci = Enc(slong , mi )を得て，A に ci を返す．同様にして，B は，cj が送られてきたら，mj = Dec(slong , cj ) を得て，A に返す．A が，(m∗0 , m∗1 ) を B に送ってきたら，B はチャレンジオラクルに(m∗0 , m∗1 ) を送る．チャレンジオラクルはランダムにチャ
レンジビット b を選び，c∗b = Enc(slong , m∗b ) を計算し，Bにそれを返す．B は，A に c∗b を返す．最後に，A は推測

ビット b を出力するので，B は b を出力する．

SKE では確率 (1 − δ(N )) で正しい r が復元され，このΠSKE に対する IND-P2-C2
確率で，上記の A の環境は，Π
ゲームと同じとなり，A は確率 1/2 ± ε で b = b となる

b を出力する．一方，確率 δ(N ) で，上記の A の環境は，
SKE に対する IND-P2-C2 ゲームとは異なる環境となり，
Π
A が b = b となる b を出力する確率は不明である．したがって，B が ΠSKE の IND-P2-C2 ゲームに勝利する確
率は，

SKE もTheorem 1. ΠSKE が IND-P2-C2 安全ならば，Π
また IND-P2-C2 安全である．より正確には，ΠSKE に対Pr[r を復元可能] Pr[b = b | r を復元可能]

して，暗号化，復号クエリを合計 q 回行い，無視できな= (1 − δ(N )) Pr[b = b | r を復元可能]

いアドバンテージで IND-P2-C2 ゲームに勝利する攻撃者

A が存在するならば，ΠSKE に対して，暗号化，復号クエ+ Pr[r を復元不可能] Pr[b = b | r を復元不可能]+ δ(N ) Pr[b = b | r を復元不可能]

リを合計 q + N 回行い，無視できないアドバンテージでとなる．A が確率 1/2 + ε（0 < ε < 1/2）で b = b となる

IND-P2-C2 ゲームに勝利する攻撃者 B が存在する．

b を出力する場合は，

c 2018 Information Processing Society of Japan


1560

情報処理学会論文誌

Vol.59 No.9 1557–1569 (Sep. 2018)

Pr[B が ΠSKE の IND-P2-C2 ゲームに勝利する]≥ (1 − δ(N )) Pr[b = b | r を復元可能]+ δ(N ) × 0 = (1 − δ(N ))(1/2 + ε)
= 1/2 + ε − δ(N )(1/2 + ε)

 short , m, hint)
ジ m，hint を入力とし，認証子 t = Mac(s は sshort ，m，t，hintを出力する．検証アルゴリズム Ver

子として受理し，b = 0 なら不正な認証子として拒否する．

となり，B のアドバンテージは ε − δ(N ) 以上となる．一方，A が確率 1/2 − ε（0 < ε < 1/2）で b = b となる b
を出力する場合は，同様にして，B のアドバンテージはε − δ(N ) 以上となる．すなわち，B のアドバンテージはε − δ(N ) となる．

 k , str )，m に対しすべての k ，str ，(sshort , hint) ← Gen(1 (sshort , m, Mac(s short , m, hint), hint) = 1 が成り立て，Verつ確率は 1 に限りなく近いこと（正当性）が要求される．

Mac に対する攻撃ゲームは，ΠMac に対する攻撃ゲーΠSKE に対す
ムとほぼ同様に定義できる．異なる部分は，Π
る攻撃ゲームと同様に，オラクルが (Gen, Mac, Ver ) では

Q.E.D.
同様にして，ΠSKE が「適応的選択平文，もしくは，非適応的選択平文攻撃，既知平文攻撃」に対する「識別不可能性，もしくは，一方向性，鍵回復攻撃耐性」を持つなら

SKE も同じ安全性を持つことが証明できる．
ば，Π
3.2 計算機援用メッセージ認証コード
3.2.1 モデル
通常のメッセージ認証コード ΠMac は 3 つのアルゴリ
ズム (Gen, Mac, Ver ) からなる．鍵生成アルゴリズム Gen
は，1k を入力とし，一様ランダムに k ビット列 slong を生成し，それを秘密鍵として出力する．認証子生成アルゴリ
ズム Mac は slong とメッセージ m ∈ {0, 1}∗ を入力とし，認証子 t ∈ {0, 1}l を出力する．ここで，{0, 1}∗ は有限長のビット列の集合を表す．Mac は確率的アルゴリズムとな
りうる．検証アルゴリズム Ver は slong と m と t を入力とし，検証結果 b を出力し，b = 1 なら正当な認証子として受理し，b = 0 なら不正な認証子として拒否する．Ver は決定的アルゴリズムである*1 ．すべての k ，slong ← Gen(1k )，m に対して，Ver (slong , m, Mac(slong , m)) = 1 であること（正当性）が要求される．

ΠMac の安全性モデルは，様々な定義が存在する．その中で最も強い安全性は適応的選択メッセージ攻撃に対するメッセージ認証子の存在的偽造不可能性（EUF-CMA）である．EUF-CMA の攻撃ゲームでは，初めに，Gen(1k ) より，slong が生成される．攻撃者は，認証子生成オラクル
に対して，適応的にクエリを送ることができる．攻撃者がmi を認証子生成オラクルに送ったら，そのオラクルは，
ti = Mac(slong , mi ) を返す．最後に攻撃者は，クエリしたメッセージ以外のメッセージ m∗ と認証子 t∗ を出力する．

Ver (slong , m∗ , t∗ ) = 1 であれば攻撃者の勝ち．
Mac も，ΠMac と同様
計算機援用メッセージ認証コード Π Mac,
 Ver ) からなる．鍵&ヒに，3 つのアルゴリズム (Gen, は，1k と str ∈ {0, 1}ku を入力
ント生成アルゴリズム Gen
上述したとおり，Mac は確率的になりうるが，一般的には決定的であるため，Ver では，Mac で認証子を再計算して，受け取った認証子と等しいかを確認する．

c 2018 Information Processing Society of Japan は，秘密鍵 slong の代わりに，sshort ，メッセー
ゴリズム Macを入力とし，検証結果 b を出力し，b = 1 なら正当な認証≥ 1/2 + ε − δ(N ) (1/2 + ε ≤ 1 より)*1とし，sshort ∈ {0, 1}ku と hint を出力する．認証子生成アル

 Mac,
 Ver ) を実行し，攻撃者が hint を得るこなく，(Gen,とができるという点である．

3.2.2 一般的構成法

MAC = (Gen,ΠMAC = (Gen, Mac, Ver ) を用いて，Π Ver ) を次のように構成できる．
Mac, k , str )：1k を入力とし，秘密鍵
鍵&ヒント生成 Gen(1slong = Gen(1k ) を生成する．次に，一様ランダムに N
個のメッセージ m0 , . . . , mN −1 を選び，それに対応する認証子 t0 = Mac(slong , m0 ), . . . , tN −1 = Mac(slong , mN −1 )を生成する．(sshort , hint) を出力する．ここで，slong =sshort r，|sshort | = |str | = ku ，hint = ((m0 , t0 ), . . . ,(mN −1 , tN −1 )) である．
 short ,m,hint)：初めに，Ver ((sshort r),
認証子生成 Mac(sm0 ,t0 ) = 1,...,Ver ((sshort r),mN −1 ,tN −1 ) = 1 をすべて満たす r を総当たりで探索し，slong = sshort r を復元する．
次に，slong を用いて m から認証子 t = Mac(slong , m) を生成し，出力する．

 (sshort , m, t, hint)：Mac
 と同様の方法で，sshort
検証 Verと hint を用いて slong を復元する．次に，slong を用いて

m と t に対して検証を行い，検証結果 b = Ver (slong , m, t)を出力する．

N の 決 定 に つ い て は ，共 通 鍵 暗 号 の 場 合 と 同 様 に ，Ver ((sshort r ), mi , ti ) = 1 がすべての i ∈ {0, . . . , N − 1}について成り立つような r（= r）が存在する確率 δ(N ) が無視できるほど小さくなるように選ぶ．このとき，r は圧倒的確率で正しく復元されるため，正当性が成り立つ．
具体的な N の値は ΠMac に依存する．一般に，MAC には CBC-MAC 等のブロック暗号を利用した方式と，HMAC
等のハッシュ関数を利用した方式がある．一般的に Ver では，Mac で認証子を再計算して，受け取った認証子と等しいかを確認することに注意されたい．

ΠMAC がブロック暗号を使用したアルゴリズムである場
合，そのブロック暗号が理想的なランダム性を持つと仮定
すると，

Pr[Mac((sshort r ), mi ) = Mac(slong , mi )] = 1/2l

1561

情報処理学会論文誌

Vol.59 No.9 1557–1569 (Sep. 2018)

が 成 り 立 つ た め ，共 通 鍵 暗 号 の 場 合 と 同 様 に δ(N ) =3.3 計算機援用公開鍵暗号

2−l·N +(k−ku ) が求まる．すなわち，l · N が k − ku より

3.3.1 モデル

十分大きくなるように，N の値を設定すればよい．たとえ

通 常 の 公 開 鍵 暗 号 ΠPKE は 3 つ の ア ル ゴ リ ズ ム

ば，l = 256，k = 128 の CBC-MAC で，ku = 102 である(Gen, Enc, Dec) からなる．鍵生成アルゴリズム Gen はとしたいならば，N = 1 に設定すればよい．

1k（k はセキュリティパラメータ）を入力とし，秘密鍵 sk ，

実際に利用されるブロック暗号は理想的なランダム性を

公開鍵 pk を出力する確率的アルゴリズムである．ここで，持たないため，さらに大きな N を使う必要がある．なお，

Gen が用いる乱数 r を kl (k) ビットとし，乱数を明示すメッセージ空間が非常に小さい場合には，δ(N ) を無視でる場合は，Gen(1k ; r) と書くことにする．暗号化アルゴリ

きるほど小さくすることが困難であるため，我々の構成にズム Enc は pk と平文 m を入力とし，暗号文 c を出力す

よって計算機援用メッセージ認証コードは構成できない．

る．復号アルゴリズム Dec は sk と c を入力とし，m を出

一方，ΠMAC がハッシュ関数を使用したアルゴリズムで力する．すべての k ，(sk , pk ) ← Gen(1k ; r)，m に対して，ある場合，N = 1 で十分である．なぜならば，δ(1) が有意

Dec(sk , Enc(pk , m)) = m であること（正当性）が要求さに高ければ，それは用いているハッシュ関数の衝突困難性

れる．

場合，δ < 2−kを破っていることになる．すなわち，用いているハッシュΠPKE の安全性モデルは，様々な定義が存在する．その関数が衝突困難性を有していれば，δ(1) は無視できるほど中で最も強い安全性は，適応的選択暗号文攻撃に対する識小さい値となる．

別不可能性（IND-CCA2）[10] である．IND-CCA2 の攻撃

3.2.3 安全性証明

ゲームは，IND-P2-C2 の攻撃ゲームとほぼ同様に定義でき

MAC は，
上記の構成法を用いて ΠMAC から構成された Π

る．異なる部分は，初めに，Gen(1k ; r) より，(sk , pk ) がΠMAC とほとんど同じ安全性を持つことを証明する．こ

生成され，pk が攻撃者に与えられ，攻撃者は任意の平文

こでは，もし ΠMAC が最も強い安全性を持っていたら，に対する暗号文を自分で計算することができるという点で

MAC も最も強い安全性を持つことを証明する．
Π
MAC
Theorem 2. ΠMAC が EUF-CMA 安全ならば，ΠMAC にもまた EUF-CMA 安全である．より正確には，Π

ある．
素因数分解を基とした公開鍵暗号の鍵生成アルゴリズムに対しては，安全のために，非常に長いビット長の一様乱数

対して，認証子生成クエリを合計 q 回行い，無視できないを入力することが望ましい．しかし，そのような一様乱数

確率で EUF-CMA ゲームに勝利する攻撃者 A が存在するは生成が困難であるため，実際には，その代わりに，擬似乱ならば，ΠMAC に対して，認証子生成クエリを合計 q + N

数が用いられる．たとえば，RSA 暗号 [11] の sk は，ランダ回行い，無視できない確率で EUF-CMA ゲームに勝利すムに選ばれた素数 p，q と，(p − 1)(q − 1) と互いに素な数のる攻撃者 B が存在する．

中からランダムに選ばれた e によって生成される．そして，

Proof. Theorem 1 の証明とほぼ同様である．異なる部分

実際の運用において，p，q として，一様乱数の代わりに擬似は，Theorem 1 の証明における IND-P2-C2 が，EUF-CMA

乱数生成器 PRG [12] より生成された擬似乱数が用いられ

MAC に対するに置き換わる点である．ここで，A は，Π

る．したがって，実際に ΠPKE を運用する場合には，一般にEUF-CMA ゲームに無視できない確率 ε で勝利する．

PRG
PRG を用いた以下のような公開鍵暗号 ΠPKEが利用され

確率 1 − δ(N ) で，r = r となるすべての r に対しPRGている．ΠPKE
は 3 つのアルゴリズム (Gen PRG , Enc, Dec)て，Ver ((sshort r), m0 , t0 ) = 1, . . . , Ver ((sshort r), mN −1 ,からなる．鍵生成アルゴリズム Gen PRG は，1k を入力とし，

tN −1 ) = 1 の少なくとも 1 つが成り立ち，このとき，BMAC に対すによってシミュレートされた A の環境は，Π

(sk , pk ) = Gen(1k ; PRG(seed )) を出力する．ただし，seed

る EUF-CMA ゲームと同じとなり，B は ΠMAC に対するPRGと同様に，正当性が要求される．ΠPKE
に対する攻撃ゲー

EUF-CMA ゲームに確率 ε で勝利することができる．しムは，初めに Gen PRG より (sk , pk ) が生成されること以外

たがって，B は確率 (1 − δ(N ))ε > ε − δ(N ) で ΠMAC のは，ΠPKE に対する攻撃ゲームとまったく同様である．

EUF-CMA ゲームに勝利する．

は Gen PRG が用いる k ビットの一様乱数である．ΠPKE

上述したように，素因数分解を基とした公開鍵暗号におQ.E.D.

いては，安全のために，非常に長いビット長の一様乱数を同様にして，ΠMAC が「非適応的選択メッセージ攻撃，

鍵生成アルゴリズムに入力することが望ましい．そして，

もしくは，既知メッセージ攻撃」に対する「存在的偽造不長い一様乱数を用いることにより，秘密鍵もまた，非常に可能性，もしくは，選択的偽造不可能性，一般的偽造不可

長いビット列となる．たとえば，RSA 暗号の秘密鍵は，現

MAC も同じ安全性を持つことが証能性」を持つならば，Π

時点で 2,048 ビット [8] である．そのため，秘密鍵を直接明できる．

復元するという計算機援用方法は現実的ではない．もし，

slong = sshort r を秘密鍵として用いた場合，sshort が記憶，
もしくは所持できないほど長いビット長となるか，もしく

c 2018 Information Processing Society of Japan


1562

情報処理学会論文誌

Vol.59 No.9 1557–1569 (Sep. 2018)は r が総当たりで探索できないほど長いビット長となる．

を証明する．安全性証明は，次の 2 段階で行う．1 段階目

PRG
PKE においても，ΠPKE
そこで，計算機援用公開鍵暗号 Π

PRGとして，ΠPKE より構成された ΠPKE
は，安全な PRG をと同様に，PRG を用いる．すなわち，slong を PRG に入用いれば，ΠPKE とほとんど同じ安全性を持つことを証明力するシードとし，生成された擬似乱数を鍵生成アルゴリ

PRG
PKE は，する．2 段階目として，ΠPKEより構成された Π

ズムに入力するという方法をとる．

PRG
ΠPKE
と同じ安全性を持つことを証明する．これらの証明

PRG
PKE も，ΠPKE
計算機援用公開鍵暗号 Πと同様に 3 つ Enc,
 Dec)
 からなる．鍵&ヒント生のアルゴリズム (Gen, は，1k と str ∈ {0, 1}ku を入力とし，成アルゴリズム Gen

により，ΠPKE が安全であり，かつ安全な PRG を用いれ
PRG
PRG
ば，ΠPKEは安全であり，そしてその ΠPKE
より構成さ

PKE もまた安全であることが証明できる．ここでれた Π

sshort ∈ {0, 1}ku ，hint ，pk を出力する．暗号化アルゴリズ
 は Enc とまったく同様のアルゴリズムである．復号
ム Enc

PRG
は，もし ΠPKE が最も強い安全性を持っていたら，ΠPKE，

 は sshort ，c，hint を入力として，m を出力
アルゴリズム Dec
 k , str )，する．すべての k ，str ，(sshort , hint, pk ) ← Gen(1 short , Enc(pkm に対して，Dec(s, m), hint) = m が成り立
つ確率は，1 に限りなく近いこと（正当性）が要求される．
PRG
PKE に 対 す る 攻 撃 ゲ ー ム は ，ΠPKE
Πに対する攻撃PRG
まず，ΠPKE より構成された ΠPKE
は，安全な PRG を

PKE も最も強い安全性を持つことを証明する．
Π

用いれば，ΠPKE とほとんど同じ安全性を持つことを証明する．PRG の安全性を示す擬似ランダム性は，次の攻撃ゲームによって定義される．初めに，チャレンジオラクル
が，ランダムにチャレンジビット b を選ぶ．b = 0 の場合

ゲームとほぼ同様に定義できる．異なる部分は，これは，真性乱数 r を生成する．b = 1 の場合は，シード seed

までの CASS に対する攻撃ゲームと同様に，オラクルがを生成し，r = PRG(seed ) を計算する．次に，攻撃者は r

 Enc,
 Dec)
 を実行し，(Gen PRG , Enc, Dec) ではなく，(Gen,
攻撃者が hint を得ることができるという点である．
3.3.2 一般的構成法
PRG
PKE =ΠPKE= (Gen PRG , Enc, Dec) を 用 い て ，Π
 Enc,
 Dec)
 を次のように構成できる．
(Gen, k , str )：k ビットの一様乱数 slong
鍵&ヒント生成 Gen(1を生成する．次に，鍵ペア (pk , sk ) = Gen PRG (1k ; slong ) を生成する．(sshort , hint, pk ) を出力する．ここで，slong =sshort r，|sshort | = |str | = ku ，hint = pk であるため，実際に出力しているのは (sshort , pk ) である．

暗号化 Enc(pk, m)：暗号文 c = Enc(pk , m) を出力する．

復号
Dec(sshort , c, hint)：初めに，k
Gen PRG (1 ; sshort r) = pk を 満 た す r を 総 当 た り で探索し，slong = sshort r を復元する．復元されると同時に
sk も復元される．次に，c を復号し，平文 m = Dec(sk , c)

る．b = b であれば攻撃者の勝ち．攻撃者のアドバンテー
ジは |Pr[b = b ] − 1/2| で定義される．

Theorem 3. ΠPKE が IND-CCA2 安全であり，かつ用
PRG
いる PRG が安全ならば，ΠPKE
もまた IND-CCA2 安全である．より正確には，ΠPKE が IND-CCA2 安全であり，PRG
ΠPKEに対して，無視できないアドバンテージで IND-

CCA2 ゲームに勝利する攻撃者 A が存在するならば，PRGの攻撃ゲームに無視できないアドバンテージで勝利する攻撃者 B が構成できる．

Proof. 仮定より，A を含むあらゆる攻撃者は，ΠPKE のIND-CCA2 ゲームに無視できないアドバンテージで勝利す
PRG
ることはできない．一方，A は ΠPKEの IND-CCA2 ゲー

ムに無視できないアドバンテージで勝利することができる．
すなわち，A が ΠPKE の IND-CCA2 ゲームに勝利する確率は無視できるほど小さい γ によって (1/2 ± γ) で表され，を出力する．

r = r に 対 し て ，Gen PRG (1k ; sshort r) = (pk , sk )，kを与えられる．最後に，攻撃者は推測ビット b を出力す



Gen PRG (1 ; sshort r) = (pk , sk ) であった場合，鍵&ヒ

ント生成において用いられた r とは異なる r が復元され，


PRG
ΠPKE
の IND-CCA2 ゲームに勝利する確率は無視できないほど大きい ζ によって (1/2 ± ζ) で表される．そして，
PRG
ΠPKE の IND-CCA2 ゲームと ΠPKEの IND-CCA2 ゲー

sk = sk である可能性がある．しかし，ΠPKE の正当性か

ムの違いは，鍵生成に一様乱数を用いているか，PRG の出ら，sk  は sk とまったく同じように秘密鍵として利用でき力する擬似乱数を用いているかのみである．そこで，B は，

PKE も正当性を持つ．
るため，Π
なお，RSA-OAEP のようにランダムオラクルを仮定している場合は，hint を slong のハッシュ値 h(slong ) とA の 2 つのゲームに対する勝ち負けの結果を利用すること
により，PRG の攻撃ゲームにアドバンテージ (ζ − γ)/2 で勝利することができる．

することで，上述の構成法よりも正規ユーザの計算コス

具体的には次のような手順となる．初めに，PRG に対すトの負担を減らすことができる．この場合，復号では，る攻撃ゲームのチャレンジオラクルが，ランダムにチャレh(slong ) = h(sshort r) を満たす r を総当たりで探索し，r

ンジビット b を選ぶ．b = 0 の場合は，一様乱数 r を生成すを復元する．あるいは，秘密情報拡張型の CASS を用いる

る．b = 1 の場合は，シード seed を生成し，r = PRG(seed )こともできる．

を計算する．次に，B は r を与えられる．B は与えられた

3.3.3 安全性証明
PKE が ΠPKE とほぼ同じ安全性を持つこと
ここでは，Π

r を用いて，Gen を実行し，(sk , pk ) を得る．次に，B は

c 2018 Information Processing Society of Japan(sk , pk ) を用いて，A との間で IND-CCA2 ゲームをシミュ
1563

情報処理学会論文誌

Vol.59 No.9 1557–1569 (Sep. 2018)

レートする．A がその IND-CCA2 ゲームに敗北した場合


1/2 ± ε で b = b を満たす．すなわち，B は確率 1/2 ± ε では，B は r が一様乱数だと判断し，推測ビット b = 0 を出

PRG
ΠPKE
に対する IND-CCA2 ゲームに勝利するため，アド力する．一方，A がその IND-CCA2 ゲームに勝利した場

バンテージは ε となる．



合は，B は r が擬似乱数だと判断し，b = 1 を出力する．


Q.E.D.

b = 0 の場合に，B が b = 0 を出力する確率は，A がPRG同様にして，ΠPKE
が「非適応的選択暗号文攻撃，もしΠPKE の IND-CCA2 ゲームに敗北する確率 1 − (1/2 ± γ)

くは，選択平文攻撃」に対する「識別不可能性，もしくは，である．b = 1 の場合に，B が b = 1 を出力する確率は，A

PKE も同じ安全性を持つこと
一方向性」を持つならば，Π

PRGが ΠPKEの IND-CCA2 ゲームに勝利する確率 1/2 ± ζ でが証明できる．

ある．よって，B は確率 (1 ± γ ± ζ)/2 で PRG の攻撃ゲー
ムに勝利するため，アドバンテージは (ζ − γ)/2 となる．

Q.E.D.

3.4 計算機援用デジタル署名
3.4.1 モデル同様にして，ΠPKE が「非適応的選択暗号文攻撃，もし通 常 の デ ジ タ ル 署 名 ΠDS は 3 つ の ア ル ゴ リ ズ ム

くは，選択平文攻撃」に対する「識別不可能性，もしくは，(Gen, Sig, Ver ) からなる．鍵生成アルゴリズム Gen はPRG
一方向性」を持ち，かつ PRG が安全ならば，ΠPKE
も同

1k （k はセキュリティパラメータ）を入力とし，秘密鍵

じ安全性を持つことが証明できる．
PRG
PRG
PKE は，ΠPKE
次に，ΠPKEより構成された Πと同じ安全性を持つことを証明する．
PRG
PKE
Theorem 4. ΠPKE
が IND-CCA2 安全ならば，ΠPKE にもまた IND-CCA2 安全である．より正確には，Π

sk ，公開鍵 pk を出力する確率的アルゴリズムである．公
開鍵暗号と同様に，Gen が用いる乱数 r を kl (k) ビットとし，乱数を明示する場合は，Gen(1k ; r) と書くことにす
る．署名アルゴリズム Sig は sk とメッセージ m を入力とし，署名 σ を出力する．検証アルゴリズム Ver は pk ，対して，暗号化クエリを合計 q 回行い，無視できないアドm，σ を入力とし，検証結果 b を出力し，b = 1 なら正当

バンテージで IND-CCA2 ゲームに勝利する攻撃者 A が存な署名として受理し，b = 0 なら不正な署名として拒否

PRG
在するならば，ΠPKEに対して，暗号化クエリを合計 q 回する．すべての k ，(sk , pk ) ← Gen(1k ; r)，m に対して，

行い，無視できないアドバンテージで IND-CCA2 ゲーム

Ver (pk , m, Sig(sk , m)) = 1 であること（正当性）が要求さに勝利する攻撃者 B が存在する．

れる．

PKE の構成では，hint = pk であるた
Proof. 我々の Π
PRGめ，Theorem 1，2 の証明とは異なり，ΠPKE
に対するPKE に対する IND-CCA2 ゲーム
IND-CCA2 ゲームと，Π

で最も強い安全性は，適応的選択メッセージ攻撃に対するは，攻撃の際に入手できる情報はまったく同じである．その攻撃ゲームは，MAC における EUF-CMA ゲームとほぼのため，初めに，B は公開鍵かつ hint である pk を与えら同様に定義できる．異なる部分は，初めに，Gen(1k ; r) よ

れたら，それを A に入力し，あとは B は A からのクエリ

り，(sk , pk ) が生成され，pk が攻撃者に与えられるというをそのままオラクルに送り，オラクルからの返答をそのま点である．

ΠDS の安全性モデルは，様々な定義が存在する．その中存在的偽造不可能性（EUF-CMA）[13] である．EUF-CMA

PKE にま A に返してやるだけでよい．ここで，A は，Π
対する IND-CCA2 ゲームに無視できないアドバンテージ
ε で勝利する（A の勝利確率は 1/2 ± ε）．

場 合 に は ，一 般 に PRG を 用 い た 以 下 の よ う な デ ジ

具体的には次のような手順となる．初めに，一様乱

ア ル ゴ リ ズ ム (Gen PRG , Sig, Ver ) か ら な る ．鍵 生 成 ア

数 seed が 生 成 さ れ ，seed を 用 い て 鍵 ペ ア (pk , sk ) ←ル ゴ リ ズ ム Gen PRG は ，1k を 入 力 と し ，(sk , pk ) =Gen PRG (1k ; seed ) が生成される．次に，B に pk が入力

Gen(1k ; PRG(seed )) を出力する．ただし，seed は Gen PRG

される．B は，pk を A に入力する．この時点で B は A をが用いる k ビットの一様乱数である．ΠDS と同様に正当起動する．A は，B に ci を適応的に送ってくる．B は，ci がPRG性が要求される．ΠDSに対する攻撃ゲームは，初めに

公 開 鍵 暗 号 と 同 様 に し て ，実 際 に ΠDS を 運 用 す る
PRG
PRG
タ ル 署 名 ΠDSが 利 用 さ れ て い る ．ΠDS
は 3 つの送られてきたら，復号オラクルに ci を送り，mi = Dec(sk , ci )Gen PRG より (sk , pk ) が生成されること以外は，ΠDS に対を得て，A に mi を返す．A が，(m∗0 , m∗1 ) を B に送ってきする攻撃ゲームとまったく同様である．

たら，B はチャレンジオラクルに (m∗0 , m∗1 ) を送る．チャ
レンジオラクルはランダムにチャレンジビット b を選び，

公開鍵暗号と同様にして，計算機援用デジタル署名に

DSおいても，PRG を用いる．計算機援用デジタル署名 Πc∗b = Enc(pk , m∗b ) を計算し，B にそれを返す．B は，A に

PRG
 Sig,
 Ver
)
も，ΠDS
と同様に 3 つのアルゴリズム (Gen,は b を出力する．

str ∈ {0, 1}ku を入力とし，sshort ∈ {0, 1}ku ，hint ，pk
 は sshort ，m，hint をを出力する．署名アルゴリズム Sigc∗b を返す．最後に，A は推測ビット b を出力するので，BPKE に対する IND-CCA2 ゲーム
上記の A の環境は，Π

と同じである．したがって，A の出力は少なくとも確率c 2018 Information Processing Society of Japan は，1k とからなる．鍵&ヒント生成アルゴリズム Gen

 は入力として，σ を出力する．検証アルゴリズム Ver
1564

情報処理学会論文誌

Vol.59 No.9 1557–1569 (Sep. 2018)

Ver とまったく同様のアルゴリズムである．すべての k , str )，m に対して，
k ，str ，(sshort , hint, pk ) ← Gen(1同様にして，ΠDS が「非適応的選択メッセージ攻撃，もしくは，既知メッセージ攻撃，鍵単独攻撃」に対する「存 (pk , m, Sig(s short , m, hint)) = 1 が成り立つ確率は 1 にVer

在的偽造不可能性，もしくは，選択的偽造不可能性，一般

限りなく近いこと（正当性）が要求される．

PRG
的偽造不可能性」を持ち，かつ PRG が安全ならば，ΠDS

PRG
DS に対する攻撃ゲームは，ΠDSΠに対する攻撃ゲームとほぼ同様に定義できる．異なる部分は，これまでの CASS に対する攻撃ゲームと同様に，オラクルが (Gen PRG , Sig, Ver ) Sig,
 Ver ) を実行し，攻撃者が hint を得る
ではなく，(Gen,も同じ安全性を持つことが証明できる．
PRG
DS も
Theorem 6. ΠDSが EUF-CMA 安全ならば，Π
また EUF-CMA 安全である．より正確には，ΠDS に対して，署名生成クエリを合計 q 回行い，無視できない確率でことができるという点である．

EUF-CMA ゲームに勝利する攻撃者 A が存在するならば，

3.4.2 一般的構成法

PRGΠDSに対して，署名生成クエリを合計 q 回行い，無視でPRG
DS = (Gen,ΠDS= (Gen PRG , Sig, Ver ) を用いて，Π Ver ) を次のように構成できる．
Sig,

在する．

 k , str )：k ビットの一様乱数 slong
鍵&ヒント生成 Gen(1Proof. 証明のスケッチは Theorem 4 の証明と同様であkを生成する．次に，鍵ペア (pk , sk ) = Gen PRG (1 ; slong ) をきない確率で EUF-CMA ゲームに勝利する攻撃者 B が存る．異なる部分は，Thereom 4 の証明における IND-CCA2生成する．(sshort , hint, pk ) を出力する．ここで，slong =DSが，EUF-CMA に置き換わる点である．ここで，A は，Π

sshort r，|sshort | = |str | = ku ，hint = pk であるため，実に対する EUF-CMA ゲームに無視できない確率 ε で勝利

際に出力しているのは (sshort , pk ) である．

 (sshort , m, hint)：初
署
名
Sig
め
に
，
k
Gen PRG (1 ; sshort r) = pk を満たす r を総当たりで探索し，slong = sshort r を復元する．復元されると同時に sk も復元される．次に，m の署名を生成し，署名 σ = Sig(sk , m)

DSする．B によってシミュレートされた A の環境は，Π

に対する EUF-CMA ゲームと同じである．すなわち，BPRGは確率 ε で ΠDSの EUF-CMA ゲームに勝利する．

Q.E.D.
PRG
同様にして，ΠDSが「非適応的選択メッセージ攻撃，を出力する．

もしくは，既知メッセージ攻撃，鍵単独攻撃」に対する「存 (pk , m, σ)：pk を用いて m と σ に対して検証を検証 Ver

在的偽造不可能性，もしくは，選択的偽造不可能性，一般行い，検証結果 b = Ver (pk , m, σ) を出力する．
kr = r に 対 し て ，Gen PRG (1 ; sshort r) = (pk , sk )，kDS も同じ安全性を持つ的偽造不可能性」を持つならば，Π
ことが証明できる．



Gen PRG (1 ; sshort r ) = (pk , sk ) であった場合，鍵&ヒント生成において用いられた r とは異なる r が復元され，


sk = sk である可能性がある．しかし，ΠDS の正当性から，sk は sk とまったく同じように秘密鍵として利用でき

3.5 計算機援用 C ＆ R 型ユーザ認証
3.5.1 モデル
通常の C&R 型ユーザ認証 ΠCRUA は 5 つのアルゴリズ

DS も正当性を持つ．
るため，Π
PRG
なお，ΠDSはランダムオラクルを仮定している方式が多いため，通常は hint を h(slong ) とすればよい．しかし，ルゴリズム Gen は 1k （k はセキュリティパラメータ）をランダムオラクルを仮定していない場合は，上述の構成法

れを秘密情報として出力する．登録アルゴリズム Enr はをとればよい．

slong を入力とし，検証情報 VI を出力する．チャレンジ生

3.4.3 安全性証明
PKE と同様に，Π
DS の安全性証明においても 2 段階Π成アルゴリズム CG は 1k を入力とし，チャレンジ C を出力する．レスポンス生成アルゴリズム C 2R は slong と Cの証明を行う．ここでは，もし ΠDS が最も強い安全性をを入力とし，レスポンス R を出力する．検証アルゴリズム

PRG
DS もまた最も強い安全性を持つ持っていたら，ΠDS，Π

ム (Gen, Enr , CG, C 2R, Ver ) からなる．秘密情報生成ア
入力とし，一様ランダムに k ビット列 slong を生成し，そVer は C ，R，VI を入力とし，検証結果 b を出力し，b = 1

ことを証明する．

なら認証に成功したものとし，b = 0 なら失敗したものとTheorem 5. ΠDS が EUF-CMA 安全であり，かつ用いする．すべての k ，slong ← Gen(1k )，C ← CG(1k ) に対PRG
る PRG が安全ならば，ΠDS
もまた EUF-CMA 安全であして，Ver (C, C 2R(slong , C), Enr (slong )) = 1 であること

PRG
る．より正確には，ΠDS が EUF-CMA 安全であり，ΠDS（正当性）が要求される．

に対して，無視できない確率で EUF-CMA ゲームに勝利

ΠCRUA の安全性モデルは，様々な定義が存在する．そする攻撃者 A が存在するならば，PRG の攻撃ゲームに無の中で最も強い安全性は，concurrent man-in-the-middle

視できない確率で勝利する攻撃者 B が構成できる．

attack によるなりすまし（IMP-CMIM）[16], [20] に対す

Proof. Theorem 3 の証明における IND-CCA2 を EUF-

る安全性である．その攻撃ゲームでは，初めに，Gen(1k )より，slong が生成される．次に，Enr (slong ) より VI が生

CMA に変えれば証明できるため，省略する．
Q.E.D.

c 2018 Information Processing Society of Japan

成され，VI が攻撃者に送られる．攻撃者は，サーバオラ

1565

情報処理学会論文誌

Vol.59 No.9 1557–1569 (Sep. 2018)

クル，複数の正規ユーザオラクル Pj に対して，適応的にEnr (sshort r)) = 1 をすべて満たす r を総当たりで探索

クエリを送ることができる*2 ．複数の正規ユーザオラクル

し，slong = sshort r を復元する．次に，slong と C を用い

Pj は，同じ slong を持っているが，初めにセットされるラてレスポンス R = C 2R(slong , C) を生成し，出力する．

ンダムテープが異なる．攻撃者が C j を正規ユーザオラ

 (C, R, VI )：Ver に C ，R，VI を入力し，検証
検証 Verクル Pj に送ったら，Pj は，R j = C 2R(slong , C  j ) を返

結果 b を生成し，出力する．

し，内部状態を「認証終了」に更新し，以後はクエリを受∗

N の 決 定 に つ い て は ，共 通 鍵 暗 号 ，MAC の 場 合 とけ付けない．サーバオラクルは，C を攻撃者に送る．な同様に，Ver (Ci , Ri , Enr (sshort r )) = 1 がすべての i ∈お，攻撃者が C ∗ をクエリとして，Pj に送ることは禁止さ{0, . . . , N − 1} について成り立つような r（= r）が存在す

れる．最後に，攻撃者は，C ∗ に対応する R∗ を出力する．

る確率 δ(N ) が無視できるほど小さくなるように選ぶ．こ∗∗Ver (C , R , VI ) = 1 であれば攻撃者の勝ち．
CRUA も，ΠCRUA と同様計算機援用 C&R 型ユーザ認証 Π Enr , CG, C ) からなに，5 つのアルゴリズム (Gen,2R, Ver は 1k と str ∈る．秘密情報&ヒント生成アルゴリズム Gen{0, 1}ku を入力とし，slong ∈ {0, 1}k ，sshort ∈ {0, 1}ku ，hint は Enr と，チャレンを出力する．登録アルゴリズム Enr
 は CG とまったく同様のアルゴリ
ジ生成アルゴリズム CG
ズムである．レスポンス生成アルゴリズム C
2R は sshort ，C ，hint を入力とし，R を出力する．検証アルゴリズム Ver
は Ver とまったく同様のアルゴリズムである．すべての k , str )，C ← CG(1 k)k ，str ，(slong , sshort , hint) ← Gen(1 (C, C (slong )) = 1 がに対して，Ver
2R(sshort , C, hint), Enr
成り立つ確率は 1 に限りなく近いこと（正当性）が要求さのとき，r は圧倒的確率で正しく復元されるため，正当性が成り立つ．
具体的な N の値は ΠCRUA に依存する．典型的な ΠCRUAのアルゴリズムとして，ハッシュ関数 h を用いたアルゴ リ ズ ム が あ げ ら れ る ．具 体 的 に は ，VI = h(slong )，R = h(h(slong ), C) であり，Ver ではレスポンスを再計算して，受け取ったレスポンスと等しいかを確認するというアルゴリズムである．このアルゴリズムの場合は N = 1
で十分である．なぜならば，δ(1) が有意に高ければ，それは用いているハッシュ関数の衝突困難性を破っていることになる．すなわち，用いているハッシュ関数が衝突困難性を有していれば，δ(1) は無視できるほど小さい値となる．
なお，δ(N ) を無視できるほど小さくすることが困難である場合は，我々の構成によって計算機援用 C&R 型ユーザ

れる．

CRUA に 対 す る 攻 撃 ゲ ー ム は ，ΠCRUA に 対 す るΠ
攻 撃 ゲ ー ム と ほ ぼ 同 様 に 定 義 で き る ．異 な る 部 分
は ，こ れ ま で の CASS に 対 す る 攻 撃 ゲ ー ム と 同 様に ，オ ラ ク ル が (Gen, Enr , CG, C 2R, Ver ) で は な く ， Enr
 , CG, C ) を実行し，攻撃者が hint を得(Gen,
2R, Ver

認証は構成できない．

3.5.3 安全性証明
CRUA は，上記の構成法を用いて ΠCRUA から構成さ
ΠCRUA は，ΠCRUA とほとれたと仮定する．そのような Π
んど同じ安全性を持つことを証明する．ここでは，もしることができるという点である．

CRUA も最も
ΠCRUA が最も強い安全性を持っていたら，Π

3.5.2 一般的構成法

強い安全性を持つことを証明する．

ΠCRUA= (Gen, Enr , CG, C 2R, Ver ) を 用 い て ， Enr , CG, C ) を次のように構成
ΠCRUA = (Gen,2R, Verできる．

 k , str )：1k を入力とし，秘秘密情報&ヒント生成 Gen(1kkTheorem 7. ΠCRUA が IMP-CMIM に対して安全なら
CRUA もまた IMP-CMIM に対して安全である．よば，ΠCRUA に対して，正規ユーザオラクルへのり正確には，Π

クエリを合計 q 回行い，無視できない確率で IMP-CMIM

密情報 slong = Gen(1 ) を生成する．次に，CG に 1 をゲームに勝利する攻撃者 A が存在するならば，ΠCRUA に入力し，N 個のチャレンジ C0 , . . . , CN −1 を生成し，それ対して，正規ユーザオラクルへのクエリを合計 q + N 回行に対応するレスポンス R0 = C 2R(slong , C0 ), . . . , RN −1 =い，無視できない確率で IMP-CMIM ゲームに勝利する攻C 2R(slong , CN −1 ) を生成する．(slong , sshort , hint) を出力

撃者 B が存在する．

する．ここで，slong = sshort r，|sshort | = |str | = ku ，Proof. 証明のスケッチは，Theorem 1，2 の証明と同様

hint = ((C0 , R0 ), . . . , (CN −1 , RN −1 )) である．

である．しかし，Theorem1，2 の IND-P2-C2，EUF-CMA

 (slong )：Enr に slong を入力し，検証情報 VI を
登録 Enr
生成し，出力する．

 k )：CG に 1k を入力し，チャレンチャレンジ生成 CG(1ジ C を生成し，出力する．
レ ス ポ ン ス 生 成 C2R(sshort , C, hint)：初 め に ，Ver (C0 , R0 , Enr (sshort r)) = 1, . . . , Ver (CN −1 , RN −1 ,*2

ここでは，ユーザ側のみを concurrent とする left-concurrencyを考える．

c 2018 Information Processing Society of Japan

をそのまま IMP-CMIM に置き換えればよいというわけで

CRUA に対する IMP-CMIM ゲー
はない．ここで，A は，Π
ムに無視できない確率 ε で勝利するものとする．
具 体 的 に は 次 の よ う な 手 順 と な る ．以 下 で は ，A
は 正 規 ユ ー ザ オ ラ ク ル と し て P0 , . . . , Pq−1 を 持 ち ，

B は P0 , . . . , Pq−1+N を 持 つ も の と す る ．ま ず B は ，Enr (Gen(1k )) により生成された検証情報 VI を受け取る ．B は ，A に hint で あ る チ ャ レ ン ジ と レ ス ポ ン ス

1566

情報処理学会論文誌

Vol.59 No.9 1557–1569 (Sep. 2018)の N ペ ア を 入 力 す る た め に ，CG(1k )よ り チ ャ レ ン ジ

時代が変わろうとも，パスワードを用いた秘密情報補完型

C0 , . . . , CN −1 を 生 成し，C0 , . . . , CN −1 を正規ユーザオ

CASS は実現可能であるといえる．

ラクル Pq , . . . , Pq−1+N に送る．Pq , . . . , Pq−1+N は，R0 =次に，sshort が生体情報の場合について議論する．生体

C 2R(slong , C0 ), . . . , RN −1 = C 2R(slong , CN −1 ) を B に返情報のエントロピーについては，その評価尺度の定義や評すので，B は ((C0 , R0 ), . . . , (CN −1 , RN −1 )) を hint とし価方法に関して，様々な提案がなされている．たとえば，て，VI とともに，A に入力する．この時点で B は A を起

文献 [17] では，ある生体認証システム S を通じて観測でき動する．A は，B に Ci を正規ユーザオラクル Pj に対するる生体情報のエントロピーを，S における本人同士の照合クエリとして，適応的に送ってくる．B は自身のオラクル

スコアの確率分布 fG (x) と，他人同士の照合スコアの確率

Pj にそのままクエリを送り，オラクルからの返答を A に

分布 fI (x) の間の Kullback-Leibler 距離 [18] D(fG fI ) に∗k

返す．サーバオラクルが C = CG(1 ) を，B に送ってき∗∗たら，B は，A に C を送る．最後に，A は R を出力す∗るので，B は R を出力する．

よって評価することを提案している．S の出力が OK（一致）/NG（不一致）の 2 値であった場合は，本人なのに不一致となる確率 β と，他人なのに一致となる確率 α を用

確率 1 − δ(N ) で，r = r となるすべての r に対して，

Ver (C0 , R0 , Enr (Sshort r )) = 1, . . . , Ver (CN −1 , RN −1 ,βいて，D(fG fI ) = (1 − β) log2 1−β
α + β log2 1−α と表現でき，β1 の場合は近似的に D(fG fI ) = − log2 α と表す

Enr (sshort r )) = 1 の少なくとも 1 つが成り立ち，このとCRUA
き，B によってシミュレートされた A の環境は，Π

ことができる．そして，文献 [19] で提案されている指静脈に対する IMP-CMIM ゲームと同じとなり，B は ΠCRUA

情報を入力するたびにそれまで得られたスコアを融合してに対する IMP-CMIM ゲームに確率 ε で勝利することがでユーザを判定する「逐次融合判定」を組み込むことにより，きる．したがって，B は確率 (1 − δ(N ))ε > ε − δ(N ) で

α = 2−64 ，2−80 ，2−128 とすることができ，エントロピー

ΠCRUA の IMP-CMIM ゲームに勝利する．

としては，D(fG fI ) = 64，もしくは，80，128 ビットまを用いたバイオメトリック暗号においては，ユーザが生体同様にして，πCRUA が「man-in-the-middle attack，con-で実現できることを実験的に示している．ただし，α の値

current attack [14]，もしくは，能動的攻撃，受動的攻撃」

を小さくするためには，指の入力回数（使用する指の本数）に対する「なりすまし耐性，パスワード推測耐性」を持つの平均値を増やす必要がある．

CRUA も同じ安全性を持つことが証明できる．
ならば，Π

以上より，生体情報を 102 ビットの一様乱数である sshortとして利用することは可能である．また，生体情報におい

4. CASS の実現可能性ても，将来的に CPU の計算機能力が向上し，安全となる

秘密情報補完型 CASS においては，その時代で安全と

slong の長さが大きくなった場合でも，r の長さを大きくなる長さに slong を設定し，それに合わせて正規ユーザはすることにより，指の入力回数の平均値を増やすことなく

sshort と r の長さを調節する．将来的に CPU の計算機能（sshort を大きくすることなく），r の復元に要する時間が力が向上し，安全となる slong の長さが大きくなった場合

1 秒のまま，slong の長さを大きくすることが可能となる．

でも，正規ユーザも計算機能力を使用するため，r の長さ

よって，時代が変わろうとも生体情報を用いた秘密情報補を調節することにより，sshort の長さを変えずに，r の復元

完型 CASS は実現可能であるといえる．

に要する時間を増加させずに，slong の長さを大きくするこ

本章のこれまでの議論は，正規ユーザが，攻撃者と同じとが可能である．本章では，sshort がパスワード，または性能を持つ計算機を利用できると仮定している．しかし，生体情報である場合を例に，秘密情報補完型 CASS の実現

現実的には，正規ユーザはスマートフォン等の計算能力の可能性について議論する．

小さな端末を利用することが期待されるのに対し，攻撃

初めに，sshort がパスワードの場合について議論する．

者はハイスペックな計算機を用意したり，クラウドコン

現在は 128 ビット鍵が主流であり，現在のコンピュータ

ピューティングサービスを利用したりするであろう．そのでは短時間（たとえば 1 秒）で 2

26程度の処理が可能なた

ような場合は，単純に「時代が変わろうとも，秘密情報補

め r を 26 ビットとすると，sshort は 102 ビットとなる．文

完型 CASS は実現可能である」ということにはならない．

献 [15] で，人間は 102 ビットのパスワードを記憶できるこ

しかし，パスワードや，生体認証，PUF 等の秘密情報のエとが示されている．将来，計算機能力が 264倍に増えたとントロピーを増やすことが困難であるあらゆる情報に対しきには，192 ビット鍵へと移行する必要ある．sshort の長て，計算機能力を使って安全性を高めることが可能である

さは人間の記憶可能な 102 ビットのまま slong = sshort rということはいえる．

の長さを 128 ビットから 192 ビットにするためには，r の長さを 26 ビットから 90 ビットへと変更する必要がある
が，計算機の能力が 264倍となっているため，r の復元に要する時間は 1 秒程度の短時間に保たれる．したがって，

c 2018 Information Processing Society of Japan


参考文献
[1]

Gassend, B., Clarke, D., Dijk, M. and Devadas, S.: Silicon physical random functions, 9th ACM Conference1567情報処理学会論文誌

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

Vol.59 No.9 1557–1569 (Sep. 2018)

on Computer and Communications Security, pp.148–
160 (2002).
Juels, A. and Wattenberg, M.: A fuzzy commitment
scheme, 6th ACM Conference on Computer and Communications Security, pp.28–36 (1999).
Proves, N. and Mazieres, D.: A Future-Adaptable Password Scheme, USENIX Annual Technical Conference(1999).
Turan, M.S., Barker, E., Burr, W. and Chen, L.: Recommendation for Password-Based Key Derivation Part
1: Storage Applications, NIST Special Publication, 800132 (2010).
Kelsey, J., Schneier, B., Hall, C. and Wagner, D.: Secure Applications of Low-Entropy Keys, 1997 Information Security Workshop, pp.121–134 (1997).
Yao, F.F. and Yin, Y.L.: Design and Analysis ofPassword-Based Key Derivation Functions, IEEE Trans.
Information Theory, Vol.51, No.9, pp.3292–3297 (2005).
兼子拓弥，本部栄成，高橋健太，西垣正勝：計算機援用ユー
ザ認証，情報処理学会論文誌，Vol.55, No.9, pp.2072–2080(2014).
Barker, E. and Roginsky, A.: Transitions: Recommendation for Transitioning the Use of Cryptographic Algorithms and Key Lengths, NIST Special Publication,
800-131A Revision 1 (2015).
Katz, J. and Yung, M.: Characterization of Security Notions for Probabilistic Private-Key Encryption, Journalof Cryptology, Vol.19, No.1, pp.67–95 (2006).
Rackoﬀ, C. and Simon, D.R.: Non-interactive zeroknowledge proof of knowledge and chosen ciphertext attack, Proc. Advances in Cryptology – CRYPTO 91,
Vol.576, pp.433–444 (1991).
Rivest, R.L., Shamir, A. and Adleman, L.: A Method for
Obtaining Digital Signatures and Public-Key Cryptosystems, Comm. ACM, Vol.21, No.2, pp.120–126 (1978).
Yao, A.C.: Theory and Applications of Trapdoor Functions, 23rd Annual Symposium on Foundations of Computer Science, pp.80–91 (1982).
Goldwasser, S., Micali, S. and Rivest, R.L.: A digital signature scheme secure against adaptive chosen-message
attacks, SIAM Journal on Computing, Vol.17, No.2,
pp.281–308 (1988).
Bellare, M. and Palacio, A.: GQ and Schnorr Identiﬁcation Schemes, Proofs of Security against Impersonation under Active and Concurrent Attacks, Advancesin Cryptology – CRYPTO 2002, pp.162–177 (2002).
Fujita, M., Yamada, M., Arimura, S., Ikeya, Y. andNishigaki, M.: An Attempt to Memorize Strong Passwords while Playing Games, Network-Based Information Systems, pp.264–268 (2015).
Gennaro, R.: Multi-trapdoor Commitments and Their
Applications to Proofs of Knowledge Secure Under Concurrent Man-in-the-Middle Attacks, Advances in Cryptology – CRYPTO 2004, pp.220–236 (2004).
Takahashi, K. and Murakami, T.: A Measure of Information Gained through Biometric Systems, Elsevier Image and Vision Computing, Vol.32, No.12, pp.1194–1203(2014).
Kullback, S. and Leibler, R.A.: On Information andSuﬃciency, The Annuals of Mathematical Statistics,
Vol.22, No.1, pp.79–86 (1951).
Murakami, T., Ohki, T. and Takahashi, K.: Optimal sequential fusion for multibiometric cryptosystems, Vol.32,
pp.93–108 (2016).
Anada, H. and Arita, S.: Identiﬁcation Schemes ofc 2018 Information Processing Society of Japan

Proofs of Ability Secure against Concurrent Man-in-theMiddle Attacks, International Conference on Provable
Security, ProveSec 2010, pp.18–34 (2010).

神農 泰圭
2016 年静岡大学情報学部情報科学科卒業．2018 年同大学院修士課程修了．
在学中，情報セキュリティに関する研
究に従事．

土屋 貴史
2015 年静岡大学情報学部情報科学科卒業．2017 年同大学院修士課程修了．
在学中，情報セキュリティに関する研究に従事．

大木 哲史 （正会員）2010 年早稲田大学理工学総合研究所
次席研究員，2013 年産業技術総合研
究所特別研究員を経て，2017 年より静岡大学大学院総合科学技術研究科講師．個人認証を中心としたネットワー
クセキュリティに関する研究に従事．

高橋 健太 （正会員）
1998 年東京大学理学部情報科学科卒
業．2000 年同大学院理学系研究科情報科学専攻修士課程修了．同年（株）
日立製作所入社．2012 年東京大学大学院情報理工学系研究科博士後期課程修了．博士（情報理工学）．2015 年より東京大学大学院客員准教授．現在，（株）日立製作所研究開発グループユニットリーダ主任研究員．生体認証，暗号技術および情報セキュリティの研究開発に従事．2008 年
情報処理学会論文賞，2011 年 SISAP Best paper，2012 年

IEEE BTAS Best reviewed paper，2015 年情報処理学会
長尾真記念特別賞，2016 年ドコモ・モバイル・サイエンス
賞先端技術部門優秀賞，関東地方発明表彰発明奨励賞等受
賞．電子情報通信学会会員．

1568

情報処理学会論文誌

Vol.59 No.9 1557–1569 (Sep. 2018)

尾形 わかは1989 年東京工業大学理学部物理学科卒
業，1991 年同大学院総合理工学研究科
物理情報工学専攻修士課程修了，1994
年同大学院理工学研究科電気・電子工学専攻博士後期課程修了．1995 年兵庫県立姫路工業大学工学部情報工学科
助手．2000 年東京工業大学理財工学研究センター助教授，

2013 年同大学大学院イノベーションマネジメント研究科
技術経営専攻教授．2015 年より同大学工学院情報通信系
教授．博士（工学）．公開鍵システム，マルチパーティプロ
トコルをはじめとする暗号理論全般の研究に従事．

西垣 正勝 （正会員）
1990 年静岡大学工学部光電機械工学科卒業．1992 年同大学院修士課程修了．1995 年同博士課程修了．日本学術振興会特別研究員（PD）を経て，1996 年静岡大学情報学部助手．同講師，助教授の後，2006 年より同創造科
学技術大学院助教授．2007 年同准教授，2010 年同教授．博士（工学）．情報セキュリティ全般，特にヒューマニクスセ
キュリティ，メディアセキュリティ，ネットワークセキュ
リティ等に関する研究に従事．2013〜014 年情報処理学会
コンピュータセキュリティ研究会主査．2015〜2016 年電子情報通信学会バイオメトリクス研究専門委員会委員長．

2016 年より日本セキュリティマネジメント学会常任理事．
本会フェロー．

c 2018 Information Processing Society of Japan

1569