TY - JOUR
T1 - CONSTRAINED INHOMOGENEOUS SPHERICAL EQUATIONS
T2 - AVERAGE-CASE HARDNESS
AU - Ushakov, Alexander
N1 - Publisher Copyright:
© 2024, Episciences. All rights reserved.
PY - 2024
Y1 - 2024
N2 - In this paper we analyze computational properties of the Diophantine problem (and its search variant) for spherical equations (Formula presented (and their variants) over the class of finite metabelian groups (Formula presented), where n ∈ N and p is prime. We prove that the problem of finding solutions for certain constrained spherical equations is computationally hard on average (assuming that some lattice approximation problem is hard in the worst case).
AB - In this paper we analyze computational properties of the Diophantine problem (and its search variant) for spherical equations (Formula presented (and their variants) over the class of finite metabelian groups (Formula presented), where n ∈ N and p is prime. We prove that the problem of finding solutions for certain constrained spherical equations is computationally hard on average (assuming that some lattice approximation problem is hard in the worst case).
KW - average case complexity
KW - finite groups
KW - group-based cryptography
KW - hash function family
KW - metabelian groups
KW - semidirect products
KW - Spherical equations
UR - http://www.scopus.com/inward/record.url?scp=85199277371&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85199277371&partnerID=8YFLogxK
U2 - 10.46298/jgcc.2024.16.1.13555
DO - 10.46298/jgcc.2024.16.1.13555
M3 - Article
AN - SCOPUS:85199277371
SN - 1867-1144
VL - 16
SP - 3:1-3:18
JO - Groups, Complexity, Cryptology
JF - Groups, Complexity, Cryptology
IS - 1
ER -