Extension of simultaneous Diophantine approximation algorithm for partial approximate common divisor variants
Abstract A simultaneous Diophantine approximation (SDA) algorithm takes instances of the partial approximate common divisor (PACD) problem as input and outputs a solution. While several encryption schemes have been published and their securities depend on the presumed hardness of variant of the PACD...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2021-11-01
|
| Series: | IET Information Security |
| Subjects: | |
| Online Access: | https://doi.org/10.1049/ise2.12032 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832559643038056448 |
|---|---|
| author | Wonhee Cho Jiseung Kim Changmin Lee |
| author_facet | Wonhee Cho Jiseung Kim Changmin Lee |
| author_sort | Wonhee Cho |
| collection | DOAJ |
| description | Abstract A simultaneous Diophantine approximation (SDA) algorithm takes instances of the partial approximate common divisor (PACD) problem as input and outputs a solution. While several encryption schemes have been published and their securities depend on the presumed hardness of variant of the PACD problem, fewer studies have attempted to extend the SDA algorithm to be applicable to these variants. In this study, the SDA algorithm is extended to solve the general PACD problem. In order to proceed, first the variants of the PACD problem are classified and how to extend the SDA algorithm for each is suggested. Technically, the authors show that a short vector of some lattice used in the SDA algorithm gives an algebraic relation between secret parameters. Then, all the secret parameters can be recovered by finding this short vector. It is also confirmed experimentally that this algorithm works well. |
| format | Article |
| id | doaj-art-a6483882abf64bd9a84381da4adafd72 |
| institution | Kabale University |
| issn | 1751-8709 1751-8717 |
| language | English |
| publishDate | 2021-11-01 |
| publisher | Wiley |
| record_format | Article |
| series | IET Information Security |
| spelling | doaj-art-a6483882abf64bd9a84381da4adafd722025-02-03T01:29:37ZengWileyIET Information Security1751-87091751-87172021-11-0115641742710.1049/ise2.12032Extension of simultaneous Diophantine approximation algorithm for partial approximate common divisor variantsWonhee Cho0Jiseung Kim1Changmin Lee2Department of Mathematical Sciences Seoul National University Seoul South KoreaSchool of Computational Sciences Korea Institute for Advanced Study Seoul Republic of KoreaSchool of Computational Sciences Korea Institute for Advanced Study Seoul Republic of KoreaAbstract A simultaneous Diophantine approximation (SDA) algorithm takes instances of the partial approximate common divisor (PACD) problem as input and outputs a solution. While several encryption schemes have been published and their securities depend on the presumed hardness of variant of the PACD problem, fewer studies have attempted to extend the SDA algorithm to be applicable to these variants. In this study, the SDA algorithm is extended to solve the general PACD problem. In order to proceed, first the variants of the PACD problem are classified and how to extend the SDA algorithm for each is suggested. Technically, the authors show that a short vector of some lattice used in the SDA algorithm gives an algebraic relation between secret parameters. Then, all the secret parameters can be recovered by finding this short vector. It is also confirmed experimentally that this algorithm works well.https://doi.org/10.1049/ise2.12032approximation theorypublic key cryptographymatrix algebra |
| spellingShingle | Wonhee Cho Jiseung Kim Changmin Lee Extension of simultaneous Diophantine approximation algorithm for partial approximate common divisor variants IET Information Security approximation theory public key cryptography matrix algebra |
| title | Extension of simultaneous Diophantine approximation algorithm for partial approximate common divisor variants |
| title_full | Extension of simultaneous Diophantine approximation algorithm for partial approximate common divisor variants |
| title_fullStr | Extension of simultaneous Diophantine approximation algorithm for partial approximate common divisor variants |
| title_full_unstemmed | Extension of simultaneous Diophantine approximation algorithm for partial approximate common divisor variants |
| title_short | Extension of simultaneous Diophantine approximation algorithm for partial approximate common divisor variants |
| title_sort | extension of simultaneous diophantine approximation algorithm for partial approximate common divisor variants |
| topic | approximation theory public key cryptography matrix algebra |
| url | https://doi.org/10.1049/ise2.12032 |
| work_keys_str_mv | AT wonheecho extensionofsimultaneousdiophantineapproximationalgorithmforpartialapproximatecommondivisorvariants AT jiseungkim extensionofsimultaneousdiophantineapproximationalgorithmforpartialapproximatecommondivisorvariants AT changminlee extensionofsimultaneousdiophantineapproximationalgorithmforpartialapproximatecommondivisorvariants |