※2012年03月16日追記
Lattice Crypto Day 2012 Japan は盛況の内に終了することができました。講演者・参加者のみなさまに改めて御礼申し上げます。
LCD2012J 実行委員会一同
【開催趣旨】
以前より格子は暗号解析の重要なツールとして利用されてきましたが、近年に
なって、ＩＤベース暗号 (IBE; ID-based Encryption) や完全準同型暗号 (FHE;
Fully-Homomorphic Encryption) を構成するためのツールとしても利用される
ようになり、注目を集めています。実際、国内外で暗号解析と暗号構成の両面
におけるさまざまな研究が進められています。しかし国内の場合、これら成果は
個別に報告されることが多く、その根底となっている格子理論がフォーカスされ
ることはほとんどありませんでした。
本集会は、暗号と格子をキーワードとして、最先端で研究を進められている方
々に講演頂くことで、格子を利用した暗号研究をさらに促進させることを目的と
しています。単なる理論だけでなく、実験的な視点からの報告も予定されており
ますので、格子と暗号の立体的な結びつきを感じ取ることもできると思います。
数学・暗号の専門者のみならず、学生などの、広い範囲からの参加をお待ちして
います。
【開催情報】
・日時：2012年3月15日（木） 12時45分～18時 (12時20分開場)
・場所：インターネットイニシアティブ (IIJ) 本社 17階 中会議室
〒101-0051 東京都千代田区神田神保町1-105 神保町三井ビルディング
http://www.iij.ad.jp/company/about/map/head-office.html
・参加費：無料
・定員：50名 (事前申込は不要ですが、満席の場合には先着順とさせていただき
ますので、ご容赦下さい)
・備考：集会終了後に神保町付近にて懇親会を開催しました
【プログラム】（講演時間・講演タイトルは変更となる可能性があります。講演概要は随時追加の予定です）
12時45分～12時50分
はじめに
12時50分～13時10分
草川 恵太 (NTT)
Brief History of Lattice Crypto World
13時10分～13時50分
國廣 昇 (東京大学)
チュートリアル：格子簡約を用いた RSA 暗号への攻撃
13時50分～14時20分
篠原 直行 (情報通信機構)
RSA 暗号の Small Secret Exponent Attack に対する統一的な手法
14時20分～14時50分
安田 雅哉 (富士通研究所)
Gentry 完全準同型暗号に対する格子縮約を用いた攻撃実験報告
(14時50分～15時10分 休憩)
15時10分～15時40分
長沼 健 (日立製作所)
みんなで考えよう！！なぜ格子暗号は解かれてしまうのか？
15時40分～16時10分
藤堂 洋介 (神戸大学)
Alwen-Peikert構成法における格子の落とし戸関数に対する評価，改良，実装
16時10分～16時40分
青野 良範 (情報通信機構)
Solving Learning with Errors via Lattice Vector Enumeration Using Extreme Pruning
16時40分～17時10分
Mehdi Tibouchi (NTT)
Fully Homomorphic Encryption Based on the LWE Assumption
17時10分～17時40分
草川 恵太 (NTT)
A Survey on LWE-based Encryption Schemes
(18時30分～ 懇親会)
【講演概要】
講演者：草川 恵太 (NTT)
講演タイトル：Brief History of Lattice Crypto World
概要：格子がどのように暗号に関わってきたのかを紹介する。格子問題そのもの
の研究、格子基底縮小アルゴリズム（LLL）を用いた攻撃の歴史、格子問題の困
難性に基づく様々な暗号方式の構成について触れる。
講演者：國廣 昇 (東京大学)
講演タイトル：チュートリアル：格子簡約を用いた RSA 暗号への攻撃
概要：本講演では，格子簡約アルゴリズムを利用したRSA暗号の解読手法の
いくつかを解説する．具体的には，RSA暗号において，秘密鍵pの上位半分が
漏洩している場合，格子簡約アルゴリズムを用いて，素因数分解が可能である
ことが知られている．また，トータルで70%の情報が漏洩している場合にも，
素因数分解が可能であることが知られている．これらのアルゴリズムについて，
詳細に解説を行う．
講演者：篠原 直行 (情報通信機構)
講演タイトル：RSA 暗号の Small Secret Exponent Attack に対する統一的な手法
概要：RSA 暗号には秘密鍵 $p,q,d$ と公開鍵 $N,e$ があり,
格子理論を用いた RSA 暗号への攻撃として,
合同式 $x(N + 1 + y) + 1 \equiv 0 \pmod{e}$ の small root を見つける方法が
いくつか提案されている.
Boneh と Durfee の手法 (BD 法) は $d \le N^{0.292}$ の条件下で秘密鍵を
多項式時間で計算することが知られている.
また, Bl\"omer と May の手法 (BM 法) では, その条件が $d \le N^{0.290}$ ではあるが,
BD 法より次元の小さい格子を使用できる.
BD 法の解析は難解であるが,Herrmann と May は, 彼らの手法 (HM 法) で提案された,
unravelled linearization technique と呼ばれる手法使ってその証明を簡略化した.
本発表では, まず unravelled linearization technique を使って BM 法の解析を簡明にし,
HM 法と BM 法を含むより一般的な格子理論攻撃を提案する.
さらに $e$ の大きさに自由度 $\alpha$ を持たせて我々の提案手法の適用条件を解析し,
その解析に有効な, パラメータを含む場合のグレブナー基底を用いた手法を提案する.
講演者：安田 雅哉 (富士通研究所)
講演タイトル：Gentry 完全準同型暗号に対する格子縮約を用いた攻撃実験報告
概要：2009年、Gentryは暗号化したままあらゆる操作が可能な完全準同型暗号（FHE）の
具体的な構成法を示した。FHEスキームは、暗号操作が限定的ではあるがFHEよりも処理
性能に優れたSHEスキームから構成される。Gentryによるスキームはイデアル格子ベースで、
他の暗号スキームに比べその安全性はあまり解明されていない。近年のChen-Nguyenによる
研究結果によると、FHEスキームの安全性を確保するためには、10,000以上の格子次元が
必要である。
それに対し、暗号操作の種類を決定する鍵パラメータの選択によっては、SHEスキームはより
低い格子次元で安全性を確保できる可能性がある。今回、SHEスキームの有用性を検証
するために、128, 256, 512格子次元の鍵パラメータに対し格子縮約アルゴリズムを利用した
攻撃実験を行った。この攻撃実験の結果から、格子縮約アルゴリズムで攻撃される可能性
のあるより高次元のSHEスキームの鍵パラメータを明らかにする。
また、本講演は、CSS 2011, ISEC 2011年11月, SCIS 2012 で発表した内容をまとめた
ものである。
講演者：長沼 健 (日立製作所)
講演タイトル：みんなで考えよう！！なぜ格子暗号は解かれてしまうのか？
概要：近年、LLLアルゴリズム、BKZアルゴリズムなどの格子簡約アルゴリズムは、
格子ベース暗号の解析をはじめ,整数計画法, 数の幾何学, 計算代数学などの
多くの分野に応用されている。
しかし、これらアルゴリズムの理論的な振る舞いに関しては、分かっていない部分も多く、
例えば、格子簡約アルゴリズムの理論値と実験結果には大きなギャップがあり、
複数の研究者（Gamma、Nguyen、Steleなど）が実験結果は理論値より良いことを
報告している。
この事は、格子暗号の安全性パラメータを決定する事を困難にし、
幾つかの格子暗号が解かれてしまう原因となっている。
※実際、幾つかの格子暗号の安全性パラメータは実験を元に決定されている。
よって、解かれにくい格子暗号方式を構成するためには、
格子簡約アルゴリズムの理論的な解析が必要不可欠である。
（例えば、LLLアルゴリズムがγ-SVPを解く確率は？などの平均値解析が必要であろう！！）
以上の状況を鑑みて、本講演では、格子簡約アルゴリズムの平均的な挙動を
解析するためのツールとして、“境界係数”を定義し、その性質を解説する。
これらは既にSCIS2012で述べた結果である。
また、SCIS2012で導入した正規Gram行列の固有値を用いて、
良い格子基底を用いた際に、枝狩り：pruningが（予想外に？）うまくいく理由
についても解説を行う。
講演者：藤堂 洋介 (神戸大学)
講演タイトル：Alwen-Peikert構成法における格子の落とし戸関数に対する評価，改良，実装
概要：近年LWE問題と呼ばれる格子問題の最悪の場合と同等に困難な問題に
注目が集まっており，その問題を利用した暗号(LWE暗号)が多数提案されている．
LWE暗号を構成する際にLWE問題の落とし戸関数が必要となる．
落とし戸関数を構成する方法の一つに2009年にAlwenらにより提案された構成法
(AP構成法)が知られている．AP構成法により生成される落とし戸関数は性能が
優れているとされ，Peikertが2009年に提案した選択暗号文攻撃に対して安全な
公開鍵暗号の構成要素の１つとして利用されている．
本発表では第一にAP構成法により構成された落とし戸関数がどの程度の性能を
持つか評価する．評価の結果，AP構成法により構成された落とし戸関数には
冗長な箇所が存在することを示す．
第二に上記で述べた冗長な箇所を事前に取り除くことで効率を改善した改良構成
法を示す．
最後にLWE暗号の実装に関する問題点と解決策に関して考察を与える．LWE
暗号の性能を正確に把握するためには，安全性が担保できかつ復号誤り確率が
低いパラメータを設定する必要がある．本発表では上記の課題を解決したパラメータ
に対して実行速度の評価を与える．
また，本発表は，ISEC 2011年11月で発表した内容をまとめたものである．
講演者：青野 良範 (情報通信機構)
講演タイトル：Solving Learning with Errors via Lattice Vector Enumeration Using Extreme
概要：本発表では，様々な暗号方式の安全性の根拠として用いられている LWE
(Learning With Errors) 問題に対する攻撃を提案する．
この攻撃は CT-RSA 2011 において Lindner と Peikert が提案したリスト復号攻撃の
改良である．攻撃の概要は
(i) LWEのエラーベクトルを短いベクトルとして含む格子を格子基底縮小アルゴリズムを
用いて構成し，
(ii)その格子の中の短いベクトルをENUMアルゴリズムを用いて全数探索を行う．
全数探索をする際、Eurocrypt 2010においてGama，Nguyen，Regevが提案した
Extreme pruningの手法を使う．特に，pruning functionを上下から設定することで、
より効率的に探索を行うことができる．
講演者：Mehdi Tibouchi (NTT)
講演タイトル：Fully Homomorphic Encryption Based on the LWE Assumption
概要：A fully homomorphic encryption scheme is one that allows public
computation of any efficient function on ciphertexts. The problem of
constructing such a scheme was proposed as far back as 1978 by Rivest,
Adleman and Dertouzos, but the first solution, due to Gentry, only came
in 2009 and used lattices. The security of Gentry's scheme was eventually
shown to be based on the worst-case hardness of bounded distance decoding
in ideal lattices, as well as an auxiliary hardness assumption regarding
certain subset-sum problems.
In this talk, we will present a somewhat simpler construction of fully
homomorphic encryption due to Brakerski and Vaikuntanathan (FOCS 2011),
and based on Regev's Learning With Errors problem (as hard as worst-case
problems for arbitrary lattices). This LWE-based scheme also does away
with Gentry's “squashing” step, which removes the dependency on
subset-sum assumptions.
講演者：草川 恵太 (NTT)
講演タイトル：A Survey on LWE-based Encryption Schemes
概要: 2005年、Regevは最悪時の格子問題から平均時のLWE問題への量子帰着を
示し、LWE問題を基にして公開鍵暗号方式を構成した。以来、LWE問題に基づいて、
CPA安全な公開鍵暗号、CCA安全な公開鍵暗号、IDベース暗号が構成されている。
2011年には、完全準同型暗号、暗号化に用いたベクトルと復号に用いるベクトル
が曖昧に一致するなら復号を許すFuzzy IDベース暗号、暗号化に用いたベクトル
と復号に用いるベクトルの内積が0ならば復号を許す内積暗号などが、LWE仮定か
ら構成されている。
本講演ではGentry, Peikert, Vaikunatanathanによる公開鍵暗号方式、Agrawal,
Boneh, BoyenによるIDベース暗号方式、Agrawal, Freeman, Vaikuntanathanによ
る内積暗号を紹介する。また、Agrawalらの内積暗号を応用に用いる際の注意を
述べる。
【発起人】草川 恵太 (NTT)
【実行委員会】國廣 昇 (東京大学) 実行委員長
須賀 祐治 (IIJ)
草川 恵太 (NTT)
伊豆 哲也 (富士通研究所)