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

Kouichi Sakurai; Tsuyoshi Takagi

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

Research output: Contribution to journal › Article › peer-review

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
Pages (from-to)	359-373
Number of pages	15
Journal	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	2587
Publication status	Published - Dec 1 2003

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Computer Science(all)

Cite this

@article{14966ba836524ad6a26dce5189e88b2f,

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",

month = dec,

day = "1",

language = "English",

volume = "2587",

pages = "359--373",

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

issn = "0302-9743",

publisher = "Springer Verlag",

}

TY - JOUR

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

AU - Sakurai, Kouichi

AU - Takagi, Tsuyoshi

PY - 2003/12/1

Y1 - 2003/12/1

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

M3 - Article

AN - SCOPUS:35248894388

SN - 0302-9743

VL - 2587

SP - 359

EP - 373

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

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

ER -

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

Abstract

All Science Journal Classification (ASJC) codes

Other files and links

Fingerprint

Cite this