博士論文

Privacy-Preserving Blockchain with Homomorphic Encryption

Tatsuo MITANI
三谷 辰雄

情報セキュリティ大学院大学
情報セキュリティ研究科
情報セキュリティ専攻

2020年9月

Privacy-Preserving Blockchain with Homomorphic Encryption

Tatsuo Mitani

Submitted in partial fulfillment of the requirements
for the Degree of Doctor of Philosophy in Informatics
in the Graduate School of Information Security

INSTITUTE OF INFORMATION SECURITY, JAPAN
September 2020

c 2020 Tatsuo Mitani

Publication list
This thesis is based on the below publications.
Peer Reviewed Papers[MO20c] T. Mitani and A. Otsuka, ”Traceability in Permissioned Blockchain,” in IEEE
Access, vol. 8, pp. 21573-21588, 2020. doi: 10.1109/ACCESS.2020.2969454
Peer Reviewed Proceedings of International Conferences[MO19] T. Mitani and A. Otsuka, ”Traceability in Permissioned Blockchain,” in 2019
IEEE International Conference on Blockchain, Atlanta, GA, USA, 2019, pp. 286293. doi: 10.1109/Blockchain.2019.00045[MO20b] T. Mitani and A. Otsuka, ”Confidential and Auditable Payments,” in Financial
Cryptography and Data Security. FC 2020. Lecture Notes in Computer Science,
vol 12063, pp 466-480. Springer, Cham. doi: 10.1007/978-3-030-54455-3 33
Preprint[MO20a] T. Mitani and A. Otsuka, “Anonymous probabilistic payment in payment
hub,” Cryptology ePrint Archive, Report 2020/748, 2020. https://eprint.iacr.
org/2020/748

iiiAbstract
Our modern society is highly digitized. Blockchain is an underlying technology that constitutes society. Privacy protection is a significant theme in society. For privacy protection,
homomorphic encryption is a promising technology capable of computing the state of encrypted data. In this thesis, we study privacy-preserving blockchain with homomorphic
encryption. There are two challenges in achieving privacy-preserving blockchain. One isconfidentiality in the transaction content. The other is unlinkability in the user identityof the transaction. We have achieved both in the permissioned blockchain. Furthermore,
we realized confidentiality and unlinkability in the permissionless blockchain.

Traceability in permissioned blockchain. We have achieved privacy protection andhigh transparency in a permissioned blockchain. Suppose that there is a sidechain thatconnects the permissionless blockchain and the permissioned blockchain. The behavior
in the permissioned blockchain is almost a black box from the perspective of the permissionless blockchain. We present a novel concept of traceability consisting of threeproperties. The properties are as follows. First, trade privacy says that who trades withwhom and at what asset amount. Second, preservation says that the total amount inside
the permissioned blockchain is immutable. We take inflow and outflow the permissionless
blockchain into consideration. Finally, noninvolvement says that some members in thepermissioned blockchain are not involved in some trades. One can prove that specified
members performed the transaction. Our approach is as follows. We model traceability with the hidden Markov model. The proof of traceability requires the calculation of
more than quadratic degrees. Therefore we encrypt this model by using homomorphic
encryption. The establishment of the original model is verifiable by the zero-knowledge
proof.
v

vi

ABSTRACT

Confidential and auditable payments. We construct the confidential and auditablepayments scheme. This proposal eliminates concerns about money laundering causedby excessively confidential transactions and contributes to blockchain’s sound use. Our
approach is as follows. For confidentiality, we keep the transaction confidential by writing
ciphertexts of transactions in a ledger. The soundness of the zero-knowledge proof realizes
the soundness of the scheme. For auditability, a court or an authority controls a uniquesecret key of the ledger’s ciphertexts. They can enforce confidential transactions openwith the secret key according to the proper procedure.
Anonymous probabilistic payment in payment hub. Privacy protection and scalability are significant problems with blockchain. We propose an anonymous probabilistic
payment under the general functionality for solving the problems. Suppose that a payer
pays a payee through a tumbler. We realize the anonymity, which says that the link, whichpayer pays which payee via the tumbler within an epoch, is broken. The epoch is theperiod when one completes transactions. Our proposal includes a probabilistic payment.
In the probabilistic payment, one pays an ordinary mount m with a certain probabilityp, and one pays a small amount mp as an expected value. It contributes scalability since
one can reduce the 1/p times transactions. We also introduce a novel fractional oblivioustransfer for the realization of the probabilistic payment. The functionality required forour proposal is the hashed time lock contract that various cryptocurrencies use. This
request is general, not restricted to any particular cryptocurrency.

Acknowledgments
Firstly, I much appreciate my supervisor, Professor Akira Otsuka. Fortunately, when I
started studying blockchain two years ago, he was willing to accept that he supervises
me. He led me to the frontier in the blockchain. I could enjoy days full of intellectual
excitement here. He has mentored me for these two years. I could not complete this workwithout his outstanding mentorship. I appreciate him for everything he has done for me.
I am incredibly grateful to Professor Seiko Arita, Professor Hiroshi Doi, and Professor
Kazuyuki Shudo for their constructive suggestions and valuable advice. I was able totake the first step in the lattice-based cryptography from the introductory paper in thebulletin written by Prof. Arita. After that, he discussed the lattice-based cryptography
and gave much guidance to me. Prof. Doi discussed the zero-knowledge proof and taught
me various things. Prof. Arita and Prof. Doi gave me much advice and notices while inschool. Prof. Shudo encouraged me in Atlanta, where I visited as my first international
conference. I am delighted that he is willing to take on the review.
I am thankful to the members of Otsuka Laboratory. They have given me many
cooperations, notices, and supports through my laboratory life. In particular, they taught
us various aspects of blockchain.
I want to show my appreciation to my managers and colleagues for their understanding and cooperation. I appreciate that Mitsubishi Chemical Corporation and Mitsubishi
Chemical Systems, Inc have supported this work. They gave me the precious opportunityof my studying blockchain in the Institute of Information Security. I could not fulfill thiswork without their excellent cooperation.
Finally, I kindly thank my family. They always encourage and help me. I sincerely
appreciate them for their affectionateness while studying and staying at home.

vii

List of Figures
2.1

Security challenge experiment for pseudorandomness of ciphertexts. . . . . 12

2.2

Zero-knowledge proof of knowledge of RLWE secrets s, e such that y =as + e (Protocol 3.2. in [BCK+ 14]) . . . . . . . . . . . . . . . . . . . . . . 16

2.3

Non-interactive zero-knowledge proof of a ciphertext of zero regarding RLWE
encryption (Figure 3 in [MO20c]) . . . . . . . . . . . . . . . . . . . . . . . 17

2.4

Non-interactive zero-knowledge proof of plaintext knowledge regarding RLWE
encryption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

3.1

Security challenge experiment for trade privacy . . . . . . . . . . . . . . . 45

3.2

Games G0TP,A (λ) and G1TP,A (λ) in the proof of Theorem 3.1.

4.1

Security challenge experiment for ledger indistinguishability . . . . . . . . 56

4.2

Security challenge experiment for non-malleability . . . . . . . . . . . . . . 57

4.3

Construction of the CAP scheme . . . . . . . . . . . . . . . . . . . . . . . 60

4.4

Security challenge experiment for plaintexts . . . . . . . . . . . . . . . . . 61

5.1

Overview of the proposed protocol . . . . . . . . . . . . . . . . . . . . . . . 67

5.2

Trapdoor by identity-based encryption [DLP14] . . . . . . . . . . . . . . . 69

5.3

Syntax of NIZK [CGL+ 16] . . . . . . . . . . . . . . . . . . . . . . . . . . . 70

5.4

The properties of NIZK

5.5

Syntax of the scheme and its simulator [CGL+ 16] . . . . . . . . . . . . . . 74

5.6

Construction of the ring fractional oblivious transfer . . . . . . . . . . . . . 77

5.7

Simulator of the ring fractional oblivious transfer . . . . . . . . . . . . . . 79

5.8

Puzzle solver protocol. We model H and H prg as random oracles. . . . . . 84

5.9

Ideal functionality Fsolver . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85

. . . . . . . . 45

. . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

5.10 Simulator for the puzzle solver protocol in the case that Alice is corrupt . . 86ix

x

LIST OF FIGURES
5.11 Simulator for the puzzle solver protocol in the case that the tumbler iscorrupt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
5.12 Puzzle promise protocol. We model H, H 0 and H shk as random oracles. . . 90
5.13 Ideal functionality Fpromise sign (Fig. 8 in [HAB+ 16]) . . . . . . . . . . . . . 91
5.14 Simulator for the puzzle promise protocol in the case that Bob is corrupt . 92
5.15 Simulator for the puzzle promise protocol in the case that the tumbler iscorrupt (Appendix F in [HAB+ 16]) . . . . . . . . . . . . . . . . . . . . . . 93

List of Tables
1.1

Overview of the contributions . . . . . . . . . . . . . . . . . . . . . . . . .

4

1.2

Properties’ comparison . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

3.1

Traceability’s Properties. Zether achieves either noninvolvement or tradeprivacy. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

3.2

Overview of parameters in the model . . . . . . . . . . . . . . . . . . . . . 36

3.3

Numbers of additions calculable with somewhat homomorphic encryption . 50

3.4

Proof size for 128-bit security . . . . . . . . . . . . . . . . . . . . . . . . . 51

xi

xii

LIST OF TABLES

Contents
Publication list

iii

Abstractv

Acknowledgmentsvii

List of Figuresix

List of Tables

xi

Contents

xiii

1 Introduction
1.1

1.2

1.3

1

Backgrounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1

1.1.1

Blockchain . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1

1.1.2

Homomorphic encryption . . . . . . . . . . . . . . . . . . . . . . . .

2

1.1.3

Zero-knowledge proof . . . . . . . . . . . . . . . . . . . . . . . . . .

2Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

1.2.1

Traceability in permissioned blockchain . . . . . . . . . . . . . . . .

4

1.2.2

Confidential and auditable payments . . . . . . . . . . . . . . . . .

6

1.2.3

Anonymous probabilistic payment in payment hub. . . . . . . . .

7. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8Organization

2 Building blocks

9

2.1

Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9

2.2

Ring learning with errors encryption . . . . . . . . . . . . . . . . . . . . . 10
2.2.1

Discrete Gaussian distribution . . . . . . . . . . . . . . . . . . . . . 10

2.2.2

Assumption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
xiii

xiv

CONTENTS
2.2.3
2.3

RLWE encryption and its syntax . . . . . . . . . . . . . . . . . . . 11

Zero-knowledge proof . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.3.1

Pedersen commitments . . . . . . . . . . . . . . . . . . . . . . . . . 13

2.3.2

Rejection sampling . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2.3.3

Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

2.3.4

Relation for the key generation . . . . . . . . . . . . . . . . . . . . 15

2.3.5

Relation for the ciphertext of zero . . . . . . . . . . . . . . . . . . . 16

2.3.6

Relation for valid ciphertext . . . . . . . . . . . . . . . . . . . . . . 22

3 Traceability in permissioned blockchain
3.1

3.2

3.3

3.4

3.5

Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.1.1

Related work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

3.1.2

Chapter organization . . . . . . . . . . . . . . . . . . . . . . . . . . 35

Traceability and modeling . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.2.1

Traceability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

3.2.2

Modeling. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

Encrypted model and its security . . . . . . . . . . . . . . . . . . . . . . . 42
3.3.1

Encrypted traceability model . . . . . . . . . . . . . . . . . . . . . 42

3.3.2

Security of trade privacy . . . . . . . . . . . . . . . . . . . . . . . . 44

3.3.3

Non-interactive zero-knowledge proof . . . . . . . . . . . . . . . . . 47

Encoding and its efficiency . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
3.4.1

Ring isomorphism encoding . . . . . . . . . . . . . . . . . . . . . . 47

3.4.2

Somewhat homomorphic encryption . . . . . . . . . . . . . . . . . . 48

3.4.3

Efficiency of zero-knowledge proof . . . . . . . . . . . . . . . . . . . 50

Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

4 Confidential and auditable payments
4.1

29

53

Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
4.1.1

Our approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

4.1.2

Related work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

4.1.3

Chapter organization . . . . . . . . . . . . . . . . . . . . . . . . . . 55

4.2

Secure CAP scheme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

4.3

Construction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

CONTENTS

xv

4.3.1

Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

4.3.2

Data structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

4.3.3

Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

4.3.4

Security analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

4.4

Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

5 Anonymous probabilistic payment in payment hub
5.1

5.2

5.3

5.4

63

Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
5.1.1

Our contribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64

5.1.2

Related work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64

5.1.3

Our approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

5.1.4

Chapter organization . . . . . . . . . . . . . . . . . . . . . . . . . . 68

Ring fractional oblivious transfer . . . . . . . . . . . . . . . . . . . . . . . 69
5.2.1

Trapdoor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

5.2.2

Non-interactive zero-knowledge proof . . . . . . . . . . . . . . . . . 69

5.2.3

Syntax and definition . . . . . . . . . . . . . . . . . . . . . . . . . . 73

5.2.4

Construction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76

Protocol and security . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
5.3.1

Puzzle solver protocol . . . . . . . . . . . . . . . . . . . . . . . . . 81

5.3.2

Puzzle promise protocol . . . . . . . . . . . . . . . . . . . . . . . . 88

Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95

6 Conclusion

97

Bibliography

99

xvi

CONTENTS

Chapter 1
Introduction
In this chapter, we describe the introduction consisting of the backgrounds, contributions,and organization.

1.1

Backgrounds

This section introduces three breakthroughs, blockchain, homomorphic encryption, andzero-knowledge proof that are deeply involved in this thesis as the backgrounds.

1.1.1

Blockchain

The first breakthrough is the blockchain. Blockchain is the underlying technology of
Bitcoin. Nakamoto [Nak08] published a paper on Bitcoin in 2008. Bitcoin is a payment
system that does not require a trusted third party, such as a bank. Participants called
nodes individually manage their ledger that records transactions. Each node agrees on
the new transactions and updates its ledger according to a consensus algorithm. Bitcoin
realizes a decentralized payment system in this way.
Wüst et al. [WG18] classified blockchain into the following two types from the viewpoint of participation. One is a permissioned blockchain in which only authorized members can participate. Hyperledger Fabric [ABB+ 18] is an implementation of permissioned
blockchains. The other is a permissionless blockchain that does not require permission toparticipate. Bitcoin, Ethereum [Woo14], and many cryptocurrencies are implementationsof permissionless blockchains.
1

2

CHAPTER 1. INTRODUCTION

1.1.2

Homomorphic encryption

The second breakthrough is the fully homomorphic encryption. Fully homomorphic encryption is capable of both addition and multiplication in ciphertext state. It had beenan open problem for about 30 years since the concept appeared. Gentry [Gen09] firstly
announced fully homomorphic encryption in 2009.
After this breakthrough, various studies have sprouted. One direction of the studies isregarding an efficient scheme. The first realization is infeasible because a ciphertext size
is too large. Regev [Reg09] defined the Learning With Errors (LWE) problem. He provedthat the LWE problem results from a worst-case lattice problem, such as the shortest
vector problem. Lyubashevsky et al. [LPR13] introduced the Ring Learning With Errors (RLWE) problem, which is an algebraic variant of the LWE problem. It is more
efficient than the LWE problem, and the same level of safety is also guaranteed. Several
schemes [BV11, FV12, BGV14] based on the RLWE problem were proposed. Also, several implementations [HS14, RR18, CLP17] based on these schemes are publicly available.
López-Alt et al. [LATV12] proposed NTRU-like fully homomorphic encryption. Acar etal. [AAUC18] evaluated that the scheme is efficient but needs the new Decisional Small
Polynomial Ratio (DSPR) assumption. We mainly consider homomorphic encryption
based on the RLWE problem in this thesis.
Another direction is the lattice-based protocols. The RLWE scheme is the latticebased cryptography. It has one aspect as post-quantum cryptography. For this reason, lattice-based protocols are one of the most important studies. Key exchange protocols [Pei14, BCNS15, ADPS16] and signature protocol [Lyu12] are proposed. Several
zero-knowledge proofs that can indicate the plaintext knowledge to a verifier have been
proposed [BCK+ 14, BDLN16, PR17].

1.1.3

Zero-knowledge proof

The third breakthrough is zero-knowledge proof. A prover having secret convinces averifier that the proposition on the secret is correct without any knowledge other thanbeing correct. Goldwasser et al. [GMR89] firstly formulated this method. The zeroknowledge proof satisfies the following three conditions:
Completeness. A prover can convince a verifier if the prover has a true secret.

1.2. CONTRIBUTIONS

3Soundness. If a cheating prover has no true secret, then the verifier can recognize that
it is false.
Zero-knowledge. A cheating verifier attempting to steal the secret from a prover cannot
obtain any knowledge other than ”the proposition is true.”

1.2

Contributions

Concerning blockchain, Bitcoin started operation in 2009. Technology has spread in
advance, and society is following behind. There are issues to be solved before we canwidely use blockchain in the real world. Throughput and privacy protection are significant
issues.
Let us describe privacy protection. There are many studies on the privacy-preserving
blockchain. Zhang et al. [ZXL19] classify seven characteristics as the characteristics ofprivacy: consistency, integrity, availability, prevention of double-spending, anonymity,
confidentiality, and unlinkability. Bitcoin has already realized the first five characteristics.
The other two are challenging. The first is the confidentiality of the transaction. That isthe privacy of the transaction content. In the distributed ledger, each participant needs toverify the contents. Considering naive, it becomes necessary to disclose the contents of thetransaction. However, this violates privacy protection. The other is the unlinkability oftransactions. That is identity-related privacy. The transaction links the payer and payee
typically. One can know the balance and trading frequency of the trader by analyzing
the links of transactions. Breaking the transaction link is necessary to protect privacy.
In the real world, blockchain not only keeps the contents secret but also is transparent.
That is two sides of the same coin. For blockchain widely used in the real world, we
believe blockchain needs to maintain the contents verifiable while keeping them private.
We propose these blockchains in Chapters 3 and 4.
Let us state throughput. For example, payment processing is limited to once every 10
minute with Bitcoin. This throughput is much lower than the performance of credit card
payments. If an open blockchain is unnecessary, one can adapt permissioned blockchain
to get high throughput. Permissioned blockchain deals with more transactions than permissionless blockchain. We realize privacy-preserving permissioned blockchain in Chapter
3. For high throughput in permissionless blockchain, probabilistic payment is promis-

4

CHAPTER 1. INTRODUCTION

ing. Probabilistic payment reduces transaction volume and realizes high throughput. We
achieve unlinkable and probabilistic payment in Chapter 5.
We show the overview of the contributions in Table 1.1. Chapter 3 achieves everything.
However, the achievement is limited to a permisssioned blockchain. Chapter 4 realizes
private and auditable permissionless blockchain. We focus on the first two in Chapter 4.
Moreover, we focus on the next two in Chapter 5. In principle, a combination of theseis a proposal that satisfies all. For blockchain widely used in the real world, we append
to factors such as public verifiability and improvement of throughput. In this thesis, westudy such privacy-preserving blockchain. We describe our contributions together with
our motivations and the related works in detail as follows.
Table 1.1: Overview of the contributions
Bitcoin
Chapter 3
Chapter 4
Chapter 5

1.2.1

public verifiability
yes
yes
yes
no

confidentiality
no
yes
yes
no

unlinkability
no
yes
no
yes

high throughput
no
yes
no
yes

Traceability in permissioned blockchain

Motivation. Processing transactions in the blockchain, we face low throughput andthe scalability problem. Since we solve the problems, there are off-chain technologies
that we can process transactions outside the blockchain (e.g., Lightning network [PD16]).
Sidechain is an off-chain technology that connects a permissioned blockchain and a permissionless blockchain at the same layer level. Dilly et al. [DPW+ 16] have proposed thistechnique connecting between Bitcoin and their permissioned blockchain Liquid. Using
this technology, we can transfer assets through a permissionless blockchain while enjoying
high throughput processing in a permissioned blockchain.
A permissioned blockchain is a black box to outsiders. Corporations often use a permissioned blockchain together with authorized participants. They also want to protect tradeprivacy by keeping their transaction information secret in commercial activities. However, they need to disclose various types of information to fulfill their social responsibility.
Transparency is vital for corporate activities. They must balance both trade privacy and1.2. CONTRIBUTIONS

5transparency. They need to share the contents of the permissioned blockchain with not
only participants but also outsiders.
Related work. Let us compare the contribution of our work with the concurrent works[DPW+ 16, PBF+ 19, BAZB20] in Table 1.2. We compare from the perspective of thefollowing three properties:
Trade privacy. Who trades with whom and at what asset amount.
Preservation. The total amount inside the permissioned blockchain, including deposits
and withdrawals to the permissionless blockchain, is stable.
Noninvolvement. Some members in the permissioned blockchain are not involved insome trades. One can prove that specified members performed the transaction.
The pool account to a permissionless blockchain is public in Dilly et al. [DPW+ 16].
There are no unauthorized deposits or withdrawals in this account. Thus, preservation
holds, although Dilly et al. do not specify this matter. Poelstra et al. [PBF+ 19] mention
that there is no unauthorized increase or decrease in coin history, and the number of coinstraded is concealed. However, the sender and receiver must be public. Zether [BAZB20] is
the work on remittance with anonymous accounts at Ethereum. Zether executes deposit
and withdrawal while preserving the whole balance. The balance between the sender andthe receiver and the transfer amount can be kept confidential. There is no defined way toindicate noninvolvement later. Dummy participants must be involved in the transaction
from the beginning. It is difficult for Zether to achieve noninvolvement and trade privacy
simultaneously.
Table 1.2: Properties’ comparison
Dilly et al. [DPW+ 16]
Poelstra et al. [PBF+ 19]
Zether [BAZB20]
Our work

Preservation
yes
yes
yes
yes

Noninvolvementnoyes
yes/noyes

Trade privacynonono/yesyesContribution. We have achieved privacy protection and high transparency in a permissioned blockchain. To improve transparency under privacy protection, we present
the traceability in the permissioned blockchain consisting of the three properties: trade

6

CHAPTER 1. INTRODUCTION

privacy, preservation, and noninvolvement. Our approach is as follows. We model the
traceability based on the hidden Markov model. Since the calculation of more thanquadratic degrees is necessary, we encrypt this model by homomorphic encryption. We
can construct an encrypted model by employing somewhat homomorphic encryption. The
zero-knowledge proof indicates the establishment of the original model. The proof is a
non-interactive zero-knowledge proof of the knowledge that the plaintext is equal to zero.
This is an adaptation of Benhamouda et al. [BCK+ 14].

1.2.2

Confidential and auditable payments

Motivation. Since Bitcoin makes transaction information public, Bitcoin is transparent. However, a bank typically keeps the user’s transaction information confidential. One
hopes that blockchain also keeps transaction information concealed. There are several
works realizing anonymity and confidentiality but do not have a forcibly auditable functionality. It is a problem that excessive confidentiality of transaction information may
cause money laundering.
Related work. There are several works realizing anonymity and confidentiality. Zerocoin [MGGR13] and Zerocash [SCG+ 14] are extensions based on Bitcoin. They realized strong anonymity and confidentiality by designing anonymous coins that skillfully
combined commitments. Zether [BAZB20] is an extension based on Ethereum. However, neither Zerocoin, Zerocash, nor Zether is forcibly auditable because of their strong
anonymity and confidentiality.
Contribution. We construct the confidential and auditable payments scheme. The
scheme allows a court or an authority to audit transactions while keeping the transaction
information confidential. The scheme eliminates concerns about money laundering andcontributes to the sound use of blockchain. Its characteristics are as follows.
• All the transactions are confidential by writing their ciphertexts in a ledger.
• The ownership and the transfer of it are provable by zero-knowledge proof. The
soundness of the zero-knowledge proof can realize the soundness of the scheme.
• A court or authority controls a unique secret key of the ciphertexts in the ledger.

1.2. CONTRIBUTIONS

7

They can enforce confidential transactions open with the secret key according to
the appropriate procedure.

1.2.3

Anonymous probabilistic payment in payment hub

Motivation. Privacy protection and scalability are significant problems with blockchain.
However, there are a few proposals to solve these problems at the same time.
Let us describe privacy protection. Bitcoin publicly records each person’s transaction
history on its distributed ledgers. Since all transactions are open, miners can verify if thedeals on the blockchain are correct. However, privacy is not protected. Many proposals
keep transactions confidential while maintaining the verifiability.
Let us explain scalability. It is costly to write all the small transactions into theblockchain. The payment of a small amount of money is called micropayment. For
micropayment, Wheeler [Whe97] and Rivest [Riv97] proposed a probabilistic payment
before blockchain appears. The probabilistic payment reduces costs for micropayment.
One pays an ordinary mount m with a certain probability p. One pays a small amount mp
as an expected value. By the probability p (e.g. p = 0.1 ∼ 0.001), one can reduce 1/p times
transactions. Micropay [Ps15], the DAM scheme [CGL+ 17] and Microcash [ABC20] haveproposed a new micropayment on the blockchain. Micropayment is attracting attention
as one of the leading solutions for scalability in the blockchain.

Related work. Let us confirm formerly anonymous cryptocurrencies. Zerocash [SCG+ 14]
is a famous anonymous cryptocurrency and is implemented as ZCash. Regarding ZCash,their group has proposed continuous researches such as BOLT [GM17] and DAM scheme[CGL+ 17]. Monero is also a famous anonymous cryptocurrency and is provided withincredible works [Noe15, SALY17, YSL+ 20, MSRL+ 19]. Next, let us confirm studies torealize anonymity for existing cryptocurrencies by using off-chain technology. TumbleBit[HAB+ 17] is compatible with Bitcoin. Zether [BAZB20] is compatible with Ethereum.
Wheeler [Whe97] and Rivest [Riv97] proposed a probabilistic payment. Micropay[Ps15] is compatible with Bitcoin. The DAM scheme, which is the extension of anonymous
ZCash, also realizes a probabilistic payment.
Bellare and Micali [BM90] and Bellare and Rivest [BR99] proposed the fractional
oblivious transfer based on the computational Diffie-Hellman assumption as the early

8

CHAPTER 1. INTRODUCTION

works. The DAM scheme also proposed a novel fractional oblivious transfer based on thedecisional Diffie-Hellman assumption as fractional message transfer [CGL+ 17, CGL+ 16].
( [CGL+ 16] is the full version of [CGL+ 17].)
Brakerski and Döttling proposed an oblivious transfer based on the LWE problem[BD18]. This work is the first oblivious transfer in the post-quantum cryptography. Liu
and Hu first proposed an efficient 1-out-of-2 oblivious transfer on the RLWE problem
and extends 1-out-of-n oblivious transfer [LH19]. To the best of our knowledge, we first
propose the fractional oblivious transfer over the ring.
Contribution. We propose an anonymous probabilistic payment. It aims to solve both
scalability and privacy protection. We realize the anonymity, which is ”k-anonymity in an
epoch.” TumbleBit [HAB+ 17] and their earlier work [HBG16] mentioned this definition.
Anonymity says that the link, which payer pays which payee via a tumbler within an
epoch, is broken. Even a tumbler never knows this link. The ”k” is the number ofparticipants trading via the tumbler. The epoch is the period during which transactions
are completed. Our proposal includes a probabilistic payment. One can reduce 1/p times
transactions, since one pays with a certain probability p (e.g. p = 0.1 ∼ 0.001). We
introduce a novel fractional oblivious transfer for a probabilistic payment. We call it
the ring fractional oblivious transfer since this is based on the RLWE encryption. The
functionality required for our proposal is the hashed time lock contract. This request is
general, not restricted to any particular cryptocurrency.

1.3

Organization

Let us present the organization in this thesis. In Chapter 2, we describe the building
blocks. We focus on RLWE encryption and zero-knowledge proof. In Chapter 3, we
describe the first work, titled ”Traceability in permissioned blockchain.” It realizes bothconfidentiality and transparency in the permissioned blockchain. We call this meaningful traceability. In Chapter 4, we state the second work, titled ”Confidential and auditable payments.” It realizes confidential and auditable payments in the permissionless
blockchain. In Chapter 5, we mention the third work, titled ”Anonymous probabilistic
payment in payment hub.” It realizes an anonymous probabilistic payment, introducing
a novel fractional oblivious transfer. In Chapter 6, we conclude this thesis.

Chapter 2
Building blocks
This chapter focuses on the ring learning with errors (RLWE) encryption and zeroknowledge proof.

2.1

Notation

Let N, Z, Q and R be the set of natural numbers, the set of integers, the set of rational
numbers and the set of real numbers, respectively. Let the finite field Zq = Z/qZ ={0, 1, . . . , q − 1}, where q is a prime number. Let Z[X] be the ring of polynomials overthe integers. Let Φl ∈ Z[X] be the l-th cyclotomic polynomial. We set l to a powerof 2. We have the cyclotomic polynomial Φl = X d + 1, where d = φ(l) and φ is theEuler function. Let the ring of integers R = Z[X]/hX d + 1i, and let Rq = Zq [X]/hX d +1i = Z[X]/hX d + 1, qi. Rq is the ring of integers R modulo q. We identify a vector(a0 , . . . , ad−1 ) ∈ Zd with a polynomial a0 + a1 X + · · · + ad−1 X d−1 ∈ R. We denote thenorms of a = a0 + a1 X + · · · + ad−1 X d−1 ∈ R as follows. |ai | is the absolute value of ai .
q
• l2 -norm |a| = a20 + a21 + · · · + a2d−1• l∞ -norm |a|∞ = max (|a0 |, |a1 |, . . . , |ad−1 |)If ∀c ∈ N, ∃nc such that ∀n > nc and f (n) < 1/nc , then we denote the function f as anegligible function negl(n). If an element a is sampled randomly from a distribution A or a$

uniform distribution over the set A, then we denote a ←− A with dollar sign. We denote the
Big O notation Õ(·), which is called Bachmann-Landau notation or asymptotic notation.
910

CHAPTER 2. BUILDING BLOCKS

We denote the ω notation ω(f (n)), which is an arbitrary function growing asymptoticallyfaster than f (n). We denote an oracle as O.

2.2

Ring learning with errors encryption

In this section, we introduce the definitions regarding the ring learning with errors (RLWE)
encryption.

2.2.1

Discrete Gaussian distribution

We describe the discrete Gaussian distribution.
1• ρdv,σ (x) = ( √2πσ)d e−|x−v|22σ 2is the continuous normal distribution over Rd centered at

v with standard deviation σ. If v = 0, then we write ρdv,σ as ρdσ .
d• Dv,σ(x) = ρdv,σ (x)/ρdσ (Zd ) is the discrete normal distribution over Zd centered atv ∈ Zd with standard deviation σ. The quantity ρdσ (Zd ) = Σz∈Zd ρdσ (z) is justa normalized quantity. It is necessary to express the function as a probability
distribution. We also mention that ∀v ∈ Zd , ρdv,σ (Zd ) = ρdσ (Zd ). The scaling factor
is the same for all v. If the dimension d is clear from the context, then we omit d
and write Dσd as Dσ . We also denote Dσ as χ.
We introduce the below lemma regarding the discrete Gaussian distribution.
√
Lemma 2.1 (Lemma 4.4 in [MR07]). Let d ∈ N. For any number σ > ω( log d), we
have√Pr [|x|∞ > σ d] ≤ 2−d+1 .
$
x←
−Dσ
$

Remark 2.1. According to Lemma 2.1, |x| ≤ B with overwhelming probability if x ←− Dσ .
B is a constant value.

2.2.2

Assumption

Let us present the problems over the ring as follows.
Definition 2.1 (Ring learning with errors (RLWEφ,q,χ ) problem). Let φ(X) ∈ Z[X] bea polynomial of degree d, let q ∈ Z be a prime integer, let χ denote a distribution over

2.2. RING LEARNING WITH ERRORS ENCRYPTION

11

the ring R = Z[X]/hφ(X)i, and let Rq = R/qR. The ring learning with errors problem
RLWEφ,q,χ is to distinguish between the following two distributions: (a, y) ∈ R2q such that
$

$

$

a←
− Rq , s, e ←− χ and y = as + e, and (a, y) ←− R2q .
The RLWE assumption indicates that the RLWE problem is hard for any probabilistic
polynomial time (PPT) algorithm. The RLWE assumption still holds even if we choose
the secret s according to the error distribution Dσ rather than uniformly [LPR13].
Definition 2.2 (Decisional small polynomial ratio (DSPRφ,q,χ ) problem (Definition 3.4
in [LATV12])). Let φ(X) ∈ Z[X] be a polynomial of degree d, let q ∈ Z be a prime integer, and let χ denote a distribution over the ring R = Z[X]/hφ(X)i. The decisional
small polynomial ratio problem DSPRφ,q,χ is to distinguish between the following two distributions: a polynomial h = g/f , where f and g are sampled from the distribution χ$(conditioned on f being invertible over Rq = R/qR), and a polynomial h ←− Rq .
According to [LATV12], let us explain a standard deviation of the discrete Gaussian
distribution Dσ and DSPR assumption. It is known that the DSPR problem is hard if
the standard deviation is significant. For the calculation using homomorphic encryption,
we want to take a small one. In this case, it is assumed that the DSPR problem is still
hard. This assumption is called the DSPR assumption.

2.2.3

RLWE encryption and its syntax

Now we introduce Brakerski-Vaikuntanathan (BV) scheme [BV11]. We describe plaintext
space, key generation, encryption and decryption as follows.
• The plaintext space M = Rp = Z[X]/hX d + 1, pi.
$$• To generate key, a, s ←− Rq , es ←− Dσ , b = as + es , where (a, b) is a public key ands is a secret key.
$

• To encrypt a plaintext m ∈ M, choose a set of randomness v, e, f ←− Dσ , andcompute the ciphertext c = (c1 , c2 ) = (bv + pe + m, av + pf ) ∈ C.
• To decrypt c = (c1 , c2 ) with secret key s and obtain a plaintext m, compute m =(c1 − s · c2 mod q) mod p.
We also introduce the syntax of the RLWE scheme as follows.

12

CHAPTER 2. BUILDING BLOCKS

Definition 2.3 (Syntax of the RLWE scheme (Definition 6 in [BKS19])). We describe
the RLWE scheme represented by a tuple of probabilistic polynomial time 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 secret key sk
and a ciphertext c ∈ C.
Definition 2.4 (Pseudorandomness of ciphertexts (Definition 7 in [BKS19])). We say a
RLWE scheme RLWE := (RLWE.Gen, RLWE.Enc, RLWE.Dec) satisfies pseudorandomnessof ciphertexts or simply RLWE is secure, if for every PPT adversary 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.1.
Exppr
RLWE,A (λ) :λ(pk, sk) ← RLWE.Gen(1 )β ← {0, 1}
β 0 ← AORLWE.Enc (·) (1λ , pk)
if β = β 0 return 1
else return 0

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

Figure 2.1: Security challenge experiment for pseudorandomness of ciphertexts.

Remark 2.2. The randomness (that is, ”noise”) in the ciphertext increases with theaddition and multiplication. For noise growth, multiplication is more remarkable thanaddition. To reduce the increasing noise, one can apply the processing called bootstrapping. However, this is costly. Homomorphic encryption without the bootstrapping is calledsomewhat homomorphic encryption.

2.3. ZERO-KNOWLEDGE PROOF

2.3

13

Zero-knowledge proof

In this section, we present the zero-knowledge proofs of knowledge for RLWE encryption.

2.3.1

Pedersen commitments

Let us introduce Pedersen commitments [Ped92]. Given a family of prime order groups{G(λ)}λ∈N such that the discrete logarithm problem is hard in G(λ) with security parameter λ, let q̃ = q̃(λ) be the order of G = G(λ). We denote all elements with order q̃ witha tilde in the following. We write the group G(λ) additively.
$• CSetup: This algorithm chooses g̃, h̃ ←− G and outputs cpars = (g̃, h̃).
$• Commit: To commit to a message m ∈ Zq̃ , it first chooses r ←− Zq̃ . It then outputs
a pair (cgmt, o) = (mg̃ + rh̃, r).
• COpen: Given a commitment cg
mt, an opening o, a public key cpars and a message?

m, it outputs accept if and only if (cgmt, o) = (mg̃ + rh̃, r).
Lemma 2.2 (Theorem 2.1. in [BCK+ 14]). Under the discrete logarithm assumption forG, the given commitment scheme is perfectly hiding and is computationally binding.
In this chapter’s protocols, we make use of the above scheme as an auxiliary commitment scheme. We denote it as (aCSetup, aCCommit, aCOpen).

2.3.2

Rejection sampling

To realize zero-knowledge proof, the technique of rejection sampling is useful [Lyu09,
Lyu12]. The technique can conceal the information of witness. Therefore, we apply thetechnique when a prover sends the response to a verifier.
Lemma 2.3 (Theorem 4.6 in [Lyu12]). Let V be a subset of Zm in which all elements have√norms less than T , σ be some element in R such that σ = ω(T log m), and h : V → R
be a probability distribution. Then, there exists a constant M = Õ(1) such that the
distribution of the following algorithm A:$

1. v ←−h$m
2. z ←− Dv,σ14

CHAPTER 2. BUILDING BLOCKSm

3. output (z, v) with probability min( MDDσm(z)(z) , 1)v,σ−ω(log m)

is within statistical distance 2

Mof the distribution of the following algorithm F:$

1. v ←−h$2. z ←− Dσm
3. output (z, v) with probability 1/M−ω(log m)

Moreover, the probability that A outputs something is at least 1−2 M. More con-2

cretely, if σ = αT for any positive α, then M = e12/α+1/(2α ) , the output of algorithm A−100

is within statistical distance 2 M−100

something is at least 1−2M

2.3.3

of the output of F, and the probability that A outputs.

Definition

We describe the formal definition of the Σ0 -protocol, the protocol and its theorem proving
this relationship.
Definition 2.5 (Definition 2.5. in [BCK+ 14] ). Let (P, V ) be a two-party protocol, where
V is a probabilistic polynomial time algorithim, and let L, L0 ⊆ {0, 1}∗ be languages withwitness 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 challenge c ←− 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 the verifier accepts the protocol run.
• Completeness: Whenever (x, w) ∈ R, the verifier V accepts with probability at least
1 − α. α is the completeness error.
• Special soundness: There exists a PPT algorithm E (the knowledge extractor) thattakes two accepting transcripts (t, c0 , s0 ), (t, c00 , s00 ) satisfying c0 6= c00 as inputs, andoutputs w0 such that (x, w0 ) ∈ R0 . The knowledge error denotes the probability thatthe verifier accepts the proof even if the prover does not know a witness.

2.3. ZERO-KNOWLEDGE PROOF

15• Special honest verifier zero-knowledge (HVZK): There exists a PPT algorithm S (thesimulator) taking x ∈ L and c ∈ C as inputs. Moreover, the simulator outputs (t, s)
so that the triple (t, c, s) is indistinguishable from an accepting protocol transcript
generated by a real protocol run.
Moreover, let us present the following useful property.
• High-entropy commitments: For all (y, w) ∈ R and for all t, the probability that anhonestly generated commitment by P takes on the value t is negligible.

2.3.4

Relation for the key generation

We want to show that we know a public key’s private key without revealing the private
key itself. We introduce the zero-knowledge proof for the purpose in this subsection. Let
us confirm Theorem 3.3. in [BCK+ 14].
Lemma 2.4 (Theorem 3.3. in [BCK+ 14]). The protocol in Fig. 2.2 is an HVZK Σ0 protocol for the following relations:√
R = {((a, y), (s, e)) : y = as + e ∧ |s|, |e| ≤ Õ( dα)}R0 = {((a, y), (s, e)) : 2y = 2as + 2e ∧ |2s|, |2e| ≤ Õ(d2 α)}
where 2s and 2e are reduced modulo q. The protocol has a knowledge error of 1/(2d), a
completeness error of 1 − 1/M , and high-entropy commitments.
We can use Lemma 2.4 for the below relation RK by replacing y → y/p, a → a/p.
√
RK = {((a, y), (s, e)) | y = as + 2e ∧ |s|, |e| ≤ Õ( dα)}Let us describe the non-interactive zero-knowledge proof for the relation RK . The protocol in Fig. 2.2 realizes the zero-knowledge proof for the relation RK . Moreover, we canobtain the non-interactive zero-knowledge proof by using Fiat-Shamir transform [FS87]
and running the protocol in parallel. Let us confirm the simulator for the relation RK .
The technique of rejection sampling is used for zero-knowledge in the protocol. According
to Lemma 2.3, the algorithm F includes no witness and is statistically indistinguishable
from the algorithm A. We can implement the simulator for RK by replacing the algorithm
A with the algorithm F.

16

CHAPTER 2. BUILDING BLOCKS
Common input: the open value (a, y)√
Relation: R = {((a, y), (s, e)) : y = as + e ∧ |s|, |e| ≤ Õ( dα)}
ProverVerifier$

rs , re ←− DÕ(√dα)
t = ars + re(caux , daux ) = aCommit(t)
c

aux
−−
→

$

c←
− C = {0, . . . , 2d − 1}c←−ss = rs + X c s
se = re + X c e
accept with probabilityDÕ(√2dα) ((se ,ss ))M D(X c e,X c s),Õ(√2dα) ((se ,ss ))t,daux ,(ss ,se )−−−−−−−→?

X c y + t = ass + se?
aCOpen(t, caux , daux ) = accept|ss |, |se | ≤ Õ(dα)
Figure 2.2: Zero-knowledge proof of knowledge of RLWE secrets s, e such that y = as + e(Protocol 3.2. in [BCK+ 14])

2.3.5

Relation for the ciphertext of zero

We want to show that we know that a given ciphertext’s plaintext is zero without decryption or revealing randomness of the ciphertext. We introduce the zero-knowledge proof
for the purpose in this subsection. We introduce the following technical lemmas.
Lemma 2.5 (Lemma 3.1 in [BCK+ 14]). Let d be a power of 2 and let 0 < i, j < 2d − 1.
Then, 2(X i − X j )−1

mod (X d + 1) only has coefficients in {−1, 0, 1}.

Lemma 2.6 (Lemma 2 in [ZZD+ 15]). For any s, t ∈ R, we have |s · t| ≤√d · |s| · |t| and|s · t|∞ ≤ d · |s|∞ · |t|∞ .
We show a non-interactive zero-knowledge proof for ciphertext of zero in Fig. 2.3. h
is a cryptographic hash function. We make the interactive proof non-interactive by using
the Fiat-Shamir heuristic [FS87]. This protocol satisfies Lemma 2.7. The parallel protocol
satisfies Theorem 2.1.
Lemma 2.7 (Lemma 5 in [MO20c]). The protocol in Fig. 2.3 is an HVZK Σ0 -protocol

2.3. ZERO-KNOWLEDGE PROOF

17

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̃( dα)}
ProverVerifier$

rv , re , rf ←− DÕ(√dα)
t1 = brv + ret2 = arv + rf
(1)
(1)
(caux , daux ) = aCommit(t1 )(2)(2)(caux , daux ) = aCommit(t2 )
(1)

(2)

caux ,caux−−−−−→
(1)
(1)
(2)
(2)
c = h(t1 , t2 , caux , daux , caux , daux )s v = rv + X c v
se = re + X c pe
sf = rf + X c pf
accept with probabilityDÕ(√3dα) ((sv ,se ,sf ))M D(X c v,X c e,X c f ),Õ(√3dα) ((sv ,se ,sf ))
(1)

(2)

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̃(dα)
Figure 2.3: Non-interactive zero-knowledge proof of a ciphertext of zero regarding RLWE
encryption (Figure 3 in [MO20c])

18

CHAPTER 2. BUILDING BLOCKS

for the following relations:√
R0 = {((c1 , c2 ), (v, e, f )) : (c1 , c2 ) = (bv + pe, av + pf ) ∧ |v|, |e|, |f | ≤ Õ( dα)}R00 = {((c1 , c2 ), (v, e, f )) : (2c1 , 2c2 ) = (2bv + 2pe, 2av + 2pf )∧ |2v|, |2e|, |2f | ≤ Õ(d2 α)}
where 2v, 2e and 2f are reduced modulo q. The protocol has a knowledge error of 1/(2d),a completeness error of 1 − 1/M , and high-entropy commitments.
Proof. We discuss the proof from the following points: completeness, honest verifier zeroknowledge, special soundness, and high-entropy commitments.
Completeness. From Lemma 2.3 of the rejection sampling, a prover responds with aprobability 1/M . If the prover does not abort, thenbsv + se = b(rv + X c v) + (re + X c pe)= X c (bv + pe) + (brv + re )= X c c1 + t1
andasv + sf = a(rv + X c v) + (rf + X c pf )= X c (av + pf ) + (arv + rf )= X c c2 + t 2
Regarding the norms, we obtain|sv | ≤ |rv | + |v| ≤ Õ(dα)|se | ≤ |re | + |e| ≤ Õ(dα)|sf | ≤ |rf | + |f | ≤ Õ(dα)√
with overwhelming probability, since the standard deviations of rv , re , rf are Õ( dα).
Honest verifier zero-knowledge. The challenge value c is randomly chosen from theset C = {0, . . . , 2d − 1}. The simulator outputs the tuple (aCommit(0), c, ⊥) with the2.3. ZERO-KNOWLEDGE PROOF

19

probability 1 − 1/M . With the probability 1/M , the simulator runs as follows.
$

rv , re , rf ←− DÕ(√dα)
t1 = brv + re − X c c1
t2 = arv + rf − X c c2
(1)
(c(1)
aux , daux ) = aCommit(t1 )
(2)
(c(2)
aux , daux ) = aCommit(t2 )Finally, the simulator outputs
(2)
(2)
(1)
(c(1)
aux , caux , c, t1 , t2 , daux , daux , (sv , se , sf )).

From Lemma 2.3, the outputs sv , se and sf without abort do not depend on v, e and fas the witness. Therefore, the simulator and the actual protocol are indistinguishable. If
the protocol aborts, then it is indistinguishable because of the hiding property of aCommit
in Lemma 2.2. For any c, an abort occurs in the same way.

Special soundness. We suppose that both
0

0

00

00

(2)
0 0 0
(1)
(2)
0
0
0
(c(1)
aux , caux , c , t1 , t2 , daux , daux , (sv , se , sf ))and(2)00 00 00 (1)(2)
00 00 00(c(1)
aux , caux , c , t1 , t2 , daux , daux , (sv , se , sf ))pass the verification by the verifier. From the binding property of the auxiliary commitment scheme in Lemma 2.2, we obtain t1 := t01 = t001 and t2 := t02 = t002 . We can havea similar discussion with regard to t1 and t2 . Let us confirm t1 . From the verification
equation, we have0

X c c1 + t1 = bs0v + s0e00

X c c1 + t1 = bs00v + s00e .

20

CHAPTER 2. BUILDING BLOCKS

From the subtraction between these two equations, we obtain
000(X c − X c )c1 = b(s0v − s00v ) + (s0e − s00e ).
000Multiplying by 2(X c − X c )−1 to the equation,
2c1 = b2(s0v − s00v )2(s0e − s00e )+=: 2bv̂ + 2ê.
X c0 − X c00 X c0 − X c00

Therefore, we obtain|2v̂| ≤ |s0v − s00v | ·√d·2
X c0 − X c00≤ Õ(d2 α).

where we had the second inequality applying Lemma 2.5 and 2.6. A similar discussion
holds for ê. We also have|2ê| ≤ |s0e − s00e | ·

√

d·

2
X c0 − X c00≤ Õ(d2 α).

In addition, dealing with the verification equation regarding t2 in a similar way of t1 ,we obtain2(s0v − s00v ) 2(s0f − s00f )+=: 2av̂ + 2fˆ.
2c2 = a c0
X − X c00 X c0 − X c00

In the same way, we obtain|2fˆ| ≤ |s0f − s00f | ·

√

d·

2
≤ Õ(d2 α).
00
c
X −X
c0

High-entropy commitments. This property directly follows from the security of theauxiliary commitment scheme.
Theorem 2.1 (Theorem 6 in [MO20c]). Let us apply the protocol in Fig. 2.3 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 completeness error and knowledge errorof negl(λ) under the condition d ≥ 2M .
(1)

(2)

Proof. In the parallel protocol, λ commitments {caux , caux }1,...,λ are sent to a verifier. We
confirm the probability that at least λ/2M out of λ proofs are valid. Each execution in2.3. ZERO-KNOWLEDGE PROOF

21

the parallel protocol is independent. It is a Bernoulli trial. We introduce the lemma of
Chernoff bounds as follows.

Lemma 2.8 (Chernoff bounds (see e.g., Theorem 4.4, 4.5 in [MU17])). Let x1 , . . . , xλ be
independent Bernoulli-distributed random variables with Pr[xi = 1] = p and Pr[xi = 0] =P
1 − p; then, for X := λi=1 xi and µ := λp,
2

Pr[X ≤ (1 − δ)µ] ≤ e−δ µ/2 , 0 < δ ≤ 1
2

Pr[X ≥ (1 + δ)µ] ≤ e−δ µ/3 , 0 < δ ≤ 1
Pr[X ≥ (1 + δ)µ] ≤ e−δµ/3 , 1 ≤ δ
hold.

First, we confirm a completeness error. From Lemma 2.7, a prover sends proof with aprobability 1/M for each time. Applying first and second inequalities of Chernoff bounds
under the condition that p = 1/M, µ = λp = λ/M and δ = 2/3,
Pr[(1 − δ)µ < X < (1 + δ)µ]= 1 − Pr[X ≤ (1 − δ)µ] − Pr[X ≥ (1 + δ)µ]2

2

≥ 1 − (e−δ µ/2 + e−δ µ/3 )= 1 − (e−2λ/9M + e−4λ/27M )Since λ/2M = µ/2 ∈ ((1 − δ)µ, (1 + δ)µ) = (µ/3, 5µ/3), λ/2M proofs are made andaccepted with overwhelming probability. Therefore, the completeness error is negl(λ).
Second, we confirm a knowledge error. From Lemma 2.7, a knowledge error is 1/2d foreach time. Let p = 1/2d, µ = λp = λ/2d and δ = d/M −1 ≥ 1 such that (1+δ)µ = λ/2M .
Applying the third inequalities of Chernoff bounds,
Pr[X ≥ (1 + δ)µ] ≤ e−δµ/3= e−λ/6M +1/3
Therefore, the knowledge error is negl(λ).

22

2.3.6

CHAPTER 2. BUILDING BLOCKS

Relation for valid ciphertext

We want to show that we know that a given ciphertext is valid without decryption or
revealing a ciphertext’s message and randomness. We introduce the zero-knowledge proof
for the purpose in this subsection. Let us introduce the relation RE as follows. In therelation RE , let a message space M = R2 .
RE = {((c1 , c2 , a, y), (m, v, e, f )) | c1 = yv + 2e + m ∧ c2 = av + 2f√
∧ |m|∞ ≤ 1 ∧ |v|, |e|, |f | ≤ Õ( dα)}
We construct a non-interactive zero-knowledge proof for the RLWE ciphertext, referringto Protocol 4.1 and Theorem 4.2 in [BCK+ 14]. We present the protocol in Fig. 2.4.
This protocol in Fig. 2.4 satisfies Lemma 2.9. We can make the completeness error andknowledge error in Lemma 2.9 negligible, by the parallelization as Theorem 2.1. Let us
explain the notation al . One obtains a by an anti-cyclic shift a vector a by l. That is,al = aX l ∈ R. If we write the elements of the vector explicitly, we haveal = (a0 , . . . , ad−1 )l = (−ad−l , . . . , −ad−1 , a0 , . . . , ad−l−1 ).

Lemma 2.9. The protocol in Fig. 2.4 is an honest verifier zero-knowledge Σ0 -protocol forthe following relations:d−1
R = {((c1 , c2 , g̃, h̃, (cgmti )d−1
i=0 , p, a, b), (m, v, e, f, (ri )i=0 )) :(c1 , c2 ) = (bv + pe + m, av + pf ) ∧
√

d−1
^

cg
mti = rm,i g̃ + rr,i h̃

i=0∧ |m|∞ ≤ 1 ∧ |v|, |e|, |f | ≤ Õ( dα)}d−1R0 = {((c1 , c2 , g̃, h̃, (cgmti )d−1
i=0 , p, a, b), (m, v, e, f, (ri )i=0 )) :(2c1 , 2c2 ) = (2bv + 2pe + 2m, 2av + 2pf ) ∧

d−1
^

2cg
mti = (2m mod q)i g̃ + 2rr,i h̃

i=0∧ |2m| ≤ 2d2 ∧ |2v|, |2e|, |2f | ≤ Õ(d2 α)}
where 2v, 2e and 2f are reduced modulo q and (2m mod q)i is the i-coefficient of 2m ∈ Rq .
The protocol has a knowledge error of 1/(2d), a completeness error of 1 − 1/M , and high-2.3. ZERO-KNOWLEDGE PROOF

23

Common input: the ciphertext (c1 , c2 ), the integer p, the public key (a, b),
the public key of commitment (g̃, h̃), the commitment (cgmti )d−1
i=0
d−1
d−1
Relation R = {((c1 , c2 , g̃, h̃, (cgmti )i=0 , p, a, b), (m, v, e, f, (ri )i=0 )) :Vd−1g(c1 , c2 ) = (bv + pe + m, av + pf)∧
i=0 cmti = rm,i g̃ + rr,i h̃√∧|m|∞ ≤ 1 ∧ |v|, |e|, |f | ≤ Õ( dα)}
ProverVerifier$

rv , re , rf ←− DÕ(√dα)$

rm ←− DÕ(√d)$

rr,i ←− Zq̃ for i = 0, . . . , d − 1
t1 = brv + pre + rm
t2 = arv + prft̃i = rm,i g̃ + rr,i h̃ for i = 0, . . . , d − 1(caux , daux ) = aCommit(t1 , t2 , (t̃i )d−1
i=0 )
c

aux
−−−−
−−→

c = h(t1 , t2 , (t̃i )d−1
i=0 , caux , daux )sv = rv + X c v
se = re + X c e
s f = rf + X c f
sm = rm + X c m
sr = rr + X c r
accept with probabilityDÕ(2√dα) ((sv ,se ,sf ,sm ))M D(X c v,X c e,X c f,X c m),Õ(2√dα) ((sv ,se ,sf ,sm ))t1 ,t2 ,(t̃i )d−1 ,daux ,(sv ,se ,sf ,sm ,sr )−−−−−−i=0−−−−−−−−−−−−−→d−1
c = h(t1 , t2 , (t̃i )i=0
, caux , daux )?
c
X c1 + t1 = bsv + pse + sm?
X c c2 + t2 = asv + psf?
(cg
mt0 , . . . , cg
mtd−1 )c + (t̃0 , . . . , t̃d−1 ) = sm g̃ + sr h̃?
d−1
aCOpen((t1 , t2 , (t̃i )i=0), caux , daux ) = accept|sv |, |se |, |sf | ≤ Õ(dα)|sm | ≤ Õ(d)Figure 2.4: Non-interactive zero-knowledge proof of plaintext knowledge regarding RLWE
encryption

24

CHAPTER 2. BUILDING BLOCKS

entropy commitments.
Proof. Let us confirm the proof from the following points: completeness, honest verifierzero-knowledge, special soundness, and high-entropy commitments.
Completeness. From Lemma 2.3 of the rejection sampling, a prover responds with aprobability 1/M . If the prover does not abort, thenbsv + pse + sm = b(rv + X c v) + p(re + X c e) + (rm + X c m)
= X c (bv + pe + m) + (brv + pre + rm )= X c c1 + t1
andasv + psf = a(rv + X c v) + p(rf + X c f )= X c (av + pf ) + (arv + prf )= X c c2 + t2 .
Let us confirm the equation of the commitment?

(cg
mt0 , . . . , cg
mtd−1 )c + (t̃0 , . . . , t̃d−1 ) = sm g̃ + sr h̃.
Let us expand the first term of the left hand side.
(cg
mt0 , . . . , cg
mtd−1 )c = (m0 g̃ + r0 h̃, . . . , md−1 g̃ + rd−1 h̃)c= (m0 , . . . , md−1 )c g̃ + (r0 , . . . , rd−1 )c h̃
= X c mg̃ + X c rh̃

We also expand the second term of the left hand side.
(t̃0 , . . . , t̃d−1 ) = (rm,0 g̃ + rr,0 h̃, . . . , rm,d−1 g̃ + rr,d−1 h̃)= (rm,0 , . . . , rm,d−1 )g̃ + (rr,0 , . . . , rr,d−1 )h̃= rm g̃ + rr h̃2.3. ZERO-KNOWLEDGE PROOF

25

Therefore we have(cg
mt0 , . . . , cg
mtd−1 )c + (t̃0 , . . . , t̃d−1 ) = (X c mg̃ + X c rh̃) + (rm g̃ + rr h̃)= (rm + X c m)g̃ + (rr + X c r)h̃= sm g̃ + sr h̃.

Let us confirm the norms of sv , se , sf and sm . The standard deviations of rv , re , rf are√√Õ( dα). Also, the standard deviations of rm is Õ( d). We have|sv | ≤ |rv | + |v| ≤ Õ(dα)|se | ≤ |re | + |e| ≤ Õ(dα)|sf | ≤ |rf | + |f | ≤ Õ(dα)|sm | ≤ |rm | + |m| ≤ Õ(d)with the overwhelming probability.
Honest verifier zero-knowledge. A challenge value c is randomly chosen from the set
C = {0, . . . , 2d−1}. A simulator outputs the tuple (aCommit(0), c, ⊥) with the probability
1 − 1/M . With the probability 1/M , the simulator runs as follows.
$

rv , re , rf ←− DÕ(√dα)$

rm ←− DÕ(√d)
t1 = brv + pre + rm − X c c1
t2 = arv + prf − X c c2t̃i = rm,i g̃ + rr,i h̃ for i = 0, . . . , d − 1(caux , daux ) = aCommit(t1 , t2 , (t̃i )d−1
i=0 )Finally, the simulator outputs(caux , daux , c, t1 , t2 , (t̃i )d−1
i=0 , (sv , se , sf , sm )).
From Lemma 2.3, the outputs sv , se , sf and sm without abort do not depend on v, e, f andm as the witness. Therefore, the simulator and the actual protocol are indistinguishable. If

26

CHAPTER 2. BUILDING BLOCKS

the protocol aborts, then it is indistinguishable because of the hiding property of aCommit.
For any c, the abort occurs in the same way.
Special soundness. Let us consider knowledge extractor and suppose that both
0
0
0
0
0
(caux , d0aux , c0 , t01 , t02 , (t̃0i )d−1
i=0 , (sv , se , sf , sm , sr ))and00 00 00 00
00(caux , d00aux , c00 , t001 , t002 , (t̃00i )d−1
i=0 , (sv , se , sf , sm , sr ))pass the verification by the verifier. From the binding property of aCommit, we have
0 d−1
00 d−1t1 := t01 = t001 , t2 := t02 = t002 , (t̃i )d−1
i=0 := (t̃i )i=0 = (t̃i )i=0 .

Let us confirm (t̃i )d−1
i=0 . From the verification, we have(cg
mt0 , . . . , cg
mtd−1 )c0 + (t̃0 , . . . , t̃d−1 ) = s0m g̃ + s0r h̃(cg
mt0 , . . . , cg
mtd−1 )c00 + (t̃0 , . . . , t̃d−1 ) = s00m g̃ + s00r h̃.
From the subtraction between these two equations, we have
000(cg
mt0 , . . . , cg
mtd−1 )(X c − X c ) = (s0m − s00m )g̃ + (s0r − s00r )h̃.

000

Multiplying by 2(X c − X c )−1 to this equation, we have(cg
mt0 , . . . , cg
mtd−1 ) =2(s0r − s00r )2(s0m − s00m )g̃+h̃ =: 2m̂g̃ + 2r̂h̃.
X c0 − X c00
X c0 − X c00

Then, let us confirm the upper bound of the norm |2m̂|. By adopting Lemma 2.5 and 2.6,
and the triangle inequality |a ± b| ≤ |a| + |b|, we have|2m̂| ≤≤√

d · |s0m − s00m | ·2
X c0 − X c00√√
d · |s0m − s00m | · d≤ d(|s0m | + |s00m |) = 2d2 .

We can have a similar discussion with regard to t1 and t2 . Let us confirm t1 . From

2.3. ZERO-KNOWLEDGE PROOF

27

the verification equation, we have0

X c c1 + t1 = bs0v + ps0e + m000

X c c1 + t1 = bs00v + ps00e + m00 .
From the subtraction between these two equations, we obtain
000(X c − X c )c1 = b(s0v − s00v ) + p(s0e − s00e ) + (m0 − m00 ).
000

Multiplying by 2(X c − X c )−1 to the equation,
2c1 = b2(s0v − s00v )2(s0e − s00e ) 2(s0m − s00m )+p+ c0=: 2bv̂ + 2pê + 2m̂.
000
Xc − Xc
X c0 − X c00
X − X c00

From the similar discussion in the upper bound of |2m̂|, we obtain|2v̂| ≤√

d · |s0v − s00v | ·2
X c0 − X c00≤ d(|s0v | + |s00v |)≤ Õ(d2 α).
Since a similar discussion also holds for ê, we have |2ê| ≤ Õ(d2 α).
In addition, dealing with the verification equation regarding t2 in a similar way of t1 ,we obtain2(s0f − s00f )2(s0v − s00v )2c2 = a c0
+ p c0=: 2av̂ + 2pfˆ.
X − X c00
X − X c00

In the same way, we obtain |2fˆ| ≤ Õ(d2 α).
High-entropy commitments. This property directly follows from the security of theauxiliary commitment scheme.

28

CHAPTER 2. BUILDING BLOCKSChapter 3
Traceability in permissioned
blockchain
This chapter is based on the below works with Akira Otsuka.
[MO19] T. Mitani and A. Otsuka, ”Traceability in Permissioned Blockchain,” in 2019
IEEE International Conference on Blockchain, Atlanta, GA, USA, 2019, pp. 286293.
[MO20c] T. Mitani and A. Otsuka, ”Traceability in Permissioned Blockchain,” in IEEE
Access, vol. 8, pp. 21573-21588, 2020. (the extended version of [MO19])

3.1

Introduction

Blockchain attracts attention in commercial activities. It is useful in various situations
such as trade finance, fund procurement, contract management and execution, and supply
chain management. In commercial activities, corporations want to protect trade privacy
by keeping it secret. Therefore, they often use permissioned blockchain with authorizedparticipants. On the other hand, they disclose various types of information in order tofulfill their social responsibilities. For example, transparency of accounting is necessary
for proper tax payment and information provision to investors. Tracking objects in supply
chain management is also essential. Transparency is vital for corporate activities.
In this way, using blockchain in corporate activities, it is crucial to balance tradeprivacy and transparency. We request the traceability to balance these two properties.
29

30

CHAPTER 3. TRACEABILITY IN PERMISSIONED BLOCKCHAIN

First, we pay attention to trade privacy. The transaction information, including priceand volume, is closely related to corporate activities. A bank generally handles accountbalances and transaction information as a secret since these are client privacy information.
It is natural for the permissioned blockchain to handle the transaction information as asecret to an external party. Then, under the protection of the trade privacy, we consider
two properties that consist of transparency. We note that the transparency holds obviously
if all transactions are public.
Preservation. An outsider can verify that there is no dishonest increase and decrease
inside the permissioned blockchain.
Noninvolvement. If there is a defect in the traded goods, the permissioned blockchain
can disclose the participants who participated in the trade as needed later.
How can we balance trade privacy and transparency for any outsiders other thanparticipants? We model traceability based on the hidden Markov model. We encrypt
this model by homomorphic encryption. The proof of traceability requires the calculationof more than quadratic degrees. The establishment of the original model is verifiable byapplying the non-interactive zero-knowledge proof of the knowledge that the plaintext is
equal to zero.
Our result
This work provides the basic technology to achieve meaningful traceability in the blockchainthat balances transactions’ privacy and transparency. Let us describe the overview, threat
model, and scenario regarding our result.
Overview
In our solution, we model the trading dynamics in the permissioned blockchain. We
realize trade privacy by encrypting this model with fully homomorphic encryption. We
also realize the transparency by proving the encrypted model equations with the zeroknowledge proof of plaintext knowledge. The calculations for traceability require morethan quadratic degrees. Since it is not 2-DNF, we cannot use the traditional method[BGN05]. Therefore, we use fully homomorphic encryption. Furthermore, we adapt thework of Benhamouda et al. in Asiacrypt 2014 [BCK+ 14]. We prove the encrypted model’s

3.1. INTRODUCTION

31

establishment by the zero-knowledge proof of knowledge in which plaintext is zero. We
introduce the three properties of traceability concretely as follows.
Trade privacy Trade privacy is privacy regarding who trades with whom and at what
asset amount in the permissioned blockchain. We denote ~x(t), ~u(t) and ~y (t) as avector of the participants’ states in the permissioned blockchain, a vector of inputs
and outputs in the permissioned blockchain, respectively. Let A(t), B(t) and C(t) bematrices of the ”distribution ratios”. ~x(t), A(t), B(t) and C(t) indicate who tradeswith whom and at what asset amount. These are private information. ~u(t) and~y (t) are public information. We express the following equations as a hidden Markov
model.
~x(t + 1) = ~x(t)A(t) + ~u(t)B(t)~y (t + 1) = ~x(t)C(t)Moreover, we mention the security of trade privacy. To protect the trade privacy,
the private information A(t), B(t), C(t) and ~x must be in hiding. Secure tradeprivacy means that no probabilistic polynomial time algorithm can distinguish if
the distribution ratios A(t), B(t), C(t) and the internal state ~x(t) were encryptedwith honest plaintexts or just zeros (false plaintexts). As the A(t), B(t), C(t) and~x(t) must be private information, this definition makes sense.
Transparency Transparency consists of preservation and noninvolvement.
Preservation the total amount of assets in the blockchain, including input andoutput, is immutable. That is,
mpX

xi (t + 1) +

i=1

np
X
i=1

yi (t + 1) =

mp
X
i=1

xi (t) +lp
Xui (t)

i=1

under the condition that
mp
X
j=1

aij +

np
X

cij = 1, for i = {1, 2, . . . , mp }

j=1
mp

X
j=1

bij = 1, for i = {1, 2, . . . , lp }

32

CHAPTER 3. TRACEABILITY IN PERMISSIONED BLOCKCHAIN
Noninvolvement One can reveal that some blockchain participants were not involved in a series of transactions. For some participant i,
aij = cij = 0, for all j 6= i,aji = cji = 0, for all j 6= i,
bji = 0, for all j.

We encrypt all the above equations with the RLWE encryption. The fact that f (x) = y
holds in plaintext means that the ciphertext of f (x) − y is a ciphertext of zero. We
suppose that a prover is a permissioned blockchain, and a verifier is a permissionless
blockchain. The permissioned blockchain shows that the model is correct to the permissionless blockchain while concealing the plaintexts.

Threat model
We assume an adversary outside the blockchain as a threat. Our solution protects theprivacy of the blockchain inside information from an actively external adversary. They
can intervene in transactions between the permissioned blockchain and the permissionless
blockchain. Their ability is computationally limited. Their goal is to break the tradeprivacy and create fake transactions and proofs. We also suppose the universal composable security [Can01]. On the other hand, we assume that the permissioned blockchain
participants are reliable as honest insiders, and the adversary cannot corrupt them. It
is why the distributed ledger of the permissioned blockchain contains the content thatparticipants want to keep secret from outside third parties. Participants trust each otherand share the secret in the permissioned blockchain.

Scenario
People trade agricultural and fishery products worldwide. To prevent the falsification oftransaction tracking, the use of blockchain is expanding in corporate activities. There arevarious cases: pork and mango [Kam18], palm oil [Hir18], coffee [TMSB18] and so on.
For our solution example, we prove the traceability every 10 minutes for 100 vegetablesin the permissioned blockchain consisting of 20,000 participants. The necessary traffic is3.1. INTRODUCTION

33

approximately 1 Mbps. We describe the details in Section 3.4. This work contributes tothe realization of meaningful traceability that balances the privacy and transparency oftransactions. It is different from the trivial traceability of only transaction tracking.
We describe how participants issue and verify the proof. Participants in the permissioned blockchain initially share the state information. Therefore, it is allowable thatthey share the randomness in encrypting it. They can attach a threshold signature to theproof of the ciphertext of zero as follows.
1. A participant chooses randomness and creates a ciphertext and proof.
2. The randomness, ciphertext, and proof are broadcast to the other participants
within the permissioned blockchain and shared.
3. They verify them by recreating their ciphertext and proof from the received randomness and plaintext.
4. They attach a ring signature to the verified proof similar to the withdrawal of Dilly
et al. [DPW+ 16].
Furthermore, participants make the proofs public in internet storage. For example,
Amazon Web Service S3 would be good. Miners in the permissionless blockchain verify
the proofs.

3.1.1

Related work

There is considerable interest in protecting privacy in blockchain. One of the approaches
is mixing transactions, exemplified in some works [Max13a, Max13b, RMSK14, BNM+ 14].
The other is the use of highly cryptographic methods. Zerocoin [MGGR13], which is anextension of Bitcoin, is one of the initial proposals that provided unlinkability between
individual Bitcoin transactions without introducing a trusted third party. Pinocchio coin
[DFKP13] proposes to incorporate the zero-knowledge succinct non-interactive argumentof knowledge (zk-SNARK) [GGPR13] into Zerocoin. Zerocash [SCG+ 14], which is the
successor to Zerocoin, uses zk-SNARK as a zero-knowledge proof of arithmetic circuit
satisfiability. Recently, zero-knowledge scalable transparent argument of knowledge (zkSTARK) [BSBHR18] and Bulletproofs [BBB+ 18] have been proposed as similar zero-

34

CHAPTER 3. TRACEABILITY IN PERMISSIONED BLOCKCHAIN

knowledge proofs. Both works mention an application to the blockchain. Thus, thezero-knowledge proof is a crucial tool for privacy protection in the blockchain.
Let us refer to some other approaches. The schemes blinding all unspent transaction output (UTXO) while maintaining the public verifiability that no trade produces
or destroys coins have been proposed [Max15, PBF+ 19]. As an application of Hyperledger Fabric, there is a method of protecting the privacy within each channel by setting
confidentiality boundaries [ACDCKK18].
The Markov chain often describes the dynamics of the blockchain. There are several
kinds of studies on selfish mining about Bitcoin [NKMS16, GKKT16, Wüs16].
Regarding homomorphic encryption, there are some works for encoding integers into
plaintext space. Regarding the NTRU encryption scheme [HPS98], Hoffstein and Silverman announced the new technique [HS01]. Regarding the RLWE encryption, Geihs etal. [GC15] applied the technique to the Brakerski-Vaikuntanathan (BV) scheme [BV11]
and Chen et al. [CLPX18] used the technique to the Fan-Vercauteren (FV) scheme [FV12].

Concurrent work
Let us confirm the concurrent works from the viewpoint of traceability in Table 3.1.
Dilly et al. have proposed the sidechain scheme between Bitcoin and the permissioned
blockchain Liquid [DPW+ 16]. In this scheme, the permissioned blockchain’s participants
determine the transfer of assets between Bitcoin and the permissioned blockchain throughtheir consensus. A fast and deterministic agreement in the permissioned blockchain realizes the high throughput of transactions. In Dilly et al. [DPW+ 16], the pool account to apermissionless blockchain is public. There are no unauthorized deposits or withdrawals inthis account. Thus, preservation holds, although Dilly et al. do not specify this matter.
Poelstra et al. [PBF+ 19] mention that there is no unauthorized increase or decreasein coin history, and the number of coins traded is concealed. However, the sender andreceiver must be public.
Zether [BAZB20] realized a payment with anonymous accounts at Ethereum. Thebalance between the sender and the receiver and the transfer amount can be kept confidential. There is no defined way to indicate noninvolvement later. Dummy participants,
except the sender and receiver, must be involved in the transaction from the beginning.
It is difficult for Zether to achieve noninvolvement and trade privacy simultaneously.

3.2. TRACEABILITY AND MODELING

35

Compared with these works, this work is the first proposal that satisfies the threeproperties of traceability. It achieves both trade privacy and transparency simultaneously.
Table 3.1: Traceability’s Properties. Zether achieves either noninvolvement or trade privacy.
Dilly et al. [DPW+ 16]
Poelstra et al. [PBF+ 19]
Zether [BAZB20]This work

3.1.2

Preservation
yes
yes
yes
yes

Noninvolvementnoyes
yes/noyes

Trade privacynonono/yesyes

Chapter organization

We organize the rest of this chapter as follows. Section 3.2 defines traceability and describes its three properties. Section 3.3 encrypts the model defined in Section 3.2 andconfirms the security. Section 3.4 introduces the ring isomorphism encoding, uses thisencoding to the traceability model, and confirms the efficiency. Finally, Section 3.5 concludes this work.

3.2

Traceability and modelingWe introduce traceability. We confirm its three properties: trade privacy, preservation,and noninvolvement.

3.2.1

Traceability

According to the review paper [BG13], various researchers define traceability in various
ways, none of which are perfect. Some researchers define the flow of products fromsuppliers to users and vice versa. Many works seem to define traceability by focusing onthe ”objects” moving between players. In contrast, we focus on how the ”state” of eachplayer’s asset amount changes from time to next time.
Let us consider the mathematical definition based on this idea. The state means thatthe amount of an asset of the participant. We represent the state of participants in thepermissioned blockchain as the vector ~x(t). That is,~x(t) = (x1 , x2 , . . . , xmp ) ∈ Pmp .

36

CHAPTER 3. TRACEABILITY IN PERMISSIONED BLOCKCHAIN

Let us explain each item in this equation. t indicates that the state is at time t. mp is
the number of participants. xi is the state of the participant i. The field P ⊂ Q.
Similarly, we represent the state from the permissionless blockchain to the permissioned blockchain as the vector ~u. We also express the state from the permissioned
blockchain to the permissionless blockchain as the vector ~y . That is,~u = (u1 , u2 , . . . , ulp ) ∈ Plp~y = (y1 , y2 , . . . , ynp ) ∈ Pnp .
lp and np are the numbers of the accounts.
We formally describe that the state transition is deterministic as follows.
Definition 3.1. Let ~x(t), ~x(t + 1) be the amount of assets in the permissioned blockchainat each time t, t + 1, respectively. Let ~y (t + 1) be the amount of assets moving from thepermissioned blockchain to the permissionless blockchain at time t + 1. Let ~u(t) be theamount of assets moving from the permissionless blockchain to the permissioned blockchain
at time t. If x(0) and u(0) are determined at the initial time t = 0, then for every timet ≥ 0, there exists some deterministic polynomial time algorithm A such that(~x(t + 1), ~y (t + 1)) = A(~x(t), ~u(t)).

3.2.2

Modeling

We discuss the deterministic polynomial time algorithm specifically. We list the model
parameters in Table 3.2.
Table 3.2: Overview of parameters in the modelParameter~x~u, ~yaij
bij
cij

Explanationaccount balance of each member in permissioned blockchain
quantity of each member in permissioned blockchain
pool account balance in permissionless blockchain
remittance between members in permissioned blockchain
deposits and products for permissioned blockchain
withdrawal and consumption from permissioned blockchain~x is information in the permissioned blockchain. A participant in the permissioned
blockchain can observe ~x. However, any participant in the permissionless blockchain
cannot. ~u and ~y are information in the permissionless blockchain. Everyone can observe3.2. TRACEABILITY AND MODELING

37

them. We call it a hidden Markov model as ~x is a latent variable for an outsider.
We confirm the state transition. We suppose that the total volume moving from xi (t)to xj (t + 1) is v. That is,xi (t + 1) = xi (t) − v
xj (t + 1) = xj (t) + v
Let us define the distribution rate aij = v/xi (t). In particular, aii is the ”staying”
rate (xi (t) → xi (t + 1)). In same way, we define the distribution rate cij = v/xi (t).
The amount xi (t) is distributed to x1 (t + 1), . . . , xi (t + 1), . . . , xmp (t + 1) at the ratio of
ai1 , . . . , aii , . . . , aimp and distributed to y1 (t + 1), . . . , ynp (t + 1) at the ratio of ci1 , . . . , cinp .
The sum of all the ratios must be equal to 1. That is,
mp
X

aij +

np
X

cij = 1.

j=1

j=1

We also define the distribution rate bij = v/ui (t) moving from ui (t) to xj (t + 1). ui is
distributed to x1 (t + 1), . . . , xmp (t + 1). The sum of all these ratios must be equal to 1.
That is,mp
X

bij = 1.

j=1

From the above discussion, we can obtain the definitions of trade privacy and preservation.

Definition 3.2 (Trade privacy). Let A = (aij ) ∈ Pmp ×mp , B = (bij ) ∈ Plp ×mp and C =(cij ) ∈ Pmp ×np , respectively. The relation of trade privacy is expressed as~x(t + 1) = ~x(t)A(t) + ~u(t)B(t)~y (t + 1) = ~x(t)C(t)Definition 3.3 (Preservation). Let aij , bij and cij be a element of the matrices A, B and38

CHAPTER 3. TRACEABILITY IN PERMISSIONED BLOCKCHAIN

C, respectively. Preservation holds if the following equations hold.
mp
X
j=1

aij +

np
X

cij = 1, for i = {1, 2, . . . , mp }

j=1
mp

X

bij = 1, for i = {1, 2, . . . , lp }j=1

We confirm the following lemma with regard to Definition 3.2, 3.3.

Lemma 3.1 (Overall preservation). If Definition 3.2 and 3.3 are satisfied, then the equation
mpX

xi (t + 1) +

i=1

np
X

yi (t + 1) =

i=1

mp
X

lp
X

xi (t) +i=1ui (t)

i=1

holds.

Proof. First, we expand the equations of Definition 3.2. For our convenience, we omit”(t)” such as ~x(t) or A(t) in this proof. The same abbreviation applies to elements ofPmp
vectors and matrices. Applying j=1
bij = 1, we obtain
mp
X

mp mp
mp
lp
X
X
X
X
xj (t + 1) =(xi aij ) +(ui bij )j=1

j=1 i=1
mp

=

=

X

np
X
j=1

lp
mp
X
X
X
xi (
aij ) +
ui (
bij )

i=1

j=1

i=1

mp

mp

lp

X
i=1

We also obtain

j=1 i=1

mp

j=1

X
X
xi (
aij ) +
ui
j=1

i=1

np mp
mp
np
X
X
X
X
yj (t + 1) =(xi cij ) =
xi (
cij )
j=1 i=1i=1

j=1

3.2. TRACEABILITY AND MODELING
Applying

Pmp

j=1 aij +39

Pnp

j=1 cij = 1, we finally obtainmpX

xj (t + 1) +

j=1

np
X

yj (t + 1)

j=1
mp

lp
mp
np
X X
X
X
X
=(
xi (
aij ) +ui ) +
xi (
cij )

=

i=1

j=1

mp

mp

X
i=1

=

mp

mp
X

i=1
np

i=1

j=1

lp

X
X
X
xi (
aij +
cij ) +
ui
j=1

xi +

i=1

lp
X

j=1

i=1

ui

i=1

The equation in the lemma holds.

Plain example. We describe the simple example. We suppose that Alice, Bob, andCarol are participants in the permissioned blockchain. They have $2, $3, and $4 in eachaccount, respectively. We formulate this situation as follows.
~x(t) = (x1 (t), x2 (t), x3 (t)) = (2, 3, 4)
We suppose that they execute the following three transactions during [t, t + 1].

• Alice gives Bob $1.

• Bob gives Carol $2.

• Carol gives Alice $3.

We assume that there is neither deposit nor withdrawal between the permissioned blockchain
and permissionless blockchain. We consider only internal transactions within the permissioned blockchain. Their accounts are represented by the following state.
~x(t + 1) = (x1 (t + 1), x2 (t + 1), x3 (t + 1)) = (4, 2, 3)

We represent the increase or decrease in the asset quantity by each transaction as the

40

CHAPTER 3. TRACEABILITY IN PERMISSIONED BLOCKCHAIN

ratio,
1
3
1
3
x1 (t + 1) = x1 (t) − x1 (t) + x3 (t) = x1 (t) + x3 (t)
2
4
2
4
2
1
1
1
x2 (t + 1) = x2 (t) + x1 (t) − x2 (t) = x1 (t) + x2 (t)
2
3
2
3
3
2
2
1
x3 (t + 1) = x3 (t) − x3 (t) + x2 (t) = x2 (t) + x3 (t)4334
We obtain ~x(t + 1) = ~x(t)A(t), where
1/2 1/2 0A(t) =  0 1/3 2/3

3/4 0 1/4
Then,P

j aij = 1 holds.

We define noninvolvement and describe local preservation.

Definition 3.4 (Noninvolvement). Regarding Definition 3.2, noninvolvement of a participant i holds at [t, t + 1], if and only if
aij = cij = 0, for all j 6= i,aji = cji = 0, for all j 6= i,
bji = 0, for all j.

Definition 3.5 (Subset of involvement). Sr is a subset of involvement such that the subset
excludes noninvolvement participants from the set of blockchain participants {1, . . . , mp }.

Lemma 3.2 (Local preservation). If Definition 3.2 and 3.3 are satisfied and Sr is a subset
of involvement, then the equation
Xi∈Srholds.

xi (t + 1) +

np
X
i=1

yi (t + 1) =Xi∈Srxi (t) +lp
X
i=1

ui (t)

3.2. TRACEABILITY AND MODELING

41

Proof. From Lemma 3.1,
mpX

xi (t + 1) +

i=1

np
X

yi (t + 1) =

i=1

mp
X

xi (t) +

i=1

lp
X

ui (t)

i=1

holds. Since every participant belongs to Sr or not,mpX

xi (t + 1) =i=1

Xxi (t + 1) +X

xi (t + 1)

i6∈Sr

i∈Sr
mp

X

xi (t) =i=1

Xxi (t) +Xxi (t)

i6∈Sr

i∈Sr

As any participant i 6∈ Sr is represented by noninvolvement, xi is invariant. That is,X

xi (t + 1) =

i6∈Sr

X

xi (t).

i6∈Sr

Therefore, we obtain
Xi∈Srxi (t + 1) +

np
X
i=1

yi (t + 1) =Xi∈Srxi (t) +lp
Xui (t)

i=1

We denote the three properties Definition 3.2, 3.3, and 3.4 as the ”traceability model”
as follows.

Definition 3.6 (Traceability model).

Trade privacy
x(t)A(t) + u(t)B(t) − x(t + 1) = 0
x(t)C(t) − y(t + 1) = 0

42

CHAPTER 3. TRACEABILITY IN PERMISSIONED BLOCKCHAIN

Preservation
mp
X

aij +

j=1

np
X

cij − 1 = 0, for i = {1, 2, . . . , mp }

j=1
mp

X

bij − 1 = 0, for i = {1, 2, . . . , lp }j=1

Noninvolvement For some i,aij = cij = 0, for all j 6= i,aji = cji = 0, for all j 6= i,
bji = 0, for all j.

Remark 3.1. One hidden Markov model corresponds to one kind of object (apple, banana,coin, and so on). If we deal with multiple objects, we can evaluate each model for eachobject. We also make its creation and consumption correspond to the input and the output
to the permissioned blockchain.

3.3

Encrypted model and its security

To conceal the state in the permissioned blockchain, we intend to encrypt the traceability
model of Definition 3.6 with the RLWE encryption. In this section, we introduce theencrypted traceability model and describe its security.

3.3.1

Encrypted traceability model

We confirm that the traceability model of Definition 3.6 corresponds to the ciphertext ofzero. We define the set C0 as a set of ciphertext obtained by encrypting plaintext m = 0
as follows.
Definition 3.7 (Ciphertext of zero).
C0 ={(c1 , c2 ) | c1 , c2 ∈ Rq ∧ ((c1 − s · c2

mod q)

mod p) = 0}.

3.3. ENCRYPTED MODEL AND ITS SECURITY

43

s is a secret key.

We change the traceability model of Definition 3.6 into implicit functions f .

Trade privacy
f1 : ~x(t)A(t) + ~u(t)B(t) − ~x(t + 1)
f2 : ~x(t)C(t) − ~y (t + 1)

Preservation
f3i :

mp
X
j=1
mp

f4i :

X

aij +

np
X

cij − 1, for i = {1, 2, . . . , mp },j=1

bij − 1, for i = {1, 2, . . . , lp }j=1

Noninvolvement aij , bij and cij themselves correspond to f directly.

P includes all the elements of the traceability model of Definition 3.6. The above
functions f1 , f2 , f3i and f4i are also closed by P. An element in P corresponds to Rp by
the ring isomorphic encoding. We will introduce the ring isomorphic encoding and its
efficiency in Section 3.4. Rp corresponds to R2q with RLWE encryption. We denote theciphertext a ∈ R2q corresponding to a ∈ P. In this section, let us write the ciphertext in bold to distinguish it from plaintext. We represent the vectors and matrices
obtained by encrypting each element in the same way. We denote encrypted vectors as~u = (u1 , u2 , . . . , ul ), ~x = (x1 , x2 , . . . , xm ), and ~y = (y1 , y2 , . . . , yn ). We denote encryptedmatrices as A = (aij ), B = (bij ) and C = (cij ). Therefore, we denote the function ffor ciphertexts in R2q corresponding to the function f for plaintexts in P. f1 , f2 correspond to Definition 3.2 and f3i , f4i correspond to Definition 3.3. For some i, aij , bij and cij
themselves correspond to Definition 3.4. We obtain encrypted functions as follows.

Definition 3.8 (Encrypted traceability model).

44

CHAPTER 3. TRACEABILITY IN PERMISSIONED BLOCKCHAIN

Trade privacymf1 (~x(t), A(t), ~u, B(t), ~x(t + 1)) ∈ C0 pnf2 (~x(t), C(t), ~y(t + 1)) ∈ C0 p

Preservation
f3i (aij , cij ) ∈ C0 for i = {1, 2, . . . , mp }f4i (bij ) ∈ C0 for i = {1, 2, . . . , lp }Noninvolvement For some i,aij , cij ∈ C0 for all j 6= i,aji , cji ∈ C0 for all j 6= i,bji ∈ C0 for all j.

Remark 3.2. We write a ciphertext and its function in bold. It is why to distinguishfrom plaintext and its function as the above description.

3.3.2

Security of trade privacy

We confirm the security of the trade-privacy equations f1 , f2 . We intend to hide the private
information A(t), B(t), C(t) and x(t) in these equations. We consider the trade-privacy
equations calculated by ciphertexts of honest plaintexts and fake plaintexts (all zeros). We
say that trade privacy is secure if and only if both are indistinguishable for an adversary.
Since the trade-privacy equations f1 , f2 consist of inner products, we propose the security
challenge experiment in Fig. 3.1.
Theorem 3.1 (Security of trade privacy). For any λ ∈ N and any probabilistic polynomial
time algorithm A, the advantage
tp−indAdvtp−ind
TP,A (λ) :=| Pr[ExpTP,A (λ) = 1] − 1/2 |is negligible in λ, where Exptp−ind
TP,A (λ) is as defined in Fig. 3.1.

3.3. ENCRYPTED MODEL AND ITS SECURITY

Exptp−ind
TP,A (λ) :(pk, sk) ← RLWE.Gen(1λ )β ← {0, 1}
β 0 ← AOTP (·,·) (1λ , pk)
if β = β 0 return 1
else return 0

45

OTP (ci , xi ) :if β = 0ci ← RLWE.Enc(pk, ci )xi ← RLWE.Enc(pk, xi )else
ci ← RLWE.Enc(pk, 0)xi ←P RLWE.Enc(pk, 0)
y := i ci · xi
return y

Figure 3.1: Security challenge experiment for trade privacy

Proof. To prove the security of trade privacy, we consider the games shown in Fig. 3.2.
We denote events as follows:

G0TP,A (λ) :(pk, sk) ← RLWE.Gen(1λ )β ← {0, 1}0
β 0 ← AOTP (·,·) (1λ , pk)
if β = β 0 return 1
else return 0
G1TP,A (λ) :(pk, sk) ← RLWE.Gen(1λ )β ← {0, 1}1
β 0 ← AOTP (·,·) (1λ , pk)
if β = β 0 return 1
else return 00OTP(ci , xi ) :if β = 0ci ← RLWE.Enc(pk, ci )xi ← RLWE.Enc(pk, xi )else
ci ← RLWE.Enc(pk, 0)xi ←P RLWE.Enc(pk, 0)
y := i ci · xi
return y

1OTP(ci , xi ) :if β = 0$
ci , xi ←
− R2q
else
$
ci , Pxi ←− R2qy := i ci · xi
return y

Figure 3.2: Games G0TP,A (λ) and G1TP,A (λ) in the proof of Theorem 3.1.

• E0 : G0TP,A (λ) = 1• E1 : G1TP,A (λ) = 1• B0 : β = 0• B1 : β = 1

46

CHAPTER 3. TRACEABILITY IN PERMISSIONED BLOCKCHAIN

We have
Pr[E0 ] = Pr[E0 ∩ B0 ] + Pr[E0 ∩ B1 ]= Pr[E0 |B0 ] · Pr[B0 ] + Pr[E0 |B1 ] · Pr[B1 ].
In the same way, we obtain
Pr[E1 ] = Pr[E1 |B0 ] · Pr[B0 ] + Pr[E1 |B1 ] · Pr[B1 ].
From the these equations, we construct an adversary B from an adversary A who candistinguish G0TP,A (λ) and G1TP,A (λ). That is,| Pr[G0TP,A (λ) = 1] − Pr[G1TP,A (λ) = 1] |=| Pr[E0 ] − Pr[E1 ] |=| 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.

In game G1TP,A (λ) the view of A is independent of β, as the ci , xi and y are chosen
uniformly at random over R2q . We have thus
Pr[G1TP,A (λ) = 1] = 1/2.

Moreover, G0TP,A (λ) is Exptp−ind
TP,A (λ) itself. Because of Definition 2.4, we finally obtainthatpr
Advtp−ind
TP,A (λ) ≤ AdvRLWE,B (λ) < negl(λ).

3.4. ENCODING AND ITS EFFICIENCY

3.3.3

47

Non-interactive zero-knowledge proof

The permissioned and permissionless blockchains do not move synchronously. The noninteractive zero-knowledge proof between blockchains is desirable. By using Theorem 2.1,
we can prove with zero-knowledge that the encrypted model of Definition 3.8 corresponds
to the model of Definition 3.6.

3.4

Encoding and its efficiency

We need to associate the rational number field P of the traceability model with the plaintext space M of the RLWE encryption. For the purpose, we adopt the ring isomorphism
encoding. In this section, we introduce the ring isomorphism encoding. Furthermore, we
confirm the efficiency of applying it to the encrypted traceability model and the zeroknowledge proof.

3.4.1

Ring isomorphism encoding

We discuss the correspondence between P and the plaintext space M = Rp = Z[X]/hX d +1, pi. We consider that the rational numbers in P are fixed-point numbers. A fixed-point
number is a number with a fixed number of digits. For example, we can handle 8.22 or
82.2 as the integer 822. We can map fixed-point numbers to integers. We define P as
follows.
P ={(n, d) | n = {−(2n1 −1 − 1), . . . , 2n1 −1 − 1} ⊂ Z, d = 2n2 }, for ∃n1 , n2 ∈ N.
We introduce the efficient encoding and decoding, the ring isomorphism encoding[GC15].
Definition 3.9 (Ring isomorphism encoding ( Section 3.2 in [GC15] ) ).

• The encoding of an integer z ∈ Z with |z| ≤ 2n−1 to a polynomial m ∈ Rp is

m=

n−1
X
i=0

zi · xi .

48

CHAPTER 3. TRACEABILITY IN PERMISSIONED BLOCKCHAIN• The decoding of a polynomial m ∈ Rp to an integer z ∈ Z isz=z 0 − (2n + 1)

if z 0 ≥ 2n−1 ,z 0otherwise,

where
0

z =

n−1
X

mi · 2imod (2n + 1).

i=0Theorem 3.2 (Theorem 1 in [GC15]). For a ∈ Z, the map φ : Z/hxn + 1, x − ai →Z/han + 1i given by
f (x) + hxn + 1, x − ai 7→ f (a) + han + 1i
is an isomorphism.
Letting a = 2 in Theorem 3.2, we obtain Rx−2 ∼= Z2n +1 . Letting n = n1 , we choose
the input integer space as Z/h2n1 − 1i. That is, the input integers exist in {−(2n1 −1 −1), . . . , 2n1 −1 − 1}. As |z| ≤ 2n1 −1 , the decoding becomes simpler from Definition 3.9, thatis, z = z 0 .

3.4.2

Somewhat homomorphic encryption

We show that somewhat homomorphic encryption is feasible for the traceability modelof Definition 3.6. We define the benchmark function f as follows, considering the innerproduct in the traceability model of Definition 3.6.

f (z) =

ladd Ylmul
X

zij for zij ∈ Z.

j=1 i=1

zij corresponds to an element of the matrices and vectors of the traceability model. We
confirm the range of integers. Since |zij | ≤ 2n1 −1 ,

d−1

2

≥

ladd Ylmul
X

zij ≥ ladd · 2lmul (n1 −1) .

j=1 i=1

We obtaind > log2 ladd + lmul (n1 − 1).

(3.1)

3.4. ENCODING AND ITS EFFICIENCY

49

Let us confirm the decryptable noise magnitude. We confirm noise growth. Let c =(c1 , c2 ) ∈ R2q and c1 − s · c2 = m + p · e. s is a secret key, m is a plaintext and e is anoise. We denote the norm as DN(c) = |m + p · e|∞ . From the condition that we candecrypt c ∈ R2q correctly, we have DN(c) < q/2. The relationship between the operationsof ciphertexts and the noise growth are as follows.
• Let c1 , c2 ∈ R2q , c = c1 + c2 . Then, we have DN(c) = DN(c1 ) + DN(c2 ).
• Let c1 , c2 ∈ R2q , c = c1 · c2 . Then, we have DN(c) ≤ d · DN(c1 ) · DN(c2 ).
We used |s · t|∞ ≤ d · |s|∞ · |t|∞ from Lemma 2.6.
The size of the noise is small. Let |s|∞ , |v|∞ , |e|∞ , |f |∞ ≤ Bχ .
According to [GC15], let Bfresh be the size of noise in no operation of ciphertexts. We
have
Bfresh = 1 + 3 · (2dBχ2 + Bχ ).
From the above equations, we can transform the condition DN(c) < q/2 into
lmul lmul −1
q/2 > ladd Bfreshd.

We obtain
log2 q > log2 ladd + lmul log2 (Bfresh d) − log2 d + 1.

(3.2)

We confirm the parameters in the RLWE encryption. Following Table 1 in [NLV11],
we choose the concrete parameters: d = 2048, log2 q = 64 and σ = 8. σ is the standard
deviation of the discrete Gaussian distribution for the randomness. As our intention
toward the traceability model of Definition 3.6, we choose n1 = 65 which is a 64-bit√
integer and lmul = 2. Let Bχ = σ d ≈ 362 from Lemma 2.1.
We confirm the upper limit of the number of additions ladd in the traceability modelof Definition 3.6 satisfying the inequalities 3.1 and 3.2. We show the upper limits of thenumber of additions ladd corresponding to d and q in Table 3.3.
We can calculate the traceability model of Definition 3.6 with sufficiently numerous
additions ladd under the practical parameters. That is, we can realize it as somewhat
homomorphic encryption.

50

CHAPTER 3. TRACEABILITY IN PERMISSIONED BLOCKCHAIN

Table 3.3: Numbers of additions calculable with somewhat homomorphic encryption
d
2048
4096
4096
8192
16384

3.4.3

dlog2 qe
89
94
120
264
423

blog2 ladd c
15.8
15.8
41.8
180.8
334.8

Efficiency of zero-knowledge proof

The computation of the encrypted traceability model is limited to low degrees. We canachieve it with somewhat homomorphic encryption. In other words, bootstrapping is
unnecessary. Therefore, the method is effectively practical for computation in the realworld.
We confirm the proof size issued by the prover with the non-interactive zero-knowledge
proof. There are multiple ciphertexts for which we want to prove that the plaintext is zero.
There is an excellent way to reduce the traffic per ciphertext. We pack these ciphertexts
into elements of one vector. The inner product of the vector is also one ciphertext. We
apply the protocol in Fig. 2.3 to the ciphertext. We can reduce the proof size per
ciphertext. An additional inner product calculation increases the degree by one. The
addition increases by kadd times the number of equations we want to prove. Comparedto the case where there is no inner product calculation, we need to enlarge the latticedimension and the ciphertext space. In the same way, we can express the inequalities asfollows.
d > log2 kadd + 2(log2 ladd + lmul (n1 − 1))

log2 q − 1 > 2 log2 ladd + 2lmul log2 Bfresh + (2lmul − 1) log2 d + log2 kadd
In same way as shown in Table 3.3, we can also estimate the proof size in Table 3.4. We
set the zero-knowledge proof count to λ = 128 for 128-bit security and kadd = ladd . The
proof size is at most 627.7 kB.
We naively evaluate the traffic regarding the example of vegetables distributed inJapan. We state elements as follows.

3.4. ENCODING AND ITS EFFICIENCY51

Table 3.4: Proof size for 128-bit security
lmul = 1
d
2048
4096
4096
8192
16384

dlog2 qe
89
94
120
264
423

blog2 ladd c
5.2
5.2
13.9
60.2
111.6

proof size (kB)
103.7
119.5
152.6
363.7
627.7

d
8192
16384

dlog2 qe264423

blog2 ladd c
28.5
77.8

proof size (kB)
363.7
627.7

lmul = 2• There are approximately 90 items whose production volume is determined by statistics, according to the Ministry of Agriculture, Forestry, and Fisheries, Japan1 . The
traffic is proportional to the number of items since one item corresponds to one
encrypted model.
• SEVEN-ELEVEN JAPAN CO., LTD. has opened approximately 21,009 stores inJapan as of October 31, 20192 . The number of participants corresponds to thenumber of stores. The number of participants is approximately 21,000. It does notaffect the traffic because it is much smaller than the upper limit 228.5 in Table 3.4.
• Frequency of proof is once every 10 minutes, as in Bitcoin. We assume that thepermissioned blockchain proves the traceability once every 10 minutes.
• Properties of traceability amount to three. In Table 3.4, we apply lmul = 2 regarding
trade privacy and lmul = 1 regarding preservation and noninvolvement. This fact
triples the traffic.
• The proof size is 363.7 kB according to Table 3.4.
Therefore, the traffic is equal to363.7 kB × 3 property × 90 item/600 sec = 1.3 Mbps.
12

http://www.maff.go.jp/j/seisan/ryutu/yasai/yasai jousei 0111.pdf (Website in Japanese)
https://www.sej.co.jp/company/en/n stores.html

52

CHAPTER 3. TRACEABILITY IN PERMISSIONED BLOCKCHAIN

The global averages on fixed broadband are 70.68 Mbps (download) and 38.23 Mbps
(upload) as of October 2019, according to Speedtest by Ookla3 . The traffic is sufficiently
smaller than the averages. It is feasible.

3.5

Conclusion

We have achieved privacy protection and high transparency in a permissioned blockchain.
Meaningful traceability consists of three properties. That is trade privacy, preservation,and noninvolvement. This work is the first proposal wherein both preservation and noninvolvement hold while protecting trade privacy. We have constructed a traceability model
based on the three properties and encrypted it with the RLWE encryption. Moreover,
we have encrypted the model with somewhat homomorphic encryption by using the ringisomorphism encoding. We have confirmed that the encrypted model is feasible. Finally,
we have confirmed that one can prove with zero-knowledge that the encrypted traceability
model is proper.
Limitation. In this work, we have expressed the traceability model of Definition 3.6
with a fixed-point number. As this extension, we can take an arbitrary denominator.
Then, the number of multiplications is approximately the same as the number of participants since a reduction to a common denominator is necessary. Because of many
numbers of multiplication, we can extend this work theoretically by fully homomorphic
encryption.

3

https://www.speedtest.net/global-index

Chapter 4
Confidential and auditable payments
This chapter is based on the below work with Akira Otsuka.

[MO20b] T. Mitani and A. Otsuka, ”Confidential and Auditable Payments,” in Financial
Cryptography and Data Security. FC 2020. Lecture Notes in Computer Science,
vol 12063, pp 466-480. Springer, Cham.

4.1

Introduction

Bitcoin is transparent because all the transactions are public. However, a bank typicallykeeps the customer’s transaction information confidential. One hopes that blockchain
also keeps their transaction information concealed. Many works realize anonymity andconfidentiality in the blockchain. However, these works have rarely a forcibly auditablefunction. It is a problem that excessive confidentiality of transaction information may
cause money laundering.
In this work, we construct the Confidential and Auditable Payments (CAP) scheme.
The scheme allows a court or an authority to audit transactions while keeping the transaction information confidential. Every participant writes their transactions as a ciphertextof homomorphic encryption in a ledger with a unique public key. The court or authority controls its secret key. They can forcefully decrypt the ciphertexts and confirm theinformation. The CAP scheme eliminates concerns about money laundering caused byconfidentiality and contributes to blockchain’s sound use.
53

54

CHAPTER 4. CONFIDENTIAL AND AUDITABLE PAYMENTS

4.1.1

Our approach

The proposed scheme is not only confidential but also auditable. We describe auditability
at first. A pair of a public key pk0 and a secret key sk0 of homomorphic encryption isissued. A court or an authority controls the secret key sk0 . They can decrypts ciphertexts
according to the appropriate procedure when requested. In this sense, the CAP scheme
is auditable.
Let us state confidentiality. Suppose that a column vector of each participant’s accountbalance ~x is updated to the next time state ~x0 by the transition matrix A. For example, let
us present a state transition for three participants. Let ~x = (x1 , x2 , x3 ), ~x0 = (x01 , x02 , x03 )and A = (aij ). A is a matrix of size 3 × 3. The equation ~x0 = ~xA holds. The transition
matrix A corresponds to the remittance by each participant. Participants use the public
key pk0 in common. Participants fill their balance in their ledger as ciphertext ~x. As
for the transition matrix, each participant writes each element in the ledger as ciphertext
A. Then, participants write their balance of the next time, reflecting the remittance inthe ledger as a ciphertext ~x0 . All the ciphertexts in the ledger are the ciphertexts ofhomomorphic encryption. ~x0 − ~xA is the ciphertext of zero if and only if ~x0 = ~xA.
Let us confirm the remittance procedure when a sender i transfers to a recipient j. We
name the sender Alice and the recipient Bob. The element aij of the transition matrix A
corresponds to this remittance. We use the zero-knowledge proof of plaintext knowledge toshow that the remittance is legitimate. Alice writes the proof regarding aij in the ledger.
This proof shows that she has not sent more than her account balance. The knowledge
corresponds to the randomness in creating the ciphertext of homomorphic encryption.
At the time of remittance, she encrypts the randomness with Bob’s public key pkj . She
sends it to him. He decrypts it with his secret key skj and obtains the randomness of theremittance. From the knowledge of the randomness collected, he proves that his updated
account balance x0j is correct by the operation ~x0 = ~xA.

4.1.2

Related work

In Bitcoin, transaction information is open. For this reason, there are some works for concealing transaction information. Zerocoin [MGGR13] and Zerocash [SCG+ 14] are extensions based on Bitcoin. They realized strong anonymity and confidentiality by designinganonymous coins that skillfully combined commitments. Zerocash uses the zero-knowledge

4.2. SECURE CAP SCHEME

55

succinct non-interactive argument of knowledge (zk-SNARK) [GGPR13] to show others
that there is no fraud such as double-spending. Zether [BAZB20] is also a cryptocurrency
that can conceal transaction information. It has been proposed as an extension basedon Ethereum. Zether has also used the zero-knowledge proof Bulletproofs [BBB+ 18] proposed by their group. Neither Zerocoin, Zerocash, nor Zether is forcibly auditable becauseof their strong anonymity and confidentiality.
Mitani and Otsuka expressed the state transition of a permissioned blockchain by usinghomomorphic encryption [MO19, MO20c]. In their scheme, the zero-knowledge proof ofplaintext knowledge shows that the encrypted model’s equation is established to outsidersof the blockchain. The validity of the state transition is certifiable. So their scheme isauditable concerning the permissioned blockchain.

4.1.3

Chapter organization

We organize the rest of this chapter as follows. Section 4.2 describes the definitions for asecure CAP scheme. Section 4.3 describes the construction of the CAP scheme, including
data structures, algorithms, and security proofs. Section 4.4 states the conclusion.

4.2

Secure CAP scheme

In this section, we define the security of a CAP scheme. Regarding security, we follow
Zerocash [SCG+ 14]. Zerocash defines and satisfies the three properties: ledger indistinguishability, transaction non-malleability, and balance. In this sense, 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. We combine transaction non-malleability and balance into non-malleability. In this sense, a CAP scheme issecure. Let us confirm the below definitions.
Definition 4.1 (Ledger indistinguishability). A CAP schemeΠ := (Setup, CreateAccount, Transition, Send, Receive)
satisfies ledger indistinguishability, if for any λ ∈ N and any probabilistic polynomial time

56

CHAPTER 4. CONFIDENTIAL AND AUDITABLE PAYMENTS

algorithm 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. 4.1. In Fig. 4.1, a pair of thequeries (Q, Q0 ) must be the same type: CreateAccount or Transition. If the query type isTransition, then Q = (Transition, A) and Q0 = (Transition, A0 ). A and A0 must be the same
~ and Q~ 0 are the lists of all
size. Each element is generally different. That is, A 6= A0 . Q
the queries that A sent to the oracles. Append is the function to append the latest queryto the lists.
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,ΠΠ
Lb ← AOb (·) (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 continue0~ Q~ 0 , Lb , L1−b )b ← A(pp, Q,
0
if b = b return 1
else return 0
Figure 4.1: Security challenge experiment for ledger indistinguishability

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

the same as Definition 4.1.

4.3. CONSTRUCTION

57

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)aif (Verify(πP) or Verify(~π b ) or Verify(Πc ) or Verify(~π 0 ))and ( i (x0i − xi ) 6∈ C0 ) in L0
return 1
else return 0
Figure 4.2: Security challenge experiment for non-malleability
Definition 4.3 (Security). A CAP schemeΠ := (Setup, CreateAccount, Transition, Send, Receive)is secure if it satisfies ledger indistinguishability of Definition 4.1 and non-malleability ofDefinition 4.2.

4.3

Construction

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

4.3.1

Notation

We introduce the zero-knowledge proof in Fig. 2.3 and execute this protocol in parallelaccording to Theorem 2.1. This chapter denotes the zero-knowledge proof of plaintext
m = 0 knowledge in the RLWE encryption and its verification as below syntax. We
represent the ciphertext in bold to distinguish from its plaintext.
• Prove(x; r) inputs the ciphertext x and its randomness r and outputs the proof π
for the knowledge of RLWE.Dec(sk, x) = 0. We denotes Prove(x; r1 , . . . , rn ) if there
are several randomnesses r1 , . . . , rn .

58

CHAPTER 4. CONFIDENTIAL AND AUDITABLE PAYMENTS• Verify(π) inputs the proof π and outputs 1 if it is valid, otherwise 0.

4.3.2

Data structures

Let us describe the data structures of the CAP scheme. We consider that the state of theassets held by each participant will transition to the next state as Chapter 3.
• Let ~x = (x1 , x2 , . . . , xn ) ∈ Qn . ~x is the amount of assets in the blockchain at time
t. n is the number of the participants in a blockchain.
• Let ~x0 = (x01 , x02 , . . . , x0n ) ∈ Qn . ~x0 is the amount of assets in the blockchain at timet + 1.
• Let A = (aij ) be a transition matrix such that ~x0 = ~xA. Its size is n × n. Let v be
the volume moving from xi to x0j . That is, x0i = xi − v and x0j = xj + v. We define
the distribution rate aij := v/xi . aii is the staying rate (xi → x0i ). In the transition,
the amount xi is distributed to x01 , . . . , x0i , . . . , x0n at the ratio of ai1 , . . . , aii , . . . , ain .
The sum of all the ratios must be equal to 1 because the total amount is constant.
P
That is, nj=1 aij = 1. Let us confirm the following lemma, which is the variant ofLemma 3.1.
Lemma 4.1. If ~x0 = ~xA andPn

j=1 aij = 1, then the equation
n
X
i=1

x0i =

n
X

xi

i=1

holds.

• Let Ledger L be a distributed ledger that each participant in the blockchain holds
and updates. L contains the ciphertexts ~x, ~x0 , A and their related proofs.
Remark 4.1. 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 virtually no difference, we will discuss A and A0 indiscriminately.

4.3. CONSTRUCTION

4.3.3

59

Algorithms

We describe the CAP scheme as follows.

Definition 4.4 (The CAP scheme). Tha CAP schemeΠ := (Setup, CreateAccount, Transition, Send, Receive)is in Fig. 4.3.

We can verify the completeness of the CAP scheme Π by confirming the construction.

4.3.4

Security analysis

We describe the below lemmas for the security of the CAP scheme Π in Definition 4.4.

Lemma 4.2 (Ledger indistinguishability). The CAP scheme Π in Definition 4.4 satisfies
ledger indistinguishability in Definition 4.1.

Proof. We consider the games in Fig. 4.4. 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 ].
Then, i = {0, 1}. We construct an adversary B from an adversary A who can distinguish

60

CHAPTER 4. CONFIDENTIAL AND AUDITABLE PAYMENTS

Transition• Inputs:
Setup• Inputs: security parameter λ• Outputs: public parameters pp and court parameters cp– public parameters pp– old accounts state ~x = (x1 , . . . , xn ) in L
– accounts randomness rx1 , . . . , rxn• Outputs in L:

1. Compute (pk0 , sk0 ) := RLWE.Gen(1λ ).
2. Set pp := pk0 .
3. Set cp := sk0 .
4. Output pp and cp.

– new accounts state ~x0 = (x01 , . . . , x0n )– new transition matrix A = (aij )– balance proofs ~π b = (π1b , . . . , πnb )c– accounts copy proofs Πc = (πij)
00– transition proofs ~π = (π1 , . . . , πn0 )CreateAccount• Inputs: public parameters pp and security parameter λ• Outputs: account ciphertext x, proof π a in L
and key pair (pk, sk)
1. Choose randomly rx .
2. Compute x := RLWE.Enc(pk0 , 0, rx ).
3. Compute π a := Prove(x; rx ).
4. Compute (pk, sk) := RLWE.Gen(1λ ).
5. Output x, π and (pk, sk).
Send

1. For i ∈ {1, . . . , n} (i sends v to j.)(a) For j ∈ {1, . . . , n}i. Send(pp, xi , rxi , xi , v, pkj ).
cii. Write πij, xcij , aij in L.
b(b) Compute
P πi :=
Prove( j aij − 1; rai1 , . . . , rain ).
(c) Write πib in L.

2. Verify(Πc )3. Verify(~π b )4. For j ∈ {1, . . . , n} (j receives v from i.)• Inputs:(a) For i ∈ {1, . . . , n}ccReceive(pp, skj , xP
i , aij , v, rv , πij ).
(b) Compute x0j := i vij .
(c) Choose rx0j randomly.
(d) Compute x0j := RLWE.Enc(pk0 , x0j , rx0j ).
P(e) Compute πj0 := Prove(x0j − i aij · xci ;rx0j , rv1j , . . . , rvnj ).
(f) Write x0j , πj0 in L.

– public parameters pp– account ciphertext x in Ledger L– randomness rx– plaintext x– sending volume v– public key pkj• Outputs:– copy proof π c– copy account xc– distribution ratio aij– volume v– randomness rv
1. Choose randomly rxc , where rxc 6= rx .
2. Compute xc := RLWE.Enc(pk0 , x, rxc ).
3. Compute π c := Prove(xc − x; rxc − rx ).
4. Compute a := v/x.
5. Choose randomly raij .
6. Compute aij := RLWE.Enc(pk0 , a, raij ).
7. Compute rv from rxc and raij .
8. Compute v := RLWE.Enc(pkj , v, rv ).
9. Compute rv := RLWE.Enc(pkj , rv , rrv ).
10. Output π c , xc , aij , v, rv .

5. Verify(~π 0 )Receive• Inputs:– public parameters pp– secret key skj– ciphertexts xc , aij , v, rv– proof π c in L
• Outputs:– volume v– randomness rv
1. Compute v := RLWE.Dec(skj , v).
2. Compute rv := RLWE.Dec(skj , rv ).
3. If aij · xc = RLWE.Enc(pk0 , v, rv ) and |rv | issmall: Output v, rv .
4. Else: Output ⊥.

Figure 4.3: Construction of the CAP scheme

4.3. CONSTRUCTIONG0CPA,A (λ):(pk, sk) ← RLWE.Gen(1λ )β ← {0, 1}CPA
β 0 ← AO0 (·,·) (1λ , pk)
if β = β 0 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 061
O0CPA (m0 , m1 ):if β = 0
Choose r randomly.
c ← RLWE.Enc(pk, m0 , r)else
Choose r randomly.
c ← RLWE.Enc(pk, m1 , r)return c
O1CPA (m0 , m1 ):
$

c←
− R2q
return c

Figure 4.4: Security challenge experiment for plaintexts
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, ExpL−IND
Π,A (λ) consistsof the game G0CPA,A (λ). Because of Definition 2.4, we obtainpr0
AdvL−IND
Π,A (λ) ≤| Pr[GCPA,A (λ) = 1] − 1/2 |≤ AdvRLWE,B (λ) < negl(λ).

Lemma 4.3 (Non-malleability). The CAP scheme Π in Definition 4.4 satisfies nonmalleability in Definition 4.2.
Proof. Let us consider the below violations of verification in the cases A wins without the62

CHAPTER 4. CONFIDENTIAL AND AUDITABLE PAYMENTS

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.
• A wins but violates Verify(~π 0 ) in Transition.
Any violations result from the violation of the zero-knowledge proof. This is theknowledge error of zero-knowledge proof. From Theorem 2.1, the knowledge error ofzero-knowledge proof is negligible.
Finally, we can lead the below theorem from Lemma 4.2 and Lemma 4.3.
Theorem 4.1 (The secure CAP scheme). The CAP scheme Π in Definition 4.4 is securein the sense of Definition 4.3.

4.4

Conclusion

We have constructed the Confidential and Auditable Payments(CAP) scheme. The CAP
scheme allows a court or an authority to audit transactions while keeping the transaction
information confidential. Every participant writes the ciphertexts of transaction information in a ledger. We have confirmed the concealment of the transaction information andthe soundness of the CAP scheme. The CAP scheme is secure in this sense. A court oran authority can forcibly reveal transaction information with a unique secret key. In thissense, we realized auditability in the CAP scheme.
Limitation. In the CAP scheme, the secret key can decrypt all transaction information.
Therefore, we expect the court or authority to disclose minimum requisite information.

Chapter 5
Anonymous probabilistic payment inpayment hub
This chapter is based on the below preprint with Akira Otsuka.
[MO20a] T. Mitani and A. Otsuka, ”Anonymous probabilistic payment in payment hub,”
Cryptology ePrint Archive, Report 2020/748, 2020. https://eprint.iacr.org/
2020/748

5.1

Introduction

There are many problems that blockchain needs to be solved. Scalability and privacy
protection are significant problems in blockchain. However, there are a few proposals tosolve these problems at the same time.
Let us state privacy protection. The transaction links a payer and a payee publicly
in Bitcoin. One can know their balance and trading frequency by analyzing the linksof transactions. Privacy is not protected. Breaking the transaction link is necessary toprotect privacy.
Let us describe scalability. It is costly to write all the small transactions into theblockchain. The payment of a small amount of money is called micropayment. For suchmicropayments, Wheeler [Whe97] and Rivest [Riv97] proposed a probabilistic payment
before blockchain appears. It reduces costs for micropayment. In probabilistic payment,
we pay an ordinary mount m with a certain probability p. We pay a small amount mp
as an expected value. By the probability p (e.g. p ≈ 0.1 ∼ 0.001), we can reduce 1/p
63

64 CHAPTER 5. ANONYMOUS PROBABILISTIC PAYMENT IN PAYMENT HUB
times transactions than a naively deterministic payment. Micropay [Ps15], the DAM
scheme [CGL+ 17] and Microcash [ABC20] have proposed a new micropayment on theblockchain. It is attracting attention as one of the leading solutions for scalability in theblockchain.

5.1.1

Our contribution

We propose an anonymous probabilistic payment. It aims to solve both scalability andprivacy protection. In this work, we realize a kind of unlinkability: ”k-anonymity inan epoch.” TumbleBit [HAB+ 17] and their earlier work [HBG16] mentioned this definition. The link means that which payer pays which payee via a tumbler within an epoch.
Anonymity means the link is broken. Even a tumbler never knows the link. The ”k” isthe number of participants trading via the tumbler. The epoch is the period during whichtransactions are completed.
Our proposal includes a probabilistic payment. In the probabilistic payment, we pay
an ordinary mount m with a certain probability p (e.g. p ≈ 0.1 ∼ 0.001) and we pay
a small amount mp as an expected value. We can reduce 1/p times transactions than adeterministic payment. We introduce a novel fractional oblivious transfer for adopting
the probabilistic payment. We apply this ingredient to a probabilistic payment from thepayer to the tumbler. We call it the ring fractional oblivious transfer since this is basedon the ring learning with errors (RLWE) encryption. The functionality required for our
proposal is hashed time lock contract (HTLC). Various cryptocurrencies adapt HTLC.
This request is general, not restricted to any particular cryptocurrency.

5.1.2

Related work

In this subsection, we describe the related work regarding anonymity in blockchain, probabilistic payment, fractional oblivious transfer, and the comparison with a concurrent
work.
Anonymity in blockchain
There are researches on a new anonymous cryptocurrency. Zerocash [SCG+ 14] is a famous anonymous cryptocurrency and is implemented as ZCash. They also have proposed continuous researches such as BOLT [GM17] and DAM scheme [CGL+ 17]. Mon-

5.1. INTRODUCTION

65

ero is also a famous anonymous cryptocurrency and is provided with incredible works[Noe15, SALY17, YSL+ 20, MSRL+ 19]. There are studies to realize anonymity for existing
cryptocurrencies by using off-chain technology. TumbleBit [HAB+ 17] is compatible with
Bitcoin. Zether [BAZB20] is compatible with Ethereum.

Probabilistic payments
Wheeler [Whe97] and Rivest [Riv97] proposed a probabilistic payment. Micropay [Ps15]
is compatible with Bitcoin. Microcash [ABC20] can be implemented as a smart contract.
The DAM scheme, which is the extension of anonymous ZCash, also realizes a probabilistic
payment.

Fractional oblivious transfer over the ring
Bellare and Micali [BM90] and Bellare and Rivest [BR99] proposed the fractional oblivioustransfer based on the computational Diffie-Hellman assumption as the early works. The
DAM scheme [CGL+ 17,CGL+ 16] also proposed a novel fractional oblivious transfer basedon the decisional Diffie-Hellman assumption as fractional message transfer. Note that
[CGL+ 16] is the full version of [CGL+ 17].
Brakerski and Döttling proposed an oblivious transfer based on the learning witherrors [BD18]. This work is the first oblivious transfer in the post-quantum cryptography.
Liu and Hu first proposed an efficient 1-out-of-2 oblivious transfer (OT) on the RLWE
assumption and extends 1-out-of-n OT [LH19]. To the best of our knowledge, we first
propose the fractional oblivious transfer over the ring.

Comparison with a concurrent work
The DAM scheme [CGL+ 17, CGL+ 16] is an anonymous probabilistic payment, which
passes ZCash transaction by a fractional oblivious transfer. Since the scheme includes a
ZCash transaction in the message, it is a ZCash specific implementation. Regarding our
proposal, the required functionality is the hashed time lock contract (HTLC). Various
cryptocurrencies such as Bitcoin, implement HTLC. Therefore our proposal is not limited
to a specific cryptocurrency.

66 CHAPTER 5. ANONYMOUS PROBABILISTIC PAYMENT IN PAYMENT HUB

5.1.3

Our approach

We present the anonymous probabilistic payment approach and the ring fractional oblivious transfer, which is a vital ingredient in our proposal.

Anonymous probabilistic payment
We propose an anonymous probabilistic payment that a payer pays a payee via a tumbler.
We name the payer Alice and the payee Bob. Suppose that she wants to send one cointo him through the tumbler with a certain probability p. We show the overview of the
protocol in Fig. 5.1. Our protocol mostly follows TumbleBit [HAB+ 17]. The difference isthe use of RLWE encryption and RFOT.
Let us explain each phase in the protocol: setup, puzzle promise, and puzzle solver
as follows. In the setup phase, the tumbler generates a one-time key pair consisting ofa public key and a private key. The tumbler also attaches proof of the zero-knowledge
proof. The tumbler publishes this proof and the public key.
In the promise phase, the tumbler and Bob interact. The tumbler prepares an escrowtransaction that pays one coin to him from the tumbler. Both the signatures of the
tumbler and he can execute this escrow transaction. The tumbler does not present its
signature to him in this phase. Instead, the tumbler creates puzzles and promises fromits signature and presents them to him. If he shows this puzzle answer, then he obtains
the tumbler signature from the promise and puzzle.
To gain the answer, Bob will ask Alice to solve the puzzle. Then, he masks the puzzle
to delete his link and sends it to her. She also masks the received puzzle from him todelete her link. She will pay and get the answer to the puzzle with a probability p in thenext phase.
In the solver phase, Alice interacts with the tumbler to get the puzzle answer. She
makes a probabilistic payment to the tumbler, paying one coin with probability p. Then,she sends the double-masked puzzle to the tumbler. She issues a transaction to thetumbler and asks the tumbler to post the puzzle answer. She asks the tumbler to decryptin exchange for the commitment to the transaction. The tumbler posts the answer andexecutes the transaction. Alice demasks the double-masked answer and sends the single
masked answer to Bob.
In the cash-out phase, Bob receives the single masked answer from Alice. He demasks

5.1. INTRODUCTION

67

it and obtains the answer. As the tumbler and he promised in the promise phase, he getsthe tumbler signature from the answer. Finally, he executes the escrow transaction andgains one coin.
Alice A

Tumbler T

Bob B
Puzzle promise protocol
Obtain puzzle z from T
y = mask(z)Send y to A

Puzzle solver protocol
β = mask(y)Send β to T
Learn s from T
m0 = demask(s)Send m0 to B
m = demask(m0 )Obtain T ’s singnature from m and post it
Figure 5.1: Overview of the proposed protocol

Ring fractional oblivious transfer
For the probabilistic payment in the solver phase, we introduce a novel ingredient. It is afractional oblivious transfer based on the RLWE encryption. We call it the ring fractional
oblivious transfer (RFOT). Let us describe RFOT.

Basic idea. In the RLWE encryption, it is essential to operate on the ring Rq =Zq [X]/hX d + 1i. An element is a polynomial of n − 1 degree. That is, a = a0 + a1 X +· · · + ad−1 X d−1 . Let us compare an element a ∈ Rq with aX k multiplied by a monomial
X k with an integer k. One can choose k randomly from the set {1, . . . , n}, where n < d.
Because X d = −1, the original coefficient of the element a is cyclically shifted regardlessof the sign. One sample coefficients of the element a randomly from the uniform distribution in key generation or encryption. The distribution is positive and negative symmetric.
The element a chosen from the distributions and the shifted aX k are indistinguishable.
Looking at the aX k , one cannot identify how much the shift is.

Procedure. Suppose that a sender sends a message m to a receiver. We name thesender Alice and the receiver Bob. First, he creates a one-time key pair, a public key,

68 CHAPTER 5. ANONYMOUS PROBABILISTIC PAYMENT IN PAYMENT HUB
and private key. He randomly chooses an integer k ∈ {1, . . . , n}, cyclically shifts the
public key by multiplying a monomial X −k . Furthermore, Bob issues this shifted public
key to her. She creates the ciphertext by the shifted public key. She does not know theshift amount of k. She also randomly chooses an integer l ∈ {1, . . . , n}, and shifts the
ciphertext by multiplying a monomial X l . He receives the shifted ciphertext and decrypts
it by the secret key. If both shifted amounts l and k match, he can obtain a message m inthe specified format. If they do not match, he has a broken message ∅. The probability
that both l and k match is 1/n.

Security. We prove that the RFOT satisfies the fractional hiding and fractional binding.
The DAM scheme [CGL+ 17,CGL+ 16] introduced the two properties. Fractional hiding is
the property that a ciphertext created by an honest encryptor can be decrypted exactlywith probability p. Fractional binding is the property that a malicious encryptor cannot
create valid ciphertext that can be decrypted with probability p0 6= p. We prove thefractional hiding and fractional binding security with the simulation-based security like
[CGL+ 17, CGL+ 16].
Let us explain the trapdoor for the simulated RFOT. We use the scheme for the
trapdoor proposed in the identity-based encryption over NTRU lattice [DLP14]. We
regard the one-time public key and private key as a user key and the simulated trapdoor
as a master key. It can directly produce the small elements of the RLWE encryption.
One can simulate a shifted secret key or plaintext and randomness from the randomly
sampled elements s1 , s2 such that y = as1 + 2s2 for the given y and the trapped a. The
trapdoor requires the decisional small polynomial ratio (DSPR) assumption.
A trapdoor using a gadget matrix is known. Micciancio and Peikert proposed a gadget
matrix based trapdoor [MP12]. Following this work, Genise and Micciancio proposed
an efficient Gaussian sampler for the trapdoor [GM18]. Cousins et al. proposed theimplementation of the RLWE encryption [CDG+ 18]. However, this method does not
output the small elements required for RLWE encryption.

5.1.4

Chapter organization

We describe the organization of this work. In Section 5.2, we introduce the ring fractional
oblivious transfer. In Section 5.3, we introduce the puzzle solver protocol and the puzzle

5.2. RING FRACTIONAL OBLIVIOUS TRANSFER

69

promise protocol and discuss the security of the protocols. In Section 5.4, we conclude
this work.

5.2

Ring fractional oblivious transfer

In this section, we introduce a fractional oblivious transfer over the ring. First, we describe
the trapdoor and the zero-knowledge proof. Next, we introduce the syntax and thedefinition of the scheme and its simulator, and its properties, referring to [CGL+ 16].
Finally, we present the construction of the ring fractional oblivious transfer and discuss
the security.

5.2.1

Trapdoor

We introduce the trapdoor based on DSPR assumption according to [DLP14]. We use
IBE.MasterKeygen(d, q) and IBE.Extract(B, t) of [DLP14]. We show the functions in Fig.
5.2. We state the difference between our functions and [DLP14]. [DLP14] calculates thehash value of the second argument in the function IBE.Extract. However, we use the target
value t as it is.
• Master key generation: IBE.MasterKeygen(d, q) → (a, B, ga , fa )On input a dimension d of the ring R and a modulo q of the ring Rq = R/qR,
IBE.MasterKeygen outputs a master public key a, a master secret key B, and small
polynomials ga , fa such that a = ga · fa−1 .
• Extractor: IBE.Extract(B, t) → (s1 , s2 )On input a master secret key B and a target value t, IBE.Extract outputs a pair ofsmall polynomials (s1 , s2 ) such that t = as1 + 2s2 , where a is the master public key.
Figure 5.2: Trapdoor by identity-based encryption [DLP14]

5.2.2

Non-interactive zero-knowledge proof

Let us state the non-interactive zero-knowledge proof (NIZK). We show the syntax of
NIZK in Fig. 5.3, referring to [CGL+ 16]. In this work, we represent NIZK according to
the syntax. R is a relation regarding an instance x and a witness w. If x and w satisfy
the relation R, then we denote (x, w) ∈ R. The non-interactive zero-knowledge proof for
the relation R is a protocol that satisfies the properties in Fig. 5.4.

70 CHAPTER 5. ANONYMOUS PROBABILISTIC PAYMENT IN PAYMENT HUB• Setup: NIZK.Setup(1λ , R) → crs
On input a security parameter λ and a relation R, NIZK.Setup outputs a common
reference strings crs.
• Prove: NIZK.Prove(crs, x, w) → π
On input a common reference strings crs, an instance x, and a witness w, NIZK.Proveoutputs a proof π.
• Verify: NIZK.Verify(crs, x, π) → 1 or 0
On input a common reference strings crs, an instance x, and a proof π, NIZK.Verify
outputs 1 if π is valid, otherwise 0.
• Simulated setup: NIZK.SimSetup(1λ , R) → (crs, td)
On input a security parameter λ and a relation R, NIZK.SimSetup outputs a common
reference strings crs and a trapdoor td.
• Knowledge extractor: NIZK.Extract(crs, td, x, π) → w
On input a common reference strings crs, a trapdoor td, an instance x, and a proof
π, NIZK.Extract outputs a witness w.
• Simulator: NIZK.Simulate(crs, td, x) → π
On input a common reference strings crs, a trapdoor td, and an instance x,
NIZK.Simulate outputs a proof π.
• Knowledge extracting simulator: NIZK.ExtSimulate(crs, td, x) → π
On input a common reference strings crs, a trapdoor td, and an instance x,
NIZK.ExtSimulate outputs a proof π.
Figure 5.3: Syntax of NIZK [CGL+ 16]

5.2. RING FRACTIONAL OBLIVIOUS TRANSFER

71

1. Completeness For any (x, w) ∈ R, the conditional probability
Pr[NIZK.Verify(crs, x, π) = 1 ∧ (x, w) ∈ R |crs ← NIZK.Setup(1λ , R), π ← NIZK.Prove(crs, x, w)] ≥ 1 − negl(λ).
2. Soundness
Let a knowledge extractor NIZK.Extract for any adversary A exist. For all (x, w) 6∈
R, the conditional probability
Pr[NIZK.Verify(crs, x, π 0 ) = 1 ∧ (x, w0 ) 6∈ R |(crs, td) ← NIZK.SimSetup(1λ , R), π ← NIZK.Prove(crs, x, w),
w0 ← NIZK.Extract(crs, td, x, π), π 0 ← A(crs, x, w0 )] ≤ negl(λ).
3. Zero-knowledge
For any adversary, the below two distribution ensembles EZreal , EZideal are computationally indistinguishable.
EZreal = {(R, crs, x, π) | crs ← NIZK.Setup(1λ , R), π ← NIZK.Prove(crs, x, w)}
EZideal = {(R, crs, x, π) | (crs, td) ← NIZK.SimSetup(1λ , R),
π ← NIZK.Simulate(crs, td, x)}
Figure 5.4: The properties of NIZK72 CHAPTER 5. ANONYMOUS PROBABILISTIC PAYMENT IN PAYMENT HUB
Let us explain NIZK.ExtSimulate regarding the relation RE for a randomly sampledpair (c1 , c2 ) as follows. We adopt the special trapdoor tdI since a pair (c1 , c2 ) is randomly
sampled.
Definition 5.1 (Extract Simulate with trapdoor). NIZK.ExtSimulate regarding the rela$tion RE for a given pair (c1 , c2 ) ←− C is stated as follows.
• NIZK.ExtSimulate(crsE , tdI , x) → π
1. Parse x as (c1 , c2 , a, y).
2. Parse tdI as (B, ga , fa ).
3. Compute (v 0 , f 0 ) = IBE.Extract(B, c2 ).
4. Compute (s1 , s2 ) = IBE.Extract(B, (c1 − yv 0 )fa−1 ).
5. Compute m0 , e0 from (c1 − yv 0 )fa−1 = as1 + 2s2 .
6. Compute π = NIZK.Prove(crsE , x, (m0 , v 0 , e0 , f 0 )).
7. Output π.
Remark 5.1. Let us confirm how to obtain m0 and e0 from (c1 − yv 0 )fa−1 = as1 + 2s2 .
Note that a = ga fa−1 , where fa and ga are small polynomials.
(c1 − yv 0 )fa−1 = as1 + 2s2(c1 − yv 0 )fa−1 = s1 ga fa−1 + 2s2
c1 − yv 0 = s1 ga + 2s2 fa
c1 = yv 0 + s1 ga + 2s2 fa
Let m0 = s1 ga mod 2 and e0 = s2 fa + s1 ga − m0 . We obtain c1 = yv 0 + 2e0 + m0 .
Lemma 5.1. Let NIZK.ExtSimulate be defined as Definition 5.1. The below two distribution ensembles EZreal
and EZideal
are computationally indistinguishable.
00EZreal= {(RE , crs, x, π) | crs ← NIZK.Setup(1λ , RE ), π ← NIZK.Prove(crs, x, w)}
0
EZideal= {(RE , crs, x, π) | (crs, td) ← NIZK.SimSetup(1λ , RE ),0
π ← NIZK.ExtSimulate(crs, td, x)}

5.2. RING FRACTIONAL OBLIVIOUS TRANSFER

73

Proof. Let us confirm Definition 5.1 of NIZK.ExtSimulate. A simulated witness w0 =(m0 , v 0 , e0 , f 0 ) is generated from the trapdoor tdI . Then the faithful witness w is entirely unnecessary. We can choose a small witness w0 that fits the norm constraint by
IBE.Extract. Besides, we can call the actual proving function NIZK.Prove inline. The
simulated proof by NIZK.ExtSimulate is computationally indistinguishable from the proof
by NIZK.Prove. We conclude that the two distribution ensembles EZreal
and EZideal
are com00putationally indistinguishable.

5.2.3

Syntax and definition

We introduce the scheme’s definitions, the correctness, the simulator, fractional hiding,and fractional binding. These definitions appear initially as fractional message transfer
in [CGL+ 16]. We follow the syntax and the definition in [CGL+ 16].

Syntax and definition of scheme and simulator
We state the syntax and the definition regarding the scheme and its simulator. We show
the syntax and definition of the scheme in Fig. 5.5.
Definition 5.2 (Correctness [CGL+ 16]). A scheme is correct if for every security parameter λ, public parameters pp ∈ RFOT.Setup(1λ ), probability p ∈ [0, 1], key pair (pk, sk) ∈RFOT.Keygen(pp, p), and message m ∈ M,

RFOT.Decrypt(pp, sk, RFOT.Encrypt(pp, pk, m)) =mwith probability p∅with probability 1 − p

Remark 5.2. The types of a decrypted message m0 are as follows. Let us name avalid/invalid message hit/miss since we illustrate a probabilistic payment as a lottery
ticket.
• m : well-formatted valid message. We also call it ”hit.”• ∅ : broken formatted invalid message. We also call it ”miss.”• ⊥ : error message reporting error occurrence

74 CHAPTER 5. ANONYMOUS PROBABILISTIC PAYMENT IN PAYMENT HUB

The syntax of the scheme• Setup: RFOT.Setup(1λ ) → pp
On input a security parameter λ, RFOT.Setup outputs a public parameter pp.
• Key generation: RFOT.Keygen(pp, p) → (pk, sk)
On input a public parameter pp and a probability p ∈ [0, 1], RFOT.Keygen outputs
a public key pk and a secret key sk.
• Encryption: RFOT.Encrypt(pp, pk, m) → c
On input a public parameter pp, a public key pk, and a message m, RFOT.Encrypt
outputs a ciphertext c.
• Decryption: RFOT.Decrypt(pp, sk, c) → m0
On input a public parameter pp, a secret key sk, and a ciphertext c, RFOT.Decrypt
outputs a message m0 .
The simulator regarding the security for the scheme• Simulated setup: RFOT.SimSetup(1λ ) → (pp, td)
On input a security parameter λ, RFOT.SimSetup outputs a public parameter pp
and a trapdoor td.
• Simulated key generation: RFOT.SimKeygen(pp, td, p) → (pk, sk)
On input a public parameter pp, a trapdoor td, and a probability p ∈ [0, 1],
RFOT.SimKeygen outputs a public key pk and a secret key sk.
• Simulated encryption: RFOT.SimEncrypt(pp, td, pk, b, m0 ) → c
On input a public parameter pp, a trapdoor td, a public key pk, a bit b, and amessage m0 , RFOT.SimEncrypt outputs a ciphertext c.
• Extracting decryption: RFOT.ExtDecrypt(pp, td, sk, c) → m
On input a public parameter pp, a trapdoor td, a secret key sk, and a ciphertext c,
RFOT.ExtDecrypt outputs a message m.
• Simulated decryption: RFOT.SimDecrypt(pp, td, sk, b) → sk0
On input a public parameter pp, a trapdoor td, a secret key sk, and a bit b,
RFOT.SimDecrypt outputs a simulated secret key sk0 .
Figure 5.5: Syntax of the scheme and its simulator [CGL+ 16]

5.2. RING FRACTIONAL OBLIVIOUS TRANSFER

75

Fractional hiding and binding
Let us introduce the definitions of fractional hiding and binding, according to [CGL+ 16].
Definition 5.3 (Fractional hiding (Claim A.7 in [CGL+ 16])). The hiding property holds
when the following distribution ensembles EHreal and EHideal are computationally indistinguishable for any adversary AH , where
EHreal = {out | RFOT.Setup(1λ ) → pp, AH (pp) → (pk, m),
RFOT.Encrypt(pp, pk, m) → c, AH (c) → out}
andEHideal = {out | RFOT.SimSetup(1λ ) → (pp, td), AH (pp) → (pk, m),”1 with probability p and 0 otherwise” → b,
if b = 1, set m0 = m; else set m0 = ∅,RFOT.SimEncrypt(pp, td, pk, b, m0 ) → c, AH (c) → out}.
Definition 5.4 (Fractional binding (Claim A.8 in [CGL+ 16])). The binding property
holds when the following distribution ensembles EBreal and EBideal are computationally indistinguishable for any adversary AB , where
EBreal = {(pp, pk, sk, c, m) | RFOT.Setup(1λ ) → pp, RFOT.Keygen(pp, p) → (pk, sk),
AB (pp, pk) → c, RFOT.Decrypt(pp, sk, c) → m}andEBideal = {(pp, pk, sk0 , c, m0 ) | ”1 with probability p and 0 otherwise” → b,
RFOT.SimSetup(1λ ) → (pp, td),
RFOT.SimKeygen(pp, td, p) → (pk, sk),
AB (pp, pk) → c, RFOT.ExtDecrypt(pp, td, sk, c) → m,
RFOT.SimDecrypt(pp, td, sk, b) → sk0 ,if b = 1, set m0 = m; else set m0 = ∅}.

76 CHAPTER 5. ANONYMOUS PROBABILISTIC PAYMENT IN PAYMENT HUB

5.2.4

Construction

We describe our proposed scheme, its correctness, and its simulation-based security.

SchemeLet us introduce the formal definition of our scheme.
Definition 5.5 (Ring fractional oblivious transfer). The ring fractional oblivious transfer(RFOT)
RFOT = (RFOT.Setup, RFOT.Keygen, RFOT.Encrypt, RFOT.Decrypt)
is defined in Fig. 5.6.

Remark 5.3. We denote the encryption as c = RFOT.Encrypt(pk, m; v, e, f ) if an encryptor specifies the randomness v, e, f .

Correctness
Let us confirm the correctness of decryption in our scheme. If l = k, then(c1 − c2 s)X −k = ((yX −k v + 2e + m)X l − (av + 2f )s)X −k= ((yX l−k − as)v + 2(eX l − f s))X −k + mX l−k= ((y − as)v + 2(eX l − f s))X −k + m= 2(es v + eX l − f s)X −k + m(es v + eX l − f s)X −k is small. We have m0 = (c1 − c2 s)X −k mod 2 = m.

Security
Let us state the simulation-based security.

5.2. RING FRACTIONAL OBLIVIOUS TRANSFER• RFOT.Setup(1λ ) → pp
1. Compute crsK ← NIZK.Setup(1λ , RK ).
2. Compute crsE ← NIZK.Setup(1λ , RE ).
$3. Set a ←− Rq .
4. Output pp = (crsK , crsE , a).
• RFOT.Keygen(pp, 1/n) → (pk, sk)
1. Parse pp as (crsK , crsE , a).
$

2. Set s, es ←− χ.
3. Compute y = as + 2es .
$4. Set k ←− {1, . . . , n}.
5. Compute y0 = yX −k .
6. Compute πK = NIZK.Prove(crsK , (a, y0 ), (sX −k , es X −k )).
7. Set pk = (1/n, a, y0 , πK ).
8. Set sk = (1/n, s, es , k, πK ).
9. Output key pair (pk, sk).
• RFOT.Encrypt(pp, pk, m) → c
1. Parse pp as (crsK , crsE , a).
2. Parse pk as (1/n, a, y0 , πK ).
$3. Set l ←− {1, . . . , n}.
4. Compute c01 = y0 v + 2e + m, c2 = av + 2f .
5. Compute c1 = c01 X l = (y0 v + 2e + m)X l .
6. Compute πE = NIZK.Prove(crsE , (c1 , c2 , a, y0 ), (m, v, e, f )).
7. Output c = (l, c1 , c2 , πE ).
• RFOT.Decrypt(pp, sk, c) → m0
1. Parse pp as (crsK , crsE , a).
2. Parse sk as (1/n, s, es , k, πK ).
3. Parse c as (l, c1 , c2 , πE ).
4. If l 6∈ {1, . . . , n}, then output ⊥.
5. If NIZK.Verify(crsE , (c1 , c2 , a, y0 ), πE ) = 0, then output ⊥.
6. If l 6= k, then output m0 = ∅.
7. If l = k, then output m0 = (c1 − c2 s)X −k mod 2.
Figure 5.6: Construction of the ring fractional oblivious transfer

77

78 CHAPTER 5. ANONYMOUS PROBABILISTIC PAYMENT IN PAYMENT HUB
Definition 5.6 (Simulated ring fractional oblivious transfer). The simulated ring fractional oblivious transfer
RFOTsim = (RFOT.SimSetup, RFOT.SimKeygen, RFOT.SimEncrypt,
RFOT.ExtDecrypt, RFOT.SimDecrypt)
is defined in Fig. 5.7.
Remark 5.4. Let us confirm that one can extract the plaintext with RFOT.ExtDecrypt,
even if l 6= k.
c1 X −l − c2 sX −k = (y0 v + 2e + m) − (av + 2f )sX −k= (yX −k v + 2e + m) − (av + 2f )sX −k= (y − as)vX −k + 2(e − f sX −k ) + m= 2(es v + e − f s)X −k + m(es v + e − f s)X −k is small. We obtain (c1 X −l − c2 sX −k ) mod 2 = m.
Lemma 5.2. The below two distribution ensembles are computationally indistinguishable:{pp | RFOT.Setup(1λ ) → pp} and {pp | RFOT.SimSetup(1λ ) → (pp, td)}.
Proof. We suppose that an adversary distinguishes the two pp. Let us confirm the variable a ∈ pp. The one is randomly sampled from Rq , and the other is equal to ga · fa−1 .
If the adversary distinguishes the two a, then the adversary could break the DSPR assumption regarding Definition 2.2. It is a contradiction. We conclude that RFOT.Setup
and RFOT.SimSetup are computationally indistinguishable.
Lemma 5.3. The below two distribution ensembles are computationally indistinguishable:{(pp, pk) | RFOT.Setup(1λ ) → pp, RFOT.Keygen(pp, p) → (pk, sk)} and{(pp, pk) | RFOT.SimSetup(1λ ) → (pp, td), RFOT.SimKeygen(pp, td, p) → (pk, sk)}.
Proof. The difference between RFOT.Keygen and RFOT.SimKeygen is each function that
outputs each proof. One is NIZK.Prove. The other is NIZK.Simulate. The proofs by5.2. RING FRACTIONAL OBLIVIOUS TRANSFER

79• RFOT.SimSetup(1λ ) → (pp, td)
1. Compute(crsK , tdK ) ← NIZK.SimSetup(1λ , RK ).
2. Compute(crsE , tdE ) ← NIZK.SimSetup(1λ , RE ).

• RFOT.ExtDecrypt(pp, td, sk, c) → m

3. Compute(a, B, ga , fa ) = IBE.MasterKeygen(d, q).

1. Parse sk as (1/n, s, es , k, πK ).

4. Set tdI = (B, ga , fa ).

2. Parse c as (l, c1 , c2 , πE ).

5. Set pp = (crsK , crsE , a).

3. Output
m = (c1 X −l − c2 sX −k ) mod 2.

6. Set td = (tdK , tdE , tdI ).
7. Output (pp, td).
• RFOT.SimKeygen(pp, td, 1/n) → (pk, sk)
1. Parse pp as (crsK , crsE , a).
2. Parse td as (tdK , tdE , tdI ).
$3. Set s, es ←− χ.

• RFOT.SimDecrypt(pp, td, sk, b) → sk0
1. Parse pp as (crsK , crsE , a).
2. Parse td as (tdK , tdE , tdI ).
3. Parse tdI as (B, ga , fa ).
4. Parse sk as (1/n, s, es , k, πK ).
5. If b = 0,

4. Compute y = as + 2es .
$5. Set k ←− {1, . . . , n}.
6. Compute y0 = yX −k .
7. Compute
πK = NIZK.Simulate(crsK , tdK , (a, y0 )).

– Compute(s0 , e0s ) = IBE.Extract(B, y0 )– Set sk0 = (1/n, s0 , e0s , k, πK ).
6. If b = 1, then output sk.

8. Set pk = (1/n, a, y0 , πK ).
9. Set sk = (1/n, s, es , k, πK ).
10. Output key pair (pk, sk).
• RFOT.SimEncrypt(pp, td, pk, b, m0 ) → c
1. Parse pp as (crsK , crsE , a).
2. Parse td as (tdK , tdE , tdI ).
3. Parse pk as (1/n, a, y0 , πK ).
$4. Set l ←− {1, . . . , n}.
5. If b = 0, then$– Set (c1 , c2 ) ←− C.
– Compute πE = NIZK.ExtSimulate(crsE , tdI , (c1 , c2 , a, y0 )).
6. If b = 1, then
– Compute c01 = y0 v + 2e + m0 , c2 = av + 2f, c1 = c01 X l .
– Compute πE = NIZK.Prove(crsE , (c1 , c2 , a, y0 ), (m0 , v, e, f )).
7. Output c = (l, c1 , c2 , πE ).

Figure 5.7: Simulator of the ring fractional oblivious transfer

80 CHAPTER 5. ANONYMOUS PROBABILISTIC PAYMENT IN PAYMENT HUB
NIZK.Prove and NIZK.Simulate are computationally indistinguishable because NIZK scheme
satisfies zero-knowledge. We conclude that the lemma holds.
Lemma 5.4 (Fractional hiding). The scheme of Definition 5.5 holds the fractional hidingof Definition 5.3.
Proof. Let us compare EHreal with EHideal . There are two differences between the two ensembles. The one is NIZK.Prove or NIZK.ExtSimulate. These proofs are indistinguishable
from Lemma 5.1.
The other difference is the encryption or random sampling. c01 = y0 v + 2e + m0 , c1 =$c01 X l , c2 = av + 2f in EHreal or (c1 , c2 ) ←− C in EHideal . If an adversary A can distinguish EHreal
and EHideal , then A could distinguish the true ciphertext (c1 , c2 ) from the randomly sam$pled element (c1 , c2 ) ←− C. This situation goes against the RLWE assumption regarding
Definition 2.1. We conclude that EHreal and EHideal are indistinguishable. The scheme holds
the fractional hiding.

Lemma 5.5 (Fractional binding). The scheme of Definition 5.5 holds the fractional hidingof Definition 5.4.
Proof. Let us compare EBreal with EBideal . RFOT.Keygen and RFOT.SimKeygen are computationally indistinguishable because of Lemma 5.3. RFOT.ExtDecrypt outputs a uniqueplaintext m for a valid ciphertext even if l 6= k. The simulated secret key sk0 is distributed independently of the actual secret key sk. When b = 1, output the actual secret
key itself. When b = 0, a different secret key (s0 , e0s ) is output, satisfying the relationshipy0 = as0 + 2e0s with the fixed public key (a, y0 ) with IBE.Extract. We conclude that thescheme holds the fractional binding.

5.3

Protocol and security

This section presents the protocols, the ideal functionalities, the theorems that each protocol realizes each ideal functionality, and the proofs regarding the puzzle solver andpuzzle promise. We present a simulation-based proof of the real/ideal world paradigm.
We build simulators in the cases of each corrupt participant. We discuss the indistinguishability of the game sequence by using a hybrid argument. The discussion is based on5.3. PROTOCOL AND SECURITY

81

TumbleBit [HAB+ 17, HAB+ 16]. We also combine the DAM scheme [CGL+ 17, CGL+ 16]
regarding the puzzle solver protocol related to RFOT.

5.3.1

Puzzle solver protocol

We present the puzzle solver protocol, the ideal functionality, the theorem, and the proof.
We show the puzzle solver protocol in Fig. 5.8 and the ideal functionality in Fig. 5.9.
We also show the simulators in Fig. 5.10 and Fig. 5.11. The simulator in Fig. 5.10
corresponds to the corrupt Alice. The simulator in Fig. 5.11 corresponds to the corrupt
the tumbler. Let us present the quick look at the protocol, the overview of the ideal
functionality, and proof sketch as the below paragraphs.

Quick look at the protocol. We change the procedure by the RSA encryption in
TumbleBit [HAB+ 17,HAB+ 16], into the one by the RLWE encryption. Also, we combine
RFOT with the procedure. The tumbler and Alice interact at the protocol. We use a
cut-and-choose technique. Alice creates real puzzles and fake puzzles, respectively.
At Step 1, She further masks the masked puzzle (ciphertext) she receives for the real
puzzles. She creates ciphertext by randomly choosing a plaintext by herself. She adds
this to the puzzle. At Step 2, she creates a ciphertext from randomly chosen plaintext
for the fake puzzles. She does not include the received puzzle in the fake puzzles. At
Step 3, she mixes these puzzles and executes the RFOT encryption. She permutes andmixes real puzzles and fake puzzles. These puzzles are just the RLWE ciphertexts. She
chooses the integer l randomly and shifts all puzzles by the single amount l. In this way,
she produces the RFOT ciphertext from the RLWE ciphertexts. She passes the puzzles
to the tumbler. At Step 4, the tumbler decrypts all the puzzles it receives. If the puzzles
are miss/error, then the tumbler cannot obtain the correct message. In this case, thetumbler aborts. (Even if the tumbler chooses s randomly, she will notice that it does
not match her plaintext at Step 7. Moreover, the tumbler does not know which puzzle
is in the fake set at this stage.) The tumbler creates a ciphertext c for the decrypted
message by using the symmetric key encryption. The tumbler also selects the hash value
h of k randomly. The tumbler sends these (c, h) to her for commitment. At Step 5, uponreceiving the commitment (c, h), she informs the tumbler of which puzzle belongs to thefake set. She sends a message and randomness to the tumbler for opening. At Step 6,

82 CHAPTER 5. ANONYMOUS PROBABILISTIC PAYMENT IN PAYMENT HUB
the tumbler verifies the received message and randomness, by matching the ciphertext
received earlier. If all can be verified correctly, the tumbler sends k belonging to the fakeset to her. At Step 7, she obtains s by the decryption process from the received k andthe ciphertext c of the symmetric key encryption. If s matches the original plaintext, she
continues. Otherwise, she aborts. At Step 8, she fills in the transaction on the blockchain.
Both the preimages of h and the tumbler’s signature can fulfill this transaction. She sends
the received puzzle to the tumbler and the message and the randomness in the real set.
At Step 9, the tumbler verifies the ciphertext from the received message, randomness, andpuzzle. If it is OK, the tumbler fills k in the transaction offered at Step 10. At Step 11,
she gets k from the transaction, executes the symmetric key encryption, and gets s. She
removes her message by the XOR operation and gets the message of the received puzzley.
Overview of the ideal functionality. We combine the functionality of TumbleBit
and the functionality of fractional message transfer (FMT) in the DAM scheme for theideal functionality. First, we incorporate mutual fairness into functionalities, following
TumbleBit. Fairness for Alice means that the tumbler earns one coin if and only if
she gets the correct answer. Fairness for the tumbler means that the protocol executes
decrypting the puzzle selected by her. Upon setup, the functionality receives the key fromthe tumbler and verifies if it is valid. If the verification is successful, the functionality
sends the key to her and the simulator. The functionality receives the request containing
the ciphertext from her and sends it to the tumbler at the evaluation. The functionality
receives the plaintext result from the tumbler, sends it to Alice, and pays to the tumbler.
Next, we append a probabilistic payment to the functionality, following the DAM
scheme. The functionality conveys a valid message with the probability p. Alice sends
to the functionality at the request, including the bit b and the probability pA . The
functionality confirms the bit b to determine whether there is an error. The tumbler
sends the key to the functionality together with the probability pT . The functionality
judges that a lottery is an error in the case that b = 0 or the probabilities do not match.
If b = 1 and the probabilities are equal, the functionality runs that the ciphertext is ahit with the probability p and is a failure with the probability 1 − p. The functionality
stores the judged value in Q as a pair (sid, mid). Let us confirm the behavior after thefunctionality receives the evaluation result from the tumbler. The functionality searches5.3. PROTOCOL AND SECURITY

83

Q for mid paired with sid. If mid is a hit and the message x from the tumbler is valid, thefunctionality sends her x and pays the tumbler. Otherwise, the tumbler refunds to her asa missing lottery or an error.
Proof sketch. In the case of corrupt Alice, she cannot learn more than the decrypted
message. Let us confirm the case of corrupt the tumbler. The protocol adopts a cut-andchoose technique like TumbleBit. Therefore, the tumbler must present invalid ciphertexts
to the real set while correctly responding to the fake set. The tumbler cannot obtain theinformation regarding the fake set and the real set before her opening. The probabilityof corrupt tumbler’s success is negligible.
Theorem 5.1. Let λ be a security parameter. Let d ≥ 2λ. Assume that H and H prg
are independent random oracles, and the RLWE and DSPR problems are hard. Then,the protocol in Fig. 5.8 securely realizes the functionality Fsolver in Fig. 5.9 with thefollowing security guarantees. The security for T is 1 − negl(λ) and the security for A is
1 − 1/ µ+η
− negl(λ).
η
Proof. We divide the proof into two cases. One is the case of the corrupt Alice. The otheris the case of the corrupt the tumbler. The simulator S in Fig. 5.10 corresponds to thecorrupt Alice A∗ . The simulator S in Fig. 5.11 corresponds to the corrupt the tumbler
T ∗.
Case that Alice is corrupt. We adopt a hybrid argument and confirm the indistinguishability between the real world and the ideal world. The simulator S in Fig. 5.10
plays a role of the corrupt Alice A∗ .
a0 : This is the real game.
a1 : The difference between a0 and a1 is how the key ki is computed. If x0 =RFOT.Decrypt(sk, βi ) 6= ∅ with salt, the simulator in this hybrid a1 sends ki0 = Equivocate(ci , x, hi ),instead of ki . If x0 = ∅, then both games receive refund and halt. From the assumption
regarding the random oracle, ci and hi statistically hide the encrypted message and thepreimage. The probability of the event Collision is negligible. So the view in a1 is indistinguishable from the view in a0 .
a2 : The difference between a1 and a2 is what one inputs Equivocate. The simulator
in this hybrid a2 computes Equivocate(ci , ρi , hi ) instead of Equivocate(ci , x + ri , hi ). Then

84 CHAPTER 5. ANONYMOUS PROBABILISTIC PAYMENT IN PAYMENT HUB
Public input: pk. πK in pk proves validity of pk in a one time setup phase.
Alice A. Input: puzzle y
the tumbler T . Secret input: sk
1. Prepare real puzzles R$

salt ←− {0, 1}λFor j = 1, . . . , µ:
$

$

$

$

rj ←
− {0, 1}λ , vj , ej , fj ←−χdj = RLWE.Enc(pk, salt||rj ; vj , ej , fj ) + y
2. Prepare fake values F
For i = 1, . . . , η:ρi ←− {0, 1}λ , vi , ei , fi ←−χδi = RLWE.Enc(pk, salt||ρi ; vi , ei , fi )3. Mix sets and RFOT
Permute {d1 , . . . , dµ , δ1 , . . . , δη } randomly0
and obtain {β10 , . . . , βµ+η}$l←
− {1, . . . , n}
For i = 1, . . . , µ + η:Parse βi0 as (c01 , c2 ) and set c1 = c01 X l
Set βi = (c01 , c2 )Let R be the indices of the di
Let F be the indices of the δisalt,l,β1 ,...,βµ+η−−−−−−−−−−→

4. Evaluation.
For i = 1, . . . , µ + η:
Evaluate βi : si = RFOT.Decrypt(sk, βi )Check if si = ∅ with salt. If not, abort.
Encrypt the result si :$ki ←− {0, 1}λ1ci = H prg (ki ) ⊕ si
(c1 ,h1 ),...,(cµ+η ,hµ+η )←−−−−−−−−−−−−−−
5. Identify fake set.

Commit to the keys: hi = H(ki )F,ρi ,vi ,ei fi ∀i∈F−−−−−−−−−−−→
6. Check fake set.
For all i ∈ F : Verify βi =RFOT.Encrypt(pk, salt||ρi ; vi , ei , fi , l)k ∀i∈Fi←−−−−−

If yes, reveal ki ∀i ∈ F . Else abort.

7. Check fake set.
For all i ∈ F :Verify hi = H(ki )Decrypt si = H prg (ki ) ⊕ ci
Verify si = ρi
Abort if any check fails
8. Post transaction Tpuzzle
Tpuzzle offers one coin within timewindow tw1
under condition ”the fulfilling transaction is signed
by T and has preimages of hj ∀j ∈ R”.

y,rj ,vj ,ej ,fj ∀j∈R−−−−−−−−−−−−→
9. Check βi unblind to y ∀j ∈ R
For all j ∈ R: Verify βi =RFOT.Encrypt(pk, salt||rj ; vj , ej , fj , l) + y
If not, abort.
10. Post transaction Tpuzzle
Tpuzzle contains kj ∀j ∈ R

11. Obtain puzzle solution.
For j ∈ R:
Learn kj from Tpuzzle
Decrypt sj = H prg (kj ) ⊕ cj
Verify βj = RFOT.Encrypt(pk, salt||sj ; vj , ej , fj , l) + y
Obtain solution sj + rj mod 2

Figure 5.8: Puzzle solver protocol. We model H and H prg as random oracles.

5.3. PROTOCOL AND SECURITY

85

Parties.
• A, T and adversary S.
Setup.
• Receive (Setup, pk, sk, pT ) from T .
• If pk or sk are invalid, then– do nothing.
• Else,– Send (Setup, pk) to A and S.
Evaluation.
• On input (request, sid, y, 1coin, pA , b) from A:– If b = 1 and pA = pT ,∗ Set mid = hit with probability pA or mid = miss with probability 1 − pA .
– Else if b = 0 or pA 6= pT , set mid = error.
– Send (request, sid, A, y) to T .
– Append (sid, mid) to Qid .
– Start counter twsid = 0.
• On input (evaluate, sid, A, x) from T :– Obtain mid corresponding sid from Qid .
– If mid = hit and x 6= ∅, then
∗ Send (sid, x) to A.
∗ Send (payment, sid, 1coin) to T .
– Else, send (refund, sid, 1coin) to A.
• If twsid = tw, send (refund, sid, 1coin) to A.
Figure 5.9: Ideal functionality Fsolver

86 CHAPTER 5. ANONYMOUS PROBABILISTIC PAYMENT IN PAYMENT HUB$

1. Receive salt, l, β1 , . . . , βµ+η from Adv. Choose ci ←− {0, 1}λ and hi ∈ {0, 1}λ2 fori ∈ [µ + η]. Send them to Adv.
2. Receive F, ρi , vi , ei , fi for i ∈ F .
For all i ∈ F , check if βi =RFOT.Encrypt(pk, salt||ρi ; vi , ei , fi , l). If check fails, output whatever Adv outputs, send (request, sid, y, 1coin, pA , b = 0) to Fsolver and halt. Else, run ki0 =Equivocate(ci , ρi , hi ). Send ki0 for i ∈ F to Adv.
3. Receive y, ri , vi , ei , fi for i ∈ R. Check if βi = RFOT.Encrypt(pk, salt||ri ; vi , ei , fi , l) +y for all i ∈ R. If the check succeeds, transaction Tpuzzle is correctly formed, executeas follows.
• Send (request, sid, y, 1coin, pA , b = 1) to Fsolver and obtain x or refund.
• If obtain x,– Run ki0 = Equivocate(ci , x + ri , hi ) with i ∈ R.
– Send transaction Tsolve with values ki0 .
• Else if obtain refund, halt.
Else, checks have failed so output whatever(request, sid, y, 1coin, pA , b = 0) to Fsolver and halt.

Adv

outputs,

send

Procedure random oracle simulation for QH , QH prg is as follows:
Receive query q for H(resp., H prg ):1. If query q ∈ QH (resp., H prg ), retrieve entry (q, a) from the set and output a.
$

2. Else a ←− {0, 1}λ2 (resp., λ1 ), and (q, a) to QH (resp., H prg ) and output a.
Procedure Equivocate(ci , mi , hi ) is stated as below:$

1. ki0 ←− {0, 1}λ1 . If ki0 ∈ QH or QH prg , output Collision and abort.
2. Compute ai = ci ⊕ mi , then append (ki0 , ai ) to QH prg .
3. Append (ki0 , hi ) to QH .
4. Output ki0 .
Figure 5.10: Simulator for the puzzle solver protocol in the case that Alice is corrupt

5.3. PROTOCOL AND SECURITY

87

1. If pk and sk are valid, S receives (request, sid, A, y) from Fsolver .
2. Compute x0 = RFOT.ExtDecrypt(pp, td, sk, y) and extract x from x0 = salt||x.
3. Receiving {ki } for all i ∈ F from Adv, S checks if all {ci }i∈F are correct. If yes, S
sends message (evaluate, sid, A, x) to Fsolver . Then, Fsolver sends the puzzle solution
x or refund to A. Meanwhile, S sends Tpuzzle to Adv.
4. S receives Tsolve from Adv. If all keys {ki } ∀i ∈ R decrypt ciphertexts ci , notcontaining valid puzzle solutions, then S outputs BAD and aborts. Else, S outputs
whatever Adv outputs and halts.
Figure 5.11: Simulator for the puzzle solver protocol in the case that the tumbler iscorruptx is a valid message of y. x is taken from Fsolver after Adv has sent Tpuzzle . Both games
receive refund instead of x and halt. The view in a2 is generated by just a single value x.
The view in a2 is indistinguishable from the view in a1 . The simulator in a2 corresponds
to Simulator S in Fig. 5.10.

Case that the tumbler is corrupt. The simulator S in Fig. 5.11 plays a role of thecorrupt the tumbler T ∗ . Because of the RLWE assumption, all ciphertexts β1 , . . . , βµ+η are
uniformly distributed. They reveal no information about the sets F and R. Furthermore,
H and H prg are modeled as a random oracle. The encryption of the key is binding.
It is impossible for an adversary Adv to change the values after the sets F and R arerevealed. We denote the event that an adversary presumes the set F as the event BAD.
The probability of the event BAD is as follows.
Pr[BAD] =

1
µ+η
η

+

1
2λ1

The difference between the transcript by the simulator S in Fig. 5.11 in the ideal
world and the one in the real world is if the event BAD happens or not. The two worlds
are distinguishable with the negligible probability Pr[BAD].
We conclude that the protocol in Fig. 5.8 securely realizes the functionality Fsolver in
Fig. 5.9.

88 CHAPTER 5. ANONYMOUS PROBABILISTIC PAYMENT IN PAYMENT HUB

5.3.2

Puzzle promise protocol

We present the puzzle promise protocol, the ideal functionality, the theorem, and theproof. We show the protocol in Fig. 5.12 and the ideal functionality in Fig. 5.13. We also
show the simulators in Fig. 5.14 and Fig. 5.15. The simulator in Fig. 5.14 corresponds
to the corrupt Bob. The simulator in Fig. 5.15 corresponds to the corrupt the tumbler.
Let us present the quick look at the protocol, the overview of the ideal functionality, andproof sketch as the below paragraphs.

Quick look at the protocol. The tumbler and Bob interact at the protocol. As withthe puzzle solver protocol, we also use the cut-and-choose technique. At Step 1, thetumbler sets up the escrow transaction. From Step 2 to Step 4, Bob creates real and fakehash values and sends the shuffled hash values to the tumbler. At Step 5, the tumbler
signs everything does corresponding puzzles and sends these with promises. At Step 6,
he opens a fake set to the tumbler. At Step 7, the tumbler verifies them and presents
the puzzle answers corresponding to the fake values. At Step 8, he verifies these answers.
Note that we must arrange a situation where it is sufficient for him to send one of thereal puzzles to Alice. At Step 9, the tumbler sends the difference from other elements andproves that the ciphertext is zero. The tumbler uses the non-interactive zero-knowledge
proof for the relation R0 . At Step 10 and 12, he can agree that it is sufficient to send
either one to her by verifying the proof and the difference. At Step 11, the tumbler posts
the transaction.
The difference from TumbleBit is the adoption of the RLWE encryption instead of
the RSA encryption. The RLWE encryption is probabilistic encryption, unlike the RSA
encryption. One can verify the ciphertext by its plaintext and randomness by reproducing and verifying it with the encryption algorithm. We make the tumbler encrypt thisrandomness with the symmetric key encryption and pass it to Bob. Let the key of thesymmetric key encryption be the plaintext itself. Even if we adopt the RLWE encryption,
we can use the only plaintext to answer the puzzle by this trick.

Overview of the ideal functionality. We show the ideal functionality in Fig. 5.13.
This ideal functionality is the same as TumbleBit. Let us outline the ideal functionality
briefly. The ideal functionality plays a role as a trusted third party. The functionality

5.3. PROTOCOL AND SECURITY

89

signs a transaction by calling the signature oracle. It is fairness for Bob that he obtains
a promise that contains a valid signature for at least one genuine transaction. It is
fairness for the tumbler that he has no knowledge of anything but the fake transaction
signature. Upon receiving fake and real transactions from him, the functionality storesthem and sends fake transactions to the tumbler. Upon receiving a promise from the
tumbler, the functionality signs the fake transactions. The functionality records faketransaction signatures and the promises to real transactions. Finally, the functionality
sends the promises to him. Upon receiving the signature verification from any party, thefunctionality tells them that the functionality has already recorded the fake transactions’signatures. Since the functionality does not store real transactions, the functionality
records them.
Proof sketch. Regarding corrupt Bob, we change the RSA encryption in the simulator
in TumbleBit into the RLWE encryption. We show the simulator in Fig. 5.14. The
simulator in Fig. 5.15 is the same as TumbleBit for corrupt the tumbler. The proof in
TumbleBit holds in the same way.
Theorem 5.2. Let λ be a security parameter. Let d ≥ 2λ. Assume that H, H 0 , and H shk
are independent random oracles, and the RLWE and DSPR problems are hard. Then, theprotocol in Fig. 5.12 securely realizes the functionality Fpromise sign in Fig. 5.13 with thefollowing security guarantees. The security for T is 1 − negl(λ) and the security for B is
1 − 1/ µ+η
− negl(λ).
η
Proof. We divide the proof into two cases. One is the case of corrupt Bob. The other isthe case of the corrupt the tumbler.
Case that Bob is corrupt. Let us confirm the indistinguishability between the realworld and the ideal world with a hybrid argument. The simulator S in Fig. 5.14 plays arole of the corrupt Bob B ∗ .
a0 : This is the real world.
a0.5 : When the simulator receives hR , hF and {β1 , . . . , βµ+η } from B ∗ , the simulator
checks the set of queries QH and extracts the pair (salt||R, hR ) and (salt||F, hF ). If there
is no pair regarding hR and hF , then the simulator aborts. This abort is the difference between a0 and a0.5 . The probability of the abort is 1/2λ2 , so the two games are statistically90 CHAPTER 5. ANONYMOUS PROBABILISTIC PAYMENT IN PAYMENT HUB
Public input: (pk, PKeph
T ). πK in pk proves validity of pk in a one time setup phase.
eph
T chooses a fresh ephemeral ECDSA-Secp256k1 key (SKeph
T , PKT ).
Bob B
the tumbler T . Secret input: sk
1. Set up Tescr(T ,B)
Sign but do not post transaction Tescr(T ,B)
timelocked for tw2 offering one coin under
the condition: ”the fulfilling transaction
Tescr(T ,B)←−−−−−−

is signed under key PKeph
and key PKB ”
T

2. Prepare µ real unsigned Tescr(T ,B) .
For i ∈ 1, . . . , µ:
$

i
0
i
ρi ←
− {0, 1}λ , Tescr(T,B) = CashOutFormat(ρi ), hti = H (Tfulfill ).
3. Prepare fake set.
For i ∈ 1, . . . , η:$ri ←− {0, 1}λ , f ti = H 0 (FakeFormat||ri ).
4. Mix sets.
Permute {f t1 , . . . , f tη , ht1 , . . . , htµ } randomly
β1 ,...,βµ+η

and obtain {β1 , . . . , βµ+η }−−−−−−−→Let R be the indices of the hti
Let F be the indices of the f ti$

Choose salt ←− {0, 1}λhR = H(salt||R), hF = H(salt||F )hR ,hF−−−−→
5. Evaluation.
For i = 1, . . . , µ + η:
ECDSA sign βi to get σi = Sig(SKeph
T , βi )$(c1 , z1 , v̄1 , ē1 , f¯1 ), . . . ,(cµ+η ,zµ+η ,v̄µ+η ,ēµ+η ,f¯µ+η )←−−−−−−−−−−−−−−−−−−−
6. Identify fake set.

$i ←− {0, 1}λ , vi , ei , fi ←− χ.
Create promise ci = H shk (i ) ⊕ σi
Encrypt v̄i = Enc(vi ; i ), ēi = Enc(ei ; i )and f¯i = Enc(fi ; i )Create puzzle zi = RLWE.Enc(pk, 0λ ||i ; vi , ei , fi )R,F,ri ∀i∈F,salt−−−−−−−−−−→
7. Check fake set.
Check hR = H(salt||R) and hF = H(salt||F )For all i ∈ F : Verify βi = H 0 (FakeFormat||ri ) ∀i∈Fi←−−−−−

Abort if any check fails
8. Check fake set.
For all i ∈ F :Validate i ∈ {0, 1}λDecrypt vi = Dec(v̄i ; i ), ei = Dec(ēi ; i ), fi = Dec(f¯i ; i )Validate puzzle zi = RLWE.Enc(pk, 0λ ||i ; vi , ei , fi )Validate promise ci :Decrypt σi = H shk (i ) ⊕ ci
0
Verify σi such that (PKeph
T , H (f ti ), σi ) = 1
Abort if any check fails
9. Prepare differences
For R = {j1 , . . . , jµ }:Set d2 = j2 − j1 , . . . , dµ = jµ − jµ−1
d2 ,...,dµ ,π2 ,...,πµ←−−−−−−−−−−−

Set πj proving zj + dj ∈ C0

10. Difference test.
For R = {j1 , . . . , jµ }: Verify πjAbort if any check fails
11. Post transaction Tescr(T ,B)
12. Start Payment Phase.
$

Set zt = zj1 . mb ←− {0, 1}λ .
Send ztb = zt + RLWE.Enc(pk, 0λ ||mb ) to Alice A.

Figure 5.12: Puzzle promise protocol. We model H, H 0 and H shk as random oracles.

5.3. PROTOCOL AND SECURITY

91

Parties.
• B, T and adversary S.
Setup.
• Inform Fpromise sign if T is corrupt or honest.
Key generation.
• Receive message (Keygen, B) from B.
• Send (Keygen, B) to S.
• Receive response (PKeph
T , Sig) from S.
• Send (Setup, PKephT ) to B.
• Record (PKeph
T , Sig).
Signature request.
0• Receive message (sign request, PKeph, {FkTxni }i∈[η] , {mi }i∈[µ] ) from B.
T0• If PKeph
6= PKephT
T , then do nothing.
• If ∀i, FkTxni compiles with FakeFormat, then send (sign request, B, PKeph
T , {FkTxni }i∈[η] ) to T .
• Else, do nothing.
Promise.
• Receive (promise, B, ans, Set) from T .
• If ans = no, then set all signatures to ⊥.
• Else, if Set 6= ∅, compute signatures as follows:– If T is honest, Set FkSigni = Sig(FkTxni , PKephT ) for i ∈ [η].
– Else T is corrupt, Send (Sign, FkTxni , B) to adversary S, and obtain respective signatures.
– Abort if there is a recorded entry (FkTxni , FkSigni , PKeph
T , 0).
eph– Record entries (FkTxni , FkSigni , PKeph
T , 1) and (mj , PKT , promise).

• Send (sign promise, ans) to B.
Signature verification.
0• Receive (Verify, sid, m, σ, PKeph) from any party P:
T0– If PKeph
6= PKephT
T , then do nothing.
– Else, if T is honest:∗ If there is a recorded entry (m, σ, PKeph
T , 1), then set ver = 1. (completeness condition)∗ If there is no recorded entry (m, σ, PKeph
T , 1), then set ver = 0 and set the entryeph(m, σ, PKT , 0). (unforgeability condition)– Else, if T is corrupt, then let ver be set by S. (corrupt signer case)• Send (Verify, sid, m, σ, ver) from party P.

Figure 5.13: Ideal functionality Fpromise sign (Fig. 8 in [HAB+ 16])

92 CHAPTER 5. ANONYMOUS PROBABILISTIC PAYMENT IN PAYMENT HUB• Simulator S simulates the messages that Adversary B ∗ expects from T as follows.
1. Inform Fpromise sign that T is honest.
eph
λ2. Compute (PKeph
T , SKT ) = Keygen(1 ).

3. Send PKeph
to B ∗ and Fpromise sign .
T• Receive hR , hF and {β1 , . . . , βµ+η } from B ∗ , runs as follows:
1. Extracts the sets F, R from the random oracle, checking the set of queries QH and extracting
the pair (salt||R, hR ) and (salt||F, hF ). If there is no pair regarding hR , hF , then set R =F = ⊥.
2. Send B ∗ the pair (ci , zi ) which is made as:$(a) For all i, ci ←− {0, 1}s .
$(b) For i ∈ F, i ←− {0, 1}λ and zi = RLWE.Enc(pk, 0λ ||i ).
$(c) For R = {j1 , . . . , jµ }, zj1 , d2 , . . . , dµ ←− {0, 1}λ and zji = RLWE.Enc(pk, 0λ ||di ) +λ(0 ||zji−1 )• Receive (F 0 , R0 , ri ) from B ∗ , runs as follows:
1. If F 0 6= F or R0 6= R, then abort.
2. If any (FakeFortmat||ri , βi ) 6∈ QH 0 for i ∈ F , then abort.
3. For j ∈ R, set mj = γ if (γ, βi ) ∈ QH 0 . Else set mj = ⊥.
4. Send to Fpromise sign the message (sign request, PKeph
T , {FakeFormat||ri }i∈F , {mj }j∈R ).
5. Obtain response (promise, B ∗ , ans, {FkSign}i∈[η] ).
6. If ans = no, then halt and output whatever B ∗ outputs.
7. Compute hjl = cjl ⊕ FkSignl .
8. Store the pair (jl , hjl ) in QH shk .
9. Send i for i ∈ F and the differences d2 , . . . , dµ .
• Finally, output whatever B ∗ outputs and halt.
Procedure RO1, which is the random oracle simulation for H is as follows:
1. Receive query q for H.
2. If q ∈ QH , retrieve (γ, a) for QH .
$3. Else a ←− {0, 1}λ2 .
4. Append (γ, a) to QH .
5. Output a.
Procedure RO2, which is the random oracle simulation for H shk is as follows:
1. Receive query q for H shk .
2. If q ∈ QH shk , retrieve (γ, a) for QH shk .
3. If γ = RLWE.Dec(sk, zi ) for some i ∈ R and (γ, a) 6∈ QH shk , then output RLWE failure.
$

4. Else a ←− {0, 1}λ2 .
5. Append (γ, a) to QH shk .
6. Output a.

Figure 5.14: Simulator for the puzzle promise protocol in the case that Bob is corrupt

5.3. PROTOCOL AND SECURITY93

The simulator S executes T ∗ internally.
First, we introduce the algorithm Sig(mi , PKephT ) as follows.
• Lfake , Lreal are internal variables.
• If (mi , βi , σi ) ∈ Lfake , output signature (βi , σi ).
• Else if (mi , βi , σi ) ∈ Lreal , then append (mi , βi ) to QH 0 , and output signature (βi , σi ).
• Else, abort.
eph
Receive (Keygen, B). Send request to T ∗ . Obtain PKeph
T . Send (PKT , Sig) to Fpromise sign .
ephReceive (sign request, B, PKT , {FkTxni }i∈[η] ).
Pick randomly F, R with F ∩ R = ∅. Compute the RO outputs hF , hR and β1 , . . . , βµ+η . Send them toT ∗.
Receive a pair (ci , zi ) from T ∗ :1. Extract i by queries to H shk
2. Let σi be the signature decrypted from ci with i
3. If ci , zi , i , βi , σi for i ∈ F are valid, store (FkTxni , βi , σi ) in Lfake .
4. If ci , zi , i , βi , σi for i ∈ F are valid, append i to set Set and append (βi , σi ) to Lreal . If such i does
not exist, set real = no.
$

For all i ∈ F , ri ←−. Send ri to T ∗ . Append the pair (FkTxni ||ri , βi ) to QH 0 .
Receive the openings 0i to fake messages i ∈ F . Obtain σi0 with 0i , ci . If any (i, ci , zi , 0i , βi , σi0 ) is invalid,
send (promise, B, no, ⊥) to Fpromise sign . Else, send (promise, B, yes, Set) to Fpromise sign .
Now let us confirm the below two cases:
Case 1: If any i ∈ F such that (i, 0i , βi , σi0 ) is valid but (·, βi , σi0 ) 6∈ Lfake , then abort and output binding fail.
Case 2: Suppose that all i ∈ F such that (i, 0i , βi , σi0 ) is valid and (·, βi , σi0 ) ∈ Lfake .
1. If real = no, abort and output cut and choose fail.
2. Else, set variables Lfake , Lreal for the algorithm Sig.

Figure 5.15: Simulator for the puzzle promise protocol in the case that the tumbler iscorrupt (Appendix F in [HAB+ 16])

94 CHAPTER 5. ANONYMOUS PROBABILISTIC PAYMENT IN PAYMENT HUB
close.
$

a1 : Instead of computing ci = H shk (i ) ⊕ σi , the simulator chooses ci ←− {0, 1}s andstores the pair (i , ci ⊕ σi ) in QH shk in a1 . The both games a0.5 and a1 are statisticallyclose because H shk is unpredictable.
a2 : Instead of computing zji = RLWE.Enc(pk, ji ), the simulator randomly chooses
zj1 , d2 , . . . , dµ from {0, 1}λ and computes zji = RLWE.Enc(pk, di ) + zji−1 . Let us check for
RLWE failure. According to the RLWE assumption, the ciphertext zji cannot be distinguished from a uniformly random value. The probability that the plaintext presented will
match is 1/2λ . It is negligible. Note that a2 computes neither i nor σi for real messages
mi with i ∈ R.
a3 : Instead of the actual signature, the simulator sends the message(sign request, PKeph
T , {FakeFormat||ri }i∈F , {mj }j∈R )to Fpromise sign . Then, the simulator S obtains the response (promise, B ∗ , ans, {FkSign}i∈[η] )and uses σi = FkSigni . a2 and a3 is identical from the view of B ∗ . a3 is the simulator S
in Fig. 5.14 itself.
We conclude that the transcript by the simulator S in Fig. 5.14 is indistinguishable
from the one in the real world.
Remark 5.5. The below lemma shows that B ∗ cannot forge a valid signature σ for a valid
message Tcash(T ,B) .
Lemma 5.6 ( Lemma 3 in [HAB+ 16] ). If ECDSA is an existentially unforgeable signaturescheme, then Pr[Eforge ] is negligible.
Case that the tumbler is corrupt. The simulator S in Fig. 5.15 plays a role ofthe corrupt the tumbler T ∗ . The difference between the real world and the ideal worldis whether the simulator S in Fig. 5.15 stops. Let us confirm the probability that thesimulator will stop for each event.
• Event cut and choose fail:Pr[cut and choose fail] =

1
µ+η
η

+

1
2λ1

5.4. CONCLUSION95• Event binding fail:Pr[binding fail] =1
2λ2

We conclude that the protocol in Fig. 5.12 securely realizes the functionality Fpromise signin Fig. 5.13.

5.4

Conclusion

Scalability and privacy protection are significant problems with blockchain. In this work,
we have proposed an anonymous probabilistic payment to solve these simultaneously.
Our proposal is not restricted to any particular cryptocurrency. We have mediated thetumbler of the payment channel hub between a payer and a payee. A cryptographic
puzzle plays a role in controlling the intermediation and the execution of transactions.
Masking the puzzle allows the payer and the payee to unlink their payments. Besides, wehave introduced a novel fractional oblivious transfer based on the RLWE encryption. We
have adopted it for the probabilistic payment. The proposed protocol realizes the ideal
functionalities discussed in TumbleBit (NDSS 2017).

96 CHAPTER 5. ANONYMOUS PROBABILISTIC PAYMENT IN PAYMENT HUB

Chapter 6
Conclusion
Blockchain is an underlying technology that constitutes our digital society. Privacy protection is a significant theme in society. Homomorphic encryption is a promising technology
for privacy protection. Confidentiality and unlinkability are challenging issues regarding privacy-preserving blockchain. High throughput is also a challenging issue regarding
blockchain. A permissionless blockchain has a much lower throughput than permissioned
blockchain. We hope that blockchain will be widely available in the real world. Privacypreserving and high throughput blockchain are desirable. In this thesis, we have studied
privacy-preserving blockchain with homomorphic encryption. First, we achieve a privacypreserving and verifiable permissioned blockchain. Next, we realize a confidential andauditable permissionless blockchain. Finally, we propose an unlinkable and high throughput permissionless blockchain.

Traceability in permissioned blockchain. We have achieved privacy protection andhigh transparency in a permissioned blockchain. Meaningful traceability consists of threeproperties. These are trade privacy, preservation, and noninvolvement. This work is
a proposal wherein both preservation and noninvolvement hold while protecting tradeprivacy. We have constructed a traceability model based on the three properties andencrypted it with the RLWE encryption. Moreover, we have encrypted the model withsomewhat homomorphic encryption by using the ring isomorphism encoding. We haveconfirmed that the encrypted model is feasible. We have shown the protocol to verify
that the plaintext is equal to zero using non-interactive zero-knowledge proof.
97

98

CHAPTER 6. CONCLUSION

Confidential and auditable payments. We have constructed a confidential and auditable payment scheme. The proposed scheme allows a court or an authority to audit
transactions while keeping the transaction information confidential. Every participant
writes the ciphertexts of transaction information in a ledger. We have confirmed the concealment of the transaction information and the soundness of the scheme. The proposed
scheme is secure in this sense. The court or the authority can forcibly reveal transaction
information with a unique secret key. In this sense, the proposed scheme is auditable.
Anonymous probabilistic payment in payment hub. Scalability and privacy protection are significant problems. To solve these simultaneously, we have proposed ananonymous probabilistic payment. Our proposal is not restricted to any particular cryptocurrency. We have mediated the tumbler of the payment channel hub between a payer
and a payee. A cryptographic puzzle plays a role in controlling the intermediation andexecution of transactions. Masking the puzzle allows the payer and the payee to unlink
their payments. Besides, we have introduced a novel fractional oblivious transfer based on
the RLWE encryption. We have adopted it for the probabilistic payment. The proposed
protocol realizes the ideal functionalities discussed in TumbleBit (NDSS 2017).

Bibliography[AAUC18]

Abbas Acar, Hidayet Aksu, A. Selcuk Uluagac, and Mauro Conti. A survey
on homomorphic encryption schemes: Theory and implementation. ACM
Comput. Surv., 51(4), July 2018.

[ABB+ 18]

Elli Androulaki, Artem Barger, Vita Bortnikov, Christian Cachin, Konstantinos Christidis, Angelo De Caro, David Enyeart, Christopher Ferris,
Gennady Laventman, Yacov Manevich, et al. Hyperledger fabric: a distributed operating system for permissioned blockchains. In Proceedings of
the Thirteenth EuroSys Conference, page 30. ACM, 2018.

[ABC20]Ghada Almashaqbeh, Allison Bishop, and Justin Cappos. Microcash:
Practical concurrent processing of micropayments. In Joseph Bonneau
and Nadia Heninger, editors, Financial Cryptography and Data Security,
pages 227–244, Cham, 2020. Springer International Publishing.

[ACDCKK18] Elli Androulaki, Christian Cachin, Angelo De Caro, and Eleftherios
Kokoris-Kogias. Channels: Horizontal scaling and confidentiality on permissioned blockchains. In Javier Lopez, Jianying Zhou, and Miguel Soriano, editors, Computer Security, pages 111–131, Cham, 2018. Springer
International Publishing.
[ADPS16]

Erdem Alkim, Léo Ducas, Thomas Pöppelmann, and Peter Schwabe. Postquantum key exchange—a new hope. In 25th USENIX Security Symposium(USENIX Security 16), pages 327–343, Austin, TX, August 2016. USENIX
Association.

[BAZB20]

Benedikt Bünz, Shashank Agrawal, Mahdi Zamani, and Dan Boneh.
Zether: Towards privacy in a smart contract world. In Joseph Bonneau
99

100

BIBLIOGRAPHY
and Nadia Heninger, editors, Financial Cryptography and Data Security,
pages 423–443, Cham, 2020. Springer International Publishing.

[BBB+ 18]

Benedikt Bünz, Jonathan Bootle, Dan Boneh, Andrew Poelstra, Pieter
Wuille, and Greg Maxwell. Bulletproofs: Short proofs for confidential
transactions and more. In 2018 IEEE Symposium on Security and Privacy(SP), pages 315–334. IEEE, 2018.

[BCK+ 14]Fabrice Benhamouda, Jan Camenisch, Stephan Krenn, Vadim Lyubashevsky, and Gregory Neven. Better zero-knowledge proofs for lattice
encryption and their application to group signatures. In Palash Sarkar
and Tetsu Iwata, editors, Advances in Cryptology – ASIACRYPT 2014,
pages 551–572, Berlin, Heidelberg, 2014. Springer Berlin Heidelberg.

[BCNS15]

J. W. Bos, C. Costello, M. Naehrig, and D. Stebila. Post-quantum key
exchange for the tls protocol from the ring learning with errors problem.
In 2015 IEEE Symposium on Security and Privacy, pages 553–570, May
2015.

[BD18]

Zvika Brakerski and Nico Döttling.

Two-message statistically sender-

private ot from lwe. In Amos Beimel and Stefan Dziembowski, editors,
Theory of Cryptography, pages 370–390, Cham, 2018. Springer International Publishing.
[BDLN16]

Carsten Baum, Ivan Damgård, Kasper Green Larsen, and Michael Nielsen.
How to prove knowledge of small secrets.

In Matthew Robshaw andJonathan Katz, editors, Advances in Cryptology – CRYPTO 2016, pages
478–498, Berlin, Heidelberg, 2016. Springer Berlin Heidelberg.
[BG13]

Techane Bosona and Girma Gebresenbet. Food traceability as an integral
part of logistics management in food and agricultural supply chain. Foodcontrol, 33(1):32–48, 2013.

[BGN05]

Dan Boneh, Eu-Jin Goh, and Kobbi Nissim. Evaluating 2-dnf formulas on
ciphertexts. In Joe Kilian, editor, Theory of Cryptography, pages 325–341,
Berlin, Heidelberg, 2005. Springer Berlin Heidelberg.

BIBLIOGRAPHY[BGV14]

101

Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan. (leveled) fully
homomorphic encryption without bootstrapping. ACM Transactions on
Computation Theory (TOCT), 6(3):13, 2014.

[BKS19]Elette Boyle, Lisa Kohl, and Peter Scholl. Homomorphic secret sharing
from lattices without fhe. In Yuval Ishai and Vincent Rijmen, editors,
Advances in Cryptology – EUROCRYPT 2019, pages 3–33, Cham, 2019.
Springer International Publishing.

[BM90]

Mihir Bellare and Silvio Micali. Non-interactive oblivious transfer and applications. In Gilles Brassard, editor, Advances in Cryptology — CRYPTO’89 Proceedings, pages 547–557, New York, NY, 1990. Springer New York.

[BNM+ 14]

Joseph Bonneau, Arvind Narayanan, Andrew Miller, Jeremy Clark, Joshua
A. Kroll, and Edward W. Felten. Mixcoin: Anonymity for bitcoin with accountable mixes. In Nicolas Christin and Reihaneh Safavi-Naini, editors,
Financial Cryptography and Data Security, pages 486–504, Berlin, Heidelberg, 2014. Springer Berlin Heidelberg.

[BR99]

Mihir Bellare and Ronald L Rivest. Translucent cryptography—an alternative to key escrow, and its implementation via fractional oblivious transfer.
Journal of cryptology, 12(2):117–139, 1999.

[BSBHR18]

Eli Ben-Sasson, Iddo Bentov, Yinon Horesh, and Michael Riabzev. Scalable, transparent, and post-quantum secure computational integrity. IACR
Cryptology ePrint Archive, 2018:46, 2018.

[BV11]

Zvika Brakerski and Vinod Vaikuntanathan. Fully homomorphic encryption from ring-lwe and security for key dependent messages. In Phillip
Rogaway, editor, Advances in Cryptology – CRYPTO 2011, pages 505–
524, Berlin, Heidelberg, 2011. Springer Berlin Heidelberg.

[Can01]

R. Canetti. Universally composable security: a new paradigm for cryptographic protocols. In Proceedings 42nd IEEE Symposium on Foundationsof Computer Science, pages 136–145. IEEE, Oct 2001.

102[CDG+ 18]

BIBLIOGRAPHY
D. B. Cousins, G. Di Crescenzo, K. D. Gür, K. King, Y. Polyakov, K.
Rohloff, G. W. Ryan, and E. Savas. Implementing conjunction obfuscation
under entropic ring lwe. In 2018 IEEE Symposium on Security and Privacy(SP), pages 354–371, 2018.

[CGL+ 16]

Alessandro Chiesa, Matthew Green, Jingcheng Liu, Peihan Miao, Ian
Miers, and Pratyush Mishra. Decentralized anonymous micropayments.
Cryptology ePrint Archive, Report 2016/1033, 2016. https://eprint.
iacr.org/2016/1033.

[CGL+ 17]

Alessandro Chiesa, Matthew Green, Jingcheng Liu, Peihan Miao, Ian
Miers, and Pratyush Mishra. Decentralized anonymous micropayments.
In Jean-Sébastien Coron and Jesper Buus Nielsen, editors, Advances in
Cryptology – EUROCRYPT 2017, pages 609–642, Cham, 2017. Springer
International Publishing.

[CLP17]

Hao Chen, Kim Laine, and Rachel Player. Simple encrypted arithmetic
library - seal v2.1. In Michael Brenner, Kurt Rohloff, Joseph Bonneau,
Andrew Miller, Peter Y.A. Ryan, Vanessa Teague, Andrea Bracciali, Massimiliano Sala, Federico Pintore, and Markus Jakobsson, editors, Financial
Cryptography and Data Security, pages 3–18, Cham, 2017. Springer International Publishing.

[CLPX18]

Hao Chen, Kim Laine, Rachel Player, and Yuhou Xia. High-precision
arithmetic in homomorphic encryption. In Nigel P. Smart, editor, Topics in Cryptology – CT-RSA 2018, pages 116–136, Cham, 2018. Springer
International Publishing.

[DFKP13]

George Danezis, Cedric Fournet, Markulf Kohlweiss, and Bryan Parno.
Pinocchio coin: building zerocoin from a succinct pairing-based proof system. In Proceedings of the First ACM workshop on Language support for
privacy-enhancing technologies, pages 27–30. ACM, 2013.

[DLP14]Léo Ducas, Vadim Lyubashevsky, and Thomas Prest. Efficient identitybased encryption over ntru lattices. In Palash Sarkar and Tetsu Iwata,

BIBLIOGRAPHY

103

editors, Advances in Cryptology – ASIACRYPT 2014, pages 22–41, Berlin,
Heidelberg, 2014. Springer Berlin Heidelberg.
[DPW+ 16]

Johnny Dilley, Andrew Poelstra, Jonathan Wilkins, Marta Piekarska,
Ben Gorlick, and Mark Friedenbach. Strong federations: An interoperable blockchain solution to centralized third-party risks. arXiv preprint
arXiv:1612.05491, 2016.

[FS87]

Amos Fiat and Adi Shamir. How to prove yourself: Practical solutions to
identification and signature problems. In Andrew M. Odlyzko, editor, Advances in Cryptology — CRYPTO’ 86, pages 186–194, Berlin, Heidelberg,
1987. Springer Berlin Heidelberg.

[FV12]

Junfeng Fan and Frederik Vercauteren. Somewhat practical fully homomorphic encryption. IACR Cryptology ePrint Archive, 2012:144, 2012.

[GC15]

Matthias Geihs and Daniel Cabarcas. Efficient integer encoding for homomorphic encryption via ring isomorphisms. In Diego F. Aranha andAlfred Menezes, editors, Progress in Cryptology - LATINCRYPT 2014,
pages 48–63, Cham, 2015. Springer International Publishing.

[Gen09]Craig Gentry. Fully homomorphic encryption using ideal lattices. In Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing, STOC ’09, pages 169–178, New York, NY, USA, 2009. Association
for Computing Machinery.

[GGPR13]Rosario Gennaro, Craig Gentry, Bryan Parno, and Mariana Raykova.
Quadratic span programs and succinct nizks without pcps. In Thomas
Johansson and Phong Q. Nguyen, editors, Advances in Cryptology – EUROCRYPT 2013, pages 626–645, Berlin, Heidelberg, 2013. Springer Berlin
Heidelberg.

[GKKT16]

Johannes Göbel, Holger Paul Keeler, Anthony E Krzesinski, and Peter G
Taylor. Bitcoin blockchain dynamics: The selfish-mine strategy in thepresence of propagation delay. Performance Evaluation, 104:23–41, 2016.

104[GM17]

BIBLIOGRAPHY
Matthew Green and Ian Miers. Bolt: Anonymous payment channels fordecentralized currencies. In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, CCS ’17, page 473–489,
New York, NY, USA, 2017. Association for Computing Machinery.

[GM18]

Nicholas Genise and Daniele Micciancio. Faster gaussian sampling for
trapdoor lattices with arbitrary modulus. In Jesper Buus Nielsen andVincent Rijmen, editors, Advances in Cryptology – EUROCRYPT 2018,
pages 174–203, Cham, 2018. Springer International Publishing.

[GMR89]Shafi Goldwasser, Silvio Micali, and Charles Rackoff. The knowledge
complexity of interactive proof systems. SIAM Journal on computing,18(1):186–208, 1989.

[HAB+ 16]

Ethan Heilman, Leen Alshenibr, Foteini Baldimtsi, Alessandra Scafuro,and Sharon Goldberg. Tumblebit: An untrusted bitcoin-compatible anonymous payment hub. 2016. https://eprint.iacr.org/2016/575.

[HAB+ 17]

Ethan Heilman, Leen Alshenibr, Foteini Baldimtsi, Alessandra Scafuro,and Sharon Goldberg. Tumblebit: An untrusted bitcoin-compatible anonymous payment hub. In Network and Distributed System Security Symposium, 2017.

[HBG16]

Ethan Heilman, Foteini Baldimtsi, and Sharon Goldberg. Blindly signed
contracts: Anonymous on-blockchain and off-blockchain bitcoin transactions. In Jeremy Clark, Sarah Meiklejohn, Peter Y.A. Ryan, Dan Wallach,
Michael Brenner, and Kurt Rohloff, editors, Financial Cryptography andData Security, pages 43–60, Berlin, Heidelberg, 2016. Springer Berlin Heidelberg.

[Hir18]

Toufic Hirbli. Palm oil traceability: Blockchain meets supply chain. Master’s thesis, Department of Supply Chain Management, Massachusetts Institute of Technology, 2018.

[HPS98]Jeffrey Hoffstein, Jill Pipher, and Joseph H. Silverman. Ntru: A ring-based
public key cryptosystem. In Joe P. Buhler, editor, Algorithmic Number

BIBLIOGRAPHY

105

Theory, pages 267–288, Berlin, Heidelberg, 1998. Springer Berlin Heidelberg.
[HS01]

Jeffrey Hoffstein and Joseph Silverman. Optimizations for ntru. Public-Key
Cryptography and Computational Number Theory, Warsaw, pages 77–88,
2001.

[HS14]

Shai Halevi and Victor Shoup.

Helib.

Retrieved from HELib:

https://github. com. shaih/HElib, 2014.
[Kam18]Reshma Kamath. Food traceability on blockchain: Walmart’s pork andmango pilots with ibm. The Journal of the British Blockchain Association,
1(1):3712, 2018.

[LATV12]Adriana López-Alt, Eran Tromer, and Vinod Vaikuntanathan. On-thefly multiparty computation on the cloud via multikey fully homomorphic
encryption. In Proceedings of the Forty-Fourth Annual ACM Symposiumon Theory of Computing, STOC ’12, page 1219–1234, New York, NY,
USA, 2012. Association for Computing Machinery.

[LH19]

Momeng Liu and Yupu Hu. Universally composable oblivious transfer from
ideal lattice. Front. Comput. Sci., 13(4):879–906, August 2019.

[LPR13]

Vadim Lyubashevsky, Chris Peikert, and Oded Regev. On ideal lattices
and learning with errors over rings. Journal of the ACM (JACM), 60(6):43,
2013.

[Lyu09]Vadim Lyubashevsky. Fiat-shamir with aborts: Applications to lattice
and factoring-based signatures. In Mitsuru Matsui, editor, Advances in
Cryptology – ASIACRYPT 2009, pages 598–616, Berlin, Heidelberg, 2009.
Springer Berlin Heidelberg.

[Lyu12]

Vadim Lyubashevsky. Lattice signatures without trapdoors. In David
Pointcheval and Thomas Johansson, editors, Advances in Cryptology –EUROCRYPT 2012, pages 738–755, Berlin, Heidelberg, 2012. Springer
Berlin Heidelberg.

106[Max13a]BIBLIOGRAPHY
Gregory Maxwell. Coinjoin: Bitcoin privacy for the real world. URL:
https://bitcointalk.org/index.php, 2013.

[Max13b]

Gregory Maxwell. Coinswap: Transaction graph disjoint trustless trading.
CoinSwap: Transactiongraphdisjointtrustlesstrading (October 2013), 2013.

[Max15]

Greg Maxwell. Confidential transactions. URL: https://people. xiph. org/˜
greg/confidential values. txt (Accessed 09/05/2016), 2015.

[MGGR13]

Ian Miers, Christina Garman, Matthew Green, and Aviel D Rubin. Zerocoin: Anonymous distributed e-cash from bitcoin. In 2013 IEEE Symposium on Security and Privacy, pages 397–411. IEEE, 2013.

[MO19]

Tatsuo Mitani and Akira Otsuka. Traceability in permissioned blockchain.
In 2019 2nd IEEE International Conference on Blockchain, pages 286–293.
IEEE, 2019.

[MO20a]Tatsuo Mitani and Akira Otsuka. Anonymous probabilistic payment inpayment hub. Cryptology ePrint Archive, Report 2020/748, 2020. https://eprint.iacr.org/2020/748.

[MO20b]

Tatsuo Mitani and Akira Otsuka. Confidential and auditable payments.
In Matthew Bernhard, Andrea Bracciali, L. Jean Camp, Shin’ichiro Matsuo, Alana Maurushat, Peter B. Rønne, and Massimiliano Sala, editors,
Financial Cryptography and Data Security, pages 466–480, Cham, 2020.
Springer International Publishing.

[MO20c]

Tatsuo Mitani and Akira Otsuka. Traceability in permissioned blockchain.
IEEE Access, 8:21573–21588, 2020.

[MP12]

Daniele Micciancio and Chris Peikert. Trapdoors for lattices: Simpler,tighter, faster, smaller. In David Pointcheval and Thomas Johansson,
editors, Advances in Cryptology – EUROCRYPT 2012, pages 700–718,
Berlin, Heidelberg, 2012. Springer Berlin Heidelberg.

[MR07]

Daniele Micciancio and Oded Regev. Worst-case to average-case reductions
based on gaussian measures. SIAM Journal on Computing, 37(1):267–302,
2007.

BIBLIOGRAPHY[MSRL+ 19]

107

Pedro Moreno-Sanchez, Randomrun, Duc V. Le, Sarang Noether, Brandon
Goodell, and Aniket Kate. Dlsag: Non-interactive refund transactions
for interoperable payment channels in monero. Technical report, 2019.
https://eprint.iacr.org/2019/595.

[MU17]

Michael Mitzenmacher and Eli Upfal. Probability and computing: randomization and probabilistic techniques in algorithms and data analysis.
Cambridge university press, 2017.

[Nak08]Satoshi Nakamoto. Bitcoin: A peer-to-peer electronic cash system. Retrieved from Website: https://bitcoin.org/bitcoin.pdf, 2008.

[NKMS16]

Kartik Nayak, Srijan Kumar, Andrew Miller, and Elaine Shi. Stubborn
mining: Generalizing selfish mining and combining with an eclipse attack.
In 2016 IEEE European Symposium on Security and Privacy (EuroS&P),
pages 305–320. IEEE, 2016.

[NLV11]

Michael Naehrig, Kristin Lauter, and Vinod Vaikuntanathan. Can homomorphic encryption be practical? In Proceedings of the 3rd ACM Workshop
on Cloud Computing Security Workshop, CCSW ’11, pages 113–124, New
York, NY, USA, 2011. ACM.

[Noe15]

Shen Noether. Ring signature confidential transactions for monero. 2015.
https://eprint.iacr.org/2015/1098.

[PBF+ 19]

Andrew Poelstra, Adam Back, Mark Friedenbach, Gregory Maxwell, andPieter Wuille. Confidential assets. In Aviv Zohar, Ittay Eyal, Vanessa
Teague, Jeremy Clark, Andrea Bracciali, Federico Pintore, and Massimiliano Sala, editors, Financial Cryptography and Data Security, pages 43–63,
Berlin, Heidelberg, 2019. Springer Berlin Heidelberg.

[PD16]

Joseph Poon and Thaddeus Dryja. The bitcoin lightning network: Scalable
off-chain instant payments, 2016.

[Ped92]

Torben Pryds Pedersen. Non-interactive and information-theoretic secure
verifiable secret sharing. In Joan Feigenbaum, editor, Advances in Cryp-

108

BIBLIOGRAPHY
tology — CRYPTO ’91, pages 129–140, Berlin, Heidelberg, 1992. Springer
Berlin Heidelberg.

[Pei14]

Chris Peikert. Lattice cryptography for the internet. In Michele Mosca,
editor, Post-Quantum Cryptography, pages 197–219, Cham, 2014. Springer
International Publishing.

[PR17]

Omer Paneth and Guy N. Rothblum. On zero-testable homomorphic encryption and publicly verifiable non-interactive arguments. In Yael Kalai
and Leonid Reyzin, editors, Theory of Cryptography, pages 283–315, Cham,2017. Springer International Publishing.

[Ps15]

Rafael Pass and abhi shelat. Micropayments for decentralized currencies.
In Proceedings of the 22nd ACM SIGSAC Conference on Computer andCommunications Security, CCS ’15, page 207–218, New York, NY, USA,2015. Association for Computing Machinery.

[Reg09]Oded Regev. On lattices, learning with errors, random linear codes, andcryptography. J. ACM, 56(6), September 2009.

[Riv97]

Ronald L. Rivest. Electronic lottery tickets as micropayments. In Rafael
Hirschfeld, editor, Financial Cryptography, pages 307–314, Berlin, Heidelberg, 1997. Springer Berlin Heidelberg.

[RMSK14]Tim Ruffing, Pedro Moreno-Sanchez, and Aniket Kate. Coinshuffle: Practical decentralized coin mixing for bitcoin. In Miroslaw Kutylowski and
Jaideep Vaidya, editors, Computer Security - ESORICS 2014, pages 345–
364, Cham, 2014. Springer International Publishing.

[RR18]

Kurt Rohloff and Gerard Ryan. The palisade lattice cryptography library.
Retrieved from Website: https://git.njit.edu/palisade/PALISADE, 2018.

[SALY17]

Shi-Feng Sun, Man Ho Au, Joseph K. Liu, and Tsz Hon Yuen. Ringct
2.0: A compact accumulator-based (linkable ring signature) protocol forblockchain cryptocurrency monero. In Simon N. Foley, Dieter Gollmann,and Einar Snekkenes, editors, Computer Security – ESORICS 2017, pages
456–474, Cham, 2017. Springer International Publishing.

BIBLIOGRAPHY[SCG+ 14]

109

Eli Ben Sasson, Alessandro Chiesa, Christina Garman, Matthew Green,
Ian Miers, Eran Tromer, and Madars Virza. Zerocash: Decentralized
anonymous payments from bitcoin. In 2014 IEEE Symposium on Security and Privacy, pages 459–474. IEEE, 2014.

[TMSB18]

Vinesh Thiruchelvam, Alexandre Shaka Mughisha, Maryam Shahpasand,and Mervat Bamiah. Blockchain-based technology in the coffee supply
chain trade: Case of burundi coffee. Journal of Telecommunication, Electronic and Computer Engineering (JTEC), 10(3-2):121–125, 2018.

[WG18]

Karl Wüst and Arthur Gervais. Do you need a blockchain?

In 2018

Crypto Valley Conference on Blockchain Technology (CVCBT), pages 45–
54. IEEE, 2018.
[Whe97]David Wheeler. Transactions using bets. In Mark Lomas, editor, Security
Protocols, pages 89–92, Berlin, Heidelberg, 1997. Springer Berlin Heidelberg.

[Woo14]

Gavin Wood. Ethereum: A secure decentralised generalised transaction
ledger. Ethereum project yellow paper, 151:1–32, 2014.

[Wüs16]

Karl Wüst. Security of blockchain technologies. Master’s thesis, Department of Computer Science, ETH Zürich, 2016.

[YSL+ 20]Tsz Hon Yuen, Shi-Feng Sun, Joseph K. Liu, Man Ho Au, Muhammed F.
Esgin, Qingzhao Zhang, and Dawu Gu. Ringct 3.0 for blockchain confidential transaction: Shorter size and stronger security. In Joseph Bonneau
and Nadia Heninger, editors, Financial Cryptography and Data Security,
pages 464–483, Cham, 2020. Springer International Publishing.

[ZXL19]Rui Zhang, Rui Xue, and Ling Liu. Security and privacy on blockchain.
ACM Computing Surveys (CSUR), 52(3), July 2019.

[ZZD+ 15]

Jiang Zhang, Zhenfeng Zhang, Jintai Ding, Michael Snook, and ÖzgürDagdelen. Authenticated key exchange from ideal lattices. In Elisabeth Oswald and Marc Fischlin, editors, Advances in Cryptology - EUROCRYPT
2015, pages 719–751, Berlin, Heidelberg, 2015. Springer Berlin Heidelberg.