Mathematical Prove (3)

Bilinear Pairing over Composite Group

Given groups $\mathbb{G}$ and $\mathbb{G}_T$ of order $N=pq$ where $p,q$ are prime, and a bilinear pairing $e: \mathbb{G} \times \mathbb{G} \rightarrow \mathbb{G}_T$.

The subgroups of $\mathbb{G}$ with size $p,q$ are defined as $\mathbb{G}_p$ and $\mathbb{G}_q$. Let generator of $\mathbb{G}$ be $g$. The generators of $\mathbb{G}_p$ and $\mathbb{G}_q$ be $g_p$ and $g_q$ can be computed as $g_p = g^q \in \mathbb{G}_p$ and $g_q = g^p \in \mathbb{G}_q$

In addition to basic bilinear pairing properties, bilinear pairing over composite group holds some additional properties:

• $e(g_p,g_q) = e(g^q,g^p) = e(g,g)^{pq} = e(g,g)^N = 1$
• $e({g_p}^a{g_q}^b,{g_p}^c) = e(g^{qa+pb}, g^{qc}) = e(g,g)^{q^2ac+Nbc} = e({g_p}^a,{g_p}^c)$

Attribute-based Broadcast Encryption

Attribute-based Broadcast Encryption (ABBE) makes use of Attribute-based Encryption scheme to implement broadcast encryption. In attribute-based encryption, a ciphertext is bundled with a data access policy (policy for short) which consists of a list of attributes connected by logic gates (typically AND and OR). Each user in the system possesses a list of attributes. To determine if a user is a legitimate decryptor of the ciphertext, the system compares his attributes with the policy. If the policy is satisfied, the user is able to decrypt the ciphertext.

Compared with conventional broadcast encryption, attribute-based encryption is like separating users into different groups and the access control (using policy) is enforced by manipulating access controls in those groups. If the number of attributes is much less than the total number of users in the system, ABBE has a big advantage on efficiency. However, it cannot enforce ad-hoc access control on every individual user like conventional broadcast encryption.

Hence, some proposed using each bit of user ID as attribute, which makes the total number of attributes becomes log N (assuming N users). This number is much smaller than the total number of users and it sounds promising. However, during my study I found two major problems in this scheme when the number of legitimate users grows large.

First, in order to get a small ciphertext size, the scheme uses Boolean algebra simplification algorithm. The idea is to first list all user IDs of legitimate users in a truth table, then applies the simplification algorithm to get a shorter Boolean algebra expression without altering its result, and this problem is NP-Hard. The two most famous algorithms for this task are Quine-McCluskey algorithm and Espresso heuristic logic minimizer. The complexity of them is yet to be found, but according to my preliminary testing, the running time (for just Boolean algebra simplification) can be much longer than running encryption of Boneh's broadcast encryption. A better simplification algorithm or a better implementation of it is required.

Second, the number of sum-of-product terms output from the simplification is not a constant. In other words, the ciphertext of this scheme will have a variable size. And this leads to a question: How large can the size be? I found it difficult searching for or understanding literature which discusses about this problem. Therefore, I try to run my own test again. I tried to compute both average case and worst case on small N (since I have to generate all combinations, it is already very large even for small N, e.g. 32). From my test, the growth of average size seems to be O(log N). For worst case, however, the size seems to be N/2. In my opinion, the problem is how often the size stays at O(log N). In real application, I think a good average bound is not enough, a good worst case bound is needed. Imagine when N = 10M, N/2 will be 5M and it results in a enormous ciphertext size.

Mathematical Prove (2)

Prove $e(A,X+Y) = e(A,X) \cdot e(A,Y)$ where $e: \mathbb{G} \times \mathbb{G} \rightarrow \mathbb{G}_T$ is a bilinear pairing and $A,X,Y \in \mathbb{G}$

Since $X,Y \in \mathbb{G}$, assume $X = xP, Y = yP $ where $ P $ is a generator of $\mathbb{G}, x,y \in \mathbb{Z}_p$ where $p$ is the order of $\mathbb{G}$
$e(A,X+Y) = e(A,xP+yP) = e(A,P)^{x+y} = e(A,P)^x \cdot e(A,P)^y$
$= e(A,xP) \cdot e(A,yP) = e(A,X) \cdot e(A,Y)$

Mathematical Prove (1)

Prove $(1-x)^{x^{-1}N} < e^{-N}$ for $x \in (0,1)$

Assume $(1-x)^{x^{-1}N} < e^{-N}$, then
$ln((1-x)^{x^{-1}N}) < -N$
$x^{-1}Nln(1-x) < -N$
$x^{-1} ln(1-x) < -1$
$ln(1-x) < -x$
$ln(1-x) + x < 0$

So we can prove $ln(1-x) + x < 0$ instead
Let $f(x) = ln(1-x) + x$,
$f'(x) = \frac{d}{d(1-x)}ln(1-x)\cdot\frac{d}{dx}(1-x)+\frac{dx}{dx} = -\frac{1}{1-x} + 1$

Since $f'(x) < 0$ for $x \in (0,1)$ and $f'(x) = 0$ when $x = 0$, $f(x)$ is strictly decreasing for $x \in (0,1)$ with the greatest value $f(0) = ln(1-0) + 0 = 0$. Therefore, $f(x) < 0$ for $x \in (0,1)$ and so $(1-x)^{x^{-1}N} < e^{-N}$ for $x \in (0,1)$

The Legendre Symbol

Introduction:

The Legendre Symbol tells us that whether a number $x \in \mathbf{Z}^*_p$ where p is prime is a perfect square (also called quadratic residue).

Definition:

For a prime p and $x \in \mathbf{Z}^*_p$, the Legendre Symbol $\mathbf{J}_p(x)$ is defined as:
$\mathbf{J}_p(x) = \begin{cases} 1 & \mbox{if } x\mbox{ is a perfect square in }\mathbf{Z}^*_p \\ 0 & \mbox{if }gcd(x,p) \neq 1 \\ -1 & \mbox{if } x\mbox{ is not a perfect square in }\mathbf{Z}^*_p \end{cases}$
The Legendre Symbol is computed by $\mathbf{J}_p(x) \equiv x^{\frac{p-1}{2}} \mbox{ mod } p$

Discussion and Proof:

• Since p is prime, $x = kp$ where $k \in \mathbb{Z}$ if $gcd(x,p) \neq 1$. As a result, $\mathbf{J}_p(x) = (kp)^{\frac{p-1}{2}} = 0 \mbox{ mod } p$
• If x is a perfect square in $\mathbf{Z}^*_p$ and g is a generator of $\mathbf{Z}^*_p$, x can be written as $g^{2i} \mbox{ mod } p \mbox{ where } 1 \leq 2i \leq p-1$. As a result, $\mathbf{J}_p(x) = g^{\frac{2i(p-1)}{2}} = g^{i(p-1)} = 1 \mbox{ mod }p$
• If x is not a perfect square in $\mathbf{Z}^*_p$ and g is a generator of $\mathbf{Z}^*_p$, x can be written as $g^{i} \mbox{ mod } p \mbox{ where } 1 \leq i \leq p-1$. Since i is odd, $\frac{i(p-1)}{2}$ is not an integer and $\mathbf{J}_p(x) = g^{\frac{i(p-1)}{2}} = \sqrt{1} = \pm{1}$. However, this does not quite match the definition. To continue the proof, we have to prove thatx is a perfect square in $\mathbf{Z}^*_p$ if and only if $x^{\frac{p-1}{2}} = 1 \mbox{ mod } p$:
  $\Rightarrow$ Assume x is a perfect square in $\mathbf{Z}^*_p$, x can be written as $g^{2i} \mbox{ mod } p \mbox{ where } 1 \leq 2i \leq p-1$ and $\mathbf{J}_p(x) = g^{\frac{2i(p-1)}{2}} = g^{i(p-1)} = 1 \mbox{ mod }p$
  $\Leftarrow$ Assume $x^{\frac{p-1}{2}} = 1 \mbox{ mod } p$. Since $x \in \mathbf{Z}^*_p$, x can be written as $g^{i} \mbox{ mod } p$ where $1 \leq i \leq p-1$. Since g is a generator of $\mathbf{Z}^*_p$, g has the order $(p-1)$. Only $g^{p-1} \equiv 1 \mbox{ mod } p$ and $g^i \not\equiv 1 \mbox{ for } i < p-1$. As a result, $(p-1)$  must divide $\frac{i(p-1)}{2}$ and so i is even and x is a perfect square in $\mathbf{Z}^*_p$
  As a result, $\mathbf{J}_p(x) \neq 1$ if x is not a perfect square in $\mathbf{Z}^*_p$ and so $\mathbf{J}_p(x) = -1$

Negligible Function

Introduction:

Modern cryptography concerns about infeasibility rather than impossibility. For example, an encryption scheme is said to be provably secure if the success probability of "breaking" by an adversary is negligibly small rather than zero. Theoretically, the probability is expressed as a probability function of a security parameter k, which is normally the cryptographic key length. Infeasiblity relies on that the success probability function to be a negligible function.

Definition:

A function $f$ is negligible if for every constant $c \geq 0$ there exists an integer $k_c$ such that $f(k) < k^{-c}$ for all $k \geq k_c$

Notes:

The above definition means that the function $f$ is bounded by any positive polynomial fraction. Since for any positive polynomial fraction $g(x)$, we can always find the smallest $c$ such that $k^{-c} \leq g(x)$ for all $k \geq k_c$. Here, by the meaning of $k \geq k_c$, we can also say that the condition holds for a sufficiently large k.

Broadcast Encryption

Broadcast encryption is a scheme which only allows qualified users to decrypt published content. Typically users are separated into subscribed users who have access to the content and unsubscribed users who do not have the access. Conventional broadcast encryption scheme uses a master secret key to encrypt the content which results in only a trusted designer of the system is allowed to produce encrypted content. This type of broadcast encryption is commonly used in Conditional Access System (CAS) such as Cable-TV.

More recently another type of broadcast encryption scheme called public key broadcast encryption was proposed which consists of a system-wide public key. With this public key, every user can produce encrypted content which only a subset of users can decrypt with their own private keys.