Keita Xagawa (草川 恵太)

About

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

Publications

Refereed International Conference Papers

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.
Liskov proposed several weakened versions of the random oracle model, called weakened random oracle models (WROMs), to capture the vulnerability of ideal compression functions, which are expected to have the standard security of hash functions, i.e., collision resistance, second-preimage resistance, and one-wayness properties. The WROMs offer additional oracles to break such properties of the random oracle. In this paper, we investigate whether public-key encryption schemes in the random oracle model essentially require the standard security of hash functions by the WROMs. In particular, we deal with four WROMs associated with the standard security of hash functions; the standard, collision tractable, second-preimage tractable, first-preimage tractable ones (ROM, CT-ROM, SPT-ROM, and FPT-ROM, respectively), done by Numayama et al. for digital signature schemes in the WROMs. We obtain the following results: (1) The OAEP is secure in all the four models. (2) The encryption schemes obtained by the Fujisaki-Okamoto conversion (FO) are secure in the SPT-ROM. However, some encryption schemes with FO are insecure in the FPT-ROM. (3) We consider two artificial variants wFO and dFO of FO for separation of the WROMs in the context of encryption schemes. The encryption schemes with wFO (dFO, respectively) are secure in the CT-ROM (ROM, respectively). However, some encryption schemes obtained by wFO (dFO, respectively) are insecure in the SPT-ROM (CT-ROM, respectively). These results imply that standard encryption schemes such as the OAEP and FO-based one do not always require the standard security of hash functions. Moreover, in order to make our security proofs complete, we construct an efficient sampling algorithm for the binomial distribution with exponentially large parameters, which was left open in Numayama et al.’s paper.
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

格子問題、符号理論、および素因数分解問題に基づく強い認証鍵交換: 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

Lattice-based Hash Functions
格子に基づく安全なハッシュ関数の構成
Keita Xagawa
Workshop on interaction between CRyptography, Information Security and MATHematics (CRISMATH) 暗号及び情報セキュリティと数学の相関ワークショップ (2010/02)
[Slides in Japanese: 20100224.pdf]
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]
A Survey on Lattice-Based Hash Functions
Keita Xagawa
New Horizons in Computing - Mini Meeting (Cryptography) (2007/03)
[Slides in Japanese: 20070303_NHC.pdf]