Forward-secure Public Key Encryption scheme

Implementation of research paper from Canetti, Halevi and Katz A Forward-Secure Public-Key Encryption Scheme

Modifications on the bilinear pairing function

In A Forward-Secure Public-Key Encryption Scheme, the authors make use of a bilinear pairing function of type 1, namely a function where both inputs come from the same elliptic curve group as $e \ : G_1 \times G_1 \rightarrow G_t$. This type of function is not commonly used today because of security and efficiency reasons. They require the use of supersingular curves which are less efficient compared to ordinary elliptic curves and especially vulnerable to the MOV attack.

For that reason we had to modify the original work to use a type 3 pairing function of the form $e \ : G_1 \times G_2 \rightarrow G_t$

Notation

SecretKey represents a secret key used to decrypt a ciphertext.
SecretKeys represents a stack composed of SecretKey.
epsilon represents the empty string.

Approach

The fspke scheme is based on a Binary Tree encryption scheme. A binary tree composed of N nodes is deployed and its pre-order transversal will determine the correspondence between a period and a node.

By example, if we have $N = 15$, here is the corresponding binary tree. Each node is composed of a binary word $w_i$ where the root word is the empty string $w_0 = \epsilon$. The following pre-oder transversal allows to get a correspondence between a period and a node and therefore a word (see function _compute\_wi_ in [utils.rs](./src/utils.rs))

Here is the matching between period and word $w_i$ for a binary tree of $N=15$ nodes.

Period index $i$	word $w_i$
0	$\epsilon$
1	0
2	00
3	000
4	001
5	01
6	010
7	011
8	1
9	10
10	100
11	101
12	11
13	110
14	111

Functions description

keygen

Takes as input $N$ the total amount of periods and generates a public key and a stack of secret keys composed of secretkey for the first period (period 0).
Public key will always remain the same and secret key will vary over periods.

update

Takes as input the public key (which stores parameter $N$), the private key stack $ski_prime$ and the index of the current period $i$. It simulates the respective binary tree to localize the current node and determine if it is a leaf. If so, the next key on top of the stack will be the next private key. If not, it runs $der$ function to push 2 newly computed private keys and takes the left son node respective private key as the one to use in the next period.

der

Takes as input the public key, the word corresponding to the node of the current period $w_i$ and the current secret key. It generates and returns the respective secret keys of the two sons of the current node.

enc

Takes as input the public key, the index of the current period $i$ and the message $m$ to encrypt. Uses the bilinear mapping function $ê$. Ciphertext is composed as following:
 pub struct Ciphertext {
          u0: G1Affine,
          ui: Vec,
          v: Fq12,
 }

dec

Takes as input the public key, the index of the current period $i$, the secret keys stack and the ciphertext to decrypt. Uses the bilinear mapping function $ê$. Returns the correct plaintext message if the ciphertext has been correctly encrypted with the respective period's index.

compute_l

Takes the total amount of periods $N$ as input and computes the depth of a binary tree of $N$ nodes.

compute_wi

Takes as input the total amount of periods $N$ and the index of a period $i$ and returns a word $w_i$ composed of $i$ first elements of a pre-order transversal of a binary tree of $N$ elements as shown in the previous tabular example.

string_to_g2_affine

A straightforward function that converts a string input into a G2Affine element.