minar
  • Member for 8 years, 6 months
  • Last seen more than a month ago
understanding forking lemma
Accepted answer
13 votes

For many signature schemes, having two signatures using the same randomness for two different hash values allows recovery of the private key. This is used in many security proofs by showing that an ...

View answer
What is meant by $\tilde\Omega(\lambda^4)$?
10 votes

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

View answer
What is the importance of Modular arithmetic in cryptography?
10 votes

Your question first calls for a remark, the XOR itself already is an instance of taking a modulo. Namely, XOR is just another name for addition modulo 2. As a consequence, using modulo n can be seen ...

View answer
Is there an intuitive explanation as to why only the private key can decrypt a message encrypted with the public key?
9 votes

Since your problem seems to be with the principle of public key crypto rather than with the math itself, here is an analogy with a physical object that may help. Take a key lock padlock as below: To ...

View answer
Do ciphertexts leak information about their algorithmic creators?
8 votes

A good block cipher should be indistinguishable from a random permutation (otherwise it is considered broken). A consequence of this is that two good block ciphers are indistinguishable from each ...

View answer
Reduction of Integer factorization to Discrete logarithm problem
8 votes

Here is a quick summary: First direction, from discrete logs modulo $N$ to factoring. Assume that there is a fixed basis $g$ for the method that computes logs. Choose a random $x$ modulo $2N$ and ...

View answer
Is it possible to determine the group order by knowing the "public" and "private" key exponents in an RSA group?
8 votes

The relationship between recovering the decryption exponent $d$ and factoring the RSA modulus $n=pq$ is a classical question in cryptography. There are three useful answers: The first answer deals ...

View answer
How did they factor RSA-704?
8 votes

Let me try a simple explanation of NFS. I will necessarily skip lots of details, but I hope you will get the main ideas. The number field sieve algorithm (NFS) is a member of a large family: index ...

View answer
why hash(hash(str)) is bad?
Accepted answer
6 votes

This call for a few different answers. First concerning any rainbow table or similar approach, nothing prevents you from defining $HH(x)=H(H(x))$ and then to apply the desired method to the composed ...

View answer
Why is it said that if we have a duplicate ciphertext block it can leak our information?
6 votes

The exact information leaked depends on the mode of operation that is in use. The simplest case is ECB, where a duplicate ciphertext block means that the corresponding plaintext blocks are also equal. ...

View answer
A block cipher with independent keys for each round
6 votes

This question can be answered in several way depending on the exact meaning you intend for more secure. First answer: No, it is not more secure in general. The most you can expect is "at least as ...

View answer
Three-way key exchange with elliptic curves without pairing
5 votes

Without pairings, there is no known single round tripartite key-exchange algorithm. However, it is possible to do it in two-rounds. For example, refer to the Burmester-Desmedt conference key protocol (...

View answer
Quadratic residue problem on composite integers
4 votes

The computation of square roots modulo a composite $N$ is hard, because a method for computing square roots can be turned into a factoring method in the following way: Choose an element $a$ modulo $N$...

View answer
Identification of correct plaintext after decryption in Rabin cryptosystem
4 votes

Nightcracker's method works fine. There also are deterministic solutions to select the correct ciphertext that require very few additional bits. One very useful ingredient is the use of the Jacobi ...

View answer
What is the difference between Shor's algorithm for factoring and Shor's algorithm for logarithms?
Accepted answer
4 votes

In fact, the basic idea of Shor's algorithm for the discrete logarithm problem is reasonably simple. Assume (as in Section 4 Discrete Log: the easy case of Shor's paper) that you have an efficient ...

View answer
Does it make sense to block RSA keys under 1024 bits?
4 votes

Hard to answer impartially, expect opinion-colored answers here. The paper you are mentioning has essentially nothing to do with keysizes. Instead they show that bad use of randomness during RSA key ...

View answer
Why does Shamir's Secret Sharing Scheme need a finite field?
4 votes

The simplest answer is probably to give an example of information leaked when using Shamir's secret sharing over the integers. Assume that we construct a low degree example, defining $q$ to be a ...

View answer
Hash Family Example
4 votes

As explained in @fgrieu answer, you can always create such a function from a regular hash function by taking variations on the IVs or internal constant. However, if you ask for a clean standardized ...

View answer
what is pairing in cryptography?
3 votes

A pairing is a non degenerate and bilinear map from $G_1\times G_2$ to $G_T$. This means that if $g_1$, $g_2$ are generators of $G_1$ and $G_2$ then: By non-degeneracy, $e(g_1,g_2)\neq 1$ and, in ...

View answer
Efficiency of finding sub group order vs factorization
Accepted answer
3 votes

Concerning question 3, here is an answer assuming that the coefficients of $r$ are known to Bob and the coefficients of $s$ hidden in an exponential representation. [This is unessential, it can be ...

View answer
Is there any weak message for an ECDSA signature?
Accepted answer
3 votes

[Partial answer] In Generic Groups, Collision Resistance, and ECDSA by D. Brown (see http://cacr.uwaterloo.ca/techreports/2002/corr2002-06.ps or http://eprint.iacr.org/2002/026) on page 17, you have ...

View answer
using elliptic curve point multiplication as a key stretching method
3 votes

If I understand correctly is to hash your password $pw$ into a point using either $P=Pad(pw)\cdot P_0$ or $P=MD5(pw)\cdot P_0$ and then use $P$ for cryptographic purpose. The exact security of this ...

View answer
security amplification
3 votes

As D.W. said, your questions are not very clear. I interpret your first question as asking how the security of an $\epsilon$-PRP varies with $\epsilon$. The answer to this is quite clear from Tessaro'...

View answer
What is the fastest elliptic curve operation f(P) in affine coordinates such that f^n(P)=P only if n is large?
3 votes

With your curve, you can use the Gallant-Lambert-Vanstone (GLV) method to answer your question. Indeed, the equation of your curve is: $$y^2=x^3+7.$$ Since $p$ is congruent to $1$ modulo $3$, there ...

View answer
How to compute the attacker's probability?
3 votes

The probability of recovering the string $R$ is the same with both of your scheme. The reason is that your second scheme can be separated into two independent parts. In the first part, you just ...

View answer
Padding in PMAC
3 votes

Obviously, PMAC needs a padding because you want to be able to compute MACs of messages which are not multiple of the block length. The padding is defined in the PMAC paper http://www.cs.ucdavis.edu/~...

View answer
Questions about the ideal cipher model
3 votes

The ideal cipher model is a way of modeling of block cipher (i.e. a keyed permutation family) which is very close to the modelization of a hash function by a random oracle. In fact, these two models ...

View answer
Seemingly simple decryption question
3 votes

If I interpret your question correctly, your unchanging 4-character input is probably just a PIN code that unlocks the use of the device. In this case, the sequence of 6-character strings is a series ...

View answer
a possibly stronger type of attack on identity-based encryption
Accepted answer
2 votes

You can probably prove the security against your game from the security in the IND-ID-CCA game of Boneh and Franklin (see http://courses.cs.vt.edu/cs6204/Privacy-Security/Papers/Crypto/IBE-Weil-...

View answer
Finding where I am in a linear recurrence relation
2 votes

First of all, your linear recurrence relation is not exactly linear, it is affine. However, in general, it is not difficult to get rid of the constant term $d$. To do this, define $A(n)=a(n)+t$, and ...

View answer