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
1
vote
1
answer
499
views
What is meant by - computational complexity $2^x$?
Recently Bi-clique Cryptanalysis allowed to obtain following results on full AES ES that claim to have
The first key recovery attack on the full AES-128 with computational
complexity $2^{126.1}$
The ...
- 323
6
votes
1
answer
3k
views
Why does applying 56-bit DES twice only give 57 bits of security? [duplicate]
Given two 56-bit keys, $k_1$ and $k_2$, why does $E_{k_1}(E_{k_2}(M))$ only give 57 bits of security?
So basically I'm unsure why it only gives 57 bits of security; I understand that one key will ...
- 171
19
votes
1
answer
10k
views
uniform vs. non-uniform PPT
I'm trying to understand PPT and in particular what the differences are in uniform and non-uniform PPT's. First, this is how I see it:
A probabilistic polynomial-time (PPT) algorithm $A$ is an ...
- 475
1
vote
1
answer
3k
views
Why is AES unbreakable?
Why is it said that AES is unbreakable? Brute force attacks would take years to crack it, so is it possible to crack it if the computational speed of machines increase in the following decade?
- 23
0
votes
1
answer
101
views
One-one correspondance complete function
I am reading the paper by John B. Kam and Georges I. Davida (1979) titled Structured Design of Substitution-Permutation Encryption Networks.
On page 749 it reads ...
- 323
2
votes
1
answer
6k
views
Differences between Work Factor and Time Complexity
I am interested to know if work factor means the same thing as time complexity.
Quoting Work Factor : Uncovering keys in cryptosystems
The Work Factor of a cryptosystem is related to its key-...
- 198
-1
votes
2
answers
3k
views
Is the complexity of Caesar (shift) ciphers “n * n!”?
Can we say that any shift cipher to be decrypted needs an algorithm of complexity “n * n!”? (where n is number of possible ...
- 323
0
votes
2
answers
1k
views
How fast would a polynomial time factoring algorithm compute?
I know factoring is the chief means of breaking RSA keys. I know an algorithm that runs in polynomial time would be able to break an RSA key pair "quickly". But how quickly is "quickly"? Note, I'm not ...
- 3,635
0
votes
1
answer
309
views
How much (home PC) CPU time is required to generate a prime number of a given size?
How much CPU time is required on a typical home computer to generate a prime number of size 100 bit, 200 bit , 512 bit and 1024 bit using given random bits of the respective sizes?
Please note that ...
3
votes
1
answer
372
views
Is xgcd faster than Fermat for calculating $d$ in RSA?
I want to calculate $d$ from $e$ when generating RSA keys.
What is faster?
Calculating $\operatorname{xgcd}(e,p)$ and $\operatorname{xgcd}(e,q)$ and CRT.
Or calculating $e^{p-2}\bmod p$ and $e^{q-2}\...
- 1,535
1
vote
0
answers
62
views
Asymmetric encryptions' computational complexity [duplicate]
I need to know the computational complexity of the public key encryption (e.g. Paillier), please.
(i.e.Paillier in his paper mentions that the computational complexity of most of public key ...
- 805
3
votes
2
answers
843
views
Proving that a function is not invert-able (one way function)
I am having problems with proving if the one-way function (https://crypto.stackexchange.com/tags/one-way-function/info) is hard to invert or not.
$2^\sqrt {m} $ one-way function $ f: \{0, 1\}^{2m} \...
2
votes
1
answer
952
views
DES-X , computation load and storage
The passage said that the computational load to attack DES-X can be reduced to approximately $2^{(56+64)}=2^{120}$ steps,and the storage of data sets should be $2^{64}$.
But I can't figure why it is ...
- 23
1
vote
0
answers
391
views
Complexity of verifying OTP secret
What is the minimum number of unique pairs of digests and inputs to a one-time pass needed to verify that a secret is equal to a ...
- 289
0
votes
4
answers
2k
views
Solution with high decryption cost and low encryption cost
I am looking for any cryptographic solution that will meet those requirements :
Only known method to get the encrypted string need to be brute force.
Decrypting on modern computer not more than ...
- 57
4
votes
2
answers
1k
views
Computational Complexity - When is it really exponential time?
I'm currently working on the discrete logarithm problem and the relevant attacks. I'm fine on the mathematical side of things, but when it comes to estimation of running times I run into problems. ...
- 75
2
votes
1
answer
1k
views
How to calculate complexity of ElGamal cryptosystem?
How to calculate time and space complexity of ElGamal encryption and decryption as there are two exponentiation operation during encryption and one during decryption? Here is my code for encryption:
<...
- 711
4
votes
1
answer
394
views
Is it a good idea to use Lagrange/Newtonian interpolation for encryption?
I see that Lagrange interpolation is commonly used for secret sharing, but could it be used for encryption?
The goal is to reduce database I/O and compute new values on the fly. Suppose the use case ...
- 473
9
votes
1
answer
7k
views
What does it mean for an adversary to run in PPT?
I've been reading this question where a detailed description of mine is given, I've understood that a polynomial-time adversary is an adversary for which the only feasible strategy are those that take ...
- 3,922
2
votes
1
answer
844
views
How to calculate bit strength of Integer Factorization Cryptography (IFC) such as RSA using Python
I would like to know how to calculate the bit-strength of Integer Factorization Cryptography (IFC) such as RSA by using Python. I gathered it is based off the complexity of factorizing the modulus (...
- 35
1
vote
1
answer
1k
views
PRG existance and P versus NP
how can we prove that if there is a secure PRG then P!=NP or in reverse order?(is there any reduction?)
a secure PRG is a pseudo random generator that for every eficient (running in probabilistic ...
- 429
2
votes
1
answer
2k
views
ECC Complexity order of point addition, scalar point multiplication and selecting random point
I am facing this problem in calculating the order of a process which involves ECC point addition: $P+Q$ , scalar multiplication: $aP$, and selecting random points in the group. The group is of prime ...
- 21
2
votes
1
answer
359
views
Explanations for the complexity values for second preimage attack on GOST?
I've been reading the article "A (second) preimage attack on the GOST hash function" by F. Mendel et al (link) and I'm having some difficulty to grasp some of the values of complexities/probabilities ...
- 101
3
votes
1
answer
504
views
Will non-ECC algorithms like RSA eventually become too inefficient?
The strength of symmetric and asymmetric encryption schemes scales with the key length, but there is a difference between symmetric algorithms like AES and asymmetric algorithms like RSA.
For example,...
- 1,778
5
votes
2
answers
1k
views
Can we say that if $P=NP$ there is no CPA secure public key encryption?
I've learned that public key encryption is based on the problem of Discrete Log (as regard to group theory) which believed to be hard.
But, can we say that it doesn't matter on which problem our ...
- 2,130
4
votes
1
answer
2k
views
Solve a Modular Exponentiation
It might be common, but if we had to solve an equation like this $m=s^{e}$ mod $n$ where $m,e,n$ are known. How can we find $s$. What optimisations could be applied? And what would the complexity of ...
- 147
3
votes
1
answer
1k
views
Brute force attack expected running time
I am a bit confused about the expected running times of brute force attacks on different cryptosystems.
So let's assume a key size of $2^n$ bits.
Symmetric key cryptography:
$E(brute)$ = $2^{n-1}\...
- 201
7
votes
1
answer
1k
views
Fully Homomorphic Encryption over the Integers - Runtime Question
I have a question regarding the paper "Fully Homomorphic Encryption over the Integers"
(http://eprint.iacr.org/2009/616.pdf): On page 6 after they set their parameters, it says
"This setting results ...
- 73
2
votes
1
answer
450
views
McEliece Public Key Encryption
The definition of Public Key Encryption(PKE) say that:
A PKE scheme is a triple of probabilistic polynomial time algorithm (PPT) (Gen,Enc,Dec).
The definition of PPT say:
In complexity theory, ...
- 2,661
1
vote
0
answers
146
views
How to develop a public key cryptosystem based on a hard problem? [closed]
Recently, I found a function that is performed on a sequence to return another sequence. All known algorithms for finding the input, given the output are of exponential complexity. I want to propose ...
- 265
2
votes
1
answer
1k
views
Why does Merkle's Puzzle requires Eve quadratic complexity of effort to break the system?
The way Applied cryptography 2ED explains the puzzle is as follows (I paraphrase it):
Bob generates 2^20 messages of the form x,y where ...
- 333
4
votes
1
answer
396
views
Complexity class of an idealised version of Bitcoin's proof-of-work (hashcash)? [closed]
To formulate this question precisely, I will define an idealized hypothetical "perfect" hash function $H(n)$ which has nice scalability properties, and will formulate a problem PERFECT HASHCASH in ...
- 149
7
votes
1
answer
720
views
Formal definition of "explicit" algorithm?
A long time ago, I read that the definition of "cryptographic hash function" is "collision-resistant one-way function". (A similar definition shows up in the FIPS standards for SHA-1 etc.)
But this ...
- 1,378
1
vote
2
answers
287
views
One-way function and $EXP$
All examples of one-way functions I have see till now are closely related to the assumption that $NP\neq P $ (or even weaker ones, such as $UP\neq P$), but why not considering the theorem $P\neq EXP$? ...
10
votes
2
answers
3k
views
Why is the complexity of RSA-1024 80 bit and not 86 bit?
Why is the complexity of RSA-1024 80 bit and not 86.76611925028119 bit?
Here is the complexity for the GNFS (pulled from the linked Wikipedia
article):
$$\exp\left( \left(\sqrt[3]{\frac{64}{...
- 425
7
votes
2
answers
3k
views
Meet-in-the-middle with checking complexity
In regards to meet in the middle type attacks, I have been considering the amount of operations in order to successfully find a key given two sets of plaintext / ciphertext pairs. All of the sources I ...
- 95
6
votes
2
answers
926
views
Is there any research about cryptography on nondeterministic Turing machines?
I know it's a highly theoretical topic, but I was wondering if there was any research out there about what cryptography would be like assuming that we had access to nondeterministic Turing machines.
...
- 81
6
votes
3
answers
1k
views
Parallel-resistant proof-of-work scheme?
I am looking for a proof-of-work scheme which cannot be effectively parallelized.
For example, in hashcash (and by extension bitcoin) you have some collision-resistant hash function $f()$, a target $...
- 2,548
4
votes
1
answer
2k
views
What is meant by $\tilde\Omega(\lambda^4)$?
I'm currently reading the paper (Leveled) fully homomorphic encryption without bootstrapping , and the following paragraph was near the start:
What is meant by the symbol used? Is it merely to ...
- 207
7
votes
3
answers
5k
views
P = NP and current cryptographic systems
I've recently heard some people claiming that if the fact that P = NP is proven, most (all?) the current cryptographic algorithm considered secure like RSA will be unusable in secure systems.
My ...
- 205
13
votes
1
answer
4k
views
What does "running in polynomial time" really mean?
I'm currently learning private-key cryptography. I've been able to see that perfect secrecy is achievable if no assumption is made about the computational power of the attacker.
However, perfect ...
- 231
8
votes
3
answers
584
views
Pen-and-paper one-way function for externally-anonymous survey
When conducting surveys, an Administrator might send an Enumerator to survey a Respondent. For "sensitive" questions (e.g. about embarrassing behavior), the Respondent may be fine with the truth being ...
0
votes
2
answers
296
views
Is solving a modular linear equation a hard problem when the coefficient is not an invertible element?
Assume that we have a linear equation like this:
$$ax=b \pmod n$$
when $x$ is the unknown, and $a$ is not an invertible element in $n$.
is finding $x$ a hard problem?
(by solving I mean finding an ...
- 951
3
votes
1
answer
18k
views
How do I derive the time complexity of encryption and decryption based on modular arithmetic?
I want to calculate the time complexity of two encryption and decryption algorithms.
The first one (RSA-like) has the encryption
$$ C := M^e \bmod N $$
and decryption
$$ M_P := C^d \bmod N. $$
...
- 151
1
vote
2
answers
584
views
Cryptographic Symmetric Stream Cipher
Let me know a cryptographic symmetric stream cipher system with only two functions say S() and P() and it should satisfy the ...
- 71
5
votes
1
answer
3k
views
How can I calculate the time complexity of modular arithmetic?
I'm doing modular arithmetic in a Java program, and I want to calculate the time complexity of the individual operations.
$$ c= a · b \bmod n $$
$$ m = a^{-1} · b \bmod n $$
How do I get an ...
- 151
5
votes
0
answers
115
views
P-Complete hashes, hashing to a larger set
Historically hashes have been from a large set (say 256 characters) to a smaller set (256 bits).
Also, hash functions that are P-complete have no known parallel algorithm; they must be computed ...
- 151
6
votes
3
answers
292
views
Polynomials and efficient computability
In public key crypto, the popular definitions of security (CPA, CCA1,2) depend on PPT adversaries. I'm trying to understand why adversaries should be PPT.
It's clear that adversaries should be at ...
- 161
4
votes
2
answers
475
views
iterated discrete log problem
Consider the following problem: given $g_1 \ldots g_i,h_1 \ldots h_i \in G$, $\forall i$ find $x_i$ such that $g_i^{x_i}=h_i$
For $i=1$ this is the discrete log problem and is assumed to to have ...
- 1,614
9
votes
1
answer
3k
views
A discrete-log-like problem, with matrices: given $A^k x$, find $k$
Let $p$ be a large prime; we will work in $GF(p)$. Let $A$ be a $n\times n$ matrix. Also, let $x$ be a $n$-vector and $k$ a positive integer.
Suppose we are given $p$, $A$, $x$, and $y$. The goal ...
- 36.2k