How version 0.7.6‐beta works in detail

This document provides an exhaustive explanation of the feldman_vss.py script, a Python implementation of Feldman's Verifiable Secret Sharing (VSS) scheme, designed with a strong emphasis on post-quantum security, efficiency, and robustness. We will dissect the code, explore the underlying cryptographic principles, and discuss the rationale behind design decisions.

I. Introduction and Design Philosophy

The feldman_vss.py script is more than just a straightforward implementation of Feldman's original VSS scheme. It represents a significant evolution, incorporating modern cryptographic best practices and addressing the looming threat of quantum computers. The core design goals are:

1. Uncompromising Post-Quantum Security: The script entirely avoids reliance on the discrete logarithm problem, which is known to be vulnerable to Shor's algorithm on a sufficiently powerful quantum computer. Instead, it exclusively employs hash-based commitments, using either BLAKE3 (preferred) or SHA3-256. This choice ensures that the scheme remains secure even in the face of quantum adversaries.

2. Provable Security: The design adheres to rigorous security principles, drawing upon established cryptographic protocols and techniques. The use of zero-knowledge proofs, secure serialization with checksums, and countermeasures against various attacks (timing, fault injection, Byzantine behavior) all contribute to a provably secure implementation (within the limitations of the Python environment).

3. Efficiency and Performance: While security is paramount, the script is also designed for practical use. It incorporates several optimizations to enhance performance:

   • Batch Verification: The batch_verify_shares function provides a highly optimized way to verify multiple shares against the same set of commitments, drastically reducing the computational overhead when dealing with many participants.
   • Precomputation: The CyclicGroup class precomputes powers of the generator, significantly speeding up exponentiation operations, which are frequent in VSS.
   • LRU Caching: A thread-safe Least Recently Used (LRU) cache (SafeLRUCache) is used to store the results of exponentiations, avoiding redundant calculations.
   • Optimized Multi-exponentiation: The efficient_multi_exp function provides an efficient algorithm for computing the product of multiple exponentiations, a common operation in verification steps.
   • msgpack Serialization: The use of msgpack provides a compact and efficient binary serialization format, minimizing the size of serialized data and the time required for serialization/deserialization.

4. Robustness and Fault Tolerance: The script is designed to be robust against a variety of attacks and errors:

   • Input Validation: Extensive input validation is performed throughout the code to prevent misuse and ensure that functions receive data of the expected type and format.
   • Error Handling: Detailed error handling is implemented, with custom exception classes (SecurityError, ParameterError, VerificationError, SerializationError) to categorize different types of errors. Error messages are sanitizable (controlled by the sanitize_errors flag in VSSConfig) to prevent leaking sensitive information in production environments.
   • Fault Injection Countermeasures: The secure_redundant_execution function attempts to mitigate fault injection attacks by executing critical computations multiple times and comparing the results. However, it's important to note that this is not a foolproof defense in pure Python (as discussed in the "Known Vulnerabilities" section).
   • Byzantine Fault Tolerance: The refresh_shares function implements a sophisticated protocol (an enhanced version of Chen & Lindell's Protocol 5) to securely refresh shares, even in the presence of Byzantine (malicious) participants. This includes mechanisms for detecting and excluding Byzantine parties, and ensuring consistency through echo-broadcast and verification proofs.

5. Flexibility and Configurability: The VSSConfig class allows customization of various parameters, including:

   • prime_bits: The number of bits in the prime modulus. The default is 4096, providing a high level of post-quantum security.
   • safe_prime: Whether to use a safe prime (where (p-1)/2 is also prime). The default is True, enhancing security.
   • secure_serialization: Whether to use a secure serialization format with checksums.
   • use_blake3: Whether to use the BLAKE3 hash function (if available). BLAKE3 is generally faster and considered more secure than SHA3-256.
   • cache_size: The size of the LRU cache for exponentiation results.
   • sanitize_errors: Whether to sanitize error messages to prevent leaking sensitive information. This should be set to True in production environments but can be set to False for debugging.

6. Integration and Extensibility:

   • Shamir Secret Sharing Compatibility: The script is designed to work seamlessly with a Shamir Secret Sharing implementation (presumably in a separate module). The create_vss_from_shamir function provides a convenient way to create a FeldmanVSS instance that is compatible with an existing Shamir instance.
   • Pedersen VSS Integration: The script includes helper functions (integrate_with_pedersen, create_dual_commitment_proof, verify_dual_commitments) to combine Feldman VSS with Pedersen VSS. This provides both the binding property of Feldman VSS (the dealer cannot change the secret after commitments are made) and the hiding property of Pedersen VSS (the commitments reveal nothing about the secret).

II. Detailed Class and Function Explanations

Let's now examine each class and function in detail, explaining their purpose, implementation, and security considerations.

A. SecurityWarning, SecurityError, ParameterError, VerificationError, SerializationError

These are custom exception and warning classes used for error handling and to signal potentially insecure configurations. They provide a structured way to categorize different types of issues that might arise.

B. VSSConfig (Dataclass)

• Purpose: Holds configuration parameters for the VSS scheme.

• Fields:

  • prime_bits: The size (in bits) of the prime modulus. A larger prime provides greater security, especially against quantum attacks. The default of 4096 bits is recommended for post-quantum security.
  • safe_prime: A boolean flag indicating whether to use a safe prime. Safe primes (where (p-1)/2 is also prime) make certain attacks more difficult. The default is True.
  • secure_serialization: Whether to use secure serialization (with checksum).
  • use_blake3: A boolean flag indicating whether to use the BLAKE3 hash function. If True (the default) and the blake3 library is available, BLAKE3 will be used; otherwise, SHA3-256 will be used.
  • cache_size: The maximum number of items to store in the LRU cache used for exponentiation results. A larger cache can improve performance but consumes more memory.
  • sanitize_errors: A boolean flag. If true, detailed error messages are replaced with generic ones to prevent leaking sensitive information that could be useful to an attacker.

• __post_init__: This method is automatically called after the object is initialized. It enforces a minimum prime_bits value of MIN_PRIME_BITS (4096) for post-quantum security, issuing a SecurityWarning if a smaller value is provided. It also checks if BLAKE3 was requested but is not available, issuing a warning.

C. SafeLRUCache

• Purpose: Implements a thread-safe Least Recently Used (LRU) cache. This is used to store the results of expensive exponentiation operations, avoiding redundant calculations.

• Fields:

  • capacity: The maximum number of items the cache can hold.
  • cache: An OrderedDict that stores the cached items. The order of items reflects their recency of use (most recently used items are at the end).
  • lock: A threading.RLock that protects the cache from concurrent access by multiple threads. An RLock (reentrant lock) allows a thread to acquire the lock multiple times without deadlocking.

• Methods:

  • get(key): Retrieves an item from the cache. If the item is found, it's moved to the end of the OrderedDict (making it the most recently used). Returns the value associated with the key, or None if the key is not found. The entire operation is protected by the lock.
  • put(key, value): Adds an item to the cache. If the key already exists, its value is updated, and it's moved to the end of the OrderedDict. If the cache is full (reached its capacity), the least recently used item (the first item in the OrderedDict) is removed. The entire operation is protected by the lock.
  • clear(): Clears all items from the cache. Protected by the lock.
  • __len__(): Returns the number of items in the cache. Protected by the lock.

D. CyclicGroup

• Purpose: Represents the cyclic group used for the cryptographic operations in the VSS scheme. This class exclusively uses gmpy2 for all arithmetic operations to ensure efficiency and (hopefully) constant-time behavior where needed.

• Fields:

  • prime: The prime modulus of the group (a gmpy2.mpz integer).
  • generator: A generator of the group (a gmpy2.mpz integer).
  • cached_powers: A SafeLRUCache instance used to store the results of exponentiation operations.
  • _precompute_exponent_length: Stores bit length of the prime.
  • _precompute_window_size: Optimal window size for precomputation.
  • _precomputed_powers: A dictionary that stores precomputed powers of the generator, used to speed up exponentiation.

• __init__:

  • Takes optional prime, generator, prime_bits, use_safe_prime, and cache_size arguments.
  • If prime is not provided, it either selects a precomputed safe prime from the SAFE_PRIMES dictionary (if available and use_safe_prime is True) or generates a new prime (either a safe prime or a regular prime, depending on use_safe_prime). Generating safe primes can be very slow, so using precomputed values is highly recommended for production use.
  • If generator is not provided, it calls _find_generator to find a generator.
  • Initializes the cached_powers LRU cache.
  • Calls _precompute_powers to precompute powers of the generator.

• Static Methods (Utility Functions):

  • _is_probable_prime(n, k=40): Performs the Miller-Rabin primality test to check if n is likely prime. k is the number of iterations (higher k increases the confidence in the result). This is a probabilistic test; there's a tiny chance a composite number could pass, but the probability is extremely low for a reasonable k value.

  • _is_safe_prime(p): Checks if p is a safe prime (i.e., if (p-1)/2 is also prime).

• Instance Methods:

  • _generate_prime(bits): Generates a random prime number with the specified number of bits. It repeatedly generates random odd numbers and tests them for primality using _is_probable_prime.

  • _generate_safe_prime(bits): Generates a safe prime with the specified number of bits. This is much slower than generating a regular prime. It generates a candidate q (of bits - 1 size) and checks if p = 2q + 1 is prime.

  • _is_generator(g): Checks if g is a generator of the group. For a safe prime p = 2q + 1, it checks if g^q != 1 mod p. This ensures g has a high order.

  • _find_generator(): Attempts to find a generator for the group. For safe primes it tries squaring random values (this often results in a generator for the q-order subgroup). As a backup, it checks some standard candidate values (2, 3, 5, 7, etc.).

  • _precompute_powers(): Precomputes powers of the generator using a multi-level windowing technique. This significantly speeds up exponentiation when the base is the generator. The window sizes are chosen adaptively based on the prime's bit length. The precomputed values are stored in the _precomputed_powers dictionary.

  • exp(base, exponent): Performs exponentiation (base^exponent mod prime) with optimizations.

    • If the base is the generator and precomputed powers are available, it uses the highly optimized _exp_with_precomputation method.
    • Otherwise, it checks the cached_powers LRU cache. If the result is found in the cache, it's returned directly.
    • If not found in the cache, it uses gmpy2.powmod for efficient modular exponentiation and stores the result in the cache.

  • _exp_with_precomputation(exponent): Performs exponentiation using the precomputed powers of the generator. It uses a multi-level windowing technique to efficiently calculate the result.

  • mul(a, b): Performs modular multiplication: (a * b) mod prime.

  • secure_random_element(): Generates a cryptographically secure random element in the group (between 1 and prime - 1). It uses the secrets module for secure randomness.

  • clear_cache(): Clears the cached_powers LRU cache.

  • hash_to_group(data): Hashes arbitrary data (bytes) to a group element uniformly. This is a crucial function for the security of the hash-based commitments. It uses a rejection sampling technique with the following key features:

    • Domain Separation: Uses a domain separation prefix (f"HTCG_PQS_v{VSS_VERSION}_r{attempt_round}_") to prevent collisions with other uses of the hash function.
    • Multiple Rounds: Makes multiple attempts (with different prefixes) to generate a valid group element.
    • Extra Security Bytes: Uses extra security bytes in the hash input to minimize any bias.
    • Strict Rejection Sampling: Only accepts values that fall within the valid range (1 to prime - 1). It does not fall back to biased modular reduction, which would weaken security.
    • BLAKE3 or SHA3-256: Uses the blake3 library if available; otherwise, it falls back to hashlib.sha3_256.
    • Raises SecurityError: If it fails to generate a uniformly distributed value after a large number of attempts, it raises a SecurityError. This is an extremely unlikely event but indicates a potential problem.

  • _enhanced_encode_for_hash(*args, context="FeldmanVSS"): This is a critical function for security. It provides a robust and deterministic way to encode multiple values of different data types (integers, strings, bytes) into a single byte string suitable for hashing. It uses both type tagging and length-prefixing to prevent collision attacks. The encoding includes:

    • Protocol Version: The VSS_VERSION is included to prevent cross-protocol attacks.
    • Context String: A context string (defaulting to "FeldmanVSS") provides domain separation, ensuring that the same inputs used in different contexts will produce different hash outputs.
    • Type Tags: Each value is preceded by a type tag (e.g., \x00 for bytes, \x01 for strings, \x02 for integers/mpz).
    • Length Prefixing: Each value is preceded by its length (as a 4-byte integer).
    • Integer Encoding: Integers are encoded as fixed-length byte strings using the bit length of the prime. This ensures that the same integer will always produce the same byte representation, regardless of the platform or Python version.

  • efficient_multi_exp(bases, exponents): Efficiently computes the product of multiple exponentiations: Π(bases[i]^exponents[i]) mod prime. This is used in verification steps. It uses a simultaneous multi-exponentiation algorithm with windowing and precomputation (when beneficial) to optimize the calculation.

  • secure_exp(base, exponent): Performs exponentiation (base^exponent mod prime) in a way that is intended to be constant-time with respect to the exponent. This is crucial for security when the exponent is a secret value (e.g., a secret key or a randomizer). It uses gmpy2.powmod, which is believed to implement constant-time modular exponentiation. However, it's important to note that true constant-time execution is difficult to guarantee in Python, and this function might still be vulnerable to subtle timing attacks.

E. constant_time_compare(a, b)

• Purpose: Compares two values (a and b) in a way that is intended to be constant-time, preventing timing attacks. Timing attacks can leak information about the values being compared based on how long the comparison takes.
• Implementation:
  • Converts the inputs to bytes for consistent handling. Integers are converted to fixed-length byte strings, strings are encoded as UTF-8, and bytes are used directly.
  • Handles different lengths by padding the shorter value with null bytes.
  • Performs a bitwise XOR operation on the bytes and accumulates the result. The result will be 0 only if all bytes are equal.
  • Returns True if the result is 0, False otherwise.
• Security Note: The docstring explicitly states that this function does not provide true constant-time guarantees in Python due to Python's execution model. This is a significant vulnerability.

F. compute_checksum(data: bytes) -> int

• Purpose: Calculates a checksum of the input data (bytes) using xxhash3_128 with a cryptographic fallback if xxhash isn't available.
• Implementation:
  • Uses blake3.blake3 if available.
  • Otherwise, uses hashlib.sha3_256.
  • Takes the first 16 bytes of the digest and converts them to an integer.
• Security: This provides a checksum for integrity checks, ensuring that serialized data hasn't been tampered with.

G. secure_redundant_execution(func: Callable, *args, sanitize_error_func=None, function_name=None, context=None, **kwargs) -> Any

• Purpose: Attempts to mitigate fault injection attacks by executing a given function (func) multiple times and comparing the results. Fault injection attacks try to induce errors in computations to leak information.
• Implementation:
  • Executes the function func a fixed number of times (currently 5).
  • Randomly shuffles the order of execution.
  • Introduces small random delays between executions.
  • Compares the results of each execution using constant_time_compare.
  • If any results differ, it raises a SecurityError.
  • If any execution fails with an exception, it logs the failure and raises a SecurityError.
  • Returns one of the results (deterministically selected to avoid timing side-channels).
  • Uses the sanitize_error_func (if provided) to sanitize error messages.
• Security Note: The docstring explicitly states that this function does not provide a perfect defense against fault injection attacks in Python due to limitations in Python's execution environment. This is another significant vulnerability.

H. FeldmanVSS

• Purpose: This is the main class that implements the Feldman Verifiable Secret Sharing scheme.

• Fields:

  • field: The finite field used for polynomial arithmetic (must have a prime attribute).
  • config: A VSSConfig instance holding configuration parameters.
  • group: A CyclicGroup instance used for the underlying cryptographic operations.
  • generator: The generator of the cyclic group (stored for convenience).
  • _commitment_cache: A cache (currently unused but likely intended for future optimizations).
  • hash_algorithm: The hash function to be used (either blake3.blake3 or hashlib.sha3_256).
  • _byzantine_evidence: Stores the byzantine evidence.

• __init__:

  • Takes a field, an optional config, and an optional group as arguments.
  • If group is not provided, it creates a new CyclicGroup instance using the parameters from config.
  • Initializes the hash_algorithm based on config.use_blake3 and the availability of the blake3 library.

• Methods:

  • _sanitize_error(self, message, detailed_message=None): Sanitizes error messages based on the sanitize_errors setting in the VSSConfig. If sanitization is enabled, it returns a generic error message; otherwise, it returns the original message. Also logs the detailed message, if provided.

  • _raise_sanitized_error(self, error_class, message, detailed_message=None): Raises an error of the specified error_class with a sanitized message.

  • _compute_hash_commitment_single(self, value, randomizer, index, context=None, extra_entropy=None): Computes a single hash-based commitment. This is the core commitment calculation, and it's called by _compute_hash_commitment. It performs the following steps:

    • Input Validation: Checks types and ensures the index is non-negative.
    • Deterministic Encoding: Uses self.group._enhanced_encode_for_hash to deterministically encode the value, randomizer, index, context, and extra_entropy (if provided) into a byte string. This encoding is crucial for security, preventing collisions and ensuring consistency.
    • Hashing: Hashes the encoded byte string using the chosen hash algorithm (blake3 or SHA3-256).
    • Modular Reduction: Reduces the hash output modulo the group's prime.

  • _compute_hash_commitment(self, value, randomizer, index, context=None, extra_entropy=None): Computes a hash-based commitment with redundant execution for fault resistance. It calls _compute_hash_commitment_single multiple times (using secure_redundant_execution) and checks that the results match.

  • _compute_combined_randomizer(self, randomizers, x): Calculates the combined randomizer used when verifying a share. This is the sum of the randomizers, each multiplied by the corresponding power of x.

  • _compute_expected_commitment(self, commitments, x): Calculates the expected commitment value for a given x coordinate. This is the sum of the commitments, each multiplied by the corresponding power of x.

  • _verify_hash_based_commitment(self, value, combined_randomizer, x, expected_commitment, context=None, extra_entropy=None): Verifies a hash-based commitment. It computes the commitment for the given value and combined_randomizer and compares it to the expected_commitment using constant_time_compare.

  • create_commitments(self, coefficients): Creates hash-based commitments to the coefficients of the secret-sharing polynomial. This is the main function used during the sharing phase.

    • Calls create_enhanced_commitments.

  • create_enhanced_commitments(self, coefficients, context=None): Creates enhanced hash-based commitments, handling low-entropy secrets using Baghery's method.

    • Entropy Check: Checks if the secret (the first coefficient) might have low entropy (less than 256 bits).
    • Extra Entropy: If the secret might have low entropy, it generates 32 bytes of extra entropy using secrets.token_bytes.
    • Commitment Calculation: For each coefficient, it generates a secure randomizer (r_i) and computes the commitment using _compute_hash_commitment. The extra_entropy is included in the commitment calculation for the secret coefficient.
    • Returns: A list of (commitment, randomizer, extra_entropy) tuples.

  • _verify_share_hash_based_single(self, x, y, commitments): Performs a single verification of a share against hash-based commitments (without redundant execution). This is called by verify_share.

  • verify_share(self, share_x, share_y, commitments): Verifies a share (share_x, share_y) against the provided commitments. This is the main function used during the verification phase. It calls _verify_share_hash_based_single multiple times (using secure_redundant_execution) for fault resistance.

  • batch_verify_shares(self, shares, commitments): Efficiently verifies multiple shares against the same set of commitments. This is a key optimization for performance.

    • Small Batches: For small batches (less than 5 shares), it calls verify_share for each share.
    • Large Batches: For larger batches, it uses an optimized approach:
      • Precomputation: Precomputes powers of x for each share to avoid redundant calculations.
      • Batch Processing: Processes shares in batches (size determined adaptively) to further improve efficiency.
      • Constant-Time Logic: Uses constant-time boolean operations (&=) to combine verification results, preventing timing attacks that could leak information about which shares are invalid.

  • serialize_commitments(self, commitments): Serializes the commitments into a string for storage or transmission.

    • Data Structure: Creates a dictionary containing the VSS version, timestamp, generator, prime, commitments, and a flag indicating that the commitments are hash-based. The commitment values, randomizers and extra entropy (if present) are converted to integers.
    • msgpack Serialization: Uses msgpack.packb to serialize the dictionary into a compact binary format.
    • Checksum: Computes a checksum of the packed data using compute_checksum.
    • Wrapper: Creates a wrapper dictionary containing the packed data and the checksum.
    • Base64 Encoding: Packs the wrapper using msgpack.packb and then encodes the result using URL-safe base64 (urlsafe_b64encode). This produces a string that can be safely stored or transmitted.

  • deserialize_commitments(self, data): Deserializes commitments from a string (created by serialize_commitments).

    • Base64 Decoding: Decodes the input string using URL-safe base64 decoding (urlsafe_b64decode).
    • msgpack Deserialization: Uses msgpack.unpackb to unpack the wrapper (containing the data and checksum).
    • Checksum Verification: Verifies the checksum using compute_checksum and constant_time_compare. If the checksum does not match, it raises a SecurityError.
    • Data Extraction: Extracts the VSS version, timestamp, generator, prime, commitments, and the hash_based flag.
    • Validation: Performs several validation checks:
      • Checks that the VSS version is supported.
      • Checks that the deserialized data has the expected structure (e.g., that commitments is a tuple, that generator and prime are integers).
      • Checks that the prime is actually prime (using CyclicGroup._is_probable_prime) and, if safe_prime is enabled in the config, that it's a safe prime.
      • Checks that the generator is in the valid range (1 to prime - 1).
      • Validates that all commitment values and randomizers are within the valid range (0 to prime - 1).
      • Enforces that the commitments are hash-based (for post-quantum security).
    • Reconstruction: Reconstructs the (commitment, randomizer, extra_entropy) tuples from the deserialized data.
    • Returns: The reconstructed commitments, generator, prime, timestamp, and the hash_based flag.

  • verify_share_from_serialized(self, share_x, share_y, serialized_commitments): Verifies a share against serialized commitments. It deserializes the commitments and then calls verify_share.

  • clear_cache(): Clears the internal caches (_commitment_cache and the group's cached_powers).

  • __del__: Destructor that clears caches and attempts to securely wipe sensitive data.

  • refresh_shares(self, shares, threshold, total_shares, original_commitments=None, participant_ids=None): Refreshes the shares while preserving the same secret. This is a crucial function for maintaining security over time, as it allows participants to generate new shares without revealing the secret or requiring the original dealer. This method implements an enhanced version of Chen & Lindell's Protocol 5 for additive secret sharing.

    • Input Validation: Performs extensive input validation to ensure the parameters are of the correct type and have valid values.
    • Default Participant IDs: If participant_ids are not provided, it generates default IDs (1 to total_shares).
    • Additive Resharing: Calls _refresh_shares_additive to perform the actual share refreshing.

  • _refresh_shares_additive(self, shares, threshold, total_shares, participant_ids): Implements the core logic for additive share refreshing, with enhanced security and efficiency. This is a complex, multi-step protocol designed to be resistant to Byzantine faults.

    1. Zero-Sharing Generation:

       • Each participant creates a sharing of zero. This means generating a random polynomial with a constant term of 0.
       • Deterministic seeds are derived from a master seed and the participant's ID. This allows for verification without requiring participants to exchange their polynomials directly.
       • random.Random() is used with the cryptographically strong derived seed. This is intentional and secure; the security comes from the seed, not the PRNG itself. This allows for deterministic but unpredictable generation of the zero-sharing polynomial.
       • Commitments to the coefficients of the zero-sharing polynomial are created using create_commitments.
       • The zero commitment (the commitment to the constant term, which is 0) is explicitly verified.

    2. Enhanced Verification (Byzantine Fault Tolerance):

       • Echo Broadcast: An echo-broadcast mechanism is used for consistency verification. Participants exchange information about the shares and commitments they received, allowing them to detect if a party is sending inconsistent information (equivocation).
       • Byzantine Detection: The _detect_byzantine_behavior function is used to identify parties that are behaving maliciously (sending inconsistent shares, invalid commitments, etc.).
       • Adaptive Quorum: An adaptive quorum-based system is used to determine how many verified shares are required. This adapts to the threat level (the number of detected invalid shares).
       • Batch Verification: Shares are verified in batches (using batch_verify_shares) for efficiency.
       • Invalidity Evidence: If an invalid share is detected, cryptographic evidence is generated (using _generate_invalidity_evidence).
       • Collusion Detection: The _enhanced_collusion_detection function attempts to identify potential collusion among parties that provided invalid shares.

    3. New Share Calculation:

       • Each participant adds the verified zero-shares they received to their original share (modulo the field prime). This results in a new share of the same secret.
       • The summation of shares is done using _secure_sum_shares for constant-time summation.

    4. New Commitment Calculation:

       • The new polynomial coefficients are reconstructed from a subset of the new shares using optimized interpolation (_reconstruct_polynomial_coefficients).
       • New commitments are created for these coefficients.

    5. Verification Data:

       • Detailed verification data is returned, including information about the number of shares, the threshold, the number of verified and invalid shares, detected Byzantine parties, and a summary of the security parameters used.

  • _secure_sum_shares(self, shares_dict, modulus): Sums shares in a constant-time fashion.

  • _get_original_share_value(self, participant_id, shares): Safely retrieves an original share, handling potential missing or malformed data.

  • _determine_security_threshold(self, base_threshold, verified_count, total_parties, invalid_parties): Calculates an adaptive security threshold, increasing the required number of verified shares based on detected threats.

  • _detect_collusion_patterns(self, invalid_shares_detected, party_ids): Detects potential collusion patterns among parties that provided invalid shares.

  • _create_invalidity_proof(self, party_id, participant_id, share, commitments): Creates a cryptographic proof that a share is invalid.

  • _generate_refresh_consistency_proof(self, participant_id, original_y, sum_zero_shares, new_y, verified_shares): Generates a proof that the share refreshing was done correctly.

  • _process_echo_consistency(self, zero_commitments, zero_sharings, participant_ids): Implements the echo-consistency protocol to detect equivocation (a party sending different values to different participants). This uses cryptographic fingerprints of the shares to ensure secure comparisons.

  • _calculate_optimal_batch_size(self, num_participants, num_shares): Determines an optimal batch size for verification, balancing efficiency and the ability to quickly identify problematic shares.

  • _prepare_verification_batches(self, zero_sharings, zero_commitments, participant_ids, batch_size): Groups shares by commitment set for efficient batch verification.

• _process_verification_batches(self, verification_batches): Processes verification batches, potentially in parallel (using concurrent.futures if available). This handles the actual verification of shares within each batch, using either batch_verify_shares or verify_share as appropriate. It includes error handling for exceptions that might occur during verification.

• _get_share_value_from_results(self, party_id, p_id, zero_sharings): Retrieves a share value from the zero_sharings dictionary, with validation to handle cases where the share might be missing.

• _generate_invalidity_evidence(self, party_id, p_id, zero_sharings, zero_commitments, verification_proofs, share_verification, echo_consistency): Generates cryptographic evidence when an invalid share is detected. This evidence includes the share itself, the commitments, and information about whether the share passed verification and echo consistency checks.

• _enhanced_collusion_detection(self, invalid_shares_detected, party_ids, echo_consistency): Implements enhanced collusion detection, looking for patterns of invalid shares that might indicate coordinated malicious behavior. It uses a combination of:

  • Invalid Share Count: Counting how many times each party provided invalid shares.
  • Targeting Patterns: Analyzing which participants were targeted by invalid shares from suspicious parties.
  • Echo Consistency Failures: Incorporating information from echo consistency checks to identify parties that equivocated.
  • Jaccard Similarity: Using the Jaccard similarity coefficient to measure the overlap in the sets of participants targeted by different suspicious parties.

• create_polynomial_proof(self, coefficients, commitments): Creates a zero-knowledge proof of knowledge of the polynomial coefficients. This allows a prover to demonstrate that they know the coefficients without revealing them. This implementation follows Baghery's framework for post-quantum security.

  • Blinding Factors: Generates random blinding factors.
  • Blinding Commitments: Creates commitments to the blinding factors.
  • Fiat-Shamir Transform: Uses the Fiat-Shamir transform to generate a non-interactive challenge. The challenge is computed by hashing a combination of public values, including the generator, prime, commitments, blinding commitments, and a timestamp.
  • Responses: Computes responses based on the blinding factors, challenge, and coefficients.
  • Returns: A dictionary containing the blinding commitments, challenge, responses, commitment randomizers, blinding randomizers, and a timestamp.

• verify_polynomial_proof(self, proof, commitments): Verifies a zero-knowledge proof of knowledge of polynomial coefficients.

  • Input Validation: Performs thorough input validation to ensure the proof and commitments have the expected structure.
  • Response Verification: Verifies the response equation for each coefficient. For hash-based commitments, this involves computing the hash commitment for the response and comparing it to the expected commitment (blinding commitment + challenge * commitment).
  • Constant-Time Comparison: Uses constant_time_compare for all comparisons.
  • Returns: True if the proof is valid, False otherwise.

• _detect_byzantine_behavior(self, party_id, commitments, shares, consistency_results=None): This is a critical function for detecting malicious behavior by the dealer. It checks for several types of inconsistencies:

  • Invalid Commitments: Checks if the commitments are well-formed (e.g., not empty, have the correct structure). For hash-based commitments, it specifically verifies that the first commitment (corresponding to the secret) is a commitment to 0.
  • Inconsistent Shares: Checks if the shares distributed by the party are consistent with the commitments. It uses verify_share for this check.
  • Equivocation: Checks for evidence of equivocation (the party sending different values to different participants) using the consistency_results from the echo-broadcast protocol (if available).
  • Returns: A tuple (is_byzantine, evidence), where is_byzantine is a boolean indicating whether Byzantine behavior was detected, and evidence is a dictionary containing details about the detected inconsistencies.

• detect_byzantine_party(self, party_id, commitments, shares, consistency_results=None): A public method that calls _detect_byzantine_behavior to detect Byzantine behavior from a specific party.

• _evaluate_polynomial(self, coefficients, x): Evaluates a polynomial at a given point x using Horner's method. This is used for generating shares and for reconstructing the secret. All arithmetic is performed modulo the field prime using gmpy2.

• _reconstruct_polynomial_coefficients(self, x_values, y_values, threshold): Reconstructs the polynomial coefficients from a set of shares (x-values and y-values) using Lagrange interpolation. This function is critical for secret reconstruction.

  • Input Validation: Checks that enough points are provided and that the x-values are unique.
  • Special Case (threshold=1): Handles the case where the threshold is 1 (constant polynomial) directly.
  • Matrix-Based Approach: For threshold > 1, it uses a matrix-based approach:
    • Vandermonde Matrix: Creates a Vandermonde matrix representing the system of linear equations.
    • Secure Gaussian Elimination: Solves the system using _secure_matrix_solve, which implements Gaussian elimination with attempts to be side-channel resistant.

• _secure_matrix_solve(self, matrix, vector, prime=None): Solves a system of linear equations using Gaussian elimination, with attempts to mitigate side-channel attacks.

  • Forward Elimination: Performs forward elimination, finding pivots and scaling rows.
  • Secure Pivot Selection: Uses _find_secure_pivot to find a non-zero pivot in a way that is intended to be side-channel resistant.
  • Modular Inverse: Calculates the inverse of the pivot using gmpy2.invert (which is more appropriate for modular inversion than powmod).
  • Constant-Time Operations: Uses constant-time operations (or attempts to) throughout the process.
  • Raises VerificationError: If non-invertible value is found during matrix operations.

• _find_secure_pivot(self, matrix, col, n): Finds a non-zero pivot for Gaussian elimination in a way that is intended to be side-channel resistant. Instead of selecting the first suitable pivot (which could create timing variations), it assigns random values to all potential pivots and selects the one with the minimal random value. This helps to prevent timing attacks that could leak information about the matrix structure.

• create_commitments_with_proof(self, coefficients, context=None): Creates commitments to polynomial coefficients and generates a zero-knowledge proof of knowledge of the coefficients in a single, combined operation. This is more efficient than creating commitments and proofs separately.

• verify_commitments_with_proof(self, commitments, proof): Verifies that a zero-knowledge proof demonstrates knowledge of the polynomial coefficients committed to by the given commitments. It calls verify_polynomial_proof.

• serialize_commitments_with_proof(self, commitments, proof): Serializes commitments and the associated zero-knowledge proof into a single string. This combines the functionality of serialize_commitments with the serialization of the proof data. The proof is included in the serialized data, along with a flag (has_proof) indicating its presence.

• deserialize_commitments_with_proof(self, data): Deserializes commitments and the associated zero-knowledge proof from a string (created by serialize_commitments_with_proof). It first deserializes the commitments using logic similar to deserialize_commitments and then extracts and reconstructs the proof data.

• verify_share_with_proof(self, share_x, share_y, serialized_data): Verifies a share and the associated zero-knowledge proof against serialized commitment and proof data. It deserializes the data using deserialize_commitments_with_proof and then calls both verify_share and verify_commitments_with_proof.

III. Factory Functions and Integration Helpers

• get_feldman_vss(field, **kwargs): A factory function that creates a FeldmanVSS instance with a post-quantum secure configuration. It ensures that the config is set appropriately for post-quantum security (at least 4096-bit primes, safe primes enabled, BLAKE3 preferred).

• create_vss_from_shamir(shamir_instance): Creates a FeldmanVSS instance that is compatible with a ShamirSecretSharing instance (presumably from a separate module). It extracts the field from the Shamir instance and configures the VSS accordingly. It also issues a warning if the Shamir instance uses a prime smaller than the recommended minimum for post-quantum security.

• integrate_with_pedersen(feldman_vss, pedersen_vss, shares, coefficients): Integrates Feldman VSS with Pedersen VSS. This provides both the binding property of Feldman VSS (the dealer cannot change the secret after commitments are made) and the hiding property of Pedersen VSS (the commitments reveal nothing about the secret). It generates both Feldman and Pedersen commitments, and creates a zero-knowledge proof (create_dual_commitment_proof) that both sets of commitments are to the same polynomial coefficients.

• create_dual_commitment_proof(feldman_vss, pedersen_vss, coefficients, feldman_commitments, pedersen_commitments): Creates a zero-knowledge proof that the Feldman and Pedersen commitments are to the same polynomial coefficients. This is a key component of the integration with Pedersen VSS.

  • Blinding Factors: Generates random blinding factors.
  • Blinding Commitments: Creates both Feldman and Pedersen commitments to the blinding factors.
  • Fiat-Shamir Transform: Uses the Fiat-Shamir transform to generate a non-interactive challenge.
  • Responses: Computes responses based on the blinding factors, challenge, and coefficients.
  • Returns: A dictionary containing the blinding commitments, challenge, responses, and (if using hash-based commitments) response randomizers.

• verify_dual_commitments(feldman_vss, pedersen_vss, feldman_commitments, pedersen_commitments, proof): Verifies the zero-knowledge proof created by create_dual_commitment_proof. It checks that both the Feldman and Pedersen commitments are consistent with the proof.

IV. Security Analysis and Known Vulnerabilities

The feldman_vss.py script is designed with a strong focus on security, but it's crucial to understand its limitations and known vulnerabilities.

A. Strengths:

• Post-Quantum Security: The exclusive use of hash-based commitments (BLAKE3 or SHA3-256) makes the scheme resistant to attacks from quantum computers.
• Provable Security (in principle): The design is based on well-established cryptographic principles and protocols (Feldman VSS, Chen & Lindell's share refreshing, zero-knowledge proofs, Fiat-Shamir transform).
• Efficiency Optimizations: Batch verification, precomputation, caching, and optimized multi-exponentiation significantly improve performance.
• Robustness Features: Input validation, error handling, and countermeasures against fault injection and Byzantine behavior enhance the script's resilience.
• Serialization with Integrity: Secure serialization with checksums protects against data tampering.
• Integration with Pedersen VSS: The ability to integrate with Pedersen VSS provides both binding and hiding properties.
• Share Refreshing: Secure share refreshing protocol enhances the resistance against Byzantine faults.

B. Known Vulnerabilities (Explicitly Acknowledged in the Docstring):

1. Timing Side-Channels in Matrix Operations: The functions _find_secure_pivot and _secure_matrix_solve are vulnerable to timing attacks in pure Python. Python's execution model makes it extremely difficult to guarantee constant-time execution of these operations. An attacker who can precisely measure the execution time of these functions might be able to glean information about the secret polynomial.

2. Non-Constant-Time Comparison: The constant_time_compare function, while intended to be constant-time, does not provide true constant-time guarantees in Python. This means that comparisons might take slightly different amounts of time depending on the values being compared, potentially leaking information to an attacker.

C. Other Potential Concerns:

• secure_redundant_execution Limitations: While secure_redundant_execution attempts to mitigate fault injection attacks, it's not a perfect defense in Python. Python's interpreter and garbage collection can introduce variations in execution timing that might make it difficult to reliably detect fault injections.
• Pure Python Implementation: The reliance on pure Python for security-critical operations is a fundamental limitation. For truly robust security, these operations should be implemented in a lower-level language (like Rust) that provides better control over execution timing and memory management.

V. Conclusion and Future Directions

The feldman_vss.py script (version 0.7.6b0) provides a sophisticated and well-documented implementation of Feldman's Verifiable Secret Sharing with a strong emphasis on post-quantum security. It incorporates numerous optimizations and security features, making it a valuable resource for developers working with secret sharing.

However, it's crucially important to be aware of the known vulnerabilities related to timing side-channels and fault injection countermeasures in the pure Python implementation. The script itself acknowledges these limitations and recommends considering it experimental until these issues are addressed.

The planned resolution, as stated in the docstring, is to integrate with Rust components for security-critical operations in future versions. This would provide a much stronger guarantee of constant-time execution and significantly improve the script's resistance to timing and fault injection attacks.