Unanswered Questions
116 questions with no upvoted or accepted answers
8
votes
0
answers
355
views
Is the complexity of NIST's CTR_DRBG needed for security?
I'm trying to find an efficient deterministic PRF construction that can quickly output a large amount of pseudo-random data from a seed of collected entropy. I ran tests with a contruction based on ...
- 1,155
6
votes
0
answers
849
views
Is this PRG secure?
$G$ is a secure PRG in range $\{0,1\}^n\rightarrow\{0,1\}^{n+1}$.
Let us define $G'(S)=G(S\oplus G(S)_{1,...,n})$, s.t. $G(S)_{1,...,n}$ is the first n bits of $G(S)$.
Is $G'(S)$ a secure PRG?
...
- 46.6k
5
votes
0
answers
120
views
Hybrid Argument proof
I am trying to understand what the Hybrid Argument is in cryptography and why is it useful.
By the definition of the Hybrid Argument we know that to prove that if two distributions $D = D_1, D_2, ...,...
- 123
5
votes
0
answers
946
views
How can we formally define a Pseudo-Random Shuffle function?
My question is related to: When we turn Random shuffle to Pseudorandom Shuffle
The idea is to permute the elements in vector $\mathbf{v}$ pseudorandomly, where $|\mathbf{v}|=n$;
I am aware that we ...
CommunityBot
- 1
4
votes
0
answers
451
views
Why: $G'(s) = G(s_1, \ldots, s_{\lfloor{n/2}\rfloor})$, where $s = s_1, \ldots, s_n$ is PRG?
I'm a novice reader of Introduction to Modern Cryptography, where it states:
Let $G$ be a pseudorandom generator with expansion factor $\ell(n) > 2n$.
In each of the following cases, say whether $...
- 2,653
4
votes
0
answers
731
views
Can we construct a PRF directly from a one way permutation function?
In Introduction to Modern Cryptography first a pseudo random generator (PRG) is constructed from a one way function (OWF). After that the PRG is used to to construct pseudorandom functions (PRF). Is ...
- 95.8k
4
votes
0
answers
314
views
is a MAC defined by a pseudo random generator secure?
Let $ G:\{0,1\}^*\rightarrow\{0,1\}^*$ be a length doubling PRG, and let $ \Pi=(Gen,Mac,Vrfy)$ be the following MAC scheme:
$ Gen $ on input $ 1^n$ uniformly samples and outputs $ k\leftarrow \{0,1\}...
- 24.6k
4
votes
0
answers
247
views
Feasible way to check n-dimensional equidistribution of PRNGs
I am currently gathering some test methods and test suites for random number generator qualities, and am a bit stuck at finding something feasible to test for n-dimensional equidistribution. As input ...
- 18.1k
4
votes
0
answers
267
views
Integer factorization based password authentication
After looking at this security issue at DjangoProject, I started to think in a password-based authentication that places the burden of PBKDF2 (or whatever is the hashing function) on the client. So I ...
- 231
3
votes
0
answers
84
views
Deriving a cryptographic PRNG from a publicly random sequence
Consider a model of computation where we have a public oracle that provides access to a random sequence $R$. Given an index $i$ the oracle returns either 0 or 1, with the responses being deterministic,...
- 131
3
votes
0
answers
108
views
Proving that a PRG is predictable
I am attending the video lectures from Prof Dan Boneh. He gives the following example.
Let $G:\mathcal K\longrightarrow \Bbb Z_2^n$ be a PRG with the property that from the last $\frac{n}{2}$ digits ...
- 266
3
votes
0
answers
270
views
Exchanging key and input in GGM tree?
I am currently working through the exercises in A Graduate Course in Applied Cryptography by Dan Boneh. I am stuck on exercise 4.16 (page 188 in this PDF)
In the GGM tree construction for constructing ...
- 23
3
votes
1
answer
1k
views
Breaking a Mersenne-twister RNG with unsequential outputs
Pardon me for this newbie-ish question. I'm still a novice in cryptography . I have an application that outputs random numbers from 0 - 12 (endpoints inclusive) unsequentially (some outputs are thrown ...
CommunityBot
- 1
3
votes
0
answers
273
views
Finding the cycle sets of an LCG
My LCG has the form:
$$S_0 = k$$
$$S_{n+1} = S_n \times a + 1 \pmod m$$
Each choice of $k$ generates a different sequence but in some cases a sequence may just be a cyclic shift of another. In this ...
- 31
3
votes
0
answers
659
views
Is a PRG that reveals the first bit of the input secure
Let $G:(0,1)^n \rightarrow (0,1)^{n+1}$ be a secure PRG.
Define $G'(s):=s_1 ||G(s)_{2,...,n+1} $.
($||$ is concatenation, and the subscript $ _{2,...,n+1}$ means the last $n$ bits of $G$)
I claim ...
- 325