Presentation | 1997/11/20 How to Prove (Non-) Existence of a Key Word As a Substring in Encrypted Messages Takako Ito, Hiroki Shizuya, |
---|---|
PDF Download Page | PDF download Page Link |
Abstract(in Japanese) | (See Japanese page) |
Abstract(in English) | Let f be an encryption function such that C=f(m). The problem we consider in this paper is, given C and a key word K, to determine whether K is contained as a substring in m or not. We show that this problem is equivalent to computing f^<-1> with respect to the polynomial-time Turing reducibility. This means that we cannot expect efficient algorithms for the problem. However; we also show that (non-)existence of K as a substring in m can be demonstrated in computational zero-knowledge if f is a group-isomorphic encryption function. We construct interactive protocols for the language and its complement equivalent to this decision problem without reducing them to an NP-complete language. |
Keyword(in Japanese) | (See Japanese page) |
Keyword(in English) | encryption function / elliptic curve / zero-knowledge |
Paper # | ISEC97-52 |
Date of Issue |
Conference Information | |
Committee | ISEC |
---|---|
Conference Date | 1997/11/20(1days) |
Place (in Japanese) | (See Japanese page) |
Place (in English) | |
Topics (in Japanese) | (See Japanese page) |
Topics (in English) | |
Chair | |
Vice Chair | |
Secretary | |
Assistant |
Paper Information | |
Registration To | Information Security (ISEC) |
---|---|
Language | JPN |
Title (in Japanese) | (See Japanese page) |
Sub Title (in Japanese) | (See Japanese page) |
Title (in English) | How to Prove (Non-) Existence of a Key Word As a Substring in Encrypted Messages |
Sub Title (in English) | |
Keyword(1) | encryption function |
Keyword(2) | elliptic curve |
Keyword(3) | zero-knowledge |
1st Author's Name | Takako Ito |
1st Author's Affiliation | Department of Computer and Mathematical Sciences, Graduate School of Information Sciences, Tohoku University() |
2nd Author's Name | Hiroki Shizuya |
2nd Author's Affiliation | Department of Computer and Mathematical Sciences, Graduate School of Information Sciences, Tohoku University |
Date | 1997/11/20 |
Paper # | ISEC97-52 |
Volume (vol) | vol.97 |
Number (no) | 381 |
Page | pp.pp.- |
#Pages | 10 |
Date of Issue |