# Questions tagged [probability]

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

88 questions
Filter by
Sorted by
Tagged with
1 vote
69 views

### An upper bound for advantage in a security game

Suppose I have defined a security game in a private-key (symmetric) encryption scheme. Remark: Note that encryption algorithm is probabilistic, so for a specific message m, $Enc_k(m)$ might output a ...
• 25
49 views

### How to understand the counterexample constructed in the PRP/PRF switching lemma towards the standard proof?

I'm reading a paper Code-Based Game-Playing Proofs and the Security of Triple Encryption , which indicates an error on the standard proof of the PRP/PRF switching lemma using the conditional ...
1 vote
44 views

### Miller-Rabin primality test strong liar probability

This might be an old topic. It is said that the probability a number is a strong liar to a composite number is less than 1/4 for one round of Miller-Rabin test, but I found it to be far less, ...
• 11
1 vote
71 views

### Reject sampling of lattice ZKP, why need factor of M

I am watching the video https://www.youtube.com/live/N5nKGtugxYY?si=ejLqW8Pk0jD9lVMn&t=2098 Or particularly this slide: May I ask why does the reject sampling output by $f(x)/g(x)*M$ probability? ...
• 361
1 vote
39 views

• 246
1 vote
44 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 ...
• 111
413 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 ...
• 33
176 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 ...
• 558
1 vote
142 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 ...
1 vote
211 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 ...
238 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 ...
85 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)...
• 2,262
194 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 ...
• 982
115 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 ...
165 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 ...
• 45
1 vote
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 '...
639 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 ...
• 424
63 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 ...
• 117
1 vote
112 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 ...
• 155
56 views

1 vote
334 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,116
1 vote
58 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 ...
• 15
532 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
48 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 ...
• 71
1 vote
103 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 ...
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 ...