Questions tagged [randomness]
Usage of randomness (i.e. non-predictable data, usually in the form of bits or numbers) for cryptographic purposes.
57
questions with no upvoted or accepted answers
5
votes
0
answers
191
views
Reusing same source for single-source randomness extractor
Let $ext$ be a single-source randomness extractor which takes a $d$-bit seed
and a $n$-bit source as input and produces a $m$-bit output.
Suppose we have a source $X$ with min-entropy $k$. Is it ...
- 51
4
votes
0
answers
375
views
Use of scrambler LFSR for randomness extraction of semi-random source
I am using a linear feedback shift register (LFSR) in a scrambler configuration as a randomness extractor for a weakly random source. This source is semi-random (aka. Santha-Vazirani source): the bits ...
- 453
4
votes
0
answers
170
views
Use of randomness in an Elgamal like encryption
Suppose I have the following encryption scheme: for a message $m\in\mathbb{F}_p^*$, I generate the ciphertext = $(g^r,f^mh^r)$ where $g$ is the generator of a cyclic group $G$ of unknown order $n$ and ...
- 263
4
votes
0
answers
237
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 ...
- 160
3
votes
0
answers
65
views
Computational Randomized Encoding in the hybrid proof
A computational randomized encoding scheme $(\textrm{RE.Encode}, \textrm{RE.Decode})$ works as follows:
$\textrm{RE.Encode}(1^\lambda, C, x, r)$: takes as input the security parameter $\lambda$ in ...
- 932
2
votes
0
answers
42
views
Deterministically secure PRG from deterministically secure OWF
Consider the construction of "A Pseudorandom Generator from any One-way Function" [HILL99] in Hastad et al.
One way to proof pseudorandomness of this construction is by contradiction.
That ...
- 161
2
votes
0
answers
30
views
Safe p-value for NIST randomness test with small sample size
In this journal paper related to physically unclonable function (PUF) [1], the authors used NIST 800-22 test to check if the bitstreams generated by their PUFs are random, which is described as ...
- 121
2
votes
0
answers
111
views
Extractor and Min-Entropy proof
I'm following a course that speaks about cryptography. In this course we talked about Min-Entropy ($H_{\infty}$) and Extractor. To show that an extractor $Ext:\{0,1\}^n \rightarrow \{0,1\}^l$ that ...
2
votes
0
answers
94
views
Fisher Yates on "faulted" random number generator cryptanalysis
For the sake of curiosity and fun, i have implemented a C# program that operate as deck dealer on 40 cards deck (following the Fisher Yates shuffeling algorithm https://en.wikipedia.org/wiki/Fisher%E2%...
- 361
2
votes
0
answers
339
views
How Are Linear Congruential Generator Multipliers Chosen?
There are several numbers that keep coming up when looking at certain random number generators, for example 6364136223846793005 is used in newer pcg-family algorithms and seems to draw it from ...
- 143
2
votes
0
answers
497
views
Can Verifiable Random Functions be used to pick a random node from a pool?
Let's say that I have a decentralized system and I have a list of nodes published on a public log like a blockchain. I want a node A to be able to connect to ...
- 161
2
votes
0
answers
86
views
Is the number still a CSPRN if we only allow an interval from a CSPRNG?
tr -dc 0-9 < /dev/urandom | fold -w 3 | awk '$0>=100 && $0<=200'
What this line does:
/dev/urandom (Linux) is proven to be a CSPRNG, that is ...
- 21
2
votes
0
answers
120
views
Special random distribution algorithm
I am implementing ring signatures as a part of an authorization system. Since the number of users could get high enough to make computation on end-user devices infeasible, I am thinking of "...
- 33
2
votes
1
answer
243
views
How to verify the claim of entropy available made by Linux 4.5?
The Linux kernel has an entropy source and it estimates its amount of bits in the device /proc/sys/kernel/random/entropy_avail. How can I verify that this number ...
- 21
1
vote
0
answers
141
views
If G is a PRG, is G' necessarily a PRG?
Given:
A function $$G: \{0,1\}^{3n} \to \{0,1\}^{6n}$$ which is known to be a secure Pseudorandom Generator (PRG).
A derived function $$G'(x_1 \| x_2) = G_b(x_1\|0^n\|x_2), \text{ where } x_1, x_2 \...
- 11
1
vote
0
answers
72
views
Two-party randomness for KEM
As indicated in an earlier Q / A, KEM's do not necessarily directly encrypt a pre-generated random value. However, it is clear that some KEM's do actually do this, with RSA-KEM being an obvious ...
- 92k
1
vote
0
answers
129
views
Probability of getting a collision using chosen plaintext attacks
For university I am doing a piece of coursework right now. This question is focusing on CPA and collisions using CPA.
Question:
I have attempted to answer part 3, but am not very confident in the ...
- 77
1
vote
1
answer
135
views
Indistinguishability obfuscation and PRFs
Consider a family of pseudorandom functions $F$, each member $f_k$ of this family is indexed by a key $k$. It is true, due to a result by Barak et al, that black box obfuscation is not possible for a ...
- 377
1
vote
0
answers
170
views
Is ChaCha20 + HMAC(SHA3) output indistinguishable from randomness?
I was wondering, if the output of following type of ChaCha + HMAC scheme is indistinguishable from randomness:
...
1
vote
0
answers
274
views
How secure is it to use a 128-bit random seed to derive a 256-bit key for seeding key-pair generation?
We are developing an open-source peer-to-peer app, Mapeo, designed for users with low technical experience (and no email or phone) to collect data in offline environments. We are generating their ...
- 11
1
vote
0
answers
124
views
Cryptographic Random Beacon VS Random Oracle
Let's start with what I mean by cryptographic random beacon (RB).
A RB is a protocol among some parties who generate a random value all together such that:
these parties do not trust each other
the ...
- 385
1
vote
0
answers
181
views
Sentinel ("trick") values for lattice attack on DSA with biased k (MSB)
I'm studying lattice attack using this sage script. There are 2 options in script: LSB and MSB. The most interesting option for me is MSB. It recovers private key with less then 100 signatures ...
- 11
1
vote
0
answers
84
views
How does a pseudorandom generator produce a similar distribution to $U_{n}$?
According to Wikipedia, a function ${\displaystyle G:\{0,1\}^{\ell }\to \{0,1\}^{n}}$ with ${\displaystyle \ell < n}$ is a pseudorandom generator against $\mathcal {A}$ with bias $\epsilon$ if, ...
- 167
1
vote
0
answers
81
views
Min Entropy per Bit for Trevisan's Extractor/or An Extractor
We know that: trevisan's extractor based on min entropy of the relative system. For trevisan extractor, we need source, seed, min entropy value per bit and error rate for per bit
I have the code for ...
- 151
1
vote
0
answers
67
views
NIST STS randomness testing inconsistent results
I have generated the nine datasets according to this document for AES-128 and testing these for randomness using NIST STS. However, the results are inconsistent. Sometimes there appear a * in the ...
- 2,397
1
vote
0
answers
90
views
libgcrypt and rdrand usage
For some reasons, I was looking into libgcrypt source code and found this.
If I understand this correctly, while asking to use /dev/random for some bytes, it actually checks first if rdrand is ...
- 11
1
vote
0
answers
145
views
Would the result of encrypting weak random data via AES-128 with a CSPRNG-generated key be considered strong/secure random data?
I am trying to understand the security implications of using a well known block (or stream but in this example block) cipher like AES-128 to produce pseudo-random data.
My specific question is would ...
- 111
1
vote
0
answers
147
views
Why does a "never-repeating" nonce limit a key to safely encrypt only a single block?
This questions comes from a section outlined in RFC 5297 on SIV-AES. The paragraph in particular outlines the idea of a never repeating nonce vs an "almost always" non-repeating nonce.
If ...
- 111
1
vote
0
answers
85
views
Randomness Test of Permuted Sequence
As we can generate a permuted sequence using KEY in KSA (Key Scheduling Algo) of RC4. Is there any way to check the randomness of the permuted sequence?
Let say I created 100 different permuted ...
1
vote
0
answers
87
views
What is fixed randomness and unfixed randomness?
I have found these notions recently in an article. What is fixed randomness ? What is unfixed randomness ?
Link of the article : http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.431.9034&...
1
vote
0
answers
112
views
Is there an algorithm or protocol that allows to securely generate random shuffles when two parties are not colluding without a sever side seed?
I am building an app that pits one party against another party in a gambling transaction – both parties have competing interests and have an incentive not to cheat the other party.
I am looking for a ...
- 31
1
vote
0
answers
75
views
Beginners question about revealing randomness in probabilistic asymmetric encryption
I am encrypting "1" with probabilistic encryption with a foreign public key (I don't have the private key for it) which results in an encrypted file e.
Can I prove to a third party, that e contains ...
- 111
1
vote
0
answers
83
views
RIsk mitigation: block cypher vs xor
It sort of looks like to me that there is a kind of risk mitigation in the architecture of block cyphers vs the xor cypher.
In XOR, the risk is entirely in the random number generator. The XOR ...
- 533
1
vote
0
answers
56
views
Fuzzy Extractor: Order of elements in set
Does order of elements in two sets matters to authenticate using Fuzzy Extractor?
Using extractor as proposed in https://www.cs.bu.edu/~reyzin/fuzzy.html
it seems the set difference is zero for this ...
- 195
1
vote
0
answers
79
views
Lsb as hard core predicate in a sign-hash scheme
Given a random oracle and a deterministic signature scheme.
Is the following $hc(x)$ an hardcore predicate of $H(SIG_k(x))$ ?
$$hc(x)=lsb(H(SIG_k(x)))$$
How would I get to think about this? I saw a ...
- 763
1
vote
0
answers
574
views
Relationship between "Entropy" and "Security" in crypto functions
There is a lot of confusion between "entropy" and "security" of a cryptographic function.
I like to visualize it as the entropy being the water, and the crypto function being a glass.
So for ...
- 533
1
vote
0
answers
58
views
Does RSA_PRBG security depend on keeping seed secret?
The HAC provides a PRBG using RSA (Chapter 5 p.185):
It appears the seed must be kept secret if $e$ is a well known value. If $e$ is uniformly distributed between 1 and $\phi$, then the seed does not ...
user10496
1
vote
0
answers
252
views
PHP predicting array_rand
Given the following PHP code (assuming PHP 5.6.x):
...
1
vote
0
answers
99
views
To prove $r_2$ is a uniformly at random value in $Z_n$, where $r_2=r_1 . m$
$m$ is arbitrary value in $Z_n$, where n is RSA modulo. Then we do: $r_2=r_1 . m (modn)$, where $r_1$ is a random value such that $r_1\in Z^*_n$.
** Question(1): is $r_2$ a uniformly at random ...
- 1,573
1
vote
1
answer
67
views
About two sequence conversion methods in NIST 800-90B
I am reading the 800-90B document.
In particular, I'm looking at Chapter 5, the chapter on checking that samples conform to IID.
There are 11 tests such as Excursion Test Statistic and Number of ...
- 315
1
vote
1
answer
114
views
Can we apply the Pseudo Random Number (PRNG) as post processing method for True Random Number (TRNG)?
From the NIST SP 800-90B, we can use these cryptographic algorithms (HMAC, AES, Hash function) as a post-processing technique for TRNG.
Besides that, can we apply the Pseudo Random Number (PRNG) as a ...
- 83
0
votes
0
answers
48
views
Generating UUID from Keccak-256 hash
Is generating Keccak-256 hashes with timestamp + nonce (ensured to be unique for each run), and taking its most significant 16 bytes sufficient to generate random V4 UUIDs?
Obviously the 13th hex ...
- 101
0
votes
0
answers
45
views
Does randomization make a big difference in the output of the BKZ algorithm?
We all know that block Korkine-Zolotarev (BKZ) algorithm is essentially a deterministic lattice reduction algorithm. However, in the actual implementation, the BKZ algorithm contains some ...
- 147
0
votes
0
answers
68
views
Why is decryption algorithm usyally deterministic?
For security against Chosen Plaintext Attack (CPA), we need randomized algorithms for encryption. But in some schemes (maybe almost all of them) take decryption algorithm deterministic. This procedure ...
- 363
0
votes
0
answers
31
views
How many number of sequences (sample size) should be selected for randomness testing of bock cipher with 256 bits key and block length?
I am working on randomness testing of block cipher. I have gone through the NIST two papers of randomness testing of AES candidate algorithm, links are given below
https://csrc.nist.gov/csrc/media/...
0
votes
0
answers
96
views
Synchronized random number generation
Let me try to reformulate the problem, as it might help a bit. The requirements are the following:
At the beginning of their connection, the two end-points perform a Diffie-Hellman to derive with a ...
- 735
0
votes
0
answers
47
views
Can disjoint distributions be Computationally indistinguishable?
As mentioned in these notes definition 2
We say that $\{Xn\}_n$ and $\{Yn\}_n$ are computationally indistinguishable if,
for all $\mathsf{nuPPT}$ $D$, there exists a negligible function $ε$ such that ...
- 251
0
votes
0
answers
47
views
Alter signature post signing without the private key
There a plethora of signature scheme's but I am wondering if there are scheme's with the following properties:
Given that you know the message, alter the signature with the public key in such a way ...
- 135
0
votes
0
answers
72
views
How do I retrieve a number which has been multiplied with a random number?
I have a 1024-bit number $n$ obtained by multiplying two 512-bit randomly generated prime numbers $p$ and $q$.
Then there's $\phi = (p-1)(q-1)$, which is another 1024-bit number.
I do not have $\phi$ ...
0
votes
0
answers
171
views
Randomness Testing of Block Ciphers with 256-bit Block/ Key length
NIST explained the process of "Randomness Testing of the AES Candidate Algorithms" in the document.
The document explains the generation of 9 datasets for AES candidates with 128-bit block ...
- 2,397