# Tag Info

10

Thomas' first procedure produces 2 bits per roll with a probability of $\frac23$, i.e. it produces $\frac43 \doteq 1.333$ bits on the average. This can be improved as he describes, but it gets quite complicated soon. Producing a single bit per roll by taking the result mod two leads to $1$ bit per roll, which is not much worse. Combining the two simple ...

6

The obvious approach is to consider the following bit extraction algorithm: Roll the die, producing an integer $n$ uniform in $\mathbb{Z}_6$. If $n < 4$, return $n$ as two bits. Otherwise, go to 1. This will return two uniform bits. The algorithm will always terminate, since the probability of recursion is equal to $\frac{2}{6}$ which is ...

2

1 way to get 3 bits of entropy from a single die roll is as follows : Roll the fair die For 2,3,4,5 yield two bits {01,10,11,00} and go to 4, for 1 or 6 yield {1,0}. For the number on the die appearing right-way-up to the thrower (0-179 degrees) yield {0} for the number on the die appearing upside-down to the thrower (180-359 degrees) yield {1} and go to ...

2

In cryptography, addition modulo $n$ (where $n$ is a positive integer, maybe $n=32$ as in the original question, or $n=2^{32}$ as in the revised question) is usually understood as the application from $\mathbb Z\times \mathbb Z$ to $\mathbb Z$, $(a,b)\mapsto c$ with $c$ such that $0\le c<n$ and $(a+b-c)$ is a multiple of $n$. That's also a common sense in ...

2

There is no known way to compute $(g^a)^k \mod p = g^{ak} \mod p$, given only $g^k \mod p$ and $g^a \mod p$ as per the Decisional Diffie–Hellman assumption. This is roughly equivalent to the discrete log problem. This is described in more detail in this paper.

1

Efficient constant-time exponentiation algorithms exist. For example, one could calculate a sequence as follows: Given $a^{k}, a^{k+1}$ calculate either $a^{2k+2}, a^{2k+1}$ or $a^{2k}, a^{2k+1}$. Both calculations differ only in which value is squared and which is multiplied, making them easy to implement with a single conditional swap as the only ...

1

Timing attacks against a function $f_k$ generally require two things: The attacker might observe the target perform $f_k(x)$ for a large number of sufficiently diversified known inputs $x$. For each $k$, there are inputs $x$ and $x'$ such that $f_k(x)$ and $f_k(x')$ are expected to execute at different speed. Now, let's assume $f_k$ is the private key ...

1

I think you have a lack of knowledge on pairings and finite fields. Your definition of the pairing $e(X,Y)=g^{XY} \bmod p$ is not correct. A pairing is defined as a map $e : \mathbb{G}_1 \times \mathbb{G}_2 \to \mathbb{G}_T$ with the property \begin{align}\text{for all }g_1 \in \mathbb{G}_1 \text{ and } g_2 \in \mathbb{G}_2: e(g_1^a,g_2^b) = ...

Only top voted, non community-wiki answers of a minimum length are eligible