Skip to main content

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.

48 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
10 votes
0 answers
163 views

Hardness of iterated squaring in Paillier group

The (computational) problem of iterated squaring (IS) in the RSA group is defined as follows, where $\leftarrow$ denotes sampling uniformly at random: Input: $(N,x,T)$, where $N$ is the RSA modulus, $...
ckamath's user avatar
  • 5,348
9 votes
0 answers
804 views

Can LWE be NP-hard?

Regev's reduction shows that LWE is quantumly at least as hard as CVP with an approximation factor of $n/\alpha$ for $0<\alpha<1$. But I just watched this talk which said that if $\sqrt{n/\log n}...
Sam Jaques's user avatar
  • 1,202
6 votes
0 answers
191 views

What are the theoretical memory requirements for these factoring algotihms?

Given an $n$ bit integer quadratic sieve takes $L(\frac12,1+o(1))$ time and number field sieve takes $L(\frac13,1.922)$ time where $L$ notation is given in https://en.wikipedia.org/wiki/L-notation. ...
Turbo's user avatar
  • 930
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 ...
Chad Brewbaker's user avatar
4 votes
0 answers
97 views

Is $g(x_1||x_2) = f(x_1 \wedge x_2)$ a one way function assuming f is a one way function

Intuitively I think not because assuming the bit string $x_1,x_2 \sim \{0,1\}^{n/2}$, $x_1 \wedge x_2$ is not uniformly random so if $g$ were still a one-way function then the fact that the definition ...
CHTM's user avatar
  • 141
4 votes
0 answers
338 views

Cryptomania and NP $\cap$ co-NP

Cryptomania is usually presented as the Impagliazzo's world, which gives us public-key cryptography under the assumption that trapdoor OWFs exist. For purposes of constructing public-key cryptography ...
Ilk's user avatar
  • 233
4 votes
0 answers
143 views

If trapdoor OWF exists then f is a trapdoor OWF, is there such a construction?

Is there a known construction of f, such that given that a trapdoor OWF exists then f is a trapdoor OWF, so we can construct inefficient cryptomania, ala Levin's construction for minicrypt in "The ...
Ilk's user avatar
  • 233
4 votes
0 answers
175 views

How many reversible gates would DES require?

How many reversible gates (said counting Toffoli and Controlled NOT, with free NOT) would be required to reversibly implement $(K,P)\mapsto(G,C)$ for the block cipher DES? $P$ is the plaintext, $C$ ...
fgrieu's user avatar
  • 142k
4 votes
0 answers
91 views

Computing cost for a trillionaire to compute GNFS in RFC 3766

RFC 3766, Section 4.1 discusses picking $n$ to achieve some target cost for employing the GNFS, i.e., $T$ is known and $N$ is unknown in the below equation: $$T = \kappa \cdot \exp{\left(c \cdot (\ln{...
GermaneDork's user avatar
3 votes
0 answers
72 views

A highly space-efficient embedding of prime factorization problem using the Ising model

I hope this is not off-topic for this SE, as it directly relates to the RSA problem. My background is in quantum information and computation, so please excuse me if my notation doesn't match your ...
Amirhossein Rezaei's user avatar
3 votes
0 answers
324 views

Group Rings on Cryptography

Let $R[G]$ or $RG$ be the group ring where $R=F_q$ and $G$ is any group. Let $Dim(V)=\vert G \vert$. It's clear that $V$ has $\vert R \vert^{\vert G \vert}$ distinct $\vert G \vert$-tuples. This ...
kub0x's user avatar
  • 898
3 votes
0 answers
225 views

Reduction from integer factoring to computational Diffie Hellman

The computational Diffie Hellman (CDH) problem for ${\mathbb{Z}}^*_p$ is given a prime $p$, a generator $g$ of ${\mathbb{Z}}^*_p$, and a pair $(g^i, g^j)$ to compute $g^{ij}$. The value $g$ is called ...
duckstar's user avatar
  • 269
3 votes
0 answers
281 views

Majority encryption algorithm?

Assume that I want to leave an encrypted message to a group of $n$ people in a way that they can only decrypt it if they work together in the following sense: For some fixed $k < n$ every sub-...
Listing's user avatar
  • 131
2 votes
0 answers
29 views

Sequences over groups and multiplicative recurrences

Feedback shift registers (FSRs) with nonlinear feedback function produce recurring sequences which satisfy polynomial recurrence relations defined by the feedback function. If the register cells are ...
Viren Sule's user avatar
2 votes
0 answers
55 views

Inefficient double-lengthening PRG

I'm trying to prove that an inefficient double-lengthening PRG exists, i.e. construct a PRG $G: \{0,1\}^n \rightarrow \{0,1\}^{2n}$ My current approach is to bound the number of poly-time non-uniform ...
Stevie's user avatar
  • 123
2 votes
0 answers
150 views

Detailed running time analysis for Shamir secret sharing scheme

I am successfully working on Shamir's secret sharing scheme for few months. But the only issue I am facing is the calculation of theoretical time complexity. Since I am from algorithmic background, I ...
Fateh's user avatar
  • 107
2 votes
0 answers
175 views

Depth of $\operatorname{SHA-256}$ implementation by fan-in $2$ and fan-out $1$ Boolean circuits?

A fan-in $2$ and fan-out $1$ Boolean circuit is a circuit consisting of $\operatorname{AND}$, $\operatorname{OR}$ and $\operatorname{NOT}$ gates where number of inputs to $\operatorname{AND}$ and $\...
Turbo's user avatar
  • 930
2 votes
0 answers
72 views

Balanced Feistel networks: Are there any lower bounds on the computational complexity of breaking a $k$-round Feistel cipher?

This paper by Patarin presents an attack (section 9) on balanced Feistel networks with $k$ rounds, where the input is a bit-string is of length $2n$. (Since it is balanced, this means each PRF takes ...
Daniel-耶稣活着's user avatar
2 votes
0 answers
690 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 ...
Aydin's user avatar
  • 442
1 vote
0 answers
73 views

What exactly is the RAM program runtime?

In my previous understanding, if a RAM program requires $T$ read/write operations to memory during its execution, then the runtime of this RAM program is $T$. However, as I have read some literature, ...
Emison Lu's user avatar
  • 112
1 vote
0 answers
36 views

A problem related to three outputs of the majority function for nine rotations of three bitstrings

Let $r(b,t)$ denote the bitstring $b$ rotated to the left by $t$ bits: for example, $$r(00110101,5)=10100110.$$ Let $m(b_1,b_2,b_3)$ denote the majority function: for example, $$m(10010111,00101110,...
lyrically wicked's user avatar
1 vote
0 answers
39 views

Find Linear Complexity of sequence beginnings

I know that in order to find the linear complexity of the two sequence beginnings $$(1,-1,0,-1,0,0,0,0,1,0,\dots)\in\mathbb{Z}_3^\mathbb{N}\\ (2,0,-1,-2,0,0,-2,2,-1,-2,\dots)\in\mathbb{Z}_5^\mathbb{N},...
stack_math's user avatar
1 vote
0 answers
87 views

Comparing complexity of RSA decryption with/without CRT

(Cross-listed on math stackexchange, received no replies) For context, this is a homework question from an assignment already turned in. I am looking for better understanding of the concepts involved, ...
mrose's user avatar
  • 111
1 vote
0 answers
64 views

How efficiently can an attacker forge parts of a fingerprint?

If two devices do not trust each other yet, you can't simply send the correct fingerprint across: you have to manually verify it. I am looking into the security of comparing only random parts of a ...
Sazed's user avatar
  • 11
1 vote
0 answers
59 views

Can Trivium ciphertext be decrypted by an adversary if the key is known, but the IV is not?

Suppose that the adversary is able to recover the key of Trivium cipher. But the associated IV is unknown to him. Will he be able to decrypt the ciphertexts without any complexity?
Ans's user avatar
  • 73
1 vote
0 answers
31 views

Help with next step in the Quadratic Sieve

So I am at the same step as someone from math.stackexchange but he never recieved an answer so I will copy-paste his question here: Say, for N = 90283, I compute bound 𝐵=𝑒(12+𝑜(1))(ln(𝑛)ln(ln𝑛√))...
aayush Lak's user avatar
1 vote
0 answers
60 views

Why is this attack complexity equal that exact number of bit operations?

in the this paper,section 3,autors attack hamsi-256. Im trying to make a parametrized version, so i need to understand how do they estimate the complexity of attack in bit operations,that reads as ...
Kirill's user avatar
  • 55
1 vote
0 answers
78 views

'random' function $r_{n+1} = f(r_n)$, $|\{r_i,\forall i\}|=N$, $r_N = r_1$ where a function $g(r_k)=k$ is harder than in ECC?

Is there a deterministic pseudo random function $f$ with $r_{n+1} = f(r_n)$, $|\{r_i,\forall i\}|=N$, $r_N = r_0$, (for given random initial value $r_0$) where a function which derives the index of a ...
J. Doe's user avatar
  • 453
1 vote
0 answers
111 views

What if an AES Whitebox 1024-bit (or larger key) is created? Does it increase complexity consistently?

Following the Chow et al paper and Muir's tutorial, I was able to implement the AES algorithm using tables embedding keys of 128, 192 and 256-bit sizes, later extended to 1024, 2048 and 4096-bit sizes....
Guilherme Balena Versiani's user avatar
1 vote
0 answers
240 views

Time complexity of Euler's totient function

I believe there are different time complexities for Euler's totient function depending on how you execute the algorithm. The two I know of are: Iterate through 1 to k and calculate each $\gcd$: $O(n \...
dkssud10's user avatar
  • 125
1 vote
0 answers
75 views

Complexity of arithmetic in (the integer ring of) a number field?

What is the running time complexity (average or worst case) of common arithmetic operations in number fields? In fact, I'm only interested in the integer ring of the quadratic extension $\mathbb{Q}[\...
gen's user avatar
  • 143
1 vote
0 answers
219 views

Double encryption : what method is the best?

Given the block-ciphers defined as follows : $1.$ $C=$ $E_{k1}($$E_{k2}$$(M))$ $2.$ $C=$ $E_{k1{\oplus}k2}$$(M)$ $3.$ $C=$ $(E_{k1}(r),E_{k2}(r$ ${\oplus}$ $M))$ where $C$ is the cipher ...
Joseph's user avatar
  • 11
1 vote
0 answers
65 views

Computation complexity of modified Euclidean algorithm

The computational complexity of the extended Euclidean algorithm is $O(log(b)^2)$ ($b$ being the second integer) as referenced by Wikipedia. How to compute the complexity of the modified extended ...
Mosen's user avatar
  • 43
1 vote
0 answers
74 views

Complexity lower bound in Uber-Assumption family

I try to wrap my head around calculating of complexity lower bound using Corollary 1 from The Uber-Assumption Family by X.Boyen (http://www.academia.edu/download/30698012/...
Przemko Robakowski's user avatar
1 vote
0 answers
397 views

Time complexity of birthday attack type problem

I have two sorted lists: $A=\{a_1, \ldots, a_n\}$ and $B=\{b_1, \ldots, b_m\}$. I know that the probability of $a_i=b_j$ is $c$ for $1 \leq i \leq n$ and $1\leq j \leq m$. The time complexity of ...
user15864's user avatar
  • 229
1 vote
0 answers
26 views

Use of elapsed execution time as a variable input

Given that, with a significant number of decimals, it may be difficult to predict elapsed execution time of a piece of code, despite having knowledge of exact hardware and software specifications; is ...
user39783's user avatar
1 vote
0 answers
33 views

Weakly Sublinear Compact FE from Succinct FE and XiO

I'm confused about a problem these days and I decided to seek an answer here. The question is about the section 4.1 of the paper LPST16. Let me recall the weakly sublinear compact FE scheme $\textrm{...
CryptoLover's user avatar
1 vote
0 answers
250 views

Best/average/worst-case complexity for cryptography

I understand that the complexity of a problem can be measured by it's best-case, average-case, or worst-case complexity. Am I correct in thinking that, for cryptographic purposes, each of these is of ...
MattBurrows's user avatar
1 vote
0 answers
397 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 ...
Brian M. Hunt's user avatar
0 votes
0 answers
67 views

Difficulty of factoring large semiprime N if given a second value y = (p-1)*r, where r is a random large prime?

Lets say we have 2 public values: N and y $$ N = pq $$ $$ y = r(p-1) $$ Where p, q, and r are large primes, are different, have a large distance between them and are kept secret. I have three ...
block103's user avatar
0 votes
0 answers
55 views

What do we mean when we say we need more than polynomial time many cipher texts

What does it mean when we say something like „we need more than polynomial time many cipher texts“? I understand it as „an adversarial can run for polynomial time and try as many messages as possible ...
jilgolfo's user avatar
0 votes
0 answers
192 views

Speed comparison of encryption algorithms

I am trying to compare various encryption algorithms in terms of encryption duration, decryption duration, information entropy, NPCR, UACI, and correlation coefficients. I used a Lena 256x256 ...
ysnky's user avatar
  • 1
0 votes
0 answers
90 views

Which contemporary programming language is apt for implementation of algorithms in cryptography?

I am a researcher in cryptography. Most of the time I generally do theoretical/Mathematical work only and not doing the implementation part. I am not able to get the feel about the time complexity of ...
Natwar's user avatar
  • 441
0 votes
0 answers
39 views

Number of bit operations required for encryption in a Block cipher

I want to find out how many bit operations are performed for encryption in AES-128 with messages size $128$ bits. For public key encryptions such as RSA and ElGamal, I know that number of bit ...
PAMG's user avatar
  • 161
0 votes
0 answers
58 views

Composing subexponential L-function

Suppose $y=f(x)$ and $z=g(y)$ such that $y\in L_x[a,b]$ and $z\in L_y[c,d]$, where $L$ is the usual sub-exponential asymptotic notation $$L_x[a,b] = \exp\left((b+o(1))(\log x)^a(\log\log x)^{1-a}\...
Sam Jaques's user avatar
  • 1,202
0 votes
0 answers
45 views

How to Solve Discret Log Computation Problem

Given $g^a$ in $Z_p$, it is hard to get the solution $a$. Everyone says yes, I wonder why it is hard. Could anyone give a specific mathematical way to show it is indeed hard?
bono_silhouette's user avatar
0 votes
0 answers
79 views

If finding a private key from a public key is [co-]NP-complete, does NP=co-NP?

In a given public key cryptosystem, if the problem of determining the private key from the public key is NP-complete or co-NP-complete, does that imply that NP = co-NP? Complexity theory is ...
Myria's user avatar
  • 2,605
0 votes
0 answers
207 views

Random self-reducibility and NP

I was reading the Wikipedia page https://en.m.wikipedia.org/wiki/Random_self-reducibility and it states: "If an NP-complete problem is non-adaptively random self-reducible the polynomial hierarchy ...
Meir Maor's user avatar
  • 11.8k