TL;DR
This paper introduces a significantly faster and more communication-efficient zero-knowledge argument protocol for verifying encrypted extended permutations. This improvement is crucial for enhancing the security and practicality of private function evaluation (PFE) protocols, especially those designed to protect against malicious adversaries.
What Problem Does This Paper Address?
The paper tackles a critical challenge in secure multi-party computation (MPC), specifically within the domain of Private Function Evaluation (PFE). PFE allows a party to privately evaluate a function (represented by a circuit) on inputs held by other parties, without revealing the function itself or the inputs beyond the final result. A key requirement for actively secure PFE protocols is ensuring that the party providing the private circuit (the "circuit provider") correctly performs an "extended permutation" (EP) on encrypted data. An EP is a generalized permutation that allows elements to be replicated or omitted, which is useful for representing circuit structures.
The problem arises because the circuit provider needs to prove they've correctly performed this EP on encrypted data without revealing the EP itself. The existing solution, a zero-knowledge argument of encrypted extended permutation, is interactive and computationally expensive, acting as an efficiency bottleneck. This paper aims to improve this zero-knowledge argument, making it more efficient and potentially non-interactive.
Methods
The core contribution of this paper is an improved zero-knowledge argument protocol for encrypted extended permutations. The authors build upon the ElGamal encryption scheme and decompose the complex task of proving a valid EP into four distinct, manageable steps:
- Extension: Parties pad the input ciphertext list with dummy ciphertexts if the output list is expected to be longer.
- Placement: Dummy ciphertexts are introduced to account for omitted elements or elements mapped to multiple outputs. The list is permuted, and ciphertexts are re-randomized.
- Replication: Dummy ciphertexts are replaced by their preceding non-dummy counterparts, effectively replicating ciphertexts for elements mapped to multiple outputs. Ciphertexts are re-randomized again.
- Finalization: Extra dummy ciphertexts are removed (if any), and the list is permuted to its final order, followed by a final re-randomization.
The protocol then uses two sub-protocols to prove the correctness of these steps:
- II_Shuffle: A zero-knowledge protocol for proving the correctness of a shuffle operation. The paper leverages an existing efficient, non-interactive version of this protocol.
- II_DH: A zero-knowledge protocol for proving knowledge of a Diffie-Hellman tuple, used to prove the correctness of certain relationships between ciphertexts.
The authors also detail how their protocol can be made non-interactive using the Fiat-Shamir heuristic.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- Decomposition for Efficiency: Breaking down the complex proof of an extended permutation into four distinct, simpler steps (extension, placement, replication, finalization) is key to achieving efficiency gains. Each step addresses a specific aspect of the EP transformation.
- Leveraging Existing Primitives: The protocol effectively combines existing cryptographic primitives (ElGamal encryption, zero-knowledge proofs for shuffling and Diffie-Hellman) to construct a novel, more efficient solution.
- Non-Interactivity Potential: The design, particularly its public-coin nature, allows for straightforward compilation into a non-interactive protocol using the Fiat-Shamir heuristic, a significant practical advantage.
- Performance Gains: The paper demonstrates substantial improvements in both communication cost and computational speed compared to prior work, making advanced PFE protocols more feasible.
Key Results
The paper presents a zero-knowledge argument protocol for encrypted extended permutations that offers significant improvements over the state-of-the-art:
- Communication Cost: The proposed protocol's communication cost is approximately 24% of the previous protocol [25].
- Computation Cost: The protocol is significantly faster, being more than 3.4 times faster than the previous protocol.
- Non-Interactive: The protocol can be instantiated to be non-interactive, whereas the previous protocol was interactive.
Limitations and Future Work
- Assumptions: The security of the protocol relies on the decisional Diffie-Hellman (DDH) assumption for the ElGamal encryption scheme.
- Sub-protocol Dependencies: The efficiency of the overall protocol is partly dependent on the efficiency of the underlying sub-protocols, specifically II_Shuffle and II_DH. While the paper uses an efficient II_Shuffle, further improvements in these sub-protocols could lead to even greater gains.
- Future Work: The paper suggests that protocols based on their improved zero-knowledge argument, such as linear actively secure PFE protocols, can also benefit from these performance enhancements. The authors' work paves the way for more practical and secure PFE implementations.
Summary updated