Research on attacking a special elliptic curve discrete logarithm problem
type: Item
instance of: scholarly article
title: Research on attacking a special elliptic curve discrete logarithm problem
zbMATH Open document ID: 1400.94176
DOI: 10.1155/2016/5361695
author: Jiang Weng
author: Yunqi Dou
author: Chuangui Ma
published in: Mathematical Problems in Engineering
publication date: 2018-10-12T00:00:00Z
review text: Summary: Cheon first proposed a novel algorithm for solving discrete logarithm problem with auxiliary inputs. Given some points \(P, \alpha P, \alpha^2 P, \ldots, \alpha^d P \in \mathbb{G}\), an attacker can solve the secret key efficiently. In this paper, we propose a new algorithm to solve another form of elliptic curve discrete logarithm problem with auxiliary inputs. We show that if some points \(P, \alpha P, \alpha^k P, \alpha^{k^2} P, \alpha^{k^3} P, \ldots, \alpha^{k^{\varphi(d) - 1}} P \in \mathbb{G}\) and a multiplicative cyclic group \(K = \langle k \rangle\) are given, where \(d\) is a prime, \(\varphi(d)\) is the order of \(K\). The secret key \(\alpha \in \mathbb{F}_p^\ast\) can be solved in \(\mathcal{O}(\sqrt{(p - 1) / d} + d)\) group operations by using \(\mathcal{O}(\sqrt{(p - 1) / d})\) storage.
Mathematics Subject Classification ID: 94A60
zbMATH DE Number: 6953310
Wikidata QID: Q59131560
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1155/2016/5361695
OpenAlex ID: W2475077774
cites work: Q5628224
cites work: Monte Carlo Methods for Index Computation (mod p)
cites work: Parallel collision search with cryptanalytic applications
cites work: Identity-Based Encryption from the Weil Pairing
cites work: Advances in Cryptology - EUROCRYPT 2004
cites work: Collusion Resistant Broadcast Encryption with Short Ciphertexts and Private Keys
cites work: Security Analysis of the Strong Diffie-Hellman Problem
cites work: Discrete logarithm problems with auxiliary inputs
cites work: Analysis on a generalized algorithm for the strong discrete logarithm problem with auxiliary inputs
cites work: Solving a Discrete Logarithm Problem with Auxiliary Input on a 160-Bit Elliptic Curve
cites work: Q3884021
cites work: Q2770573
description: scientific article; zbMATH DE number 6953310