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 senior PQC researcher at Technology Innovation Institute (TII) (2023--present), was a senior researcher at NTT (2019--2023) and was a researcher at NTT (2010--2019).
• Research interests: Post-quantum cryptography, lattice-based cryptography, public-key cryptography, lattice problems, and coding problems.
• I was/am/will be on the following program committees: PKC 2025, SPACE 2024, ASIACRYPT 2024, ASIACRYPT 2023, PQCrypto 2023, ProvSec 2023, CT-RSA 2023, PQCrypto 2022, PKC 2022, ProvSec 2021, PQCrypto 2021, ProvSec 2020, PQCrypto 2020, PQCrytpo 2019, PQCrypto 2018, PQCrypto 2017, PQCrypto 2016, IWSEC 2013, IWSEC 2012.

See DBLP: Keita Xagawa, Google Scholar: Keita Xagawa, and ORCiD: Keita Xagawa.

Publications by Year

Journals, Conferences, and Preprints

1. [EPRINT:MorXag24] Quantum Group Actions

   Tomoyuki Morimae, Keita Xagawa

   ia.cr/2024/1578 and arXiv:2410.04777 (2024/10)

2. [EPRINT:KulXag24] Strong Existential Unforgeability and More of MPC-in-the-Head Signatures

   Mukul Kulkarni, Keita Xagawa

   ia.cr/2024/1069 (2024/07)

3. [PRA:MisXag24] Secure multiparty quantum computation protocol for quantum circuits: The exploitation of triply even quantum error-correcting codes

   Petr A. Mishchenko, Keita Xagawa

   Physical Review A, 110, 022444 (2024/08)

   See also arXiv:2206.04871 (2022/06) [ARXIV:MisXag22a]

4. [EC:Xagawa24] Signatures with Memory-Tight Security in the Quantum Random Oracle Model

   Keita Xagawa

   EUROCRYPT 2024 Part VII, LNCS 14657, pp.30-58 (2024/05)

   See also ia.cr/2023/1734 (2023/12) [EPRINT:Xagawa23b]

5. [CiC:Xagawa24] On the Efficiency of Generic, Quantum Cryptographic Constructions

   Keita Xagawa

   IACR Communications in Cryptology, 1(1), 8 (2024/04)

   See also ia.cr/2023/1142 (2023/07) [EPRINT:Xagawa23a]

6. [PKC:KosXag24] Probabilistic Hash-and-Sign with Retry in the Quantum Random Oracle Model

   Haruhisa Kosuge, Keita Xagawa

   PKC 2024 Part I, LNCS 14601, pp.259-288 (2024/04)

   See also ia.cr/2022/1359 (2022/10) [EPRINT:KosXag22]

7. [LATINCRYPT:NFNTXY23] Making the Identity-Based Diffie-Hellman Key Exchange Efficiently Revocable

   Kohei Nakagawa, Atsushi Fujioka, Akira Nagai, Junichi Tomida, Keita Xagawa, Kan Yasuda

   LATINCRYPT 2023, LNCS 14168, pp.171-191 (2023/10)

8. [TCHES:TUXITH23] Multiple-Valued Plaintext-Checking Side-Channel Attacks on Post-Quantum KEMs

   Yutaro Tanaka, Rei Ueno, Keita Xagawa, Akira Ito, Junko Takahashi, and Naofumi Homma

   IACR Transactions on Cryptographic Hardware and Embedded Systems (TCHES), 2023(3), pp.473-503 (2023/06)

   See also ia.cr/2022/940 (2022/07) [EPRINT:TUXITH22]

9. [PKC:MarXag23] Post-Quantum Anonymity of Kyber

   Varun Maram, Keita Xagawa

   PKC 2023 Part I, LNCS 13940, pp.3-35 (2023/05)

   Best paper

   See also ia.cr/2022/1696 (2022/12) [EPRINT:MarXag22]

10. [ARXIV:MisXag22b] An improvement on the versatility of secure multi-party quantum computation protocol: exploitation of triorthogonal quantum error-correcting codes

    Petr A. Mishchenko, Keita Xagawa

    arXiv:2211.00777 (2022/11)

11. [DCC:ABNXXY22] Cryptanalysis of Boyen's Attribute-Based Encryption Scheme in TCC 2013

    Shweta Agrawal, Rajarshi Biswas, Ryo Nishimaki, Keita Xagawa, Xiang Xie, and Shota Yamada

    Designs, Codes and Cryptography, 90(10), pp.2301-2318 (2022/10); First online: 24 July 2022

    Available in Springer's WebSite.

    See also ia.cr/2021/505 (2021/04) [EPRINT:ABNXXY21]

12. [EC:Xagawa22] Anonymity of NIST PQC Round-3 KEMs

    Keita Xagawa

    EUROCRYPT 2022 Part III, LNCS 13277, pp.551-581 (2022/05)

    See also ia.cr/2021/1323 (2021/10) [EPRINT:Xagawa21c]. This paper supersedes [EPRINT:Xagawa21b]

13. [TCHES:UXTITH22] Curse of Re-encryption: A Generic Power/EM Analysis on Post-Quantum KEMs

    Rei Ueno, Keita Xagawa, Yutaro Tanaka, Akira Ito, Junko Takahashi, and Naofumi Homma

    IACR Transactions on Cryptographic Hardware and Embedded Systems (TCHES), 2022(1), pp.296-322 (2021/11)

    See also ia.cr/2021/849 (2021/06) [EPRINT:UXTITH21]

    Errata: See ia.cr/2022/724 [EPRINT:SHRWS22] for our mistake on KR-PCA against HQC. (2022/07/15)

14. [AC:XIUTH21] Fault-Injection Attacks against NIST's Post-Quantum Cryptography Round 3 KEM Candidates

    Keita Xagawa, Akira Ito, Rei Ueno, Junko Takahashi, and Naofumi Homma

    ASIACRYPT 2021 Part II, LNCS 13091, pp.33-61 (2021/12)

    See also ia.cr/2021/840 [EPRINT:XIUTH21]

    Errata: See ia.cr/2022/724 [EPRINT:SHRWS22] for our mistake on KR-PCA against HQC. (2022/07/15)

15. [SAC:Xagawa21] The Boneh-Katz Transformation, Revisited: Pseudorandom/Obliviously-Samplable PKE from Lattices and Codes and Its Application

    Keita Xagawa

    SAC 2021, LNCS 13203, pp.47-67 (2021/09-10)

    See also ia.cr/2021/740 [EPRINT:Xagawa21a]

16. [EPRINT:Xagawa21b] NTRU leads to Anonymous, Robust Public-Key Encryption

    Keita Xagawa

    ia.cr/2021/741 (2021/06)

    This work is superseded by [EC:Xagawa22]

17. [AC:YKXT20] Non-Committing Encryption with Constant Ciphertext Expansion from Standard Assumptions

    Yusuke Yoshida, Fuyuki Kitagawa, Keita Xagawa, and Keisuke Tanaka

    ASIACRYPT 2020 Part II, LNCS 12492, pp.36-65 (2020/12)

    See also ia.cr/2020/1210

18. [TCS:HSTX20] Quantum algorithm for the multicollision problem

    Akinori Hosoyamada, Yu Sasaki, Seiichiro Tani, and Keita Xagawa

    Theoretical Computer Science, 842, pp.100-117 (2020/11)

    See also ia.cr/2018/1122 and arXiv:1811.08097

19. [ASIACCS:CPSWX20] ModFalcon: Compact Signatures Based On Module-NTRU Lattices

    Chitchanok Chuengsatiansup, Thomas Prest, Damien Stehlé, Alexandre Wallet, and Keita Xagawa

    ACM AsiaCCS 2020, pp.853-866 (2020/10)

    See also ia.cr/2019/1456

20. [RSA:FerXag20] Post-Quantum Provably-Secure Authentication and MAC from Mersenne Primes

    Houda Ferradi and Keita Xagawa

    CT-RSA 2020, LNCS 12006, pp.469-495 (2020/02)

    See also ia.cr/2019/409

21. [DCC:ABDGLTX20] Cryptanalysis of a rank-based signature with short public keys

    Nicolas Aragon, Olivier Blazy, Jean-Christophe Deneuville, Philippe Gaborit, Terry Shue Chien Lau, Chik How Tan, and Keita Xagawa

    Designs, Codes and Cryptography, 88(4), pp.643-653 (2020/04); First online: 16 December 2019

    Available in Springer's WebSite. The results of Song, Huang, Mu, and Wu got accepted on Dec. 21st 2018 at PKC'19, made available as ePrint 2019/053 on Jan. 25th 2019, a cryptanalysis implementation was publicly released on Jan. 30th 2019 by Deneuville et al. (github:deneuville/cryptanalysisSHMW), Lau and Tan (arXiv:1902.00241v1), then Xagawa (ia.cr/2019/120) published independently a description of the attack. The paper has been withdrawn since, both from ePrint and PKC'19, around Feb. 26th 2019. This work merges the implementation of Aragon et al., and the works of Lau and Tan, and Xagawa.

22. [AC:HhaXagYam19] Quantum Random Oracle Model with Auxiliary Input

    Minki Hhan, Keita Xagawa, and Takashi Yamakawa

    Asiacrypt 2019 Part I, LNCS 11921, pp.584-614 (2019/12)

    See also ia.cr/2019/1093

23. [PQCRYPTO:HSTX19] Improved Quantum Multicollision-Finding Algorithm

    Akinori Hosoyamada, Yu Sasaki, Seiichiro Tani, and Keita Xagawa

    PQCrypto 2019, LNCS 11505, pp.350-367 (2019/05)

    See [TCS:HSTX20]. See also ia.cr/2018/1122 and arXiv:1811.08097

24. [PQCRYPTO:XagYam19] (Tightly) QCCA-Secure Key-Encapsulation Mechanism in the Quantum Random Oracle Model

    Keita Xagawa and Takashi Yamakawa

    PQCrypto 2019, LNCS 11505, pp.249-268 (2019/05)

    See also ia.cr/2018/838

25. [EC:SaiXagYam18] Tightly-Secure Key-Encapsulation Mechanism in the Quantum Random Oracle Model

    Tsunekazu Saito, Keita Xagawa, and Takashi Yamakawa

    EUROCRYPT 2018 Part III, LNCS 10822, pp.520-551 (2018/04)

    See also ia.cr/2017/1005

26. [RSA:BooTibXag18] Cryptanalysis of Compact-LWE

    Jonathan Bootle, Mehdi Tibouchi and Keita Xagawa

    CT-RSA 2018, LNCS 10808, pp.80-97 (2018/04)

    See also ia.cr/2017/742

27. [PQCRYPTO:Xagawa18] Practical Cryptanalysis of a Public-key Encryption Scheme Based on Non-linear Indeterminate Equations at SAC 2017

    Keita Xagawa

    PQCrypto 2018, LNCS 10786, pp.142-161 (2018/04)

    See also ia.cr/2017/1224

    Note: I have reported the attacks in this paper to the original authros, Akiyama et al. Their submission "Giophantus" in NIST PQC Round~1 and their revised paper ia.cr/2017/1241 reflect the attacks in this paper.

28. [IJIS:SEXY18] Accumulable Optimistic Fair Exchange from Verifiably Encrypted Homomorphic Signatures

    Jae Hong Seo, Keita Emura, Keita Xagawa, and Kazuki Yoneyama

    International Journal of Information Security, 17(2), pp.193-220 (2018/04); First Online: 22 March 2017

    Available at https://dx.doi.org/10.1007/s10207-017-0367-z.

29. [EPRINT:Xagawa18] Practical Attack on RaCoSS-R

    Keita Xagawa

    ia.cr/2018/831

30. [AC:HosSasXag17] Quantum Multicollision-Finding Algorithm

    Akinori Hosoyamada, Yu Sasaki, and Keita Xagawa

    ASIACRYPT 2017 Part II, LNCS 10625, pp.179-210 (2017/12)

    See also [TCS:HSTX20]. See also ia.cr/2017/864

31. [SIGMOD:HorKikXag17] Cryptanalysis of Comparable Encryption in SIGMOD'16

    Caleb Horst, Ryo Kikuchi, and Keita Xagawa

    SIGMOD 2017, pp.1069-1084 (2017/05)

    Summary: We cryptanalyze cryptosystems proposed by Karras et al. (SIGMOD'16).

32. [AC:FujXag16] Public-Key Cryptosystems Resilient to Continuous Tampering and Leakage of Arbitrary Functions

    Eiichiro Fujisaki and Keita Xagawa

    ASIACRYPT 2016 Part I, LNCS 10031, pp.908-938 (2016/12)

33. [EPRINT:Xagawa16] Groth-Sahai Proofs Revisited Again: A Bug in ``Optimized'' Randomization

    Keita Xagawa

    ia.cr/2016/476

34. [DCC:NisXag15] Verifiably encrypted signatures with short keys based on the decisional linear problem and obfuscation for encrypted VES

    Ryo Nishimaki and Keita Xagawa

    Designs, Codes, and Crypography, 77(1), pp.61-98 (2015/10); First online: 24 June 2014

35. [DCC:FSXY15] Strongly secure authenticated key exchange from factoring, codes, and lattices

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

    Designs, Codes and Cryptography, 76(3), pp.469-504 (2015/09); First online: 23 April 2014

    The journal version of [PKC:FSXY12]. See also ia.cr/2012/211

36. [LATINCRYPT:FujXag15] Efficient RKA-Secure KEM and IBE Schemes Against Invertible Functions

    Eiichiro Fujisaki and Keita Xagawa

    LATINCRYPT 2015, LNCS 9230, pp.3-20 (2015/08)

37. [ACNS:SEXY15] Accumulable Optimistic Fair Exchange from Verifiably Encrypted Homomorphic Signatures

    Jae Hong Seo, Keita Emura, Keita Xagawa, and Kazuki Yoneyama

    ACNS 2015, LNCS 9092, pp.192-214 (2015/06)

    See the journal version [IJIS:SEXY18]

38. [IEICE:NisXag15] Key-Private Proxy Re-Encryption from Lattices, Revisited

    Ryo Nishimaki and Keita Xagawa

    IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences, Vol.E98-A, No.1, pp.100-116. (2015/01)

    An extended construction of [PKC:CCLNX14]

39. [EPRINT:FujXag15] Note on the RKA security of Continuously Non-Malleable Key-Derivation Function from PKC 2015

    Eiichiro Fujisaki and Keita Xagawa

    ia.cr/2015/1088

40. [IEICE:FujFujXag14] Non-malleable Multiple Public-Key Encryption

    Atsushi Fujioka, Eiichiro Fujisaki, and Keita Xagawa

    IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences, Vol.E97-A, No.6, pp.1318-1334. (2014/06)

41. [IEICE:FujSaiXag14] Secure Hierarchical Identity-Based Identification without Random Oracles

    Atsushi Fujioka, Taiichi Saito, and Keita Xagawa

    IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences, Vol.E97-A, No.6, pp.1307-1317. (2014/06)

42. [PKC:AFFPTX14] Practical Cryptanalysis of a Public-Key Encryption Scheme Based on New Multivariate Quadratic Assumptions

    Martin R. Albrecht, Jean-Charles Faugère, Robert Fitzpatrick, Ludovic Perret, Yosuke Todo, and Keita Xagawa

    PKC 2014, LNCS 8383, pp.446-464 (2014/03)

    [EPRINT:AFFP13] + [EPRINT:TodXag13]

43. [PKC:CCLNX14] Re-encryption, functional re-encryption, and multi-hop re-encryption: A framework for achieving obfuscation-based security and instantiations from Lattices

    Nishanth Chandran, Melissa Chase, Feng-Hao Liu, Ryo Nishimaki, and Keita Xagawa

    PKC 2014, LNCS 8383, pp.95-112 (2014/03)

    See also ia.cr/2015/491. See also [IEICE:NisXag15] for a key-private PRE from lattices.

44. [ASIACCS:FSXY13] Practical and Post-Quantum Authenticated Key Exchange from One-Way Secure Key Encapsulation Mechanism

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

    ASIACCS 2013, pp.83-94 (2013/05)

45. [PKC:Xagawa13] Improved (Hierarchical) Inner-Product Encryption from Lattices

    Keita Xagawa

    PKC 2013, LNCS 7778, pp.235-252 (2013/02-03)

    See ia.cr/2015/249 for the full version.

46. [PKC:NisXag13] 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/02-03)

    See [DCC:NisXag15] and ia.cr/2015/248 for the full version.

47. [EPRINT:TodXag13] Cryptanalysis of the Huang-Liu-Yang Cryptosystem from PKC 2012

    Yosuke Todo and Keita Xagawa

    ia.cr/2013/481

    See [PKC:AFFPTX14] for the merged paper.

48. [EPRINT:Xagawa13] Message Authentication Codes Secure against Additive Related-Key Attacks

    Keita Xagawa

    ia.cr/2013/111

49. [CANS:FujSaiXag12] 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)

50. [ICICS:FujSaiXag12] Security Enhancement of Identity-Based Identification with Reversibility

    Atsushi Fujioka, Taiichi Saito, and Keita Xagawa

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

51. [ISC:FujSaiXag12] Secure Hierarchical Identity-Based Identification without Random Oracles

    Atsushi Fujioka, Taiichi Saito, and Keita Xagawa

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

52. [ACNS:FujSaiXag12] 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)

53. [PKC:FSXY12] 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 [DCC:FSXY15] and ia.cr/2012/211 for the full version.

54. [PKC:KNTX10] 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 ia.cr/2010/122 for the full version.

55. [AC:SSTX09] 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 ia.cr/2009/285 for the draft of the full version.

56. [PROVSEC:XagTan09] 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)

57. [AC:KawTanXag08] 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]

58. [AAAC:XagTan08] A Compact Signature Scheme with Ideal Lattice (Extended Abstract) (1-page)

    Keita Xagawa and Keisuke Tanaka

    AAAC 2008

    This work is superseded by [AC:SSTX09].

    [2008AAAC.pdf] [Slides:20080426_AAAC.pdf]

59. [PKC:KawTanXag07] 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]

Domestic Symsioum/Conference/Workshop

1. [CSS:KulXag24] Strong Existential Unforgeability of MPC-in-the-Head Signatures

   MPC-in-the-Head署名の強存在的偽造不可能性

   मुकुल कुळकर्णी (Mukul Kulkarni), 草川 恵太

   CSS 2024 3H4-4 (2024/10)

2. [SCIS:Xagawa24] Signatures with Memory-Tight Security in the Quantum Random Oracle Model (Extended Abstract)

   量子ランダムオラクルモデルで空間緊密な安全性帰着をもつ署名方式（概要版）

   草川 恵太

   SCIS 2024 4A2-4 (2024/01)

3. [SCIS:MarXag23] Kyberの耐量子計算機匿名性（概要版）

   Varun Maram, 草川 恵太

   SCIS 2023 2A2-1 (2023/01)

4. [SCIS:KosXag23] Probabilistic Hash-and-sign with Retry in the Quantum Random Oracle Model

   小菅 悠久, 草川 恵太

   SCIS 2023 2A4-3 (2023/01)

5. [CSS:MarXag22] KyberとSaberの耐量子計算機安全性（概要版）

   Varun Maram, 草川 恵太

   CSS 2022 2A3-IV-4 (2022/10)

   CSS2022優秀論文賞

6. [IEICE-HWS:TUXITH22] Side-Channel Attacks on Post-Quantum KEMs Using Multi-class Classification Neural Network

   耐量子鍵カプセル化メカニズムに対する多クラス分類ニューラルネットワークを用いたサイドチャネル攻撃の検討

   田中 裕太郎, 上野 嶺, 草川 恵太, 伊東 燦, 高橋 順子, 本間 尚文

   IEICE-HWS2022-7 (2022/07)

7. [SCIS:Xagawa22] NIST PQC Round3候補の鍵カプセル化方式の匿名性

   草川 恵太

   SCIS 2022 1A2-1 (2022/01)

8. [SCIS:UXTITH22] 耐量子鍵カプセル化メカニズムに対する一般化サイドチャネル攻撃

   上野 嶺, 草川 恵太, 田中 裕太郎, 伊東 燦, 高橋 順子, 本間 尚文

   SCIS 2022 1C1-1 (2022/01)

9. [SCIS:XIUTH22] NIST PQC Round3候補の鍵カプセル化方式への故障注入攻撃

   草川 恵太, 伊東 燦, 上野 嶺, 高橋 順子, 本間 尚文

   SCIS 2022 2A2-1 (2022/01)

10. [QIT:MisXag21] Secure multi-party quantum computation based on triply-even quantum error-correcting codes

    立法重偶量子誤り訂正符号に基づいた量子秘密計算

    Mishchenko Petr, 草川 恵太

    QIT 45 - 12(2021/11)

11. [SCIS:Xagawa21] Boneh-Katz変換再訪

    草川 恵太

    SCIS 2021 1A1-2 (2021/01)

12. [SCIS:Xagawa20] 暗号方式構成の効率の限界について

    草川 恵太

    SCIS 2020 1A1-2 (2020/01)

13. [SCIS:NTXM19] GLP署名の故障利用攻撃に対する安全性評価

    長濱 拓季, 藤堂 洋介, 草川 恵太, 森井 昌克

    SCIS 2019 2D4-1 (2019/01)

14. [SCIS:Xagawa19] Practical Attack on RaCoSS-R

    RaCoSS-Rへの実時間攻撃

    Keita Xagawa

    SCIS 2019 3B2-5 (2019/01)

15. [SCIS:Xagawa18] Practical Cryptanalysis of a Public-key Encryption Scheme Based on Non-linear Indeterminate Equations at SAC 2017: Extended Abstract

    「非線型不定方程式に基づく公開鍵暗号」への実時間攻撃

    Keita Xagawa

    SCIS 2018 1B2-3 (2018/01)

16. [SCIS:KOSXKH18] KEMを用いた動的多者鍵配布プロトコル

    金城 皓羽, 岡野 裕樹, 齋藤 恆和, 草川 恵太, 小林 鉄太郎, 星野 文学

    SCIS 2018 3A2-1 (2018/01)

17. [SCIS:NFTXM18] 整数計画法を用いた平文回復攻撃による二値行列LWE暗号の安全性評価

    長濱 拓季, 船引 悠生, 藤堂 洋介, 草川 恵太, 森井 昌克

    SCIS 2018 4A1-2 (2018/01)

18. [SCIS:Xagawa17:3E4-3] Cryptanalysis of "Proxy Re-Encryption Schemes with Key Privacy from LWE"

    「LWEに基づく再暗号化鍵匿名性を持つ代理人再暗号化方式」に対する攻撃

    Keita Xagawa

    SCIS 2017 3E4-3 (2017/01).

    We show that a new version of the KP-PRE from LWE [ia.cr/2016/327] is neither CCA2-secure nor key-private in the CCA setting.

19. [SCIS:Xagawa17:2E3-3] 自己破壊可能回路を許す公開鍵暗号の安全性の分離

    Keita Xagawa

    SCIS 2017 2E3-3 (2017/01).

    There exists a PKE which is NM-SDA-secure but not IND-CCA2-seucre.

20. [SCIS:Xagawa16] Groth-Sahai Proofs Revisited Again: A Bug in ``Optimized'' Randomization

    Groth-Sahai証明再々訪

    Keita Xagawa

    SCIS 2016 3E3-1 (2016/01)

21. [SCIS:FujXag15] 防御不可能なタンパリング以外のほぼ全てのタンパリングから暗号回路を守る方法

    Eiichiro Fujisaki and Keita Xagawa

    SCIS 2015 3D3-1 (2015/01)

22. [SCIS:SEXY15:2E4-4] Verifiably Encrypted Homomorphic Signatures

    検証可能暗号化準同型署名

    Jae Hong Seo, Keita Emura, Keita Xagawa, and Kazuki Yoneyama

    SCIS 2015 2E4-4 (2015/01)

23. [SCIS:SEXY15:1E1-5] Accumulable Optimistic Fair Exchange

    ツケ払いに適した楽観的公平交換

    Jae Hong Seo, Keita Emura, Keita Xagawa, and Kazuki Yoneyama

    SCIS 2015 1E1-5 (2015/01)

24. [SCIS:HTXM14] GPGPUを用いたGSW13完全準同型暗号の高速実装

    Ryo Hirano, Yosuke Todo, Keita Xagawa, and Masakatu Morii

    SCIS 2014 1D3-1 (2014/01)

25. [SCIS:KanXagTak14] 多変数公開鍵暗号Simple Matrix方式の復号化における問題点

    Yuta Kanno, Keita Xagawa, and Tsuyoshi Takagi

    SCIS 2014 3E1-4 (2014/01)

26. [SCIS:CCLNX14] 格子問題に基づく再暗号化方式の難読化について

    Nishanth Chandran, Melissa Chase, Feng-Hao Liu, Ryo Nishimaki, and Keita Xagawa

    SCIS 2014 4E1-4 (2014/01)

    See [PKC:CCLNX14]

27. [SCIS:Xagawa14] RKA-KDM-CCA secure public-key encryption scheme

    Keita Xagawa

    SCIS 2014 4E2-2 (2014/01)

28. [SCIS:Xagawa13] Message Authentication Codes Secure against Additive Related-Key Attacks

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

    Keita Xagawa

    SCIS 2013 1B1-2 (2013/01)

    See [EPRINT:Xagawa13]

29. [SCIS:FujXag13] 可逆なタンパー関数に耐性を持つ暗号学的回路

    Eiichiro Fujisaki and Keita Xagawa

    SCIS 2013 2B2-3 (2013/01)

30. [SCIS:Xagawa12] An Attack on Key-Exchange Protocols Proposed by Accardi et al.

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

    Keita Xagawa

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

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

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

    SCIS 2011 3F4-1 (2011/01)

    See [PKC:FSXY12]

32. [SCIS:Xagawa11] Indistinguishability against Related-Key Attacks in the Public-Key Settigns and Bidrectional Proxy Re-Encryption

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

    Keita Xagawa

    SCIS 2011 2A2-5 (2011/01)

33. [SCIS:XagTan10] 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]

34. [SCIS:XagKaw10] 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)

35. [SCIS:XagTan09:4A2-5] 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)

    See [AC:SSTX09] (and my Ph.D Thesis)

    [Slides in Japanese:20090123_SCIS_IdealLWE.pdf]

36. [SCIS:XagTan09:3F2-5] 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]

37. [SCIS:XagTan09:3F2-4] Zero-Knowledge Protocols for NTRU

    NTRU暗号に対するゼロ知識証明

    Keita Xagawa and Keisuke Tanaka

    SCIS 2009 3F2-4 (2009/01)

    See [PROVSEC:XagTan09]

    [Slides in Japanese:20090122_SCIS_NTRU-ZK.pdf]

38. [SCIS:NXKT09:3D1-2] 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)

    See [PKC:KNTX10]

39. [SCIS:NXKT09:3D1-1] 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)

    See [PKC:KNTX10]

    [Slides in Japanese: 20080723_LA.pdf], [Slides in Japanese: 20090122_SCIS_Dist.pdf]

40. [SCIS:XagTan08] A Compact Signature Scheme with Ideal Lattice (Extended Abstract)

    イデアル格子問題に基づくコンパクトな署名方式

    Keita Xagawa and Keisuke Tanaka

    SCIS 2008 3D3-2 (2008/01)

    See [AC:SSTX09] (and my Ph.D Thesis)

    [Slides in Japanese: 20080124_SCIS_Ideal.pdf]

41. [SCIS:XagKawTan08] 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), LA Symposium 2007 Summer 11 (2007/07)

    See [AC:KawTanXag08] and my Ph.D Thesis

    [TR: C-249.pdf], [Slides in Japanese: 20080124_SCIS_SID.pdf]

42. [SCIS:XagKawTan07:1C1-2] 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]

43. [SCIS:XagKawTan07:1C1-1] 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]

44. [SCIS:XagKawTan06] 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)

    See [PKC:KawTanXag07] and my master 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 errors...

  [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]

Lectures

1. 2024-Fall, XCO.T474: Theory of Cryptography for Cybersecurity

   XCO.T474: サイバーセキュリティ暗号理論

   At Tokyo Institute of Technology with Takahiro Matsuda and Ryo Nishimaki.

   攻撃×5の予定

   See slides and problems in gitlab.com/xagawa/sciencetokyo24

2. 2023-Fall, XCO.T474: Theory of Cryptography for Cybersecurity

   XCO.T474: サイバーセキュリティ暗号理論

   At Tokyo Institute of Technology with Takahiro Matsuda and Ryo Nishimaki.

   攻撃×4の予定

   See slides and problems in gitlab.com/xagawa/titech23

3. 2022-Fall, XCO.T474: Theory of Cryptography for Cybersecurity

   XCO.T474: サイバーセキュリティ暗号理論

   At Tokyo Institute of Technology with Takahiro Matsuda and Ryo Nishimaki.

   攻撃×5の予定

   See slides and problems in gitlab.com/xagawa/titech22

4. 2021 集中講義

   豊橋技術科学大学

   At Toyohashi University of Technology.

5. 2021-Fall, XCO.T474: Theory of Cryptography for Cybersecurity

   XCO.T474: サイバーセキュリティ暗号理論

   At Tokyo Institute of Technology with Takahiro Matsuda, Ryo Nishimaki, and Keisuke Tanaka.

   攻撃×4の予定

   See slides and problems in gitlab.com/xagawa/titech21

6. 2020-Fall, XCO.T474: Theory of Cryptography for Cybersecurity

   XCO.T474: サイバーセキュリティ暗号理論

   At Tokyo Institute of Technology with Takahiro Matsuda and Ryo Nishimaki.

   攻撃×4の予定

   See slides and problems in gitlab.com/xagawa/titech20

7. 2019-Fall, XCO.T474: Theory of Cryptography for Cybersecurity

   XCO.T474: サイバーセキュリティ暗号理論

   At Tokyo Institute of Technology with Takahiro Matsuda and Ryo Nishimaki.

   秘密分散と秘密計算の予定

   See slides and problems in gitlab.com/xagawa/titech19

8. 2018-Fall, XCO.T474: Theory of Cryptography for Cybersecurity

   XCO.T474: サイバーセキュリティ暗号理論

   At Tokyo Institute of Technology with Takahiro Matsuda and Ryo Nishimaki.

9. 2017-Fall, XCO.T474: Theory of Cryptography for Cybersecurity

   XCO.T474: サイバーセキュリティ暗号理論

   At Tokyo Institute of Technology with Takahiro Matsuda and Ryo Nishimaki.

10. 2016-Fall, XCO.T474: Theory of Cryptography for Cybersecurity

    XCO.T474: サイバーセキュリティ暗号理論

    At Tokyo Institute of Technology with Takahiro Matsuda and Ryo Nishimaki.

11. 2014-Spring-75024: Topics on Mathematical and Computing Science VI

    2014-Spring-75024: 数理・計算科学特論第六

    At Tokyo Institute of Technology with Eiichiro Fujisaki and Ryo Nishimaki.

12. 2013-Spring-75024: Topics on Mathematical and Computing Science VI

    2013-Spring-75024: 数理・計算科学特論第六

    At Tokyo Institute of Technology with Ryo Nishimaki.

Talks

1. A survey of side-channel assisted key-recovery attacks against lattice-based key-encapsulation mechanisms

   格子ベースの鍵カプセル化方式に対するサイドチャネル攻撃を利用した鍵回復攻撃

   Keita Xagawa

   現代暗号に対する安全性解析・攻撃の数理 (2023/09/20-22)

   My slides are available in their Japanese website.

2. (---)

   Keita Xagawa

   防衛省 --- (2022/10/??)

3. Anonymity of NIST PQC Round-3 KEMs

   Keita Xagawa

   ENSL/CWI/RHUL Joint Online Cryptography Seminars (2022/06/27)

4. 耐量子計算機暗号の動向

   Keita Xagawa

   第66回 ISSスクエア水平ワークショップ 『耐量子セキュリティ』 (2022/06/24)

5. 耐量子計算機暗号の動向

   Keita Xagawa

   Interop Tokyo 2022 Conference: YE2-02 量子セキュリティ：矛と「盾」 (2022/06/16)

   パネリストの1人として参加

6. (---)

   Keita Xagawa

   INTERPOL Innovation Center Virtual Room (2022/05/24)

7. 耐量子計算機暗号の実現に向けたＮＴＴの研究開発

   Keita Xagawa

   マルチメディア推進フォーラム Part881 ｢究極のセキュリティ『量子暗号』と『耐量子計算機暗号』その最新動向｣～各国が覇を競う量子コンピューター時代の暗号通信～ (2022/03/31)

8. 格子暗号理論とその応用

   Keita Xagawa

   東京大学大学院数理科学研究科・理学部数学科 情報数学セミナー (2022/01/13)

9. 耐量子計算機暗号の解説 ～符号暗号を中心として～

   Keita Xagawa

   SITA 2021 (2021/12)

   My slides in English are available in their website (SITA).

10. Key-recovery Attacks against Lattice-based KEM with Plaintext-checking/Key-mismatch Oracle and Relation to Side-channel Analysis and Fault-injection Analysis

    格子暗号への平文・鍵確認オラクルを用いた鍵回復攻撃とサイドチャネル攻撃・故障利用攻撃

    Keita Xagawa

    新世代暗号の設計・評価 (2021/11)

    My slides are available in their Japanese website.

11. 量子攻撃・量子構成の下界について

    Keita Xagawa

    IEICE General Conference 2021 ADI-1. 信学会総合大会2021 ADI-1. 量子計算と暗号の進展 (2021/03)

12. 量子攻撃・量子構成の下界について

    Keita Xagawa

    IEICE General Conference 2020 ADI-1. 信学会総合大会2020 ADI-1. 量子計算と暗号の発展 (2020/03)

    Due to COVID-19, the conference is missing...

13. 耐量子暗号

    Keita Xagawa

    The 2nd YITP Quantum Information School 第二回基研量子情報スクール (2020/02)

    My slides in Japanese: http://www2.yukawa.kyoto-u.ac.jp/~tomoyuki.morimae/Xagawa.pdf

14. 格子暗号の現状とこれから

    Keita Xagawa

    第51回 ISSスクエア水平ワークショップ 『Post-Quantum Cryptographyの現状とこれから』 (2018/01)

15. Post-Quantum Cryptography in NTT

    Keita Xagawa

    3rd Asia Post-Quantum Cryptography Forum (2017/03)

16. A brief summary of FHE, MLM, and iO with lattices (in 30 min.)

    AI-1-7. 完全準同型暗号, 多線形写像, 識別不能難読化の数学的基礎：特に格子問題

    Keita Xagawa

    IEICE General Conference AI-1. 信学会総合大会2015 AI-1. 最新暗号ツールの研究動向：完全準同型暗号、多線形写像、難読化 (2015/03)

17. Practical Cryptanalysis of a Public-Key Encryption Scheme Based on New Multivariate Quadratic Assumptions

    Keita Xagawa

    Workshop: Post-Quantum Cryptography and Its Related Topics (2013/12)

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

    Keita Xagawa

    PKC2013を勉強する会 (2013/06)

19. A Survey on LWE-based Encryption Schemes

    Keita Xagawa

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

20. Brief History of Lattice Crypto World

    Keita Xagawa

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

21. Lattice-based Hash Functions

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

    Keita Xagawa

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

    [Slides in Japanese: 20100224.pdf]

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

23. A Survey on Lattice-Based Hash Functions

    Keita Xagawa

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

    [Slides in Japanese: 20070303_NHC.pdf]