Skip to main content
New
Stack Overflow Jobs powered by Indeed: A job site that puts thousands of tech jobs at your fingertips (U.S. only). Search jobs

Questions tagged [probability]

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

Filter by
Sorted by
Tagged with
1 vote
0 answers
38 views

Expected size of a set hashed to a specific value

In Theorem D.5 of Goldreich's Computational Complexity: A Conceptual Perspective, Goldreich states: Let $m \leq n$ be integers, $H_n^m$ be a family of pairwise independent hash functions, and $S \...
Germ's user avatar
  • 133
2 votes
0 answers
59 views

Inequalities in collision search on the separation between the classical and quantum random oracle (ROM vs QROM)

I'm trying to read the separation between the classical and quantum random oracle through a paper "Random Oracles in a Quantum World" by Dan Boneh, Ozgur Dagdelen, Marc Fischlin, Anja ...
Dai Chi DO's user avatar
3 votes
1 answer
43 views

MPC Security- Need for Joint Distribution

The security of the multi-party computation protocol can be given by real/ideal world paradigm. The simulator based proof considers the joint distribution of adversary's output and honest parties ...
Novice_researcher's user avatar
5 votes
3 answers
923 views

Is this probability negligible?

Let $X \in \{0,1\}^{2n}$ be a uniformly distributed random string and $Y \in \{0,1\}^{2n}$ such that $H(Y) = n$. Does this imply that $Pr(X=Y) = 2^{-n}$? If it's not, is this probability necessarily ...
Lourenço Abecasis's user avatar
0 votes
0 answers
36 views

Analyzing Insertion Behavior in a Randomized Hash Table

The following problem of my is from final exam for my online course last year; I couldn't have the time to do it, so I want to check whether my answer is correct; Q5) Given an (entirely) random hash ...
Jaclyn's user avatar
  • 1
2 votes
1 answer
125 views

Statistics-heavy crypto papers

I'm currently taking a course in which we choose a stats-heavy paper and analyse it, summarising our work in the form of a written report and presentation. I have tried to find such a paper in crypto, ...
smoking_big_ole_doinks's user avatar
1 vote
1 answer
125 views

Unbounded distinguishers and statistical indistinguishability

In constructing a SHVZK simulator for a sigma protocol I am working on I have encountered some fairly basic questions, but ones which are not often discussed in textbooks and papers - consider the two ...
Lev's user avatar
  • 468
1 vote
1 answer
85 views

Biasedness of the XOR variable of two independent biased boolean variable

My question is very basic one. Suppose there are two independent boolean variable $X_1$ and $X_2$. It is given that $X_1$ is biased towards $0$ and $X_2$ is biased towards $1$ with same amount of bias....
hiren_garai's user avatar
3 votes
1 answer
88 views

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

I am working with lossy ID-schemes and their security in the QROM. Following the article of Kiltz et al. , I am at a loss of the number 8 appearing in most reductions throughout the article. I know it ...
Rory's user avatar
  • 335
2 votes
1 answer
78 views

The second moment and fourth moment of $\mathcal{P}(V)$?

Backgroud: I am reading the paper "Learning a Parallelepiped: Cryptanalysis of GGH and NTRU Signatures". (here is the link). And I got stuck in understanding the computation of moment. ...
zbo's user avatar
  • 75
2 votes
1 answer
109 views

Defining the random variables $K,M,C$ and Perfect Secrecy

In many books on Cryptography, we refer to probability distributions over the key space $\mathcal{K}$, over the plaintext space $\mathcal{M}$ and over the ciphertext space $\mathcal{C}$. Then, we let $...
Chris's user avatar
  • 236
1 vote
1 answer
43 views

Difficulty in the calculation of accuracy in an RP-algorithm

I am studying about RP-algorithm from the book Algebraic Aspects of Cryptography by Neal Koblitz. The following example is given in the beginning which is the Probabilistic Primality Test. I ...
Esha's user avatar
  • 111
3 votes
2 answers
356 views

How to calculate probability of cracking a password from entropy?

I am working on a project for my maths assessment where I research the effect of complexity and length on a given password. Currently, I am working on calculating the probability of guessing a ...
Ember's user avatar
  • 33
3 votes
2 answers
175 views

Privacy intuition vs formal definition

Suppose we define privacy as a game where a machine $M$ has a coin $b$, and on input $M_0, M_1$ always replies with encrypted $M_0$ if $b=0$ and encrypted $M_1$ if $b=1$. The adversary can send as ...
pintor's user avatar
  • 558
1 vote
0 answers
136 views

Physical meaning of Negligible and Non-Negligible Functions

I've been itching my head over this for a while despite going through the queries related to the topic. Can someone explain me negligible and non-negligible function in a concise way? As of my naive ...
A typical nerd's user avatar
1 vote
2 answers
181 views

Clarification of some probability concepts used in crypto

So I am a math major who is trying to learn some crypto. However I have some difficulties with some of the probability definitions that are assumed in the cryptography book that I am using at the ...
mathInferno's user avatar
3 votes
1 answer
224 views

Streams Ciphers - Linear feedback shift register logic behind design

I’m just seeking a better understanding as to the logic behind design of the A5/1 cipher’s keystream generator. Why are the registers degree chosen in such a fashion (19,22 and 23 bits long ...
Julian Fusco-Wright's user avatar
2 votes
1 answer
74 views

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

From a text on Interactive Proofs $x \in {0,1}^n$ is input $V$ is verifier $P$ is prover $r$ is $V$'s internal randomness $P$ provides a value $y$ which is claimed to be equal to $f(x)$ (Completeness)...
user93353's user avatar
  • 2,245
3 votes
3 answers
149 views

Why we need to consider a probability ensemble and not just a probability distribution in the definition of Security under Simulation?

I'm currently reading this classic paper "How To Simulate It" and on most of the definitions it is using the term probability ensemble to represent the message space. From my understanding a ...
tur11ng's user avatar
  • 962
0 votes
1 answer
110 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 ...
Pedro Paixao's user avatar
3 votes
1 answer
162 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 ...
Gordon's user avatar
  • 45
1 vote
1 answer
107 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 '...
Alex Breeze's user avatar
7 votes
2 answers
621 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 ...
X. G.'s user avatar
  • 424
0 votes
1 answer
56 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 ...
MR.-c's user avatar
  • 117
1 vote
1 answer
108 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 ...
zxcv's user avatar
  • 155
0 votes
1 answer
56 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, ...
lyrically wicked's user avatar
4 votes
1 answer
581 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 ...
Max1z's user avatar
  • 145
2 votes
0 answers
99 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 ...
Christopher Simmons's user avatar
1 vote
1 answer
146 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 ...
Nav89's user avatar
  • 137
2 votes
2 answers
125 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 ...
Tiana Johnson's user avatar
0 votes
1 answer
49 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 ...
Hunger Learn's user avatar
1 vote
1 answer
1k 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, ...
Hunger Learn's user avatar
1 vote
2 answers
86 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 ...
João Víctor Melo's user avatar
1 vote
0 answers
70 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 ...
Chito Miranda's user avatar
2 votes
1 answer
213 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{...
lyrically wicked's user avatar
1 vote
1 answer
382 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 ...
tur11ng's user avatar
  • 962
1 vote
0 answers
134 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 (...
IngIng's user avatar
  • 11
1 vote
0 answers
49 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 ...
DiegoLopez's user avatar
1 vote
1 answer
840 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 < ...
independentvariable's user avatar
1 vote
1 answer
323 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 $τ$ ...
aiootp's user avatar
  • 803
1 vote
1 answer
55 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 ...
phi.nm's user avatar
  • 15
0 votes
2 answers
515 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 ...
Guerlando OCs's user avatar
1 vote
0 answers
44 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 ...
Paprika's user avatar
  • 71
1 vote
1 answer
96 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 ...
Guerlando OCs's user avatar
2 votes
1 answer
86 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 ...
hiren_garai's user avatar
1 vote
0 answers
210 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. ...
partyTuringFriend's user avatar
2 votes
1 answer
455 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 ...
zackit's user avatar
  • 133
1 vote
0 answers
63 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 $...
UNOwen's user avatar
  • 11
9 votes
6 answers
8k 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 ...
DudeWhoWantsToLearn's user avatar
2 votes
2 answers
79 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 ...
Harry's user avatar
  • 129