(57)【要約】【課題】  鍵管理が容易で、鍵の信頼性を高くするのに適した復号方法を提供する。【解決手段】  復号システム１は、暗号文ｅから全文復号文ｍとその一部である部分復号文ｍ'を得るものである。有限群Ｇ及びＨ、群の準同型φ：Ｇ→Ｈ、並びに、前記有限群Ｇ及びＨにそれぞれ対応する暗号方式ＳG及びＳHの写像φZ：ＳG→ＳHを用いる。暗号装置は、完全公開鍵ｈを用いて平文を暗号化することにより全文暗号文ｅを得る。全文復号装置は、全文暗号文ｅを秘密鍵ｆを用いて復号することにより、全文復号文ｍを得る全文復号手段を備える。部分復号装置は、全文暗号文ｅに対して、部分暗号文ｅ'＝φZ（ｅ）を計算し、前記部分暗号文ｅ'を秘密鍵ｆ'＝φZ（ｆ）を用いて復号することにより、部分復号文ｍ'＝φZ（ｍ）を得る部分復号手段を備える。【選択図】  図２
2017038336.tif 000002
【特許請求の範囲】
【請求項１】
暗号文ｅから全文復号文ｍとその一部である部分復号文ｍ'を得る復号システムであって、
有限群Ｇ及びＨ、群の準同型φ：Ｇ→Ｈ、並びに、前記有限群Ｇ及びＨにそれぞれ対応する暗号方式ＳG及びＳHの写像φZ：ＳG→ＳHに対して、
完全公開鍵ｈを用いて平文を暗号化することにより前記全文暗号文ｅを得る暗号装置と、
前記全文暗号文ｅを秘密鍵ｆを用いて復号することにより、前記全文復号文ｍを得る全文復号手段を備える全文復号装置と、
前記全文暗号文ｅに対して、部分暗号文ｅ'＝φZ（ｅ）を計算し、前記部分暗号文ｅ'を秘密鍵ｆ'＝φZ（ｆ）を用いて復号することにより、前記部分復号文ｍ'＝φZ（ｍ）を得る部分復号手段を備える部分復号装置を備える複合システム。
【請求項２】
暗号文ｅから全文復号文ｍの一部である部分復号文ｍ'を得る復号方法であって、
有限群Ｇ及びＨ、群の準同型φ：Ｇ→Ｈ、並びに、前記有限群Ｇ及びＨにそれぞれ対応する暗号方式ＳG及びＳHの写像φZ：ＳG→ＳHに対して、
前記暗号文ｅは、公開鍵ｈを用いて暗号化され、秘密鍵ｆを用いて復号することにより、前記全文復号文ｍを得ることができ、
部分復号手段が、部分暗号文ｅ'＝φZ（ｅ）を計算し、ｅ'を秘密鍵ｆ'＝φZ（ｆ）を用いて復号することにより、前記部分復号文ｍ'＝φZ（ｍ）を得る部分復号ステップを含む復号方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本願発明は、復号方法に関し、特に、暗号文から全文復号文の一部である部分復号文を得る復号方法に関する。
【背景技術】
【０００２】
一つの平文を暗号化して多数の受信者に対して送付する状況において、暗号文の復号部分を受信者に応じて指定可能な公開鍵暗号方式が知られている。
【０００３】
このような部分復号方式を実現する方法として、複数の公開鍵を利用する方法が知られている。復号可能なメッセージの部分情報がｎ通りある場合、暗号送信者はｎ個の公開鍵を使って暗号文を作る。部分復号を行う受信者は、事前に教えられたｎ個未満の秘密鍵を用いて、暗号文の部分情報を手に入れることができる。知っている秘密鍵の個数が多いほど、より完全に近いメッセージを手に入れることができる。
【０００４】
平文分割暗号化は、例えば、想定される複数の受信者に応じて一つの平文を予め分割し、各々の平文の断片を各受信者の公開鍵で暗号化するものである。また、例えば、送信者が秘密鍵と公開鍵のペアを複数生成し、予め分割した平文の各々の断片を各々の公開鍵で暗号化するものもある。平文分割暗号化に工夫を加えたものとして、処理効率を追求したものが知られている（非特許文献１及び２参照）。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】M. Bellare、外３名著， Multirecipient encryption schemes:How to save on bandwidth and computation without sacricing security. IEEE Transactions on Information Theory, 53(11):3927〜3943, 2007.
【非特許文献２】M. Bellare、外２名著，Randomness re-use in multi-recipient encryption schemeas. In Public Key Cryptography - PKC 2003, 6th International Workshop on Theoryand Practice in Public Key Cryptography, Miami, FL, USA, January 6-8, 2003, Proceedings, pages 85〜99, 2003.
【非特許文献３】J. Hoffstein、外２名著，NTRU: A ring-based public key cryptosystem. In Algorithmic Number Theory, Third International Symposium, ANTS-III, Portland, Oregon,USA, June 21-25, 1998, Proceedings, pages 267〜288, 1998.
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、背景技術において、複数の公開鍵の間には互いに依存関係はない。鍵管理において、これらの公開鍵をひもづけておかなければならない。また、鍵の一部を他の公開鍵暗号通信に流用される可能性があり、そこから秘密情報が漏えいする危険性がある。さらに、漏えいした秘密情報をつなぎ合わせて、全ての公開鍵を復元される危険性もある。また、複数の鍵を用いるため、複数回の暗号化アルゴリズム、復号化アルゴリズムを実行しなければならない手間も生じる。
【０００７】
そこで、本願発明は、鍵管理が容易で、鍵の信頼性を高くするのに適した復号方法を提供することを目的とする。
【課題を解決するための手段】
【０００８】
本願発明の第１の観点は、暗号文ｅから全文復号文ｍとその一部である部分復号文ｍ'を得る復号システムであって、有限群Ｇ及びＨ、群の準同型φ：Ｇ→Ｈ、並びに、前記有限群Ｇ及びＨにそれぞれ対応する暗号方式ＳG及びＳHの写像φZ：ＳG→ＳHに対して、完全公開鍵ｈを用いて平文を暗号化することにより前記全文暗号文ｅを得る暗号装置と、前記全文暗号文ｅを秘密鍵ｆを用いて復号することにより、前記全文復号文ｍを得る全文復号手段を備える全文復号装置と、前記全文暗号文ｅに対して、部分暗号文ｅ'＝φZ（ｅ）を計算し、前記部分暗号文ｅ'を秘密鍵ｆ'＝φZ（ｆ）を用いて復号することにより、前記部分復号文ｍ'＝φZ（ｍ）を得る部分復号手段を備える部分復号装置を備えるものである。
【０００９】
本願発明の第２の観点は、暗号文ｅから全文復号文ｍの一部である部分復号文ｍ'を得る復号方法であって、有限群Ｇ及びＨ、群の準同型φ：Ｇ→Ｈ、並びに、前記有限群Ｇ及びＨにそれぞれ対応する暗号方式ＳG及びＳHの写像φZ：ＳG→ＳHに対して、前記暗号文ｅは、公開鍵ｈを用いて暗号化され、秘密鍵ｆを用いて復号することにより、前記全文復号文ｍを得ることができ、復号手段が、部分暗号文ｅ'＝φZ（ｅ）を計算し、ｅ'を秘密鍵ｆ'＝φZ（ｆ）を用いて復号することにより、前記部分復号文ｍ'＝φZ（ｍ）を得る部分復号ステップを含むものである。
【００１０】
なお、本願発明を、各観点の部分復号を実現するための復号装置として捉えてもよい。また、コンピュータにおいて、各観点の復号方法を実現するためのプログラム、及び、そのプログラムを記録するコンピュータ読み取り可能な記録媒体として捉えてもよい。
【発明の効果】
【００１１】
本願発明の各観点では、暗号化のための鍵は、１つの公開鍵のみである。また、完全復号鍵も１つの秘密鍵のみである。背景技術では、暗号化のために複数の公開鍵が必要となり、完全復号鍵は複数の秘密鍵から構成されていた。そのため、本願発明の各観点によれば、暗号化のための鍵も完全復号鍵も一つであり、１回の暗号化・復号処理で済み、さらに、鍵管理が容易になって鍵生成センターの負担を軽減することができる。
【００１２】
さらに、本願発明では、部分復号できる鍵と完全復号できる鍵に互いに強い依存性を持っている。背景技術では、完全鍵の一部を他の暗号にも流用することができるため、完全鍵の信頼性に問題があった。本願発明の各観点によれば、部分復号鍵と完全復号鍵が１対１に対応するため、鍵の信頼性が高くなる。
【図面の簡単な説明】
【００１３】
【図１】本願発明の概要を説明するための図である。
【図２】本願発明の実施の形態に係る復号システムの一例を示すブロック図である。
【図３】図２の（ａ）暗号装置３、（ｂ）全文復号装置５、及び、（ｃ）部分復号装置７の動作の一例を示すフロー図である。
【図４】本願発明の他の実施の形態の一例を示すフロー図である。
【発明を実施するための形態】
【００１４】
以下、本願発明の実施の形態について説明する。なお、本願発明の実施の形態は、下記の実施例に限定されるものではない。
【実施例】
【００１５】
本願発明の概要を説明する。本願発明は、２つの有限群Ｇ、Ｈと、その間の群の準同型φ：Ｇ→Ｈを用いる。発明者らは、任意の有限群Ｇに対し，それに付随する格子ベース暗号方式ＳGを構成する方法を既に提案した（例えば、安田、外２名著，“非可換環を用いたNTRU方式の拡張”，SCIS 2015参照）。このＳGは、いわゆるNTRU方式と呼ばれるものの変形方式となる。実際、Ｇを有限巡回群とすると、オリジナルのNTRU方式と一致する。
【００１６】
図１は、本願発明の概要を説明するための図である。２つの有限群Ｇ、Ｈがあれば、図１（ａ）のように、２つの暗号方式ＳG、ＳHが対応することになる。この対応は、さらに函手性を持つ。群の準同型φ：Ｇ→Ｈがあると、数１のような写像φZが定義できる。ここで、ＳｋG、ＰｋG、ＭG、ＣGは、ＳGのそれぞれ秘密鍵、公開鍵、平文、暗号文である。ＳｋH、ＰｋH、ＭH、ＣHも同様である。特に、ＳGの秘密鍵ＳｋGを知っている人は、φZを通してＳHの秘密鍵ＳｋHを計算することができる。よって、暗号文ＣHから平文ＭHも計算することも可能となる。一方、逆にＳｋHからＳｋGを計算することは困難である（ようにできる）。φZを通して、完全文書Ｍから部分文書Ｍ2を、公開鍵ＰｋGから公開鍵ＰｋHを、秘密鍵ＳｋGから秘密鍵ＳｋHを、完全暗号文Ｃから部分暗号文Ｃ2を、計算することができる。他方、逆に計算することは、困難にすることができる。
【００１７】
この性質を利用すると、ＭHをＭGの部分情報とみなしたとき、部分情報ＭHのみ復号可能な権限と、全体情報ＭGを復号可能な権限という２つの異なる権限を作ることが可能となる。図１（ｂ）を参照して、文書・秘密鍵の対応を説明する。ＳGの文書・秘密鍵５１は、φZを用いることにより、ＳHの文書・秘密鍵５３を得ることができる。図１（ｃ）を参照して、暗号文・公開鍵の対応を説明する。ＳGでは、ＳHの暗号文（公開鍵）の情報を含めたすべての情報で撹拌されている。φZを用いることにより、ＳGの暗号文・公開鍵５５から、ＳHの暗号文・公開鍵５７を得ることができる。
【００１８】
【数１】
2017038336.tif 000003
【００１９】
本願発明は、例えば、会員向けの電子化された論文の販売などへ応用することができる。論文の情報は、公開鍵ＰｋGによって、すべての情報で撹拌されている。会員は、部分鍵ＳｋHをもらえる。会員は、部分鍵ＳｋHを用いて論文の冒頭部分（著者や要約部など）を見ることができ、購入の判断基準とすることができる。会員は、論文を購入したければ、完全鍵ＳｋGを購入することで論文全体（完全版）を手に入れることができる。部分鍵ＳｋHは完全鍵ＳｋGと１対１に対応するので、安全に商品を購入することができる。
【００２０】
以下、提案方式の一般的構成について数学的に説明する。
【００２１】
有限群Ｇを固定する。Ｚ［Ｇ］を、式(1)の集合で定義する。ただし、［ｇ］は、ｇ∈Ｇに付随する形式的な元であり、｛［ｇ］｜ｇ∈Ｇ｝がＺ［Ｇ］の基底となる。Ｚ［Ｇ］上の和と積を次のように定義する。この和と積によりＺ［Ｇ］は環となる。これをＧに対する群環と呼ぶ。
(1)  和は、成分ごとの和により定義する。
(2)  任意のｇ，ｈ∈Ｇに対して、［ｇ］＊［ｈ］＝［ｇｈ］と定義する。これをＺ線形に伸ばして、Ｚ［Ｇ］上の積を定義する。
【００２２】
【数２】
2017038336.tif 000004
【００２３】
例えば、ＣN＝＜σ＞を位数Ｎの巡回群とする。このとき、数３で定まるＺ線形写像は環同型となる。
【００２４】
【数３】
2017038336.tif 000005
【００２５】
まず、群環NTRUについて説明する。有限群Ｇを固定し、Ｎ＝＃Ｇとする。ここで、＃Ｇは、Ｇの要素数である。また、ｐ、ｑをそれぞれ正の整数とする。
【００２６】
Ｒ＝Ｚ［Ｇ］の任意の元ｆは、式(2)と一意的に表すことができる。Ｒの部分集合Ｌf、Ｌξ、Ｌr、Ｌmを定義する。なお、式(3)及び(5)では、右肩にＧを記載している。右肩の記載Ｇは、省略することがある。まず、ＬmGを、式(3)とおく。正整数ｄ、ｄ'に対して、式(4)とする。３つの正整数ｄ1、ｄ2、ｄ3を選び、式(5)とする。
【００２７】
【数４】
2017038336.tif 000006
【００２８】
続いて、鍵生成について説明する。ｆ∈Ｌf、ξ∈Ｌξをランダムに選ぶ。ただし、ｆは、さらに以下を満たさなければならない。もし満たさない場合は、満たすまでｆを選びなおす。失敗する確率はＮ／ｑより小さく、数回の探索で条件を満たすｆを見つけ出すことが可能である。
条件  １＋ｐ・ｆ  mod  ｑ  は可逆である。
【００２９】
このとき、Ｆq∈Ｚ［Ｇ］で式(6)となるものが存在する。このとき、ｈ≡Ｆq・ｐξ mod ｑなるｈ∈Ｚ「Ｇ」を公開鍵とし、ｆを秘密鍵とする。
【００３０】
【数５】
2017038336.tif 000007
【００３１】
続いて、暗号化について説明する。メッセージｍは、ＬmGの元と対応しているものとする。ｍを暗号化するには、まずｒ∈ＬrGをランダムに選ぶ。次にｅ≡ｈ・ｒ＋ｍ  mod  ｑを計算する。ｅが暗号文となる。
【００３２】
続いて、復号化について説明する。ｅを復号するには、ａ≡（１＋ｐ・ｆ）・ｅ  mod  ｑを計算する。このとき、ａの係数を−ｑ／２からｑ／２の間に入るように取ると、これはｍに一致する。
【００３３】
上のように構成された方式をNTRU（Ｇ，ｄ1，ｄ2，ｄ3）と表すことにする。
【００３４】
続いて、群の準同型と群環NTRUの関係について説明する。群の準同型φ：Ｇ→Ｈがあるとする。このとき、群環の間の環準同型が数６のように誘導される。
【００３５】
【数６】
2017038336.tif 000008
【００３６】
今，共通のｐ、ｑで構成された２つの群環NTRU方式ＮＴＲＵ（Ｇ，ｄ1，ｄ2，ｄ3）、ＮＴＲＵ（Ｈ，ｄ'1，ｄ'2，ｄ'3）が与えられているとする。ＮＴＲＵ（Ｇ，ｄ1，ｄ2，ｄ3）の公開鍵をｈ、秘密鍵をｆ、平文をｍ、暗号文をｅとする。これらはいずれもＺ［Ｇ］の元であることに注意する。Ｚ［Ｈ］の元ｈ'、ｆ'、ｍ'、ｅ'を数７のように定義する。
【００３７】
【数７】
2017038336.tif 000009
【００３８】
もし、ｆ'、ｍ'がそれぞれＮＴＲＵ（Ｈ，ｄ'1，ｄ'2，ｄ'3）における秘密鍵と平文の条件を満たすならば、ｆ'を秘密鍵とするとｈ'は公開鍵となり、ｍ'を平文とするとｅ'は暗号文となることがφZの環準同型性から分かる。
【００３９】
続いて、群環NTRUと群の準同型を応用して、部分復号方式を構成する方法を説明する。ここでいう部分復号方式とは、以下のような要請を満たす暗号方式のことである。
(1)平文Ｍとその部分平文Ｍ'（⊂Ｍ）があり、Ｍが暗号文Ｃに暗号化されているとする。
(2)このとき、アリスは、暗号文Ｃから平文Ｍを復号する権限を持つ。
(3)一方、ボブは、暗号文Ｃから部分平文Ｍ'のみを復号する権限を持つ。
【００４０】
以下、提案する部分復号方式を、鍵生成、アリスの暗号化・復号化、ボブの復号化の順に説明する。
【００４１】
まず、鍵生成について説明する。有限群Ｇ、Ｈと群の準同型φ：Ｇ→Ｈが与えられているとする。アリスはＺ［Ｇ］上でＮＴＲＵ（Ｇ，ｄ1，ｄ2，ｄ3）の秘密鍵ｆG∈ＬfGを生成する。ただし、φZ(ｆG)∈ＬfHを満たすものとする。
【００４２】
次に、ｆGからＮＴＲＵ（Ｇ，ｄ1，ｄ2，ｄ3）の公開鍵ｈG∈Ｚ［Ｇ］を構成する。このｈGがアリスの公開鍵である。アリスの秘密鍵はｆGであり、ボブの秘密鍵はｆH:=φZ(ｆG)である．
【００４３】
続いて、アリスの暗号化を説明する。メッセージｍはＬmGの元と対応しているものとする。ただし、φZ(ｍ)∈ＬmHを満たすと仮定する。ｍを暗号化するには、まず、ｒ∈ＬrGをφZ(r)∈ＬrHとなる範囲でランダムに選ぶ。次に、ｅ≡ｐｒ・ζ＋ｍ  mod  ｑを計算する。ｅが暗号文となる。
【００４４】
続いて、アリスの復号化を説明する。ｅを復号するには、まず、ａ≡（１＋ｐ・ｆ）・ｅ  mod  ｑを計算する。このとき、ａの係数を−ｑ／２からｑ／２の間に入るように取る。そして、ａ  mod  ｐを計算することによりｍを得る。
【００４５】
続いて、ボブの復号化を説明する。まず、ｅ'＝φZ（ｅ）を計算する。次に、ａ≡（１＋ｐ・ｆ'）・ｅ'  mod  ｑを計算する。このとき、ａの係数を−ｑ／２からｑ／２の間に入るように取る。そして、ａ  mod  ｐを計算することによりｍ'＝φZ（ｍ）を得る。
【００４６】
続いて、具体例を説明する。
【００４７】
まず、多変数NTRUについて説明する。Ｎ1、Ｎ2を自然数とする。また、ＣNで位数Ｎの巡回群を表す。Ｇ＝ＣN_1×ＣN_2とし、Ｈ＝ＣN_1とする。準同型φ：Ｇ→ＨをＣN_1上の射影として定める。これにより部分復号方式が定まる。Ｈを用いた群環NTRUは通常のNTRUと同じであり、また、Ｇは２変数の多変数NTRUと同じものである。同様の考え方で一般次数の多変数NTRUを用いた部分復号方式も考えることができる。
【００４８】
続いて、Frobenius群について説明する。ｌを素数とし、有限体Ｋ＝ＧＦ（ｌ）を考える。ａ∈ＧＦ（ｌ）×、ｂ∈ＧＦ（ｌ）に対して、ψa,b：Ｋ→Ｋを、式(7)で定める。ここで、ＧＦ（ｌ）×は、体ＧＦ（ｌ）からゼロ元０を除いたものである。これは、乗法に関して群をなす。
【００４９】
式(8)とおくと、これは合成を積として有限群になる（Frobenius群）。実際、ＧはＧＦ（ｌ）×のＫへの自然な作用により定まる半直積と同型になる（式(9)）。よって、Ｈ＝ＧＦ（ｌ）×とすると、自然な準同型φ：Ｇ→Ｈが作られる。これにより部分復号方式が定まる。
【００５０】
【数８】
2017038336.tif 000010
【００５１】
続いて、トイ・イグザンプル１の説明をする。ＧがＣN_1×ＣN_2の場合（２変数NTRU）の具体例を説明する。Ｎ1＝６、Ｎ2＝３、ｐ＝３、ｑ＝１０２４とする。２変数多項式Σi,jａijｘiｙjは行列（ａij）ijと対応させることができる。よって、以下、２変数多項式を行列の形で表すことにする。数９にあるように、ＳGでの秘密鍵はｆGと表すことができる。ｆGと対応するＳHの秘密鍵ｆHは、ｆGの最後の列のものとなる。これから計算される公開鍵は、ｈG及びｈHとなる。ｈHはｈGから誰でも計算可能なので、公開鍵はｈGのみで十分である。平文をｍG及びｍHとする。ｍHは、ｍGから定まる。すると、暗号文は、ｅG及びｅHとなる。ｅHは、ｅGから誰でも計算可能なので、暗号文はｅGのみで十分である。
【００５２】
【数９】
2017038336.tif 000011
【００５３】
続いて、トイ・イグザンプル２の説明をする。ＧがFrobenius群Ｆl,l-1の場合の具体例を説明する。ｌ＝５、ｐ＝３、ｑ＝１０２４とする。数１０にあるように、ＳGでの秘密鍵は、ｆGと表すことができる。ｆGと対応するＳHの秘密鍵ｆHは、ｆGの最後の列のｆHとなる。これから計算される公開鍵は、ｈG及びｈHとなる。ｈHは、ｈGから誰でも計算可能なので、公開鍵はｈGのみで十分である。平文を、ｍG及びｍHとする。ｍHは、ｍGから定まる。暗号文は、ｅG及びｅHとなる。ｅHはｅGから誰でも計算可能なので、暗号文はｅGのみで十分である。
【００５４】
【数１０】
2017038336.tif 000012
【００５５】
本実施例では、オリジナルのNTRU暗号を一般化した群環NTRUを構成した。この一般化により、公開鍵が１個であることを特徴とする部分復号方式を構成した。
【００５６】
この提案方式の安全性については、オリジナルのNTRU暗号（非特許文献３参照）とほぼ同等である。そのため、オリジナルのNTRU暗号の安全性が基準となる。オリジナルのNTRU暗号について、その秘密鍵に対し中間一致攻撃が提案されているものの、定量的評価がなされ、パラメータの適切な値の下で安全であるとされている。また、LLL格子基底簡約アルゴリズムを用いた格子簡約攻撃については、既に充分な安全性評価がなされており、定量的評価がなされ、パラメータの適切な値の下で安全であるとされている。これらの二種類の攻撃を組み合わせたハイブリッド攻撃も提案されているが、ハイブリッドによる効率化込みでも、安全性について定量的評価がなされ、パラメータの適切な値の下で安全であるとされている。
【００５７】
図２及び図３を参照して、本願発明の実施の形態に係る復号システムの構成と動作の一例を説明する。図２は、本願発明の実施の形態に係る復号システムの構成の一例を示すブロック図である。図３は、図２の暗号装置３、全文復号装置５、及び、部分復号装置７の動作の一例を示すフロー図である。
【００５８】
復号システム１は、暗号装置３と、全文復号装置５と、部分復号装置７を備える。
【００５９】
暗号装置３は、平文記憶部１１と、公開鍵記憶部１３と、暗号文記憶部１５と、制御部１７と、暗号処理部１９を備える。平文記憶部１１は、メッセージｍを記憶する。メッセージｍはＬmGの元と対応しているものとする。ただし、φZ(ｍ)∈ＬmHを満たすと仮定する。制御部は、平文記憶部１１からメッセージｍを読みだし、公開鍵記憶部１３から公開鍵ｈを読みだす（図３（ａ）のステップＳＴ１）。暗号処理部１９は、ｍを暗号化するために、まず、ｒ∈ＬrGをφZ(r)∈ＬrHとなる範囲でランダムに選ぶ。次に、ｅ≡ｐｒ・ξ＋ｍ  mod  ｑを計算する（図３（ａ）のステップＳＴ２）。ｅが暗号文となる。制御部１７は、暗号文記憶部１５に、暗号文ｅを記憶する（図３（ａ）のステップＳＴ３）。
【００６０】
全文復号装置５は、暗号文記憶部２１と、秘密鍵記憶部２３と、復号文記憶部２５と、制御部２７と、全文復号処理部２９を備える。暗号文記憶部２１は、暗号装置３により暗号化されて得られた暗号文ｅを記憶する。秘密鍵記憶部２３は、全文を復号可能な秘密鍵ｆを記憶する。制御部２７は、暗号文記憶部２１から暗号文ｅを読みだし、秘密鍵記憶部２３から秘密鍵ｆを読みだす（図３（ｂ）のステップＳＴＡ１）。全文復号処理部２９は、暗号文ｅを復号するために、まず、ａ≡（１＋ｐ・ｆ）・ｅ  mod  ｑを計算する。このとき、ａの係数を−ｑ／２からｑ／２の間に入るように取る。そして、ａ  mod  ｐを計算することにより、全文復号文ｍを得る（図３（ｂ）のステップＳＴＡ２）。制御部２７は、全文復号文ｍを復号文記憶部２５に記憶する（図３（ｂ）のステップＳＴＡ３）。
【００６１】
部分復号装置７は、暗号文記憶部３１と、秘密鍵記憶部３３と、復号文記憶部３５と、制御部３７と、部分復号文処理部３９と、部分復号処理部４１を備える。暗号文記憶部２１は、暗号装置３により暗号化されて得られた暗号文ｅを記憶する。秘密鍵記憶部２３は、部分的に復号可能な秘密鍵ｆ'＝φZ(ｆ)を記憶する。制御部２７は、暗号文記憶部３１から暗号文ｅを読みだし、秘密鍵記憶部２３から秘密鍵ｆ'を読みだす（図３（ｃ）のステップＳＴＰ１）。部分暗号文処理部３９は、ｅ'＝φZ（ｅ）を計算する（図３（ｃ）のステップＳＴＰ２）。次に、部分復号処理部４１は、ａ≡（１＋ｐ・ｆ'）・ｅ’  mod  ｑを計算する。このとき、ａの係数を−ｑ／２からｑ／２の間に入るように取る。そして、ａ  mod  ｐを計算することにより部分復号文ｍ'＝φZ（ｍ）を得る（図３（ｃ）のステップＳＴＰ３）。制御部２７は、復号文記憶部３５に、部分復号文ｍ'を記憶する（図３（ｃ）のステップＳＴＰ４）。
【００６２】
なお、例えば、図４にあるように、秘密鍵記憶部において、保有する秘密鍵が全文を復号できるものか部分的に復号できるものかを示す情報を記憶するようにし、復号処理にあたり、まず、制御部が全文を復号できるか否かを判断し、全文を復号できるものであるならば復号処理部が暗号文全文を復号し、部分的に復号できるものであるならば、復号処理部が、部分暗号文を計算して、部分暗号文を秘密鍵により復号して部分復号文を得るようにしてもよい。
【符号の説明】
【００６３】
１  復号システム、３  暗号装置、５  全文復号装置、７  部分復号装置、１１  平文記憶部、１３  公開鍵記憶部、１５  暗号文記憶部、１７  制御部、１９  暗号処理部、２１  暗号文記憶部、２３  秘密鍵記憶部、２５  復号文記憶部、２７  制御部、２９  全文復号処理部、３１  暗号文記憶部、３３  秘密鍵記憶部、３５  復号文記憶部、３７  制御部、３９  部分暗号文処理部、４１  部分復号処理部
【図１】
2017038336.tif 000013
【図２】
2017038336.tif 000014
【図３】
2017038336.tif 000015
【図４】
2017038336.tif 000016