POD-Mini and POD-AS

I Intro

%load_ext autoreload
%autoreload 2

This is a Python implementaton of Pod-Mini of zkPod via klefki, for more details, just check the technial Paper.

from klefki.types.algebra.concrete import (
    EllipticCurveGroupSecp256k1 as ECG,
    EllipticCurveCyclicSubgroupSecp256k1 as CG,
    FiniteFieldSecp256k1 as F,
    FiniteFieldCyclicSecp256k1 as CF
)

from operator import add
G = CG.G

import random

N = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
random_f = lambda: CF(random.randint(1, N) % CF.P)

q = random_f()
H = G @ q

from hashlib import sha256

hash = lambda x, y: CF(int(sha256(str(x.value + y).encode()).hexdigest(), 16) % N)
hash2 = lambda x, y, z: CF(int(sha256(str(x.value + y + z).encode()).hexdigest(), 16) % N)

II POD-Mini

Initializer Phase

data = 123456789
tag = 6

m = CF(data)
o = CF(tag)

sigma = G @ m + H @ o

Deliver Phase

k_w = random_f()

k = hash(k_w, 1)
k_ = hash(k_w, 2)
k0 = hash(k_w, 3)
k0_ = hash(k_w, 4)

K = G @ k + H @ k_
K0 = G @ k0 + H @ k0_
(K, K0)

(EllipticCurveGroupSecp256k1::(FiniteFieldSecp256k1::60833088545442599426394672598201640952972051730298604958359191447690851122096, FiniteFieldSecp256k1::48051097886287326595482477027746542056422212554885787335326880757550380565553),
 EllipticCurveGroupSecp256k1::(FiniteFieldSecp256k1::109757020878345036275695788298328814894135468587935766610813179219963914817284, FiniteFieldSecp256k1::3503186752654184182707842700539194665709151565486434874163610016019483430925))

• \(S \rightarrow R\): \((K, K_0)\)

c = random_f()

• \(R \rightarrow S\): \(c\)

m_ = k + c * m
o_ = k_ + c * o
z = k0 + c * k
z_ = k0_ + c * k_
(m_, o_, z, z_)

(FiniteFieldCyclicSecp256k1::4188847662850428514190277999937279562610735694457763843035367735100439750049,
 FiniteFieldCyclicSecp256k1::113829453438446661247390864254644542435892738603979657221855887955677525600276,
 FiniteFieldCyclicSecp256k1::108203930121791436016800137198409918309056563447049654576428359618878344960306,
 FiniteFieldCyclicSecp256k1::83764309071589516840408152095024667788508464591543119082668639417611269829753)

• \(S \rightarrow R: (\bar{m}, \bar{o}, z, z')\)

R should verify that:

\[\begin{split}Com(m; o)^c \cdot Com(k_0;k'_0) \stackrel{?}{=} Com(\bar{m}; \bar{o})\\ Com(k_0;k'_0) \cdot Com(k;k')^c \stackrel{?}{=} Com(z;z')\end{split}\]

assert sigma @ c + K == G @ m_ + H @ o_

assert K0 + (K @ c) == G @ z + H @ z_

Reveal-phase

• \(R \rightarrow J: \rho\)

• \(S \rightarrow J: k_{\omega}\)

\[z \stackrel{?}{=} H(k_{\omega}, 3) + c \cdot H(k_{\omega}, 1)\]

assert z == hash(k_w, 3) + c @ hash(k_w, 1)

assert m == (m_ - hash(k_w, 1)) / c

(m_ - hash(k_w, 1)) / c

FiniteFieldCyclicSecp256k1::123456789

POD-AS

from IPython.display import Image

f = Image("lena-mini.jpg")

Init Phase

In the init-phase, the data file is splitted into a block matrix of \(n × s\) . Each row of the matrix is called a \(block\), which consists of \(s\) slices. The initializer adds one additional column of random slices \(m_{0i}\) to the matrix for padding. The slices of \(m_{0i}\) are used for blind factors as o in PoD-Mini.

import numpy as np

Image(f.data)

M = np.array(list(map(CF, f.data))).reshape(-1, 5)

M.shape

(205, 5)

w, h = M.shape

Pad = np.matrix([random_f() for _ in range(0, h)])

Pm = np.concatenate((Pad.T, M.T), axis=1).T.tolist()

n, s = np.matrix(Pm).shape

np.matrix(Pm).shape

(206, 5)

\[\begin{split}u_j \stackrel{$}{\leftarrow} \mathbb{G}, j \in [0, s] \\ m_{i0} \stackrel{$}{\leftarrow}\mathbb{G}, i \in [1, n]\\ \sigma_i = \prod_{j=0}^s u_j^{m_{ij}}, i\in[1,n]\end{split}\]

The initializer needs to generate \(s + 1\) group elements randomly.

U = [G @ random_f() for _ in range(0, s)]

from functools import reduce

def v_multi(g: [ECG], a: [CF]) -> [ECG]:
    return reduce(lambda x,y: x+y,
                  list(map(lambda a: a[0] @ a[1], zip(g, a))))

\[\sigma_i = Com(m_{i1}, ...,m_{i,s};m_{i0}) = u_0^{m_{i0}} \cdot \prod_{j=1}^s u_j^{m_{ij}}\]

sigma = [v_multi(U, Pm[i]) for i in range(0, n)]

Deliver Phase

\[\begin{split}k_{\omega} \stackrel{$}{\leftarrow} \mathbb{Z}_p \\\end{split}\]

kw = random_f()

\[k_{i,j} \leftarrow H(k_{\omega}, i,j)\]

k = [[hash2(kw, i, j) for j in range(0, s+1)] for i in range(0, n+1)]

assert np.matrix(k).shape == (n + 1, s + 1)

The topmost row \(k_{0j}\) is for hiding keys in the same column, the leftmost \(k_{i0}\) is for encrypting padding slices.

Then \(S\) constructs commitments \(K\) i to \(i\)-th row of keys, including the leftmost key \(k_{i0}\) on each row.

\[K_i = \prod_{j=0}^s u_j^{k_{ij}}; i\in[0,n]\]

K = [reduce(add, [U[j]@k[i][j] for j in range(0, s)]) for i in range(0, n)]

\(S \rightarrow R: \mathbf{K}_[0, n]\)

\(R \rightarrow S: c\)

c = random_f()

\[\begin{split}\bar{m}_{ij}=k_{ij}+m_{ij}\cdot c^i; i\in[1,n], j\in[0,s] \\\end{split}\]

M_ = [[k[i][j] + Pm[i][j]*(c**i) for j in range(0, s)] for i in range(1, n)]

np.matrix(M_).shape == (n - 1, s)

True

\[z_j=\sum_{i=0}^n k_{ij}\cdot c^i; j \in[0,s]\]

z = [reduce(add, [k[i][j] * c**i for i in range(0, n)]) for j in range(0, s)]

\(S \rightarrow R: \bar{m}_{[1,n][0,s]}, z_{[0,s]}\)

\[\prod_{i=1}^n (\sigma_i^{c^i} \cdot K_i) \stackrel{?}{=} \prod_{i=1}^n \left(\prod_{j=0}^s u_j^{\bar{m}_{ij}} \right)\]

assert reduce(add, [sigma[i] @ CF(c ** i) + K[i] for i in range(1, n)]) == \
        reduce(add, [v_multi(U, M_[i]) for i in range(0, n - 1)])

\[\prod_{i=0}^n K_i^{(c^i)} \stackrel{?}{=} \prod_{i=0}^su_j^{zj}\]

assert reduce(add, [K[i] @ CF(c ** i) for i in range(0, n)]) == \
    reduce(add, [U[j] @ z[j] for j in range (0, s)])

If \(R\) accepts the keys and data, he has to submit a delivery receipt to \(J\) \((\mathbf{z},c)\), where \(\mathbf{z}\) is the aggregation of \(z_{[0,s]}\) :

\[\mathbf{z}=\sum_{i=0}^s z_j\]

\(R \rightarrow J: \rho(\mathbf{z}, c)\)

Z = reduce(add, z)

\[\rho \stackrel{?}{=} (\prod_{j=0}^s z_j, c)\]

assert (Z, c) == (reduce(add, z), c)

\(f \rightarrow R: k_{\omega}\)

\[\begin{split}k_{ij} \leftarrow H(k_{\omega}, i, j); i\in[0,n],j\in[1,s]\\\end{split}\]

\[\begin{split}\bar{m}_{ij}=k_{ij}+m_{ij}\cdot c^i; i\in[1,n], j\in[0,s] \\\end{split}\]

\[\begin{split}m_{ij} = \frac{\bar{m}_{ij} - k_{ij}}{c^i} ; i\in[0,n],j\in[1,s]\\\end{split}\]

Data = [[(M_[i][j] - k[i+1][j])/(c**(i+1)) for j in range(0, s)] for i in range(0, n-1)]

assert Data == Pm[1:]

Image(reduce(add, (map(lambda x: bytes([x.value]), reduce(add, Data)))))