| Presentation | 2015-03-02 On the Limit of Security Proof for Homomorphic Encryption Daiki TAKAHASHI, Shingo HASEGAWA, Shuji ISOBE, Eisuke KOIZUMI, Hiroki SHIZUYA, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | In this paper, we explore on the limitation of security proofs for homomorphic encryptions. We consider the computational complexity for verifying the validity of the plaintext-ciphertext pairs, that is, on any given pair (b, c), to determine whether or not c is a ciphertext of the plaintext b. We show that for any homomorphic encryption scheme, if the complexity of its verification problem is characterized by the classes in the low hierarchy within NP, then the scheme cannot be proven to be secure beyond the low hierarchy classes via reduction proofs. We also discuss the case where the complexity of the verification problem is characterized by SZK, the class of languages that have statistical zero-knowledge proofs, and show that the limitation of the security proofs is characterized by some intermediate class between SZK and AM ∩ coAM. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | homomorphic encryption / security proof / low hierarchy / statistical zero-knowledge |
| Paper # | IT2014-67,ISEC2014-80,WBS2014-59 |
| Date of Issue |
| Conference Information | |
| Committee | ISEC |
|---|---|
| Conference Date | 2015/2/23(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) | On the Limit of Security Proof for Homomorphic Encryption |
| Sub Title (in English) | |
| Keyword(1) | homomorphic encryption |
| Keyword(2) | security proof |
| Keyword(3) | low hierarchy |
| Keyword(4) | statistical zero-knowledge |
| 1st Author's Name | Daiki TAKAHASHI |
| 1st Author's Affiliation | Graduate School of Information Sciences, Tohoku University() |
| 2nd Author's Name | Shingo HASEGAWA |
| 2nd Author's Affiliation | Graduate School of Information Sciences, Tohoku University |
| 3rd Author's Name | Shuji ISOBE |
| 3rd Author's Affiliation | Graduate School of Information Sciences, Tohoku University |
| 4th Author's Name | Eisuke KOIZUMI |
| 4th Author's Affiliation | Graduate School of Information Sciences, Tohoku University |
| 5th Author's Name | Hiroki SHIZUYA |
| 5th Author's Affiliation | Graduate School of Information Sciences, Tohoku University |
| Date | 2015-03-02 |
| Paper # | IT2014-67,ISEC2014-80,WBS2014-59 |
| Volume (vol) | vol.114 |
| Number (no) | 471 |
| Page | pp.pp.- |
| #Pages | 6 |
| Date of Issue | |