5.5. sdzkp.sgd

Classes

class sdzkp.sgd.SubgroupDistanceProblem(generators, m, n, g, min_dist)[source]

A class representing the subgroup distance problem.

m

The number of generators.

Type:: int

n

The size of the symmetric group.

Type:: int

generators_arrayform

The generators in array form.

Type:: dict

K

The minimum Hamming distance.

Type:: int

g

A target permutation.

Type:: list

H

The elementary abelian subgroup.

Type:: ElementaryAbelianSubgroup

round_data

Data for each round.

Type:: dict

Initializes a SubgroupDistanceProblem instance.

Parameters:

generators (dict) – The generators in array form.
m (int) – The number of generators.
n (int) – The size of the symmetric group.
g (list) – The target permutation.
min_dist (int) – The minimum Hamming distance.

classmethod create_from_linearized_generators(linearized_generators, m, n, g, min_dist)[source]

Creates an instance of SubgroupDistanceProblem from linearized generators.

Parameters:

linearized_generators (list) – A list of linearized generators.
m (int) – The number of generators.
n (int) – The size of the symmetric group.
g (list) – The target permutation.
min_dist (int) – The minimum Hamming distance.

Returns:

An initialized instance.

Return type:

SubgroupDistanceProblem

print_generators_arrayform()[source]: Prints the generators in array form.

hamming_distance(p1, p2)[source]

Calculates the Hamming distance between two permutations.

Parameters:

p1 (list) – The first permutation.
p2 (list) – The second permutation.

Returns:

The Hamming distance.

Return type:

int

linearize_generators()[source]

Linearizes the generators for storage or processing.

Returns:: A list of linearized generators.
Return type:: list

class sdzkp.sgd.SubgroupDistanceProblemWithSolution(max2sat_instance)[source]

A subclass of SubgroupDistanceProblem that includes a solution.

p

The number of variables in the max2sat instance.

Type:: int

m

The number of generators.

Type:: int

q_original

The number of clauses in the max2sat instance.

Type:: int

clauses

The max2sat clauses.

Type:: list

K_prime

The maximum number of satisfied clauses in the max2sat instance.

Type:: int

q

The number of extended clauses for the subgroup distance problem.

Type:: int

generators

The generators in binary form.

Type:: dict

generators_arrayform

The generators in array form.

Type:: dict

generators_support

The support of each generator.

Type:: dict

average_support

The average support of all generators.

Type:: int

H

The elementary abelian subgroup.

Type:: ElementaryAbelianSubgroup

h

The solution for the subgroup distance problem.

Type:: list

max2sat_instance_solution

The solution to the max2sat instance.

Type:: list

solution_t_h

The solution in bit array form.

Type:: list

K

The minimum Hamming distance.

Type:: int

num_transpositions_in_generators

The number of transpositions in the generators.

Type:: int

n

The size of the symmetric group.

Type:: int

blinder

A list used to map integers to transpositions.

Type:: list

g

The permutation g in Sn.

Type:: list

H_WithSolution

The elementary abelian subgroup with the solution.

Type:: ElementaryAbelianSubgroupWithSolution

Initializes a SubgroupDistanceProblemWithSolution instance.

Parameters:: max2sat_instance – An instance of the max2sat problem.

setup_sdzkp_round(round_id)[source]

Sets up a round of the Subgroup Distance Zero-Knowledge Proof (SDZKP).

Parameters:: round_id (int) – The ID of the round.
Returns:: The initialized round.
Return type:: SubgroupDistanceRound

convert_max2sat_solution_to_subgroupdistance_solution(solution)[source]

Converts a max2sat solution to a solution for the subgroup distance problem.

Parameters:: solution (list) – The max2sat solution.
Returns:: The corresponding solution for the subgroup distance problem.
Return type:: list

create_x_for_variable_i(i)[source]

Creates the x_i vector for a variable in the subgroup distance problem.

Parameters:: i (int) – The index of the variable.
Returns:: The x_i vector.
Return type:: list

create_y_for_variable_i_clause_j(i, j)[source]

Creates the y_ij vector for a variable and a clause in the subgroup distance problem.

Parameters:

i (int) – The index of the variable.
j (int) – The index of the clause.

Returns:

A tuple containing the y_ij vector for the true and false cases.

Return type:

tuple

create_y_for_variable_i(i)[source]

Creates the y_i vector for a variable in the subgroup distance problem.

Parameters:: i (int) – The index of the variable.
Returns:: A tuple containing the y_i vector for the true and false cases.
Return type:: tuple

reduce_to_sdp_for_variable_i(i)[source]

Reduces the subgroup distance problem for a variable.

Parameters:: i (int) – The index of the variable.
Returns:: A tuple containing the true and false generators.
Return type:: tuple

group_triplets(arr)[source]

Groups an array into triplets and returns them as a string.

Parameters:: arr (list) – The array to group.
Returns:: A string representation of the triplets.
Return type:: str

print_generators()[source]: Prints the generators of the subgroup distance problem.

print_generators_arrayform()[source]: Prints the generators in array form for the subgroup distance problem.

generate_random_3bits(support)[source]

Generates a random 3-bit vector based on the support of a generator.

Parameters:: support (int) – The support of the generator.
Returns:: A 3-bit vector.
Return type:: list

extend_generator(i, tf, random_bits)[source]

Extends a generator with random bits and updates its support.

Parameters:

i (int) – The index of the generator.
tf (str) – Indicates whether the generator is “t” or “f”.
random_bits (list) – The random bits to add.

add_random_3bits_to_solution_generators()[source]: Adds random 3-bit vectors to the solution generators to balance the Hamming distance.

extend_sdp()[source]: Extends the subgroup distance problem by adding random triplets to the solution generators.

reduce_to_sdp_and_extend()[source]: Reduces the max2sat problem to the subgroup distance problem and extends it.

get_bit_i_of_generators(i)[source]

Retrieves the i-th bit of all generators.

Parameters:: i (int) – The bit index.
Returns:: A list of the i-th bits of all generators.
Return type:: list

xor_and_check_combinations(bit_array, value, combinations=None)[source]

Performs XOR on all combinations of the bit array and checks for a match with the value.

Parameters:

bit_array (list) – The array of bits.
value (int) – The value to match.
combinations (list, optional) – A list of combinations to check. Defaults to None.

Returns:

A list of correct combinations.

Return type:

list

test_membership(perm)[source]

Tests if a permutation is a member of the group.

Parameters:: perm (list) – The permutation to test.
Returns:: True if the permutation is a member, False otherwise.
Return type:: bool

convert_generators_to_arrayform_using_blinder()[source]: Converts the binary representation of the generators to array form using a blinder.

convert_binary_permutation_to_arrayform_using_blinder(generator_v)[source]

Converts a binary permutation to array form using a blinder.

Parameters:: generator_v (list) – The binary permutation.
Returns:: The permutation in array form.
Return type:: list

generate_permutation_g_in_Sn()[source]

Generates a permutation g in Sn.

Returns:: The generated permutation.
Return type:: list

generate_random_blinder()[source]

Generates a random blinder for mapping integers to transpositions.

Returns:: The blinder.
Return type:: list

class sdzkp.sgd.SubgroupDistanceRound[source]

A class representing a single round in the SDZKP.

s

A random seed for generating randomness.

Type:: int

t_r

A bit array for random elements.

Type:: list

r

A randomly generated element.

Type:: list

G

A permuted element.

Type:: list

t_u

A bit array for another random element.

Type:: list

U

A second permuted element.

Type:: list

R

A random array of integers.

Type:: list

c

A challenge bit.

Type:: int

C1, C2, C3

Commitments generated during the round.

Type:: list

round_result

The result of the round.

Type:: bool

Initializes a SubgroupDistanceRound instance.

set_seed(s)[source]

Sets the random seed.

Parameters:: s (int) – The seed to set.

hash(data)[source]

Computes the SHA3-512 hash of the given data and encodes it in base64.

Parameters:: data – The data to hash.
Returns:: The base64-encoded hash.
Return type:: bytes

generate_commitment(data)[source]

Generates a cryptographic commitment for the given data.

Parameters:: data – The data to commit to.
Returns:: The commitment (hash).
Return type:: bytes

generate_commitments()[source]: Generates the commitments C1, C2, and C3 based on Z1, Z2, and the seed.

generate_random_array(n)[source]

Generates a random array of integers.

Parameters:: n (int) – The length of the array.

generate_Z1_and_Z2()[source]: Generates Z1 and Z2 as the sum of U and R, and G and R, respectively.