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. ...

learn more… | top users | synonyms

9
votes
1answer
828 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 ...
5
votes
2answers
315 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
2answers
198 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 ...
1
vote
1answer
5k 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. $$ ...
0
votes
2answers
394 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 ...
3
votes
1answer
835 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 ...
3
votes
0answers
68 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 ...
3
votes
2answers
125 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 ...
3
votes
2answers
175 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 ...
4
votes
1answer
363 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 ...
6
votes
1answer
258 views

Finding where I am in a linear recurrence relation

Suppose I have a linear recurrence relation $$a(n) = c_1 a(n-1) + \dots + c_k a(n-k) + d,$$ where the constants $c_1,\dots,c_k,d$ are given and the initial values $a(0),\dots,a(k-1)$ are given as ...
4
votes
3answers
394 views

Discrete log problem, when we have many examples

Suppose I have many instances of the discrete log problem, all using the same unknown exponent. Is this problem easier than the standard discrete log problem? Oh, heck, I should be more precise. ...
1
vote
2answers
784 views

What is the time complexity of the RC4 encryption & decryption algorithms?

I'm trying to figure out what the time complexity of RC4 encryption & decryption algorithms is, in big-O-notation.
1
vote
2answers
493 views

Complexity of ECB and OFB

What is the complexity of ECB in terms of Time and Memory? and also in OFB? I can't find it in the internet, so I decided to ask it in here.
3
votes
3answers
243 views

Are asymptotic lower bounds relevant to cryptography?

An asymptotic lower bound such as exponential-hardness is generally thought to imply that a problem is "inherently difficult". Encryption that is "inherently difficult" to break is thought to be ...
4
votes
1answer
4k views

Big-O Notation: Encryption Algorithms

I am currently completing a dissertation concerning the encryption of data through a variety of cryptographic algorithms. I have spent much time reading journals and papers but as yet have been ...
7
votes
4answers
2k views

What is the largest performed/possible bruteforce attack to date?

I've read that cracking 128-bit key is currently out of reach of all humanity. However, I can't seem to find any information on what scope of brute force attacks have been performed or are possible at ...
3
votes
3answers
925 views

Complexity of arithmetic in a finite field?

I am wondering what the complexities are of adding/subtracting and muliplying/dividing numbers in a finite field $\mathbb{F}_q$. I need it to understand an article I am reading. Thank you