by Remaud, Maxime, Schrottenloher, André and Tillich, Jean-Pierre
Abstract:
The Dihedral Coset Problem ($}{\$\backslashtextsf\DCP\$}{\$) in $}{\$\backslashmathbb \Z\_N$}{\$has been extensively studied in quantum computing and post-quantum cryptography, as for instance, the Learning with Errors problem reduces to it. While the Ettinger-Høyer algorithm is known to solve the $}{\$\backslashtextsf\DCP\$}{\$in $}{\$O\backslashleft( \backslashlog \N\ \backslashright) $}{\$queries, it runs inefficiently in time $}{\$O\backslashleft( N \backslashright) $}{\$. The first time-efficient algorithm was introduced (and later improved) by Kuperberg (SIAM J. Comput. 2005). These algorithms run in a subexponential amount of time and queries $}{\$\backslashtilde\O\\backslashleft( 2^\\backslashsqrt\c_\\backslashtextsf\DCP\\\backslashlog \N\\\ \backslashright) $}{\$, for some constant $}{\$c_\\backslashtextsf\DCP\\$}{\$.
Reference:
Time and Query Complexity Tradeoffs for the Dihedral Coset Problem (Remaud, Maxime, Schrottenloher, André and Tillich, Jean-Pierre), In Post-Quantum Cryptography (Johansson, Thomas, Smith-Tone, Daniel, eds.), Springer Nature Switzerland, 2023.
Bibtex Entry:
@inproceedings{10.1007/978-3-031-40003-2_19,
abstract = {The Dihedral Coset Problem ({\$}{\$}{\backslash}textsf{\{}DCP{\}}{\$}{\$}) in {\$}{\$}{\backslash}mathbb {\{}Z{\}}{\_}N{\$}{\$}has been extensively studied in quantum computing and post-quantum cryptography, as for instance, the Learning with Errors problem reduces to it. While the Ettinger-Høyer algorithm is known to solve the {\$}{\$}{\backslash}textsf{\{}DCP{\}}{\$}{\$}in {\$}{\$}O{\backslash}left( {\backslash}log {\{}N{\}} {\backslash}right) {\$}{\$}queries, it runs inefficiently in time {\$}{\$}O{\backslash}left( N {\backslash}right) {\$}{\$}. The first time-efficient algorithm was introduced (and later improved) by Kuperberg (SIAM J. Comput. 2005). These algorithms run in a subexponential amount of time and queries {\$}{\$}{\backslash}tilde{\{}O{\}}{\backslash}left( 2^{\{}{\backslash}sqrt{\{}c{\_}{\{}{\backslash}textsf{\{}DCP{\}}{\}}{\backslash}log {\{}N{\}}{\}}{\}} {\backslash}right) {\$}{\$}, for some constant {\$}{\$}c{\_}{\{}{\backslash}textsf{\{}DCP{\}}{\}}{\$}{\$}.},
address = {Cham},
author = {Remaud, Maxime and Schrottenloher, André and Tillich, Jean-Pierre},
booktitle = {Post-Quantum Cryptography},
date-added = {2024-09-14 16:59:59 +0200},
date-modified = {2024-09-14 16:59:59 +0200},
editor = {Johansson, Thomas and Smith-Tone, Daniel},
isbn = {978-3-031-40003-2},
pages = {505--532},
publisher = {Springer Nature Switzerland},
title = {Time and Query Complexity Tradeoffs for the Dihedral Coset Problem},
year = {2023}}