Discrete Logarithm and Minimum Circuit Size

This paper shows that the Discrete Logarithm Problem is in ZPPMCSP (where MCSP is the Minimum Circuit Size Problem). This result improves the previous bound that the Discrete Logarithm Problem is in BPPMCSP, shown by Allender et al. [1]. In doing so, this paper helps classify the relative difficulty...

Full description

Saved in:
Bibliographic Details
Published in:Information processing letters 2017-12, Vol.128, p.1-4
Main Author: Rudow, M.
Format: Article
Language:English
Subjects:
Computational complexity
Discrete logarithm problem
Minimum circuit size problem
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:This paper shows that the Discrete Logarithm Problem is in ZPPMCSP (where MCSP is the Minimum Circuit Size Problem). This result improves the previous bound that the Discrete Logarithm Problem is in BPPMCSP, shown by Allender et al. [1]. In doing so, this paper helps classify the relative difficulty of the Minimum Circuit Size Problem. •This paper proves that DLP∈ZPPMCSP.•The proof follows the structure of a known proof that DLP∈BPPMCSP, shown by Allender et al. [1].•The proof improves the previous result by finding a generator and only computing discrete logarithms with respect to it.
ISSN:0020-0190
1872-6119
DOI:10.1016/j.ipl.2017.07.005