multi_party_ecdsa/utilities/zk_pdl/
mod.rs

1#![allow(non_snake_case)]
2/*
3    Multi-party ECDSA
4
5    Copyright 2018 by Kzen Networks
6
7    This file is part of Multi-party ECDSA library
8    (https://github.com/KZen-networks/multi-party-ecdsa)
9
10    Multi-party ECDSA is free software: you can redistribute
11    it and/or modify it under the terms of the GNU General Public
12    License as published by the Free Software Foundation, either
13    version 3 of the License, or (at your option) any later version.
14
15    @license GPL-3.0+ <https://github.com/KZen-networks/multi-party-ecdsa/blob/master/LICENSE>
16*/
17
18//! We use the proof as given in protocol 6.1 in https://eprint.iacr.org/2017/552.pdf
19//! Statement: (c, pk, Q, G)
20//! witness (x, r, sk) such that Q = xG, c = Enc(pk, x, r) and Dec(sk, c) = x.
21//! note that because of the range proof, the proof is sound only for x < q/3
22
23use std::ops::Shl;
24
25use curv::arithmetic::traits::*;
26use curv::cryptographic_primitives::commitments::hash_commitment::HashCommitment;
27use curv::cryptographic_primitives::commitments::traits::Commitment;
28use curv::elliptic::curves::{secp256_k1::Secp256k1, Point, Scalar};
29use curv::BigInt;
30use paillier::Paillier;
31use paillier::{Add, Decrypt, Encrypt, Mul};
32use paillier::{DecryptionKey, EncryptionKey, RawCiphertext, RawPlaintext};
33use serde::{Deserialize, Serialize};
34use sha2::Sha256;
35use thiserror::Error;
36use zk_paillier::zkproofs::IncorrectProof;
37use zk_paillier::zkproofs::RangeProofNi;
38
39#[derive(Error, Debug)]
40pub enum ZkPdlError {
41    #[error("zk pdl message2 failed")]
42    Message2,
43    #[error("zk pdl finalize failed")]
44    Finalize,
45}
46
47#[derive(Clone)]
48pub struct PDLStatement {
49    pub ciphertext: BigInt,
50    pub ek: EncryptionKey,
51    pub Q: Point<Secp256k1>,
52    pub G: Point<Secp256k1>,
53}
54#[derive(Clone)]
55pub struct PDLWitness {
56    pub x: Scalar<Secp256k1>,
57    pub r: BigInt,
58    pub dk: DecryptionKey,
59}
60
61#[derive(Debug, Clone)]
62pub struct PDLVerifierState {
63    pub c_tag: BigInt,
64    pub c_tag_tag: BigInt,
65    a: BigInt,
66    b: BigInt,
67    blindness: BigInt,
68    q_tag: Point<Secp256k1>,
69    c_hat: BigInt,
70}
71
72#[derive(Debug, Clone)]
73pub struct PDLProverState {
74    pub decommit: PDLProverDecommit,
75    pub alpha: BigInt,
76}
77
78#[derive(Debug, Serialize, Deserialize, Clone)]
79pub struct PDLVerifierFirstMessage {
80    pub c_tag: BigInt,
81    pub c_tag_tag: BigInt,
82}
83
84#[derive(Debug, Serialize, Deserialize, Clone)]
85pub struct PDLProverFirstMessage {
86    pub c_hat: BigInt,
87    pub range_proof: RangeProofNi,
88}
89
90#[derive(Debug, Serialize, Deserialize, Clone)]
91pub struct PDLVerifierSecondMessage {
92    pub a: BigInt,
93    pub b: BigInt,
94    pub blindness: BigInt,
95}
96
97#[derive(Debug, Clone, Serialize, Deserialize)]
98pub struct PDLProverDecommit {
99    pub q_hat: Point<Secp256k1>,
100    pub blindness: BigInt,
101}
102
103#[derive(Debug, Serialize, Deserialize, Clone)]
104pub struct PDLProverSecondMessage {
105    pub decommit: PDLProverDecommit,
106}
107
108pub struct Prover {}
109pub struct Verifier {}
110
111impl Verifier {
112    pub fn message1(statement: &PDLStatement) -> (PDLVerifierFirstMessage, PDLVerifierState) {
113        let a_fe = Scalar::<Secp256k1>::random();
114        let a = a_fe.to_bigint();
115        let q = Scalar::<Secp256k1>::group_order();
116        let q_sq = q.pow(2);
117        let b = BigInt::sample_below(&q_sq);
118        let b_fe = Scalar::<Secp256k1>::from(&b);
119        let b_enc = Paillier::encrypt(&statement.ek, RawPlaintext::from(b.clone()));
120        let ac = Paillier::mul(
121            &statement.ek,
122            RawCiphertext::from(statement.ciphertext.clone()),
123            RawPlaintext::from(a.clone()),
124        );
125        let c_tag = Paillier::add(&statement.ek, ac, b_enc).0.into_owned();
126        let ab_concat = a.clone() + b.clone().shl(a.bit_length());
127        let blindness = BigInt::sample_below(q);
128        let c_tag_tag = HashCommitment::<Sha256>::create_commitment_with_user_defined_randomness(
129            &ab_concat, &blindness,
130        );
131        let q_tag = &statement.Q * &a_fe + &statement.G * b_fe;
132
133        (
134            PDLVerifierFirstMessage {
135                c_tag: c_tag.clone(),
136                c_tag_tag: c_tag_tag.clone(),
137            },
138            PDLVerifierState {
139                c_tag,
140                c_tag_tag,
141                a,
142                b,
143                blindness,
144                q_tag,
145                c_hat: BigInt::zero(),
146            },
147        )
148    }
149
150    pub fn message2(
151        prover_first_messasge: &PDLProverFirstMessage,
152        statement: &PDLStatement,
153        state: &mut PDLVerifierState,
154    ) -> Result<PDLVerifierSecondMessage, ZkPdlError> {
155        let decommit_message = PDLVerifierSecondMessage {
156            a: state.a.clone(),
157            b: state.b.clone(),
158            blindness: state.blindness.clone(),
159        };
160        let range_proof_is_ok =
161            verify_range_proof(statement, &prover_first_messasge.range_proof).is_ok();
162        state.c_hat = prover_first_messasge.c_hat.clone();
163        if range_proof_is_ok {
164            Ok(decommit_message)
165        } else {
166            Err(ZkPdlError::Message2)
167        }
168    }
169
170    pub fn finalize(
171        prover_first_message: &PDLProverFirstMessage,
172        prover_second_message: &PDLProverSecondMessage,
173        state: &PDLVerifierState,
174    ) -> Result<(), ZkPdlError> {
175        let c_hat_test = HashCommitment::<Sha256>::create_commitment_with_user_defined_randomness(
176            &BigInt::from_bytes(prover_second_message.decommit.q_hat.to_bytes(true).as_ref()),
177            &prover_second_message.decommit.blindness,
178        );
179
180        if prover_first_message.c_hat == c_hat_test
181            && prover_second_message.decommit.q_hat == state.q_tag
182        {
183            Ok(())
184        } else {
185            Err(ZkPdlError::Finalize)
186        }
187    }
188}
189
190impl Prover {
191    pub fn message1(
192        witness: &PDLWitness,
193        statement: &PDLStatement,
194        verifier_first_message: &PDLVerifierFirstMessage,
195    ) -> (PDLProverFirstMessage, PDLProverState) {
196        let c_tag = verifier_first_message.c_tag.clone();
197        let alpha = Paillier::decrypt(&witness.dk, &RawCiphertext::from(c_tag));
198        let alpha_fe = Scalar::<Secp256k1>::from(alpha.0.as_ref());
199        let q_hat = &statement.G * alpha_fe;
200        let blindness = BigInt::sample_below(Scalar::<Secp256k1>::group_order());
201        let c_hat = HashCommitment::<Sha256>::create_commitment_with_user_defined_randomness(
202            &BigInt::from_bytes(q_hat.to_bytes(true).as_ref()),
203            &blindness,
204        );
205        // in parallel generate range proof:
206        let range_proof = generate_range_proof(statement, witness);
207        (
208            PDLProverFirstMessage { c_hat, range_proof },
209            PDLProverState {
210                decommit: PDLProverDecommit { blindness, q_hat },
211                alpha: alpha.0.into_owned(),
212            },
213        )
214    }
215
216    pub fn message2(
217        verifier_first_message: &PDLVerifierFirstMessage,
218        verifier_second_message: &PDLVerifierSecondMessage,
219        witness: &PDLWitness,
220        state: &PDLProverState,
221    ) -> Result<PDLProverSecondMessage, ZkPdlError> {
222        let ab_concat = &verifier_second_message.a
223            + verifier_second_message
224                .b
225                .clone()
226                .shl(verifier_second_message.a.bit_length()); // b|a (in the paper it is a|b)
227        let c_tag_tag_test =
228            HashCommitment::<Sha256>::create_commitment_with_user_defined_randomness(
229                &ab_concat,
230                &verifier_second_message.blindness,
231            );
232        let ax1 = &verifier_second_message.a * witness.x.to_bigint();
233        let alpha_test = ax1 + &verifier_second_message.b;
234        if alpha_test == state.alpha && verifier_first_message.c_tag_tag == c_tag_tag_test {
235            Ok(PDLProverSecondMessage {
236                decommit: state.decommit.clone(),
237            })
238        } else {
239            Err(ZkPdlError::Message2)
240        }
241    }
242}
243
244fn generate_range_proof(statement: &PDLStatement, witness: &PDLWitness) -> RangeProofNi {
245    RangeProofNi::prove(
246        &statement.ek,
247        Scalar::<Secp256k1>::group_order(),
248        &statement.ciphertext,
249        &witness.x.to_bigint(),
250        &witness.r,
251    )
252}
253
254fn verify_range_proof(
255    statement: &PDLStatement,
256    range_proof: &RangeProofNi,
257) -> Result<(), IncorrectProof> {
258    range_proof.verify(&statement.ek, &statement.ciphertext)
259}
260
261#[cfg(test)]
262mod test;
multi_party_ecdsa/utilities/zk_pdl/mod.rs

multi_party_ecdsa/utilities/zk_pdl/
mod.rs
