Keita Xagawa (草川 恵太)
About
- “Xagawa” is pronounced as Kusagawa, neither Zagawa nor Shagawa :)
- I received my Ph.D. from Tokyo Institute of Technology in March 2010. (adviser: Keisuke Tanaka).
- I am a researcher in NTT.
- Research interests: Lattice-based cryptography, public-key cryptography, lattice problems, and coding problems.
- I was/am/will be on the following program committees: IWSEC 2012
See Bibliography on Lattice-based Cryptosystems and Bibliography on Code-based Cryptosystems.
Publications
Refereed International Conference Papers
-
- Security Enhancements by OR-Proof in Identity-Based Identification
- Atsushi Fujioka, Taiichi Saito, and Keita Xagawa
- ACNS 2012, LNCS XXXX, pp.xxx-xxx (2012/06)
-
- Strongly Secure Authenticated Key Exchange from Factoring, Codes, and Lattices
- Atsushi Fujioka, Koutarou Suzuki, Keita Xagawa, and Kazuki Yoneyama
- PKC 2012, LNCS XXXX, pp.xxx-xxx (2012/05)
- See also Cryptology ePrint Archive: 2012/211
-
- Security of Encryption Schemes in Weakened Random Oracle Models (Extended Abstract)
- Akinori Kawachi, Akira Numayama, Keisuke Tanaka, and Keita Xagawa
- PKC 2010, LNCS 6056, pp.403-419 (2010/05)
- See Cryptology ePrint Archive: 2010/122 for the full version.
-
- Efficient Public Key Encryption Based on Ideal Lattices (Extended Abstract)
- Damien Stehlé, Ron Steinfeld, Keisuke Tanaka, and Keita Xagawa
- ASIACRYPT 2009, LNCS 5912, pp.617-635 (2009/12)
- See Cryptology ePrint Archive: 2009/285 for the draft of the full version.
- The potential high efficiency of public-key encryption based on structured lattices was first indicated by the NTRU cryptosystem, which was proposed about 10 years ago. Unfortunately, the security of NTRU is only heuristic. Thus, it remained an important research challenge to construct an efficient encryption scheme based on structured lattices which admits a proof of security relative to a well established cryptographic assumption. We make progress in addressing the above challenge.We show how to construct a CPA-secure public-key encryption scheme with security provably based on the worst case hardness of the approximate Shortest Vector Problem in structured ideal lattices. Under the assumption that the latter is exponentially hard to solve even with a quantum computer, our scheme resists any subexponential attack and offers (quasi-)optimal asymptotic performance: if n is the security parameter, both keys are of bit-length \widetilde{O}(n) and the amortized costs of both encryption and decryption are \widetilde{O}(1) per message bit. Our construction adapts the trapdoor one-way function of Gentry, Peikert and Vaikuntanathan (STOC 2008), based on the Learning With Errors problem, to structured lattices. Our main technical tools are an adaptation of Ajtai's trapdoor key generation algorithm (ICALP 1999) to structured ideal lattices, and a reinterpretation of Regev's quantum reduction between the Closest Vector Problem and sampling short lattice vectors. We think these techniques are very likely to find further applications in the future.
-
- Zero-Knowledge Protocols for NTRU: Application to Identification and Proof of Plaintext Knowledge
- Keita Xagawa and Keisuke Tanaka
- ProvSec 2009, LNCS 5848, pp.198-213 (2009/11)
- We propose zero-knowledge and proof-of-knowledge protocols for NTRU. One is for the relation on secret-key knowledge and the other for that on plaintext knowledge. They are the first non-trivial constructions of these protocols for NTRU. Additionally, the former directly yields an identification scheme based on NTRU. See also my Ph.D Thesis.
- [Draft: 2009TX-NTRUZK.pdf]
-
- Concurrently Secure Identification Schemes Based on the Worst-Case Hardness of Lattice Problems
- Akinori Kawachi, Keisuke Tanaka, and Keita Xagawa
- ASIACRYPT 2008, LNCS 5350, pp.372-389 (2008/12)
- Errata: in the introduction, I wrote that we can apply the ORing technique to the Lyubashevsky identification scheme. However, since there is no simulator in Lyubashevsky's proof, we cannot take OR the statements of Lyubashevsky's relations. See also my Ph.D Thesis.
- In this paper, we show that two variants of Stern’s identification scheme [IEEE Transaction on Information Theory '96] are provably secure against concurrent attack under the assumptions on the worst-case hardness of lattice problems. These assumptions are weaker than those for the previous lattice-based identification schemes of Micciancio and Vadhan [CRYPTO '03] and of Lyubashevsky [PKC '08]. We also construct efficient ad hoc anonymous identification schemes based on the lattice problems by modifying the variants.
- [Draft: 2008KTX-SID.pdf] [Slides:20081210_ASIA_SID.pdf]
-
- A Compact Signature Scheme with Ideal Lattice (Extended Abstract) (1-page)
- Keita Xagawa and Keisuke Tanaka
- AAAC 2008
- This work is superseded by “Efficient Public Key Encryption Based on Ideal Lattices” with Stehlé, Steinfeld, and Tanaka in ASIACRYPT 2009.
- [2008AAAC.pdf] [Slides:20080426_AAAC.pdf]
-
- Multi-bit Cryptosystems Based on Lattice Problems
- Akinori Kawachi, Keisuke Tanaka, and Keita Xagawa
- PKC 2007, LNCS 4450, pp.315-329 (2007/04)
- See also my master thesis.
- We propose multi-bit versions of several single-bit cryptosystems based on lattice problems, the error-free version of the Ajtai-Dwork cryptosystem by Goldreich, Goldwasser, and Halevi [CRYPTO '97], the Regev cryptosystems [JACM 2004 and STOC 2005], and the Ajtai cryptosystem [STOC 2005]. We develop a universal technique derived from a general structure behind them for constructing their multi-bit versions without increase in the size of ciphertexts. By evaluating the trade-off between decryption errors and the hardness of underlying lattice problems, it is shown that our multi-bit versions encrypt O(log n)-bit plaintexts into ciphertexts of the same length as the original ones with reasonable sacrifices of the hardness of the underlying lattice problems. Our technique also reveals an algebraic property, named pseudohomomorphism, of the lattice-based cryptosystems.
- [Draft: 2007KTX.pdf] [Slides:20070418_PKC_MultiBit.pdf]
Unrefereed International/Domestic Workshops/Symposiums
-
- Accardiらの鍵共有プロトコルに対する攻撃
- Keita Xagawa
- SCIS 2012 2A2-2 (2012/01-02)
-
- 格子問題、符号理論、および素因数分解問題に基づく強い認証鍵交換: KEMからの一般構成
- Kazuki Yoneyama, Keita Xagawa, Koutarou Suzuki, and Atsushi Fujioka
- SCIS 2011 3F4-1 (2011/01)
-
- Indistinguishability against Related-Key Attacks in the Public-Key Settigns and Bidrectional Proxy Re-Encryption
- 関連鍵攻撃に対する識別不可能性と双方向代理人再暗号化
- Keita Xagawa
- SCIS 2011 2A2-5 (2011/01)
-
- Proxy Re-Encryption based on Learning with Error
- 格子に基づく代理人再暗号化
- Keita Xagawa and Keisuke Tanaka
- ASIACRYPT 2009 Rump Session (2009/12), SCIS 2010 2A3-3 (2010/01), LA Symposium 2009 Winter 7 (2010/02)
- See also my Ph.D Thesis.
- [Slides:20100120_SCIS_PRE.pdf]
-
- Pseudorandomness of the Legendre Sequences and Robust Quantum State Decoding (old title:Simultaneous Security of Quantum Hardcore Functions)
- ルジャンドル列の擬似乱数性と頑健な量子状態復号 (旧タイトル:量子ハードコア関数の同時安全性)
- Keita Xagawa and Akinori Kawachi
- LA Symposium 2009 Summer 4 (2009/07), SCIS 2010 4B1-1 (2010/01)
-
- An IND-CCA2 Secure Encryption Scheme from an Ideal LWE Assumption
- イデアル版LWE仮定に基づくIND-CCA2安全な暗号方式
- Keita Xagawa and Keisuke Tanaka
- SCIS 2009 4A2-5 (2009/01)
- This work is superseded by “Efficient Public Key Encryption Based on Ideal Lattices” with Stehlé, Steinfeld, and Tanaka in ASIACRYPT 2009. See also my Ph.D Thesis.
- [Slides in Japanese:20090123_SCIS_IdealLWE.pdf]
-
- NFALSE: Another Ring-Based Public Key Cryptosystem with Faster Encryption
- NFALSE: 多項式環に基づくより高速な公開鍵暗号
- Keita Xagawa and Keisuke Tanaka
- SCIS 2009 3F2-5 (2009/01), LA Symposium 2008 Winter 26 (2009/02)
- [Slides in Japanese:20090122_SCIS_NFALSE.pdf]
-
- Zero-Knowledge Protocols for NTRU
- NTRU暗号に対するゼロ知識証明
- Keita Xagawa and Keisuke Tanaka
- SCIS 2009 3F2-4 (2009/01)
- This work is superseded by “Zero-Knowledge Protocols for NTRU: Application to Identification and Proof of Plaintext Knowledge” with Tanaka in ProvSec 2009. See also my Ph.D Thesis.
- [Slides in Japanese:20090122_SCIS_NTRU-ZK.pdf]
-
- RSA-OAEP is secure in the Weakened Random Oracle Models
- Akira Numayama, Keita Xagawa, Akinori Kawachi, and Keisuke Tanaka
- SCIS 2009 3D1-2 (2009/01)
- This work is superseded by “Security of Encryption Schemes in Weakened Random Oracle Models (Extended Abstract)” with Kawachi, Numayama, and Tanaka in PKC 2010.
-
- Sampling Methods Revisited: Approximation Sampling with Huge Parameters
- 近似サンプリング法の精度保証
- Akira Numayama, Keita Xagawa, Akinori Kawachi, and Keisuke Tanaka
- SCIS 2009 3D1-1 (2009/01), LA Symposium 2008 Summer 15 (2008/07)
- This work is superseded by “Security of Encryption Schemes in Weakened Random Oracle Models (Extended Abstract)” with Kawachi, Numayama, and Tanaka in PKC 2010.
- [Slides in Japanese: 20080723_LA.pdf], [Slides in Japanese: 20090122_SCIS_Dist.pdf]
-
- A Compact Signature Scheme with Ideal Lattice (Extended Abstract)
- イデアル格子問題に基づくコンパクトな署名方式
- Keita Xagawa and Keisuke Tanaka
- SCIS 2008 3D3-2 (2008/01)
- This work is superseded by “Efficient Public Key Encryption Based on Ideal Lattices” with Stehlé, Steinfeld, and Tanaka in ASIACRYPT 2009. See also my Ph.D Thesis.
- [Slides in Japanese: 20080124_SCIS_Ideal.pdf]
-
- Concurrently Secure Identification Schemes and Ad Hoc Anonymous Identification Schemes Based on the Worst-Case Hardness of Lattice Problems
- 格子問題に基づく高い安全性をもつ認証方式
- Keita Xagawa, Akinori Kawachi, and Keisuke Tanaka
- SCIS 2008 3D3-1 (2008/01), Technical Report (2007/11)
- This work is superseded by “Concurrently Secure Identification Schemes Based on the Worst-Case Hardness of Lattice Problems” in ASIACRYPT 2008. An old version appeared in LA Symposium 2007 Summer 11 (2007/07). See also my Ph.D Thesis.
- [TR: C-249.pdf], [Slides in Japanese: 20080124_SCIS_SID.pdf]
-
- Proof of Plaintext Knowledge for the Regev Cryptosystems
- Regev暗号に対する平文知識証明
- Keita Xagawa, Akinori Kawachi, and Keisuke Tanaka
- SCIS 2007 1C1-2 (2007/01), Technical Report (2007/01)
- See also my master's thesis.
- [TR: C-236.pdf] [Slides in Japanese: 20070123_SCIS_PPK.pdf]
-
- A Lattice-Based Cryptosystem and Proof of Knowledge on Its Secret Key
- 格子暗号の秘密鍵についての知識証明
- Keita Xagawa, Akinori Kawachi, and Keisuke Tanaka
- SCIS 2007 1C1-1 (2007/01), LA Symposium Winter 2006 7 (2007/02), Technical Report (2007/01)
- SCIS 2007 Award, LA/EATCS Best Presentation Award. See also my master's thesis.
- [TR: C-235.pdf] [Slides in Japanese: 20070123_SCIS_PSK.pdf]
-
- Multi-bit Cryptosystems Based on Lattice Problems
- 格子問題に基づく複数ビット公開鍵暗号方式
- Keita Xagawa, Akinori Kawachi, and Keisuke Tanaka
- SCIS 2006 2A4-4 (2006/01), LA Winter 2005 7 (2006/01)
- This work is superseded by “Multi-bit Cryptosystems Based on Lattice Problems” in PKC 2007. See also my master's thesis.
- [Slides in Japanese: 20060128_LA.pdf]
Thesis
-
- Cryptography with Lattices
- 格子暗号
- Keita Xagawa
- Ph.D Thesis, Department of Mathematical and Computing Sciences, Tokyo Institute of Technology, March 2010, supervisor: Keisuke Tanaka.
- There are several typos and
- [2010Thesis.pdf]
-
- A Study on Lattice-Based Public-Key Cryptosystems
- Keita Xagawa
- Master's Thesis, Department of Mathematical and Computing Sciences, Tokyo Institute of Technology, March 2007, supervisor: Keisuke Tanaka.
- Errata: I noted, in Section 4.1, that we cannot apply the Micciancio-Vadhan protocol~[CRYPTO 2003] to the proof of possession for a secret key in the Regev05 cryptosystem. However, using the idea of q-ary lattice, one can use the protocol to the proof of possession. I note that obtained it is weak in some sense, since a length of an extracted secret key may be longer than original one.
- [2007MT.pdf]
Talks