You are looking at a specific version 20190329:131009 of this paper. See the latest version.

Paper 2019/325

An Efficient Private Evaluation of a Decision Graph

Hiroki Sudo and Koji Nuida and Kana Shimizu

Abstract

A decision graph is a well-studied classifier and has been used to solve many real-world problems. We assumed a typical scenario between two parties in this study, in which one holds a decision graph and the other wants to know the class label of his/her query without disclosing the graph and query to the other. We propose a novel protocol for this scenario that can obliviously evaluate a graph that is designed by an efficient data structure called the graph level order unary degree sequence (GLOUDS). The time and communication complexities of this protocol are linear to the number of nodes in the graph and do not include any exponential factors. The experiment results revealed that the actual runtime and communication size were well concordant with theoretical complexities. Our method can process a graph with approximately 500 nodes in only 11 s on a standard laptop computer. We also compared the runtime of our method with that of previous methods and confirmed that it was one order of magnitude faster than the previous methods.

Metadata
Available format(s)
PDF
Category
Applications
Publication info
Published elsewhere. Minor revision. ICISC2018
DOI
10.1007/978-3-030-12146-4_10
Keywords
decision graphhomomorphic encryptionoblivious transfer and GLOUDS.
Contact author(s)
hsudo108 @ ruri waseda jp
History
2019-03-29: received
Short URL
https://ia.cr/2019/325
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.