Confidential and auditable payments?
Tatsuo Mitani1,2 and Akira Otsuka1
1Institute of Information Security, Yokohama, Japan{dgs187101,otsuka}@iisec.ac.jp
2
Mitsubishi Chemical Systems, Inc.

Abstract. In this paper, we construct the Confidential and Auditable
Payments (CAP) scheme. We keep the transaction confidential by writing
ciphertexts of transactions in a ledger. We also realize the soundness of
the CAP scheme by the soundness of the zero-knowledge proof. A court
controls a unique secret key of the ciphertexts written in the ledger.
The court can enforce confidential transactions open with the secret key
according to the legal procedure. Although there are many works forprotecting transaction’s privacy strictly, the CAP scheme eliminates concerns about money laundering caused by excessively confidential transactions. It contributes to the sound use of blockchain.
Keywords: blockchain · homomorphic encryption · zero-knowledge proof.

1

Introduction

Bitcoin [13] has spread around the world in the past decade. This virtual technology is called a blockchain. Bitcoin makes transaction information public. For
this reason, Bitcoin is transparent. The bank keeps the customer’s transaction
information confidential. Therefore, there is a need to keep transaction information concealed even in the blockchain. However, excessive confidentiality oftransaction information may cause money laundering.
In this paper, we construct the Confidential and Auditable Payments (CAP)
scheme that allows a court to audit transactions while keeping the transaction
information confidential. Every participant writes their account balance as aciphertext of homomorphic encryption in a ledger with a unique public key. They
realize transactions by calculating ciphertexts. The court controls its secret key
and can forcefully decrypt the ciphertexts and confirm the information.
1.1

Related work

In Bitcoin, transaction information is open. For this reason, there are some works
for concealing transaction information. Zerocoin [10] and Zerocash [15] are extensions based on Bitcoin. They realized strong anonymity by designing anonymouscoins that skillfully combined commitments. Zerocash uses the zero-knowledge?

Supported by Mitsubishi Chemical Corporation.

2

Tatsuo Mitani and Akira Otsuka

succinct non-interactive argument of knowledge (zk-SNARK) [6] to show to others that there is no fraud such as double-spending. Recently, Zether [4], a cryptocurrency that can conceal transaction information, has been proposed as anextension based on Ethereum. Zether has also used the zero-knowledge proof
Bulletproofs [5] proposed by their group.
Mitani and Otsuka expressed the state transition of a permissioned blockchain
using homomorphic encryption [11]. In their scheme, a zero-knowledge proof ofplaintext knowledge shows that the equation of the encrypted model is established to outsiders of the blockchain, and proves the validity of the state transition.
1.2

Our approach

There are many works for protecting transaction privacy strictly. However, weintend to reduce the excessive confidentiality inducing money laundering. We
propose a confidential and auditable scheme.
Let us state our approach. We describe auditability at first. A pair of apublic key pk0 and a secret key sk0 of homomorphic encryption is issued. The
court controls this secret key sk0 . They can decrypts ciphertexts according to
the judicial procedure when requested. In this sense, the scheme is auditable.
Next, we state confidentiality. As shown in Fig. 1, we consider that a column vector of each participant’s account balance ~x is updated to the next timestate ~x0 by the transition matrix A. That is, ~x0 = ~xA. The transition matrix
A corresponds to the remittance by each participant. Each participant uses the
public key pk0 in common. Each participant writes their balance in the ledger as
ciphertext ~x. As for the transition matrix, each participant writes each elementin the ledger as ciphertext A. Then, each participant writes their balance of thenext time, reflecting the remittance in the ledger as a ciphertext ~x0 . All the ciphertexts in the ledger are the ciphertexts of homomorphic encryption. ~x0 − ~xA
is the ciphertext of zero if and only if ~x0 = ~xA.

a23x2

a12 a31

x3

a33

a22
−→
x1

x02

x03

−→
a11

x01

Fig. 1. Illustration of a state transition for three participants. ~x = (x1 , x2 , x3 ), ~
x0 =
0
0
0
0
(x1 , x2 , x3 ) and A = (aij ) are plaintexts. The corresponding ciphertexts are ~x, ~x and
A. Because of the homomorphic encryption, ~x0 − ~xA is the ciphertext of zero if andonly if ~x0 = ~
xA.

Confidential and auditable payments

3

Let us confirm the remittance procedure when a sender i transfers to a recipient j. The element aij of the transition matrix A corresponds to this remittance.
We use zero-knowledge proof of plaintext knowledge of ciphertext to show thatthe remittance is legitimate. The sender also writes the proof regarding aij in theledger. This proof shows that the sender has not sent more than their accountbalance. Knowledge corresponds to the randomness in creating the ciphertextof homomorphic encryption. At the time of remittance, the sender encrypts therandomness with the recipient’s public key pkj . Then the sender sends it to therecipient. The recipient decrypts with their secret key skj and obtains the randomness of the remittance. From the knowledge of the randomness collected,
the recipient proves that their updated account balance x0j is correct by theoperation ~x0 = ~xA.
We organize the rest of this paper as follows. Section 2 describes two ingredients: the ring learning with errors(RLWE) and the zero-knowledge proof(ZKP).
Section 3 describes the definitions for a secure CAP scheme. Section 4 describes
the construction of the CAP scheme, including data structures, algorithms, andsecurity proofs. Section 5 states the conclusion and future work.

2

Building blocks

Notation. We summarize the parameters and notation in this paper in Table
1. We identify a vector (a0 , . . . , and −1 ) with a polynomial a0 + a1 X + · · · +and −1 X nd −1 .
RLWE. Fully homomorphic encryption is capable of both addition and multiplication in ciphertexts. Gentry realized it in 2009 [7]. The RLWE scheme [9] is oneof the most promising forms. We introduce the definitions used in this paper.
Definition 1 (Syntax of the RLWE scheme (Definition 6 in [2])). We
describe the RLWE scheme represented by a tuple of PPT algorithms
RLWE := (RLWE.Gen, RLWE.Enc, RLWE.Dec)
with the following syntax. We denote a message space as M and a ciphertext
space as C.
– RLWE.Gen(1λ ) returns a key pair (pk, sk) from an input 1λ .
– RLWE.Enc(pk, m, r) returns a ciphertext c ∈ C from an input of the public
key pk, a message m ∈ M and a randomness r.
– RLWE.Dec(sk, c) returns a message m ∈ M or ⊥ from an input of the secretkey sk and a ciphertext c ∈ C.
Definition 2 (Pseudorandomness of ciphertexts (Definition 7 in [2])).
We say a RLWE scheme RLWE := (RLWE.Gen, RLWE.Enc, RLWE.Dec) satisfies
pseudorandomness of ciphertexts or simply RLWE is secure, if for every PPTadversary A the advantage
pr
Advpr
RLWE,A (λ) :=| Pr[ExpRLWE,A (λ) = 1] − 1/2 |is negligible in λ, where Exppr
RLWE,A (λ) is as defined in Fig. 2.

4

Tatsuo Mitani and Akira Otsuka
Table 1. List of Parameters and Notation
Parameters
N, Z, Q and R
Zq = Z/qZnd
R = Z[X]/hX nd + 1i
Rqq
= Zq [X]/hX nd + 1i

|a| =Explanation
the sets of natural numbers, integers, rational numbers
and real numbers
the finite field {0, 1, . . . , q − 1}
the degree of the polynomial
the ring of integers
the ring of integers modulo q

a20 + a21 + · · · + a2nd −1 l2 -norm of a ∈ Rq . ai is the coefficient of X i .

a negligible function f such that ∀n > nc , f (n) < 1/nc
under ∀c ∈ N, ∃nc
randomly sampled from the distribution A or$a←−Afrom a uniform distribution over the set A.
Õ(·)
Bachmann-Landau notationthe ω notation is a function growing asymptoticallyω(f (n))faster than f (n).
Oan oracle
Dσ and Dv,σ are discrete gaussian distributions on R
nd
nd
nd
with
mean 0, v and standard deviation σ.
Dv,σ = ρv,σ (x)/ρ0,σ (Z ) and−|x−v|2ndndnd1
Dσ = ρ0,σ(x)/ρ0,σ(Znd )
ρv,σ (x) = ( √2πσ
)nd e 2σ2 over Rnd
nd
nd
ρ0,σ
(Znd ) = Σz∈Znd ρ0,σ(z)Adv
the advantage of an adversary in a gameExpthe experiment in a gamePr[E]the probability that an event E occurs.
negl(n)Remark 1. We consider RLWE scheme that is secure in the sense of Definition
2. We write a ciphertext c in the boldface like this. We concretely consider
Brakerski-Vaikuntanathan (BV) scheme [3] in Table 2.
ZKP. Goldwasser et al. originally formulated this method [8]. ZKP is an interactive protocol that a prover that has a secret can inform a verifier of the factthat the proposition on the secret is correct. A prover can prevent the secretfrom being leaked. A verifier can reject a malicious prover with no secret.
Benhamouda et al. originally proposed the zero-knowledge proof of knowledgeof randomness in RLWE encryption [1]. Then, Mitani and Otsuka adopt its
scheme for the zero-knowledge proof of plaintext m = 0 knowledge in RLWE
encryption [11, 12]. We state this detail in Appendix A. In this paper, we denotethe zero-knowledge proof and its verification as below syntax.
– Prove(x; r) inputs the ciphertext x and its randomness r and outputs theproof π for the knowledge of RLWE.Dec(sk, x) = 0. We denotes Prove(x; r1 , . . . , rn )if there are some randomnesses r1 , . . . , rn .
– Verify(π) inputs the proof π and outputs 1 if it is valid, otherwise 0.

Confidential and auditable payments
Exppr
RLWE,A (λ) :λ(pk, sk) ← RLWE.Gen(1 )β ← {0, 1}
β 0 ← AORLWE.Enc (·) (1λ , pk)
if β = β 0 return 1
else return 0

5

ORLWE.Enc (m) :if β = 0c ← RLWE.Enc(pk, m)
else
$
− R2q
c←
return c

Fig. 2. Security challenge experiment for pseudorandomness of ciphertexts.
Table 2. Brakerski-Vaikuntanathan (BV) scheme
Parameters
M = Rp(a, b) and sc = (c1 , c2 ) = (bv + pe + m, av + pf )m = (c1 − s · c2 mod q) mod p

3

Explanation
the plaintext space(a, b) is a public key. s is a secret key.
$$

Then, a, s ←− Rq , es ←− Dσ , b = as + es .
the ciphertext of a plaintext m ∈ M$

Then, a set of randomness v, e, f ←− Dσ .
decryption of c = (c1 , c2 )Secure CAP scheme

In this section, we define the security of a CAP scheme. Regarding security, we
follow Zerocash [15]. Zerocash defines and satisfies the three properties; ledger
indistinguishability, transaction non-malleability, and balance. In this sense, the
DAP scheme of Zerocash is secure. We adjust the three properties for a CAP
scheme. We modify ledger indistinguishability. Balance corresponds to the proof
regarding the transition matrix, according to Lemma 1. We combine transaction
non-malleability and balance into non-malleability. In this sense, a CAP schemeΠ is secure. Let us confirm the below definitions.
Definition 3 (Ledger indistinguishability). A CAP schemeΠ := (Setup, CreateAccount, Transition, Send, Receive)
satisfies ledger indistinguishability, if for any λ ∈ N and any PPT adversary A,
the advantage
L−IND
AdvL−IND
Π,A (λ) :=| Pr[ExpΠ,A (λ) = 1] − 1/2 |is negligible in λ, where ExpL−IND
Π,A (λ) is defined in Fig. 3.
In Fig. 3, a pair of the queries (Q, Q0 ) must be the same type; CreateAccountor Transition. If the query type is Transition, then Q = (Transition, A) and Q0 =(Transition, A0 ). A and A0 must be same size. Each element is generally different.
~ and Q~ 0 are the lists of all the queries that A sent to theThat is, A 6= A0 . Q
oracles. Append is the function to append the latest query to the lists.

6

Tatsuo Mitani and Akira Otsuka
ExpL−IND
Π,A (λ):pp, cp ← Setup(1λ )L0 ← O0Π (pp); L1 ← O1Π (pp)$b←
− {0, 1}
while:~ Q~ 0 , Lb , L1−b )(Q, Q0 ) ← A(pp, Q,
ΠObΠ (·)
Lb ← A(pp, Q, Lb ); L1−b ← AO1−b (·) (pp, Q0 , L1−b )~ ← Append(Q,~ Q); Q~ 0 ← Append(Q~ 0 , Q0 )Q
~ Q
~ 0 , Lb , L1−b )c ← A(pp, Q,
if c = 1 breakelse continue~ Q~ 0 , Lb , L1−b )b0 ← A(pp, Q,
if b = b0 return 1
else return 0
Fig. 3. Security challenge experiment for ledger indistinguishability

Definition 4 (Non-malleability). A CAP schemeΠ := (Setup, CreateAccount, Transition, Send, Receive)
satisfies non-malleability, if for any λ ∈ N and any PPT adversary A, the advantage
NM
AdvNM
Π,A (λ) := Pr[ExpΠ,A (λ) = 1]Πis negligible in λ, where ExpNM
Π,A (λ) is defined in Fig. 4. Besides, O and Append
are the same as Definition 3.

We lead the below definition of a secure CAP scheme.
Definition 5 (Security). A CAP schemeΠ := (Setup, CreateAccount, Transition, Send, Receive)is secure if it satisfies ledger indistinguishability of Definition 3 and non-malleabilityof Definition 4.

4

Construction

In this section, we describe data structures, algorithms, and security analysis.
4.1

Data structures

In this subsection, we describe data structures of the CAP scheme. Following
the ideas of Mitani and Otsuka [11], we consider that the state of the assets heldby each participant will transition to the next state.

Confidential and auditable payments

7

ExpNM
Π,A (λ):pp, cp ← Setup(1λ )L ← OΠ (pp)while:~ L)
Q ← A(pp, Q,ΠL ← AO (·) (pp, Q, L)~ ← Append(Q,
~ Q)
Q
~ L)
c ← A(pp, Q,
if c = 1 breakelse continue~ L)A∗ ← A(pp, Q,
0O Π (·)
L ←A(pp, (Transition, A∗ ), L)Paif (Verify(π ) or Verify(~π b ) or Verify(Π c ) or Verify(~π 0 )) and ( i (x0i − xi ) 6∈ C0 ) in L0
return 1
else return 0

Fig. 4. Security challenge experiment for non-malleability– ~x = (x1 , x2 , . . . , xn ) ∈ Qn . ~x is the amount of assets in the blockchain attime t. n is the number of the participants in a blockchain.
– ~x0 = (x01 , x02 , . . . , x0n ) ∈ Qn . ~x0 is the amount of assets in the blockchain attime t + 1.
– A = (aij ) is a transition matrix such that ~x0 = ~xA. Its size is n × n. We
suppose that the total volume moving from xi to x0j is v. That is, x0i = xi − v
and x0j = xj + v. We define the distribution rate aij := v/xi . In particular,
we consider aii as the ”staying” rate (xi → x0i ). In the transition, the amountxi is distributed to x01 , . . . , x0i , . . . , x0n at the ratio of ai1 , . . . , aii , . . . , ain . The
sum
Pn of all the ratios must be equal 1 because of the preservation. That is,
j=1 aij = 1. Let us confirm the following lemma.
Pn
Lemma 1 (Lemma 1 in [11]). If ~x0 = ~xA and j=1 aij = 1, then thePnPnequation i=1 x0i = i=1 xi holds.
– Ledger L is a distributed ledger each participants in the blockchain holds
and updates. L contains the ciphertexts ~x, ~x0 , A and related proofs.
Remark 2. It is impractical to force all participants to join the transition matrix
A every time. We assume a transition matrix A0 that pertains only to participants
trading at a particular time t. That is, A0 is the submatrix of the transition
matrix A for all participants. Since there is essentially no difference, we will
discuss A and A0 indiscriminately.
4.2

Algorithms

We describe the CAP schemeΠ := (Setup, CreateAccount, Transition, Send, Receive)

8

Tatsuo Mitani and Akira Otsuka

in Fig. 5. We can verify the completeness of the CAP scheme Π by confirming
the construction in Fig. 5.
4.3

Security analysis

We describe the below lemmas for the security of the CAP scheme Π in Fig. 5.
Lemma 2 (Ledger indistinguishability). The CAP scheme Π in Fig. 5 satisfies ledger indistinguishability in Definition 3.
Proof. We consider the games in Fig. 6. We denote events as follows.
– E0 : G0CPA,A (λ) = 1– E1 : G1CPA,A (λ) = 1– B0 : β = 0– B1 : β = 1
Since B0 and B1 are disjoint events, we have
Pr[Ei ] = Pr[Ei ∩ B0 ] + Pr[Ei ∩ B1 ] = Pr[Ei |B0 ] · Pr[B0 ] + Pr[Ei |B1 ] · Pr[B1 ].
where i = {0, 1}. We construct an adversary B from an adversary A who candistinguish G0CPA,A (λ) and G1CPA,A (λ). That is,| Pr[G0CPA,A (λ) = 1] − Pr[G1CPA,A (λ) = 1] |=| Pr[E0 ] − Pr[E1 ] |=| (Pr[E0 |B0 ] · Pr[B0 ] + Pr[E0 |B1 ] · Pr[B1 ]) − (Pr[E1 |B0 ] · Pr[B0 ] + Pr[E1 |B1 ] · Pr[B1 ]) |=| Pr[B0 ] · (Pr[E0 |B0 ] − Pr[E1 |B0 ]) + Pr[B1 ] · (Pr[E0 |B1 ] − Pr[E1 |B1 ]) |≤ Pr[B0 ]· | Pr[E0 |B0 ] − Pr[E1 |B0 ] | + Pr[B1 ]· | Pr[E0 |B1 ] − Pr[E1 |B1 ] |= (Pr[B0 ] + Pr[B1 ]) · Advpr
RLWE,B (λ)= Advpr
RLWE,B (λ)
where we applied Pr[B0 ] + Pr[B1 ] = 1 in the last equation. Since the game
G1CPA,A (λ) is independent of β, we have thus Pr[G1CPA,A (λ) = 1] = 1/2. Moreover,0
ExpL−IND
Π,A (λ) consists of the game GCPA,A (λ). Because of Definition 2, we obtainpr0
AdvL−IND
Π,A (λ) ≤| Pr[GCPA,A (λ) = 1] − 1/2 |≤ AdvRLWE,B (λ) < negl(λ).

Lemma 3 (Non-malleability). The CAP scheme Π in Fig. 5 satisfies nonmalleability in Definition 4.
Proof. Let us consider the below violations of verification in the cases A wins
without the knowledge of randomness.
– A wins but violates Verify(π a ) in CreateAccount.
– A wins but violates Verify(~π b ) in Transition.
– A wins but violates Verify(Π c ) in Transition.

Confidential and auditable payments

9Transition
Setup– Inputs: security parameter λ– Outputs: public parameters pp and court parameters cp
1. Compute (pk0 , sk0 ) := RLWE.Gen(1λ ).
2. Set pp := pk0 .
3. Set cp := sk0 .
4. Output pp and cp.

– Inputs:• public parameters pp• old accounts state ~x = (x1 , . . . , xn ) in L
• accounts randomness rx1 , . . . , rxn– Outputs in L:• new accounts state ~x0 = (x01 , . . . , x0n )• new transition matrix A = (aij )• balance proofs ~π b = (π1b , . . . , πnb )c• accounts copy proofs Π c = (πij)• transition proofs ~π 0 = (π10 , . . . , πn0 )1. For i ∈ {1, . . . , n} (i sends v to j.)(a) For j ∈ {1, . . . , n}i. Send(pp, xi , rxi , xi , v, pkj ).
– Inputs: public parameters pp and security paramc
ii. Write πij, xcij , aij in L.
eter λa(b) Compute– Outputs: account ciphertext x, proof π in L andX
key pair (pk, sk)
πib := Prove(aij − 1; rai1 , . . . , rain ).
j
1. Choose randomly rx .
2. Compute x := RLWE.Enc(pk0 , 0, rx ).
(c) Write πib in L.
3. Compute π a := Prove(x; rx ).
2. Verify(Π c )4. Compute (pk, sk) := RLWE.Gen(1λ ).
3. Verify(~π b )5. Output x, π and (pk, sk).
4. For j ∈ {1, . . . , n} (j receives v from i.)(a) For i ∈ {1, . . . , n}Sendcci. Receive(pp, sk
Pj , xi , aij , v, rv , πij ).
0(b) Compute xj := i vij .
– Inputs:(c) Choose rx0j randomly.
• public parameters pp(d) Compute x0j := RLWE.Enc(pk0 , x0j , rx0j ).
• account ciphertext x in Ledger L• randomness rx(e) Compute• plaintext xX• sending volume v
πj0 := Prove(x0j −aij ·xi ; rx0j , rv1j , . . . , rvnj ).
i• public key pkj– Outputs:(f) Write x0j , πj0 in L.
• copy proof π c
5. Verify(~π 0 )• copy account xc• distribution ratio aij
Receive• volume v• randomness rv– Inputs:• public parameters ppcc
1. Choose randomly rx , where rx 6= rx .
• secret key skjc
2. Compute x := RLWE.Enc(pk0 , x, rxc ).
• ciphertexts xc , aij , v, rv
3. Compute π c := Prove(xc − x; rxc − rx ).
• proof π c in L
4. Compute a := v/x.
– Outputs:
5. Choose randomly raij .
• volume v
6. Compute aij := RLWE.Enc(pk0 , a, raij ).
• randomness rv
7. Compute rv from rxc and raij .
8. Compute v := RLWE.Enc(pkj , v, rv ).
1. Compute v := RLWE.Dec(skj , v).
9. Compute rv := RLWE.Enc(pkj , rv , rrv ).
2. Compute rv := RLWE.Dec(skj , rv ).
cc
10. Output π , x , aij , v, rv .
3. If aij ·xc = RLWE.Enc(pk0 , v, rv ) and |rv | is small:
Output v, rv .
4. Else: Output ⊥.

CreateAccountFig. 5. Construction of the CAP scheme

10

Tatsuo Mitani and Akira Otsuka
G0CPA,A (λ):(pk, sk) ← RLWE.Gen(1λ )β ← {0, 1}CPA
β 0 ← AO0 (·,·) (1λ , pk)0
if β = β return 1
else return 0
G1CPA,A (λ):(pk, sk) ← RLWE.Gen(1λ )β ← {0, 1}CPA
β 0 ← AO1 (·,·) (1λ , pk)
if β = β 0 return 1
else return 0

O0CPA (m0 , m1 ):if β = 0
Choose r randomly.
m ← RLWE.Enc(pk, m0 , r)else
Choose r randomly.
m ← RLWE.Enc(pk, m1 , r)return m
O1CPA (m0 , m1 ):
$

m←
− R2q
return m

Fig. 6. Security challenge experiment for plaintexts– A wins but violates Verify(~π 0 ) in Transition.
Any violations result from the violation of zero-knowledge proof, that is, theknowledge error of zero-knowledge proof. From Lemma 6, the knowledge errorof zero-knowledge proof is negligible.
Finally, we can lead the below theorem from Lemma 2 and Lemma 3.
Theorem 1 (The secure CAP scheme). The CAP scheme Π in Fig. 5 issecure in the sense of Definition 5.

5Conclusion

In this paper, we constructed the confidential and auditable payments(CAP)
scheme that allows a court to audit transactions while keeping the transaction
information confidential. We proposed that every participant writes the ciphertexts of transaction information in a ledger and confirmed the ledger indistinguishability, that is, the concealment of the transaction information. Besides,
we confirmed the soundness of the CAP scheme by the soundness of the zeroknowledge proof. Therefore the CAP scheme is secure. A court can forcibly clarify transaction information with a unique secret key. In this sense, we realized
auditability in the CAP scheme.

Future work. In the CAP scheme, the secret key of a court can decrypt alltransaction information. Therefore, we expect the court to disclose minimum
requisite information. Building a decryptable scheme for each account is an open
problem.

Confidential and auditable payments

11

References
1. Benhamouda, F., Camenisch, J., Krenn, S., Lyubashevsky, V., Neven, G.: Betterzero-knowledge proofs for lattice encryption and their application to group signatures. In: Sarkar, P., Iwata, T. (eds.) Advances in Cryptology – ASIACRYPT 2014.
pp. 551–572. Springer Berlin Heidelberg, Berlin, Heidelberg (2014)
2. Boyle, E., Kohl, L., Scholl, P.: Homomorphic secret sharing from lattices withoutfhe. In: Ishai, Y., Rijmen, V. (eds.) Advances in Cryptology – EUROCRYPT 2019.
pp. 3–33. Springer International Publishing, Cham (2019)
3. Brakerski, Z., Vaikuntanathan, V.: Fully homomorphic encryption from ring-lwe
and security for key dependent messages. In: Rogaway, P. (ed.) Advances in Cryptology – CRYPTO 2011. pp. 505–524. Springer Berlin Heidelberg, Berlin, Heidelberg (2011)
4. Bünz, B., Agrawal, S., Zamani, M., Boneh, D.: Zether: Towards privacy in a smart
contract world. IACR Cryptology ePrint Archive 2019, 191 (2019)
5. Bünz, B., Bootle, J., Boneh, D., Poelstra, A., Wuille, P., Maxwell, G.: Bulletproofs:
Short proofs for confidential transactions and more. In: 2018 IEEE Symposium on
Security and Privacy (SP). pp. 315–334. IEEE (2018)
6. Gennaro, R., Gentry, C., Parno, B., Raykova, M.: Quadratic span programs andsuccinct nizks without pcps. In: Johansson, T., Nguyen, P.Q. (eds.) Advances in
Cryptology – EUROCRYPT 2013. pp. 626–645. Springer Berlin Heidelberg, Berlin,
Heidelberg (2013)
7. Gentry, C.: Fully homomorphic encryption using ideal lattices. In: Proceedings ofthe Forty-First Annual ACM Symposium on Theory of Computing. pp. 169–178.
STOC 09, Association for Computing Machinery, New York, NY, USA (2009).
https://doi.org/10.1145/1536414.1536440
8. Goldwasser, S., Micali, S., Rackoff, C.: The knowledge complexity of interactive
proof systems. SIAM Journal on computing 18(1), 186–208 (1989)
9. Lyubashevsky, V., Peikert, C., Regev, O.: On ideal lattices and learning with errors
over rings. Journal of the ACM (JACM) 60(6), 43 (2013)
10. Miers, I., Garman, C., Green, M., Rubin, A.D.: Zerocoin: Anonymous distributed
e-cash from bitcoin. In: 2013 IEEE Symposium on Security and Privacy. pp. 397–
411. IEEE (2013)
11. Mitani, T., Otsuka, A.: Traceability in permissioned blockchain. In: 2019 IEEE
International Conference on Blockchain (Blockchain). pp. 286–293 (July 2019).
https://doi.org/10.1109/Blockchain.2019.00045
12. Mitani, T., Otsuka, A.: Traceability in permissioned blockchain. IEEE Access 8,21573–21588 (2020). https://doi.org/10.1109/ACCESS.2020.2969454
13. Nakamoto, S., et al.: Bitcoin: A peer-to-peer electronic cash system (2008)
14. Pedersen, T.P.: Non-interactive and information-theoretic secure verifiable secretsharing. In: Feigenbaum, J. (ed.) Advances in Cryptology — CRYPTO ’91. pp.
129–140. Springer Berlin Heidelberg, Berlin, Heidelberg (1992)
15. Sasson, E.B., Chiesa, A., Garman, C., Green, M., Miers, I., Tromer, E., Virza,
M.: Zerocash: Decentralized anonymous payments from bitcoin. In: 2014 IEEE
Symposium on Security and Privacy. pp. 459–474. IEEE (2014)

A

Non-interactive zero-knowledge proof

Following Benhamouda et al. [1], and Mitani and Otsuka [11, 12], we describe thenon-interactive zero-knowledge proof of plaintext m = 0 knowledge. First, we12Tatsuo Mitani and Akira Otsuka

describe the formal definition of the Σ 0 -protocol, the protocol and its theorem
proving this relationship.
Definition 6 (Definition 2.5. in [1]). Let (P, V ) be a two-party protocol,
where V is a PPT, and let L, L0 ⊆ {0, 1}∗ be languages with witness relations
R, R0 such that R ⊆ R0 . Then (P, V ) is called a Σ 0 -protocol for L, L0 with completeness error α, a challenge set C, a public input x and a private input w, if
and only if it satisfies the following conditions:– Three-move form: The prover P , on input (x, w), computes a commitment
t and sends it to V . The verifier V , on input x, then draws a challengec ← C and sends it to P . The prover sends a response s to the verifier.
Depending on the protocol transcript (t, c, s), the verifier finally accepts or
rejects the proof. The protocol transcript (t, c, s) is called accepting, if theverifier accepts the protocol run.
– Completeness: Whenever (x, w) ∈ R, the verifier V accepts with probability
at least 1 − α.
– Special soundness: There exists a PPT algorithm E (the knowledge extractor)
which takes two accepting transcripts (t, c0 , s0 ), (t, c00 , s00 ) satisfying c0 6= c00 as
inputs, and outputs w0 such that (x, w0 ) ∈ R0 .
– Special honest verifier zero knowledge (HVZK): There exists a PPT algorithm S (the simulator) taking x ∈ L and c ∈ C as inputs, that outputs(t, s) so that the triple (t, c, s) is indistinguishable from an accepting protocol
transcript generated by a real protocol run.
– High-entropy commitments: For all (y, w) ∈ R and for all t, the probability
that an honestly generated commitment by P takes on the value t is negligible.
Let us introduce Pedersen commitments [14] for the zero-knowledge proof. we
make use of the commitments as an auxiliary commitment scheme. We denote
it as (aCSetup, aCCommit, aCOpen).
Pedersen commitments. Given a family of prime order groups {G(λ)}λ∈N suchthat the discrete logarithm problem is hard in G(λ) with security parameter
λ, let q̃ = q̃(λ) be the order of G = G(λ). To avoid confusion, we denote all
elements with order q̃ with a tilde in the following. We will write the group G(λ)
additively.
$– aCSetup: This algorithm chooses g̃, h̃ ←− G and outputs cpars = (g̃, h̃).
$– aCommit: To commit to a message m ∈ Zq̃ , it first chooses r ←− Zq̃ . It theng o) = (mg̃ + rh̃, r).
outputs a pair (cmt,g an opening o, a public key cpars and a– aCOpen: Given a commitment cmt,?
g o) =
message m, it outputs accept if and only if (cmt,(mg̃ + rh̃, r).
Lemma 4 (Theorem 2.1. in [1]). Under the discrete logarithm assumption forG, the Pedersen commitment scheme is perfectly hiding and is computationallybinding.

Confidential and auditable payments

13

Common input: the public key (a, b), the ciphertext (c1 , c2 )√Relation: R0 = {((c1 , c2 ), (v, e, f )) : (c1 , c2 ) = (bv + pe, av + pf ) ∧ |v|, |e|, |f | ≤ Õ( nd α)}
ProverVerifier$

rv , r e , r f ←− DÕ(√nd α)
t1 = brv + re , t2 = arv + rf
(1)
(1)
(caux , daux ) = aCommit(t1 )
(2)

(1)

(2)

(caux , daux ) = aCommit(t2 )
(1)
(1)
(2)
(2)
c = h(t1 , t2 , caux , daux , caux , daux )ccsv = rv + X v, se = re + X pe, andsf = rf + X c pf , accept with probabilityDÕ(√3n α) ((sv ,se ,sf ))d√

M D(X c v,X c e,X c f ),Õ(

3nd α)((sv ,se ,sf ))

(2)

c

,c

(1)

(2)

aux aux−−−−−−→

t1 ,t2 ,daux ,daux ,(sv ,se ,sf )

(1)

(1)

(2)

(2)

−−−−−−−−−−−−−−−−−→ c = h(t1 , t2 , caux , daux , caux , daux )?

X c c1 + t1 = bsv + se?

X c c2 + t2 = asv + sf
?
(1)
(1)
aCOpen(t1 , caux , daux ) = accept
?
(2)
(2)
aCOpen(t2 , caux , daux ) = accept|sv |, |se |, |sf | ≤ Õ(nd α)
Fig. 7. Non-interactive zero-knowledge proof of a ciphertext of zero regarding RingLWE encryption (Figure 3 in [12])We show a non-interactive zero-knowledge proof of ciphertext of zero in Fig.
7. h is a cryptographic hash function. This protocol satisfies Lemma 5. The
parallel protocol satisfies Lemma 6.
Lemma 5 (Lemma 5 in [12]). The protocol in Fig. 7 is an HVZK Σ 0 -protocol
for the following relations:√
R0 = {((c1 , c2 ), (v, e, f )) : (c1 , c2 ) = (bv + pe, av + pf ) ∧ |v|, |e|, |f | ≤ Õ( nd α)}
R00 = {((c1 , c2 ), (v, e, f )) : (2c1 , 2c2 ) = (2bv + 2pe, 2av + 2pf ) ∧ |2v|, |2e|, |2f | ≤ Õ(n2d α)}
where 2v, 2e and 2f are reduced modulo q. The protocol has a knowledge errorof 1/(2nd ), a completeness error of 1 − 1/M , and high-entropy commitments.
Lemma 6 (Theorem 6 in [12]). Let us apply the protocol in Fig. 7 for λ times
in parallel (the parallel protocol). Let the parallel protocol be accepting if and only
if at least λ/2M out of λ proofs were valid under the condition that an honest
verifier rejects no proofs. Then, the parallel protocol has both a completenesserror and knowledge error of negl(λ) under the condition nd ≥ 2M .