# Tag Info

10

As you probably know $f(\lambda)=O(\lambda^4)$ means that $|f|$ asymptotically upper bounded by some constant times $\lambda^4$. The notation $f(\lambda)=\Omega(\lambda^4)$ corresponds to an asymptotic lower-bound. Now, the $\tilde O$ and $\tilde \Omega$ are closely related notations, where we not only ignore constants but also values which are polynomial ...

9

Perfect secrecy is achievable in a few cases, such as one-time pads, and, well, that's pretty much it. Most cryptographic protocols are vulnerable to an all-powerful, all-knowing attacker. If you do not put any restriction on what the attacker can do, then Guess the key. Profit. breaks almost any cryptography, as does Wave a magic wand. Profit. So at ...

9

A proof of P = NP would prove that one-way functions do not exist. That in turn would imply, that almost no secure cryptographic primitives can exist according to the accepted definitions of security. (No symmetric encryption, no MACs, no pseudorandom generators, no signature schemes, ...) However, it would just mean that no scheme can be provably secure. ...

8

Presumably, it's because they rounded it down to a nice round number of bits. Nobody's going to use an 86.76611925028119 bit key in practice, but an 80-bit key is plausible. Besides, the 86.whatever bit symmetric key length is only approximate, anyway: even using the GNFS, implementation details could easily swing it several bits either way, and of course, ...

8

What Dan Boneh says is not a formal definition as you want it. Let me quote Rogaway on this: In cryptographic practice, a collision-resistant hash-function (also called a collision-free or collision-intractable hash-function) maps arbitrary-length strings to fixed-length ones; it’s an algorithm $H:\{0,1\}^*\rightarrow \{0,1\}^n$ for some fixed ...

7

There are techniques for doing online surveys on sensitive subjects. They don't follow the approach you outlined, but here's a sketch of how they work. Suppose we want to survey people to determine how many people have ever seriously considered suicide (say), but we suspect many people might be unwilling to answer honestly because of the stigma associated ...

7

When $n$ is prime, solving for $e$-th roots modulo $n$ is easy, since it suffices to compute $d = e^{-1} \pmod {n-1}$ and then $s = m^d \pmod n$. If $n$ is not prime, but is instead a RSA modulus (a composite integer that is the product of two big primes), then the problem becomes apparently hard (in the sense that we don't have a clue how to do it ...

6

The last major effort I know of for cracking keys was the Distributed.net effort. You can find the project page at http://www.distributed.net/RC5/en. In 2002, they cracked a 64-bit RC5 key using at total of 331,252 computers over 1,757 days. Their maximum throughput was "equivalent to 32,504 800MHz Apple PowerBook G4 laptops or 45,998 2GHz AMD Athlon XP ...

6

Most of these algorithms (i.e. the block ciphers DES, Triple DES, AES, Blowfish) are normally only working on a fixed block size, and take approximately the same time independently of input, thus they are $O(1)$. If you put them into a mode of operation to encrypt longer messages, you usually get an $O(m)$ complexity, where $m$ is the message size, as you ...

6

Let $n = \lceil \log q \rceil$ (with "$\log$" being the base-2 logarithm, so $n$ is the size, in bits, of $q$). If $q$ is a prime integer (i.e. $\mathbb{F}_q$ is the field of integers modulo $q$), then classical implementations will have cost $O(n)$ for addition and subtraction, $O(n^2)$ for multiplications and divisions. The cost of multiplications can be ...

6

Well, if $q$ is a prime (and not $p^n$ with $n>1$), then addition, subtraction and multiplication can be performed by doing the traditional operations modulo $q$, that is: $a +_{\mathbb{F}_q}b \equiv (a+b) \bmod q$ $a -_{\mathbb{F}_q}b \equiv (a-b) \bmod q$ $a \times_{\mathbb{F}_q}b \equiv (a\times b) \bmod q$ As such, addition and subtraction can be ...

6

There is no direct inference from $P = NP$ or $P \neq NP$ to security or insecurity of any particular encryption algorithm. As far as practical consequences are concerned, the "$P = NP$" problem is severely overhyped. If $P = NP$ then any problem for which a solution can be verified in polynomial time can also be solved in polynomial time. "Polynomial time" ...

5

I've previously answered this question over at How will security need to be changed if P=NP? (on our sister site, the IT Security Stack Exchange). In addition, see the answers to What would be the scenario if P = NP for RSA algorithm? for still more on the subject. The short answer is that a proof that P=NP doesn't necessarily mean that all cryptography is ...

5

I don't know the general answer, however, it appears that Baby-step Giant-step is able to give you the solution in $O(\sqrt{in})$ time (where $n$ is the size of $G$); this is $O(\sqrt{i})$ times longer than it takes the same algorithm to solve a single discrete-log problem. The first observation is that if you know the group order $n$ and a group generator ...

5

On the third case, I have a comment. The third oracle may help the adversary using Cheon's algorithm for the DL problem. Let $q$ be a prime order of the subgroup $\mathbb{G}$ of $(\mathbb{Z}/p\mathbb{Z})^{\times}$. In the third case, the adversary has an oracle $a \mapsto a^k$ for any $a$. Hence, it can obtain $g^{k^i}$ from $g^{k^{i-1}}$ and so on. When ...

5

I'll expand on the comment I left on my answer. The purpose of Part 2 of NIST SP 800-57 is to "[provide] guidance on policy and security planning requirements for U.S. government agencies". Keeping that in mind, the table on page 64, i.e. the table from whence the numbers in that question came, includes more than just RSA key sizes. Namely, it includes some ...

5

Actually, it's not true that public key encryption is based on Discrete Log; the ones in common use (DH, ECDH, ECDSA) are (and even RSA can be viewed as "based on Discrete Log", at least from the standpoint of "if you can solve the Discrete Log modulo a composite, you can break RSA"). However, we do have a number of public key systems (NTRU, McEliece) which ...

4

The Handbook on Applied Cryptography (link to the pdf version is on Alfred's webpage) has some of the known techniques to do finite field arithematic. If you are doing arithmetic to implement Elliptic Curve Cryptography (note the comment made by Paulo), then there are methods that depends on whether you are doing it in Jacobian or Projective plane (inverse ...

4

In practice the view would be that no, it does not get any easier. Indeed many popular deployed schemes depend on it. For example the Trusted Authority in the Boneh-Franklin IBE scheme has a master secret s and issues private keys to users in the form s.ID_i, where ID_i is a point on an elliptic curve, and ID_i is related to the identity of the i-th user. It ...

4

Well, assuming that you have a fixed block cipher (that is, you don't change the block cipher as the length of the message increases), then given a message of length $N$: Both ECB and OFB take $O(N)$ time for both encryption and decryption. Both ECB and OFB take $O(1)$ space in addition to the space to hold the encrypted/decrypted message (which is ...

4

The answer appears to be similar to one that I asked on cstheory.SE about Discrete log in GL(2,p) (i.e., given $A,B$, find $k$ such that $A^k=B$). In this question we are given less information, but similar techniques should still apply. Start by putting $A$ into Jordan normal form, i.e., write $A=PJP^{-1}$ where $J$ is the Jordan normal form and $P$ is a ...

4

Well, there are some major problems with your code. Technically, the time estimate of your code is correct (that is, if you insert modulo operations when you update pow1 and pow2), however no one would actually use that algorithm to do ElGamal. Lets hit some of the issues: You use an $O(N)$ algorithm to compute $x^N$; in real usage, exponents are huge ...

4

Summary. The short answer is: Cryptography would be insecure. Any encryption you can do with a non-deterministic algorithm, can be broken (in approximately the same running time) by another non-deterministic algorithm. Non-determinism is extremely powerful. If you give everyone access to non-determinism, then secure encryption becomes impossible: the ...

4

Well, one assumption you appear to be making is that, with 2DES, there will be approximately $2^{56}$ possible key matches. Actually, there are an expected $2^{48}$ possible key matches; here's why: Let us assume we're running the meet-in-the-middle attack on 2DES, and consider an arbitrary incorrect encryption trial (that is, we try an encryption key that ...

4

On the first question The public key of DGHV's SHE scheme consists of $\tau+1$ $\gamma$-bit numbers, that is, $pk = (x_0,\dots,x_\tau)$, where $x_i$ is chosen from the distribution $\mathcal{D}_{\gamma,\rho}(p)$ over $[0,2^{\gamma})$. Therefore, the length of $pk$ is $O(\tau \gamma)$, which is $\tilde{O}(\lambda^{10})$ if we adopt the parameters $\gamma = ... 4 Well, ECC takes about$2^{n/2}$time to break because there are smarter ways to attack it than literally trying each possible key separately. With AES, the best known-attack is to try a key, and see if it works. If it doesn't, all you've learned is that that specific key wasn't it, only$2^{n}-1$more to go... However, with ECC, there are other methods. ... 4 Preliminary: Almost the same article is available for free without breaking any law, nor downloading 5GB (formatting is shifted by at most one third of a page). It is also (as well as all other articles of IACR crypto conferences from 2000-2011) in the IACR Online Proceedings, specifically in the FSE 2008 section, but then you need to subtract about 223 from ... 3 Calculate$g = GCD(a, n)$and$n^\prime = n / g$. If$b \not\equiv 0 \pmod g$, then there is no solution. Divide whole equation by$g$giving you$a^\prime· x_0 = b^\prime \pmod{n^\prime}$and solve for$x_0$. Then solutions for$x$are$x_0 + k· n^\prime$for$k = 0, 1, ..., g-1\$.

3

I'll be assuming the question considers time complexity in big-O notation only, because that's common, the simplest, and there is no indication of the contrary. The price to pay for this simplicity is that the resulting time complexity is often a poor way to compare the efficiency of different algorithms. In this section I restrict to the standard ...

3

Stream ciphers are essentially just random number generators, so for each input bit they generate a random bit (based on a seed, i.e. the key) and combine it with the input bit, giving you the output bit. So: c = m ⊕ G(k) m = c ⊕ G(k) Where c is ciphertext, m is plaintext, G is the RNG and k is the key. As such, all stream ciphers should be O(n) ...

Only top voted, non community-wiki answers of a minimum length are eligible