# Tag Info

Accepted

### Is it hard to compute $g^{ab}$ when given $(g, g^a, g^b, \frac{a}{b})$?

It is indeed a hard problem - in fact, it is at least as hard as the square Diffie-Hellman problem (SDH), which states that given $(g,g^a)$, it is infeasible to compute $g^{a^2}$. It is a standard and ...
• 20.7k
Accepted

### How does a non-prime modulus for Diffie-Hellman allow for a backdoor?

I've since then wrote a paper to answer this question (of course with a huge help from Poncho) I found many ways to implement a backdoor, some are Nobody-But-Us (NOBUS) backdoors, while some are not (...
• 1,565
Accepted

### Is it possible to generate backdoored DH parameters?

A trapdoor in a discrete log group was first suggested in 1992 by Daniel M. Gordon[1] in response to the recently proposal by NIST for the Digital Signature Standard (among hundreds of other responses[...
Accepted

### Which properties of a group are used in the steps of Diffie Hellman?

I’m trying to understand which properties of a group are used in DHKE at each step. Actually, you can implement a DH-style operation in any semigroup; you need closure, and you need associativity (...
• 149k

### Non-commutitive and nonassociative algebraic structures in cryptography

A self-distributive algebra is an algebra $(X,*)$ that satisfies the identity $x*(y*z)=(x*y)*(x*z)$. There are several cryptosystems that use self-distributive algebras as platforms and these ...
• 1,245
Accepted

### Concrete example of Montgomery Multiplication

In this answer we study modular multiplications using Montgomery arithmetic, illustrated with the example $7510\cdot 8431\cdot 2143\bmod9137$, working in base $\beta=10$ because the question does. ...
• 144k

### PhD in cryptography using elliptic curves

If you want to end up in the industry, I strongly doubt a PhD is a good investment of your time, regardless of the rest of this discussion. I believe a general purpose quantum computer, the kind that ...
• 11.9k
Accepted

### Why is Approximate GCD a hard problem?

TL;DR The AGCD problem does require asymptotic exponential time to be solved. In general, LLL cannot solve the AGCD problem The parameters $(\gamma, \eta, \rho) = (\lambda^5, \lambda^2, \lambda)$ ...

### Why can every prime number be written as 6k±1?

I am not sure if this question should be considered on topic here, but I will answer anyway. Theorem: All prime numbers larger than $3$ can be written as $6k+1$ or $6k-1$ for some natural number $k$. ...
• 11.9k

### Calculating RSA private exponent when given public exponent and the modulus factors using extended Euclid

A useful way to understand the extended Euclidean algorithm is in terms of linear algebra. (This is somewhat redundant to fgrieu's answer, but I decided to post this anyway, since I started writing ...
• 46.3k

### Calculating RSA private exponent when given public exponent and the modulus factors using extended Euclid

The method in the other answer is didactic, but requires backtracking earlier calculations, and thus having kept these or use of recursion, which is undesirable in constrained environments as often ...
• 144k
Accepted

• 1,357

### Proving the knowlege of e-th root in an non-interactive way

Bad news is that what you ask for is impossible to achieve with the proposed Guillou-Quisquater (GQ) identification protocol. Unfortunately, $\Sigma$-protocols for group-homomorphisms are not ...
• 1,194
Accepted

### Why discrete logarithm modulo composite moduli not popular and not defined in standards?

Such a scheme includes factorization as an additional barrier in case discrete logarithm modulo primes is broken and so why is this not popular and defined in standards? Actually, it would not be an &...
• 149k
Accepted

### Is FFT for power-of-two cyclotomic rings possible if q is not 1 modulo 2n?

Yes, in a way. When $q \neq 1 \mod 2n$ the ring $R_q$ is not fullt splitting (into polynomials of degree one). However, it might be splitting into several smaller polynomials of degree larger than one....