The 2024 Developer Survey results are live! See the results

# Questions tagged [blum-blum-shub]

The Blum Blum Shub generator is a deterministic Pseudo-Random Bit Generator with security demonstrably reducible to that of integer factorization.

21 questions
Filter by
Sorted by
Tagged with
22 views

### Generating arbitrary state/bit using Blum Blum Shub generaor. Simplification of Carmichael function term?

From wikipedia: An interesting characteristic of the Blum Blum Shub generator is the possibility to calculate any $x_i$ value directly (via Euler's theorem): x_i = \left( x_0^{2^i \bmod \lambda(M)} ...
460 views

### Period of Blum-Blum-Shub

Reading about Blum-Blum-Shub, I have found that everyone has stressed the importance of $gcd(p-1, q-1)$ being a small number, as this leads to a large period. I found it really difficult to find a ...
2k views

604 views

### Is BBS used for generation of keys for any modern cryptosystem?

Is there any (current) cryptosystem or digital signature or cryptographic primitive that uses the BBS PRG in order to generate its secret keys?
473 views

### Are factorization algorithms parallelizable?

I was reading about the Blum-Blum-Shub random number generator, and its security depends on the hardness of factoring very large numbers (like many things in crypto do). I'm just wondering, if I have ...
1 vote
309 views

### If Blum Blum Shub is modified to use a prime modulus, is it still secure?

The definition of the Blum Blum Shub cryptographically secure pseudorandom number generator is $x=x^2 \mod N$ where $N=p \times q$, $p \in \mathbb P$, and $q \in \mathbb P$. Supposedly, the security ...
1 vote
574 views

### Why is knowing M not enough to break Blum Blum Shub?

In Blum Blum Shub, the generator is $x_{n+1}={x_n}^2 \mod M$ where $M=p \cdot q$, $p \in \mathbb P$, and $q \in \mathbb P$. Supposedly, knowing $p$ and $q$ is enough to break the system. But if I know ...
1 vote
227 views

### Exploration of Blum Micali Security By Seed Size

I'm new to cryptography and am most intrigued by mathematically based pseudo random number generators. With reference to the Blum Micali algorithm: $X_{i+1} = G^{X_i} \bmod P$ can security be ...
939 views

### Advantages to knowing $p$ and $q$ in Blum Blum Shub?

Do you gain any advantage by knowing the factorization of $M$ (over just knowing $M$ itself) in the Blum Blum Shub generator? The only advantage I see is being able to calculate the $i$-th number ...
224 views

### Why is $-1$ an illegal message in the Goldwasser-Micali Encryption Scheme

I'm not sure why in the Goldwasser-Micali encryption scheme with a Blum integer $N$, the message $-1$ is always a illegal message. Can you give me some direction for starting? What is illegal ...
The Blum-Blum-Shub generator is a deterministic Pseudo-Random Bit Generator with security reducible to that of integer factorization. Setup: Secretly chose random primes $P$, $Q$, with \$P\equiv Q\...