Cryptography

Questions tagged [probability]

Ask Question

Questions about the branch of mathematics concerned with modeling and analyzing random phenomena.

50 questions
Newest
Active
Bountied
Unanswered
Filter by
Sorted by
Tagged with
0
votes
0answers
40 views

One time pad, Proof for a problem

We know 2 plaintexts of length L and 2 ciphertexts of length L(we don't know which one belongs which), assuming each given ciphertext is generated by encrypting one of the given plaintexts by XOR'ing (...
1
vote
0answers
30 views

What is the success probability of a single exploitation attempt for these scenarios

Consider an architectural security measure intended to prevent stack buffer overflow attacks where, instead of storing the return address on the stack, the CPU stores the difference of the stack ...
1
vote
1answer
44 views

Differential Privacy: Gaussian Mechanism when $\epsilon >1$, Laplace Mechanism when $\epsilon = 0$

In Differential Privacy resources, the limiting cases of $\epsilon, \delta$ are not justified well enough. For example, on Wikipedia, it is said that Gaussian mechanism only works when $\epsilon < ...
1
vote
1answer
43 views

Is the collision chance 2^(n/2) of an n-bit tag τ unchanged if reduced to (n/2)-bits using a reduction of τ to some 2^(n/2) order group element?

If $H(k, Μ) = τ$, in the context where $τ$ is an $n$-bit tag produced as a mac on a key, $k$, and a message, $M$, through a keyed-hash function, $H$, is there a function $F(τ) = T$ that transforms $τ$ ...
1
vote
1answer
32 views

How was the adversary's success probability calculated in this 2002 paper by Dodis, Katz, Xu, Yung about key-insulated signature schemes?

In this paper ("Strong key insulated signature schemes" by by Dodis, Katz, Xu, Yung (2002)), I understand most of the proof for Lemma 1 (pg. 9); I struggle with how some of the probability ...
0
votes
2answers
175 views

What are the fastest algorithms that sample from the uniform distribution?

Lots of cryptography algorithms rely on pseudorandom number generators. Sometimes, given a plaintext, you need to generate a pseudorandom number from it. What are some fast algorithms that do so? I've ...
1
vote
0answers
14 views

How hypergeometric sampling works in order preserving encryption?

According to https://crypto.stackexchange.com/a/8800/53007: Start with the entire domain [M] and range [N]. Call y←N/2 our range gap. Now using our key k we generate some pseudorandom coins and give ...
1
vote
1answer
30 views

Understanding this notation for the probability distribution of order preserving encryption

I'm reading this PDF: https://link.springer.com/content/pdf/10.1007/978-3-642-01001-9_13.pdf about order preserving encryption functions and there's this on page 9 (or 232): It's describing the ...
2
votes
1answer
56 views

Checking Independence of combination of uniform random variables to use pilling up lemma

My question is very basic one. Suppose $a_0, a_1, a_2, a_3, a_4, b_0, b_1, b_2, b_3, b_4$ are $10$ uniform random variables from $\{0,1\}$ independent of each other. Now there are expressions of the ...
1
vote
0answers
31 views

Simple shift cipher probability exercise

This is a super simple probability exercise: If we have a simple shift/ceasar cipher. Let's say that there are only three messages encypted. ...
2
votes
1answer
73 views

trying to identify the key of a vigenere cipher via brute force

I'm working on a bit of an ARG game type thing that uses the vigenere cipher. what im wondering is the chance a player could brute force said cipher by simply checking all possible key sequences of ...
1
vote
0answers
44 views

If a different plaintext may produce the same ciphertext, is the system perfectly secure?

Define the injective map $\phi: \Omega\rightarrow \mathbb{N}$, such that $\Omega=\mathcal{A}^n$ denotes the set of all strings of length $n\in\mathbb{N}^*$ from an alphabet $\mathcal{A}$ of elements $...
9
votes
6answers
4k views

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

In theory, there are infinite inputs, that you can hash with SHA-256. So theoretically it would be possible that one hash string would read 0xaaaaaaaa... But would ...
2
votes
2answers
75 views

What is the best way to accurately describe this statistical probability? [closed]

I am in the process of writing some information for an App. I need to express the probability of something happening but in a way that is correct but easy to understand. I'm confused on the actual ...
0
votes
1answer
164 views

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

I encountered this while solving a crypto puzzle. This is the puzzle. ...
0
votes
0answers
20 views

Conditional probability being Constant in Threshold Cryptography

I am working on Threshold implementation of algorithms to prevent side channel attacks. I am not that much proficient in Statistics and Probability theory. I want to know what is the significance of ...
2
votes
1answer
79 views

GetModulus negligible probability

I have this textbook definition, I shall include below. GenModulus denotes a ppt algorithm that, on input $1^n$, outputs $(N, p, q)$ where $N = p\,q$ and (except with negligible probability) $p$ and $...
2
votes
1answer
109 views

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

I'm currently reading "Cryptography Engineering - Design Principles and Practical Applications" written by "Niels Ferguson, Bruce Schneier, Tadayoshi Kohno" published by Wiley in ...
0
votes
1answer
69 views

How to deal with concrete security against lots of queries?

In general, $O(1/\epsilon^2)$ queries are required to distinguish between two distributions that are statistically close at most $\epsilon$. This informal state deals with the required number of ...
0
votes
0answers
24 views

Probability of an adversary attacks mix networks encryption communication

Assume Alice and Bob communicate through a mix-net consisting of 3 intermediate routers. Assume each intermediate router waits to receive k packets before decrypting (or re-encrypting) each, permuting ...
1
vote
1answer
56 views

Can we determine a security parameter in the hybrid argument where the number of hybrids is polynomially bounded but not known?

Let $\lambda$ be a statistical security parameter. Consider a security proof that is based on hybrid argument, where there are polynomially many (say, $n = p(\lambda)$) hybrids, $H_1, ..., H_n$. Any ...
4
votes
3answers
233 views

Can you have perfect secrecy with countable message/key spaces by dropping countable additivity?

This classic paper by Chor and Kushilevitz shows that if the key space and the message space are both countably infinite, then it is impossible to have a perfectly secure private-key encryption scheme....
1
vote
2answers
109 views

On The Next Bit Test

I would like to know what $O(v(n))$ really means in detailed and simple words please. I found it everywhere in the literature I am reviewing but I cannot find what the intuition of it (especially if ...
-1
votes
1answer
109 views

Explaining the reason of radically more accuracy while using different set of hash functions instead of same set of hash functions on some operations

So I am looking for an explanation of an experiment. In this experiment, I took a set of k hash functions. Say the total number of data points I am working on is d. Call an algorithm A which used that ...
3
votes
1answer
94 views

Laplace Inequality

I am trying to prove that if $r_i \sim Lap(0,1/\varepsilon)$ where $\varepsilon >0$ then: $$Pr[r_i \geq 1+r^*] \geq e^{-\varepsilon}Pr[r_i \geq r^{*}]$$. I know that for $r*>0$ it satisfies ...
2
votes
0answers
27 views

Probability that length of shortest nonzero vector is less than a number

Let $\Lambda\subset \mathbb{Z}^n$ be an $n-$ dimensional lattice with determinant $d$. We know that the probability that a uniformly random integer vector $x$ is a point in $\Lambda$ is given by $\...
3
votes
1answer
209 views

Likelihood of signature collision with EdDSA

Taking EdDSA as an example, given the length of a signature is 512-bits for a given data payload, what is the probability of a collision where there is another 512-bit value that is also a valid ...
1
vote
1answer
72 views

Probability that rank of a square matrix, whose each element is uniformly random from a ring of integers modulo prime p, is not full

I am currently reading a paper from CRYPTO, which is a top conference in cryptology. In the paper, the authors use a thereom like the one given below without a rigorous proof: the probability that $...
5
votes
1answer
540 views

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

I am in need of a non-uniform random number generator where each n-bit output has a hamming weight with a certain binomial distribution. For example, I would like a non-uniform PRNG which generates ...
0
votes
2answers
127 views

Random Oracle to prove an Authenticated DH protocol

I am trying to understand how they use the random oracle to solve the CDH. For example, in the security proof on page 7 of the following paper; A Lightweight Message Authentication Scheme for Smart ...
0
votes
1answer
45 views

How to have a bound (upper or lower) of Gaussion distribution over lattice based crypto>

In lattice-based crypto, we always need to sample 'noise' from Gaussian distribution, but how to measure the bound the noise? For example, if the Gaussian distribution is D_{u,\sigma}, where u is the ...
1
vote
0answers
87 views

Primal and dual attack against NTRU

I am looking at the primal attack against schemes in the second round of the NIST Post-Quantum Standardization Project. The cost of primal attack usually comes from an estimate described in NewHope ...
2
votes
1answer
279 views

Statistical distance in distributions

I have two questions regarding to statistical distance in distributions. 1: If $Z$ is uniform random variable over $N$ consecutive integers and $m < N$ then $Z$ mod $m$ has statistical distance ...
1
vote
1answer
97 views

Compute statistical distance between two distributions over tuples

Let $X$ denote one distribution. Let $f,g, \text{ and } h$ denote three functions. If we have the results: $g(X)$ is within a negligible statistical distance of $h(X)$. Is it possible to prove $$(f(...
1
vote
0answers
172 views

How do I calculate the conditional probability of a Caesar cipher?

I have a frequency distribution of letters for the plaintext and the ciphertext. I'm trying to determine the conditional probabilities to identify the plaintext/ciphertext pairings. If I encrypt ...
1
vote
1answer
94 views

$X_ {i_1}, . . . , X_{ i_ k} $ are IID random variables or not?

In this paper secret sharing is to distribute information (the secret) over a set of participants such that the secret can only be reconstructed if certain authorized combinations of participants join ...
0
votes
1answer
65 views

Can anybody please explain why is the probabilty of finding a desired message for random chaining values equal $2^{-224}$?

Can someone explain why does probability is equal $2^{-224}$ in the following piece of paper? The length of messages blocks in Hamsi is equal 32 and the length of chaining values is equal 256.
2
votes
0answers
42 views

decrypting a one-time-pad that outputs 0,1 in preknown probabilities

assuming a two users want to use a one time pad ciphersystem, and they are using a program that was developed by a third party that was supposed to create random undependable bits, but for some reason ...
0
votes
3answers
509 views

Derivation of birthday paradox probability

I am trying to come up with an explanation of the probability of birthday collision. $P$(no collision among t people) = $(1− \frac{1}{365}) · (1-\frac{2}{365}) ··· (1-\frac{t-1}{365})$ For one ...
1
vote
0answers
35 views

Again on discrete gaussians over lattices [duplicate]

Define $$\rho_{s,c}(x) = exp(-\pi \cdot \frac{\|x - c\|^2}{s^2})$$ and $$\rho_{s,c}(L) = \sum_{x \in L} \rho_{s,c}(x)$$ Then Discrete Gaussian over $L$ with center $c$ and standard deviation $s$ is ...
1
vote
2answers
125 views

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

Statistical closeness implies computational indistinguishability was recently posed. It revolves around a numeric value $\Delta(n)$ of the statistical difference between a pair of distribution ...
6
votes
2answers
837 views

Statistical closeness implies computational indistinguishability

This is so trivial that authors usually don't bother to give an explicit proof. But for me there is some vagueness. We say that two ensembles $X_n$ and $Y_n$ are statistically close, if $$ \Delta(n) ...
1
vote
1answer
98 views

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 <...
3
votes
2answers
105 views

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

I don't understand what does it mean by "The probability is taken is over the coin tosses of K." Does it mean, the probability distribution is generated based on exactly same data but only the ...
0
votes
1answer
34 views

Can randomness protect a list of signatures against forgery attacks?

Suppose we have a list of signatures $S = [s_1, .., s_n]$ for a list of messages $M = [m_1, .., m_n]$, and we want to verify that $S$ is a valid signature of $M$, so each $s_i$ should be valid for ...
4
votes
0answers
115 views

What is the probability equation of rotational cryptanalysis on modulo multiplication?

The answer in this question defined how to calculate the probability of rotational cryptanalysis on modulo multiplication $\odot$. This paper defined an algebraic equation of how to calculate the ...
2
votes
2answers
1k views

Why the definition in $\epsilon$-differential privacy is multiplicative rather than additive？

According to its mathematical definition, a random algorithm $M: D\rightarrow R$ satisfies $\epsilon$-differential privacy if the adjacent datasets $x, y \in D$ where $D$ is a whole dataset and ...
0
votes
2answers
260 views

Meet-in-the-middle probability of success

In page 358 of Bruce Schneier's Apllied Crypto, when explaining the meet-in-the-middle attack, he states that the success probability is «1 in $2^{2m - 2n}$» with two plaintext/ciphertext pairs, and «...
7
votes
1answer
7k views

Using a hash function as a random number generator

Using MD5 or SHA1 for instance, and applying integers (as seed so to speak) to the hash function, in sequence, and only keeping, say, the first 64 bits of the resulting hash, do we always have a ...
2
votes
1answer
93 views

Is there a rule of thumb for ZK protocols?

There's always a small chance for many zero knowledge protocols that the prover had a lot of luck to prove something to the verifier. Take the Ali Baba cave as an example: The prover has a 50% ...

Your privacy

By clicking “Accept all cookies”, you agree Stack Exchange can store cookies on your device and disclose information in accordance with our Cookie Policy.