1

暗号・認証分科会

2

活動方針

目的：

暗号・認証技術を一般の人々に分かりやすく説明する！

3

活動方針

どういう人に説明する？

暗号そのものを良く知らない暗号への認識が古典暗号止まりAES・RSAくらいは
知ってるが
最新動向は
良く知らないなどなど...

4

活動方針

どういう人に説明する？

暗号そのものを良く知らない暗号への認識が古典暗号止まりAES・RSAくらいは
知ってるが
最新動向は
良く知らない「最新の暗号技術ってどのようなものがあるのか？」について説明5

研究キーワード

共通鍵暗号

情報量的安全性

相手認証

公開鍵暗号

計算量的安全性

生体・人工物認証

IDベース暗号

証明可能安全性

ヒューマンクリプト

電子署名

汎用結合可能性

匿名性

ハッシュ関数暗号実装の安全性

PKI

鍵共有

CRYPTREC

PGP

マルチパーティプロトコル

量子暗号

PAKE

6

活動メンバー

研究リーダー
趙 晋輝 先生

指導教授
花岡 悟一郎 先生

7

活動メンバー

M2

M1

登丸 尚哉

髙橋 モハマドシャールク

奥村 祐太

西垣 佳亮

小倉 朱門

藤田 真緒

三平 大悟

上里 優介

山本 恭敬

8

活動内容

暗号技術を分かりやすく説明

まずは我々がその技術を理解する必要がある！

9

活動内容

各自が決めたテーマ
について調査学習

指導教授からフィード
バックをもらう

レポートにまとめ指導教員に提出

10

活動テーマ

これらはすべて「先端的」暗号技術！

髙橋 モハマドシャールク

量子暗号

小倉 朱門

格子暗号

上里 優介

プロキシ再暗号化

奥村 祐太

IDベース暗号藤田 真緒

属性ベース暗号山本 恭敬

CKKS方式準同型暗号

11

「先端的」
とは？

本活動で考える「先端的」の定義について紹介する。

12「非先端的」≠「古典的」
ここでは、RSA暗号や楕円曲線暗号、AESも「非先端的」と考える。

古典暗号

現代暗号

先端的暗号

シーザー暗号

RSA暗号

格子暗号

ヴィジュネル暗号

AES

IDベース暗号13「先端的」と「非先端的」の違いは？

従来の安全性・機能性

新しいテクノロジー

より高い
安全性が
欲しい！

より高い
機能性が
欲しい！

これらの要望に応えるべく考案されたのが「先端的」暗号技術

14「新しいテクノロジー」とは？

もちろん沢山あるが、我々が取り上げたのは...

►量子コンピュータ

►クラウドコンピューティング

15

量子コンピュータと先端的暗号技術•

量子コンピュータによってどのような要望が生ま
れたのか？

•

その要望に応じてどのような技術が考案されたのか？

16

量子コンピュータと耐量子性►►

量子コンピュータによって従来の暗号の安全性が脅かされる恐れがある

量子コンピュータでも解けない暗号が欲しい！
►

そのような暗号を耐量子暗号という。

髙橋 モハマドシャールク

量子暗号

小倉 朱門

格子暗号

17

量子暗号
►
►

量子暗号は，通信を盗聴しようとするどんな盗聴者に対しても盗聴を防止できる安全な暗号方式
量子暗号は量子鍵配送、ワンタイムパッドで成り立っている►

量子鍵配送：共通鍵を安全に相手に送信するための仕組
み► ワンタイムパッド：情報理論的に安全であることが証明された暗号技術

18

量子暗号

19

格子暗号
►

暗号化に格子問題を利用した暗号
格子とは…基底を整数倍してたし合わせてできる点の集合

20

格子暗号
►

►
►

格子暗号の構成
公開鍵：基底B, y，秘密鍵：x

NP困難に分類され，量子コンピュータでも解くことは難しい
NIST(National Institute of Standards and Technology)による標準化も進む

21

クラウド
コンピュー
ティングと
先端的暗号技術•

クラウドによってどのような要望が生まれたのか？

•

その要望に応じてどのような技術が考案されたのか？

22

クラウドサービスと暗号►►

多くの情報がクラウドサービスに集まってきている
それらの情報が安全に扱われる保証はあるのか？
►►►

ベンダーが誤って秘密情報をばらまいたりしないか？
内部処理で秘密情報をそのまま扱うのは潜在的に危険では？

安全性(とプライバシー)と機能性を両立させたい！

23

クラウドサービスと暗号►

安全性(とプライバシー)と機能性を両立させたい！

上里 優介

プロキシ再暗号化

奥村 祐太

IDベース暗号藤田 真緒

属性ベース暗号山本 恭敬

CKKS方式準同型暗号

24

プロキシ再暗号化

Aliceの暗号文
平文►►

AliceからBobへの再暗号化鍵 (公開情報)

通常の再暗号化

Bobの暗号文►※鍵はAliceしか作成できないプロキシ再暗号化

平文を介さない → 再暗号化の過程で平文が漏洩しない
再暗号化鍵は公開可能 (公開しても秘密情報は得られない )→ 第三者が再暗号化可能 → 処理負担の制御が可能
再暗号化可能 ⇔ 再暗号化鍵が存在する→ 非中央集権的なアクセス制御が実現できる

具体例: BBS暗号、AFGH暗号

IDベース暗号►►

従来の公開鍵暗号は公開鍵では相手が誰かわからない→ 公開鍵証明書認証局(CA)に問い合わせて本人認証
IDベース暗号では公開鍵が個人情報→ 公開鍵の認証が必要ない暗号方式の実現

25

26

属性ベース暗号►►►

IDベース暗号に基づいた暗号で、IDを属性の集合として捉えることで詳細なアクセス制御を組み込んだ暗号属性を指定して、文書の暗号化ができる→会社などの人数の多い組織におけるアクセス制御が容易
CP-ABE：暗号文に条件を、秘密鍵に属性を埋め込む方式
KP-ABE ：暗号文に属性を、
秘密鍵に条件を埋め込む方式

CKKS方式準同型暗号►►►

準同型暗号とは
暗号文のまま足し算や掛け算かできる
サーバーに生データを置く必要がない→ 情報漏洩のリスク低減

►
►
►
►

27

CKKS方式準同型暗号 [Cheon+17]複素数の暗号化：より実用的に安全性：RLWE仮定による耐量子計算機性
rescailing：乗算時のノイズを抑制

28

まとめ
►
►

暗号の役割は単なる暗号化，復号に留まらない求められる安全性は変化し，より高い機能性を求められる

29

付録：暗号技術の紹介スライド

以下のスライドは、各メンバーが活動を通じて作成した暗号技術の紹介スライドです。
►
►
►
►
►
►

p. 30～ 量子暗号 (髙橋)p. 51～ 格子暗号 (小倉)p. 71～ プロキシ再暗号化 (上里)p. 88～ IDベース暗号 (奥村)p. 112～ 属性ベース暗号 (藤田)p. 126～ CKKS方式準同型暗号 (山本)

量子暗号

背景
• 近年量子コンピュータの実用化に向けて開発が進められています。
• 量子コンピュータの処理速度は現代のコン
ピュータよりも高速であるため、RSA 暗号などが現実的な時間で破られる恐れが出てきました。

量子暗号とは• 量子暗号は，通信を盗聴しようとするどんな盗聴者に対しても盗聴を防止できる安全な暗号方式• 具体的に言うと、量子鍵配送によって事前に暗号鍵を伝送共有し、ワンタイムパッドと呼ばれる暗号方式で通信を暗号化すること

量子暗号が無いと・・・• どんな暗号化された通信も攻撃者が解読できてし
まう
RSA暗号の鍵の長さが2048bit（デジタル署名（なりすましを防ぐために使われる）の場合）であるとき、最高性能のスーパーコンピューターで解読に1億年以上かかると言われていますですが、（十分な性能を持つ）量子コンピュータでは数時間で4096bitの鍵を解読することができてしまうと言われています※数時間で解くためにショアのアルゴリズムというのを使う必要があります通信が解読されることで起きうること• クレジットカードの番号が流出してしまい、攻撃者に利用される• 企業の機密情報を漏洩させ、企業が倒産に追い込まれる• 相手国の防衛戦略を入手し、弱点を攻撃し侵略・・・などの恐ろしい出来事が起こると言えます自分には関係ない• スライドで挙げた「RSA暗号」が使われている
場面
SSL/TLS サーバー証明書の「ドメイン認証」（そのほかにもメール送信者の認証に使われる
S/MIME証明書、電子契約時の電子署名にも使われています）

自分には関係ない• SSL/TLS サーバー証明書の「ドメイン認証」
SSL/TLS サーバー証明書とはウェブサイトにアクセスする際に行われる通信の暗号化、

ウェブサイトがなりすまされていないかのチェック（ドメイン認証）に使われます
国内上場企業における常時SSL化対応サイトは 91.4% ！
→ RSA暗号が今日の社会に浸透していることがわかります※常時SSL化 調査レポート 上場企業サイト対応状況（2023年10月版）,
https://www.feedtailor.jp/report_aossl/

量子暗号の全体図※補足
共通鍵：平文を暗号化、復号化をするのに用いられる鍵のこと
平文：文章のこと（メールと考えるとわかりやすいですね！）
暗号化：平文を他人がわからないようにすること
復号化：暗号化された平文をもとの平文に戻すこと

暗号化
共通鍵

平文

平文ゲット！

送信
共通鍵で暗号化された平文
共通鍵を光子に乗せる
1

平文の暗号化に共通鍵を使用後、送信機を用いて共通鍵を光子に変換

復
号
化

送信機

0

1

0

1

共通鍵で暗号化された平文

共通鍵

0

送信
受信機

受信機を用いて光子を共通鍵に変換量子暗号とは• 量子暗号は，通信を盗聴しようとするどんな盗聴者に対しても盗聴を防止できる安全な暗号方式• 具体的に言うと、量子鍵配送によって事前に暗号鍵を伝送共有し、ワンタイムパッドと呼ばれる暗号方式で通信を暗号化すること

量子鍵配送の具体的説明
共通鍵を光子に乗せる
1

共通鍵

共通鍵を光
子に変換

送信機

0

1
送信

0

1

0

受信機

光子を共通
鍵に変換

共通鍵

• 量子鍵配送は共通鍵を安全に相手に送信するための仕組み• 量子鍵配送の手順• 送信機は送信方法を、受信機は受信方法をランダムに選択します• 送信機は共通鍵の情報を1ビットずつエンコードし、送信機が送信を行い, 受信機が受信します• (1),(2) を繰り返し, 送信機が鍵のすべての情報（ビッ ト）の送信を終えた後、送信機、受信機が事前に選択した送信方法, 受信方法を開示します• 送信機の送信方法と受信機の受信方法が一致すれば終了し, 一致しなければ再度 (1) に戻ります

量子鍵配送の具体的説明
共通鍵を光子に乗せる
1

共通鍵

共通鍵を光
子に変換

送信機

0

1
送信

0

1

0

受信機

光子を共通
鍵に変換

• 注意点
• 送信および受信方法は2種類あり、送信機と受信機はその中からランダムに選択します

共通鍵

量子鍵配送の安全性
共通鍵を光子に乗せる
1

共通鍵を光
共通鍵
送信機
子に変換
• 3つの観点で安全性を考えてみます

0

1
送信

0

1

0

受信機

光子を共通
鍵に変換

共通鍵

①盗聴の検知はできるのか？
光子の性質を用いて可能。光子は抜き取られた場合、光子の総数が変化するため検知が可能。
また光子を盗聴すると光子の状態が変化するため検知が可能。
②そもそも盗聴できるのか？
盗聴は可能ですが、盗聴の検知が可能です。そのため結果として盗聴されてない光子の送信が可能。
③光子の改ざんは可能なのか？
理論上可能です。ですが、盗聴者は検知回避のためすべての光子の送信方法を知っておく必要があり、それを知ることは現実的に不可能と言えます。

量子暗号とは• 量子暗号は，通信を盗聴しようとするどんな盗聴者に対しても盗聴を防止できる安全な暗号方式• 具体的に言うと、量子鍵配送によって事前に暗号鍵を伝送共有し、ワンタイムパッドと呼ばれる暗号方式で通信を暗号化すること

ワンタイムパッドの具体的説明

暗号化

復号化
送信

共通鍵

平文

共通鍵で暗号化された平文共通鍵で暗号化された平文共通鍵• ワンタイムパッド（バーナム暗号とも呼ばれる）は、上記の図で言うと暗号化、復号化で使われる暗号方式です。

送信

ワンタイムパッドの具体的説
明• ワンタイムパッドは排他的論理和（XOR）を用いて平文を暗号化する
A

B

A XOR B

0

0

0

1

0

1

0

1

1

1

1

0

排他的論理和（XOR）：AとBが与えられた時AとBが等しければ0、
そうでなければ1となる演算のこと※ コンピュータは0と1しか扱うことができないため入力は0,1のいずれかとなりますワンタイムパッドの具体的説
明• Aを平文、Bを共通鍵とし、AとBの排他的論理
和を計算すると暗号文が得られます
平文

共通鍵

暗号文

0

0

0

1

0

1

0

1

1

1

1

0

ワンタイムパッドの具体的説
明• 平文は共通鍵と暗号文の排他的論理和を計算することで得られます
暗号文

共通鍵

平文

0

0

0

1

0

1

1

1

0

0

1

1

ワンタイムパッドの安全性• 情報理論的に安全であることが証明されている• 情報理論的に安全であるとは？
「攻撃者が暗号文 を入手している場合としていない場合で平文に関して得られる情報量が等しい」ことを指している→ 攻撃者がどんなに頑張っても暗号文から得られる手掛かりがゼロ

ワンタイムパッドって本当に安全？
• 「情報理論的に安全であること」と「暗号解読」の関係
暗号解読とは「総当たり攻撃よりも,速く（効率的に）解読すること」を指します※ 総当たり攻撃とは考えられる答えをすべて試す攻撃例）0-9までの数字が用いられる4桁の暗証番号
この場合総当たり攻撃すると10（通り）× 10 × 10 × 10 = 10000
回試す必要がありますワンタイムパッドって本当に安全？
• 「情報理論的に安全であること」と「暗号解読」の関係
ここまでを整理すると①暗号解読とは総当たり攻撃よりも効率的に解読すること②情報理論的に安全 =「総当たり攻撃」以外に解読する方法はない→ つまり情報理論的に安全であれば暗号解読は
できない！

まとめ
• 量子暗号は非常に強力な暗号技術である• 量子暗号が実用化されればみんなが安心して情報のやり取りができるようになる• これを機に量子暗号に興味を持っていただければ嬉しいです格子暗号

目次• 現代暗号技術• 量子コンピュータ• 耐量子計算機暗号• 格子暗号1

現代暗号技術➢ 公開鍵暗号方式• 公開鍵eと秘密鍵dに暗号化と復号• 秘密鍵を持つBは解読可能• 秘密鍵を知らない攻撃者は解読不可能

2

RSA暗号➢ RSA暗号• 広く普及している公開鍵暗号の一つ• 素因数分解の困難性が根拠• 自然数𝑁は公開．𝑁 = 𝑝𝑞の素因数𝑝, 𝑞は非公開• 公開鍵と秘密鍵には以下を満たす自然数𝑒, 𝑑を使用
gcd 𝑒, 𝑝 − 1 𝑞 − 1 = 1
𝑒𝑑 = 1 (mod 𝑝 − 1 𝑞 − 1 )• 平文は𝑚 ∈ 𝑁ℤ

3

RSA暗号の仕組み

4

•

送信者A

受信者B

RSA暗号の安全性➢ RSA暗号への攻撃方法①公開鍵から秘密鍵を計算（完全解読）②自然数𝑁を素因分解する③公開鍵，暗号文から平文を計算（一方向性の解読）②から①，③が計算可能③は未解決問題

しかし，素因数分解は現実的な時間で計算できない

素因数分解の困難性が
RSA暗号の安全性の根拠

5

量子コンピュータ

6➢ 通常のコンピュータ• 2つの状態を0, 1によって表現➢ 量子コンピュータ• 観測前は2つの状態の重ね合わせ．観測によって状態を決定
通常のコンピュータ

量子コンピュータ

状態の重ね合わせどちらかが確定

観測で確定

量子コンピュータ

7➢ 通常のコンピュータ• 2つの状態を0, 1によって表現➢ 量子コンピュータ• 観測前は2つの状態の重ね合わせ．観測によって状態を決定
通常のコンピュータ

量子コンピュータ

状態の重ね合わせどちらかが確定

観測で確定

RSA暗号の高速解読

8➢ ショアのアルゴリズム• 量子フーリエ変換を利用したアルゴリズム．
高速で素因数分解可能が可能になる• スーパーコンピュータでも１億年以上かかる計算を実用的な時間で計算可能に

将来的にRSA暗号の安全性が破られる
https://xtech.nikkei.com/atcl/nxt/column/18/01191/012900001/

RSA暗号の高速解読による影響➢ 情報漏洩
• 暗号通信が完全に覗ける• インターネットユーザは約44億人．そのすべてのキャッシュカード情報などが晒せる• 情報漏洩による損害賠償の見積もりは１人あたり約2万3000円➢ 電子署名の偽造• RSAを利用した署名• 多くのドメイン認証に利用• 秘密鍵が流出した場合，
SSL証明書が失効→多くのサービスが利用できなくなる9

耐量子計算機暗号➢ 耐量子計算機暗号• 量子コンピュータでも解読困難な数学的な問題➢ 求められる機能• 平文が高速に暗号化• 落とし戸により暗号文を高速で復元• 鍵，暗号文のサイズが小さい

10

耐量子計算機暗号11 格子暗号

 多変数多項式暗号

 符号暗号

 同種写像暗号

格子の問題の困難性に基づいた暗号
誤り訂正符号を利用した
暗号

多変数多項式を利用した
暗号
楕円曲線における
同種写像に基づく暗号

NP困難な問題のワーストケースへの帰着により高い安全性

格子暗号は最も注目されている

格子暗号➢ 格子暗号• 格子問題に基づく暗号• 安全性はSVP/CVPの困難性に基づく➢ 格子• 𝑛この線型独立なベクトル𝒃1 , 𝒃2 , ⋯ , 𝒃𝑛 の線形和の集合

12

LWE問題➢ Learning with Error (LWE)問題• 微小なエラー𝒆を含む𝒚から𝒙を求める問題• CVPやSVPに帰着されるため，LWEによる暗号構成ではそれらの困難性を安全性の根拠とする

𝐵 = 𝒃1 𝒃2 ⋯ 𝒃𝑛 , 𝒙, 𝒚, 𝒆 ∈ ℝ𝑛
𝒚 = 𝐵𝒙 + 𝒆
↓
𝒙 =?

13

格子暗号の構成•

14

SVP/CVP➢ 最近ベクトル問題（CVP）• 位置𝒙から最も近い格子点を求める問題➢ 最短ベクトル問題（SVP）• 𝒔 ∈ ℒのうち最小となるベクトル𝒔を求める問題

15

CVP/SVP• 総当たりでの計算• NP困難であることが知られている

無数にあるベクトルの中から，ベクトルの大きさを計算して最も短いものを探すのは時間がかかる

16

LWEチャレンジ

17• ダルムシュタット工科大学主催のチャレンジ• 耐量子計算機暗号の標準化にむけた安全な暗号化のパラメータ選定の技術的な根拠として利用
𝑛 is dimension
𝛼 is the relative error size
解決済み
未解決

11月15日現在の解読状況

https://www.latticechallenge.org/lwe_challenge/challenge.php

格子暗号の標準化

18• NIST により2017年から耐量子計算機暗号の標準化に向けた動き• 2022年7月時点での標準化状況➢ PKE/KEM-CRYSTALS-KYBER (格子ベースKEM)➢ Signature-CRYSTALS-DILITHIUM (格子ベース署名)-FALCON (格子ベース署名)-SPHINCS (ハッシュベース署名)

まとめ⚫ RSA暗号は素因数分解の困難性を安全性の根拠とした暗号方式⚫ 量子コンピュータによってRSA暗号が高速で解読可能⚫ 耐量子計算機暗号として格子暗号に注目⚫ 耐量子計算機暗号の標準化に向けた動向

19

プロキシ再暗号化について背景① クラウドサービスは便利• コスト削減・生産性向上につながりうる• 場所の制約を受けない• 広く利用されている• 利用者数も増加傾向にある

データを効率よく共有クラウドサービスの利用状況(総務省, 令和4年)

背景② クラウドサービスは安全か？

内部犯

人的ミス

脆弱性

機密情報の流出

多数の利用者
↓
攻撃対象に
なりやすい

プライバシー上の問題も

背景③ クラウドサービスは安全か？
クラウドサービスに限らないが，サーバやサービス事業社は必ずしも信頼できるとはいえない

出典:
https://www.onebe.co.jp/dlpnews/archives/%e5%af%8c%e5%a3%ab%e9%80%9a%e3%82%af%e3%83%a9%e3%82%a6%e3%83%89%e3%83%86%e3%82%af%e3%83%8e%
e3%83%ad%e3%82%b8%e3%83%bc%e3%82%ba%e3%80%81%e8%84%86%e5%bc%b1%e6%80%a7%e3%82%92%e7%aa%81%e3%81%84%e3%81%9f.html

出典: https://www.nri.com/jp/knowledge/blog/lst/2018/fis/kiuchi/1221_2

出典: https://www.itmedia.co.jp/enterprise/articles/1609/01/news073.html

背景④ クラウドサービスは安全か？

ユーザが設定するパスワード

データ暗号
化用の鍵

password

出典: https://news.mynavi.jp/techplus/article/20221223-2544442/

パスワードベースの暗号化はクラウドサービスも含め広く採用されている→パスワードの強度次第では，暗号文の流出だけでも機密情報が危険に晒される

色々なサイトのログ
インパスワードなど

アカウント情報(メールア
ドレスや電話番号など)およびサイト情報(URL)

password

流出!?

脆弱なパスワー
ドだと...

バックアップ背景⑤クラウドサービスを利用してもらうには

内部犯

技術

人的ミス

脆弱性

機密情報の流出

多数の利用者
↓
攻撃対象に
なりやすい

高い安全性
↓
強力な宣伝材料データを安全に管理する• データ をそのままクラウドに保管→情報流出の恐れ• 安全に保管するには暗号化が効果的• 復号鍵を持たない人からは内容を見られない

平文のままで保管暗号化して保管

第3者に流出する恐れがある

第3者には内容が分からない

データを安全に共有する• 公開鍵暗号を利用する• 暗号化鍵

Alice

と復号鍵

Bob

が別なので事前の鍵共有が不要

Alice

公開鍵暗号で暗号化→復号鍵のやりとりは不要
復号鍵をやりとりすると流出の恐れがある

Bob

データを大勢と共有するときは？
• 暗号化するのは平文を持っているユーザ側→大きな負担• サーバに暗号文の生成を安全に行わせられないか？

？

ユ
ー
ザ
側
の
負
担

…

…

…

…

プロキシ再暗号化とは• 再暗号化を実現する• 再暗号化: Aliceが復号可能な暗号文→Bobが復号可能な暗号文• 再暗号化鍵を用いて再暗号化が行われる• その計算は第3者が実行できる• 再暗号化鍵や暗号文が外部に流出しても秘密情報は漏洩しない• サーバにも漏洩しない

プロキシ再暗号化の仕組み
① 暗号化

＋

→

② 通常の復号＋→③ 再暗号化鍵の生成④ 再暗号化＋＋→→⑤ 再暗号化による暗号文の復号 (通常の復号と同じでも違ってもよい)＋→

BBS暗号 ：ElGamal暗号を派生させた暗号方式※プロキシ再暗号化の先駆けである方式．
(プロキシ再暗号化としては安全性が不十分)

再暗号化鍵

再暗号化
Aliceの暗号文

復号

Aliceの秘密鍵

Bobの暗号文復
号

Bobの秘密鍵正式なプロキシ再暗号化技術の例• AFGH(Ateniese-Fu-Green-Hohenberger)暗号• ペアリング(双線形写像)を利用 (ペアリングは楕円曲線などで利用可能)

楕円曲線：ペアリング：楕円曲線上の点

AFGH暗号
再暗号化鍵

Aliceの暗号文

復
号

再暗号化

Aliceの秘密鍵

Bobの暗号文復
号

Bobの秘密鍵なぜプロキシ再暗号化は安全か？
• BBS暗号の公開情報から平文を当てる難しさ• DH問題：からを求める問題DH問題の難しさ
難• 復号鍵が入手できる→ 平文が入手困難

平文が入手できる

復号鍵も入手困難

再暗号化鍵が流出しても秘密情報は漏洩しない

まとめ• プロキシ再暗号化は，暗号文を・第3者に・復号させずに再暗号化させる暗号方式．
• 送信先の公開鍵と自身の秘密鍵で作成した再暗号鍵からは，第3者は自分平文や復号鍵などの秘密情報が分からない．

参考
1. 総務省, “令和4年通信利用動向調査の結果”, 2023, available athttps://www.soumu.go.jp/johotsusintokei/statistics/data/230529_1.pdf
2. M. Blaze, G. Bleumer and M. Strauss, “Divertible Protocols and Atomic Proxy
Cryptography”, EUROCRYPT, Springer-Verlag, pp. 127-144, 1998.
3. G. Ateniese, K. Fu, M. Green and S. Hohenberger, “Improved proxy reencryption schemes with applications to secure distributed storage”, ACM
Trans. Inf. Syst. Secur., Vol. 9, No. 1, pp. 1-30, 2006.

IDベース暗号とは

目次
１．必要となった背景
２．求められていた機能
３．IDベース暗号の仕組みと安全性
４．IDベース暗号によって得られた効果・性能

1目次
１．必要となった背景
２．求められていた機能
３．IDベース暗号の仕組みと安全性
４．IDベース暗号によって得られた効果・性能

2共通鍵暗号と公開鍵暗号
暗号鍵

平文

復号鍵

暗号文
送信者

平文
受信者

共通鍵暗号…暗号鍵と復号鍵が同じ信用できる通信経路での鍵のやり取りが必要
公開鍵暗号…暗号鍵（公開鍵）と復号鍵（秘密鍵）が異なる
共通鍵暗号よりも計算時間が多くなる
3

公開鍵暗号が抱える問題
公開鍵

送信者

本当に本人？

受信者

メッセージを送る際に、送信者からは公開鍵しかわからない⇒本当に送りたい相手の公開鍵なのか？

公開鍵証明書認証局(CA)に問い合わせ4公開鍵暗号が抱える問題
CA
①
③

②

送信者

④

①受信者がデジタル署名付きの公開鍵証明書をCAに発行してもらう(公開鍵公開時)②受信者が公開鍵証明書を送信者へ送る③送信者はCAに問い合わせて公開鍵証明書のデ
ジタル署名用の鍵を入手し検証する④送信者が受信者側の公開鍵を用いて暗号化し、暗号文を送る

公開鍵

受信者
5

目次
１．必要となった背景
２．求められていた機能
３．IDベース暗号の仕組みと安全性
４．IDベース暗号によって得られた効果・性能

6公開鍵暗号が抱える問題
CA

送信者

送信者

受信者

受信者

送信者

受信者

送信者

受信者

証明書の発行が社会全体のいたるところで行われており大きな負担になっている

7

全世界での一日あたりの発行数

実際に大手認証局であるLet`s Encryptは10月28日にX(旧Twitter)
上で一日の公開鍵証明書の発行数が3.5億件に至ったと述べている

8個人情報を公開鍵にした暗号
公開鍵(個人情報)

送信者

公開鍵が個人情報
だから誰に送ろうとしているかわかる

受信者

公開鍵とID(identity)の同一化が求められ“公開鍵の認証が必要ない暗号”として生まれたのがIDベース暗号
IDとして利用できるものは氏名・住所・メアド・ドメイン名など
9目次
１．必要となった背景
２．求められていた機能
３．IDベース暗号の仕組みと安全性
４．IDベース暗号によって得られた効果・性能

10IDベース暗号の仕組み
ⅰ)Setup-公開パラメータの集合-マスターキーⅱ)Extract-ユーザーキーⅲ)Encrypt-平文-暗号文ⅳ)Decrypt-平文

𝑀𝑃𝐾 = 𝑝, 𝐺1 , 𝐺𝑇 , 𝑒, 𝑛, 𝑔, 𝑔𝑝𝑢𝑏 , 𝐻1 , 𝐻2
𝑀𝑆𝐾

𝑆𝐾𝐼𝐷 (𝑀𝑃𝐾, 𝐼𝐷から生成)
𝑀

𝐶(𝑀𝑃𝐾, 𝐼𝐷, 𝑀から生成)

𝑀(𝑀𝑃𝐾, 𝑆𝐾𝐼𝐷 , 𝐶から生成)

11

IDベース暗号の仕組み
Setup
・このアルゴリズムでは公開パラメータとマスターキーを生成する
・素数位数の群は巡回群であるため、二つの素数位数の群を用いて双線形性を満たすPairing写像を定義できる・巡回群には生成元が必ず存在するため，生成元とマスターキーなどを用いていくつかのパラメータを生成し，ハッシュ関数を含めて公開パラメータとする

12

IDベース暗号の仕組み
Setup

素数𝑝
位数𝑝の乗法群𝐺1 , 𝐺𝑟
𝐺1 の生成元𝑔Pairing写像𝑒: 𝐺1 × 𝐺1 → 𝐺𝑟∗
ランダムな元𝑠 ∈ 𝑍𝑝

13

IDベース暗号の仕組み
Setup

𝑔𝑝𝑢𝑏 = 𝑔 𝑠
ハッシュ関数𝐻1 : {0,1}∗ → 𝐺1
𝐻2 : 𝐺𝑟 → {0,1}∗

公開パラメータ𝑀𝑃𝐾 = 𝑝, 𝐺1 , 𝐺𝑇 , 𝑒, 𝑛, 𝑔, 𝑔𝑝𝑢𝑏 , 𝐻1 , 𝐻2
マスターキー𝑀𝑆𝐾 = 𝑠

14

IDベース暗号の仕組み
Extract
・このアルゴリズムではユーザーキーを生成する
・公開鍵として用いたいIDを二進数で表し，ハッシュ関数を用いて巡回群の元に変換し公開鍵を生成する
・公開鍵にマスターキーを用いてユーザーキーを生成する

15

IDベース暗号の仕組み
Extract

個人情報𝐼𝐷 ∈ {1,0}∗
公開鍵𝑄𝐼𝐷 = 𝐻1 (𝐼𝐷) ∈ 𝐺1
ユーザーキー𝑆𝐾𝐼𝐷 = 𝑄𝐼𝐷 𝑠

16IDベース暗号の仕組み
Encrypt
・このアルゴリズムでは平文から暗号文を生成する
・公開パラメータと公開鍵にペアリング写像を適用し、巡回群の元を生成する・生成した巡回群の元にハッシュ関数を適用し、二進数の暗号鍵を生成する
・𝑍𝑝 ∗ からランダムな元を一つ選択し、生成した暗号鍵と公開パラメータ、平文を共に用いることで暗号文を計算できる
17

IDベース暗号の仕組み
Encrypt

平文𝑀
𝑔𝐼𝐷 = 𝑒(𝑄𝐼𝐷 , 𝑔𝑝𝑢𝑏 ) ∈ 𝐺𝑟
ランダムな元𝑟 ∈ 𝑍𝑝 ∗暗号文𝐶 = (𝑔𝑟 , 𝑀 ⊕ 𝐻2 (𝑔𝐼𝐷 𝑟 ))18

IDベース暗号の仕組み
Decrypt
・このアルゴリズムでは暗号文から平文を復号する
・送られてきた暗号文にハッシュ関数とPairing写像、ユーザーキーを用いることで復号できる

19

IDベース暗号の仕組み
Decrypt

暗号文𝐶 = (𝑈, 𝑉)
平文𝑀 = 𝑉 ⊕ 𝐻2 (𝑒(𝑆𝐾𝐼𝐷 , 𝑈))

20IDベース暗号の安全性
IDベース暗号では双線形性を満たすペアリング写像が用いられている
ペアリング写像の性質から、盗聴者が暗号を解読するには・送信者が持つランダムパラメータ𝑟
・受信者が持つユーザー鍵𝑆𝐾𝐼𝐷のどちらかが必要であるが、どちらも公開情報でないことから解読は困難であることが知られている
21

目次
１．必要となった背景
２．求められていた機能
３．IDベース暗号の仕組みと安全性
４．IDベース暗号によって得られた効果・性能

22

IDベース暗号によって得られた効果・性能
IDベース暗号はペアリングを用いて実装され、他の暗号に応用されている。
フォワードセキュア暗号-鍵の漏洩に強い暗号
放送暗号-多数の受信者に一括で暗号文を送信してもサイズが大きくならない暗号
タイムリリース暗号-ある時刻が来るまでは復号することが出来ない暗号
キーワード検索暗号-暗号化されたままキーワード検索を行うことが出来る暗号23

属性ベース暗号属性ベース暗号ができた背景
⽂書の管理
昔

現在

紙媒体

電⼦ファイル

電⼦ファイルの閲覧権限の付与には、公開鍵暗号が使⽤されている。
2

属性ベース暗号ができた背景

従来の公開鍵暗号の問題点• 閲覧権限の付与の⾮効率性☆組織の⼈数の⼤きさに依存☆権限付与の⼿間が多く、複雑

鍵と属性を1対N、N対1対応できる属性ベース暗号が提案された。
3

属性ベース暗号に求められた機能

1.

暗号⽂の復号者を管理する機能- 復号条件を満たした⼈のみが復号可能。

2.

暗号鍵と復号鍵が1対N、N対1対応する機能- ⼀つの暗号⽂を複数の秘密鍵で復号可能。
- ⼀つの秘密鍵で複数の暗号⽂を復号可能。
4

【機能例】ある会社での⽂書のアクセス権限の付与
社員100名に1MBの⽂書を読めるようにする。
属性ベース暗号「なし」【問題点】
・社員それぞれに対して⽂書を送信

暗号化しなくてはいけない。

暗号⽂書A

A

送信

⽂書

暗号⽂書B

B

⽂書

暗号化
送信

C

→暗号化した⽂書は、
1MB×100⼈分=100MB必要になる。
⼈数に⽐例して、データ量が⼤
きくなる。

暗号⽂書C

5

【機能例】ある会社での⽂書のアクセス権限の付与
社員100名に1MBの⽂書を読めるようにする。
属性ベース暗号「あり」【改善点】
・1つの⽂書に対して、

A必要な暗号化した⽂書は1つのみ。

送信
暗号化
送信

⽂書

B

C

送信

暗号⽂書ABC

⽂書→暗号化した⽂書は、
1MB×1⼈分=1MB必要。
⼈数に⽐例せず⼀定。

6

属性ベース暗号の仕組み (IDベース暗号の⼀般化)

IDベース暗号
個⼈を特定することが可能な情報であるIDを公開鍵として⽤いる暗号⽅式。
IDの例：emailアドレス、携帯番号 etc.
従来の公開鍵暗号は、公開鍵とその所有者を証明書で保証する必要があったが、IDを利⽤することで、保証が不要となった。
送信

暗号⽂書B

A

暗号⽂書B
復号

暗号化

BのIDを利⽤した
公開鍵

B
BのIDに対応した
秘密鍵

⽂書

⽂書

7

属性ベース暗号の仕組み (最も原始的な属性ベース暗号)

属性が⼀つの属性ベース暗号【例】総務部の⼈だけが復号できる属性ベース暗号・「総務部」という属性を公開鍵として⽂書を暗号化し、「総務部」という属性に対応した秘密鍵を⽤いて暗号⽂の復号を⾏う。

送信

暗号⽂書
(総務部のみが
開ける)
営業部
A

暗号⽂書
(総務部のみが
開ける)
復号

暗号化

公開鍵
属性：総務部

総務部
B

秘密鍵
属性：総務部⽂書

・IDベース暗号におけるIDと属性
ベース暗号における属性が同じ働きをしている。
→属性が⼀つの属性ベース暗号は、属性がIDのIDベース暗号である。

⽂書

8

属性ベース暗号の仕組み (1対N対応)
属性が複数ある属性ベース暗号

!∪#

復号

送信

ID=属性A

暗号文書A
属性A

暗号文書A

文書

AのIDを利用した
秘密鍵

暗号化

復号

文書
送信

ID=属性B
暗号文書B

属性B

暗号文書B

文書

BのIDを利用した
秘密鍵

・AもしくはBの属性を持てば暗号を復号できる．
【 IDベース暗号を⽤いた実現⽅法】
・属性AをIDとしたIDベース暗号で⽂書を暗号化．
・同様に，属性BをIDとしたIDベース暗号で⽂書を暗号化．
・属性を満たした者にそれぞれ秘密
鍵を配布する．

9

属性ベース暗号の仕組み (1対N対応)
属性が複数ある属性ベース暗号

!∩#
秘密鍵s

秘密鍵の情報を含むs+rとrを暗号化
属性A

属性を満たしている
⼈に秘密鍵を配布することで，情報を復
号可能

暗号化

暗号化
⽂書

暗号⽂書

暗号化された情報s+r

情報s+r

送信
属性B

属性! ∩ #
復号

送信
暗号化
情報r

暗号化された情報r
暗号化された情報s+rとr

情報s+rとr⼆つの情報から秘密鍵sを復元

・AとB両⽅の属性を持たないと暗号を復号できる．
【 IDベース暗号を⽤いた実現⽅法】
・属性AをIDとしたIDベース暗号で情報 “s+r”を暗号化．
・属性BをIDとしたIDベース暗号で情報 “r”を暗号化．
・両⽅の属性を満たしたものは，
情報“s+r”と“r”を復号することができ，その⼆つの情報から，秘密鍵 “s”の情報を⼊⼿できる．

10

KP-ABE(Key Policy Attribute Based Encryption)
暗号⽂に属性を、秘密鍵にポリシーを埋め込む⽅式の属性ベース暗号
秘密鍵にポリシーを埋め込むことで、条件を満たした⼈に鍵を配布する。

鍵⽣成センター公開

マスター公開鍵：!" #マスター秘密鍵：
!$ #

!" #

!$ #を⽤いて，関係式&に関する
秘密鍵'#( を⽣成

属性A

秘密鍵'#(
⽂書M

⽂書M
復号

暗号⽂書C

図1:KP-ABEの仕組み

暗号化

11

CP-ABE(Ciphertext Policy Attribute Based Encryption)
暗号⽂にポリシーを、秘密鍵に属性を埋め込む⽅式
暗号化の際にポリシーを埋め込むことで、ポリシーを満たした⼈のみが暗号⽂を復号できる。
鍵⽣成センター公開

マスター公開鍵：!" #マスター秘密鍵：
!$ #

!" #

!$ #を⽤いて，属性Aに関する
秘密鍵'#( を⽣成

関係式%

秘密鍵'#(
⽂書M

⽂書M
復号

暗号⽂書C

図2:CP-ABEの仕組み

暗号化

12

属性ベース暗号によって得られた効果①鍵の管理が効率的に⾏える
従来の公開鍵暗号
個⼈⼀⼈⼀⼈に秘密鍵が必要

属性ベース暗号
属性ごとの鍵⽣成②アクセス制御が容易
従来の公開鍵暗号
個⼈⼀⼈⼀⼈にアクセス権限を付与

属性ベース暗号属性ごとにアクセス権限を付与
13

属性ベース暗号の安全性

DBDH仮定「楕円曲線上の点Pと整数a, b, cと有限体の値%に対して、(', (', )', *', %)が与えられたときに% = -(', ')./0 を判定する」という問題を解くことが難しいという仮定

14

CKKS方式の準同型暗号

目次• はじめに• CKKS方式の暗号化/復号フレームワーク• 準同型暗号とPPDM• Encode, Decode, 鍵生成, 暗号化, 復号の定義• 安全性の確認• 深層学習への適用に立ちはだかる壁• Appendix（各種証明）

2

はじめに
近年、 ChatgptなどのニューラルベースのAI技術が猛威を振るっている.
AIを利用したサービスの提供において、サーバへのAIモデル搭載は必要不可欠
サーバが攻撃を受けるとAIモデル、学習データが漏洩してしまう恐れがある.
そこで、サーバ上の学習/推論を暗号化したままできないか、という議論がある
本活動では秘密計算もとい秘密学習/推論を実現する最先端暗号技術「CKKS方式の準同型暗号」について調査した.

3

原論文紹介
論文名: Homomorphic Encryption for Arithmetic of Approximate Numbers.
著者: Jung Hee Cheon, Andrey Kim, Miran Kim, Yong Soo Song
国際会議: ASIACRYPT 2017: 409-437

4

CKKS方式の暗号化/復号フレームワーク

複素数列

EncodeDecode

整数係数多項式

Encrypt

暗号

Decrypt5暗号化、復号の例
192 + 181𝑥
− 256𝑥 2 + 90𝑥 3[4 − 𝑖,2 + 7𝑖]
複素数列

Encode

整数係数多項式

Decode[4.005 − 1.006𝑖,
1.995 + 6.994𝑖]

誤差を伴う復号

Encrypt

暗号

Decrypt
192 + 180𝑥
− 256𝑥 2 + 90𝑥 3

6

乗算の例
192 + 181𝑥 − 256𝑥 2 + 90𝑥 3
160 + 91𝑥 + 160𝑥 2 + 45𝑥 3[4 − 𝑖, 2 + 7𝑖][3 + 4𝑖, 2 − 𝑖]
複素数列

Encode

整数係数多項式

Decode[16.00 + 13.01𝑖,
11.00 + 11.99𝑖]

Encrypt
Decrypt

暗号×

864 + 679𝑥 + 32𝑥 2 + 453𝑥 37

準同型暗号とは準同型暗号. 暗号文のまま加算や乗算が可能な暗号.

3

19

3×5

×
5

8

15

32

活用事例
加法準同型暗号を用いた化合物データの検索

https://www.aist.go.jp/aist_j/press_release/pr2011/pr20111
101/pr20111101.html

8情報漏洩件数
近年、情報漏洩件数は年々増加している.

東京商工リサーチのページから引用
https://www.tsr-net.co.jp/data/detail/1197322_1527.html
9情報漏洩の事例と被害規模
個人情報の漏洩は過去に多く起こっている. 規模が大きいほど被害も大きい.

株式会社ベネッセコーポレーションの個人情報漏洩
株式会社ベネッセコーポレーションは、2014年7月、顧客の個
人情報が外部に漏洩したことを公表した. 原因は業務委託先の元社員による不正行為. 流出した個人情報の数は、約2,895万件.
特別損失260億円を計上.
森永製菓株式会社の顧客情報漏洩

森永製菓株式会社は、2022年3月、管理運用する複数のサーバに対して、
不正アクセスが発生し、顧客情報が流出した可能性があることを発表した。最大で、1,648,922人の個人情報が漏洩した可能性があるとのこと.
10課題: データ分析と情報漏洩のジレンマ
データ分析の専門家の育成には膨大なコストがかかる.
データ分析の外部委託はデータを外部に渡すことから情報漏洩のリスクが高まる.

わが社の***データ
分析したいなあ

でもうちには専門家いないし、外部への委託は漏洩のリスクがあるしなあ11

プライバシー保護データマイニング
前述の課題はプライバシー保護データマイニング技術（PPDM）により解決される.

パーソナルデータの分析

個人情報保護

PPDM

k-匿名化
秘密分散
差分プライバシー
連合学習
準同型暗号
etc…
12

PPDMの1技術としての準同型暗号の特徴• 秘匿データの分析、機械学習技術への応用が可能.
➢ 暗号化したまま計算を行えるため、計算サーバには暗号化済みのAIモデルとデー
タのみを置いておけばよく、従来と比較してデータ漏洩のリスクが少ない.

13

活用例1. データ分析の業務委託• 近年機械学習を用いたデータサイエンス技術は進歩しており、高精度な予測が期待できる• 業務委託により自社でデータサイエンティストを育成するコストを削減できる• 個人情報の漏洩が大きな損失に• 情報漏洩の可能性は委託先の情報管理体制に依存し、委託元は関与しづらい• 委託先がデータを漏洩した場
合、委託元の損失に

PPDM• 委託元は暗号化したデータだけを委託先に渡し、委託先は暗号文のままデータ分
析を行う• 委託先が知れるのは暗号文のみ→委託先からのデータ漏洩を防ぐことができる• 準同型暗号を用いることでデータ分析における機械学
習技術をそのまま活用できる
14活用例2. 個人情報含むデータの販売• 自社で有益なビッグデータを保有する会社は「データ販売」を1つの事業にできる• JRなどは加工済パーソナルデータの外部販売に意欲的• 個人情報が特定できる形でデータを販売できない

PPDM• データの暗号化により外部販売が可能になる• 準同型暗号を用いることで分析時に機械学習の活用が可能になる

15

従来の準同型暗号の問題点
実数の暗号化に対応していない
浮動小数点数を値に持つデータの分析の秘密計算に使いにくい

乗算のたびに暗号文のサイズが大きくなる
サイズ𝑚の暗号と𝑛の暗号を乗算するとサイズ𝑚 + 𝑛 − 1の暗号が得られる
例えば、𝑎𝑛 を暗号化しようとするとサイズ𝑂(𝑛)の暗号となってしまう16

従来の準同型暗号との違い その1
各暗号の平文空間をあらわした図.
従来の暗号とは違い, CKKS方式の暗号は複素数を平文にとることができる.
これにより、準同型暗号の深層学習への適用が現実味を帯びた.

複素数ℂ

CKKS
整数ℤ
BGV
GSW

トーラス
𝕋 = ℝ/ℤ

TFHF

BGV [Zvika Brakerski, 2011]
GSW [Craig Gentry et al., 2013]
TFHF [Ilaria Chillotti et al., 2020]※TFHEは[Ilaria Chillotti et al., 2016]をベースにつくられている

CKKS [Jung Hee Cheon et al., 2017]17

従来の準同型暗号との違い その2
CKKS方式の暗号では, リサイズ処理を用いて乗算時の暗号文サイズ増加を抑制した.
サイズ2

𝑐𝑎

サイズ2

𝑐𝑏

×

サイズ3

サイズ3→2𝑐𝑎 𝑐𝑏

ResizeCKKS方式のoutput

従来暗号のoutput18有用性（開発者視点）
平文のまま
学習

攻撃

学習データ
初期モデル

学習済モデル

学習データ
学習済モデル

攻撃者に学習データ、学習済みモデルが漏洩する
19

有用性（開発者視点）
暗号文のまま
学習
学習データ
初期モデル

暗号化した
学習データ

学習済みモ
デル

推論結果の
暗号文

攻撃

暗号文

攻撃者は暗号文しか入手できない
20

有用性（ユーザ視点）
平文のまま
推論

入力データ

出力データ

攻撃

入力データ
出力データ

攻撃者に入出力データが漏洩する
21

有用性（ユーザ視点）
暗号文のまま
推論
入力データ

暗号化した
入力データ

出力データ

出力データ
の暗号文

攻撃

暗号文

攻撃者は暗号文しか入手できない
22

CKKS方式の準同型暗号の設計思想• RLWEベースの暗号フレームワークに落とし込むために、複素ベクトルと整数係数多項式を1対1に対応させ、近似的な変換（Encode）と逆変換（Decode）を可能にした.
• 乗算時の暗号文サイズ増加を抑えるために、評価鍵を用いたリサイズ処理を導入した.
• 平文に含まれるノイズを小さくするため、BGV方式の暗号[Brakerski et al., 2012]で提案されたmodulus switchingと同様の処理であるRescaleを導入した.

23

定義
•
•
•

𝐽 ≔ −1𝑁 ∈2∗ℕ𝜉≔𝑒𝜋𝐽𝑁

平文の次数の2倍∈ℂ

1の2𝑁乗根• 𝐴 = 𝐴𝑖𝑗 ≔ 𝜉 2𝑖−1 𝑗−1 ∈ ℂ𝑁×𝑁

ヴァンデルモンド行列• 𝑏𝑗 ≔ 𝐴1𝑗 , … , 𝐴𝑁𝑗 = (𝜉𝑗−1 , 𝜉 3 𝑗−1 , … , 𝜉 2𝑁−1 𝑗−1 )• ∆𝑠𝑐𝑎𝑙𝑒 ∈ ℕ

十分大きな数

𝐴の𝑗列目

𝑛 𝑛• ℤ(𝑛) ≔ ℕ ∩ [− , )2 224Encode, Decodeの定義
Encode

𝑁
ℂ2

𝜋 −1

𝜎 −1

ℂ𝑁

𝜋

× ∆𝑠𝑐𝑎𝑙𝑒𝑅𝜎÷ ∆𝑘𝑠𝑐𝑎𝑙𝑒

𝜋 −1 : [𝑧1 , 𝑧2 , … , 𝑧𝑁 ] → [𝑧1 , … , 𝑧𝑁 , 𝑧𝑁 , … , 𝑧ഥ1 ]2

2

2

𝜋: [𝑧1 , … , 𝑧𝑁 , 𝑧𝑁 , … , 𝑧ഥ1 ] → [𝑧1 , 𝑧2 , … , 𝑧𝑁 ]22<𝑧,𝑏 ><𝑧,𝑏 >

𝑅

Decode※ 𝑅 = ℤ 𝑋 /(𝑋 𝑁 + 1)

2

<𝑧,𝑏 >

𝜎 −1 : 𝑧 → <𝑏 ,𝑏1 > + <𝑏 ,𝑏2 > 𝑋 + ⋯ + <𝑏 ,𝑏𝑁 > 𝑋 𝑁−1
1 1

2 2

𝜎: 𝑓 → (𝑓 𝜉 , 𝑓 𝜉 3 , … , 𝑓 𝜉 2𝑁−1 )

𝑁

𝑁

25

鍵生成、暗号化、復号の定義
鍵生成
𝑞𝑙 ← 𝑞0 𝑝𝑙 (𝑙 = 0, … , 𝐿)𝑎 ∈ ℤ𝑞𝐿 [𝑋]/(𝑋 𝑁 + 1), 𝑎′ ∈ ℤ𝑃⋅𝑞𝐿 [𝑋]/(𝑋 𝑁 + 1)𝑒, 𝑒 ′ ~𝒩(0, 𝜎 2 )秘密鍵: 𝑠𝑘 = 𝑠 ∈ ℤ 3 [𝑋]/(𝑋 𝑁 + 1)
公開鍵: 𝑝𝑘 = 𝑝1 , 𝑝2 = −𝑎 ⋅ 𝑠 + 𝑒, 𝑎 𝑞𝐿
評価鍵: 𝑒𝑣𝑘 = −𝑎′ ⋅ 𝑠 + 𝑒 ′ + 𝑃𝑠 2 , 𝑎′ 𝑃⋅𝑞𝐿

公開鍵𝑝𝑘から秘密鍵𝑠𝑘を求めるのは困難（後述）

暗号化(Encrypt)

暗号文: 𝑐 = 𝑐1 , 𝑐2 = ( 𝑣 ⋅ 𝑝1 + 𝑒1 + 𝜇 𝑞𝐿 , 𝑣 ⋅ 𝑝2 + 𝑒2 𝑞𝐿 )復号(Decrypt)

復号文: 𝜇′ = 𝑐1 + 𝑐2 ⋅ 𝑠 𝑞𝑙

𝐿 − 𝑙回のリスケール

26

安全性の確認
公開鍵 𝑝𝑘 = 𝑝1 , 𝑝2 = ( −𝑎 ⋅ 𝑠 + 𝑒 𝑞𝐿 , 𝑎) から秘密鍵 𝑠 が求められるか−𝑎 ⋅ 𝑠 + 𝑒 𝑞𝐿 と 𝑎 = 𝑎 𝑞𝐿 から 𝑠 が求められるかRLWE仮定集合{ 𝑎𝑖 𝑞𝐿 , −𝑎𝑖 ⋅ 𝑠 + 𝑒𝑖 𝑞𝐿 } と集合{ 𝑎𝑖 𝑞𝐿 , 𝑏𝑖 𝑞𝐿 }を混ざっている状態から分離することは難しい。

難しい
CKKS方式の暗号はRLWE仮定をもとに安全性が保証されている.

27

RLWE仮定にはちょうどいい𝜎が重要
簡単のため𝑎, 𝑠, 𝑒 ∈ ℝとする.

𝜎小さい• 分離しやすい＝秘密鍵𝑠の値が解読されやすい• 平文に含まれるノイズが小さい＝誤差が無視できるくらい小さい

𝜎大きい• 分離しにくい＝秘密鍵𝑠の値が解読されにくい• 平文に含まれるノイズが大きい＝誤差が無視できないほど大きい28

Resize処理を用いた暗号文の乗算の流れ
暗号文𝑐𝑎 , 𝑐𝑏 の乗算を考える.

𝐷𝑒𝑐𝑟𝑦𝑝𝑡 𝑐𝑎 ⋅ 𝐷𝑒𝑐𝑟𝑦𝑝𝑡 𝑐𝑏= 𝑐𝑎1 + 𝑐𝑎2 ⋅ 𝑠 𝑞𝑙 ⋅ 𝑐𝑏1 + 𝑐𝑏2 ⋅ 𝑠 𝑞𝑙
= 𝑐𝑎1 ⋅ 𝑐𝑏1 + 𝑐𝑎1 𝑐𝑏2 + 𝑐𝑏1 𝑐𝑎2 ⋅ 𝑠 + 𝑐𝑎2 ⋅ 𝑐𝑏2 ⋅ 𝑠 2 𝑞𝑙
= 𝑐0′ + 𝑐1′ 𝑠 + 𝑐2′ 𝑠 2 𝑞𝑙

Resize

このままだと乗算暗号文は(𝑐0′ , 𝑐1′ , 𝑐2′ )となり, 𝑐𝑎 , 𝑐𝑏 と比較してサイズが1増える.
サイズを2に保つために, 以下の式であらわされる評価鍵𝑒𝑣𝑘を用いる.
𝑒𝑣𝑘 = (−𝑎′ 𝑠 + 𝑒 ′ + 𝑃𝑠 2 , 𝑎′ )※𝑃は十分大きくとる

ここで𝑐𝑎 , 𝑐𝑏 を乗算して得られる暗号として以下に示す(𝑑0 , 𝑑1 )を出力する.
𝑑0 , 𝑑1 = 𝑐0′ , 𝑐1′ + [𝑃−1 ⋅ 𝑐2′ ⋅ 𝑒𝑣𝑘]

→ 出力

29

加算・乗算暗号の復号可能性
Decryptにより生じる誤差が十分小さいかどうかの確認
加算暗号の場合乗算暗号の場合

𝐷𝑒𝑐𝑟𝑦𝑝𝑡 𝑐𝑎 + 𝑐𝑏
= 𝐷𝑒𝑐𝑟𝑦𝑝𝑡 𝑐𝑎 + 𝐷𝑒𝑐𝑟𝑦𝑝𝑡 𝑐𝑏= 𝑝𝑎 + 𝑒𝑎 + (𝑝𝑏 + 𝑒𝑏 )= 𝑝𝑎 + 𝑝𝑏 + (𝑒𝑎 + 𝑒𝑏 )𝐷𝑒𝑐𝑟𝑦𝑝𝑡 𝑐𝑎 ⋅ 𝐷𝑒𝑐𝑟𝑦𝑝𝑡 𝑐𝑏= 𝑝𝑎 + 𝑒𝑎 (𝑝𝑏 + 𝑒𝑏 )= 𝑝𝑎 𝑝𝑏 + 𝑝𝑎 𝑒𝑏 + 𝑝𝑏 𝑒𝑎 + 𝑒𝑎 𝑒𝑏

小さい≈ 𝑝𝑎 + 𝑝𝑏 にできる

小さくない…

≈ 𝑝𝑎 𝑝𝑏 にできない

30

乗算暗号文のノイズを減らす方法
𝑞𝑙′
𝑐←𝑐 mod 𝑞𝑙′
𝑞𝑙

rescaling𝑐 ← 𝑐 mod 𝑞𝑙′

simple modular
reduction𝑞′• rescalingにより平文に含まれるノイズを 𝑙 の比で減らすことができる.
𝑞𝑙′

𝑞𝑙• 同時に、平文そのものも の比で減少する. 復号するときは注意が必要.
𝑞𝑙• レベルの異なる暗号どうしで計算するときは計算前にレベルの高い暗号を低いほうに合わせる必要があるが、原論文ではrescalingではなくsimple modular reductionを用いている.

31

深層学習への適用に立ちはだかる壁• CKKS方式の準同型暗号は乗算回数に制限がある（制限回数を超えて乗算を行うと誤差が無視できないほどに大きくなる）• 一般に, ニューラルベースのAIモデルの秘密学習/推論が普及していないのは乗算回数に制限があることが理由として挙げられる.
• 以降では, ニューラルネットワークで用いる計算に対して加算, 乗算
回数を見積もる.

32

NNで要求される関数
計算グラフ

必要な計算（準伝播）

加算グラフ

加算

乗算グラフ

乗算

指数グラフ

指数計算

対数グラフ

対数計算

ReLUグラフmax(0,x)計算必要な計算（逆伝播）除算33

NNで要求される関数
機能

関数名

必要な計算

線形変換

Affine変換

加算、乗算

活性化関数

ReLU

Max計算

Softmax

指数計算、除算、
加算

CrossEntropyLoss

対数計算、乗算、
加算

MeanSquaredError

乗算、加算

損失関数

加算、乗算以外は秘密計算が難しい…

すべての計算を加算、乗算のみを用いた計算にすればよい.
34

和積のみでの計算（多項式近似）
指数, 対数, max計算は多項式に近似できる.
∞𝑥𝑛
𝑥2 𝑥3 𝑥4
𝑒 =෍= 1+𝑥+ +
+
+⋯
𝑛!
2
6 24
𝑥

𝑛=0

∞

−1 𝑛−1 𝑛𝑥2 𝑥3 𝑥4
log 1 + 𝑥 = ෍
𝑥 =𝑥− +
− + ⋯ ( 𝑥 < 1)
𝑛
2
3
4
𝑛=1

𝑥
= （略）
max 0, 𝑥 ≈ 𝑆𝑤𝑖𝑠ℎ 𝑥 =1 + 𝑒 −𝑥

※Swish [Ramachandran et al., 2017]

乗算回数の多さから、実用的ではないとする意見もある.
35

和積のみでの計算（除算）𝑥ො = 1 − 𝑥, 𝑥ො ≤ を満たすとき, 十分大きい 𝑟 に対して以下の式が成り立つ.
2
1

𝑟−1

𝑗

𝑥 −1 ≈ ෑ(1 + 𝑥ො 2 )𝑗=0

和積のみで𝑥 −1 をあらわすことができている.

36

乗算回数（多項式）求めるもの: 𝑑次の多項式の代入計算に必要な乗算回数
乗算回数:
導出:

log 𝑑 + 1 + σ𝑑𝑖=1 𝑓(𝑖) （𝑓(𝑖): 𝑖の2進数表記における1の個数）

高速指数計算法を用いて 𝑥, 𝑥 2 , 𝑥 4 , 𝑥 8 , … , 𝑥 2を計算する. この計算は log 𝑑 + 1
回の乗算が必要になる。
その後, 多項式の代入計算を行う. 𝑖次の項の計算には𝑓(𝑖)回の乗算が必要になる.
log 𝑑

𝑎0 + 𝑎1 𝑥 + 𝑎2 𝑥 2 + 𝑎3 𝑥 3 + 𝑎4 𝑥 4 + ⋯ + 𝑎𝑑 𝑥 𝑑

1回

1回

2回

1回

例えば, 𝑑 = 4のときは合計8回の乗算が必要となる.

38

まとめ
•
•
•
•
•
•

準同型暗号の活用によりデータのプライバシーを保護しながら分析を行うことができる.
CKKS方式の準同型暗号はRLWE仮定に基づく複素数暗号化フレームワーク.
CKKS方式の暗号は近似準同型暗号.
リサイズ処理により乗算暗号文のサイズ爆発を抑えることに成功.
リスケール処理により計算精度を保ったまま誤差を小さくできる. （回数制限あり）
ニューラルネットワークへの応用には乗算回数の壁がある. 実用化にはまだ遠い.

39

Appendix

40

Encode(z) の各係数が実数であることの証明
命題. 𝐸𝑛𝑐𝑜𝑑𝑒 𝑧 ∈ ℝ[𝑥]/(𝑥 𝑁+1 + 1)

以下、命題の証明<𝑧 ′ ,𝑏𝑖><𝑏𝑖,𝑏𝑖 >1= 𝑁 (𝑧1 𝐴1𝑖 + ⋯ + 𝑧𝑁 𝐴𝑁𝑖 + 𝑧𝑁 𝐴 𝑁+1 𝑖 + ⋯ + 𝑧ഥ1 𝐴𝑁𝑖 )
2 2
2
2
1
= 𝑁 (𝑧1 𝐴1𝑖 + ⋯ + 𝑧𝑁 𝐴𝑁𝑖 + 𝑧𝑁 𝐴𝑁𝑖 + ⋯ + 𝑧ഥ1 𝐴1𝑖 )
2 2
2 2
1
= { 𝑧1 𝐴1𝑖 + 𝑧ഥ1 𝐴1𝑖 + ⋯ + (𝑧𝑁 𝐴𝑁𝑖 + 𝑧𝑁 𝐴𝑁𝑖 )}
𝑁
2 2
2 2
1
= {𝑅𝑒 𝑧1 𝐴1𝑖 + ⋯ + 𝑅𝑒(𝑧𝑁 𝐴𝑁𝑖 )}
𝑁
2 2

∈ℝ

′

<𝑧 ,𝑏 >
𝐸𝑛𝑐𝑜𝑑𝑒(𝑧) において 𝑥 𝑖−1 の係数は <𝑏 ,𝑏𝑖> とあらわされるので, 𝐸𝑛𝑐𝑜𝑑𝑒(𝑧)𝑖 𝑖の各係数は実数である. ∎41

Decode(Encode(z))≈z の証明 補題1
補題1. 1 ≤ 𝑘1 ≤ 𝑁, 1 ≤ 𝑘2 ≤ 𝑁 のとき, σ𝑁
𝑖=1 𝐴𝑘1 𝑖 𝐴𝑘2 𝑖 = ቊ
以下補題1の証明

𝑁,0,(𝑘1 + 𝑘2 = 𝑁 + 1)
(𝑘1 + 𝑘2 ≠ 𝑁 + 1)

σ𝑁
𝑖=1 𝐴𝑘1 𝑖 𝐴𝑘2 𝑖
2𝑘1 +2𝑘2 −2 (𝑖−1)
= σ𝑁
𝑖=1 𝜉

これは𝑘1 + 𝑘2 = 𝑁 + 1 のとき𝑁 となる. 以降ではそうでないときを考える.
𝜉 2𝑘1 +2𝑘2 −2 (𝑖−1) , 𝑖 = 1, … , 𝑁 について、周期を𝑁′(≤ 𝑁)とおく. 𝜉 2𝑘1 +2𝑘2−2 (𝑖−1) , 𝑖 =′1, … , 𝑁′ について、これらは互いに異なる1の𝑁′乗根であるから, 方程式𝑧 𝑁 = 1 の′
2𝑘1 +2𝑘2 −2 (𝑖−1) は0 になる.
解である. よって, 解と係数の関係によりその総和σ𝑁
𝑖=1 𝜉
2𝑘1 +2𝑘2−2 (𝑖−1) = 0 が成り立つ. ∎したがって, σ𝑁
𝑖=1 𝜉42Decode(Encode(z))≈z の証明 補題2
𝑝 𝑥′<𝑧 ,𝑏𝑖> 𝑖−1
≔ σ𝑁
とおく.
𝑖=1⌊<𝑏 ,𝑏 >⌉𝑥𝑖𝑖

補題2. 𝑝 𝐴𝑘2 ≈ ∆𝑠𝑐𝑎𝑙𝑒 𝑧𝑘
以下補題2の証明
𝑝 𝐴𝑘2′<𝑧 ,𝑏𝑖 > 𝑖−1= σ𝑁⌊
𝑖=1 <𝑏 ,𝑏 >⌉𝐴𝑘2

≈ σ𝑁
𝑖=1

= σ𝑁
𝑖=1

𝑖

𝑖

<𝑧 ′ ,𝑏𝑖 >𝑖−1𝐴<𝑏 ,𝑏 > 𝑘2𝑖 𝑖′<𝑧 ,𝑏𝑖 >𝐴<𝑏𝑖 ,𝑏𝑖 > 𝑘𝑖∆
= 𝑠𝑐𝑎𝑙𝑒 σ𝑁
𝑖=1{𝑧1 𝐴1𝑖 + ⋯ + 𝑧𝑁 𝐴𝑁𝑖 + 𝑧𝑁 𝐴 𝑁+1 𝑖 + ⋯ + 𝑧ഥ1 𝐴𝑁𝑖 }𝐴𝑘𝑖
𝑁
2 2
2
2
∆𝑠𝑐𝑎𝑙𝑒 𝑁
σ𝑖=1{𝑧1 𝐴𝑁𝑖 + ⋯ + 𝑧𝑁 𝐴 𝑁+1 𝑖 + 𝑧𝑁 𝐴𝑁𝑖 + ⋯ + 𝑧ഥ1 𝐴1𝑖 }𝐴𝑘𝑖 (∵ 𝐴𝑗𝑖 = 𝐴(𝑁−𝑗+1)𝑖 )
=
𝑁
2

2

2

2

∆
𝑁
𝑁
𝑁
σ𝑁
σ
= 𝑠𝑐𝑎𝑙𝑒
{𝑧
𝐴
𝐴
+
⋯
+
𝑧
𝐴
+
𝑧
ഥ
𝑁 σ𝑖=1 𝐴 𝑁
𝑁 σ𝑖=1 𝐴𝑁 𝐴𝑘𝑖 + ⋯ + 𝑧
1
𝑁𝑖
𝑘𝑖
𝑘𝑖
1
𝑖=1
𝑖=1 𝐴1𝑖 𝐴𝑘𝑖 }
+1 𝑖
𝑖
𝑁
2
2
2
2
∆
= 𝑠𝑐𝑎𝑙𝑒 𝑧𝑘 σ𝑁(∵ 補題1より)
𝑖=1 𝐴(𝑁−𝑘+1)𝑖 𝐴𝑘𝑖
𝑁∆= 𝑠𝑐𝑎𝑙𝑒𝑧𝑘 𝑁𝑁= ∆𝑠𝑐𝑎𝑙𝑒 𝑧𝑘 ∎43

Decode(Encode(z))≈z の証明
命題. 𝐷𝑒𝑐𝑜𝑑𝑒 𝐸𝑛𝑐𝑜𝑑𝑒 𝑧

以下、命題の証明

𝐷𝑒𝑐𝑜𝑑𝑒(𝐸𝑛𝑐𝑜𝑑𝑒 𝑧 )≈𝑧<𝑧 ′ ,𝑏 >𝑖𝑖−1 )= 𝐷𝑒𝑐𝑜𝑑𝑒(𝑝 𝑥 ≔ σ𝑁
𝑖=1 <𝑏 ,𝑏 > 𝑥= ∆−1𝑠𝑐𝑎𝑙𝑒 (𝑝 𝐴12 , … , 𝑝𝑖𝑖

𝐴𝑁 2 )2≈ ∆−1
𝑠𝑐𝑎𝑙𝑒 (∆𝑠𝑐𝑎𝑙𝑒 𝑧1 , … , ∆𝑠𝑐𝑎𝑙𝑒 𝑧𝑁 )= (𝑧1 , … , 𝑧𝑁 )

=𝑧∎

2

2

(∵ 補題2より𝑝 𝐴𝑘2 = ∆𝑠𝑐𝑎𝑙𝑒 𝑧𝑘 )44

Decrypt(Encrypt(p))≈p の証明
命題. 𝐷𝑒𝑐𝑜𝑑𝑒 𝐸𝑛𝑐𝑟𝑦𝑝𝑡(𝑝) ≈ 𝑝
以下、命題の証明

𝐷𝑒𝑐𝑟𝑦𝑝𝑡(𝐸𝑛𝑐𝑟𝑦𝑝𝑡 𝑝 )= 𝑐1 + 𝑐2 ⋅ 𝑠 𝑞𝑙
=

=
=

=

=

𝑣 ⋅ 𝑝1 + 𝑒1 + 𝑝 𝑞𝐿 + 𝑣 ⋅ 𝑝2 + 𝑒2 𝑞𝐿 ⋅ 𝑠𝑞𝑙𝑣 ⋅ −𝑎 ⋅ 𝑠 + 𝑒 𝑞𝐿 + 𝑒1 + 𝑝 𝑞 + 𝑣 ⋅ 𝑎 + 𝑒2 𝑞𝐿 ⋅ 𝑠𝐿𝑞𝑙𝑣 ⋅ −𝑎 ⋅ 𝑠 + 𝑒 𝑞𝐿 + 𝑒1 + 𝑝 𝑞 + 𝑣 ⋅ 𝑎 + 𝑒2 𝑞𝐿 ⋅ 𝑠
𝐿𝑣 ⋅ (−𝑎 ⋅ 𝑠 + 𝑒) + 𝑒1 + 𝑝 + (𝑣 ⋅ 𝑎 + 𝑒2 ) ⋅ 𝑠 𝑞𝐿𝑣 ⋅ 𝑒 + 𝑒1 + 𝑝 + 𝑒2 ⋅ 𝑠 𝑞𝐿

= 𝑣 ⋅ 𝑒 + 𝑒1 + 𝑝 + 𝑒2 ⋅ 𝑠 𝑞𝑙
= 𝑝 + 𝑒′
≈𝑝∎

𝑞𝑙

𝑞𝑙

𝑞𝐿

𝑞𝑙

(∵ 𝑞𝑙 は𝑞𝐿 の約数)
45

Decode(p+e)≈Decode(p) の証明
命題. 𝑒 ≪ 𝑝 のとき, 𝐷𝑒𝑐𝑜𝑑𝑒 𝑝 + 𝑒 ≈ 𝐷𝑒𝑐𝑜𝑑𝑒(𝑝)以下、命題の証明

𝑒′(𝑎) は𝑝(𝑎) に比べて小さいので, 𝑝 𝑎 + 𝑒 ′ (𝑎) ≈ 𝑝(𝑎) が成り立つ.
よって,𝐷𝑒𝑐𝑜𝑑𝑒(𝑝 + 𝑒 ′ )
′
′
= ∆−1
𝑠𝑐𝑎𝑙𝑒 ((𝑝 + 𝑒 ) 𝐴12 , … , (𝑝 + 𝑒 ) 𝐴𝑁2 )≈ ∆−1𝑠𝑐𝑎𝑙𝑒 (𝑝 𝐴12 , … , 𝑝= 𝐷𝑒𝑐𝑜𝑑𝑒(𝑝) ∎𝐴𝑁 2 )
22

46

加法準同型性の証明
命題. 𝐷𝑒𝑐𝑟𝑦𝑝𝑡 𝑐𝑎 + 𝑐𝑏 = 𝐷𝑒𝑐𝑟𝑦𝑝𝑡 𝑐𝑎 + 𝐷𝑒𝑐𝑟𝑦𝑝𝑡 𝑐𝑏
以下、命題の証明

𝐷𝑒𝑐𝑟𝑦𝑝𝑡 𝑐𝑎 + 𝐷𝑒𝑐𝑟𝑦𝑝𝑡 𝑐𝑏= 𝑐𝑎1 + 𝑐𝑎2 ⋅ 𝑠 𝑞𝑙 + 𝑐𝑏1 + 𝑐𝑏2 ⋅ 𝑠 𝑞𝑙
= 𝑐𝑎1 + 𝑐𝑏1 + (𝑐𝑎2 + 𝑐𝑏2 ) ⋅ 𝑠 𝑞𝑙
= 𝐷𝑒𝑐𝑟𝑦𝑝𝑡(𝑐𝑎 + 𝑐𝑏 ) ∎47

暗号文の乗算の流れ
暗号文𝑐𝑎 , 𝑐𝑏 の乗算を考える.

𝐷𝑒𝑐𝑟𝑦𝑝𝑡 𝑐𝑎 ⋅ 𝐷𝑒𝑐𝑟𝑦𝑝𝑡 𝑐𝑏= 𝑐𝑎1 + 𝑐𝑎2 ⋅ 𝑠 𝑞𝑙 ⋅ 𝑐𝑏1 + 𝑐𝑏2 ⋅ 𝑠 𝑞𝑙
= 𝑐𝑎1 ⋅ 𝑐𝑏1 + 𝑐𝑎1 𝑐𝑏2 + 𝑐𝑏1 𝑐𝑎2 ⋅ 𝑠 + 𝑐𝑎2 ⋅ 𝑐𝑏2 ⋅ 𝑠 2 𝑞𝑙
= 𝑐0′ + 𝑐1′ 𝑠 + 𝑐2′ 𝑠 2 𝑞𝑙

このままだと乗算暗号文は(𝑐0′ , 𝑐1′ , 𝑐2′ )となり, 𝑐𝑎 , 𝑐𝑏 と比較してサイズが1増える.
サイズを2に保つために, 以下の式であらわされる評価鍵𝑒𝑣𝑘を用いる.
𝑒𝑣𝑘 = (−𝑎′ 𝑠 + 𝑒 ′ + 𝑃𝑠 2 , 𝑎′ )※𝑃は十分大きくとる

ここで𝑐𝑎 , 𝑐𝑏 を乗算して得られる暗号として以下に示す(𝑑0 , 𝑑1 )を出力する.
𝑑0 , 𝑑1 = 𝑐0′ , 𝑐1′ + [𝑃−1 ⋅ 𝑐2′ ⋅ 𝑒𝑣𝑘]48

乗法準同型性の証明
命題. 𝐷𝑒𝑐𝑜𝑑𝑒 (𝑑0 , 𝑑1 ) ≈ 𝐷𝑒𝑐𝑟𝑦𝑝𝑡 𝑐𝑎 ⋅ 𝐷𝑒𝑐𝑟𝑦𝑝𝑡(𝑐𝑏 )以下、命題の証明

𝐷𝑒𝑐𝑟𝑦𝑝𝑡 𝑑0 , 𝑑1
= 𝑑0 + 𝑑1 𝑠
≈ 𝑐0′ + 𝑃−1 𝑐2′ −𝑎′ 𝑠 + 𝑒 ′ + 𝑐2′ 𝑠 2 + (𝑐1′ 𝑠 + 𝑃−1 𝑐2′ 𝑎′ 𝑠)= 𝑐0′ + 𝑐1′ 𝑠 + 𝑐2′ 𝑠 2 + 𝑃−1 𝑐2′ 𝑒 ′≈ 𝐷𝑒𝑐𝑟𝑦𝑝𝑡 𝑐𝑎 ⋅ 𝐷𝑒𝑐𝑟𝑦𝑝𝑡(𝑐𝑏 ) ∎49