ISSN2188−1200

IMI Workshop of the Joint Usage Research Projects

Exploring Mathematical and Practical Principles of
Secure Computation and Secret Sharing
Editors: Hiroaki Anada, Yasuhiko Ikematsu, Koji Nuida,

Satsuya Ohata, Yuntao Wang

九州大学マス・フォア・インダストリ研究所

MI Lecture Note Vol.85 : Kyushu University

IMI Workshop of the Joint Usage Research Projects

Exploring Mathematical and Practical Principles of
Secure Computation and Secret Sharing

Editors:
Hiroaki Anada, Yasuhiko Ikematsu, Koji Nuida, Satsuya Ohata, Yuntao Wang

A

About MI Lecture Note Series
The Math-for-Industry (MI) Lecture Note Series is the successor to the COE Lecture
Notes, which were published for the 21st COE Program “Development of Dynamic
Mathematics with High Functionality,” sponsored by Japan’s Ministry of Education,
Culture, Sports, Science and Technology (MEXT) from 2003 to 2007. The MI Lecture Note Series has published the notes of lectures organized under the following two
programs: “Training Program for Ph.D. and New Master’s Degree in Mathematics as
Required by Industry,” adopted as a Support Program for Improving Graduate School
Education by MEXT from 2007 to 2009; and “Education-and-Research Hub for
Mathematics-for-Industry,” adopted as a Global COE Program by MEXT from 2008 to2012.
In accordance with the establishment of the Institute of Mathematics for Industry (IMI)in April 2011 and the authorization of IMI’s Joint Research Center for Advanced andFundamental Mathematics-for-Industry as a MEXT Joint Usage / Research Center in
April 2013, hereafter the MI Lecture Notes Series will publish lecture notes and proceedings by worldwide researchers of MI to contribute to the development of MI.
October 2018
Osamu Saeki
Director
Institute of Mathematics for Industry

IMI Workshop of the Joint Usage Research Projects

Exploring Mathematical and Practical Principles of Secure Computation and Secret Sharing

MI Lecture Note Vol.85, Institute of Mathematics for Industry, Kyushu University
ISSN 2188-1200
Date of issue: February 9, 2022
Editors: H
 iroaki Anada, Yasuhiko Ikematsu, Koji Nuida, Satsuya Ohata, Yuntao Wang
Publisher:
Institute of Mathematics for Industry, Kyushu University
Graduate School of Mathematics, Kyushu University
Motooka 744, Nishi-ku, Fukuoka, 819-0395, JAPANTel +81-(0)92-802-4402, Fax +81-(0)92-802-4405
URL https://www.imi.kyushu-u.ac.jp/

BPreface
As operation of the ultra-high speed and ultra-low delay fifth generation communication
service begins in countries of the world, the expectation to a cryptographic technology
increases in our society. For example, there is demand of treating data with a guarantee thatno leakage of private information arise in the analysis handling customer data across theirorganizations. To meet the nee, secure computation in cryptology is being developed bycompanies, aiming practical application of commercial level. As another example, secretsharing that can, in theory, attain confidentiality and reliability of cloud storage is being
developed to obtain more availability and efficiency. However, these developments are at anintermediate point of the spiral intertwined with research activity.
For the techniques of secure computation and secret sharing to be taken in and to be used
actually, mathematical investigation, rigorous security proofs and recapturing usage
performance are indispensable. Especially, the following directions are important from thepoint of view of mathematics: (1) classifying mathematical approaches such as abstract
algebra, information theory, coding theory, combinatorics and game theory; (2) mitigating
assumptions of security, that is, semi-honest adversaries versus active adversaries,
computational security versus information-theoretic security, etc.; (3) improving efficiency,that is, decreasing computational amount, communication cost, the number of rounds andcomplexity of randomness.
The purpose of this workshop was to gather researchers in industry and academia in orderto share their experience on mathematical approaches and practical implementations of
secure computation and secret sharing for securing distributed data processing and data
storage. Then the participants discussed the actual problems which the industry was facing
when implementing the cryptographic technologies. Also, they discussed the appropriate
solutions. The workshop consisted of the invited lectures and tutorials on recent results of
secure computation and secret sharing. We hope that this lecture note would help readers
obtain some intuition in the technologies.

Hiroaki Anada, Representative of the Organizers

Acknowledgements

This work was supported by 2021 IMI Joint Use Research Program Workshop (I) "Exploring
Mathematical and Practical Principles of Secure Computation and Secret Sharing".

iIMI Joint Research Project in 2021

Exploring Mathematicaland Practical Principles
of Secure Computationand Secret Sharing
Date:

November 8(Mon)-10(Wed), 2021

Keynote speaker:
Johannes BUCHMANN, Technische Universität Darmstadt“Cryptographic long-term security”

Invited speakers:
Reo ERIGUCHI, The University of Tokyo
Keitaro HIWATASHI, The University of Tokyo
Kosuke KANEKO, Robert T.Huang Entrepreneurship Center of Kyushu University
Yi LU, Tokyo Institute of Technology
Ibuki MISHINA, NTT Social Informatics Laboratories
Kirill MOROZOV, University of North Texas
Hikaru TSUCHIDA, NEC Corporation

Venue: Online■Organizing Committee ▶ Hiroaki ANADA, University of Nagasaki■■■■

Yasuhiko IKEMATSU, Institute of Mathematics for Industry, Kyushu University
Koji NUIDA, Institute of Mathematics for Industry, Kyushu University
Satsuya OHATA
Yuntao WANG, Japan Advanced Institute of Science and Technology■Sponsored by ▶ Institute of Mathematics for Industry, Kyushu University■Registration fee ▶ Free

https://www.imi.kyushu-u.ac.jp/kyodo-riyo/research_meetings/view/30
Contact : imikyoten@jimu.kyushu-u.ac.jp (For general inquiries) Institute of Mathematics for Industry, Kyushu Universityii九州大学 IMI 共同利用・研究集会（I）

秘密計算 ・秘密分 散の数理 と実用の 探求
E x pl or i ng Ma th e ma t ic al an d P ra c ti c al P r in c ip le so f S ec u re Co mp u ta t io n a nd Se cr e t S ha ri n g
日時：

2021 年 11 月 08 日（月）16:00 ～ 18:25
火2021 年 11 月 09 日（水）09:00～ 11:252021 年 11 月 10 日（水）16:00 ～ 18:15
Zoom によるオンライン開催

場
所：
組織委員 ：
 Hiroaki Anada(University of Nagasaki) （研究代表者）
 Yasuhiko Ikematsu (IMI, Kyushu University)
 Koji Nuida(IMI, Kyushu University) Satsuya Ohata Yuntao Wang (Japan Advanced Institute of Science and Technology)

プログラム
11 月 08 日（月）16:00-16:05
オープニング
16:05-16:55
講演者：Johannes Buchmann（Technische Universität Darmstadt）
講演タイトル：“Cryptographic Long-Term Security”
17:05-17:40
講演者：Yi Lu（Tokyo Institute of Technology / National Institute ofAdvanced Industrial Science and Technology）
講演タイトル： “Efficient Two-party Exponentiation from Quotient Transfer”
17:50-18:25
講演者：Hikaru Tsuchida（NEC Corporation）
講演タイトル：“General-purpose Compiler for Secure Three-party
Computation and Its Application to Prediction by Machine Learning Model”
11 月 09 日（火）09:00-09:05
第 2 日オープニング
09:05-09:55
講演者：Kirill Morozov（University of North Texas）
講演タイトル：“Evolving Secret Sharing From Evolving Perfect Hash Families”

iii

10:05-10:40
講演者：Ibuki Mishina（NTT Social Informatics Laboratories）
講演タイトル：“Secure-Computation AI : a Python Library for Machine
Learning in Secure Computation”
10:50-11:25
講演者：Kosuke Kaneko（Robert T.Huang Entrepreneurship Center of Kyushu
University）
講演タイトル：“Possibility of Secret Sharing using EtherCAT”
11 月 10 日（水）16:00-16:05
第 3 日オープニング
16:05-16:40
講演者：Yasuhiko Ikematsu（Institute of Mathematics for Industry）
講演タイトル：“An Indeterminate Equation Scheme having Homomorphic
Property”
16:50-17:25
講演者：Reo Eriguchi（The University of Tokyo）
講演タイトル：“Homomorphic Secret Sharing for Multipartite and General
Adversary Structures Supporting Parallel Evaluation of Low-Degree
Polynomials”
17:35-18:10
講演者：Hiroaki Anada（University of Nagasaki）
講演タイトル：“A Comparison of How to Garble Arithmetic and Boolean
Circuits”
18:10-18:15
クロージング最新情報及び参加情報は下記 URL(QR コード)のウェブサイトにて御確認下さい．
https://www.imi.kyushu-u.ac.jp/kyodo-riyo/research_meetings/view/30

iv

Contents

Cryptographic Long-term Security ������������������������������������������������������������������������������� 1
Johannes Buchmann (Technische Universität Darmstadt)

Efficient Two-party Exponentiation from Quotient Transfer ������������������������������������������ 19
Yi Lu (Joint work with Keisuke Hara, Kazuma Ohara, Jacob Schuldt, and Keisuke Tanaka)(Tokyo Institute of Technology /National Institute of Advanced Industrial Science and Technology)

General-purpose Compiler for Secure Three-party Computation and Its Application to
Prediction by Machine Learning Model �������������������������������������������������������������������� 33
Hikaru Tsuchida (NEC Corporation)

Evolving Secret Sharing From Evolving Perfect Hash Families �������������������������������������� 47
Kirill Morozov (University of North Texas)

Secure-Computation AI: a Python Library for Machine Learning in Secure Computation ����� 63
Ibuki Mishina (Joint work with Dai Ikarashi, Koki Hamada and Ryo Kikuchi)(NTT Corporation)

Possibility of Secret Sharing using EtherCAT ��������������������������������������������������������������� 73
Kosuke Kaneko (Robert T. Huang Entrepreneurship Center of Kyushu University)

An indeterminate equation scheme having homomorphic property �������������������������������� 87
Yasuhiko Ikematsu (Institute of Mathematics for Industry, Kyushu University)

Homomorphic Secret Sharing for Multipartite and General Adversary Structures
Supporting Parallel Evaluation of Low-Degree Polynomials ��������������������������������������� 95
Reo Eriguchi (Joint work with Koji Nuida) (The University of Tokyo)

A Comparison of How to Garble Arithmetic and Boolean Circuits- Case of Functional Encryption - ��������������������������������������������������������������������������� 105
Hiroaki Anada (Joint work with Kotaro Chinen) (University of Nagasaki)v

vi

IMI Workshop: Exploring Mathematical and Practical Principles
of Secure Computation and Secret Sharing
November 8–10, 2021, Kyushu University

Cryptographic Long-term Security
Johannes BuchmannTechnische Universität Darmstadt
johannes.buchmann@tu-darmstadt.deDigitization is omnipresent and all important areas of our private, political, social,and economic lives depend on it. As a result, digitization must meet ever greater
security requirements. In particular, security must be guaranteed for a very long periodof time. One important technology that enables cybersecurity is cryptography. In thetalk, I talk about how cryptography can enable long-term protection and the importantrole Secret Sharing plays in this.

1Cryptographic Long-Term Security
Johannes Buchmann, TU Darmstadt

The challenge

Requires long-term protection!

2

Protection goals

Integrity

Data existed attime t0 .
Not changed
since.

t𝑡𝑡𝑡𝑡0

Authenticity

I can verify thedata origin.

t

𝑡𝑡𝑡𝑡0

3

Non-repudiation

Anyone canverify the data
origin.

t

𝑡𝑡𝑡𝑡0

t

Confidentiality
Data at rest

𝑡𝑡𝑡𝑡0

Data in transit

Availability

4

t

t

Protection by cryptography

Protection goal
Confidentiality
Integrity
Authenticity
Non-repudiation
Availability

Cryptographic method
Encryption + key exchange
Hash, MAC, digital signature
MAC, digital signature
Digital signature----------------------

Today’s cryptography is complexity-based
Cryptographic method
Key Exchange+ Encryption
Hash, MAC

Algorithms
Hard problem
RSA/Diffie-Hellman Factoring/Discrete Logarithm
AES
AES
SHA-3, HMAC

SHA-3

Digital signature

RSA, ECDSA

Factoring, EC-DL

5

Today’s complexity-based cryptography
is not sustainable

Algorithm

Standardized

BrokenBy

Lifetime

DES

1977

1997

Brute force

20 years
31 years?

Diffie-Hellman

1999

2030?

Quantum computer

MD5

1992

1996/2004

Analysis of algorithm 4 years

RSA

1991

RSA-512
ECDSA

2005

2030?

Quantum computer

39 years?

2000

Number Field Sieve

9 years2030?

Quantum computer

25 years?

Aspects of cryptographic long-term security

Cryptography that can resist
new attacks

Long-term protection of data

6

Availability of Cryptography

Since 2017

Long-term protection of data7

Confidentiality

Integrity

Authenticity

Non-repudiation

Protection time: human life expectancy – one century

Integrity, authenticity, non-repudiation

Time stampℎ
𝐻𝐻𝐻𝐻𝐻𝐻𝐻𝐻𝐻𝐻𝐻𝐻ℎ⟶ℎ

𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆 ℎ, 𝑡𝑡𝑡𝑡 ⟶8

Integrity, authenticity, non-repudiation

Valid time stamp
existed at time t0

t

𝑡𝑡𝑡𝑡0

Time stamps use signatures
which are not long-term

Time stamp security can be prolonged!

9Timestamp chain – RFC 4998

Timestamp

𝑇𝑇𝑇𝑇0

𝑇𝑇𝑇𝑇0

𝑇𝑇𝑇𝑇1

𝑡𝑡𝑡𝑡0

𝑡𝑡𝑡𝑡1

…
…

𝑇𝑇𝑇𝑇0 … 𝑇𝑇𝑇𝑇𝑘𝑘𝑘𝑘−1
𝑇𝑇𝑇𝑇𝑘𝑘𝑘𝑘

𝑡𝑡𝑡𝑡𝑘𝑘𝑘𝑘

Time

Challenges
Hash value may reveal information about signed data
Sudden break of cryptography
Format change

Confidentiality

10Encryption

Data in transit
Data at rest

Long-term secure?

200 Zettabytes = 2*1023 Bytes ~ 200 TB/Person in the world
Cyphertexts may be stored now and can be decrypted later
Encryption security cannot be prolonged

Information theoretic confidentiality
protection is required

11

Data in transit

Data in transit

Quantum Key Distribution+
One-Time Pad encryption

12Challenges
QKD is point-to-point

Trusted nodes required

Solutions to point-to-point
challenge

Backbone with pre-shared keys
AliceCharlie
TrustedNode 1

Bob

TrustedNode 3

TrustedNode 2Diana

13

Quantum key hub
Alice

Bob

Hub

Charlie

Diana

Quantum Key Hub Darmstadt

Walther et. al. 2021

Data at rest

14

Quantum Key Distribution?

+
One-Time Pad encryption

Data at rest

Solution: secret sharing

Proactive Secret Sharing
10111100
1100011001101100
11110010
10111100
1100011001101100
11110010
10111100
1100011001101100
11110010

10111100
1100011001101100
11110010

Renew shares

Herzberg 1995

15

10111100
1100011001101100
11110010

Hierarchical secret sharing

Traverso et al. 2016

LINCOS architecture
Confidentiality
Secret sharing
Information theoreticallysecure channels
Data owner

Shareholders

Computationallysecure channels
Evidence service

Confidentialitypreserving long-term
integrity protection

Integrity
Timestamp services

Geihs et al. 2016

H-LINCOS with NICT

16

Availability

How can historians access encrypted data?

Conclusion

17

Provably and efficient
secure LT private
channels

Security models

LT integrity protection
preserving
confidentiality

Complex and private
access structures

An architecture for LT
confidentiality andintegrity

Verifiable and private
outsourced
computation

Format change

Sudden break ofcryptography?

?

High performance LT
key exchange

Long-term availability?

?

Thank you very much for your attention!

18

IMI Workshop: Exploring Mathematical and Practical Principles
of Secure Computation and Secret Sharing
November 8–10, 2021, Kyushu University

Efficient Two-party Exponentiation from Quotient
Transfer
Yi Lu (Joint work with Keisuke Hara, Kazuma Ohara, Jacob
Schuldt, and Keisuke Tanaka)
Tokyo Institute of Technology / National Institute of Advanced Industrial Scienceand Technology
lu.y.ai@m.titech.ac.jp
Secure multi-party computation (MPC) allows participating parties to jointly compute a function over their inputs while keeping them private. In particular, MPC basedon additive secret sharing has been widely studied as a tool to obtain efficient protocols
secure against a dishonest majority, including the important two-party case. In thispaper, we propose a two-party protocol for an exponentiation functionality based onan additive secret sharing scheme. Our proposed protocol is based on a new simple
but efficient approach involving quotient transfer that allows the parties to perform themost expensive part of the computation locally. Our protocol requires 6 rounds and4 invocations of multiplication. This is the first two-party protocol for an exponentiation functionality with constant-round efficiency based on an additive secret sharing
scheme. As an intermediate primitive for our efficient two-party exponentiation protocol, we propose an efficient modulus conversion protocol, which may be of independentinterest.

19Efficient Two-party Exponentiationfrom Quotient Transfer
LU YI (Tokyo Tech/AIST）
Hara Keisuke (Tokyo Tech/AIST）
Ohara Kazuma (AIST）
Jacob Schuldt (AIST)
Tanaka Keisuke (Tokyo Tech)Multi Party Computation (MPC)
Secret input𝑥𝑥!
Secret input𝑥𝑥%

Secret input𝑥𝑥"

𝑓𝑓(𝑥𝑥" , 𝑥𝑥# , 𝑥𝑥$ , 𝑥𝑥% , 𝑥𝑥& )Secret input𝑥𝑥$

Secret input
𝑥𝑥#

Multi Party Computation (MPC)
Secret input𝑥𝑥!
Secret input𝑥𝑥%

𝑓𝑓(𝑥𝑥" , 𝑥𝑥# , 𝑥𝑥$ , 𝑥𝑥% , 𝑥𝑥& )Secret input𝑥𝑥$

Secret input𝑥𝑥"

Secret input𝑥𝑥#

20Basic Properties for MPC• Correctness : the function is computed
correctly• Security : Only the output is revealed

Modeling Adversaries• Adversarial Behavior• Semi-honest : follows the protocol specification• Malicious : follows any arbitrary strategy• Adversarial power• Polynomial-time : computational security• Computationally unbounded :information-theoretic security

Modeling Adversaries• Adversarial Number• Honest-Majority: The number of honest party isover half of all participants• Dishonest-Majority: The number of adversary isover half of all participantsSemi-honest and Computationally unbounded21

The performance of MPC• Rounds: The number of communications, which
can be done simultaneously will be counted as one
round• Communication Complexity: The number of bits
which are transferred in communication
The number of invocations of Multiplication.
• Computation Complexity: The number ofcomputations which is done in protocol

Multi Party Computation (MPC)
MethodCommunication
Complexity

RoundsComputation
Complexity

Secret Sharing

small

big

small

FHE

big

small

big

GarbledCircuit(GC)

big

small

normal-big

Table 2. Three Method to Implement MPC

Secret Sharing
A method for distributing a secret among a group ofparticipants
𝑆𝑆!
Secret S

Division𝑆𝑆"

Secret S

𝑆𝑆&

Reconstruction⋮22

(k,n) threshold Secret Sharing SchemeØDivide secret data (D) into pieces (n)ØKnowledge of some pieces (k) enables toderive secret data (D)ØKnowledge of any pieces (k-1) makes secretdata (D) completely undetermined.
Such a scheme is called a (k,n) threshold scheme

Variants of Secret Sharing Scheme
Shamir’s Secret Sharing

Additive Secret Sharing𝑥𝑥 ∈ 𝔾𝔾 𝑖𝑖𝑖𝑖 𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑥𝑥" + ⋯ + 𝑥𝑥. ≡ 𝑥𝑥 𝑚𝑚𝑚𝑚𝑚𝑚 𝑝𝑝

𝑠𝑠 𝑖𝑖𝑖𝑖 𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠
𝑓𝑓 𝑥𝑥 = 𝑎𝑎*+" 𝑥𝑥 *+" + ⋯ + 𝑎𝑎" 𝑥𝑥 + 𝑎𝑎,
𝑎𝑎, = s，𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠 𝑎𝑎- 𝑖𝑖 = 1, … , t 𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟

𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠 𝑥𝑥- ∈ 𝔾𝔾 , (𝑖𝑖 = 1, … , 𝑛𝑛)

𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠 𝑠𝑠- = 𝑓𝑓 𝑖𝑖 (𝑖𝑖 = 1, … , 𝑛𝑛)

Threshold

Set

Core
Technique

Shamir’s Secret Sharing

k<n/2

Lagrange
interporation

Additive Secret Sharingn-1

𝔽𝔽p (p: prime)
𝔾𝔾 (Finite
Additive
Group)

Merits of Additive Secret Sharing𝑥𝑥 ∈ 𝔾𝔾[x]! +[𝑥𝑥]" + ⋯ + 𝑥𝑥 # ≡ 𝑥𝑥 𝑚𝑚𝑚𝑚𝑚𝑚 𝑝𝑝[𝑥𝑥] ← 𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠(𝑥𝑥), 𝑥𝑥 = ([x]" , [𝑥𝑥]# , … , 𝑥𝑥 . )𝑥𝑥 ← 𝑅𝑅𝑅𝑅𝑅𝑅𝑅𝑅𝑅𝑅𝑅𝑅𝑅𝑅𝑅𝑅𝑅𝑅𝑅𝑅𝑅𝑅𝑅𝑅𝑅𝑅𝑅𝑅([𝑥𝑥])• Merits ：The compatibility with well-known dishonestmajority frameworks.

• [Bea92] “Beaver triple” is a well-known and easy way to introduce

multiplication in the dishonest-majority setting• To the best of our knowledge, all known efficient offline protocols
generating Beaver triples are designed for additive secret sharing，[DPSZ12, DKL+13, KPR18]， [ALSZ15,KOS16]

23

Addition and Multiplication in MPC
Party 1 generates 𝑎𝑎
Party 2 generates 𝑏𝑏

formulation
Addition
Multiplication

𝑎𝑎 + 𝑏𝑏 = [𝑎𝑎 + 𝑏𝑏]
𝑎𝑎 ' 𝑏𝑏 = [𝑎𝑎 ' 𝑏𝑏]

Communication
Local (0 round)1 roundIn general, all of the computations are implemented by using
addition and multiplication.

Research Background

Background:

The meaning of Exponentiation MPC
2 party【RSC+19】【MLS+20】【CVA18】

3 party【KRC+20】【AA20】

4 party【BCP+20】【CRS20】【CCPS19】

Softmax function
𝜎𝜎(𝑧𝑧)/ =𝑒𝑒 0!
, 𝑓𝑓𝑓𝑓𝑓𝑓 𝑗𝑗 = 1, … 𝐾𝐾
0"∑3
12" 𝑒𝑒Table 3. Researches on Deep learning MPC Protocol[RSC+19] M. Sadegh Riazi, Mohammad Samragh, Hao Chen, Kim Laine, KristinLauter, Farinaz Koushanfar. XONN: XNORbased Oblivious Deep Neural Network Inference. USENIX Conference on Security Symposium 2019.
[KRC+20] Nishant Kumar, Mayank Rathee, Nishanth Chandran, Divya Gupta, Aseem Rastogi, Rahul Sharma. CrypTFlow:
Secure TensorFlow Inference. IEEE S&P 2020.
[BCP+20] Megha Byali, Harsh Chaudhari*, Arpita Patra, and Ajith Suresh. FLASH:Fast and Robust Framework for Privacypreserving Machine Learning. PoPETs 2020.
…

24

Background:3 types of Exponentiation MPC• Public Base:• Public Exponent:• Private Exponentiation:

𝑎𝑎["]
[𝑎𝑎]"

Our work consider the setting public base[𝑎𝑎]["]𝑒𝑒 %!
, 𝑓𝑓𝑓𝑓𝑓𝑓 𝑗𝑗 = 1, … 𝐾𝐾%"∑)&'( 𝑒𝑒𝜎𝜎(𝑧𝑧)$ =Normal method to Compute EXP MPC:
Bit-decomposition (BD)
Convert the input of arithmetic circuits into ones of Boolean circuits

BD

[𝑥𝑥]$

[𝑥𝑥]* = [𝑥𝑥+ ], … 𝑥𝑥-.( ,/such as 𝑥𝑥 = ∑-.(/'+ 2 𝑥𝑥/ , 𝑥𝑥/ ∈ {0,1}such as 𝑥𝑥 ∈ 𝔽𝔽4[DFK+06]

Round complexity: Ο(1)Invocations of multiplication: Ο(𝑙𝑙 log 𝑙𝑙)

Normal method to Compute EXP MPC:
Bit-decomposition (BD)For example: [DFK+06]$%&[𝑥𝑥]! = [𝑥𝑥" ]# … 𝑥𝑥$%& # , / 2' 𝑥𝑥' , 𝑥𝑥' ∈ {0,1}
'("

&'(

#

-.(

#

-.(

#

𝑎𝑎 " = 𝑎𝑎∑#$% 1 "# = < 𝑎𝑎1 "# = <(𝑥𝑥/ 𝑎𝑎1 + 1 − 𝑥𝑥/ )/'+Round complexity: Ο(1)Invocations of multiplication: Ο(𝑙𝑙 log 𝑙𝑙)

25

/'+

Existing Exponentiation protocol without BD

Motivation:
Without Bit-decomposition

Additive secret sharing

EXP MPC

New Framework for Modular
Exponentiation Protocol

Naive Approach[𝑎𝑎 " ], ← ℱ234 (𝑎𝑎, [𝑥𝑥], )Party A

Input : 𝑎𝑎, [𝑥𝑥]&#
Locol: 𝑦𝑦& = 𝑎𝑎

𝑎𝑎 " < 𝑝𝑝"[+]!

Share: [𝑦𝑦& ] ← 𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠(𝑦𝑦& )𝑦𝑦& = { 𝑦𝑦& &# , 𝑦𝑦& )# }[𝑥𝑥] ← 𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠(𝑥𝑥)[𝑥𝑥]!' +[𝑥𝑥]"' ≡ 𝑥𝑥 𝑚𝑚𝑚𝑚𝑚𝑚 𝑝𝑝
𝑦𝑦! "'𝑦𝑦" !'

Mult: 𝑎𝑎 + = 𝑦𝑦& ⋅ [𝑦𝑦) ]Party B

Input : 𝑎𝑎, [𝑥𝑥]#)#

Locol: 𝑦𝑦) = 𝑎𝑎 [+]!

Share: [𝑦𝑦) ] ← 𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠(𝑦𝑦) )𝑦𝑦) = { 𝑦𝑦) &# , 𝑦𝑦) )# }Mult: 𝑎𝑎 + = 𝑦𝑦& ⋅ [𝑦𝑦) ]26

Problem of Naive Approach[𝑥𝑥](, +[𝑥𝑥]1, ≡ 𝑥𝑥 𝑚𝑚𝑚𝑚𝑚𝑚 𝑝𝑝

For
example:(*𝑒𝑒 ["]) 5["]) = B

𝑎𝑎 " < 𝑝𝑝

4 + 4 ≡ 3 𝑚𝑚𝑚𝑚𝑚𝑚 5
𝑒𝑒 % ⋅ 𝑒𝑒 % = 𝑒𝑒 F ≠ 𝑒𝑒 $𝑒𝑒 "([𝑥𝑥](, + [𝑥𝑥]1, ≤ 𝑝𝑝*𝑒𝑒 ["]) 5["]) ., = 𝑒𝑒 "5, = 𝑒𝑒 "5( 𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒= 𝑒𝑒 "56, = 𝑒𝑒 "56

𝑡𝑡 ∈ 1,0Quotient Transfer Functionality
When [𝑥𝑥](, +[𝑥𝑥]1, ≡ 𝑥𝑥 𝑚𝑚𝑚𝑚𝑚𝑚 𝑝𝑝, which means[𝑥𝑥](, +[𝑥𝑥]1, = 𝑥𝑥 + 𝑡𝑡𝑡𝑡, 𝑡𝑡 ∈ 1,0[𝑥𝑥](,[𝑡𝑡](,7[𝑥𝑥]1,QT

When [𝑥𝑥]"4 +[𝑥𝑥]#4 ≤ 𝑝𝑝, 𝑡𝑡 = 0, else 𝑡𝑡 = 1[𝑡𝑡]1,7Constrained Quotient transfer Protocol
Constrain means x is even.

𝑥𝑥 = 4, 𝑝𝑝 = 7, 𝑝𝑝 & = 11[𝑥𝑥]!% +[𝑥𝑥]"% = 4𝑚𝑚𝑚𝑚𝑚𝑚 7[𝑥𝑥](8 = 5∵ [𝑥𝑥]"G +[𝑥𝑥]#G = 11 > 7

𝐿𝐿𝐿𝐿𝐿𝐿 [𝑥𝑥]"G"" = 1[𝑥𝑥]18 = 6∴ 𝑡𝑡 = 1

𝐿𝐿𝐿𝐿𝐿𝐿 [𝑥𝑥]#G

𝐿𝐿𝐿𝐿𝐿𝐿 [𝑥𝑥](8 (( + 𝐿𝐿𝐿𝐿𝐿𝐿 𝑥𝑥 18 ((− 2× 𝐿𝐿𝐿𝐿𝐿𝐿 𝑥𝑥 18 (( × 𝐿𝐿𝐿𝐿𝐿𝐿 𝑥𝑥 (827"" = 0(( = 1

Constrained Quotient transfer Protocol
Constrain means x is even.
𝐿𝐿𝐿𝐿𝐿𝐿 [𝑥𝑥]!'

𝑃𝑃!

= ( 𝐿𝐿𝐿𝐿𝐿𝐿 [𝑥𝑥]!''([𝑡𝑡]!'( = 𝐿𝐿𝐿𝐿𝐿𝐿 [𝑥𝑥]!'

!

'!

!

, [𝐿𝐿𝐿𝐿𝐿𝐿 [𝑥𝑥]!''!

⊕ 𝐿𝐿𝐿𝐿𝐿𝐿 [𝑥𝑥]'"!

𝐿𝐿𝐿𝐿𝐿𝐿 [𝑥𝑥]"']"'( )[𝐿𝐿𝐿𝐿𝐿𝐿 [𝑥𝑥]!' ]"'(𝐿𝐿𝐿𝐿𝐿𝐿 [𝑥𝑥]"'!

'!

, [𝐿𝐿𝐿𝐿𝐿𝐿 [𝑥𝑥]"' ]"'( )

!

'!

'!

∵ [𝑥𝑥]!' +[𝑥𝑥]'" = V

'(

𝑃𝑃"

= ( 𝐿𝐿𝐿𝐿𝐿𝐿 [𝑥𝑥]"'[𝑡𝑡]"'( = 𝐿𝐿𝐿𝐿𝐿𝐿 [𝑥𝑥]!'"'!

⊕ 𝐿𝐿𝐿𝐿𝐿𝐿 [𝑥𝑥]"'"'!

[𝑥𝑥]!' +[𝑥𝑥]"' ≤ 𝑝𝑝
= 𝑥𝑥 + 𝑡𝑡𝑡𝑡
𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑥𝑥
𝑥𝑥 + 𝑝𝑝∴ 𝑡𝑡 = 𝐿𝐿𝐿𝐿𝐿𝐿 [𝑥𝑥]!' ⊕ 𝐿𝐿𝐿𝐿𝐿𝐿 [𝑥𝑥]"' = P

0
1[𝑥𝑥]!' + [𝑥𝑥]'" ≤ 𝑝𝑝
𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒Constrained Quotient transfer Protocol

Exponentiation protocol[𝑥𝑥]&# +[𝑥𝑥])# ≡ 𝑥𝑥 𝑚𝑚𝑚𝑚𝑚𝑚 𝑝𝑝, 𝑥𝑥 is even$%𝑎𝑎 " < 𝑝𝑝𝑎𝑎[W]#X[W]# = 𝑎𝑎 WX*4 = 𝑎𝑎 WX*

𝑡𝑡 ∈ 1,0

If 𝑡𝑡 = 1, [𝑥𝑥]"4 +[𝑥𝑥]#4 > 𝑝𝑝,
𝑑𝑑 = 𝑎𝑎 WX" , 𝑜𝑜" = 0, 𝑜𝑜# =𝑑𝑑 = 𝑎𝑎 WX"
𝑜𝑜 = 𝑜𝑜# 𝑎𝑎+" = 𝑎𝑎 W

If 𝑡𝑡 = 0, [𝑥𝑥]"4 +[𝑥𝑥]#4 ≤ 𝑝𝑝, 𝑑𝑑 =𝑎𝑎 W , 𝑜𝑜" = 𝑑𝑑 = 𝑎𝑎 W , 𝑜𝑜# = 0
𝑜𝑜 = 𝑜𝑜" = 𝑎𝑎 W

28

Problem 2： assumption
a! = 𝑎𝑎"!

𝑎𝑎 dose not always exist in ℤ$

We need b and p, which
satisfy
𝑎𝑎 = 𝑏𝑏 " 𝑚𝑚𝑚𝑚𝑚𝑚 𝑝𝑝𝑝

𝑎𝑎 ' < 𝑝𝑝𝑝

Assume we can find such b and p’

Conversion protocol[𝑥𝑥]$& ← [𝑥𝑥]$Correctness[𝑥𝑥𝑥]#!" = [𝑥𝑥]#! −[𝑡𝑡]#!" ×𝑝𝑝[𝑥𝑥𝑥]$!" = [𝑥𝑥]$! −[𝑡𝑡]$!" ×𝑝𝑝[𝑥𝑥𝑥]%!" = [𝑥𝑥]%! −[𝑡𝑡]%!" ×𝑝𝑝[𝑥𝑥′]!$& +[𝑥𝑥𝑥]"$& 𝑚𝑚𝑚𝑚𝑚𝑚 𝑝𝑝 & = 𝑥𝑥 !$ − 𝑡𝑡 !$! ×𝑝𝑝 + 𝑥𝑥 "$ − 𝑡𝑡 "$! ×𝑝𝑝 𝑚𝑚𝑚𝑚𝑚𝑚 𝑝𝑝𝑝= [𝑥𝑥]!$ +[𝑥𝑥]"$ −= 𝑥𝑥 + 𝑡𝑡×𝑝𝑝 −29

𝑡𝑡 !$! + 𝑡𝑡 "$! ×𝑝𝑝 𝑚𝑚𝑚𝑚𝑚𝑚 𝑝𝑝𝑝

𝑡𝑡 !$! + 𝑡𝑡 "$! ×𝑝𝑝 𝑚𝑚𝑚𝑚𝑚𝑚 𝑝𝑝𝑝

Correctness[𝑥𝑥𝑥]!$& +[𝑥𝑥𝑥]"$& 𝑚𝑚𝑚𝑚𝑚𝑚 𝑝𝑝𝑝 = 𝑥𝑥 + 𝑡𝑡×𝑝𝑝 −𝑡𝑡 !$! + 𝑡𝑡 "$! ×𝑝𝑝 𝑚𝑚𝑚𝑚𝑚𝑚 𝑝𝑝𝑝= 𝑥𝑥 + 𝑡𝑡×𝑝𝑝 − 𝑡𝑡×𝑝𝑝 𝑚𝑚𝑚𝑚𝑚𝑚 𝑝𝑝# = 𝑥𝑥

= 𝑥𝑥 + 𝑡𝑡×𝑝𝑝 − 𝑡𝑡 + 𝑝𝑝# ×𝑝𝑝 𝑚𝑚𝑚𝑚𝑚𝑚 𝑝𝑝𝑝= 𝑥𝑥

Our Exponentiation Protocol

Our Result

30

𝑡𝑡 !$! + 𝑡𝑡 "$! < 𝑝𝑝𝑝
elseOpen Problem
2 party EXP MPC

extendn party EXP MPC
n party QT protocol

2 party QT protocol

No Efficient? Efficient n party EXP MPC

Thank you for your listening

31

IMI Workshop: Exploring Mathematical and Practical Principles
of Secure Computation and Secret Sharing
November 8–10, 2021, Kyushu University

General-purpose Compiler for Secure Three-party
Computation and Its Application to Prediction by
Machine Learning Model
Hikaru Tsuchida
NEC Corporation
h tsuchida@nec.com
Multiparty computation (MPC) based on a secret sharing scheme (SS-MPC) enables
multiple parties to compute an arbitrary function represented as a circuit without revealing parties’ inputs. In SS-MPC, each party distributes its inputs as shares that look
like random numbers among several parties, and the computation proceeds by using
shares locally and communicating among the parties. In particular, the secure threeparty computation protocol based on a replicated secret sharing scheme (SS-3PC) over
the ring [1] has gained attention in recent years because it can perform high throughput
even when SS-3PC computes a complex function (e.g., machine learning applications)represented as mixed circuits (which are composed of Boolean and arithmetic circuits).
When SS-MPC computes a complex function represented as mixed circuits, efficient
share conversion protocols can improve performance. In particular, SS-3PC over Z2k
can achieve faster share conversions than that over the prime-order field because Z2kpreserves the structure of the individual bits more than the prime-order field.
While research on protocol design is ongoing, there is still a significant obstacle
to implement the applications via MPC due to the high level of expertise required todesign a specific MPC execution considering a trade-off between communication andround complexities. Research and development of general-purpose compilers have been
actively conducted to mitigate this problem. It can compile the high-level codes to themixed circuits that MPC computes. Hence, by using the general-purpose compilers,even non-experts of MPC can implement applications based on MPC.
In this talk, we explain one of the general-purpose compilers for SS-3PC, NEC-SPDZ
and the share conversion protocols over Z2 and Z2k to compute a complex function via
SS-3PC by referring to [2]. We also explain the implementation based on NEC-SPDZ
and evaluation of the prediction by typical machine learning models, e.g., the decision
tree and the hierarchical mixture of experts models via SS-3PC by referring to [2, 3].
References[1] Toshinori Araki, Jun Furukawa, Yehuda Lindell, Ariel Nof, and Kazuma Ohara. High-Throughput
Semi-Honest Secure Three-Party Computation with an Honest Majority. ACM-CCS 2016, pp.805817.
[2] Toshinori Araki, Assi Barak, Jun Furukawa, Marcel Keller, Yehuda Lindell, Kazuma Ohara,and Hikaru Tsuchida. Generalizing the SPDZ Compiler For Other Protocols. ACM-CCS 2018,
pp.880-895.
[3] Yusaku Maeda, Hikaru Tsuchida, Kazuma Ohara, Ryo Furukawa, Isamu Teranishi, and Koji
Nuida. Implementation and Evaluation of Prediction by Heterogeous Mixture Models based onThree-Party Secure Computation. SCIS 2020, 3C3-5.

33

General-purpose Compiler for Secure Three-party
Computation and Its Application to Prediction by
Machine Learning Model
Hikaru Tsuchida(NEC Corporation)© NEC Corporation 2021

Agenda1. Introduction
2. General-purpose compiler
3. Private decision tree evaluation via three-party
computation
4. Private hierarchical mixture of experts evaluation via
three-party computation
5. Conclusion

Introduction[A+16] Toshinori Araki, Jun Furukawa, Yehuda Lindell, Ariel Nof, and Kazuma Ohara. High-Throughput Semi-Honest
Secure Three-Party Computation with an Honest Majority. ACM-CCS 2016, pp.805-817.
[A+18] Toshinori Araki, Assi Barak, Jun Furukawa, Marcel Keller, Yehuda Lindell, Kazuma Ohara, and Hikaru Tsuchida.
Generalizing the SPDZ Compiler For Other Protocols. ACM-CCS 2018, pp.880-895.

34

Multiparty computation (MPC) MPC provides only the outputs of the function to parties without
revealing parties’ inputs.

Input
𝒙𝒙𝟎𝟎
𝑓𝑓𝑓𝑓𝑓� , 𝑥𝑥� , 𝑥𝑥� )

Input
𝒙𝒙𝟏𝟏
4

Input
𝒙𝒙𝟐𝟐

© NEC Corporation 2021

Multiparty computation (MPC) Even if there are some parties that are corrupted by anadversary, MPC enables parties to compute the function securely.

Corruption

Input
𝒙𝒙𝟎𝟎
𝑓𝑓𝑓𝑓𝑓� , 𝑥𝑥� , 𝑥𝑥� )

Input
𝒙𝒙𝟏𝟏
5

Input
𝒙𝒙𝟐𝟐

© NEC Corporation 2021

MPC based on secret sharing (SS-MPC)
 Each party distributes its inputs as shares that look like random numbers among
several parties.
 Example of shares : 𝑥𝑥 𝑥 𝑥𝑥� + 𝑥𝑥� + 𝑥𝑥� mod 2� (𝑘𝑘 𝑘 𝑘𝑘
Share
𝒙𝒙𝟎𝟎

Share
𝒙𝒙𝟏𝟏

𝑓𝑓𝑓𝑓𝑓𝑓Share
𝒙𝒙𝟐𝟐

The computation proceeds by using shares locally and communicating among the parties.
6© NEC Corporation 2021

35

Three-party computation based on replicated secretsharing (SS-3PC)
 SS-3PC [A+16] over the ring has gained attention in recent years because it canachieve high throughput.
 𝑥𝑥 𝑥 𝑥𝑥� + 𝑥𝑥� + 𝑥𝑥� mod 2� (𝑘𝑘 𝑘 𝑘𝑘

 𝑃𝑃� ’s share over ℤ�� : 𝑥𝑥 �� ,� = (𝑥𝑥� , 𝑥𝑥 ��� ��� � )Corruption

𝑃𝑃� ’s share(𝒙𝒙𝟎𝟎 , 𝒙𝒙𝟏𝟏 )7© NEC Corporation 2021

𝑓𝑓𝑓𝑓𝑓𝑓𝑃𝑃� ’s share(𝒙𝒙𝟏𝟏 , 𝒙𝒙𝟐𝟐 )𝑃𝑃� ’s share(𝒙𝒙𝟐𝟐 , 𝒙𝒙𝟎𝟎 )Three-party computation based on replicated secretsharing (SS-3PC)
 SS-3PC [A+16] over the ring has gained attention in recent years because it canachieve high throughput.
 𝑥𝑥 𝑥 𝑥𝑥� + 𝑥𝑥� + 𝑥𝑥� mod 2� (𝑘𝑘 𝑘 𝑘𝑘

 𝑃𝑃� ’s share over ℤ�� : 𝑥𝑥 �� ,� = (𝑥𝑥� , 𝑥𝑥 ��� ��� � )At most single corruption among three parties
Corruption

𝑃𝑃� ’s share(𝒙𝒙𝟎𝟎 , 𝒙𝒙𝟏𝟏 )8© NEC Corporation 2021

𝑓𝑓𝑓𝑓𝑓𝑓𝑃𝑃� ’s share(𝒙𝒙𝟏𝟏 , 𝒙𝒙𝟐𝟐 )𝑃𝑃� ’s share(𝒙𝒙𝟐𝟐 , 𝒙𝒙𝟎𝟎 )Three-party computation based on replicated secretsharing (SS-3PC)
 SS-3PC [A+16] over the ring has gained attention in recent years because it canachieve high throughput.
 𝑥𝑥 𝑥 𝑥𝑥� + 𝑥𝑥� + 𝑥𝑥� mod 2� (𝑘𝑘 𝑘 𝑘𝑘

 𝑃𝑃� ’s share over ℤ�� : 𝑥𝑥 �� ,� = (𝑥𝑥� , 𝑥𝑥 ��� ��� � )Attempts to get as much information as possible
while following the protocol specification
Corruption

𝑃𝑃� ’s share(𝒙𝒙𝟎𝟎 , 𝒙𝒙𝟏𝟏 )9© NEC Corporation 2021

𝑃𝑃� ’s share(𝒙𝒙𝟏𝟏 , 𝒙𝒙𝟐𝟐 )Semi-honest adversary
𝑓𝑓𝑓𝑓𝑓𝑓36

𝑃𝑃� ’s share(𝒙𝒙𝟐𝟐 , 𝒙𝒙𝟎𝟎 )Three-party computation based on replicated secretsharing (SS-3PC)
 SS-3PC [A+16] over the ring has gained attention in recent years because it canachieve high throughput.
 𝑥𝑥 𝑥 𝑥𝑥� + 𝑥𝑥� + 𝑥𝑥� mod 2� (𝑘𝑘 𝑘 𝑘𝑘

 𝑃𝑃� ’s share over ℤ�� : 𝑥𝑥 �� ,� = (𝑥𝑥� , 𝑥𝑥 ��� ��� � )Corruption

𝑃𝑃� ’s share(𝒙𝒙𝟎𝟎 , 𝒙𝒙𝟏𝟏 )𝑓𝑓𝑓𝑓𝑓𝑓

10© NEC Corporation 2021

𝑃𝑃� ’s share Remark:𝑃𝑃� ’s share(𝒙𝒙𝟏𝟏 , 𝒙𝒙𝟐𝟐 ) MPC computes a function, 𝒇𝒇, represented as a circuit. (𝒙𝒙𝟐𝟐 , 𝒙𝒙𝟎𝟎 )Types of circuits
1. Boolean circuit

2. Arithmetic circuit

3. Mixed circuit (= Boolean & arithmetic circuits) SS-3PC over the ring computes a complex function (e.g., machine learning application) represented as amixed circuit using the share conversion protocols.

Remark:We denote the share of
11

over

© NEC Corporation 2021

�� as

��

�� ,�

�� ,�

�� ,� .

Toy example requiring share conversion protocols
 ex. Less-than operation
Share over

��

��
��
��
※ 𝑃𝑃� sets 𝑎𝑎 𝑎 𝑎𝑎 �� ,� = (𝑎𝑎� −𝑏𝑏� mod 2� , 𝑎𝑎��� −𝑏𝑏��� mod 2� ).

Share conversion (bit decomposition)

Array ofshares over

�

� �

�
※ 𝑎𝑎 𝑎 𝑎𝑎 𝑎 ∑������ 2 ⋅ (𝑎𝑎 𝑎 𝑎𝑎𝑎𝑎� s.t.

MSB extraction

Share over

12

�

�

���

���
𝑎𝑎 𝑎 𝑎𝑎 𝑎� ∈ ℤ� .
��� �

Remark:Since ℤ�� preserves the structure of the individual bits, SS-3PC over ℤ�� canachieve the fast share conversion protocols [A+18].

© NEC Corporation 2021

37

Obstacle to implement applications via MPC
 While research on protocol design is ongoing, there is still a significant obstacle toimplement the applications via MPC.
 It is too hard to describe the complex function as a mixed circuit and implement iteven for an expert.

Solution to overcome this obstacle is a general-purpose compiler.
13© NEC Corporation 2021

General-purpose compiler[A+18] Toshinori Araki, Assi Barak, Jun Furukawa, Marcel Keller, Yehuda Lindell, Kazuma Ohara, and Hikaru Tsuchida.
Generalizing the SPDZ Compiler For Other Protocols. ACM-CCS 2018, pp.880-895.

General-purpose compiler General-purpose MPC compiler can compile the high-level descriptions into the
MPC operations based on various MPC protocols.
 Ex) SPDZ (also known as SCALE-MAMBA), MP-SPDZ, Obliv-C, …

 Researchers and developers around the world are interested in the generalpurpose compiler.
 SoK paper in IEEE S&P’19• HASTINGS, Marcella, et al. SoK: General purpose compilers for secure multi-party computation. In: 2019 IEEE symposium on security andprivacy (SP). IEEE, 2019. p. 1220-1237.

 Contributed talk in RWC’20• https://rwc.iacr.org/2020/slides/Hastings.pdf

15© NEC Corporation 2021

38

SPDZ (@CRYPTO’14, Eurocrypt’18, etc.)
 SPDZ compiler

 It takes the high-level description (Program) as input and outputs the intermediate code (Bytecode)with optimization.

 SPDZ VM

 It takes the pre-computed values (Prep) as inputs, interprets Bytecode as MPC operations based on
SPDZ protocols, and run it.
Programming
Front-end

Computation
Back-end

Compiler

InputsBytecode

OutputProgram

16

Prep
VM

© NEC Corporation 2021

SPDZ (@CRYPTO’14, Eurocrypt’18, etc.)
 SPDZ compiler

 It takes the high-level description (Program) as input and outputs the intermediate code (Bytecode)with optimization.

 SPDZ VM

 It takes the pre-computed values (Prep) as inputs, interprets Bytecode as MPC operations based on
SPDZ protocols, and run it.
Programming
Front-end
Compiler

Remark:Computation
InputsPrep
Back-end
1. Program is a Python-like code.

Program

17

VM
Bytecode
2. It is enough for the developer to pay
attention only to the description of
Program, and there isno need to know
Output
MPC.

© NEC Corporation 2021

NEC-SPDZ
 In [A+18], we extended the SPDZ compiler to work with not only SPDZ protocols
but various MPC protocols including SS-3PC.
 NEC-SPDZ is the variants of extended SPDZ compiler and VM working with SS3PC.
 https://github.com/nec-mpc

 The following applications can run on NEC-SPDZ.
1.
2.

18

Decision tree evaluation
Hierarchical mixture of experts evaluation© NEC Corporation 2021

39

Private decision tree evaluation via three-party
computation[A+18] Toshinori Araki, Assi Barak, Jun Furukawa, Marcel Keller, Yehuda Lindell, Kazuma Ohara, and Hikaru Tsuchida.
Generalizing the SPDZ Compiler For Other Protocols. ACM-CCS 2018, pp.880-895.

Decision tree It is a commonly-used tool for decision support and widely studied in machinelearning.
 ex. credit decision If it takes 𝐴𝐴𝐴𝐴𝐴𝐴𝐴 𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴 𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴 𝐴 20, 600, 𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇 as inputs, then it outputs RISKY.
Age < 35
False

True

Income < 500

20

Residence == Silicon Valley

False

True

SAFE

RISKY

False

True

RISKY

SAFE

© NEC Corporation 2021

Decision tree It is a commonly-used tool for decision support and widely studied in machinelearning.
 ex. credit decision If it takes 𝐴𝐴𝐴𝐴𝐴𝐴𝐴 𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴 𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴 𝐴 20, 600, 𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇 as inputs, then it outputs RISKY.
1. Choose the featurefrom inputs
Ex) Age = 20

Age < 35
False

True

Income < 500

21

False

True

SAFE

RISKY

Residence == Silicon Valley
False

True

RISKY

SAFE

© NEC Corporation 2021

40

Decision tree It is a commonly-used tool for decision support and widely studied in machinelearning.
 ex. credit decision If it takes 𝐴𝐴𝐴𝐴𝐴𝐴𝐴 𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴 𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴 𝐴 20, 600, 𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇 as inputs, then it outputs RISKY.
Age < 35
False

True

Income < 500

22

2. Compare thefeature and thedecision valueEx.) Age = 20 < 35

Residence == Silicon Valley

False

True

SAFE

RISKY

False

True

RISKY

SAFE

© NEC Corporation 2021

Decision tree It is a commonly-used tool for decision support and widely studied in machinelearning.
 ex. credit decision If it takes 𝐴𝐴𝐴𝐴𝐴𝐴𝐴 𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴 𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴 𝐴 20, 600, 𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇 as inputs, then it outputs RISKY.
Age < 35
False

True

Income < 500

23

3. Compute the pathEx) Age = 20 < 35 (True)
Residence = Tokyo!= Silicon Valley (False)

Residence == Silicon Valley

False

True

SAFE

RISKY

False

True

RISKY

SAFE

© NEC Corporation 2021

Decision tree It is a commonly-used tool for decision support and widely studied in machinelearning.
 ex. credit decision If it takes 𝐴𝐴𝐴𝐴𝐴𝐴𝐴 𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴 𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴 𝐴 20, 600, 𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇 as inputs, then it outputs RISKY.
Age < 35
False

True

3. Compute the pathEx) Age = 20 < 35 (True)
Residence = Tokyo!= Silicon Valley (False)

Income < 500
Residence == Silicon Valley
Remark:Private decision tree
based on SS-3PC
outputs theTrue evaluation (PDTE)
False
True
share of the chosen label without revealing confidential
information of tree
and sensitive
information of input.
SAFE
RISKY
RISKY
False

SAFE

24

© NEC Corporation 2021

41

Experimental setting of PDTE
 Task Credit decision Structure of tree It is built from real data published for the following paper.

• Vivek Kumar Singh, Burcin Bozkaya, Alex Pentland, Money Walks: Implicit Mobility Behavior and Financial Well-Being,
PLoS ONE 10(8): e0136628. https://doi.org/10.1371/journal.pone.0136628

 It has 1,256 leaves at depths from 4 to 30.

 Environments

 AWS m5.12xlarge instances in a single region providing 10Gbps network communication

25© NEC Corporation 2021

Single execution of PDTE
 The execution time of PDTE via SS-3PC is shorter than that via the other MPC
protocols.
Resource

Security(𝑛𝑛𝑛𝑛# parties
𝑡𝑡𝑡 # corruptions)

Online time[sec]

1 core# rounds
Precomputation
time [sec]26

48 cores

SS-3PC(ℤ𝟐𝟐𝒌𝒌 )SPDZ(𝔽𝔽� )

Semihonest
𝒕𝒕 𝒕 𝒕𝒕𝒕𝒕𝒕
0.4641

Malicious(※2)
𝑡𝑡 𝑡𝑡𝑡2746

783

0.3005(Not
5.2204required) (※3)

[LN17](𝔽𝔽� )

Malicious(※2)
𝑡𝑡 𝑡𝑡𝑡𝑡𝑡
3.0416

BMR (※1)

Malicious(※2)
𝑡𝑡 𝑡𝑡𝑡0.5353

584

28

(Not
required)

1041.8※1… BMR ran on i3.2xlarge instances. ※2… The malicious security is stronger than the semi-honest security. ※3… It ran on r4.8xlarge instances.
[LN17] Lindell, Yehuda, and Ariel Nof. "A framework for constructing fast MPC over arithmetic circuits with malicious adversaries and an honestmajority." Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. 2017.

© NEC Corporation 2021

Batch vectorization of PDTE
 We have implemented the batch vectorization of PDTE at a single machine.

PDTE via
SS-3PC

Non-batch[sec]

Batch × 1
[sec]

Batch × 64
[sec]

0.464

2.949

5.945

Non-batch: 0.464 [sec]Batch × 1 : 2.949 [sec]⇒ It is slowed down by
the overhead ofparallel processing.

27

Batch × 1 : 2.949 [sec]Batch × 64 : 5.945 [sec]⇒ Even if the parallelism is multiplied by 64,
the execution time is only about 2x.
⇒ Inference of decision trees can be donein less than 0.1 seconds on average.

© NEC Corporation 2021

42

Private hierarchical mixture of experts evaluation
via three-party computation[M+20] Yusaku Maeda, Hikaru Tsuchida, Kazuma Ohara, Ryo Furukawa, Isamu Teranishi, and Koji Nuida.
Implementation and Evaluation of Prediction by Heterogeneous Mixture Models based on Three-Party
Secure Computation. SCIS 2020, 3C3-5.

Hierarchical mixture of experts (HME) Loosely speaking, HME is almost the same as the decision tree, but differs in that it
assigns experts (not labels) to leaves.

Condition 1
False

True

Condition 3

𝑦𝑦 𝑦 𝑦𝑦� ⋅ 𝑥𝑥𝑥 𝑥 𝑥𝑥�
29

Condition 2
True

False

False

𝑦𝑦 𝑦 𝑦𝑦� ⋅ 𝑥𝑥𝑥 𝑥 𝑥𝑥�

True

𝑦𝑦 𝑦 𝑦𝑦� ⋅ 𝑥𝑥𝑥 𝑥 𝑥𝑥�

𝑦𝑦 𝑦 𝑦𝑦� ⋅ 𝑥𝑥𝑥 𝑥 𝑥𝑥�

© NEC Corporation 2021

Hierarchical mixture of experts (HME) Loosely speaking, HME is almost the same as the decision tree, but differs in that it
assigns experts (not labels) to leaves.

Condition 1
False

True

Condition 3
False

Condition 2
True

False

True

Remark:1. An application of HME is electricity demand forecasting.
𝑦𝑦 𝑦 𝑦𝑦� ⋅ 𝑥𝑥𝑥 𝑥 𝑥𝑥�
𝑦𝑦 𝑦 𝑦𝑦� ⋅ 𝑥𝑥𝑥 𝑥 𝑥𝑥�
𝑦𝑦 𝑦 𝑦𝑦� ⋅ 𝑥𝑥𝑥 𝑥 𝑥𝑥�
𝑦𝑦 𝑦share𝑦𝑦� ⋅ 𝑥𝑥𝑥 of𝑥 𝑥𝑥the�
2. Private
HME evaluation (PHMEE)
based on SS-3PC
outputs theresult of the chosen expert without revealing confidential informationof tree and sensitive information of input.
30© NEC Corporation 2021

43

Experimental setting of PHMEE Tree is pre-trained by synthetic data.
 Environments

 Each server: Intel (R) Xenon (R) CPU E5-2697 v4 @ 2.30 GHz

 We use three servers providing 10Gbps network communication.

31© NEC Corporation 2021

Execution time change of PHMEE by change in # dimension of input vector
 Height of tree: 4

 Number of input data : 10
# Dimensionof input vector plaintext
1

2
4

ିଵ

ିହ

ିଵ

ିଵ
ିଵ

ିହ

5

MPC
(floating-point
number)

ିହ
ିହ

3

32

Execution time [sec]MPC(fixed-point
number)ିଵିହ

Remark:As # dimension increases, the execution time over MPC of fixed-point/floating-point
number increases by about 0.056/0.86 seconds.

© NEC Corporation 2021

Execution time change of PHMEE by change in height of tree
 # dimension of input vector : 3
 Number of input data
Height of tree

2

3
4
5
6

: 10
Execution time [sec]plaintext

MPC(fixed-point
number)MPC(floating-point
number)

ିହ

ିଶ

ିହ

ିଵ

ିଵ

ିହ

ିଵ

ିଵ

ିହ

ିଵ

ିହ

Remark:As the height of tree increases, the execution time over MPC increases exponentially.
33© NEC Corporation 2021

44

Execution time change of PHMEE by change in number of input data
 # dimension of input vector : 3
 Height of tree

Number of input
data

: 3

Execution time [sec]plaintext

1
10
20
30
40

MPC

MPC

(fixed-point number)(floating-point number)

ି଺

ିଶ

ିହ

ିଵ

ିଵ

ିହ

ିଵ

ିଵ

ିହ

ିଵ

ିହ

Remark:As the number of input data increases by one, the execution time over MPC
of fixed-point/floating-point number increases by about 0.019/0.265
seconds.
34© NEC Corporation 2021

Conclusion

Conclusion
 SS-3PC [A+16] over the ring has gained attention in recent years because it canachieve high throughput.
 By using the general-purpose compiler, MPC applications (e.g., machine learning
applications) can be implemented and evaluated by non-experts.
 Ex) PDTE [A+18] and PHMEE [M+20]

36© NEC Corporation 2021

45

46

IMI Workshop: Exploring Mathematical and Practical Principles
of Secure Computation and Secret Sharing
November 8–10, 2021, Kyushu University

Evolving Secret Sharing
From Evolving Perfect Hash Families
Kirill Morozov
University of North Texas
Kirill.Morozov@unt.edu
The concept of Evolving Secret Sharing introduced by Komargodski, Naor and Yogev [4] puts forward an idea of maintaining secret sharing schemes with potentiallyinfitine number of participants. Specifically, in this framework, new shares are generated for new participants on demand, and no communication with old participants isrequired.
Armed with the relation between perfect hashing families (PHF) and secret sharing
schemes [2, 1, 5], we introduce an evolving (non-abelian) multiplicative secret sharing
scheme. An importance of secret sharing over non-abelain groups is that it encompasses, e.g., permutation groups—a basis for MIX operations used, in particular, inelectronic voting.
To achieve our goal, we introduce a novel concept of Evolving PHF. In these families,
a domain of the hash function is not known in advance, but may be increased in the
future—according to a particular application. The framework of Evolving PHF may
be of independent interest, and it may encompass other combinatorial objects.
This talk is based on a joint work with Yvo Desmedt and Sabyasachi Dutta [3].
References[1] Blackburn, S. R., Burmester, M., Desmedt, Y. and Wild, P. R. , “Efficient multiplicative sharing
schemes”, Eurocrypt ’96, LNCS 1070 , 107-118 (1996)[2] Desmedt, Y., Di Crescenzo, G. and Burmester, M., “Multiplicative Non-abelian Sharing Schemes
and their Application to Threshold Cryptography”, Asiacrypt ’94: 21-32 (1994)[3] Desmedt, Y., Dutta, S., Morozov, K. “Evolving Perfect Hash Families: A Combinatorial Viewpoint of Evolving Secret Sharing”, CANS 2019: 291-307 (2019)[4] Komargodski, I., Naor, M. and Yogev, E., “How to Share a Secret, Infinitely”, TCC (B2) 2016:
485-514 (2016)[5] Safavi-Naini R., Wang H., “Robust Additive Secret Sharing Schemes over Zm . Cryptography
and Computational Number Theory. Progress in Computer Science and Applied Logic, vol 20:
357-368, Birkhauser (2001)47

Evolving Secret Sharing
From Evolving Perfect Hash Families
Kirill Morozov (諸蔵 霧流)
University of North Texas

IMI Workshop of the Joint Research Projects
Exploring Mathematical and Practical Principles
of Secure Computation and Secret Sharing
November 9, 2021

Credits• This presentation is based on a joint work with Yvo Desmedt(University of Texas at Dallas) and Sabyasachi Dutta(University of Calgary), published at CANS 20192

Plan of this talk• Short introduction of UNT• Secret sharing and its applications• Evolving secret sharing (Komargodski, Naor, Yogev, TCC 2016)• Secret sharing from perfect hashing (multiplicative scheme)• Evolving perfect hash families: definition and construction• Implication for secret sharing• Conclusion and future works
348

University of North Texas (UNT)• Celebrating 130 years in 2020

• Tier One research university
by the Carnegie Classification• 40,000 students enrolled• Location: Denton, Texas• Part of the Dallas-Fort Worth metroplex• 25 miles to DFW International Airport
4

Cybersecurity research and education at UNT• Center for Information and Cyber Security (CICS) https://cics.unt.edu• Research areas: blockchain applications, network security, cloudsecurity, cryptographic protocols, privacy-preserving computation, …
• NSA/DHS National Center of Academic Excellence (CAE)• BSc and MSc in Cybersecurity offered by
the Department of Computer Science and Engineering (CSE), UNT• Growing graduate enrollment, CSE department is now hiring

5

Secret sharing and its applications

649

Secret sharing[Blakley, AFIPS’79][Shamir, Commun. ACM‘79]

Dealers – secret data
“shares” ofthe secret

s1

s2

s3

Parties:. . . . .

• “Forbidden sets” of shares provide no information about the secret• “Access sets” of shares allow for efficient reconstruction
7

Information-theoretic vs. computational security• Computationally secure cryptographic systems(overwhelming majority of practical protocols, e.g., TLS):• Rely on unproven complexity assumptions• Threatened by advances in algorithm theory
and in computing technologies (e.g., quantum)• Require continuous security evaluationand extension of key sizes• Information-theoretically secure systems rely on
physical assumptions (part of communication model)

8

Applications of secret sharing
Building block for:• Threshold cryptography• Multi-party computation• Perfectly secure message transmission•…

“Multi-signatures”
used in cryptocurrencies
E-voting
E-auctions
E-commerce
E-government

Stand-alone protocol for:• Secure and reliable storage (e.g., in the cloud setting)
•…

50

9

Application of secret sharing for cloud storage• Goal: Security + reliability

User datas

S1 (share)
Storage
Provider 1S2 (share)

Sn (share)

Storage
Provider 2Storage
Provider n• Example: SecureSlice, a component of IBM Cloud Object Storage
10

Shamir (k,n) Threshold Secret Sharing[Shamir, Commun. ACM 22(11) ’79]

• Share Generation: Dealer chooses

fs(x)fs(x) R Fp[X]: deg(fs)  k-1,

fs(x) = s + b1x + b2x2 + … + bk-1xk-1• s is the secret, bj R Fp , 1  j  k-1, p>n

s
0

1

2

3

…

n

• shares are si = fs(i), 1  i  n• Reconstruction: Using Lagrange interpolation,
any subset of k parties can compute the secret s
11

Example application: Long-term storage• As new storage providers emerge and old ones go out of business,
it would be convenient for the data owner (dealer) to keep adding
providers (parties) on the rolling basis• Problem: Scalability, as we need p > # parties for Shamir’s scheme• What if the number of parties is not known in advance?
• E.g., potentially infinite• May choose a large “p” but still cannot support
infinitely many parties
1251

Solutions• [Cachin ‘95], [Csirmaz and Tardos, ‘12]: On-line secret sharing• # of authorized sets a party can join is bounded• [Komargodski, Naor, Yogev ‘16]: Evolving secret sharing• More efficient, no limitation as above• Many follow-up works

13

Comparison of secret sharing protocols• Secret redistribution (Wong, Wing, Wang ‘02):
The parties change access structure
without involving the dealer (e.g., enroll new members)• Note: No secret reconstruction is done
• Evolving secret sharing: The dealer adds parties on demand• Note: The dealer knows the secret(or can reconstruct it using existing parties)
14

Evolving secret sharing (KNY16)• General evolving access structures:
The size of T-th participant’s share is 2T-1
• Evolving k-threshold’s share size:
’(T) = log T + (k-1)·max{ log T + k , (log T +k) },where the share size of the base scheme is (t)• When Shamir secret sharing is the base scheme• Let us consider this construction for k=2• (Any two parties can reconstruct the secret)
15

52

16

KNY16 (2,)-threshold scheme• Secret s  GF(p);bi R GF(p)• Divide parties in “generations”; gen. g has Size(g) = 2g
• Party T belongs to generation g = log T
• (k,n)-threshold Shamir sharing of s  GF(p) is denoted by Sh(k,n)(s)• Gen 0 : P1 [ b1 ]• Gen 1 : P2 [ s + b1 , b2 , Sh1(2,2)(s) ] ; P3 [ s + b1 , b2 , Sh1(2,2)(s) ]• Gen 2 : P4 [ s + b1 , s + b2 , b3 , Sh2(2,4)(s) ] ; P5 [ s + b1 , s + b2 , b3 , Sh2(2,4)(s) ]P6 [ s + b1 , s + b2 , b3 , Sh2(2,4)(s) ] ; P7 [ s + b1 , s + b2 , b3 , Sh2(2,4)(s) ](2,)-threshold scheme:
Correctness and security (sketch)
Gen 0 : P1 [ b1 ]Gen 1 : P2 [ s + b1 , b2 , Sh1(2,2)(s) ] ; P3 [ s + b1 , b2 , Sh1(2,2)(s) ]Gen 2 : P4 [ s + b1 , s + b2 , b3 , Sh2(2,4)(s) ] ; P5 [ s + b1 , s + b2 , b3 , Sh2(2,4)(s) ]P6 [ s + b1 , s + b2 , b3 , Sh2(2,4)(s) ] ; P7 [ s + b1 , s + b2 , b3 , Sh2(2,4)(s) ]• Reconstruction: Gen 0 (P1) uses b1 with any party down the generations• Security: One-time pad (p-ary)• Reconstruction: Gen 1: Within the same generation, use Shamir’s share,
down the generations, use b2• Security: Within the same generation, Shamir’s scheme
17
down the generations, one-time pad(2,)-threshold scheme:
Correctness and security (sketch), cont.
Gen 0 : P1 [ b1 ]Gen 1 : P2 [ s + b1 , b2 , Sh1(2,2)(s) ] ; P3 [ s + b1 , b2 , Sh1(2,2)(s) ]Gen 2 : P4 [ s + b1 , s + b2 , b3 , Sh2(2,4)(s) ] ; P5 [ s + b1 , s + b2 , b3 , Sh2(2,4)(s) ]P6 [ s + b1 , s + b2 , b3 , Sh2(2,4)(s) ] ; P7 [ s + b1 , s + b2 , b3 , Sh2(2,4)(s) ]• To continue, apply the same reasoning as in the previous slide, recursively• Reconstruction: Gen 2: Within the same generation, use Shamir’s share,
down the generations, use b3• Security: Within the same generation, Shamir’s scheme
down the generations, one-time pad
1853

Discussion• A (k,)-threshold scheme was also presented in [KNY16]• Out of scope today• For the above (2,)-threshold scheme, we need to work overa field (because Shamir’s scheme is used)19

Our goals• Understand combinatorial interpretation of evolving secretsharing schemes• Avoid the use of finite fields• To accommodate the most general case,e.g., a permutation group (which is non-abelian)

20

Perfect hash family – Definition• A family of functions F is called an (N;n,m,w)-Perfect Hash Family(PHF), if:• Each f  F : [n] → [m] with |F| = N, and• For any w-subset X  [n],  g  F : g|X is one-to-one

2154• A family of functions F is calledan (N;n,m,w)-Perfect Hash Family (PHF), if:• Each f  F : [n] → [m] with |F| = N, and• For any w-subset X  [n],f1 fi  F : fi|X is one-to-one

PHF – Example
0 1 2 3

M =

4

5 6

7

0 0 0 0 1 1 1 1
0 0 1 1 0 0 1 1
0 1 0 1 0 1 0 1

f2
f3• i-th row represents a function fi : {0,1}3 → {0,1}• For any 2-subset S  {0,1}3  i s.t. fi restricted to S is one-to-one• E.g., restrict to {2,3}, then f3 is one-to-one,
restrict to {1,2}, then f2 and f3 are one-to-one
22

Remark on PHF• Any binary matrix with pairwise distinct columns represents a PHF• Fact: For any t  2, there exists a ( t ; 2t, 2, 2)-PHF
0 1 2 3

M =

4

5 6

7

0 0 0 0 1 1 1 1
0 0 1 1 0 0 1 1
0 1 0 1 0 1 0 1

f1
f2

M represents a (3,8,2,2)-PHF

f3

23(2,n)-threshold secret sharing from PHF
0 1 2 3

M =

4

5 6

7

0 0 0 0 1 1 1 1
0 0 1 1 0 0 1 1
0 1 0 1 0 1 0 1

f1
f2
f3

[Desmedt, DiCrescenzo, Burmester: Asiacrypt ‘94]
[Safavi-Naini, Wang: Progress in CS and Applied Logic ‘02]

• Secret s  G() ; parties Pj , j = 0..7
• ShareGen: For i = 1..3 : bi R G(), share of Pj : sM[i,j]  bi for i = 1..3

• Example: Share of P0 : ( b1 , b2, b3 ), Share of P1 : ( b1 , b2, sb3 )• Reconstruction: Solve the system xb3 = sb3 to obtain the secret s• Security: One-time pad (q-ary, multiplicative)

55

24

(2,n)-threshold secret sharing from PHF (cont.)
0 1 2 3

M =

4

5 6

7

0 0 0 0 1 1 1 1
0 0 1 1 0 0 1 1
0 1 0 1 0 1 0 1

f1
f2
f3

• Secret s  G() ; parties Pj , j = 0..7
• ShareGen: For i = 1..3 : bi R G()• Share of Pj : sM[i,j]  bi for i = 1..3

• In general: Reconstruction follows by the w-subset (last) propertyof PHF• Question: Can we construct an evolving scheme?
• Natural approach: “Evolving” PHF
25

Preliminary definitions• Def.: Evolving family of sets: A sequence of sets {Xn}n0
is an evolving family of sets if Xi  Xi+1 for all i0,
i.e., the family is strictly monotone increasing• Def. (Partial function): A rule X → Y is called a partial function,
if there exists a subset X’ X s.t. when restricted to X’,
f|X’ : X’ → Y is a (total) function
26

Evolving Perfect Hash Functions – Definition• Def.: Let {Xr} be an evolving family of sets, {Yr} be a sequence ofsets (which may or may not be evolving) and {wr} be a nondecreasing sequence of positive integers
A sequence of families of partial and total functions {Fr} is calledan ( {Xr}, {Yr}, {wr} )-Evolving PHF, if:• Each f  Fr is a partial/total function from Xr → Yr and• For any wr-subset X’ Xr , there exists g  Fr such thatthe restriction of g of X’ is one-to-one
2756Remarks• In the paper, we make a distinction between “evolving” PHF
family, which is finite and “perpetually evolving”, which is infinite• In such the families, only the sequence of domains {Xr} needs tobe an evolving family of sets
• The sequence of co-domains {Yr} need not be evolving, in fact,
it can be constant, i.e., Yr = Y for all r• In addition, the non-decreasing sequence of {wr} can bea constant sequence28

Our proposal of Perpetually Evolving PHF• Focus on the binary case, i.e.,
co-domain Yr = Y = {0,1} and wr = w = 2, for all r• Notation: An m-dimensional vector of zeroes as 0m
and that of ones as 1m• After introduction of r-th partial row, the evolved matrix isdenoted as M(r)• Denote the non-zero columns of M as C1,…,C2t-1• Each of them is a t-bit column vector

29

Our construction• Consists of the following three procedures:• Init: Assign 0t as the first column of M(0)• 1st Partial Row:
1. Place the remaining 2t-1 columns C1,…,C2t-1 to the right of 0t
2. Append a partial row 02t-1 just below them
3. Copy C1,…,C2t-1 to the right as columns 2t+1 to 2t+1-1
4. Append a partial row 12t-1 just below the columns copied above
30

57

Our construction (cont.)• r-th Partial Row to M(r-1):
1. Choose the last a = /2 columns B[1], B[2], …, B[a] of M(r-1),
where  denotes # columns in M(r-1)
2. Append a partial row 0a just below B[1], B[2], …, B[a]3. Copy B[1], B[2], …, B[a] to the right of M(r-1)
4. Append a partial row 1a just below the columns copied above

31

Example: Evolving PHF
0 1 2 3

M(0) := M =

4

5 6

7

0 0 0 0 1 1 1 1
0 0 1 1 0 0 1 1
0 1 0 1 0 1 0 1• Let us with a PHF defined by M
• Denote it as M(0)• Next, let us compute the next generation M(1)32

Example: Evolving PHF (cont.)
C1 C2 C3 C4 C5 C6 C7

M(1) =

0 0 0 0 1 1 1 1 0 0 0 1 1 1 1
0 0 1 1 0 0 1 1 0 1 1 0 0 1 1
0 1 0 1 0 1 0 1 1 0 1 0 1 0 1
0 0 0 0 0 0 0 1 1 1 1 1 1 1• Init: 1st column is all-zero.
• 1st Partial Row: 1. The remaining columns C1,…,C7 are to the right of 03
2. Append a partial row 07.
3. Copy C1,…,C7 to the right.
4. Append a partial row 17.
33

58

Example (cont.)
C0 C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 C11 C12 C13 C14

M(1) =

0 0 0 0 1 1 1 1 0 0 0 1 1 1 1
0 0 1 1 0 0 1 1 0 1 1 0 0 1 1
0 1 0 1 0 1 0 1 1 0 1 0 1 0 1
0 0 0 0 0 0 0 1 1 1 1 1 1 1• This is an empty entry (partial function)• Claim: M(1) defines a (partial) PHF• Proof sketch: C0 and each block individually is M(0) => PHF;
across the blocks, use the last row

Example(cont.)
M(2) =

Block A

Block B0 0 0 0 1 1 1 1 0 0 0 1 1 1 1
0 0 1 1 0 0 1 1 0 1 1 0 0 1 1
0 1 0 1 0 1 0 1 1 0 1 0 1 0 1
0 0 0 0 0 0 0 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0

34

Block C

1 0 0 0 1 1 1 1
1 0 1 1 0 0 1 1
1 1 0 1 0 1 0 1
0 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1• Claim: M(2) defines a (partial) PHF• Consider the blocks of columns A, B and C as marked above• Any pair of columns in Blocks B and C differ in at least position due to the last row• Any pair of columns in Block A and Block B (resp. Block C ) differ in at least one
position because M(1) is PHF
35

Main result• Thm.: Our construction implements a perpetually evolving PHF.
• Proof (sketch): By induction.
• The base case intuition: two slides back.
• The induction step intuition: the previous slide.

• Corollary: There exists an evolving (2,)-threshold multiplicative
secret sharing scheme• Note: The underlying group may be non-abelian
36

59Parameters and share size
• If the 1st column of M(0) is t-dimensional, r-th partial row adds
(3/2)r-12t new columns, i.e., increases the domain byexponentially many elements• Share size for T-th participant: ( t + O(log(r,T)) )·log|G|37

Conclusion• Studied a combinatorial interpretation of evolving secret sharing• Proposed a recursive construction of perpetually evolving PHF• It implies an evolving (2,)-threshold multiplicative secretsharing scheme

38

Future work
• Further study of evolving combinatorial objects• Blueprint: Start with a recursive construction for such,and develop it into an evolving scheme• Extension to (k,)-threshold case39

60

References
1. Blakley, G.R.: Safeguarding cryptographic keys. AFIPS 1979.
2. Cachin, C.: On-line secret sharing. Cryptography and Coding, 1995.
3. Csirmaz, L., Tardos, G.: On-line secret sharing. Des. Codes Crypt. 63(1), 2012.
4. Desmedt, Y., Di Crescenzo, G., Burmester, M.: Multiplicative non-abelian sharing
schemes and their application to threshold cryptography. ASIACRYPT 1994.
5. Desmedt, Y., Dutta, S., Morozov, K.: Evolving Perfect Hash Families: A Combinatorial
Viewpoint of Evolving Secret Sharing, CANS 2019.
6. Komargodski, I., Naor, M., Yogev, E.: How to share a secret, infinitely. TCC 2016.
7. Safavi-Naini, R., Wang, H.: Robust additive secret sharing schemes over Zm.
Cryptography and Computational Number Theory. Progress in Computer Science andApplied Logic (20), 2001.
8. Shamir, A.: How to share a secret. Commun. ACM 22(11), 1979.
9. Wong, T. M., Wang, C., and Wing, J. M.: Verifiable secret redistribution for archive
system,” IEEE Security in Storage Workshop, 2002.
40

Thank you very muchfor your attention,and questions, please!
(Kirill.Morozov@unt.edu)

61

IMI Workshop: Exploring Mathematical and Practical Principles
of Secure Computation and Secret Sharing
November 8–10, 2021, Kyushu University

Secure-Computation AI : a Python Library for
Machine Learning in Secure Computation
Ibuki Mishina (Joint work with Dai Ikarashi, Koki Hamada
and Ryo Kikuchi)
NTT Corporation
ibuki.mishina.br@hco.ntt.co.jp
Big data analysis using machine learning (AI) is expected to be a technology thatenables complex analysis and inference, but because it requires a large amount of data,
including personal information, it often faces issues related to privacy. Therefore, as asolution to this problem, a technology has been attracting attention in recent years, inwhich learning and inference is calculated while keeping data encrypted using securecomputation.
Research on secure computation for machine learning, especially deep learning has
been very active in the past few years, and faster methods have been proposed one
after another[1]. In addition, there has been research in the area of proposing andimplementing easy-to-understand software framework for machine learning researchersand engineers[2]. Thus, various researches on secure computation for machine learning
are being conducted, not only on performance but also usability and so on.
In our research, we have implemented various machine learning methods such as
logistic regression and deep learning in secure computation with high speed and highaccuracy[3, 4]. Furthermore, we have implemented an software framework for machinelearning in secure computation as a Python library[5], with an application programming
interface similar to general machine learning libraries. Our secure-computation AI ischaracterized by high performance in terms of accuracy and processing speed, a richlineup of analyses, and ease of use, all of which are necessary for an AI library. In thispaper, we introduce the performance, the lineup of analysis methods, and application
programming an interface of our secure-computation AI library.
References[1] Wagh, Sameer and Tople, Shruti and Benhamouda, Fabrice and Kushilevitz, Eyal and Mittal,
Prateek and Rabin, Tal. Falcon: Honest-majority maliciously secure framework for private deeplearning. arXiv preprint arXiv:2004.02229, 2020.
[2] Knott, Brian and Venkataraman, Shobha and Hannun, Awni and Sengupta, Shubho and Ibrahim,
Mark and van der Maaten, Laurens. CrypTen: Secure multi-party computation meets machinelearning. arXiv preprint arXiv:2109.00984, 2021.
[3] Ibuki Mishina, Koki Hamada, Dai Ikarashi and Ryo Kikuchi. Fast and Accurate Logistic Regression and Data Standardization Using Secure Real Number Operations. In CSS(in Japanese),
2020.
[4] Ibuki Mishina, Koki Hamada and Dai Ikarashi. Realization of Practical Secure Deep Learning.
In CSS(in Japanese), 2019.
[5] Ibuki Mishina, Koki Hamada, Dai Ikarashi and Ryo Kikuchi. A Design and an Implementationof a Python Library for Secure Deep Learning. In SCIS(in Japanese), 2021.

63

Secure-Computation AI:

a Python Library for Machine Learning
in Secure Computation

NTT Social Informatics Laboratories

Ibuki Mishina

Secure Computation
×

Machine Learning(AI)Outline1. What’s Secure-computation AI?

2. Our Research
1.

Algorithm Impementation

2.

API Implementation
364Outline

1. What’s Secure-computation AI?

2. Our Research
1.

Algorithm Impementation

2.

API Implementation
4

Secure Computation

Computation while keeping data encrypted
Usual computation

Encrypt and store

Secure Computation

Decrypt when in use

Encrypt and store

Use while encrypted
5Machine Learning(AI)Build a model based on training datain order to make inferences• Structural data

Train data and build models• Images• Time-series data
etc…

6

65

Deep Learning
Used for image classification, etc.
Hidden layer

Input
Layer

Output
layer

…
…

…

…

…

…

…

…

dog！
cat！

7

Secure-Computation AI

AI training and inference
while keeping data encrypted• Structural data

Train data and build models• Images• Time-series data
etc…

8Research Topics in Secure-Computation AI• Algorithm Implementation– There are many methods for machine learning– Often the plaintext algorithm cannot be used as is– e.g. secureML, secureNN, ABY3…

• API Implementation– Implement APIs that are easy for data scientists to use– e.g. Crypten(Facebook), tf-encrypted(google)
966Outline

1. What’s Secure-computation AI?

2. Our Research
1.

Algorithm Impementation

2.

API Implementation
10

Our Research Goals• Practical Secure-Computation AI– Many analytical methods available– Fast & high accuracy– Easy-to-use interface for data analysts
11

What we've implemented• Linear Regression(CSS2020)        …

• Logistic Regression(CSS2018/SCIS2019/CSS2019/CSS2020)• Deep Learning(FIT2019/CSS2019/SCIS2020/SCIS2021)

 ∑  

1
1   • Decision Trees & Gradient Booting(CSS2021)• Hierarchical clustering(CSS2021)• Medical Statistics(CSS2019/CSS2020)

1267

Secure Logistic Regression/Linear Regression
Previous Research

Our Research• Optimizer→SGD• Optimizer → Newton-CG
Fast convergence,no need for inverse matrix calculation

Easy, but slow convergence.

13

Secure Deep Learning(1/2)
Previous Research

Our Research• Optimizer→SGD only

• Optimizer → SGD, Adam,
momentum etc…

• Dropout → ×• Dropout → 〇• Scaling → ×• Scaling → 〇Dropout

14

Secure Deep Learning(2/2)
Dataset︓MNIST(784×60,000)
Model : 784→128→128→10(2 hidden layers)
ABY3[MR18]
NTT(SCIS2021)*

time[sec]

accuracy[%]

95

96

2700

94

*CPU︓3.50GHz(8core)×2 / RAM︓768GB / NW︓10G

15

68

Outline

1. What’s Secure-computation AI?

2. Our Research
1.

Algorithm Impementation

2.

API Implementation
16

Famous machine learning libraries(plaintext)• Keras:– deep learning library with a simple interface• Scikit-learn：– Machine learning library for various types of analysis• Pandas:– Libraries to support data analysis

These are all
Python libraries
17

Our Goals

Python Library for Secure-Computation AI
Keras + scikit-learn + pandas

18

69

MEVAL : Secure computation Library• Secret sharing based secret computation library being
developed by NTT• Can be freely programmed to combine more than 100
operations, including arithmetic, logic, comparison, and real
number operations.
• Optimized for secure computation, enabling fast andaccurate processing.
19

Background
Optimized interface for secure computation
is different from plain text↓
For data analysts unfamiliar with secure computation,
an interface optimized for secure computation is difficult
20

Our Contribution
Describes AI program with a simple interface
similar to a plain text library

Convert Python code

program optimized

for secret calculations

21

70

Idea
A secure-computation AI program written in mevalis several thousand lines long,
but there are not many parameters for the data analyst to rewrite.

1. Prepare a secure-computation AI program in which all but
the parameters are described in advance2. Embed parameters specified by the analyst from theplaintext IF into the secure computation program

22

Our Secure-Computation AI Library
import asa Python library
preprocessing

Keras like
NN model design
23

Comparison of Others• Crypten(Facebook), tf-encrypted(google)– Model : Deep Learning only
– Processing performance of secure computation is not high– Interfaces compatible with Pytorch or tensorflow• NTT– Model : Deep Learning, Decision Trees, Clustering, etc…
– Fast & high accuracy
2471Future work
• Further expansion of AI methods• Expansion of functions other than AI methods– Preprocessing, Model evaluation, etc…

• Publishing Secure-Computation AI Library
25

Conclusion• Secure-Computation AI:– AI training and inference while keeping data encrypted• Research Topics in Secure-Computation AI:– Algorithm Implementation• Deep Learning, Logistic Regression, Decision Trees, etc…

– API Impementation• Python Library for Secure-Computation AI
26

72

IMI Workshop: Exploring Mathematical and Practical Principles
of Secure Computation and Secret Sharing
November 8–10, 2021, Kyushu University

Possibility of Secret Sharing using EtherCAT
Kosuke Kaneko
Robert T.Huang Entrepreneurship Center of Kyushu University
kaneko.kosuke.437@m.kyushu-u.ac.jp
In this presentation, we explain the possibility of Secret Sharing using EtherCAT(Ethernet for Control Automation Technology) which is an industrial network
technology. We implemented an algorithm of Secret Sharing using EtherCAT and
evaluated their time performance of encryption/decription. We discuss the possibilityof Secret Sharing using EtehrCAT based on results of the evaluation.

73

Possibility of
Secret Sharing using EtherCAT
Kosuke Kaneko
Robert T.Huang Entrepreneurship Center of Kyushu University

This research was supported by Skydisc, Inc.
Exploring Mathematical and Practical Principles of Secure Computation and Secret Sharing @ IMI, Kyushu University. Nov. 9, 2021.

1

About me! 2014:! Ph.D of Information Science at Kyushu University! 2014 ‒ 2016:! Assistant Professor at Innovation Center for Educational Resource, Kyushu
University Library! 2016 ‒ 2021:! Associate Professor at Cybersecurity Center in Information Infrastracture
Iniciative, Kyushu University! 2021 - :! Associate Professor at Robert T.Huang Entrepreneurship Center, Kyushu
University

Exploring Mathematical and Practical Principles of Secure Computation and Secret Sharing @ IMI, Kyushu University. Nov. 9, 2021.

2

Outline1.

Research Background and Purpose! Smart Factory, EtherCAT! Our IDEA of Secret Sharing X EtherCAT

2.

Method and Implementation! Our proposed protocol

3.

Experiment and Result! Calculation time for encryption/decription

4.

Conclusion and Discussion

Exploring Mathematical and Practical Principles of Secure Computation and Secret Sharing @ IMI, Kyushu University. Nov. 9, 2021.

74

3

Reserch Background

Exploring Mathematical and Practical Principles of Secure Computation and Secret Sharing @ IMI, Kyushu University. Nov. 9, 2021.

4

What is today’s topic?

SecretSharing

EtherCAT

Exploring Mathematical and Practical Principles of Secure Computation and Secret Sharing @ IMI, Kyushu University. Nov. 9, 2021.

5

What is EtherCAT ? - Overview ! Ethernet for Control Automation Technology! A network for industry(factory automation netowrk, belt conveyor)! Device to device communication(master and slaves)! IEEE 802.3 Ethernet/Ethernet Cable

Images fromhttps://monoist.atmarkit.co.jp/mn/a
rticles/1309/17/news001_4.html(Common Open Technology)

EtherCAT Fieldbus
Master

Slave

Slave

Slave

Slave

Slave

Exploring Mathematical and Practical Principles of Secure Computation and Secret Sharing @ IMI, Kyushu University. Nov. 9, 2021.

75

6

Smart Factory Circumstances

Cloud Server! Industry 4.0: Factory x AI

Edge Server! They don’t like to take data outof their factory so much
Factory

Encription?

Machines
Exploring Mathematical and Practical Principles of Secure Computation and Secret Sharing @ IMI, Kyushu University. Nov. 9, 2021.

7

What is our IDEA? (1/2)
Edge Server

EtherCAT Fieldbus
Encryption
Decryption
Data

MasterSlave

Secret Sharing

Slave

Slave

Slave

Slave

Shares(1) Encryption: Data Distribution(2) Decryption: Data Collection
Exploring Mathematical and Practical Principles of Secure Computation and Secret Sharing @ IMI, Kyushu University. Nov. 9, 2021.

8What is our IDEA? (2/2)
EtherCAT Devices (Masters and Slaves)

Edge Server(No Plain Data)
Shares Distribution
Shares Collection

Mst

Slv

Slv

Slv
S

Slv

Slv

Shares Distribution
Shares Collection

Mst

Slv

Slv
S

Slv
S

Slv

Slv

Shares Distribution
Shares Collection

Mst

Slv
S

Slv

Slv

Slv
S

Slv
S

S

Is it a good idea?
Exploring Mathematical and Practical Principles of Secure Computation and Secret Sharing @ IMI, Kyushu University. Nov. 9, 2021.

76

9

Research Purpose! Investigation for discussing possibility of Secret Sharing
with EtherCAT! Evaluation: Calculation time for encryption/decryption! To investigate calculation time by changing situations! Number of slaves in EtherCAT fieldbus! Number of shares for Secret Sharing! Number of required shares for Secret Sharing
Exploring Mathematical and Practical Principles of Secure Computation and Secret Sharing @ IMI, Kyushu University. Nov. 9, 2021.

10

Method and Implementation

Exploring Mathematical and Practical Principles of Secure Computation and Secret Sharing @ IMI, Kyushu University. Nov. 9, 2021.

11

What is EtherCAT ? - Data Frame EtherCAT is based on Ethernet:
Data frame for communication is Ethernet frame.
Ethernet frame
Ethernet EtherCATHeaderHeaderSlave1

Slave2

Slave3

Slave4

…

IN

IN

IN

IN

…

OUT

OUT

Data space

OUT

OUT

FCS

IN: Write
OUT: Read

Exploring Mathematical and Practical Principles of Secure Computation and Secret Sharing @ IMI, Kyushu University. Nov. 9, 2021.

77

12

What is EtherCAT ? - Network Structure ! EtherCAT adopts daisy chain network structure! Each device has two ethernet ports

MasterSlave1

Slave3

Slave2

Slave4

Exploring Mathematical and Practical Principles of Secure Computation and Secret Sharing @ IMI, Kyushu University. Nov. 9, 2021.

13

What is EtherCAT ? - EtherCAT Communication One Ethernet cable has two way paths
Slave1Master…

Slave3

Slave2

Slave1

IN

IN

IN

OUT

OUT

OUT

Slave2

Slave3…

Exploring Mathematical and Practical Principles of Secure Computation and Secret Sharing @ IMI, Kyushu University. Nov. 9, 2021.

14

What is EtherCAT ? - EtherCAT Communication One Ethernet cable has two way paths
Slave1Master…

Slave3

Slave2

Slave1

IN

IN

IN

OUT

OUT

OUT

Slave2

Slave3…

Exploring Mathematical and Practical Principles of Secure Computation and Secret Sharing @ IMI, Kyushu University. Nov. 9, 2021.

78

15

What is EtherCAT ? - EtherCAT Communication One Ethernet cable has two way paths
MasterSlave1

Slave2…

Slave3

Slave3

Slave2

Slave1

IN

IN

IN

OUT

OUT

OUT

…

Exploring Mathematical and Practical Principles of Secure Computation and Secret Sharing @ IMI, Kyushu University. Nov. 9, 2021.

16

What is EtherCAT ? - EtherCAT Communication One Ethernet cable has two way paths
MasterSlave1

Slave2

Slave3…

Slave3

Slave2

Slave1

IN

IN

IN

OUT

OUT

Exploring Mathematical and Practical Principles of Secure Computation and Secret Sharing @ IMI, Kyushu University. Nov. 9, 2021.

OUT

…

17

What is EtherCAT ? - EtherCAT Communication One Ethernet cable has two way paths
MasterSlave1

Slave2…

Slave3

Slave1OUT

IN

Slave2OUT

IN

Slave3OUT

IN…

Exploring Mathematical and Practical Principles of Secure Computation and Secret Sharing @ IMI, Kyushu University. Nov. 9, 2021.

79

18

What is EtherCAT ? - EtherCAT Communication One Ethernet cable has two way paths
Slave1Master…

Slave1OUT

IN

Slave2OUT

IN

Slave3OUT

IN

Slave2

Slave3…

Exploring Mathematical and Practical Principles of Secure Computation and Secret Sharing @ IMI, Kyushu University. Nov. 9, 2021.

19

What is EtherCAT ? - Communication Protocol ! No handshake protocol, not like TCP/IP! Transmission frequency: 125µs (8,000 times/sec.)

MasterSlave1

Slave4

Slave3

Slave2

Exploring Mathematical and Practical Principles of Secure Computation and Secret Sharing @ IMI, Kyushu University. Nov. 9, 2021.

20

What dvantage does EtherCAT has for Secret Sharing?
! Network stracture is originally suitable to Secret Sharing! Devices are distributed in Factory and they communicate each other anytime! Quick communication for shares distribution and collection! No handshake protocol, 8,000 times/sec.
EtherCAT Devices (Masters and Slaves)

Edge Server(No Data)
Shares Distribution
Shares Collection

Mst

Shares Distribution
Shares Collection

Shares Distribution
Shares Collection

Slv

Slv

Slv
S

Slv

Slv

Mst

Slv

Slv
S

Slv
S

Slv

Slv

Mst

Slv
S

Slv

Slv

Slv
S

Slv
S

S

Exploring Mathematical and Practical Principles of Secure Computation and Secret Sharing @ IMI, Kyushu University. Nov. 9, 2021.

80

21

Our Proposed Protocol
Ethernet EtherCATHeaderHeader

(1/3)

Slave1

Slave2

Slave3

Slave4

IN

IN

IN

IN

OUT

OUT

OUT

OUT

FCS

To store a “control symble” into the first bit like:!

“~” is for time out…

“)” is for encription mode

ControlSymbol“!” is for storing shares

Share Data“%” is for check state“^” is for decription mode“&” is for done the process

Exploring Mathematical and Practical Principles of Secure Computation and Secret Sharing @ IMI, Kyushu University. Nov. 9, 2021.

Our Proposed Protocol

22

(2/3)

Transmission frequency: 125µs (8,000 times/sec.)
MasterSlave1

Slave2

Slave3!
…

Slave3

Slave2

Slave1

IN

IN

IN

OUT

OUT

OUT

…

Not Wait

Exploring Mathematical and Practical Principles of Secure Computation and Secret Sharing @ IMI, Kyushu University. Nov. 9, 2021.

Our Proposed Protocol

23

(2/3)

Transmission frequency: 125µs (8,000 times/sec.)
MasterSlave1

Slave2

Slave3&…

Slave3

Slave2

Slave1

IN

IN

IN

OUT

OUT

OUT

…

Exploring Mathematical and Practical Principles of Secure Computation and Secret Sharing @ IMI, Kyushu University. Nov. 9, 2021.

81

24

What is EtherCAT ? - EtherCAT Communication One Ethernet cable has two way paths
Slave1MasterSlave2

Slave3&
Slave1OUT

IN

Slave2OUT

IN

Slave3OUT

IN…

Exploring Mathematical and Practical Principles of Secure Computation and Secret Sharing @ IMI, Kyushu University. Nov. 9, 2021.

25

Experiment and Result

Exploring Mathematical and Practical Principles of Secure Computation and Secret Sharing @ IMI, Kyushu University. Nov. 9, 2021.

26

Experiment Environment
Master Device

Raspberry Pi 3 B+

Slave Devices

EasyCAT Shield for Arduino

EtherCATSOEM Library(https://github.com/OpenEtherCATsociety/SOEM)

Network Tool

Ethernet Cable (CAT7, 1m)

ProtocolOur Proposed Protocol

Secret Sharing

Shamir Secret Sharing(https://github.com/dsprenkels/sss)

Exploring Mathematical and Practical Principles of Secure Computation and Secret Sharing @ IMI, Kyushu University. Nov. 9, 2021.

82

27

Problems! We needed to divide a share into 4 data; it took 4 times long timeto transmit shares.
! Shamir Secret Sharing library (https://github.com/dsprenkels/sss) is
generate 112 bytes size shares.
! EasyCAT Shield for Arduino can transfor only 32 bite in one time.

! Timeout:! Some slave devices could not receive a share sometimes. We set timeout as0.03 sec. If elapsed time was over the timeout, then transmission was
restarted again.
Exploring Mathematical and Practical Principles of Secure Computation and Secret Sharing @ IMI, Kyushu University. Nov. 9, 2021.

Experiment Rule

Master28

Shares are
distributed
randomly

Slave1

Slave2S

Slave3S

Slave4! Exp. 1: To change number of slaves for EtherCAT (2 - 8)
! Exp. 2: To change number of shares for Secret Sharing (2 ‒ 8)
! Exp. 3: To change number of required shares for Secret Sharing (2 - 8)
! Investigation for calcluation times for ecription and decription in each case! To do encription/decription 100 times and calculate average time
Exploring Mathematical and Practical Principles of Secure Computation and Secret Sharing @ IMI, Kyushu University. Nov. 9, 2021.

29

Experiment Scene (8 slaves)

Exploring Mathematical and Practical Principles of Secure Computation and Secret Sharing @ IMI, Kyushu University. Nov. 9, 2021.

83

30

Result: Culculation times for encription by each caseSec.

8 slaves
8 shares6 required shares!"#$"%&!'($)*+&,-)*+&.%'"$/012&.*#$34%)5*&1)6"&708"9:

!"'#

!"'

!"!&

!"!%

!"!$

!"!#

!

#(#

$(#

$($

%(#

%($

%(%

&(#

&)*+,- .*%)*+,- .*$)*+,- .*#)*+,- .*

&($

&(%

&(&

Exploring Mathematical and Practical Principles of Secure Computation and Secret Sharing @ IMI, Kyushu University. Nov. 9, 2021.

31

Result: Culculation times for decription by each caseSec.

!"#$"%&!'($)*+&,-)*+&.%'"$/012&!'($"-&3"#$45%)6*&1)7"&809":;!"!%&$!"!%&!"!%%$!"!%%!"!%!$!"!%!"!!#$

!"!!#

&'&

('&

('(

)'&

)'(

*+,-./ 0,)+,-./ 0,

)')

*'&

(+,-./ 0,

*'(

*')

*'*

&+,-./ 0,

Exploring Mathematical and Practical Principles of Secure Computation and Secret Sharing @ IMI, Kyushu University. Nov. 9, 2021.

32

Result: Compare times by the same scale

Sec.

Sec.

!"#$"%&!'($)*+&,-)*+&.%'"$/012&.*#$34%)5*&1)6"&708"9:

!"'$

!"'$

!"'#

!"'#

!"'

!"'

!"!&

!"!&

!"!%

!"!%

!"!$

!"!$
!"!#

!"!#
!

!"#$"%&!'($)*+&,-)*+&.%'"$/012&!'($"-&3"#$45%)6*&1)7"&809":;

!
#(#

$(#

$($

%(#

%($

%(%

&(#

&)*+,- .*%)*+,- .*$)*+,- .*#)*+,- .*

&($

&(%

&(&

#(#

$(#

$($

%(#

%($

%(%

&(#

&)*+,- .*%)*+,- .*$)*+,- .*#)*+,- .*

&($

&(%

&(&

Timeout was flequently
happened
Exploring Mathematical and Practical Principles of Secure Computation and Secret Sharing @ IMI, Kyushu University. Nov. 9, 2021.

84

33

Slaves: 8, Shares: 3, Required: 2Sec.

!"#$%&'()*$+,-./)'0.1%'2!3#4%&5'67'!"#$%&587'9%:;.$%<5=>

!"!%

!"!$$

!"!$$

!"!$

!"!$

!"!#$

!"!#$

!"!#

!"!#

&
#
'
&!
&(
&%
&)
**
*$
*+
(&
(#
('
#!
#(
#%
#)
$*
$$
$+
%&
%#
%'
'!
'(
'%
')
+*
+$
++
)&
)#
)'
&!!

!"!%

AVE. 0.051 sec.

!"#$%&'?%*$+,-./)'0.1%'2!3#4%&5'67'!"#$%&587'9%:;.$%<5=>

&
#
'
&!
&(
&%
&)
**
*$
*+
(&
(#
('
#!
#(
#%
#)
$*
$$
$+
%&
%#
%'
'!
'(
'%
')
+*
+$
++
)&
)#
)'
&!!

Sec.

AVE. 0.051 sec.

Exploring Mathematical and Practical Principles of Secure Computation and Secret Sharing @ IMI, Kyushu University. Nov. 9, 2021.

34

Conclusion and Discussion

Exploring Mathematical and Practical Principles of Secure Computation and Secret Sharing @ IMI, Kyushu University. Nov. 9, 2021.

35

Conclusion! Calculation times for encryption/decryption weresignificantly influenced by number of shares, but it were
not so much influenced by number of slaves andnumber of required shares.
! If it was good condition (no timeout), it took about 0.05
sec. for encryption/decryption.
Exploring Mathematical and Practical Principles of Secure Computation and Secret Sharing @ IMI, Kyushu University. Nov. 9, 2021.

85

36

Discussion Time

Exploring Mathematical and Practical Principles of Secure Computation and Secret Sharing @ IMI, Kyushu University. Nov. 9, 2021.

86

37

IMI Workshop: Exploring Mathematical and Practical Principles
of Secure Computation and Secret Sharing
November 8–10, 2021, Kyushu University

An indeterminate equation scheme having
homomorphic property
Yasuhiko Ikematsu
Institute of Mathematics for Industry, Kyushu University
ikematsu@imi.kyushu-u.ac.jp
Indeterminate encryption schemes are public key cryptosystems using indeterminate equations having a solution with small coefficients over a finite field. At Sac
2017, Akiyama et al. proposed an indeterminate encryption scheme “Giophantus(TM)”whose public key is a polynomial in two variables over a finite ring. In this talk, we
introduce the construction of the Giophantus scheme and explain that it becomes asomewhat homomorphic encryption (SHE).

87

Exploring Mathematical and Practical Principles
of Secure Computationand Secret Sharing

An Indeterminate Equation Scheme
Having Homomorphic Property*Yasuhiko Ikematsu (Kyushu University)
Koichiro Akiyama (Toshiba Corporation)
10th November 2021

1

PQC

2/19

Post-Quantum Cryptography•

Lattice base・・・SVP, CVP•

Code base・・・Syndrome decoding problem•

Isogeny base・・・Isogeny path finding problem•

Multivariate base・・・MQ problem

NIST PQC standardization third round in 2020
NIST 3rdSignature

Encryption/KEM

Lattice

2

5

Code

0

3

Isogeny01Multivariate

2

0

Else

2

0

Overview

3/19

Ø Indeterminate equation cryptosystem for PQC
Section Finding Problem

𝑋𝑋 𝑥𝑥, 𝑦𝑦 = 0 over 𝔽𝔽! [𝑡𝑡]

Ø GiophantusTM proposed by Akiyama et al.
Small Section Problem

𝑋𝑋 𝑥𝑥, 𝑦𝑦 = 0 over 𝔽𝔽! 𝑡𝑡 / 𝑡𝑡 " − 1Ø Homomorphic property

Additive & Multiplicative88

Contents

4/19§1 Indeterminate equation cryptosystem§2 Giophantus§3 Homomorphic property§4 Conclusioin

1.1 Section finding problem

5/19

𝑞𝑞 ∈ ℕ : prime, 𝑛𝑛 > 0 : integer

𝔽𝔽$ 𝑡𝑡, 𝑥𝑥, 𝑦𝑦 : three-variable polynomial ring

Section Finding Problem

𝑋𝑋 𝑡𝑡, 𝑢𝑢! , 𝑢𝑢# = 0

Given 𝑋𝑋 𝑡𝑡, 𝑥𝑥, 𝑦𝑦 ∈ 𝔽𝔽$ 𝑡𝑡, 𝑥𝑥, 𝑦𝑦

Find one solution (section) (𝑢𝑢! 𝑡𝑡 , 𝑢𝑢# 𝑡𝑡 ) ∈ 𝔽𝔽$ 𝑡𝑡 % with degree 𝑛𝑛.
• If deg !,# 𝑋𝑋 𝑡𝑡, 𝑥𝑥, 𝑦𝑦 > 1, the problem is difficult.

• From this problem, some cryptosystems are constructed.

1.2 Indeterminate equation cryptosystem

6/19

𝑞𝑞 ∈ ℕ : prime, 𝑛𝑛, 𝑑𝑑 > 0 : integer

Secret Key
𝑢𝑢! = 𝑎𝑎& + 𝑎𝑎' 𝑡𝑡 + ⋯ + 𝑎𝑎()' 𝑡𝑡 ()' ∈ 𝔽𝔽$ [𝑡𝑡]𝑢𝑢# = 𝑏𝑏& + 𝑏𝑏' 𝑡𝑡 + ⋯ + 𝑏𝑏()' 𝑡𝑡 ()' ∈ 𝔽𝔽$ [𝑡𝑡]Public Key
𝑋𝑋 𝑡𝑡, 𝑥𝑥, 𝑦𝑦 ∈ 𝔽𝔽$ 𝑡𝑡, 𝑥𝑥, 𝑦𝑦 degree 𝑑𝑑 s.t. 𝑋𝑋(𝑡𝑡, 𝑢𝑢! , 𝑢𝑢# ) = 0 in 𝔽𝔽$ [𝑡𝑡]• Secret key is randomly chosen from 𝔽𝔽$ [𝑡𝑡].

• Public key is obtained by the linear system in 𝑐𝑐*,+## 𝑐𝑐!,# 𝑡𝑡 𝑢𝑢$! 𝑢𝑢% = 0,!,#

where 𝑋𝑋 ≔ ∑!,# 𝑐𝑐!,# (𝑡𝑡)𝑥𝑥 ! 𝑦𝑦 # .

• It is difficult to compute (𝑢𝑢! , 𝑢𝑢# ) from the public key 𝑋𝑋.

891.2 Indeterminate equation cryptosystem
Message:

7/19

𝑚𝑚 𝑡𝑡 = 𝑚𝑚* + 𝑚𝑚+ 𝑡𝑡 + ⋯ + 𝑚𝑚",+ 𝑡𝑡 ",+ ∈ 𝔽𝔽! [𝑡𝑡]Encryption: 1. Randomly choose 𝑟𝑟 𝑡𝑡, 𝑥𝑥, 𝑦𝑦 ∈ 𝔽𝔽 𝑡𝑡, 𝑥𝑥, 𝑦𝑦!

2. Compute 𝑐𝑐 ≔ 𝑚𝑚 + 𝑋𝑋 5 𝑟𝑟

Decryption: 1. Compute𝑐𝑐 𝑢𝑢- , 𝑢𝑢. = 𝑚𝑚 + 𝑋𝑋(𝑡𝑡, 𝑢𝑢- , 𝑢𝑢. ) 5 𝑟𝑟(𝑡𝑡, 𝑢𝑢- , 𝑢𝑢. )= 𝑚𝑚

1.3 Progression of IEC

8/19

𝑐𝑐 = 𝑚𝑚 + 𝑋𝑋 & 𝑟𝑟

multiple structure

Linear Algebra Attack

Reduction Attack

𝑐𝑐 = 𝑚𝑚 𝑡𝑡 & 𝑠𝑠 + 𝑋𝑋 & 𝑟𝑟(𝑡𝑡)three variables

Trace Attack by Voloch

𝑐𝑐 = 𝑚𝑚 & 𝑠𝑠 + 𝑋𝑋 & 𝑟𝑟 PKC2009

noise addition[2]

Ideal Decomposition Attack[3]GiophantusTM

𝑐𝑐 = 𝑚𝑚 𝑡𝑡 + 𝑋𝑋 & 𝑟𝑟 + ℓ & 𝑒𝑒 mod 𝑡𝑡 ! − 1[2] K. Akiyama et al., An Algebraic Surfaces Cryptosytem, PKC2009, LNCS 5443, pp. 425–442[3] J. Faug`ere et al., Algebraic Cryptanalysis of the PKCʼ09 Algebraic Surface Cryptosystem, PKC2010, LNCS 6056, pp. 35–52

Contents

9/19§1 Indeterminate equation cryptosystem§2 Giophantus§3 Homomorphic property§4 Conclusioin

902.1 Small section problem

10/19

𝑞𝑞 ∈ ℕ : prime, 𝑛𝑛 > 0 : integer, 𝑙𝑙 > 0 : small integer

𝑋𝑋 𝑥𝑥, 𝑦𝑦 ∈ 𝔽𝔽$ 𝑡𝑡, 𝑥𝑥, 𝑦𝑦 /(𝑡𝑡 ( − 1)

Definition(𝑢𝑢! , 𝑢𝑢# ) ∈ 𝔽𝔽$ 𝑡𝑡 % is called a small section of 𝑋𝑋
if X 𝑢𝑢! , 𝑢𝑢# = 0 and 0 ≤their coefficients≤ 𝑙𝑙 − 1.

Small Section Problem
Given 𝑋𝑋 𝑥𝑥, 𝑦𝑦 ∈ 𝔽𝔽$ 𝑡𝑡, 𝑥𝑥, 𝑦𝑦 / 𝑡𝑡 ( − 1 with a small section,
Find one small section (𝑢𝑢! , 𝑢𝑢# ) of 𝑋𝑋.

Giophantus[4] is constructed based on this problem.

[4] K. Akiyama et al, A Public-key Encryption Scheme Based on Non-linear Indeterminate Equations (Giophantus),
IACR ePrint2017/1241

2.2 Construction

11/19

𝑞𝑞 ∈ ℕ : large prime, 𝑛𝑛, 𝑑𝑑 > 0 : integer, 𝑙𝑙 > 0 : small integer

𝑅𝑅$,( ≔ 𝔽𝔽$ 𝑡𝑡 /(𝑡𝑡 ( − 1)Secret Key
𝑢𝑢! = 𝑎𝑎& + 𝑎𝑎' 𝑡𝑡 + ⋯ + 𝑎𝑎()' 𝑡𝑡 ()'𝑢𝑢# = 𝑏𝑏& + 𝑏𝑏' 𝑡𝑡 + ⋯ + 𝑏𝑏()' 𝑡𝑡 ()', where 0 ≤ 𝑎𝑎* , 𝑏𝑏* ≤ 𝑙𝑙 − 1.

Public Key
𝑋𝑋 𝑥𝑥, 𝑦𝑦 ∈ 𝑅𝑅$,( 𝑥𝑥, 𝑦𝑦 degree 𝑑𝑑 s.t. 𝑋𝑋(𝑢𝑢! , 𝑢𝑢# ) = 0 in 𝑅𝑅$,(• Secret key is randomly chosen from 𝔽𝔽$ [𝑡𝑡].

• Public key is obtained by the linear system in 𝑐𝑐*,+• It is difficult to compute (𝑢𝑢! , 𝑢𝑢# ) from the public key 𝑋𝑋.

2.2 Construction
Message:
Encryption:

Decryption:

12/19

𝑚𝑚 𝑡𝑡 = 𝑚𝑚& + 𝑚𝑚' 𝑡𝑡 + ⋯ + 𝑚𝑚()' 𝑡𝑡 ()' , 0 ≤ 𝑚𝑚* ≤ 𝑙𝑙 − 1
1. Randomly choose 𝑟𝑟 𝑥𝑥, 𝑦𝑦 ∈ 𝔽𝔽$ 𝑡𝑡, 𝑥𝑥, 𝑦𝑦

2. Randomly choose small 𝑒𝑒 𝑥𝑥, 𝑦𝑦 ∈ 𝔽𝔽$ 𝑡𝑡, 𝑥𝑥, 𝑦𝑦

3. Compute 𝑐𝑐 ≔ 𝑋𝑋 I 𝑟𝑟 + 𝑙𝑙 I 𝑒𝑒 + 𝑚𝑚 mod (𝑞𝑞, 𝑡𝑡 ( − 1)
1. Compute 𝑐𝑐 𝑢𝑢! , 𝑢𝑢# = 𝑙𝑙 I 𝑒𝑒(𝑢𝑢! , 𝑢𝑢# ) + 𝑚𝑚

2. Compute 𝑚𝑚, = 𝑐𝑐 𝑢𝑢! , 𝑢𝑢# mod 𝑙𝑙

If each coefficient of 𝑐𝑐 𝑢𝑢! , 𝑢𝑢# is in 0, 𝑞𝑞 − 1 , then 𝑚𝑚 = 𝑚𝑚𝑚.
Thus, we need to take 𝑞𝑞 as follows:/01&,' 2

𝑞𝑞 > 𝑙𝑙 − 1 + 𝑙𝑙 K (𝑘𝑘 + 1)𝑛𝑛- 𝑙𝑙 − 1 -3'-.&

91

2.3 Attacks

13/19

1. Key Recovery Attack
Public key 𝑋𝑋(𝑡𝑡, 𝑥𝑥, 𝑦𝑦)

SVP problem

2. Linear Algebraic Attacka small section (𝑢𝑢! , 𝑢𝑢# )small
polynomial

Ciphertext 𝑐𝑐 ≡ 𝑋𝑋 I 𝑟𝑟 + (𝑙𝑙 I 𝑒𝑒 + 𝑚𝑚)

Recover message 𝑚𝑚

CVP problem

known

Giophantus is IND-CPA under the IE-LWE assumption.

Contents

14/19§1 Indeterminate equation cryptosystem§2 Giophantus§3 Homomorphic property§4 Conclusioin

3.1 Additive homomorphic

15/19

𝑐𝑐' ≔ 𝑋𝑋 I 𝑟𝑟' + 𝑙𝑙 I 𝑒𝑒' + 𝑚𝑚'

𝑐𝑐% ≔ 𝑋𝑋 I 𝑟𝑟% + 𝑙𝑙 I 𝑒𝑒% + 𝑚𝑚%

𝑐𝑐 ≔ 𝑐𝑐' + 𝑐𝑐% = 𝑋𝑋 I (𝑟𝑟' +𝑟𝑟% ) + 𝑙𝑙 I (𝑒𝑒' +𝑒𝑒% ) + 𝑚𝑚' + 𝑚𝑚%

Decryption: 1. Compute 𝑐𝑐 𝑢𝑢! , 𝑢𝑢# = 𝑙𝑙 I 𝑒𝑒' + 𝑒𝑒% 𝑢𝑢! , 𝑢𝑢# + 𝑚𝑚' + 𝑚𝑚%
2. Compute 𝑚𝑚, = 𝑐𝑐 𝑢𝑢! , 𝑢𝑢# mod 𝑙𝑙(i) Each coefficient of 𝑐𝑐 𝑢𝑢! , 𝑢𝑢# is in 0, 𝑞𝑞 − 1(ii) Each coefficient of 𝑚𝑚' + 𝑚𝑚% is in [0, 𝑙𝑙 − 1]

Then 𝑚𝑚! = 𝑚𝑚" + 𝑚𝑚#
92

3.1 Additive homomorphic

16/19

𝜆𝜆: max of coef of messages 𝑚𝑚' , 𝑚𝑚%

If the following holds, then 𝑚𝑚, = 𝑚𝑚' + 𝑚𝑚%(i) 𝑙𝑙 > 2𝜆𝜆/01 2(ii) 𝑞𝑞 > 2 I 𝑙𝑙 − 1 + 𝑙𝑙 ∑-.& 𝑘𝑘 + 1 𝑛𝑛- 𝑙𝑙 − 1 -3'
n 𝑁𝑁5 -times additive homomorphic case 𝑐𝑐 ≔ 𝑐𝑐' + 𝑐𝑐% + ⋯ + 𝑐𝑐4(
If the following holds, then decryption succeeds•

𝑙𝑙 > 𝑁𝑁5 𝜆𝜆/01• 𝑞𝑞 > 𝑁𝑁5 𝑙𝑙 − 1 + 𝑙𝑙 ∑-.&&,'

2

𝑘𝑘 + 1 𝑛𝑛- 𝑙𝑙 − 1 -3'

3.2 Multiplicative homomorphic 17/19
𝑐𝑐' ≔ 𝑋𝑋 I 𝑟𝑟' + 𝑙𝑙 I 𝑒𝑒' + 𝑚𝑚'

𝑐𝑐% ≔ 𝑋𝑋 I 𝑟𝑟% + 𝑙𝑙 I 𝑒𝑒% + 𝑚𝑚%

𝑐𝑐 ≔ 𝑐𝑐' I 𝑐𝑐%= 𝑋𝑋 I 𝑋𝑋𝑟𝑟' 𝑟𝑟% + ⋯+ 𝑙𝑙 % 𝑒𝑒' 𝑒𝑒% + 𝑙𝑙𝑒𝑒' 𝑚𝑚% + 𝑙𝑙𝑒𝑒% 𝑚𝑚' + 𝑚𝑚' I 𝑚𝑚%

Decryption: 1. Compute 𝑐𝑐 𝑢𝑢! , 𝑢𝑢#

2. Compute 𝑚𝑚, = 𝑐𝑐 𝑢𝑢! , 𝑢𝑢# mod 𝑙𝑙(i) Each coefficient of 𝑐𝑐 𝑢𝑢! , 𝑢𝑢# is in 0, 𝑞𝑞 − 1(ii) Each coefficient of 𝑚𝑚' 𝑚𝑚% is in [0, 𝑙𝑙 − 1]

Then 𝑚𝑚! = 𝑚𝑚" $ 𝑚𝑚#

Conclusion

18/19• We introduced an indeterminate equation scheme
called “Giophantus”.
• Giophantus is considered to be a scheme
for post-quantum cryptography.
• We explained some homomorphic property of Giophantus.

Future work
• Parameter selection• Bootstrapping• More efficient HE scheme based on IES

9319/19Thank you

94

IMI Workshop: Exploring Mathematical and Practical Principles
of Secure Computation and Secret Sharing
November 8–10, 2021, Kyushu University

Homomorphic Secret Sharing for Multipartite andGeneral Adversary Structures Supporting Parallel
Evaluation of Low-Degree Polynomials
Reo Eriguchi (Joint work with Koji Nuida)
The University of Tokyo
reo-eriguchi@g.ecc.u-tokyo.ac.jp
Homomorphic secret sharing (HSS) for a function f allows input parties to distributeshares for their private inputs and then locally compute output shares from which thevalue of f is recovered. HSS can be directly used to obtain a two-round multiparty
computation protocol for possibly non-threshold adversary structures whose communication complexity is linear in its share size and independent of the size of f .
Although several constructions of HSS schemes have been proposed, they do notgive a satisfactory solution to practical non-threshold adversary structures ∆. Whenmany parties are involved, ∆ is likely to be specified by a general adversary structure
rather than by a single threshold. The scheme [2] needs to set a corruption thresholdto the maximum size of X ∈ ∆ and then are inapplicable if ∆ contains at least one setof size exceeding their tolerable thresholds. The construction [3] is applicable to any
adversary structure but results in exponentially large share size for a specific class of
non-threshold adversary structures, e.g., multipartite ones. It is therefore important
to construct HSS schemes tailored to given non-threshold adversary structures in orderto tolerate corruptions in real-world situations.
In this talk, we introduce our constructions of HSS schemes tolerating multipartite and general adversary structures and supporting parallel evaluation of a single
low-degree polynomial [1]. Our multipartite scheme tolerates a wider class of adversary structures than the previous multipartite one in the particular case of a single
evaluation and has exponentially smaller share size than the general construction.
While restricting the range of tolerable adversary structures (but still applicable tonon-threshold ones), our schemes perform ℓ parallel evaluations with communication
complexity approximately ℓ/ log ℓ times smaller than simply using ℓ independent instances. We also formalize two classes of adversary structures taking into accountreal-world situations to which the previous threshold schemes are inapplicable. Our
schemes then perform O(m) parallel evaluations with almost the same communication
cost as a single evaluation, where m is the number of parties.
References[1] R. Eriguchi and K. Nuida. Homomorphic secret sharing for multipartite and general adversary
structures supporting parallel evaluation of low-degree polynomials. ASIACRYPT 2021, accepted.
[2] Y. Ishai, R.W.F. Lai, and G. Malavolta. A geometric approach to homomorphic secret sharing.
PKC 2021, pp. 92–119.
[3] K. Phalakarn, V. Suppakitpaisarn, N. Attrapadung, and K. Matsuura. Constructive t-securehomomorphic secret sharing for low degree polynomials. INDOCRYPT 2020, pp. 763–785.

95

Homomorphic Secret Sharing forMultipartite and General Adversary Structures
Supporting Parallel Evaluation of Low-Degree Polynomials
Exploring Mathematical and Practical Principles of
Secure Computation and Secret Sharing
November 10, 2021

Reo Eriguchi (The University of Tokyo, AIST)
Joint work with Koji Nuida
1

Input 𝒙𝒙

Multiparty Computation (MPC)
Company A

Customer information

Reconstruction
Output player

MPC protocol for 𝑓𝑓

Output 𝑓𝑓(𝒙𝒙)Statistical analysis

64Company B

Company C

20Adversary

1 2 3 4 5 6 7 8 9 10 11 12 13Time

Learns nothing beyond the output

2

Homomorphic Secret Sharing (HSS) [BGI16]• Share generation: 𝑠𝑠1 , … , 𝑠𝑠𝑚𝑚 ← Share(𝑥𝑥)– {𝑠𝑠𝑗𝑗 ∶ 𝑗𝑗 ∈ 𝐴𝐴} reveals no information on 𝑥𝑥 for a subset 𝐴𝐴 ⊆ [𝑚𝑚].

• Evaluation: 𝑦𝑦𝑗𝑗 ← Eval(𝑓𝑓, 𝑠𝑠𝑗𝑗,1 , … , 𝑠𝑠𝑗𝑗,𝑛𝑛 ), 𝑧𝑧 ← Dec(𝑦𝑦1 , … . , 𝑦𝑦𝑚𝑚 )– 𝑧𝑧 = 𝑓𝑓(𝑥𝑥1 , … , 𝑥𝑥𝑛𝑛 )Input player

Output player

𝑥𝑥1

⋯

𝑥𝑥𝑛𝑛

Server 1

𝑠𝑠1,1 ⋯

𝑠𝑠𝑛𝑛,1Server 𝑚𝑚

𝑠𝑠𝑚𝑚,1 ⋯⋮Dec(𝑦𝑦1 , … , 𝑦𝑦𝑚𝑚 ) = 𝑓𝑓(𝑥𝑥1 , … , 𝑥𝑥𝑛𝑛 )Eval

𝑠𝑠𝑛𝑛,𝑚𝑚 Eval

96

𝑦𝑦1
𝑦𝑦𝑚𝑚

3

Application to MPC• MPC based on HSS– Two rounds– Succinctness: communication cost ≈ share size (independent of the size of 𝑓𝑓)– Corruption power is characterized by its adversary structure
Possibly non-threshold

𝑚𝑚 Players

𝑥𝑥2

𝑥𝑥1

Sharing inputs

Output player
𝑓𝑓(𝑥𝑥1 , … , 𝑥𝑥𝑚𝑚 )𝑥𝑥𝑚𝑚 Evaluation (local)

Collect shares

Corruption

4

Adversary Structure
The collection Δ of subsets of players revealing no information on a secret input• Threshold

Δ = {𝑋𝑋 ∶ 𝑋𝑋 ≤ 𝑡𝑡}• MultipartiteΠ = (𝑃𝑃1 , … , 𝑃𝑃𝐿𝐿 ) ∶ partition of [𝑚𝑚]Whether 𝑋𝑋 ∈ Δ or not is uniquely determined by 𝑋𝑋 ∩ 𝑃𝑃1 , … , 𝑋𝑋 ∩ 𝑃𝑃𝐿𝐿

• General
No assumption on Δ

Π = ( 𝑚𝑚 ) ⇒ ThresholdΠ = 1 , … , 𝑚𝑚 ⇒ General

Example: Δ induced by a graphAdversary colludes with adjacent players

5Previous HSS• HSS for degree-𝑑𝑑 polynomials
ThresholdGeneralMultipartite∀𝐴𝐴1 , … , 𝐴𝐴𝑑𝑑 ∈ Δ
𝐴𝐴1 ∪ ⋯ ∪ 𝐴𝐴𝑑𝑑 ≠ [𝑚𝑚]

[BGW88]Type 𝑄𝑄𝑑𝑑[EK20][BIW10]𝑚𝑚✗ Strong limit on corruption power (Threshold: 𝑡𝑡 < )𝑑𝑑◎ Unconditional security

97

6

Previous HSS• HSS for degree-𝑑𝑑 polynomials

General ◎ Full threshold (𝑡𝑡 = 𝑚𝑚 − 1)

Multipartite

Threshold✗ Strong assumption

Lattice-based[Gentry09], [DHRW16][BGW88]Type 𝑄𝑄𝑑𝑑[BIW10][EK20]𝑚𝑚✗ Strong limit on corruption power (Threshold: 𝑡𝑡 < )𝑑𝑑◎ Unconditional security

7

Previous HSS• HSS for degree-𝑑𝑑 polynomials

General ◎ Full threshold (𝑡𝑡 = 𝑚𝑚 − 1)

Multipartite

Threshold[ILM21]𝑂𝑂(1)Lattice-based✗ Strong assumption[Gentry09], [DHRW16]

Type 𝑄𝑄𝑑𝑑𝑘𝑘[BGW88][PSAM20]
𝑂𝑂(2𝑚𝑚 )Type 𝑄𝑄𝑑𝑑[BIW10][EK20]○ Weak limit on corruption power𝑚𝑚(Threshold: 𝑡𝑡 < (𝑘𝑘 + 1) ⋅ )𝑑𝑑○ Assuming 𝑘𝑘-HE(HE for degree-𝑘𝑘 poly.)𝑚𝑚✗ Strong limit on corruption power (Threshold: 𝑡𝑡 < )𝑑𝑑◎ Unconditional security

8

Our Results✓ Multipartite HSS for degree-𝑑𝑑 polynomials from 𝑘𝑘-HE✓ Extension to ℓ parallel evaluations of a single polynomial (SIMD operation)
Threshold[ILM21]𝑂𝑂(1)Multipartite

Type 𝑄𝑄𝑑𝑑𝑘𝑘
Type 𝑄𝑄𝑑𝑑𝑘𝑘,ℓ𝑂𝑂(log 𝑚𝑚 + ℓ )[This work]
𝑚𝑚𝑂𝑂(1)𝑚𝑚𝑂𝑂(1) log 𝑚𝑚 + ℓ
Type 𝑄𝑄𝑑𝑑

General[PSAM20]
𝑂𝑂(2𝑚𝑚 )𝑂𝑂(2𝑚𝑚 log 𝑚𝑚 + ℓ )998General HSS for Parallel Evaluation

10

Parallel Evaluation of Degree-𝑑𝑑 Poly.

[ILM21]𝑂𝑂(1)GeneralMultipartite

ThresholdType 𝑄𝑄𝑑𝑑𝑘𝑘
Type 𝑄𝑄𝑑𝑑𝑘𝑘,ℓ𝑂𝑂(log 𝑚𝑚 + ℓ )[PSAM20]
𝑂𝑂(2𝑚𝑚 )[This work]
𝑚𝑚𝑂𝑂(1)

Packed secret sharing[FY92]

𝑂𝑂(2𝑚𝑚 log 𝑚𝑚 + ℓ )𝑚𝑚𝑂𝑂(1) log 𝑚𝑚 + ℓ

11

Our Proposed HSS
HSS [PSAM20]

Packed secret sharing [FY92]✓General adversary structure✗ Threshold adversary structure✗ NOT support parallel evaluation✓ Support parallel evaluation

Our HSS✓General adversary structure✓Support parallel evaluation

99

12

Starting Point: HSS of [PSAM20]• General adversary structure Δ ⊆ 2[𝑚𝑚]– Monotonically decreasing (𝐴𝐴 ⊆ 𝐵𝐵 ⊆ 𝑚𝑚 and 𝐵𝐵 ∈ Δ ⇒ 𝐴𝐴 ∈ Δ)
– All maximal subsets Δ+ = 𝐴𝐴1 , … , 𝐴𝐴𝑁𝑁 = {𝐴𝐴 ∶ 𝐴𝐴 ∈ Δ and 𝐵𝐵 ∉ Δ for all 𝐵𝐵 ⊋ 𝐴𝐴}• HSS scheme of [PSAM20]– Assuming 𝑘𝑘-HE, 𝑥𝑥 ↦ 𝑥𝑥
– Share generation:

1. Randomly split 𝑠𝑠 into 𝑠𝑠1 , … , 𝑠𝑠𝑁𝑁

Randomly split 𝑠𝑠

Secret input
𝑠𝑠 ∈ 𝔽𝔽

2. Give 𝑠𝑠𝑖𝑖 to 𝑗𝑗 ∈ 𝐴𝐴𝑖𝑖 and give 𝑠𝑠𝑖𝑖 to 𝑗𝑗 ∈ 𝐴𝐴𝑖𝑖

• Privacy– Coalition of 𝐴𝐴𝑖𝑖 ∈ Δ+ misses 𝑠𝑠𝑖𝑖 (only obtains 𝑠𝑠𝑖𝑖 )𝑠𝑠 = 𝑠𝑠1 + ⋯ + 𝑠𝑠𝑁𝑁

𝐴𝐴1

𝐴𝐴1

𝑠𝑠1
⋮
𝑠𝑠1
𝑠𝑠1
⋮
𝑠𝑠1

⋯
⋯

Replicate 𝑠𝑠𝑖𝑖

𝑠𝑠𝑁𝑁
⋮
𝑠𝑠𝑁𝑁
𝑠𝑠𝑁𝑁
⋮
𝑠𝑠𝑁𝑁

𝐴𝐴𝑁𝑁

𝐴𝐴𝑁𝑁
13

Packed Secret Sharing [FY92]• Threshold adversary structure {𝑋𝑋 ∶ 𝑋𝑋 ≤ 𝑡𝑡}• Secret input: (𝑠𝑠1 , … , 𝑠𝑠ℓ ) ∈ 𝔽𝔽ℓ• Share generation:
1. Choose a random polynomial 𝜑𝜑 ∈ 𝔽𝔽[𝑋𝑋] such that
𝑠𝑠1 = 𝜑𝜑 𝛼𝛼1 , … , 𝑠𝑠ℓ = 𝜑𝜑 𝛼𝛼ℓ ,deg 𝜑𝜑 ≤ 𝑡𝑡 + ℓ − 1.
2. Give 𝜑𝜑 𝑗𝑗 to Server 𝑗𝑗• Privacy
𝜑𝜑 𝑗𝑗1 , … , 𝜑𝜑(𝑗𝑗𝑡𝑡 ) reveals no information on (𝑠𝑠1 , … , 𝑠𝑠ℓ )• Reconstruction
𝜑𝜑 can be recovered from shares of 𝐴𝐴 ⊆ [𝑚𝑚] if 𝐴𝐴 ≥ 𝑡𝑡 + ℓ

14

Our Proposed HSS
HSS [PSAM20]

Packed secret sharing [FY92]✓General adversary structure✗ Threshold adversary structure✗ NOT support parallel evaluation✓ Support parallel evaluation

Our HSS✓General adversary structure✓Support parallel evaluation

100

15

Our Proposed HSS• General adversary structure Δ ⊆ 2[𝑚𝑚]– All maximal subsets Δ+ = 𝐴𝐴1 , … , 𝐴𝐴𝑁𝑁 = {𝐴𝐴 ∶ 𝐴𝐴 ∈ Δ and 𝐵𝐵 ∉ Δ for all 𝐵𝐵 ⊋ 𝐴𝐴}
Randomly split 𝒔𝒔

Secret input
𝒔𝒔 ∈ 𝔽𝔽ℓ• Our HSS scheme– Assuming 𝑘𝑘-HE, 𝑥𝑥 ↦ 𝑥𝑥
– Share generation:

𝒔𝒔 = 𝒔𝒔1 + ⋯ + 𝒔𝒔𝑁𝑁

1. Randomly split 𝒔𝒔 into 𝒔𝒔1 , … , 𝒔𝒔𝑁𝑁
𝐴𝐴1
2. Share 𝒔𝒔𝑢𝑢 via packed secret sharing:
Give 𝜑𝜑𝑢𝑢 (𝑗𝑗) to 𝑗𝑗 ∈ 𝐴𝐴𝑢𝑢 and give 𝜑𝜑𝑢𝑢 (𝑗𝑗) to 𝑗𝑗 ∈ 𝐴𝐴𝑢𝑢
where deg 𝜑𝜑𝑢𝑢 ≤ ℓ − 1
𝐴𝐴1

Share 𝒔𝒔𝑢𝑢

𝜑𝜑1 (𝑗𝑗)⋮⋯

𝜑𝜑1 (𝑗𝑗)• Privacy– Coalition of 𝐴𝐴𝑢𝑢 ∈ Δ+ misses 𝒔𝒔𝑢𝑢

𝜑𝜑𝑁𝑁 (𝑗𝑗)𝐴𝐴𝑁𝑁⋮

𝜑𝜑𝑁𝑁 (𝑗𝑗)

𝐴𝐴𝑁𝑁
16

Parallel Evaluation• Evaluation of a single degree-𝑑𝑑 polynomial– Secret input: 𝒙𝒙(1) , … , 𝒙𝒙 𝑑𝑑 ∈ 𝔽𝔽ℓ𝑖𝑖𝑖𝑖– 𝒙𝒙(𝑖𝑖) is randomly split into 𝒙𝒙(𝑖𝑖) = 𝒚𝒚1 + ⋯ + 𝒚𝒚𝑁𝑁
𝑖𝑖

𝑖𝑖

𝑖𝑖

𝑖𝑖

– 𝒚𝒚𝑢𝑢 = 𝜑𝜑𝑢𝑢 𝛼𝛼1 , … , 𝜑𝜑𝑢𝑢 𝛼𝛼ℓ , deg 𝜑𝜑𝑢𝑢 ≤ ℓ − 1𝒙𝒙(1) ∗ ⋯ ∗ 𝒙𝒙(𝑑𝑑) =෍

𝒋𝒋= 𝑗𝑗1 ,…,𝑗𝑗𝑑𝑑 ∈ 𝑁𝑁 𝑑𝑑

1

𝑑𝑑

𝒚𝒚𝑗𝑗1 ∗ ⋯ ∗ 𝒚𝒚𝑗𝑗𝑑𝑑

(𝑑𝑑)

1

More than 𝑑𝑑(ℓ − 1) points of 𝜑𝜑𝑗𝑗1 ⋯ 𝜑𝜑𝑗𝑗𝑑𝑑 must be collected from servers∗ denotes the element-wise product17

Parallel Evaluation• Evaluation of a single degree-𝑑𝑑 polynomial– Server 𝑖𝑖 has

(1)

(𝑑𝑑)

𝜑𝜑𝑢𝑢 (𝑖𝑖), … , 𝜑𝜑𝑢𝑢 (𝑖𝑖)
(1)

(𝑑𝑑)

1

𝑑𝑑

ℎ

(𝜑𝜑𝑗𝑗1 ⋯ 𝜑𝜑𝑗𝑗𝑑𝑑 )(𝑖𝑖) = ෑ 𝜑𝜑𝑗𝑗ℎ 𝑖𝑖ℎ∶𝑖𝑖∉𝐴𝐴𝑗𝑗ℎ(ℎ)

ෑ 𝜑𝜑𝑗𝑗ℎ (𝑖𝑖)ℎ∶𝑖𝑖∈𝐴𝐴𝑗𝑗ℎ11

𝒚𝒚𝑢𝑢 = 𝜑𝜑𝑢𝑢

𝛼𝛼1 , … , 𝜑𝜑𝑢𝑢

𝐴𝐴𝑢𝑢

𝜑𝜑𝑢𝑢 (𝑖𝑖)𝐴𝐴𝑢𝑢

if 𝑖𝑖 ∈ 𝐴𝐴𝑢𝑢

𝜑𝜑𝑢𝑢 (𝑖𝑖) , … , 𝜑𝜑𝑢𝑢 (𝑖𝑖)

– Server 𝑖𝑖 can compute1

if 𝑖𝑖 ∉ 𝐴𝐴𝑢𝑢

(1)

𝜑𝜑𝑢𝑢 (𝑖𝑖)⋮(1)

Product of 𝑘𝑘 ciphertexts∀ 𝑗𝑗1 , … , 𝑗𝑗𝑑𝑑 ∈ 𝑁𝑁 𝑑𝑑 , # 𝑖𝑖 ∈ 𝑚𝑚 ∶ # ℎ ∶ 𝑖𝑖 ∈ 𝐴𝐴𝑗𝑗ℎ ≤ 𝑘𝑘 > 𝑑𝑑(ℓ − 1)

101

𝛼𝛼ℓ

18

Remaining Problem• Context hiding– Output shares should reveal nothing beyond 𝑓𝑓(𝑥𝑥1 , … , 𝑥𝑥𝑛𝑛 )– Needs re-randomization with fresh shares of 0
Type 𝑄𝑄𝑑𝑑𝑘𝑘,ℓ∀ 𝑗𝑗1 , … , 𝑗𝑗𝑑𝑑 ∈ 𝑁𝑁 𝑑𝑑 , ෍ 𝑘𝑘 − # ℎ ∶ 𝑖𝑖 ∈ 𝐴𝐴𝑗𝑗ℎ𝑖𝑖∈ 𝑚𝑚+> (𝑑𝑑 + 1)(ℓ − 1)

𝑥𝑥 + ∶= max{𝑥𝑥, 0}

Type 𝑄𝑄𝑑𝑑𝑘𝑘,ℓ ⇒ Type 𝑄𝑄𝑑𝑑𝑘𝑘,1 ⇔ Type 𝑄𝑄𝑑𝑑𝑘𝑘

19

Efficiency• Share size
– Server 𝑖𝑖 receives 𝑂𝑂 𝑁𝑁 field elements and 𝑂𝑂(𝑁𝑁) ciphertexts– 𝑚𝑚 + ℓ different points are necessary
𝑂𝑂 2𝑚𝑚 log 𝑚𝑚 + ℓ

All maximal subsets Δ+ = 𝐴𝐴1 , … , 𝐴𝐴𝑁𝑁

20

Conclusion✓ Multipartite HSS for degree-𝑑𝑑 polynomials from HE✓ Extension to ℓ parallel evaluations of a single polynomial (SIMD operation)
Threshold[ILM21]𝑂𝑂(1)Multipartite

Type 𝑄𝑄𝑑𝑑𝑘𝑘
Type 𝑄𝑄𝑑𝑑𝑘𝑘,ℓ𝑂𝑂(log 𝑚𝑚 + ℓ )[This work]
𝑚𝑚𝑂𝑂(1)𝑚𝑚𝑂𝑂(1) log 𝑚𝑚 + ℓ

General[PSAM20]
𝑂𝑂(2𝑚𝑚 )𝑂𝑂(2𝑚𝑚 log 𝑚𝑚 + ℓ )21102

References[BGI16]: E. Boyle, N. Gilboa, and Y. Ishai. Breaking the circuit size barrier for secure computation under DDH.
CRYPTO.
[BGW88]: M. Ben-Or, S. Goldwasser, and A. Wigderson. Completeness theorems for non-cyptographic faulttolerant distributed computation. STOC.
[EK20]: R. Eriguchi and N. Kunihiro. d-Multiplicative secret sharing for multipartite adversary structures. ITC.

[BIW10]: O. Barkol, Y. Ishai, and E. Weinreb. On d-multiplicative secret sharing. Journal of Cryptology.
[Gentry09]: C. Gentry. Fully homomorphic encryption using ideal lattices. STOC.

[DHRW16]: Y. Dodis, S. Halevi, R.D. Rothblum, D. Wichs. Spooky encryption and its applications. CRYPTO.
22

References[ILM21]: Y. Ishai, R.W.F. Lai, and G. Malavolta. A geometric approach to homomorphic secret sharing. PKC.
[PSAM20]: K. Phalakarn, V. Suppakitpaisarn, N. Attrapadung, and K. Matuura. Constructive t-securehomomorphic secret sharing for low degree polynomials. INDOCRYPT.
[FY92]: M. Franklin and M. Yung. Communication complexity of secure computation. STOC.

23

Thank you!

24

103

IMI Workshop: Exploring Mathematical and Practical Principles
of Secure Computation and Secret Sharing
November 8–10, 2021, Kyushu University

A Comparison of
How to Garble Arithmetic and Boolean Circuits- Case of Functional Encryption Hiroaki Anada (Joint work with Kotaro Chinen)
University of Nagasaki
anada@sun.ac.jp
The technique of garbling circuits that was initiated by Yao [1] is currently oneof the fundamental cryptographic primitives. It is generalized and enhanced as therandomized encoding of functions [2, 3], which can treat not only boolean circuits but
also arithmetic circuits. In this talk, after warming up with examples of randomized
encoding, we focus into garbling encryption circuits of functional encryption following
the work of Goyal, Koppla and Waters [4]. We see that there is a gap between “boolean”
and “arithmetic” in security proofs; in the case of boolean, we only have to select oneof two evaluated keys, but in the case of arithmetic, we must evaluate a key-value forany given input.
References[1] Andrew Chi-Chih Yao. How to generate and exchange secrets (extended abstract). In 27th Annual
Symposium on Foundations of Computer Science, Toronto, Canada, 27-29 October 1986, pages
162–167. IEEE Computer Society, 1986.
[2] Benny Applebaum, Yuval Ishai, and Eyal Kushilevitz. How to garble arithmetic circuits. In Rafail
Ostrovsky, editor, IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS
2011, Palm Springs, CA, USA, October 22-25, 2011, pages 120–129. IEEE Computer Society,2011.
[3] Benny Applebaum. Garbled circuits as randomized encodings of functions: a primer. In Yehuda
Lindell, editor, Tutorials on the Foundations of Cryptography, pages 1–44. Springer International
Publishing, 2017.
[4] Rishab Goyal, Venkata Koppula, and Brent Waters. Semi-adaptive security and bundling functionalities made generic and easy. In Martin Hirt and Adam D. Smith, editors, Theory of Cryptography- 14th International Conference, TCC 2016-B, Beijing, China, October 31 - November 3, 2016,
Proceedings, Part II, volume 9986 of Lecture Notes in Computer Science, pages 361–388, 2016.

105

IMI Workshop of the Joint Research Projects
November 8 to 10, 2021

“Exploring Mathematical and Practical Principles
of Secure Computation and Secret Sharing”

A Comparison of How to Garble
Boolean & Arithmetic Circuits- Case of Functional Encryption Hiroaki ANADA(Joint work with Kotaro CHINEN: 2nd grade of master course)
University of Nagasaki

Part I: Intuitive Introduction to

Randomized Encodings (RE)2

Garbling techniques[1] Yao: “How to generate and exchange secrets”, SFCS 1986
[2] Applebaum, Ishai, Kushilevitz: "How to Garble Arithmetic
Circuits", FOCS 2011
 GC-based secure computation ☺
 This talk: Garbling functional encryption circuit (?)3106

Gates: Boolean / Arithmetic• Boolean gates• Arithmetic gates1 ∈ 0,1




+

×

ADD

MULTIPLY ∈  or finite ring Formulars & Circuits• Formula• Circuit

*



∘



1



•  ∘   ∗  ∘   → 


∘












•  ∘   ∗  ∘   → 
•  ∘   ∗  ∘   → 

4



+



∘



∘



∘



∘

×

MULTIPLY

ADD

*



*



5

Yao’s garbling [1]∈: 0,1  → 0,1 ↦

1. (Correctness)
2. (Privacy) ,   …  ,  , … ,  ,  , Deco, Simu

Deco  ,   , … ,   →  Simu  →    ,   , … ,  [1] Yao: “How to generate and exchange secrets”, SFCS 1986

107

6

Garbling as randomized encoding (RE)of functions [2]∈:  →  ⋅ ↦  ,  ⋅ ; , Deco, Simu

1. (Correctness)
Deco   ,  ; 
2. (Privacy)

Simu  → →     ,  ; 

[3] Applebaum: “Garbled Circuits as Randomized Encodings of Functions: a Primer” in Tutorials on theFoundations of Cryptography, pp.1-44, 2017

7

DARE (: Decomposable Affine RE) [3]
1. Decomposable:• Each output-entry ( ) contains at most one input-entry ( )•      

2. Affine:• Each output-entry ( ) is affine function of input-entries ( , … ,  )•       [2] Applebaum, Ishai, Kushilevitz: "How to Garble Arithmetic Circuits", FOCS 2011

Example 1 ⋅ ↦  ,  ⋅ ;      ,  ≔     •   ≔ ∅• 
,  ;  ≔ • Deco ∅,  , 
• Deco ∅,  ,≔      ,   • Simu ; ̃ ≔ ∅,   ̃ , ̃, Deco   ,  ;   

+

ADD



8

, Simu

→                • Simu  →   ∅,   ,   [2] Applebaum, Ishai, Kushilevitz: "How to Garble Arithmetic Circuits", FOCS 2011, pp.120-129[3] Applebaum: “Garbled Circuits as Randomized Encodings of Functions: a Primer” in Tutorials on theFoundations of Cryptography, pp.1-44, 2017

9108

Example 2  ,  ⋅ ;  ⋅ ↦     ,  ≔   : •   ≔ ∅,    ,  
• 
 ,  ;  ,  ≔ • Deco ∅,  ,  , 

, Deco   ,  ;    ,×

MULTIPLY   ,≔    

• Deco ∅,    ,    ,        • Simu ; ̃ , ̃ ≔ ∅, ̃ , ̃ , ̃ ̃    

, Simu    

→                      

: • Simu  →   ∅,    ,    ,        

10

Example 2’  ,  ⋅ ;  ⋅ ↦     ,  ≔   : •   ≔ ∅,    ,  ,  
• 
 ,  ;  ,  ,  ≔• Deco ∅, ,    ,    

• Simu ; ̃ , ̃ , ̃ ≔ ∅,• Simu  →   ∅,Example 3

MULTIPLY   ,     , 
,



,

• Deco ∅,,• Deco ∅,



: 

11

  ,  ⋅ ; ;  ,  ,  ,  ≔ ,,      

, Deco   ,  ; 

• Simu  →   ∅,

×



,





  

≔      

,

 

, Simu+  →         

̃
̃
,
, ̃̃ ̃    ̃ ̃  ̃        ,          ,   

109



               ,          ,   

• Simu ; ̃ , ̃ , ̃ , ̃ ≔ ∅,                 ,  ,  ≔     : •   

→                   

̃
̃
, 
̃ ̃    ̃ ̃•    ∅,    ,  ,  ,  

, Simu             ,       

 ⋅ ↦

×



≔              ,       

• Deco ∅,, Deco   ,  ; 



: 

12

Example 4  ,  ⋅ ;  ⋅ ↦, Deco   ,  ; 

     ,  ,  ,  ≔     •      ,  ,  ,  ,  ,  ,  ,  , 
• 

,

≔

,



,

    ,         ,    

, ,  ,

 







  

+×              ,,,   ≔               • Simu ;  , ̃ , ̃ , ̃ , ̃ , ̃ , ̃ , ̃ , ̃
̃
̃
̃
≔ ̃  ̃ , ̃  ̃ ,,,,̃ ̃    ̃̃  ̃̃ ̃    ̃
• Deco, Simu

×  
≔   ;  ,  ,  ,  ,  ,  ,  ,  , 




 



 

̃
̃  ̃

: 
13

DARE (: Decomposable Affine RE) [3]
1. Decomposable:• Each output-entry ( ) contains at most one input-entry ( )•      

2. Affine:• Each output-entry ( ) is affine function of input-entries ( , … ,  )•       

3. Decomposable & Affine•      

[2] Applebaum, Ishai, Kushilevitz: "How to Garble Arithmetic Circuits", FOCS 2011

DARE:



+

Problem at Affinization  
•      ,  ,  ,  ,  ,  ,  ,  ,  ≔   
≔



,

,

    

,

,







;  ,  ,  ,  ,  ,  ,  ,  , 
         

,





    

• Exponential blowup (of key size)in “Depth of ”.. ,  

×  ×     ,  ,  ,  ≔     • 

14

 

 

         

Key size (Online part)

Depth

15

110

DARE:

M-size (offline part)+  

×•     

×

Key-Affinization then Key-Shrinkage [2, 3]



 

 

•   …  ;    , … ,   
K-size (online part)
KA.

Depth

Depth

KS.

[2] Applebaum, Ishai, Kushilevitz: "How to Garble Arithmetic Circuits", FOCS 2011, pp.120-129[3] Applebaum: “Garbled Circuits as Randomized Encodings of Functions: a Primer” in Tutorials on theFoundations of Cryptography, pp.1-44, 201716

Part II: Our Observation on

Garbling “Functional Encryption” Circuits- Boolean vs. Arithmetic -17

Motivation (1/4)

Functional encryption (FE)• Setup 1 , 1 → mpk, msk
• KG mpk, msk,  → sk
• Encr mpk, ;  → ct
• Decr mpk, sk , ct → • Identity-based Encr
• Attribute-based Encr
• Inner-product Encr
...

18

111

Motivation (2/4)

Security levels of FE
Table1: Available data before target-fixing
DataPK
Oracle(1)Selective-(2)Semi-adaptive✓-(3)Adaptive✓✓

Target ,  ,  ∗ PK ,  ,  ∗ 

KGO ,  ,  ∗ (1) < (2) < (3):

Advantageous for Adversary  But, when achieved, (3) or (2) is ideal ☺
19

Motivation (3/4)(1)Selective-to-(2)Semi-adaptive Conversion[4]• Circuit  ≔ Encr ⋅ , ; ∈

: 0,1  → 0,1 • Yao’s garbling:↦

mpk   …  ,  ,  , … ,  ,   , Deco, Simu

[4] Goyal, Koppla, Waters: “Semi-Adaptive Security and Bundling Functionalities Made Generic and Easy”, TCC 2016•

Motivation (4/4)(1)Sel-to-(2)Sma. Conv.

FE  Setup , KG , Encr , Decr• Setup 1 , 1Setup 1 , 1 → mpk  , msk 
KG 1 →pk , sk , pk , sk , … , pk  , sk  , pk  , sk 
mpk  ≔ pk  
msk  ≔ sk   , mpk  , msk 
Return mpk  , msk  • KG mpk  , msk  , 

KG mpk  , msk  → sk ,sk , ≔ sk  , mpk  , sk ,
Return sk , 

20

mpk    … ↦ ,  ,  , … ,  ,   , Deco, Simu

• Use PKE  KG , Enc , Dec • Encr mpk  ,  ∈ 0,1 , ≔ Encr ⋅ , ; ↦  ,  ,  , … ,  ,   , Deco, Simu

Enc pk  ,  → ct  
Return ct    , ct  • Decr mpk  , sk , , ct    , Deco  ,   , … ,   → ct 

Decr mpk  , sk , , ct  → 
Return 

21

112

Our observation

A comparison of garbling Boolean & Arithmetic circuits
Boolean• Only has to select one of two evaluated keys
 ,    ,  , … ,  ,  • “Selection function” selects one of the two for each place
mpk    …  , ,   , … ,  

Arithmetic• Must evaluate a key-value for any given input in  ⊂  ⋅ ;     ,  ⋅ ;   ,  ⋅ ;  
22What’s problem??

Game with garbling challenger for FE security

Boolean1 , 1 

Garbling chall.



KG 1 → pk  , sk  
Setup 1 , 1 → mpk  , msk  

mpk ≔ pk   ∗ , ∗  ∈ 0,1
mpk      …  ,ct  ← Encmpk  , ∗ ; , Simu ct  → If   1 ∗ ,  ∗ ≔  ,   , … ,  
, 

else
∗ ,  ∗ ≔  ∈ 0,1
mpk  , ∗ ,  ≔ Encr ⋅ , ;   ≔ 0 Comp. sec.
under assump.

☺

∗ ,  ∗

Enc pk  ,  → ct  
ct    , ct  If     ≔ 1else ≔ 0

If    return " Win"else return " Lose"

Arithmetise?

?
23

Problem to be solved..
• Establish a “arithmetic GKW” compiler..

• Hopefully by using “arithmetic garbling” [3][4]• For what?

• More efficiecy☺

[2] Applebaum, Ishai, Kushilevitz: "How to Garble Arithmetic Circuits", FOCS 2011, pp.120-129[3] Applebaum: “Garbled Circuits as Randomized Encodings of Functions: a Primer” in Tutorials on theFoundations of Cryptography, pp.1-44, 2017

24

113

Summary• There is a gap between

Boolean& Arithmetic

Boolean• Only has to select one of two evaluated keys
 ,    ,  , … ,  ,  • “Selection function” selects one of the two for each place
mpk    …  , ,   , … ,  

Arithmetic• Must evaluate a key-value for any given input in  ⊂  ⋅ ;     ,  ⋅ ;   ,  ⋅ ;  

25Thank you for your attention!☺

26

114

MI レクチャーノートシリーズ刊行にあたり
本レクチャーノートシリーズは、文部科学省 21 世紀 COE プログラム「機能数理学の構築と展開」（H.15-19 年度）において作成した COE Lecture Notesの続刊であり、文部科学省大学院教育改革支援プログラム「産業界が求める数学博士と新修士養成」（H19-21 年度）および、同グローバル COE プログラ
ム「マス・フォア・インダストリ教育研究拠点」（H.20-24 年度）において行われた講義の講義録として出版されてきた。平成 23 年 4 月のマス・フォア・
インダストリ研究所（IMI）設立と平成 25 年 4 月の IMI の文部科学省共同利用・共同研究拠点として「産業数学の先進的・基礎的共同研究拠点」の認定を受け、今後、レクチャーノートは、マス・フォア・インダストリに関わる国内外の研究者による講義の講義録、会議録等として出版し、マス・フォア・インダ
ストリの本格的な展開に資するものとする。
平成 30 年 10 月
マス・フォア・インダストリ研究所所長

佐伯修

2021年度 九州大学マス・フォア・インダストリ研究所 共同利用研究集会

秘密計算・秘密分散の数理と実用の探求
発
編
発

行
集
行

2022年２月９日
穴田啓晃，池松泰彦，縫田光司，大畑幸矢，Yuntao Wang
九州大学マス・フォア・インダストリ研究所
九州大学大学院数理学府〒819-0395 福岡市西区元岡744
九州大学数理・IMI 事務室
TEL 092-802-4402 FAX 092-802-4405
URL https://www.imi.kyushu-u.ac.jp/

印

刷

城島印刷株式会社〒810-0012 福岡市中央区白金 2 丁目 9 番 6 号
TEL 092-531-7102 FAX 092-524-4411

シリーズ既刊
Issue

Author／Editor

Title

Published

COE Lecture Note

Mitsuhiro T. NAKAO
Kazuhiro YOKOYAMA

Computer Assisted Proofs - Numeric and Symbolic Approaches 199pages

August 22, 2006

COE Lecture Note

M.J.Shai HARAN

Arithmetical Investigations - Representation theory, Orthogonal
polynomials and Quantum interpolations- 174pages

August 22, 2006

COE Lecture Note Vol.3

Michal BENES
Masato KIMURA
Tatsuyuki NAKAKI

Proceedings of Czech-Japanese Seminar in Applied Mathematics 2005
155pages

COE Lecture Note Vol.4

宮田

辺要素有限要素法による磁界解析 - 機能数理学特別講義 21pages May 15, 2007

COE Lecture Note Vol.5

Francois APERY

Univariate Elimination Subresultants - Bezout formula, Laurent series
and vanishing conditions - 89pages

September 25, 2007

COE Lecture Note Vol.6

Michal BENES
Masato KIMURA
Tatsuyuki NAKAKI

Proceedings of Czech-Japanese Seminar in Applied Mathematics 2006
209pages

October 12, 2007

COE Lecture Note Vol.7

若山 正人
中尾 充宏

九州大学産業技術数理研究センター キックオフミーティング
138pages

October 15, 2007

COE Lecture Note Vol.8

Alberto PARMEGGIANIIntroduction to the Spectral Theory of Non-Commutative Harmonic
Oscillators 233pages

January 31, 2008

COE Lecture Note Vol.9

Michael I.TRIBELSKY

Introduction to Mathematical modeling 23pages

February 15, 2008

COE Lecture Note Vol.10

Jacques FARAUT

Infinite Dimensional Spherical Analysis 74pages

March 14, 2008

COE Lecture Note Vol.11

Gerrit van DIJK

Gelfand Pairs And Beyond 60pages

August 25, 2008

COE Lecture Note Vol.12

Faculty of Mathematics,
Kyushu University

Consortium “MATH for INDUSTRY” First Forum 87pages

September 16, 2008

COE Lecture Note Vol.13

九州大学大学院
数理学研究院

プロシーディング「損保数理に現れる確率モデル」― 日新火災・九州大学 共同研究2008年11月 研究会 ― 82pages

February 6, 2009

健治

October 13, 2006

シリーズ既刊
Issue

Author／Editor

Title

Published

COE Lecture Note Vol.14

Michal Beneš,
Tohru Tsujikawa
Shigetoshi Yazaki

Proceedings of Czech-Japanese Seminar in Applied Mathematics 2008
77pages

February 12, 2009

COE Lecture Note Vol.15

Faculty of Mathematics,
Kyushu University

International Workshop on Verified Computations and Related Topics
129pages

February 23, 2009

COE Lecture Note Vol.16

Alexander Samokhin

Volume Integral Equation Method in Problems of Mathematical Physics February 24, 2009
50pages

COE Lecture Note Vol.17

矢嶋
及川
梶原
辻
福本

非線形波動の数理と物理 66pages

February 27, 2009

COE Lecture Note Vol.18

Tim Hoffmann

Discrete Differential Geometry of Curves and Surfaces 75pages

April 21, 2009

COE Lecture Note Vol.19

Ichiro Suzuki

The Pattern Formation Problem for Autonomous Mobile Robots―Special Lecture in Functional Mathematics― 23pages

April 30, 2009

COE Lecture Note Vol.20

Yasuhide Fukumoto
Yasunori Maekawa

Math-for-Industry Tutorial: Spectral theories of non-Hermitian
operators and their application 184pages

June 19, 2009

COE Lecture Note Vol.21

Faculty of Mathematics,
Kyushu University

Forum “Math-for-Industry”
Casimir Force, Casimir Operators and the Riemann Hypothesis
95pagesNovember 9, 2009

COE Lecture Note Vol.22

Masakazu Suzuki
Hoon Hong
Hirokazu Anai
Chee Yap
Yousuke Sato
Hiroshi Yoshida

The Joint Conference of ASCM 2009 and MACIS 2009:
Asian Symposium on Computer Mathematics Mathematical Aspects ofComputer and Information Sciences 436pages

December 14, 2009

COE Lecture Note Vol.23

荒川 恒男
金子 昌信

多重ゼータ値入門

February 15, 2010

COE Lecture Note Vol.24

Fulton B.Gonzalez

Notes on Integral Geometry and Harmonic Analysis

COE Lecture Note Vol.25

Wayne Rossman

Discrete Constant Mean Curvature Surfaces via Conserved Quantities
130pages

May 31, 2010

COE Lecture Note Vol.26

Mihai Ciucu

Perfect Matchings and Applications

July 2, 2010

徹
正行
健司
英一
康秀

111pages

66pages

125pages

March 12, 2010

シリーズ既刊
Issue

Author／Editor

Title

Published

COE Lecture Note Vol.27

九州大学大学院
数理学研究院

Forum “Math-for-Industry” and Study Group Workshop
Information security, visualization, and inverse problems, on the basisof optimization techniques 100pages

October 21, 2010

COE Lecture Note Vol.28

ANDREAS LANGERMODULAR FORMS, ELLIPTIC AND MODULAR CURVESLECTURES AT KYUSHU UNIVERSITY 2010 62pages

November 26, 2010

COE Lecture Note Vol.29

木田 雅成
原田 昌晃
横山 俊一

Magma で広がる数学の世界

December 27, 2010

COE Lecture Note Vol.30

原
松井
廣島

Mathematical Quantum Field Theory and Renormalization Theory
201pages

January 31, 2011

COE Lecture Note Vol.31

若山 正人
福本 康秀
高木
剛
山本 昌宏

Study Group Workshop 2010 Lecture & ReportFebruary 8, 2011

COE Lecture Note Vol.32

Institute of Mathematics
for Industry,
Kyushu University

Forum “Math-for-Industry” 2011
“TSUNAMI-Mathematical Modelling”
Using Mathematics for Natural Disaster Prediction, Recovery andProvision for the Future 90pages

September 30, 2011

COE Lecture Note Vol.33

若山 正人
福本 康秀
高木
剛
山本 昌宏

Study Group Workshop 2011 Lecture & Report

October 27, 2011

COE Lecture Note Vol.34

Adrian Muntean
Vladimír Chalupecký

Homogenization Method and Multiscale Modeling

COE Lecture Note Vol.35

横山夫
林

計算機代数システムの進展

COE Lecture Note Vol.36

Michal Beneš
Masato Kimura
Shigetoshi Yazaki

Proceedings of Czech-Japanese Seminar in Applied Mathematics 2010
107pages

COE Lecture Note Vol.37

若山 正人
高木
剛
Kirill Morozov
平岡 裕章
木村 正人
白井 朋之
西井 龍映
栄 伸一郎
穴井 宏和
福本 康秀

平成23年度 数学・数理科学と諸科学・産業との連携研究ワーク February 20, 2012
ショップ 拡がっていく数学 ～期待される “見えない力” ～154pages

隆
卓
文生

俊一
紀恵
卓也

157pages

128pages

140pages

72pages

210pages

October 28, 2011

November 30, 2011

January 27, 2012

シリーズ既刊
Issue

Author／Editor

Title

Published

COE Lecture Note Vol.38

Fumio Hiroshima
Itaru Sasaki
Herbert Spohn
Akito Suzuki

Enhanced Binding in Quantum Field Theory

COE Lecture Note Vol.39

Institute of Mathematics
for Industry,
Kyushu University

Multiscale Mathematics: Hierarchy of collective phenomena andinter­relations between hierarchical structures 180pages

March 13, 2012

COE Lecture Note Vol.40

井ノ口順一
太田 泰広
筧
三郎
梶原 健司
松浦
望

離散可積分系・離散微分幾何チュートリアル2012

March 15, 2012

COE Lecture Note Vol.41

Institute of Mathematics
for Industry,
Kyushu University

Forum “Math-for-Industry” 2012
“Information Recovery and Discovery”

COE Lecture Note Vol.42

佐伯
若山
山本

Study Group Workshop 2012 Abstract, Lecture & Report

178pages

November 19, 2012

COE Lecture Note Vol.43

Institute of Mathematics
for Industry,
Kyushu University

Combinatorics and Numerical Analysis Joint Workshop

103pages

December 27, 2012

COE Lecture Note Vol.44

萩原学

モダン符号理論からポストモダン符号理論への展望

107pages

January 30, 2013

COE Lecture Note Vol.45

金山

寛

Joint Research Workshop of Institute of Mathematics for Industry(IMI), Kyushu University“Propagation of Ultra-large-scale Computation by the Domaindecomposition-method for Industrial Problems (PUCDIP 2012)”
121pages

February 19, 2013

COE Lecture Note Vol.46

西井 龍映
栄 伸一郎
岡田 勘三
落合 啓之
小磯 深幸
斎藤 新悟
白井 朋之

科学・技術の研究課題への数学アプローチ―数学モデリングの基礎と展開― 325pages

February 28, 2013

COE Lecture Note Vol.47

SOO TECK LEE

BRANCHING RULES AND BRANCHING ALGEBRAS FOR THE
COMPLEX CLASSICAL GROUPS 40pages

March 8, 2013

COE Lecture Note Vol.48

溝口
脇
平坂
谷口
島袋

博多ワークショップ「組み合わせとその応用」 124pages

March 28, 2013

修
正人
昌宏

佳寛
隼人
貢
哲至
修

204pages

March 12, 2012

152pages

October 22, 2012

91pagesシリーズ既刊
Issue

Author／Editor

COE Lecture Note Vol.49

照井
小原
濱田
横山
穴井
横田

MI Lecture Note Vol.50

章
功任
龍義
俊一
宏和
博史

Title

Published

マス・フォア・インダストリ研究所 共同利用研究集会 II
数式処理研究と産学連携の新たな発展 137pages

August 9, 2013

Ken Anjyo
Hiroyuki Ochiai
Yoshinori Dobashi
Yoshihiro Mizoguchi
Shizuo Kaji

Symposium MEIS2013:
Mathematical Progress in Expressive Image Synthesis

October 21, 2013

MI Lecture Note Vol.51

Institute of Mathematics
for Industry, Kyushu
University

Forum “Math-for-Industry” 2013
“The Impact of Applications on Mathematics”

MI Lecture Note Vol.52

佐伯
岡田
髙木
若山
山本

Study Group Workshop 2013 Abstract, Lecture & Report
142pages

November 15, 2013

MI Lecture Note Vol.53

四方 義啓
櫻井 幸一
安田 貴徳
Xavier Dahan

平成25年度 九州大学マス・フォア・インダストリ研究所
共同利用研究集会 安全・安心社会基盤構築のための代数構造～サイバー社会の信頼性確保のための数理学～ 158pages

December 26, 2013

MI Lecture Note Vol.54

Takashi Takiguchi
Hiroshi Fujiwara

Inverse problems for practice, the present and the future

January 30, 2014

MI Lecture Note Vol.55

栄 伸一郎
溝口 佳寛
脇
隼人
渋田 敬史

Study Group Workshop 2013 数学協働プログラム Lecture & Report
98pages

February 10, 2014

MI Lecture Note Vol.56

Yoshihiro Mizoguchi
Hayato Waki
Takafumi Shibuta
Tetsuji Taniguchi
Osamu Shimabukuro
Makoto Tagami
Hirotake Kurihara
Shuya Chiba

Hakata Workshop 2014
~ Discrete Mathematics and its Applications ~March 28, 2014

MI Lecture Note Vol.57

Institute of Mathematics
for Industry, Kyushu
University

Forum “Math-for-Industry” 2014:“Applications + Practical Conceptualization + Mathematics = fruitful
Innovation” 93pages

October 23, 2014

MI Lecture Note Vol.58

安生健一
落合啓之

Symposium MEIS2014:
Mathematical Progress in Expressive Image Synthesis

November 12, 2014

修
勘三
剛
正人
昌宏

154pages

October 30, 2013

97pages

93pages

141pages

135pagesシリーズ既刊
Issue

Author／Editor

MI Lecture Note Vol.59

西井
岡田
梶原
髙木
若山
脇
山本

龍映
勘三
健司
剛
正人
隼人
昌宏

MI Lecture Note Vol.60

西浦博

MI Lecture Note Vol.61

Title

Published

Study Group Workshop 2014 数学協働プログラム
Abstract, Lecture & Report 196pages

November 14, 2014

平成26年度九州大学 IMI 共同利用研究・研究集会（I）
感染症数理モデルの実用化と産業及び政策での活用のための新たな展開 120pages

November 28, 2014

溝口 佳寛
Jacques Garrigue
萩原
学
Reynald Affeldt

研究集会
高信頼な理論と実装のための定理証明および定理証明器
Theorem proving and provers for reliable theory and implementations(TPP2014) 138pages

February 26, 2015

MI Lecture Note Vol.62

白井朋之

Workshop on “β-transformation and related topics”

March 10, 2015

MI Lecture Note Vol.63

白井朋之

Workshop on “Probabilistic models with determinantal structure”
107pages

August 20, 2015

MI Lecture Note Vol.64

落合
土橋

啓之
宜典

Symposium MEIS2015:
Mathematical Progress in Expressive Image Synthesis

September 18, 2015

MI Lecture Note Vol.65

Institute of Mathematics
for Industry, Kyushu
University

Forum “Math-for-Industry” 2015
“The Role and Importance of Mathematics in Innovation”

MI Lecture Note Vol.66

岡田 勘三
藤澤 克己
白井 朋之
若山 正人
脇
隼人
Philip Broadbridge
山本 昌宏

Study Group Workshop 2015 Abstract, Lecture & Report
156pages

MI Lecture Note Vol.67

Institute of Mathematics
for Industry, Kyushu
University

IMI-La Trobe Joint Conference“Mathematics for Materials Science and Processing”
66pages

February 5, 2016

MI Lecture Note Vol.68

古庄
小谷
新甫

英和
久寿
洋史

結び目と Grothendieck-Teichmüller 群
116pages

February 22, 2016

MI Lecture Note Vol.69

土橋
鍛治

宜典
静雄

Symposium MEIS2016:
Mathematical Progress in Expressive Image Synthesis

MI Lecture Note Vol.70

Institute of Mathematics
for Industry,
Kyushu University

Forum “Math-for-Industry” 2016
“Agriculture as a metaphor for creativity in all human endeavors”
98pagesNovember 2, 2016

MI Lecture Note Vol.71

小磯
二宮
山本

Study Group Workshop 2016 Abstract, Lecture & Report

November 21, 2016

深幸
嘉行
昌宏

59pages

124pages

74pages

October 23, 2015

November 5, 2015

82pages

143pages

October 24, 2016

シリーズ既刊
Issue

Author／Editor
朝雄
泉
文生

Title

Published

MI Lecture Note Vol.72

新井
小嶋
廣島

MI Lecture Note Vol.73

穴田 啓晃
Kirill Morozov
須賀 祐治
奥村 伸也
櫻井 幸一

Secret Sharing for Dependability, Usability and Security of Network
Storage and Its Mathematical Modeling 211pages

March 15, 2017

MI Lecture Note Vol.74

QUISPEL, G. Reinout W.
BADER, Philipp
MCLAREN, David I.
TAGAMI, Daisuke

IMI-La Trobe Joint Conference
Geometric Numerical Integration and its Applications

March 31, 2017

MI Lecture Note Vol.75

手塚
田上
山本

Study Group Workshop 2017 Abstract, Lecture & Report

MI Lecture Note Vol.76

宇田川誠一

Tzitzéica 方程式の有限間隙解に付随した極小曲面の構成理論―Tzitzéica 方程式の楕円関数解を出発点として― 68pages

August 4, 2017

MI Lecture Note Vol.77

松谷 茂樹
佐伯
修
中川 淳一
田上 大助
上坂 正晃
Pierluigi Cesana
濵田 裕康

平成29年度 九州大学マス・フォア・インダストリ研究所
共同利用研究集会（I）
結晶の界面，転位，構造の数理 148pages

December 20, 2017

MI Lecture Note Vol.78

瀧澤 重志
小林 和博
佐藤憲一郎
斎藤
努
清水 正明
間瀬 正啓
藤澤 克樹
神山 直之

平成29年度 九州大学マス・フォア・インダストリ研究所
プロジェクト研究 研究集会（I）
防災・避難計画の数理モデルの高度化と社会実装へ向けて
136pages

February 26, 2018

MI Lecture Note Vol.79

神山
畔上

平成29年度 AIMaP チュートリアル
最適化理論の基礎と応用 96pages

February 28, 2018

MI Lecture Note Vol.80

Kirill Morozov
Hiroaki Anada
Yuji Suga

IMI Workshop of the Joint Research Projects
Cryptographic Technologies for Securing Network Storage
and Their Mathematical Modeling 116pages

March 30, 2018

MI Lecture Note Vol.81

Tsuyoshi Takagi
Masato Wakayama
Keisuke Tanaka
Noboru Kunihiro
Kazufumi Kimoto
Yasuhiko Ikematsu

IMI Workshop of the Joint Research Projects
International Symposium on Mathematics, Quantum Theory,
and Cryptography 246pages

September 25, 2019

MI Lecture Note Vol.82

池森

令和 2 年度 AIMaP チュートリアル
新型コロナウイルス感染症にかかわる諸問題の数理
145pages

March 22, 2021

集
大助
昌宏

直之
秀幸

俊文

Mathematical quantum field theory and related topics

133pages

71pages

118pages

January 27, 2017

October 20, 2017

シリーズ既刊
Issue

Author／Editor

Title

Published

MI Lecture Note Vol.83

早川健太郎
軸丸 芳揮
横須賀洋平
可香谷 隆
林
和希
堺
雄亮

シェル理論・膜理論への微分幾何学からのアプローチとその建築曲面設計への応用 49pages

July 28, 2021

MI Lecture Note Vol.84

Taketoshi Kawabe
Yoshihiro Mizoguchi
Junichi Kako
Masakazu Mukai
Yuji Yasui

SICE-JSAE-AIMaP Tutorial
Advanced Automotive Control and Mathematics

December 27, 2021

110pages九州大学マス・フォア・インダストリ研究所

九州大学大学院 数理学府
URL http://www.imi.kyushu-u.ac.jp/