# Questions tagged [complexity]

Complexity describes - in simple words - how hard (complex) it is to reach a specific goal; and under which conditions. In cryptography, this mostly ends up in using the complexity theory to analyze things. One of the main goals of complexity theory is to prove lower bounds on the resources (e.g. time and/or space) needed to solve a certain computational problem. Cryptography can therefore be seen as the complexity theory's main field of use.

258 questions
Filter by
Sorted by
Tagged with
225 views

### More general - what is the hard problem of recovering r from r*p mod q?

I would like to know the cryptographic hard problem that is most closely tied to recovering integer $r$ from the modular product $r\times p\mod q$. (This is a simplification of an earlier post that ...
• 273
1 vote
118 views

### What is the hard problem for this algebraic encryption construct?

I would like to know what cryptographic hard problem this reduces to. Select two large prime numbers $p$ and $q$, and let $N=pq$. Select a random positive integer $r$. Compute the encryption of ...
• 273
435 views

### Average number of multiplications in left-to-right k-ary exponentiation

On page 617 in chapter 14 of The Handbook of Applied Cryptography, the average number of multiplications in left-to-right k-ary exponentiation is $l\times (2^k-1)/2^k$, where $l=\lfloor t/k\rfloor$,...
• 211
612 views

### Computing the powers of hash (ripemd-160) function

Is there a way I can compute $2^{100}$th power of ripemd-160 of my string, just like I can do with square matrix powers? I.e. can I easily compute ripemd-160 large amount of times?
• 23
1 vote
1k views

### What is the cost of encrypting of long message with public-key cryptography?

Let m be a message of arbitrary size, potentially very large. Is it necessary to use larger parameters in the public-key encryption scheme in order for the receiver to decrypt that message? My guess ...
• 258
282 views

• 225
207 views

• 932
119 views

### PRNG output with truly random noise

I am considering a situation where an adversary does not have access to the $n$-bit output string of a PRNG, but instead receives a noisy version of it, where each bit of the string is flipped with ...
1k views

• 499
92 views

### Find a constant $C$ in $O(Cn^2)$?

I am writing a paper on RSA, and I am calculating some encryption running times. I have been told that the encryption running time is $O(n^2)$ where $n$ is the modulus. I have also been told that ...
674 views

### Performance of Fully homomorphic encryption VS Paillier encryption in Practice

Consider two schemes both have computation complexity linear to the input size (i.e. number of inputs). One scheme is based on Paillier encryption and the other one is based on fully homomorphic ...
• 442
827 views

### Usage of Zero-knowledge proofs for NP-complete languages

It is well known that if OWFs/PRGs exist, then there is a zero knowledge proof for any NP-complete language, say G3C (graph coloring in 3 colors). The zero-knowledge notion maintains that any ...
152 views

### DSSP reduction to DSSI

In “Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies" by DeFeo, Jao and Plut, a reduction from the Decisional Supersingular Product (DSSP) problem to Decisional ...
• 502