Skip to main content
21 votes
Accepted

Is it possible that a SHA256 hash has the same hex character over and over again?

First of all, the output of SHA-256 is binary and consists of 32 bytes (256 denotes the output size in bits). What you are talking about is apparently the hexadecimal encoding of these bytes. The ...
Maarten Bodewes's user avatar
  • 93.2k
15 votes

Is it possible that a SHA256 hash has the same hex character over and over again?

Yes, it's possible. Given the size of the input space (not actually infinite, but still very, very large), it's also likely, for any given 256-bit value, that several inputs that hash to that value ...
hobbs's user avatar
  • 285
11 votes
Accepted

Statistical closeness implies computational indistinguishability

A probabilistic distinguisher is still a deterministic function of its input and random coins. So a probabilistic distinguisher trying to distinguish $X$ from $Y$ is equivalent to a deterministic ...
Mikero's user avatar
  • 13.5k
10 votes
Accepted

Is it possible to construct a PRNG where the output numbers have a certain distribution of hamming weights?

The obvious way to do this is to generate N words, and use logical operations to combine them in a single word such that each bit of the output word is a 1 with probability approximately 0.1 (and the ...
poncho's user avatar
  • 148k
6 votes
Accepted

Is there a rule of thumb for ZK protocols?

As usual, choosing the security parameters represents a tradeoff between the security and the efficiency. Therefore, it also strongly depends on two things: how crucial it is that no one breaks the ...
Geoffroy Couteau's user avatar
6 votes

Is it possible that a SHA256 hash has the same hex character over and over again?

But would that also be possible practically, or do the algorithms check that this is not happening? This is practically beyond anybody to find a 32-$a$'s for SHA-256 without pure luck or one need ...
kelalaka's user avatar
  • 49k
6 votes

Is this probability negligible?

With much effort, one can get a bound such that I am unclear how tight it is. The bound is non-standard. There is also evidence that replacing your assumption on $Y$ would yield easier bounds. I'll ...
Mark Schultz-Wu's user avatar
  • 13.5k
5 votes
Accepted

Why the definition in $\epsilon$-differential privacy is multiplicative rather than additive´╝č

In short, with this multiplicative definition, it could be ruled out the possibility that an individual's record would be randomly selected and published. Consider a malicious algorithm $M^*$ that ...
Shan Chen's user avatar
  • 2,725
5 votes
Accepted

Is there only one formula for the statistical difference between a pair of distribution ensembles?

What we call "statistical distance" in cryptography is called total variation distance by statisticians. So it certainly exists outside of cryptography. I can't speak to its applications within ...
Mikero's user avatar
  • 13.5k
5 votes
Accepted

Cryptography Engineering - Design Principles and Practical Applications - Chapter 9 Generating Randomness - Section 9.4 The Generator

This section talks about Fortuna, where it uses a block cipher with a 128-bit block and a 256-bit key size. The cipher is used in CTR mode. In the CTR mode, if an attacker can access the internal ...
kelalaka's user avatar
  • 49k
4 votes

Statistical closeness implies computational indistinguishability

Another way to see this would be to try and upper bound the distinguishing advantage for any distinguisher and relate that to the statistical distance. Edit: Since the following answer is really ...
Marc Ilunga's user avatar
  • 3,338
4 votes
Accepted

Derivation of birthday paradox probability

The probability becomes more intuitive when one pictures the $t$ persons entering one by one in the room. Before the first person enters, there's no collision/coincidence of birth-date, thus ...
fgrieu's user avatar
  • 142k
4 votes
Accepted

On The Next Bit Test

But this notation is defined (informally) in the first paper. The notation $O(\nu(n))$ is used for any function, $f(n)$, that vanishes faster than the inverse of any polynomial, that is for every ...
kodlu's user avatar
  • 22.7k
4 votes
Accepted

Calculating minimum number of messages hashed a 50% probability of a collision (Birthday Paradox)

You are approximately correct; they are wrong. Their answer calculates the chance of matching a particular value i.e. hash inversion. To see this $k$ tries have a $(2047/2048)^k$ of failing to find a ...
Daniel S's user avatar
  • 24.1k
4 votes
Accepted

How are probabilities combined in the game hopping proof technique?

The three equations you reference are (we'll just take them as truth - their proof can be found in the PDF): $$ \begin{align} |Pr[S_0] - Pr[S_1]| & = \epsilon_{\text{ddh}} & \text{ (1)} \\ |Pr[...
Morrolan's user avatar
  • 1,157
4 votes
Accepted

The different bounds of PRP/PRF switching lemma

The simple answer is, both lemmas are correct and the first one trivially implies the second one. This follows simply because for any $q\in\mathbb{N}$, $q(q-1) = q^2-q \leq q^2$. Why then do both ...
Maeher's user avatar
  • 6,861
4 votes
Accepted

How many $k$-bit words of a random bitstring are we expected to extract before all $2^k$ possible words occur?

This known as the coupon collector's problem, with the number of coupons replaced by $2^k$ and $k$ is the number of independent bits drawn ($k=4$ in the question's example). It's expected $(k\log(2)+\...
fgrieu's user avatar
  • 142k
4 votes
Accepted

Probability conventions in cryptography

I completely understand your thoughts, I also had a similar question here. I will answer your question based on my understanding, I would like to hear any thoughts or disagreements, because I haven't ...
tur11ng's user avatar
  • 962
4 votes
Accepted

Interactive Proofs: Why $\delta \lt \frac 13$ for Soundness & Completeness?

This is arbitrary. The definition of the class does not change as long as the $\delta$s are sufficiently away from $1/2$, where 'sufficiently' means by a non-negligible value in $n$, as they can be ...
ckamath's user avatar
  • 5,298
4 votes
Accepted

Where does the 8 come from? Generic Search Problem with Bounded Probabilities

As the paper states, you should look directly at HRS16, Theorem 1. The proof there seems fairly straightforward, but it seems to depend on theorem 7.2 of Zhandry2012. This itself appears to depend on ...
Mark Schultz-Wu's user avatar
  • 13.5k
4 votes
Accepted

Statistics-heavy crypto papers

I am afraid your search for Annals of Stats etc. level of purely statistical theoretical papers in cryptology may not yield too many examples. The field is very applied and the role of statistics is ...
kodlu's user avatar
  • 22.7k
4 votes

Is this probability negligible?

You can get a very loose lower bound on the complementary probability via Fano's inequality: $$ H(X|Y) \leq H_2(e)+P(X\neq Y) \log\left(|{\cal X}|-1\right), $$ where $e$ is the binary variable $X\...
kodlu's user avatar
  • 22.7k
4 votes

Is this probability negligible?

No. It's not necessarily $1/2^n$, and it's not necessarily negligible in $n$. Consider the joint distribution on $X,Y$ induced by the following random process: Pick $X=(X_1,\dots,X_{2n})$ uniformly ...
D.W.'s user avatar
  • 36.5k
3 votes
Accepted

Likelihood of signature collision with EdDSA

Can we provably state that for a given payload and given private key, there is only one valid signature in the 512-bit signature space? No. If you consider EdDSA verification a legitimate signer can ...
Ruggero's user avatar
  • 7,104
3 votes

Statistical distance in distributions

If $m$ divides $N$, then you get the uniform distribution over $[m].$ Let $k=N-\lfloor N/m \rfloor m.$ Note that $k\geq 0,$ with $k>0,$ if $m$ does not divide $N.$ When you reduce $Z$ modulo $m$, ...
kodlu's user avatar
  • 22.7k
3 votes
Accepted

Compute statistical distance between two distributions over tuples

No, you cannot prove that, since it is not generally true. Consider the following counter example. Let $X$ be a distribution over $\{0,1\}$ with $$\Pr_{b\gets X}[b=0] = \Pr_{b\gets X}[b=1]=\frac{1}{2}....
Maeher's user avatar
  • 6,861
3 votes
Accepted

What's the meaning of probabilities in differential privacy formula?

No, it means that the functions are chosen from some domain with some probability distribution. This is standard for randomized algorithms. For simplicity, assume there are $N$ randomized functions $...
kodlu's user avatar
  • 22.7k
3 votes
Accepted

What is / How would I calculate the number of bits(?) I need to make the probability of a collision very small?

If I wanted to create a TOTP-esque algorithm that generated a string n characters long, with each character being a base64 character, generated from a user secret <...
poncho's user avatar
  • 148k
3 votes
Accepted

Using a hash function as a random number generator

Caveat: that answer is written with my mind in Vulcan mode. That is, I'm answering the question as taken literally (in the first part); or in only a minor variant (second part); and ignoring the ...
fgrieu's user avatar
  • 142k
3 votes
Accepted

Understanding this notation for the probability distribution of order preserving encryption

In cryptography the notation of $x\stackrel{\\\$}{\gets}S$ (also sometimes seen as $x\gets_{\\\$}S$) means that $x$ is chosen uniformly at random from the set $S$. If an algorithm is on the right side ...
SEJPM's user avatar
  • 46.1k

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