All Questions
Tagged with cryptography probability
61
questions
0
votes
0
answers
32
views
Problems about Probability Analysis of the Success Rate
I am currently reading a paper on linear cryptanalysis and I am a bit confused by the probability analysis of its success rate. I wonder if I can seek advice here?
Let $N$ be the number of given ...
2
votes
1
answer
145
views
Can we do any better bijective mapping of a permutation series which is only bijective for a probabilistic subset of its input domain?
So we want to bijectively map one path to another. But depending on start and target node we can only choose from a subset of all transitions. It would look like this:
We also do not know where one ...
- 77
1
vote
0
answers
47
views
Are these two definitions of one-way function equivalent?
Here comes two definition of one-way function, the first one comes from wikipedia while the second one is by myself.
I'm curious about whether they are equivalent and have been considering for a long ...
- 21
0
votes
1
answer
69
views
Why can differential privacy be proved using probability density function?
I am reading The Algorithmic Foundations of Differential Privacy and get confused about the proof of Therom 3.6 on page 36:
Theorem 3.6. The Laplace mechanism preserves $(ε, 0)$-differential privacy.
...
3
votes
1
answer
41
views
Justifying a randomization technique for efficiently checking equalities in a prime-order group
In cryptography papers, I have seen a technique used to confirm that two equalities hold in a group that requires performing only a single computation in the group. This is apparently more efficient ...
4
votes
1
answer
201
views
Permuted Hamming distance
Suppose Alice wants to send a message to Bob, they agree on a $n$ letters alphabet $\Omega = \{a_1, \cdots, a_n\}$ and they both agree on a shared secret $\omega=\omega_1 \cdots \omega_m$ $\omega_i \...
- 175
4
votes
1
answer
78
views
Question on Chernoff bound type probability argument.
The following result was given in the research article (claim 6) and no justification was provided for the proof. I have presented the claim in simple terms below. Basically, I want to understand what ...
- 1,497
1
vote
1
answer
360
views
Stochastic independence and linear combination of uniform random variables
The following theorems are part of this paper
Suppose that $(X_1,\dots,X_k)$ is a family of i.i.d. uniform random variables in $\mathbb{F}^{n}$ (why do we assume that the exponent of the field/set/...
- 429
0
votes
1
answer
85
views
Infinite Sequence vs. Indexed Set
I'm having a look at this provable cryptography tutorial and early on there is a definition of something called a "probability ensemble" which I haven't come across before.
A probability ...
- 411
1
vote
0
answers
57
views
How to sample from an hypergeometric distribution mathematically?
There are lots of implementations of functions that sample from hypergeometric distributions and they use these 2 constants:
...
- 6,756
0
votes
1
answer
37
views
Repeated application of union bound
I was learning about probability theory, with different events, until I came across something I wanted to query.
I wanted to check if the above picture means if I pick k = 3, then:
- 135
0
votes
1
answer
30
views
doing proofs of implications
Hi this question is regarding a proof from the book "INTRODUCTION TO MODERN CRYPTOGRAPHY" (https://eclass.uniwa.gr/modules/document/file.php/CSCYB105/Reading%20Material/[Jonathan_Katz%...
- 119
0
votes
1
answer
30
views
summing over distribution of occurence of letters in english language
i have this structure, representing the percentwise distribution of the usage of letters in the english language:
...
- 119
2
votes
1
answer
82
views
What is the expected number of random choices to find a quadratic residue mod p?
Say you have $x$, which is not a quadratic residue mod $p$. What is the expected number of random choices of $d \in F_p$ needed such that $x+d$ is a quadratic residue?
In a work of Maurer (page 277) ...
- 167
2
votes
1
answer
159
views
Confused about the definition of differential privacy
From standard references, the definition of differential privacy is as follows.
A mechanism $M$ is called $\epsilon$-differential privacy
($\epsilon$-dp) if it satisfies the following condition: for ...
- 21