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. ...
5
votes
2answers
121 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
95 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
503 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. $$
...
-1
votes
2answers
175 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 following conditions:
There will be two independent computers say M1 and ...
2
votes
1answer
184 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 ...
1
vote
2answers
94 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
1answer
71 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 ...
3
votes
1answer
180 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 ...
3
votes
0answers
127 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 ...
2
votes
3answers
195 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
246 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.
0
votes
2answers
313 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.
4
votes
4answers
482 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
175 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 ...
1
vote
1answer
697 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 ...
2
votes
3answers
215 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
