A reject timing attack on an IND-CCA2 public-key cryptosystem

Kouichi Sakurai; Tsuyoshi Takagi

doi:10.1007/3-540-36552-4_25

A reject timing attack on an IND-CCA2 public-key cryptosystem

Kouichi Sakurai, Tsuyoshi Takagi

Mathematical Informatics

Research output: Chapter in Book/Report/Conference proceeding › Chapter

9 Citations (Scopus)

Abstract

EPOC-2 is a public-key cryptosystem that can be proved IND-CCA2 under the factoring assumption in the random oracle model. It was written into a standard specification P1363 of IEEE, and it has been a candidate of the public-key cryptosystem in several international standards (or portfolio) on cryptography, e.g. NESSIE, CRYPTREC, ISO, etc. In this paper we propose a chosen ciphertext attack against EPOC-2 from NESSIE by observing the timing of the reject signs from the decryption oracle. We construct an algorithm, which can factor the public modulus using the difference of the reject symbols. For random 384-bit primes, the modulus can be factored with probability at least 1/2 by invoking about 385 times to the decryption oracle.

Original language	English
Title of host publication	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Editors	Pil Joong Lee, Chae Hoon Lim
Publisher	Springer Verlag
Pages	359-373
Number of pages	15
ISBN (Electronic)	9783540007166
DOIs	https://doi.org/10.1007/3-540-36552-4_25
Publication status	Published - 2003

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	2587
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/3-540-36552-4_25

Cite this

Sakurai, K., & Takagi, T. (2003). A reject timing attack on an IND-CCA2 public-key cryptosystem. In P. J. Lee, & C. H. Lim (Eds.), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp. 359-373). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2587). Springer Verlag. https://doi.org/10.1007/3-540-36552-4_25

A reject timing attack on an IND-CCA2 public-key cryptosystem. / Sakurai, Kouichi; Takagi, Tsuyoshi.
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). ed. / Pil Joong Lee; Chae Hoon Lim. Springer Verlag, 2003. p. 359-373 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2587).

Research output: Chapter in Book/Report/Conference proceeding › Chapter

Sakurai, K & Takagi, T 2003, A reject timing attack on an IND-CCA2 public-key cryptosystem. in PJ Lee & CH Lim (eds), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 2587, Springer Verlag, pp. 359-373. https://doi.org/10.1007/3-540-36552-4_25

Sakurai K, Takagi T. A reject timing attack on an IND-CCA2 public-key cryptosystem. In Lee PJ, Lim CH, editors, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Springer Verlag. 2003. p. 359-373. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-36552-4_25

Sakurai, Kouichi ; Takagi, Tsuyoshi. / A reject timing attack on an IND-CCA2 public-key cryptosystem. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). editor / Pil Joong Lee ; Chae Hoon Lim. Springer Verlag, 2003. pp. 359-373 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inbook{a211cf74cd504e649f921af440751867,

title = "A reject timing attack on an IND-CCA2 public-key cryptosystem",

abstract = "EPOC-2 is a public-key cryptosystem that can be proved IND-CCA2 under the factoring assumption in the random oracle model. It was written into a standard specification P1363 of IEEE, and it has been a candidate of the public-key cryptosystem in several international standards (or portfolio) on cryptography, e.g. NESSIE, CRYPTREC, ISO, etc. In this paper we propose a chosen ciphertext attack against EPOC-2 from NESSIE by observing the timing of the reject signs from the decryption oracle. We construct an algorithm, which can factor the public modulus using the difference of the reject symbols. For random 384-bit primes, the modulus can be factored with probability at least 1/2 by invoking about 385 times to the decryption oracle.",

author = "Kouichi Sakurai and Tsuyoshi Takagi",

year = "2003",

doi = "10.1007/3-540-36552-4_25",

language = "English",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "359--373",

editor = "Lee, {Pil Joong} and Lim, {Chae Hoon}",

booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

address = "Germany",

}

TY - CHAP

T1 - A reject timing attack on an IND-CCA2 public-key cryptosystem

AU - Sakurai, Kouichi

AU - Takagi, Tsuyoshi

PY - 2003

Y1 - 2003

N2 - EPOC-2 is a public-key cryptosystem that can be proved IND-CCA2 under the factoring assumption in the random oracle model. It was written into a standard specification P1363 of IEEE, and it has been a candidate of the public-key cryptosystem in several international standards (or portfolio) on cryptography, e.g. NESSIE, CRYPTREC, ISO, etc. In this paper we propose a chosen ciphertext attack against EPOC-2 from NESSIE by observing the timing of the reject signs from the decryption oracle. We construct an algorithm, which can factor the public modulus using the difference of the reject symbols. For random 384-bit primes, the modulus can be factored with probability at least 1/2 by invoking about 385 times to the decryption oracle.

AB - EPOC-2 is a public-key cryptosystem that can be proved IND-CCA2 under the factoring assumption in the random oracle model. It was written into a standard specification P1363 of IEEE, and it has been a candidate of the public-key cryptosystem in several international standards (or portfolio) on cryptography, e.g. NESSIE, CRYPTREC, ISO, etc. In this paper we propose a chosen ciphertext attack against EPOC-2 from NESSIE by observing the timing of the reject signs from the decryption oracle. We construct an algorithm, which can factor the public modulus using the difference of the reject symbols. For random 384-bit primes, the modulus can be factored with probability at least 1/2 by invoking about 385 times to the decryption oracle.

UR - http://www.scopus.com/inward/record.url?scp=35248894388&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=35248894388&partnerID=8YFLogxK

U2 - 10.1007/3-540-36552-4_25

DO - 10.1007/3-540-36552-4_25

M3 - Chapter

AN - SCOPUS:35248894388

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 359

EP - 373

BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

A2 - Lee, Pil Joong

A2 - Lim, Chae Hoon

PB - Springer Verlag

ER -

A reject timing attack on an IND-CCA2 public-key cryptosystem

Abstract

Publication series

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this