Subtraction in hypergraph space The presented method belongs to the HFHE scheme and is one of its parts that implements a mechanism that supports all types of mathematical operations on encrypted data.
A brief introduction to advanced math operations on hypergraphs
For simplicity, the example uses two vectors of 32 bytes each and the key size is limited to 4 megabytes.
The size of the vectors is chosen for clarity. Optimization is excluded, and checks for the completeness of the data are also excluded, since the size of the vectors can be estimated directly by comparison. The mechanism for transforming data into the “hypergraph space” was described earlier.
If we assume that a single vector with preset settings has been created for the computing base, then the simplest subtraction mechanism can be described as indicated in the code block below.
Copy let hypergraph_subtract hg1 hg2 =
let xor_result = hypergraph_xor hg1 hg2 in
let and_result = hypergraph_and hg1 hg2 in
let not_hg1 = hypergraph_not hg1 in
let part1 = hypergraph_and xor_result (hypergraph_not and_result) in
let part2 = hypergraph_and (hypergraph_not hg1) not_hg1 in
hypergraph_xor part1 part2 This code fragment allows us to see the subtraction method between two cipher vectors. The description of the subtraction method comes down to one simple formula:
Sub ( H G 1 , H G 2 ) = ( H G 1 ⊕ H G 2 ) & ( H G 1 ‾ & H G 2 ‾ ) ⊕ ( ( H G 1 ⊕ H G 2 ) & ( H G 1 & H G 2 ) ‾ ) \begin{align*}
\text{Sub}(H_{G_1}, H_{G_2}) = & (H_{G_1} \oplus H_{G_2}) \& (\overline{H_{G_1}} \& \overline{H_{G_2}}) \\
& \oplus ((H_{G_1} \oplus H_{G_2}) \& \overline{(H_{G_1} \& H_{G_2})})
\end{align*} Sub ( H G 1 , H G 2 ) = ( H G 1 ⊕ H G 2 ) & ( H G 1 & H G 2 ) ⊕ (( H G 1 ⊕ H G 2 ) & ( H G 1 & H G 2 ) ) The transformed hypergraphs are obtained by directly inverting each bit of the ciphertext. The resulting hypergraph is obtained by subtracting two encryption vectors with a predefined base key.
Implementation of the subtraction method is presented as follows:
Copy let hypergraph_and hg1 hg2 =
let row_length = List . length ( List . hd hg1) in
List . mapi ( fun i row1 ->
List . mapi ( fun j a ->
let b = List . nth ( List . nth hg2 i) j in
let a_int = BitSet . to_int a in
let b_int = BitSet . to_int b in
let result_int = (a_int * b_int) mod 256 in
BitSet . of_int result_int
) row1
) hg1
let hypergraph_or hg1 hg2 =
let row_length = List . length ( List . hd hg1) in
List . mapi ( fun i row1 ->
List . mapi ( fun j a ->
let b = List . nth ( List . nth hg2 i) j in
let a_int = BitSet . to_int a in
let b_int = BitSet . to_int b in
let result_int = (a_int + b_int - (a_int * b_int / 256 )) mod 256 in
BitSet . of_int result_int
) row1
) hg1
let hypergraph_xor hg1 hg2 =
let row_length = List . length ( List . hd hg1) in
List . mapi ( fun i row1 ->
List . mapi ( fun j a ->
let b = List . nth ( List . nth hg2 i) j in
let a_int = BitSet . to_int a in
let b_int = BitSet . to_int b in
let result_int = (a_int + b_int - 2 * (a_int * b_int / 256 )) mod 256 in
BitSet . of_int result_int
) row1
) hg1
let hypergraph_not hg =
List . map ( List . map BitSet . not_) hg
let hypergraph_subtract hg1 hg2 =
let xor_result = hypergraph_xor hg1 hg2 in
let and_result = hypergraph_and hg1 hg2 in
let not_hg1 = hypergraph_not hg1 in
let part1 = hypergraph_and xor_result (hypergraph_not and_result) in
let part2 = hypergraph_and (hypergraph_not hg1) not_hg1 in
hypergraph_xor part1 part2 Hypergraph stability assessment
The resulting hypergraph obtained after the transformations retains its stability. It can be empirically confirmed.
To confirm the stability of the resulting hypergraph, it is necessary to construct an adjacency matrix, then calculate the first and second moments and find the final variance. Low variance values indicate a coherent data structure.
Construction of an adjacency matrix:
A Sub ( H G 1 , H G 2 ) = ( A H G 1 ⊕ A H G 2 ) & ( A H G 1 ‾ & A H G 2 ‾ ) ⊕ ( ( A H G 1 ⊕ A H G 2 ) & ( A H G 1 & A H G 2 ) ‾ ) \begin{align*}
A_{\text{Sub}}(H_{G_1}, H_{G_2}) = & (A_{H_{G_1}} \oplus A_{H_{G_2}}) \& (\overline{A_{H_{G_1}}} \& \overline{A_{H_{G_2}}}) \\
& \oplus ((A_{H_{G_1}} \oplus A_{H_{G_2}}) \& \overline{(A_{H_{G_1}} \& A_{H_{G_2})}})
\end{align*}
A Sub ( H G 1 , H G 2 ) = ( A H G 1 ⊕ A H G 2 ) & ( A H G 1 & A H G 2 ) ⊕ (( A H G 1 ⊕ A H G 2 ) & ( A H G 1 & A H G 2 ) ) Determine the Y n Y_n Y n S u b ( H G 1 , H G 2 ) Sub(H_{G_1}, H_{G_2}) S u b ( H G 1 , H G 2 )
Y n = Sub ( H G 1 , H G 2 ) Y_n = \text{} \, \text{Sub}(H_{G_1}, H_{G_2}) Y n = Sub ( H G 1 , H G 2 ) Calculation of the first moment:
E [ Y n ] = ∑ A n ! ( ( n / r ) ! ) r ( r ( r − 1 ) ( r − 2 ) ( r − 3 ) r 4 + 6 r ( r − 1 ) ( r − 2 ) r 3 n + 10 r ( r − 1 ) r 2 n 2 + 1 n 3 ) m E[Y_n] = \sum_{A} \frac{n!}{((n/r)!)^r} \left( \frac{r(r-1)(r-2)(r-3)}{r^4} + \frac{6r(r-1)(r-2)}{r^3 n} + \frac{10r(r-1)}{r^2 n^2} + \frac{1}{n^3} \right)^m E [ Y n ] = A ∑ (( n / r )! ) r n ! ( r 4 r ( r − 1 ) ( r − 2 ) ( r − 3 ) + r 3 n 6 r ( r − 1 ) ( r − 2 ) + r 2 n 2 10 r ( r − 1 ) + n 3 1 ) m Calculation of the second moment:
E [ Y n 2 ] = O r ( ( E [ Y n ] ) 2 n r − 1 / 2 ∑ A 1 ∏ i , j = 1 r a i j + 1 exp ( n ( γ ( A ) − ϕ ( A ) ) ) ) E[Y_n^2] = O_r \left( (E[Y_n])^2 n^{r-1/2} \sum_A \frac{1}{\prod_{i,j=1}^{r} \sqrt{a_{ij} + 1}} \exp\left(n(\gamma(A) - \phi(A))\right) \right)
E [ Y n 2 ] = O r ( ( E [ Y n ] ) 2 n r − 1/2 A ∑ ∏ i , j = 1 r a ij + 1 1 exp ( n ( γ ( A ) − ϕ ( A )) ) ) where:
ϕ ( A ) = ∑ i , j = 1 r a i j n ln ( r 2 a i j ) \phi(A) = \sum_{i,j=1}^{r} \frac{a_{ij}}{n} \ln(r^2 a_{ij}) ϕ ( A ) = i , j = 1 ∑ r n a ij ln ( r 2 a ij ) and:
γ ( A ) = c ln ( [ r 3 ( r − 1 ) ( r − 2 ) ( r − 3 ) ] 2 ∑ { i 1 , i 2 , i 3 , i 4 } = 4 , { j 1 , j 2 , j 3 , j 4 } = 4 a i 1 j 1 a i 2 j 2 a i 3 j 3 a i 4 j 4 n 4 )
\gamma(A) = c \ln \left( \left[ \frac{r^3}{(r-1)(r-2)(r-3)} \right]^2 \sum_{\{i_1, i_2, i_3, i_4\}=4, \{j_1, j_2, j_3, j_4\}=4} \frac{a_{i_1 j_1} a_{i_2 j_2} a_{i_3 j_3} a_{i_4 j_4}}{n^4} \right)
γ ( A ) = c ln [ ( r − 1 ) ( r − 2 ) ( r − 3 ) r 3 ] 2 { i 1 , i 2 , i 3 , i 4 } = 4 , { j 1 , j 2 , j 3 , j 4 } = 4 ∑ n 4 a i 1 j 1 a i 2 j 2 a i 3 j 3 a i 4 j 4 Introducing ϵ i j = a i j n − 1 r 2 \epsilon_{ij} = \frac{a_{ij}}{n} - \frac{1}{r^2} ϵ ij = n a ij − r 2 1 i , j = 1 , … , r i, j = 1, \ldots, r i , j = 1 , … , r
then:
ϕ ( A ) = ϕ ( Υ ) = ∑ i , j = 1 r ( 1 r 2 + ϵ i j ) ln ( 1 + r 2 ϵ i j )
\phi(A) = \phi(\Upsilon) = \sum_{i,j=1}^{r} \left(\frac{1}{r^2} + \epsilon_{ij}\right) \ln(1 + r^2 \epsilon_{ij})
ϕ ( A ) = ϕ ( Υ ) = i , j = 1 ∑ r ( r 2 1 + ϵ ij ) ln ( 1 + r 2 ϵ ij ) from this, it follows that:
γ ( A ) = γ ( Υ ) = c ln ( [ r 3 ( r − 1 ) ( r − 2 ) ( r − 3 ) ] 2 ∑ { i 1 , i 2 , i 3 , i 4 } = 4 , { j 1 , j 2 , j 3 , j 4 } = 4 ( 1 r 2 + ϵ i 1 j 1 )
\gamma(A) = \gamma(\Upsilon) = c \ln \left( \left[ \frac{r^3}{(r-1)(r-2)(r-3)} \right]^2 \sum_{\{i_1, i_2, i_3, i_4\}=4, \{j_1, j_2, j_3, j_4\}=4} \left(\frac{1}{r^2} + \epsilon_{i_1 j_1}\right) \right.
γ ( A ) = γ ( Υ ) = c ln [ ( r − 1 ) ( r − 2 ) ( r − 3 ) r 3 ] 2 { i 1 , i 2 , i 3 , i 4 } = 4 , { j 1 , j 2 , j 3 , j 4 } = 4 ∑ ( r 2 1 + ϵ i 1 j 1 ) ( 1 r 2 + ϵ i 2 j 2 ) ( 1 r 2 + ϵ i 3 j 3 ) ( 1 r 2 + ϵ i 4 j 4 ) )
\left. \left(\frac{1}{r^2} + \epsilon_{i_2 j_2}\right) \left(\frac{1}{r^2} + \epsilon_{i_3 j_3}\right)\left(\frac{1}{r^2} + \epsilon_{i_4 j_4}\right) \right)
( r 2 1 + ϵ i 2 j 2 ) ( r 2 1 + ϵ i 3 j 3 ) ( r 2 1 + ϵ i 4 j 4 ) )
The structure and clustering of the hypergraph after math transformations, adding new ciphertext elements, and the values of various data remains unchanged despite the progressive increase in noise interference for each operation.
A detailed explanation will be provided in a separate article.
Variance Calculation for Y n Y_n Y n
Var ( Y n ) = E [ Y n 2 ] − ( E [ Y n ] ) 2 \text{Var}(Y_n) = E[Y_n^2] - (E[Y_n])^2 Var ( Y n ) = E [ Y n 2 ] − ( E [ Y n ] ) 2 Benchmarks and tests
To illustrate, consider two 32-byte vectors. Add a key and perform homomorphic subtraction on a moderately noisy hypergraph with a predefined noise level:
Copy let vector_1 = [
0 x5 9 ; 0 x7 4 ; 0 x2 0 ; 0 x0 8 ; 0 x5 7 ; 0 x2 1 ; 0 x4d ; 0 x6 9 ;
0 x4d ; 0 x0 4 ; 0 x5 9 ; 0 x1a ; 0 xc2 ; 0 x8 4 ; 0 x3 5 ; 0 xc2 ;
0 xb5 ; 0 x6f ; 0 x2c ; 0 x9a ; 0 x7b ; 0 xff ; 0 xde ; 0 x3a ;
0 x1 7 ; 0 xe5 ; 0 x8b ; 0 x2 1 ; 0 xa4 ; 0 xd0 ; 0 x3e ; 0 x9 0 ;
0 x4 9
] in
let vector_2 = [
0 x3 5 ; 0 x4 4 ; 0 x1 5 ; 0 x0 9 ; 0 x6 7 ; 0 x1 2 ; 0 x3d ; 0 x5 9 ;
0 x3d ; 0 x1 4 ; 0 x4 9 ; 0 x2a ; 0 xb2 ; 0 x9 4 ; 0 x2 5 ; 0 xa2 ;
0 xa5 ; 0 x1b ; 0 x6e ; 0 x8 8 ; 0 x7c ; 0 x4 4 ; 0 x3 1 ; 0 xd2 ;
0 x6a ; 0 x5d ; 0 x8f ; 0 x9 3 ; 0 x7 1 ; 0 x5 8 ; 0 xb7 ; 0 x0e ;
0 x2b
] in Let's define the basis for computation as follows:
Copy let init_set_count mod_val =
let set_count = Array . make mod_val 0 in
for i = 0 to mod_val - 1 do
let mod_val = (i land 1 ) * 2 + (i land 2 ) + (i lsr 2 land 1 ) + (i lsr 3 land 1 ) +
(i lsr 4 land 1 ) + (i lsr 5 land 1 ) + (i lsr 6 land 1 ) + (i lsr 7 land 1 ) + 3 in
set_count . ( i ) <- (mod_val lsl 28 ) lor 6
done ;
set_count
let next_position set_count previous_set =
assert (previous_set >= 0 && previous_set < Array . length set_count) ;
set_count . ( previous_set ) lsr 16
let spectral set_count previous_set bit_cipher limit hyper_base =
let mod_val = set_count . ( previous_set ) land 255 in
let next_pos = set_count . ( previous_set ) lsr 14 in
if mod_val < limit then
let updated_count =
set_count . ( previous_set ) +
(((bit_cipher lsl 18 ) - next_pos) * hyper_base . ( mod_val ) land 0 xffffff0 0 ) in
Array . copy set_count |> fun new_count ->
new_count . ( previous_set ) <- updated_count ;
new_count
else
set_count
let next_position_hyp previous_set current_set sub_graph =
sub_graph |> next_position (previous_set lsl 8 lor current_set . ( previous_set ) )
let spectral_hyp previous_set current_set bit_cipher sub_graph =
sub_graph |> spectral previous_set bit_cipher 90 |> fun new_count ->
let indirect_graph = ref current_set . ( previous_set ) in
indirect_graph := ( ! indirect_graph + ! indirect_graph + bit_cipher) land 255 ;
let new_previous_set = (previous_set + previous_set + bit_cipher) land 255 in
new_count , new_previous_set
let hypergraph_processor () =
let current_set = Array . init 256 ( fun _ -> 0 x6 6 ) in
let sub_graph = init_set_count 0 x1 0000 in
let rec next_position_hyp_rec previous_set =
next_position_hyp previous_set current_set sub_graph |> fun next_pos ->
next_position_hyp_rec next_pos
in
let rec spectral_hyp_rec previous_set =
spectral_hyp previous_set current_set sub_graph |> fun ( new_count , new_previous_set ) ->
spectral_hyp_rec new_previous_set ;
new_count
in
next_position_hyp_rec , spectral_hyp_rec Preparing the key:
Copy let generate_ZRH_key start_vector flag size =
let input = start_vector ^ string_of_bool flag in
let input_bytes = Cs . of_string input in
let rec hash_iteration acc count =
if count = 0 then acc
else
let hash = Hash . SHA512 . hmac ~ key : input_bytes ( Cs . of_string acc) in
hash_iteration ( Cs . to_string ( Hash . SHA512 . digest hash)) (count - 1 )
in
let final_hash = hash_iteration "" 1000 in
let rec extend_key acc current_size =
if current_size >= size then acc
else extend_key (acc ^ final_hash) (current_size + 64 )
in
let extended_key = extend_key "" 0 in
String . sub extended_key 0 size
let key_size = 4 * 1024 * 1024
let ZRH_key = generate_ZRH_key start_vector flag key_size
Subtraction and division (will be provided separately) are the most complex and resource intensive operations.
After passing the vector values and performing subtraction, we obtained the following results:
Copy Encryption of vector 1 took: 0.00136 seconds
After encrypting vector 1 - Memory usage: 93.64 MB
Encryption of vector 2 took: 0.0015375 seconds
After encrypting vector 2 - Memory usage: 91.12 MB
Encrypted result: be bf f6 f7 3e 37 76 bf dc fd 9e bf 4c 6d 0e
df e7 e7 ed ed f7 ff fd e5 21 25 6b 6f b5 b9 ff 23 3b 1e 73 56
bf 92 f7 3a f7 f3 bf bb f3 ff bb f7 fe ff fe ff fe ff fe ff f5
f4 bf be 75 7c 3f f6 e3 e6 eb ee 77 7a 7f e2 f9 fd bb bf ed e9
af fb eb ef e3 e7 ff f3 f7 eb dc fd 96 b7 dc f5 96 df 4b 6e 43
66 df f2 d7 4a d7 f7 dd fd 57 7f 5d d5 f9 fc b3 b6 fd f0 b7 fa
f4 f1 fe fb f0 fd fa f7 ee ef ae af fe ff be ef ae 8f ee cf 3e
Decryption took: 0.00118917 seconds
After decryption - Memory usage: 112.07 MB
Decrypted result: 24 30 0b ffffffff fffffff0 0f 10 10 10 fffffff0 10 fffffff0 10 fffffff0 10 20 10 54 ffffffbe 12 ffffffff bb ad ffffff68 ffffffad 88 fffffffc ffffff8e 33 78 ffffff87 82 1e
Program ended with exit code: 0
The assessment of the resource efficiency of the described mathematical method used in the Octra code remains at the discretion of the readers.
Last updated 5 months ago
