Q1 SecureBox Protocal Design

1.1 Task Description

Authenticated data structures problem: You are designing SecureBox, an authenticated online file storage system. For simplicity, there is only a single folder. Users must be able to add, edit, delete, and retrieve files, and to list the folder contents.

When a user retrieves a file, SecureBox must provide a proof that the file hasn’t been tampered with since its last update. If a file with the given name doesn’t exist, the server must report that — again with a proof. Design a protocol such that proof size, verification time, and digest size are all sub-linear.

1.2 Parameters Choose

For the Hash algorithm, I choose SHA-256. And the ECC is used as Asymmetric Encryption Algorithm with key length = 106 bites. According to the paper, the strength is equailvalent to RSA-512.

1.3 Protocal Process

Part 1: Key Agreement

1. First of all, User A use his secret key to encrypt his $ID_A$ with a randomly generated key $K_A$.

$$ A \rightarrow S: ID_A \| E_{SK_A}[ID_A \| K_A ] $$

1. The server uses $PK_A$ to check wether the message is from A. If this message is from A, store $K_A$, then randomly generate a key $K_S$ and send to A as belows:

$$ S \rightarrow A: ID_S \| E_{SK_S}[\ ID_S \| K_A \| K_S ] $$

1. When A receives the message from step 2, he also need to check whether the message is from the sever and whether contains $K_A$. If the verification passes, then the $K_S$ is stored and A will send an ACK with $K_S$ to the sever for response.

$$ A \rightarrow S: ID_A \| E_{SK_A}[ID_A \| K_S \| ACK ] $$

1. After the sever receives ACK message from step 3, User A and Server can use $K = (K_A \| K_S)$ as their session key.

Part 2: Communication

When the communication establishes, both Server and User A can make sure that they are commnunicating with the other. In other words, User A is sure that he is communicating with the server and the server is also sure to connect with A. When User A needs to send request to the server, adding, editing, deleting or retrieving files and wants to list the folder contents. Different operations are described by FLAG.

• Add file

$$ A \rightarrow S: E_K[ FLAG \| FileName \| File \| E_{SK_A}[H(File)]] $$

and the FLAG = add

• Edit, delete or retrieve File

$$ A \rightarrow S: E_K[ FLAG \| FileName] $$

and the FLAG = edit / delete / retrieve

• List the folder contents

$$ A \rightarrow S: E_K[ FLAG \| FolderPath] $$

and the FLAG = list

After receiving the request from user A. The server will use the session key to decrypt the message, verify the request and read FLAG to decide what to do: add, edit, delete or retrieve file, or list folder contents. Finally, the server sends the code ( error code ) and message ( detailed info ) to user .

$$ S \rightarrow A: E_K[ Code \| Message] $$

On the web server File Storage System, for simplicity, all files are save in single folder. Moreover, we also need a database to save the key-value $Filename : E_{SK_A}[H(File)]$.

• User A wants to edit, delete or retrieve file

When user A want to operate a file, it will check if the file with the same FileName exists. If the file cannot not find, throw out errors info for response. If the file exists, then the server would check by caclulating:

$$ D_{PK_A}\{ E_{SK_A}[H(File)] \} \overset{?}{=} H(File) $$

If TRUE, it means that A owns this file and the file hasn't been tampered ( file integrity ). Therefore, he can edit, delete or retrieve file. If False, user A has no permission to operate this file or the file has been probably damaged.

• User A wants to add (upload) file on the server

If the sever cannot find the file with Filename. The file will be stored on the server and a new record is inserted in database: $Filename : E_{SK_A}[H(File)]$.

If the file with the same name has already exsits, the server first calculates

$$ D_{PK_A}\{ E_{SK_A}[H(File)] \} \overset{?}{=} H(File) $$

to verify the ownership of this file.

If A owns the file, the old one will be overwritten by new file with related database record updated. If the file doesn't belong to A, the permission error is thrown out.

• List folders contents

This is the most easiest one because we don't limit the accessibility of different users to the folders. All users can see the folder contents and only operating files needs permission.

Q2 Shamir's Secret Sharing Problem

2.1 Problem Description

One such scheme uses $n=6, k=3$ and following secret share points in the plane:

(1,1494)
(2,1942)
(3,2578)
(4,3402)
(5,4414)
(6,5614)

1. Reconstruct $f(x)$ and recover the secret $S$;
2. Prove that any subset of 3 points will do.

2.2 Solution

Because $k = 3$, we only need to pick three points to reconstruct $f(s)$ and recover secret $S$. I use these three points (1,1494), (2,1942), (3,2578) and numpy is used to help me solve this set of equations

$$ a_0 + a_1x_1 + a_2x_1^2 = y_1 \\ a_0 + a_1x_2 + a_2x_2^2 = y_2 \\ a_0 + a_1x_3 + a_2x_3^2 = y_3 $$

$a_0,a_1,a_2$ can be solved by computing matrix multiplication.

$$ \begin{bmatrix} a_0 \\ a_1 \\ a_2 \end{bmatrix} = \begin{bmatrix} 1 & x_1 & x_1^2 \\ 1 & x_2 & x_2^2 \\ 1 & x_2 & x_2^2 \end{bmatrix}^{-1} \begin{bmatrix} y_1 \\ y_2 \\ y_3 \end{bmatrix} $$

The following code do this

import numpy as np

X = np.matrix([
    [1, 1, 1],
    [1, 2, 4],
    [1, 3, 9],
])
Y = np.matrix([1494, 1942, 2578]).reshape(-1,1)
X.I.dot(Y)

The result is

matrix([[1234.],
        [ 166.],
        [  94.]])

Therefore, we can reconstruct $f(x)$

$$ \begin{aligned} f(x) &= a_0 + a_1x + a_2x^2 \\ &= 1234 + 166x + 94x^2 \end{aligned} $$

Let $x=0$, we can get the secret $S=1234$.

To prove that any subset of 3 points will do, we need to realize that $f(x) = a_0 + a_1x + a_2x^2$ represents a quadratic curve in the plane coordinate system and 3 points determine a quadratic curve. Therefore, given a quadratic equation, if we want to solve $a_0,a_1,a_2$, we at least need three points and any subset of 3 points can reconstruct the curve equation.

Q3 Electric Motor Bike Charge Application

3.1 Problem Description

Assume the charge is free for each session of 20 minutes charge, if user chooses to watch an one-minute advertisement on the mobile phone. Otherwise the user will have to pay a fee for the charge. Please design a secure blockchain ledger system for charge station owners, users, and advertisers.

The system can record the charge usage, ads views, and the token reward program such that the token reward is based on the charge station usage. Design your process such that the “reward program” data is secure for all parties and cannot be colluded to fake usage (to earn reward tokens) or fake viewing advertisement (to earn free charge).

3.2 System Design

Before discussing the charging payment and advertisement reward, we need to define the structure of our secure blockchain ledger system.

We first define the structure of block:

type Block struct {
    Header        *Header
    MarkleTree    *MarkleTree
}

type Header struct {
    PrevioustBlockHash  []byte  # Hash of previous block
    MarkleRoot          []byte  # Hash of Markle Tree root
    Hash                []byte  # current block hash
    Height              int64   # Block height
    MinerAddr           string  # Miner's address
    TxNumber            int64   # Number of transactions in the block
    Hash                []byte  # current block hash
    Size                int     # Size of the block
    Timestamp           int64   # Created timestamp of the block
    Nonce               int     # Number once
}

The transaction data is stored in Markle Tree.

Transaction structure:

type Transaction struct {
    ID          []byte  # Hash of the TX
    Timestamp   int64   # Created timestamp
    From        []byte  # The address of user or advertiser
    To          []byte  # The address of the address of the charge station owner
    Amount      int64   # The money to pay
    Time        int64   # how many minutes does the user take to charge or watch advertisement
    Type        string  # 'Charge' or 'Advertisement'
}

The blocks are connected one by one as a chain. We use the Hash function to verify block and prevent the data from being tampered. Every transactions can be searched through blockchain and Markle Tree root Hash is used to verify if a TX exists in certain block. In addtion, each transaction contains the detailed information including sender address, receiver address, amount and timestamp. Once the charging and advertisement data is recorded, it cannot be changed. Therefore, the "reward program" data is secure for all parties and cannot be colluded.

The overall structure of blockchain is shown below.

Every charge station has its owner and after finishing charging, users have to scan the QR code and pay money for the owner. From the blockchain view, a transaction is created and recorded. The user sends an amount of money to the charge station owner address through TX. For example, we assume the charging fee is $x$ ( RMB per minute ) and the charging time is $t$ minutes:

Charge Transaction {
    ID: (The hash of TX)
    Timestamp: (timestamp)
    From: (User address)
    To: (Charge station owner address)
    Amount: xt
    Time: t
    Type: 'Charge'
}

If users watch advertisement, users can get 20-minutes free charge for every one-minutes watching. Actually, these charging fees are paid by advertiser. In other words, after a user watches his advertisement, the advertiser'll send awards according the the user's watching time. For instance, we assume that the user watching advertiment for $t$ minutes and charging fee is $x$ ( RMB per minute ), so the transaction is as follows:

Adevertisement Transaction{
    ID: (The hash of TX)
    Timestamp: (timestamp)
    From: (Advertiser address)
    To: (User address)
    Amount: 20xt
    Time: t
    Type: 'Advertisement'
}