Asiacrypt2007

第2研究室 > 学会/セミナー報告 > Asiacrypt2007
【会議名】Asiacrypt2007
【日程】2007年12月2日(日)〜12月6日(木)
【場所】クラウンプラザホテル リバーサイド クチン(マレーシア・サラワク州・クチン市)

参加者:173人(主催者発表) 


以下 橋本研究員による報告

-----------------------------------------------------------------------------
A Kilobit Special Number Field Sieve Factorization, 
K. Aoki (NTT), J. Franke, T. Kleinjung  (Univ. Bonn, Dep. Math.),
A. K. Lenstra (EPFL & Bell Lab.), D. A. Osvik (EPFL),
1024bit以上のメルセンヌ数を素因数分解するための特殊数体篩法の改良を行った。
Matrix step や Enhance sieving step にもっと改良の余地があるとのこと。
-----------------------------------------------------------------------------  
When e-th Roots Become Easier Than Factoring, 
A. Joux (DGA and Univ. Versailles), D. Naccache (Ecole normale superieure),
E. Thome (INRIA Lorraine, LORIA),
RSAを解読すること(e-th rootを求めること)が、素因数分解を行うことよりも、
理論的には簡単であることを証明した。
ただし、これは非常に大きい数に対しての話であり、現実的な範囲で本当に易しく
なるかは別の話であるとのこと。
Q.A. 証明中で用いた多項式のとり方に関する、技術的な質疑。
--------------------------------------------------------------------------------  
Faster Addition and Doubling on Elliptic Curves, 
D. J. Bernstein (Univ. Illinois), T. Lange (Tech. Univ. Eindhoven), 
楕円曲線の演算を、Edwards 曲線を用いて、効率的にした。
実際に、Montgomeryの方法よりも速くなるとのこと。
------------------------------------------------------------------------------
A Non-Interactive Shuffle with Pairing Based Verifiability, 
J. Groth (Univ. College London), S. Lu (UCLA, Math Dep.),
Shuffle の正しさに対する、効率的な一方向零知識証明を、初めて構成できた。
ペアリングを利用している。
-----------------------------------------------------------------------------
On Privacy Models for RFID, 
S. Vaudenay (EPFL),
個人認証方式の形式的なモデルを、公開鍵暗号系を基にしたnarrow-strong forward privacy
や、ランダムオラクルを基にしたnarrow-destructive privacyなどを用いて構成した。
Q. 特殊なケースではどう構成するのか?
A. Corruptionがある場合と、ない場合とで分けて考える必要がある。 
-----------------------------------------------------------------------------------
Obtaining Universally Composable Security: Towards the Bare Bones of Trust,
R. Canetti (IBM T.J. Watson Research Center),
Universally Composable secureなプロトコルを構成するための、set-up assumtion model 
の個数の比較を行い、authenticated communicationを与えるset-up model についての
考察が行われた。
common reference strong をどう拡張するかが問題であるとのこと。 
------------------------------------------------------------------------------------
A Simple Variant of the Merkle-Damgard Scheme with a Permutation, 
S. Hirose (Univ. Fukui), J. H. Park, A. Yun (ETRI Network & Commun. Security),
Merkle-Damgard 方式に基づいた新たなハッシュ関数の構成を行った。
そして、simple MAC 構成法との安全性の比較が行われた。
Q. 誕生日問題以外に前提となる仮定はあるか?
A. ないが、実用性は確かだ。
------------------------------------------------------------------------------
Seven-Property-Preserving Iterated Hashing: ROX, 
E. Andreeva, G. Neven (Katholieke Univ. Leuven),
T. Shrimpton (Portland State Univ. and Univ. Lugano),
B. Preneel (Katholieke Univ. Leuven),
ハッシュ関数に関する7つのsecurity notion を全てみたす新たな Random-Oracle
XORとよばれる方式を構成した。
Q. 既存の方式の中で、aSec とaPre をみたすものはなかったのか?
A. 自分が知る限りでは、これが最初だと思う。  
-----------------------------------------------------------------------------------
How to Build a Hash Function from Any Collision-resistant Function,
T. Ristenpart (Univ. of California),
T. Shrimpton (Portland State Univ. and Univ. of Lugano),
provably collision-resistantな関数からどのようにハッシュ関数を作るか、
という話。ひとつの方法として、Mix-Compress-Mix構成法が紹介された。
効率的な構成法や、もともとの関数のよい性質を保存するやり方があるか
が問題であるとのこと。  
---------------------------------------------------------------------------------
Fully Anonymous Group Signatures without Random Oracles,
J. Groth (Univ. College London),
双線形群を用いたgroup signature の新たな方式の構成が行われた。
この方式は、fully anonymousで、効率的である、という特徴をもつとのこと。
Q. key attack はできるか?
A. よくわからない。  
-----------------------------------------------------------------------------------
Group Encryption,
A. Kiayias (Univ. Connecticut), Y. Tsiounis (BestQuotes),
M. Yung (Google Inc. and Columbia Univ.),
group encryption に関する新たな暗号プリミティブを与える。
きちんと構成を行えば、CCA2に対しても安全であるとのこと。
どんな活用法があるか、もっと効率的にできるか、が問題であるとのこと。
------------------------------------------------------------------------------------
Identity-Based Broadcast Encryption with Constant Size Ciphertexts and Private Keys,
C. Delerablee (Orange Labs), 
一定サイズの暗号文と秘密鍵をもつidentity-based broadcast encryption scheme を
初めて構成した。
もっと安全性が強く保証されるような構成ができるかが問題であるとのこと。
------------------------------------------------------------------------------------
Boosting Merkle-Damgard Hashing for Message Authentication,
K. Yasuda (NTT), 
既存のMerkle-Damgard方式よりも速いメッセージ認証方式を構成した。
pseudo-random functionを用いているらしい。
double key version の安全性の評価も行われている。  
-----------------------------------------------------------------------------------
On Efficient Message Authentication Via Block Cipher Design Techniques,
G. Jakimoski and K. P. Subbalakshmi (Stevens Institute of Technology),
block 暗号のblockを作るときに、非線形置換を用いる。
こうすると、XOR universal ハッシュ関数が、max. differential probability 
に近い安全性をもつように構成できるとのこと。
Q.A. マイク故障で聴き取れず。  
-------------------------------------------------------------------------------------
Symmetric Key Cryptography on Modern Graphics Hardware,
J. Goodman and J. Yang (Advanced Micro Devices, Inc.),
Blue Ray や HD-DVD に使われているGPUに対して、AESやDESのCPUとの動作速度
の比較が行われた。
Scatter やDoulbe precisionなどのソフトウェアに活用したい、とのこと。
-------------------------------------------------------------------------------------
Blind Identity-Based Encryption and Simulatable Oblivious Transfer,
M. Green and S. Hohenberger (The Johns Hopkins Univ.),
blind Identity-based Encryption の定式化を行い、その実用方式に
ついての考察が行われた。
キーワード検索にも用いれそうだ、とのこと。  
-------------------------------------------------------------------------------------
Multi-Party Indirect Indexing and Applications,
M. Franklin, M. Gondree and P. Mohassel (Dept. of Computer Science, Univ.y of California, Davis),
Poly-log blow-upを用いたRAM machine によるNaor-Nissim のmulti-party computing 方式
の新たな拡張を行った。
constant round mOT protocol をどう拡張するかが問題だ、とのこと。  
--------------------------------------------------------------------------------------
Two-Party Computing with Encrypted Data,
S. G. Choi, A. Elbaz (Comp. Sci. Dep., Columbia Univ.),
A. Juels (RSA Lab.), T. Malkin (Comp. Sci. Dep., Columbia Univ.),
M. Yung (Google Inc. and Columbia Univ.),
Two party 間のonline secure computation の新たなモデルを考える。
ElGammal 型の暗号方式を用いているようだ。
offline/online model を作ったとのこと。
---------------------------------------------------------------------------------------- 
Known-Key Distinguishers for Some Block Ciphers,
L. R. Knudsen (Technical Univ. of Denmark),
V. Rijmen (Graz Univ. of Technology), 
いくつかのblock cipher に対して、known-key attack への耐性を調べた。
AESや7-round Feistel cipherに対する議論も行われた。
(Q.A. スライド中の表現についての確認)
-------------------------------------------------------------------------------------
Generic Attacks on Unbalanced Feistel Schemes with Expanding Functions,
J. Patarin (Univ. Versailles), V. Nachef (Univ. Cergy-Pontoise),
C. Berbain (France Telecom Research and Developpement),
Unbalanced Feistel scheme に対するnovel Known Plaintext Attackと
Non-addaptive Chosen Plaintext Attack として、Two、SQUARE, R1〜R4を提案し、
これらの攻撃に対抗できるような改良を行った。
Q. 実験の中で、方法によりパラメータが異なるがどう決めたのか?
A. 体の構造によっては、non-sense になるパラメータがある。
なので、選び方は難しいが、とりあえず、このパラメータで実験した。
--------------------------------------------------------------------------------------
On Tweaking Luby-Rackoff Ciphers,
D. Goldenberg (College of William and Mary), S. Hohenberger (Johns Hopkins Univ.),
M. Liskov, E. C. Schwartz, H. Seyalioglu (College of William and Mary),
Tweakable blockcipher が直接Luby-Rackoff cipherから作られ、いくつかの場合に、
それらが既存の構成法よりも効率的であることを示した。
---------------------------------------------------------------------------------
Secure Protocols with Asymmetric Trust,
I. Damgard (Aarhus Univ.), Y. Desmedt (Univ. College London),
M. Fitzi (ETH Zurich), J. B. Nielsen (Aarhus Univ.), 
multi-party protocolのstandard general-adversary modelに対して、
既存のものよりも一般的なasymmetric-trust model を導入した。
そして、broadcastに対する非自明な上限・下限を与えた。
また、asymmetric trustを表現するフレームワークを与えた。
もっと、効率的なやり方がないかが問題。  
---------------------------------------------------------------------------------
Simple and Efficient Perfectly-Secure Asynchronous MPC,
Z. Beerliova-Trubiniova and M. Hirt (ETH Zurich),
安全なmulti-party computationとして、aymnchronous MPC protocolを導入した。
少ないoptimal playerに対してはperfect secureであることが示されている。  
----------------------------------------------------------------------------------
Efficient Byzantine Agreement with Faulty Minority,
Z. Beerliova-Trubiniova, M. Hirt and M. Riser (ETH Zurich)
悪意のあるplayer が過半数でないときに、情報理論的な安全性をもつ
Byzantine Agreement protocol を構成した。
やはり、効率性が問題であるとのこと。
Q.A. Real broadcastに関する技術的なこと。
-----------------------------------------------------------------------------------
Information-theoretic Security without an Honest Majority,
A. Broadbent and A. Tapp (Univ. de Montreal),
正直者が多数派であることを仮定しなくとも安全な6つのmultiparty protocol を与えた。
6つとは、veto, vote, anonymous bit transmission, collision detection, notification, 
anonymous message transmission のこと。
正直でない人の数に依らない方式をどう作るかが問題。
------------------------------------------------------------------------------------
Black-Box Extension Fields and the Inexistence of Field-Homomorphic One-Way Permutations,
U. Maurer and D. Raub (ETH Zurich),
有限体に関するblack-box field extraction problem の一般化を考え、小さな指標をもつ
有限体に対して、このrepresentation problem とrelated problem に対する、効率的な
アルゴリズムを作った。
Q.A. 多項式時間のFp-EX traction に関する技術的な質疑。  
--------------------------------------------------------------------------------------
Concurrent Statistical Zero-Knowledge Arguments for NP from One Way Functions,
V. Goyal, R. Moriarty, R. Ostrovsky and A. Sahai (UCLA),
任意のhonest verifier statistica zero-knowledge argumentから、concurrent satistical 
zero-knowledge argumentが作れることを証明している。さらに、任意の一方向関数から、
NPな任意の言語に関するconcurrent satistical zero-knowledge argument system を構成した。
Q. 破られているものはあるか?
A. あったと思うが、よくわからない。  
-------------------------------------------------------------------------------------
Anonymous Quantum Communication,
G. Brassard, A. Broadbent (Univ. Montreal),
J. Fitzsimons (Univ. of Oxford), S. Gambs, A. Tapp  (Univ. Montreal), 
active adversaryに対して理論的に安全なquantum stateのanonymous transmission に関する最初の
プロトコルを構成した。
------------------------------------------------------------------------------------
Authenticated Key Exchange and Key Encapsulation in the Standard Model,
T. Okamoto (NTT), 
Diffie-Hellman 仮定やtarget collision resistant hash function やpseudo-random function 
の仮定のもとで、authenticated key exchange やkey encapsulation のような暗号プリミティブ
のいくつかの型を実現する新たなパラダイムを導入した。
random oracle なしの実用的なtwo-pass PKI-AKEを構成したのは初めてであるとのこと。
----------------------------------------------------------------------------------------
Miniature CCA2 PK Encryption: Tight Security Without Redundancy,
X. Boyen (Voltage Inc.)
ElGammal と同じくらいコンパクトだが、CCA2に対して安全な公開鍵暗号系を構成した。
Kurosawa-Matsuo(2004)の方法とも関連しているようだ。  
--------------------------------------------------------------------------------------
Bounded CCA2-Secure Encryption,
R. Cramer (CWI & Leiden Univ.), G. Hanaoka (AIST),
D. Hofheinz (CWI), H. Imai (AIST),
E. Kiltz (CWI), R. Pass (Cornell Univ.),
A. Shelat (U. Virginia), V. Vaikuntanathan (MIT), 
Bounded CCA2-securityをもつ暗号方式について。
non-malleabilityとindistinguishabilityが同値でないことも証明された。  
--------------------------------------------------------------------------------------
Relations Among Notions of Non-Malleability for Encryption,
R. Pass (Cornell Univ.), A. Shelat (U. Virginia), V. Vaikuntanathan (MIT)
pragmatic indistinguishability based approach やsemantical simulation-based approach
の特徴づけを与え、それらのrobustnessに対する考察も行った。
Q. CPC1 security modelは何かあるか?
A. 知りません。  
----------------------------------------------------------------------------------------
Cryptanalysis of the Tiger Hash Function,
F. Mendel (IAIK), V. Rijmen (Graz Univ. of Technology)
ある程度高い複雑さをもつfull Tiger hash function に対する、pseudo-near-collision
を示した。security marginは期待していたほどではなかったとのこと。  
---------------------------------------------------------------------------------------
Cryptanalysis of Grindahl,   (最優秀)
T. Peyrin (France Telecom R&D, AIST, Univ. Versailles)
Grindahlとよばれるハッシュ関数に対する、新たな暗号解析の方法を提唱した。
256-bitのGrindahlがcollision resistantでないことを示したとのこと。
Q. good division hash functionを作れるか?
A. 多分できる。  
---------------------------------------------------------------------------------------
A Key Recovery Attack on Edon80,
M. Hell and T. Johansson (Lund Univ.)
eSTREAM projectで提唱されたストリーム暗号Edon80の暗号解析を行った。
とくに、key recovery attackについて詳しく解説されたようだ。
Q.A. memory complexityに関する技術的なやりとり。
--------------------------------------------------------------------------------------

以上

ページトップへ戻る

Copyright © 2006 Institute of Systems & Information Technologies/KYUSHU. All Rights Reserved.