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 at 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 2013, IWSEC 2012

See Bibliography on Lattice-based Cryptosystems and Bibliography on Code-based Cryptosystems.

See DBLP: Keita Xagawa, Google Scholar: Keita Xagawa, and MAS: Keita Xagawa

Publications

Refereed International Conference Papers

1. Practical and Post-Quantum Authenticated Key Exchange from One-Way Secure Key Encapsulation Mechanism

   Atsushi Fujioka, Koutarou Suzuki, Keita Xagawa, and Kazuki Yoneyama

   ASIA CCS 2013, pp.xxx-xxx (2013/5)

   To appear

2. Improved (Hierarchical) Inner-Product Encryption from Lattices

   Keita Xagawa

   PKC 2013, LNCS 7778, pp.235-252 (2013/2-3)

3. Verifiably Encrypted Signatures with Short Keys based on the Decisional Linear Problem and Obfuscation for Encrypted VES

   Ryo Nishimaki and Keita Xagawa

   PKC 2013, LNCS 7778, pp.405-422 (2013/2-3)

4. Applicability of OR-Proof Techniques to Hierarchical Identity-Based Identification

   Atsushi Fujioka, Taiichi Saito, and Keita Xagawa

   CANS 2012, LNCS 7712, pp.169-184 (2012/12)

5. Security Enhancement of Identity-Based Identification with Reversibility

   Atsushi Fujioka, Taiichi Saito, and Keita Xagawa

   ICICS 2012, LNCS 7618, pp.202-213 (2012/10)

6. Secure Hierarchical Identity-Based Identification without Random Oracles

   Atsushi Fujioka, Taiichi Saito, and Keita Xagawa

   ISC 2012, LNCS 7483, pp.258-273 (2012/09)

7. Security Enhancements by OR-Proof in Identity-Based Identification

   Atsushi Fujioka, Taiichi Saito, and Keita Xagawa

   ACNS 2012, LNCS 7341, pp.135-152 (2012/06)

8. Strongly Secure Authenticated Key Exchange from Factoring, Codes, and Lattices

   Atsushi Fujioka, Koutarou Suzuki, Keita Xagawa, and Kazuki Yoneyama

   PKC 2012, LNCS 7293, pp.467-484 (2012/05)

   See also Cryptology ePrint Archive: 2012/211

9. 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.

10. 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.

11. 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]

12. 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.

    [Draft: 2008KTX-SID.pdf] [Slides:20081210_ASIA_SID.pdf]

13. 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]

14. 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.

    [Draft: 2007KTX.pdf] [Slides:20070418_PKC_MultiBit.pdf]

Unrefereed International/Domestic Workshops/Symposiums/Preprints

1. Message Authentication Codes Secure against Additive Related-Key Attacks

   加法的関連鍵攻撃に対して安全なメッセージ認証符号

   Keita Xagawa

   SCIS 2013 1B1-2 (2013/01), Cryptology ePrint Archive: 2013/111

2. 可逆なタンパー関数に耐性を持つ暗号学的回路

   Eiichiro Fujisaki and Keita Xagawa

   SCIS 2013 2B2-3 (2013/01)

3. An Attack on Key-Exchange Protocols Proposed by Accardi et al.

   Accardiらの鍵共有プロトコルに対する攻撃

   Keita Xagawa

   SCIS 2012 2A2-2 (2012/01-02)

4. 格子問題、符号理論、および素因数分解問題に基づく強い認証鍵交換: KEMからの一般構成

   Kazuki Yoneyama, Keita Xagawa, Koutarou Suzuki, and Atsushi Fujioka

   SCIS 2011 3F4-1 (2011/01)

   This work is superseded by “Strongly Secure Authenticated Key Exchange from Factoring, Codes, and Lattices” with Fujioka, Suzuki, and Yoneyama in PKC 2012.

5. Indistinguishability against Related-Key Attacks in the Public-Key Settigns and Bidrectional Proxy Re-Encryption

   関連鍵攻撃に対する識別不可能性と双方向代理人再暗号化

   Keita Xagawa

   SCIS 2011 2A2-5 (2011/01)

6. 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]

7. 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)

8. 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]

9. 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]

10. 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]

11. 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.

12. 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]

13. 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]

14. 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]

15. 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]

16. 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]

17. 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 erros...

  [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

1. A Survey on LWE-based Encryption Schemes

   Keita Xagawa

   Lattice Crypto Day 2012 Japan (LCD2012J) (2012/03)

2. Brief History of Lattice Crypto World

   Keita Xagawa

   Lattice Crypto Day 2012 Japan (LCD2012J) (2012/03)

3. Lattice-based Hash Functions

   格子に基づく安全なハッシュ関数の構成

   Keita Xagawa

   Workshop on interaction between CRyptography, Information Security and MATHematics (CRISMATH) 暗号及び情報セキュリティと数学の相関ワークショップ (2010/02)

   [Slides in Japanese: 20100224.pdf]

4. Efficient Public Key Encryption Based on Ideal Lattices

   イデアル格子で作る公開鍵暗号方式、他

   Keita Xagawa

   4th Secure Construction of PKC and Its Applications Workshop 第4回公開鍵暗号の安全な構成とその応用ワークショップ (2010/02)

   [Slides in Japanese: 20100223_Workshop.pdf]

5. A Survey on Lattice-Based Hash Functions

   Keita Xagawa

   New Horizons in Computing - Mini Meeting (Cryptography) (2007/03)

   [Slides in Japanese: 20070303_NHC.pdf]