| IEICE Technical Committee Submission System Conference Paper's Information |
Online Proceedings [Sign in] Tech. Rep. Archives |
| Go Top Page | Go Previous | [Japanese] / [English] |
| Paper Abstract and Keywords | ||
| Presentation | 2017-11-10 15:10 Lattice Attacks on Elliptic Curve Diffie-Hellman key exchange Sota Onozawa (The Univ. of Tokyo), Atsushi Takayasu (The Univ. of Tokyo/AIST), Noboru Kunihiro (The Univ. of Tokyo)  ISEC2017-69 SITE2017-51 LOIS2017-46 |
|
| Abstract | (in Japanese) | (See Japanese page) |
| (in English) | Boneh and Venkatesan (Crypto’96) introduced the hidden number problem (HNP) to study the security of Diffie-Hellman key exchange protocol by assuming exposures of partial information. In short, an HNP solver tries to recover a shared key through the protocol by issuing adaptive queries to an oracle who answers partial information of shared keys. Shani (PKC’17) first studied an elliptic curve HNP (EC-HNP) to study the security of elliptic curve Diffie-Hellman key exchange protocol. He reduced the EC-HNP to simultaneous modular equations then proposed a deterministic key recovery algorithm that utilized lattice-reduction algorithms. If an EC-HNP oracle answers about 83 % most significant bits (MSBs) of shared keys sufficiently many times, the algorithm works in polynomial time.In this work, we improves the attack by using lattice-based Coppersmith’s method. We show that higher degree polynomials, which were not used in previous works, are useful to obtain better results. Concretely, although our proposed algorithm is heuristic, it works in polynomial time by assuming an oracle who answers about 65 % MSBs only 11 times. Furthermore, even if the number of queries is only 3 times, our algorithm works in polynomial time with about 78 % MSBs. Therefore, our attack requires a weaker oracle than Shani’s attack; less number of queries and less partial information. | |
| Keyword | (in Japanese) | (See Japanese page) |
| (in English) | / / / / / / / | |
| Reference Info. | IEICE Tech. Rep., vol. 117, no. 285, ISEC2017-69, pp. 115-122, Nov. 2017. | |
| Paper # | ISEC2017-69 | |
| Date of Issue | 2017-11-02 (ISEC, SITE, LOIS) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| Copyright and reproduction |
All rights are reserved and no part of this publication may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopy, recording, or any information storage and retrieval system, without permission in writing from the publisher. Notwithstanding, instructors are permitted to photocopy isolated articles for noncommercial classroom use without fee. (License No.: 10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| Download PDF | ISEC2017-69 SITE2017-51 LOIS2017-46 |
|
| Conference Information | |
| Committee | LOIS ISEC SITE |
| Conference Date | 2017-11-09 - 2017-11-10 |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Paper Information | |
| Registration To | ISEC |
| Conference Code | 2017-11-LOIS-ISEC-SITE |
| Language | Japanese |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Lattice Attacks on Elliptic Curve Diffie-Hellman key exchange |
| Sub Title (in English) | |
| Keyword(1) | |
| Keyword(2) | |
| Keyword(3) | |
| Keyword(4) | |
| Keyword(5) | |
| Keyword(6) | |
| Keyword(7) | |
| Keyword(8) | |
| 1st Author's Name | Sota Onozawa |
| 1st Author's Affiliation | The University of Tokyo (The Univ. of Tokyo) |
| 2nd Author's Name | Atsushi Takayasu |
| 2nd Author's Affiliation | The University of Tokyo/National Institute of Advanced Industrial Science and Technology (The Univ. of Tokyo/AIST) |
| 3rd Author's Name | Noboru Kunihiro |
| 3rd Author's Affiliation | The University of Tokyo (The Univ. of Tokyo) |
| 4th Author's Name | |
| 4th Author's Affiliation | () |
| 5th Author's Name | |
| 5th Author's Affiliation | () |
| 6th Author's Name | |
| 6th Author's Affiliation | () |
| 7th Author's Name | |
| 7th Author's Affiliation | () |
| 8th Author's Name | |
| 8th Author's Affiliation | () |
| 9th Author's Name | |
| 9th Author's Affiliation | () |
| 10th Author's Name | |
| 10th Author's Affiliation | () |
| 11th Author's Name | |
| 11th Author's Affiliation | () |
| 12th Author's Name | |
| 12th Author's Affiliation | () |
| 13th Author's Name | |
| 13th Author's Affiliation | () |
| 14th Author's Name | |
| 14th Author's Affiliation | () |
| 15th Author's Name | |
| 15th Author's Affiliation | () |
| 16th Author's Name | |
| 16th Author's Affiliation | () |
| 17th Author's Name | |
| 17th Author's Affiliation | () |
| 18th Author's Name | |
| 18th Author's Affiliation | () |
| Speaker | Author-1 |
| Date Time | 2017-11-10 15:10:00 |
| Presentation Time | 30 minutes |
| Registration for | ISEC |
| Paper # | ISEC2017-69, SITE2017-51, LOIS2017-46 |
| Volume (vol) | vol.117 |
| Number (no) | no.285(ISEC), no.286(SITE), no.287(LOIS) |
| Page | pp.115-122 |
| #Pages | 8 |
| Date of Issue | 2017-11-02 (ISEC, SITE, LOIS) |
[Return to Top Page]