Questions tagged [probability]

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

Filter by
Sorted by
Tagged with
0 votes
1 answer
49 views

False positive error rate of truncated hash match

I’m having difficulty calculating the false positive error probability of matching a prefix of a hash that was truncated to m bits. Say I have string S1 that produces a SHA256 hash H1. I then save the ...
user avatar
3 votes
1 answer
77 views

Quantifying the success probability of brute force attack against (search) LPN

I've been trying to learn about attacks on LPN ($n$-bit secret, noise rate $\eta$), and have found several allusions to a brute force algorithm that runs in time exponential in $n$ and requires a ...
user avatar
  • 33
0 votes
0 answers
19 views

About notations that are used to describe probability that A wins the game(probabilistic algorithm?)

I am studying cryptography by myself, especiall and there are somewhat confusing notations. Here are two examples in digital signature that I want to check: $$Pr \left[ 1 \leftarrow \mathcal{V}(\hat{\...
user avatar
1 vote
1 answer
81 views

Probabilistic SHA-256 hash tending all values to 0.5

I wrote SHA-256 with arrays of integers representing the bits (e.g. [1,0,...,1]), and then I altered it to accept partial values (e.g. [0.5, 0.79, 0.0, 1]), as in each value has an x chance of being '...
user avatar
7 votes
2 answers
515 views

Probability conventions in cryptography

I am working on Victor Shoup's tutorial on game-based security proof and want to figure out some notions from the perspective of probability theory. Consider the following PRF advantage defined on ...
user avatar
  • 404
0 votes
1 answer
36 views

Explaining: The probability of breaking an encryption scheme

I was reading intro to modern cryptography and didn't understand how did they calculate the probability: Say we have a cryptographic scheme in which an honest parties run for $10^6 \cdot n^2$ cycles ...
user avatar
  • 117
1 vote
1 answer
64 views

"randomized" indistinguishability vs "deterministic" indistinguishability

Let $X$ be a measurable space. For each $n\in\mathbb N$, let $P_n$ and $Q_n$ be probabilities on $X$. We say that $(P_n)_{n\in\mathbb N}$ and $(Q_n)_{n\in\mathbb N}$ are statistically ...
user avatar
  • 145
0 votes
1 answer
46 views

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

Let $C(X)$ denote the cardinality of the set $X$. For example, $C(\{0\}) = 1, C(\{0, 2\}) = 2$ etc. Let $S$ denote a (potentially infinite) sequence of random bits. Split $S$ into $k$-bit words $w_1, ...
user avatar
4 votes
1 answer
183 views

The different bounds of PRP/PRF switching lemma

The PRP/PRF switching lemma is usually denoted as follows: I understand the proof of this version of the bound $\frac{q(q-1)}{2^{n+1}}$ and the game-playing technique behind it. However, I came ...
user avatar
  • 115
2 votes
0 answers
51 views

What's the probability distribution of 3DES keys' key check values?

Do the key check values of two-key 3DES keys have a uniform distribution? If not I'm curious as to what the distribution is. I ask because I want to know how safe it is to use a key's KCV as an ...
user avatar
1 vote
1 answer
112 views

Mathematical formulation for a cryptosystem

I will try to define easily the cryptographic system of this paper. The author designs a communication game for $N$ players. The private information of every player is denoted as $t_i\in T_i$ and ...
user avatar
  • 131
1 vote
1 answer
65 views

Differential Privacy with Outliers

To use the Laplace mechanism, we have to get the global sensitivity of a query function. What do we do in the case where there is one huge outlier(or multiple outliers) in the dataset such that the ...
user avatar
0 votes
1 answer
41 views

Is the Secret sharing scheme thresholds of variable of interest shared related with the entropy of the variable?

Is the $t$ out of $n$, namely $(t,n)$, threshold in the secret sharing scheme related to the entropy of the random variable that is shared according to the scheme? What changes in the secret sharing ...
user avatar
0 votes
0 answers
25 views

Secret sharing scheme combined with probability theory results?

As a sequel of my previous post I am writing a new one with respect to the secret sharing scheme. I will only cite here the answer because I want to make a question on it. $\textbf{Answer:}$ To be ...
user avatar
0 votes
0 answers
22 views

How to design such a secure multiparty computation scheme with the players using a majority rule

Suppose that $y$ is a uniform random variable that is defined over the field (or group or abelian group) $Y$. Let us suppose that there are $N=\{1,2,\cdots,i\cdots,N\}$ agents and only one of them, ...
user avatar
1 vote
1 answer
990 views

Could this be a secure multiparty secret sharing scheme?

Suppose that $y$ is a uniform random variable that is defined over the field (or group or abelian group) $Y$. Let us suppose that there are $N=\{1,2,\cdots,i\cdots,N\}$ agents and only one of them, ...
user avatar
1 vote
2 answers
73 views

Why Entropy to be defined as Joint Probability Distribution Sum?

From Stinson's book, during the demonstration of the following Theorem which says: $H(X,Y) \leq H(X) + H(Y)$, with equality if and only if $X$ and $Y$ are independent random variables. The author ...
user avatar
1 vote
0 answers
61 views

Understanding notation of probability of algorithm equal to 1

I would like to understand what the following notation means: let $A$ be a polynomial-time algorithm and say $X(a,n)$ is a probability ensemble where $a\in\{0,1\}^*$ and $n\in\mathbb{N}$. What does ...
user avatar
1 vote
1 answer
93 views

What are the expected values of a particular rotational-XOR property of a sequence of random bitstrings?

Assuming that $x$ is a sequence of $l$ bits and $0 \le n < l$, let $R(x, n)$ denote the result of the left bitwise rotation of $x$ by $n$ bits. For example, if $x = 0100110001110000$, then $$\begin{...
user avatar
1 vote
1 answer
233 views

How are probabilities combined in the game hopping proof technique?

I'm currently studying a paper (Sequences of Games: A Tool for Taming Complexity in Security Proofs) on proving semantic security using the Game Hopping technique by Victor Shoup. On pages 9-11, he is ...
user avatar
  • 661
1 vote
0 answers
91 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 (...
user avatar
  • 11
1 vote
0 answers
36 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 ...
user avatar
1 vote
1 answer
157 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 < ...
user avatar
1 vote
1 answer
56 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 $τ$ ...
user avatar
  • 23
1 vote
1 answer
41 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 ...
user avatar
  • 15
0 votes
2 answers
230 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 ...
user avatar
1 vote
0 answers
17 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 ...
user avatar
  • 51
1 vote
1 answer
49 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 ...
user avatar
2 votes
1 answer
61 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 ...
user avatar
1 vote
0 answers
49 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. ...
user avatar
2 votes
1 answer
157 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 ...
user avatar
  • 133
1 vote
0 answers
50 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 $...
user avatar
  • 11
9 votes
6 answers
6k 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 ...
user avatar
2 votes
2 answers
78 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 ...
user avatar
  • 129
0 votes
1 answer
470 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. ...
user avatar
  • 1,647
2 votes
1 answer
103 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 $...
user avatar
2 votes
1 answer
118 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 ...
user avatar
0 votes
1 answer
83 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 ...
user avatar
1 vote
1 answer
68 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 ...
user avatar
  • 404
4 votes
3 answers
255 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....
user avatar
1 vote
2 answers
141 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 ...
user avatar
  • 117
-1 votes
1 answer
114 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 ...
user avatar
3 votes
1 answer
102 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 ...
user avatar
2 votes
0 answers
36 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 $\...
user avatar
3 votes
1 answer
289 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 ...
user avatar
  • 1,264
1 vote
1 answer
80 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 $...
user avatar
  • 11
5 votes
1 answer
559 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 ...
user avatar
  • 153
0 votes
2 answers
167 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 ...
user avatar
  • 105
0 votes
1 answer
66 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 ...
user avatar
  • 333
1 vote
0 answers
124 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 ...
user avatar
  • 147