Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Algorithm
2.1.
Generic Algorithm
2.2.
Discrete Logarithm Problem
3.
Lower Bounds on the complexity of Generic Algorithms In Cryptography
4.
Frequently Asked Questions
4.1.
What are algorithms used for?
4.2.
In cryptography, what is a discrete logarithm problem?
4.3.
Is the discrete logarithm problem complex?
4.4.
What is the discrete logarithm assumption?
5.
Conclusion
Last Updated: Mar 27, 2024

Lower Bounds on the complexity of Generic Algorithms In Cryptography

Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

The contemporary name for a problem-solving technique, algorithm, is often used nowadays for the rules that a machine, particularly a computer, must follow to achieve a specific objective. It is not necessarily applicable to computer-mediated activities. This article discusses how the lower bounds on the complexity of generic algorithms work. Let's get started.

Lower Bounds on the complexity of Generic Algorithms In Cryptography

Algorithm

An algorithm composes well-defined instructions for solving a specific issue in computer programming. 

Example:

An algorithm for multiplying two numbers:

  • Consider two numerical inputs.
  • Using the * operator.
  • Multiply two integers together.
  • Display result.

Generic Algorithm

A generic algorithm accepts a collection of inputs and outputs the desired result since it is not dependent on any attribute of the group's representation. 

  • A generic algorithm may be used with any encoding. 
  • It is also a general-purpose algorithm. 
  • It makes no use of any representation characteristic of the group elements. Each element of the group has its representation.

Shanks' algorithm, the Pollard-Rho algorithm, and the Pohlig-Hellman algorithm are a few examples of generic algorithms for the discrete logarithm issue. 

Discrete Logarithm Problem

Logarithms that are groups of multiplicative cyclic groups are referred to as discrete logarithms. 

If "A" is a multiplicative cyclic group and "a" is a generator of "A," then every element h in "A" may be expressed as an ax for any x, according to the definition of cyclic groups. The element of x is the discrete logarithm to the base "a" of h in group A. It finds the discrete logarithm to the base "a" of h in group A given a group A, a generator "a" of the group, and an element h of A. 

The difficulty of obtaining discrete logarithms varies according to the groupings. For example, Zp*, where p is a prime number, is a frequent group choice for discrete logarithm-based cryptosystems.

By definition, the discrete logarithm issue occurs in a cyclic subgroup of order n, which is isomorphic and is well known and very straightforward to establish. It means that we may be able to solve the discrete logarithm issue in any subgroup of order n of any group A by "reducing" the problem to the easily solvable version in (Zn, +).

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Lower Bounds on the complexity of Generic Algorithms In Cryptography

Lowering bounds on the complexity, in other words, means reducing the complexity of generic algorithms solving in discrete logarithms about cryptography. The discrete logarithm issue identifies the number such that αa ≡ β (mod n). α has a multiplicative inverse modulo n. We can compute α −1 mod n with the extended euclidean algorithm. We can solve a, yielding logα β = βα−1 mod n. This is quite similar to the random oracle model, which considers a hash function to be a random function to establish an idealized model from which formal security proofs may be produced.

In the unknown group order of the root extraction issue for finite Abelian groups, lowering the complexity is trouble. This is a natural extension of the RSA ciphertext decryption issue.

The difficulty of this problem for generic algorithms—that is, for algorithms that operate on any group without relying on any unique characteristics of the group under consideration—is always the same.

Even though the method may be able to select the "public exponent" itself, we need to demonstrate an exponential lower constraint on the general complexity of root extraction. In other words, the strong RSA and standard RSA assumptions are demonstrably accurate regarding genetic algorithms.

The findings apply to arbitrary groups; therefore, protection from general assaults follows for any root-extraction-based cryptographic design.

Frequently Asked Questions

What are algorithms used for?

Algorithms provide instructions for solving a problem or accomplishing a task. Algorithms are used in computer coding and help in powering the internet.

In cryptography, what is a discrete logarithm problem?

The discrete logarithm problem is described as finding the discrete logarithm of base g of h in group G. Discrete logarithm problems are relatively straightforward. The difficulty of obtaining discrete logarithms varies according to the groupings.

Is the discrete logarithm problem complex?

While the DLP is widely regarded as a "hard problem," its complexity is determined not by the group's order (or structure) but by how the group is explicitly represented.

What is the discrete logarithm assumption?

The one more-discrete logarithm assumption (OMDL) underpins the security analysis of identification protocols, blind signatures, and multi-signature methods, such as blind schnorr signatures and the newer MuSig2 multi-signatures.

Conclusion

This article discusses how the lower bounds on the complexity of generic algorithms work.

To learn more about cryptography, check out the following articles.

 

To learn more about DSA, competitive coding, and many more knowledgeable topics, please look into the guided paths on Coding Ninjas Studio. Also, you can enroll in our courses and check out the mock test and problems available to you. Please check out our interview experiences and interview bundle for placement preparations.

Happy Learning!

Previous article
Calculus but Index Calculus Method
Next article
Galois Field in Cryptography
Live masterclass