Research Activities

2017.4-2018.3

Selected papers

1. Hiroshi Nomaguchi, Atsuko Miyaji, Chunhua Su, "Evaluation and Improvement of Pseudo-Random Number Generator for EPC Gen2", The 16th IEEE International Conference On Trust, Security And Privacy In Computing And Communications (TrustCom-17), pp. 721-728, (2017).

RFID enable applications are ubiquitous in our society, especially become more and more important as IoT management rises. Meanwhile, the concern of security and privacy of RFID is also increasing. The pseudorandom number generator is one of the core primitives to implement RFID security. Therefore, it is necessary to design and implement a secure and robust pseudo-random number generator (PRNG) for current RFID tag. In this paper, we study the security of light-weight PRNGs for EPC Gen2 RFID tag which is an EPC Global standard. Based on our analysis, we propose an new scheme which outperform the existing PRNGs for EPC Gen2 RFID tag. We build our PRNG with a combination of NLFSR and DLFSR, and achieve more efficiency and security. We also show that our proposed PRNG has good randomness and passed the NIST randomness test. we also shows that it is resistant to identification attacks and GD attacks.

2. Tomoaki Mimoto, Shinsaku Kiyomoto, Katsuya Tanaka, Atsuko Miyaji, "(p, N)-identifiability: Anonymity under Practical Adversaries", The 16th IEEE International Conference On Trust, Security and Privacy In Computing And Communications (TrustCom 2017), pp. 996-1003, (2017)

Personal data has great potential for building an efficient and sustainable society; thus several privacy preserving techniques have been proposed to solve the essential issue of maintaining privacy in the use of personal data. Anonymization techniques are promising techniques applicable to huge-size personal data in order to reduce its re-identification risk. However, there is a trade-off between the utility of anonymized datasets and the risk of re-identification of individuals from the anonymized dataset, and so far no perfect solution has been provided. In previous studies, ideal adversaries in possession of all records of an original dataset have been considered in risk analyses, because an anonymized dataset is assumed to be publicly accessible, and once the record of a target is re-identified, privacy breaches are serious and may be uncontrollable. However, anonymized datasets are assumed to be distributed between organizations via secure channels in typical business situations. In this paper, we consider the actual risk to anonymized datasets and propose an analysis method that yields more stringent risk estimation in real settings with real adversaries. Furthermore, we present some experimental results using medical records. Our method is practical and useful for anonymized datasets generated by common anonymization methods such as generalization, noise addition and sampling, and can lead to generate more useful anonymized datasets.

3. 西田佳史, 北村光司, 米山尚子, 山中龍宏, "災害共済給付データとテキストマイニング技術を用いた柔道事故のトレンド分析," 日本公衆衛生雑誌Vol.64, No.10, pp. 649

Published Papers

Steven Gordon, Xinyi Huang, Atsuko Miyaji, Chunhua Su, Karin Sumongkayothin, Komwut Wipusitwarakun,``Recursive Matrix Oblivious RAM: An ORAM Construction for Constrained Storage Devices", IEEE Trans. Information Forensics and Security 12(12), pp. 3024-3038, (2017)
Yong Yu, Atsuko Miyaji, Man Ho Au, Willy Susilo, ``Cloud computing security and privacy: Standards and regulations", Computer Standards & Interfaces 54, pp.1-2, (2017).
Rashed Mazumder, Atsuko Miyaji, Chunhua Su, "A simple construction of encryption for a tiny domain message", the 51th Annual Conference on Information Sciences and Systems(CISS2017), IEEE, 1-6, 2017.
Tung Chou, "McBits revisited: toward a fast constant-time code-based KEM", Journal of Cryptographic Engineering, pp. 1-13, (2018).
Chen-Mou Cheng, Kenta Kodera, and Atsuko Miyaji,``On the computational complexity of ECDLP for elliptic curves in various forms using index calculus", the 20th Annual International Conference on Information Security and Cryptology (ICISC 2017), Lecture Notes in Computer Science, vol. 10779, pp. 245 - 263, (2018).
Ha Thi Thu Doan, François Bonnet, and Kazuhiro Ogata, ``Specifying a Distributed Snapshot Algorithm as a Meta-Program and Model Checking it at Meta-Level'', in the 37th IEEE International Conference on Distributed Computing Systems (ICDCS), pp. 1586-1596, June (2017).
François Bonnet, Quentin Bramas, Xavier Défago, Thanh Dang Nguyen, ``Killing Nodes as a Countermeasure to Virus Expansion'', in the 24th International Colloquium on Structural Information and Communication Complexity (SIROCCO), pp. 227-243, (2017).
François Bonnet, Simon Viennot, ``Analytical Solution for "EinStein würfelt nicht!" with one stone!'', in the 15th International Conference on Advances in Computer Games (ACG), pp. 1-12, (2017).
François Bonnet, Simon Viennot, ``Toward Solving EinStein würfelt nicht!'', in the 15th International Conference on Advances in Computer Games (ACG), pp. 13-25, (2017).
Ha Thi Thu Doan, François Bonnet, and Kazuhiro Ogata, ``Model Checking of Robot Gathering'', in the 21st International Conference On Principles Of Distributed Systems (OPODIS), pp. 1-16, (2017).
Tomoaki Mimoto, Shinsaku Kiyomoto, Katsuya Tanaka, Atsuko Miyaji, "(p, N)-identifiability: Anonymity under Practical Adversaries", The 16th IEEE International Conference On Trust, Security And Privacy In Computing And Communications (TrustCom 2017), pp. 996-1003, (2017).
Hiroshi Nomaguchi, Atsuko Miyaji, Chunhua Su,``Evaluation and Improvement of Pseudo-Random Number Generator for EPC Gen2",The 16th IEEE International Conference On Trust, Security And Privacy In Computing And Communications (TrustCom-17), pp. 721-728, (2017).
Shinsaku Kiyomoto, Mohammad Shahriar Rahman, Anirban Basu, "On blockchain-based anonymized dataset distribution platform",15th IEEE International Conference on Software Engineering Research, Management and Applications (SERA 2017), pp. 85 - 92, (2017).
Yoshifumi Nishida, Koji Kitamura, Mikiko Oono, "Smart transfer of social problem into industry by linking living data center with social function library: Case study of toothbrush injury prevention", the 3rd IEEE Annual International Smart Cities Conference, (2017).
Toru Nakamura, Welderufael B. Tesfay, Shinsaku Kiyomoto, Jetzabel Serna, "Default Privacy Setting Prediction by Grouping User's Attributes and Settings Preferences", the 12th International Workshop on Data Privacy Management (DPM2017), LNCS, vol. 10436, pp. 107-123, (2017).
Rashed Mazumder, Atsuko Miyaji, Chunhua Su: "Probably Secure Keyed-Function Based Authenticated Encryption Schemes for Big Data." Int. J. Found. Comput. Sci. 28(6): 661-682 (2017)

2016.4-2017.3

International Conference

Security core technology group
[J-1] Atsuko Miyaji, Kazuhisa Nakasho, Shohei Nishida, ``Privacy-Preserving Integration of Medical Data A Practical Multiparty Private Set Intersection",Journal of Medical Systems,Vol. 41 No. 3, pp. 1-10, (2017)

Medical data are often maintained by different organizations. However, detailed analyses sometimes require these datasets to be integrated without violating patient or commercial privacy. Multiparty Private Set Intersection (MPSI), which is an important privacy-preserving protocol, computes an intersection of multiple private datasets. This approach ensures that only designated parties can identify the intersection. In this paper, we propose a practical MPSI that satisfies the following requirements: The size of the datasets maintained by the different parties is independent of the others, and the computational complexity of the dataset held by each party is independent of the number of parties. Our MPSI is based on the use of an outsourcing provider, who has no knowledge of the data inputs or outputs. This reduces the computational complexity. The performance of the proposed MPSI is evaluated by implementing a prototype on a virtual private network to enable parallel computation in multiple threads. Our protocol is confirmed to be more efficient than comparable existing approaches.

Secure data management group
[K-1] Nakamura T., Kiyomoto S., Tesfay W.B., Serna J, "Easing the Burden of Setting Privacy Preferences: A Machine Learning Approach", Communications in Computer and Information Science book series, (CCIS), Volume 691, Springer, 2017.

Setting appropriate privacy preferences is both a difficult and cumbersome task for users. In this paper, we propose a solution to address users' privacy concerns by easing the burden of manually configuring appropriate privacy settings at the time of their registration into a new system or service. To achieve this, we implemented a machine learning approach that provides users personalized privacy-by-default settings. In particular, the proposed approach combines prediction and clustering techniques, for modeling and guessing the privacy profiles associated to users' privacy preferences. This approach takes into consideration the combinations of service providers, types of personal data and usage purposes. Based on a minimal number of questions that users answer at the registration phase, it predicts their privacy preferences and sets an optimal default privacy setting. We evaluated our approach with a data set resulting from a questionnaire administered to 10,000 participants. Results show that with a limited user input of 5 answers the system is able to predict the personalised privacy settings with an accuracy of 85%.

Living safety testbed group
[A-1] Kenta Imai, Koji Kitamura, Yoshifumi Nishida, Hiroshi Takemura, Tatsuhiro Yamanaka, "Smart Share of Serious Injury among Schools in the Era of Cloud Computing," Injury Prevention, Vol. 22, No. 2(Proc. of the 12th world conference on injury prevention and safety promotion (Safety2016)), pp. A236, September 2016.

[Background] A large number of injuries occur in Japanese school environments. To prevent injuries in school, it is important to share injury data and find serious injuries that we have to deal with. In this paper, we developed a cloud computing system for sharing serious injury among schools.

[Methods] We develop the following method; First, using text mining, we obtain feature values expressing characteristics of the situation for each situation data. Second, we detect serious injury situation that should be shared among schools by evaluating both similarity among environmental characteristics of schools and medical cost. We use 5,817 injuries from sixty nine Japanese schools' injury data to evaluate the developed system in cooperation with Japan Sport Council. This injury data include Japanese elementary and junior high school injury data.

[Results] The developed system classified 5,817 injury data were into twenty three groups and could detect serious injuries for each group. The developed system also enables us to recommend serious situations that a school risk manager should know. For example, when a user inputs "a student was playing tag and hit his head on a chin-up bar." into the system, the system outputs "a student was playing with ball after school. He ran after the ball and hit his nose on a chin-up bar." The output injury case is similar to the input injury case but it is much more serious since bone fractures occurred. Thus, system allows us to share serious injury situation among schools.

[Conclusions] We describes a new system for sharing serious injury in a new manner that fits with the era of cloud computing. Disseminating the developed software to more schools and creating community for school safety is an important future work.

Health testbed group

2016.4-2015.3 ===> 2015.4-2016.3

International Conference

Security core technology group
[J-1] Ryoma Ito and Atsuko Miyaji, "Refined Glimpse correlations of RC4", IEICE Trans., Fundamentals. Vol. E99-A, No.1, 3-13, 2016.
Secure data management group
[K-1] Toru Nakamura, Shinsaku Kiyomoto, Welderufael B. Tesfay, Jetzabel Serna-Olvera, "Personalised Privacy By Default Preferences - Experiment and Analysis -", 2nd International Conference on Information Systems Security and Privacy (ICISSP2016), 53-62, 2016.
Living safety testbed group
Health testbed group

2015.4-2016.3 ===> 2014.4-2015.3

International Conference

Security core technology group
[J-1] Atsuko Miyaji and Kazumasa Omote, "Self-healing wireless sensor networks", Concurrency and Computation: Practice and Experience, Vol. 27 No.10, 2547-2568, 2015
[J-2] Steven Gordon, Atsuko Miyaji, Chunhua Su and Karin Sumongkayothin, "M-ORAM: A Matrix ORAM with logN bandwidth cost", The 16th International Workshop on Information Security Applications (WISA 2015), Lecture Notes in Computer Science, 9503, Springer-Verlag, 3-15, 2015.
[J-3] Jiageng Chen, Atsuko Miyaji, Chunhua Su and Liang Zhao, "A New Statistical Approach For Integral Attack", The 9th International Conference on Network and System Security (NSS 2015), Lecture Notes in Computer Science, 9408, 345-358, 2015.
[J-4] Atsuko Miyaji and Syouhei Nishida, "A Scalable and Efficient Multiparty Private Set Intersection ", The 9th International Conference on Network and System Security(NSS 2015), Lecture Notes in Computer Science, 9408(2015), Springer-Verlag, 376-385.

Both scalability and flexibility become crucial for privacy preserving protocols in the age of Big Data. Private Set Intersection (PSI) is one of important privacy preserving protocols. Usually, PSI is executed by 2-parties, a client and a server, where both a client and a server compute jointly the intersection of their private sets and at the end only the client learns the intersection and the server learns nothing. From the scalable point of view, however, the number of parties are not limited to two. In this paper, we propose a scalable and flexible multiparty PSI (MPSI) for the first time: the data size of each party is independent to each other and the computational complexity is independent to the number of parties. We also propose d-and-over MPSI for the first time.

Keywords
Multi party, PSI
[J-5] Ryoma Ito and Atsuko Miyaji, "How TKIP induces biases of internal states of generic RC4", The 20th Australasian Conference on Information Security and Privacy(ACISP 2015), Lecture Notes in Computer Science, 9144(2015), Springer-Verlag, 329-342.

In 2014, Sen Gupta et al. found linear correlations between the keystream byte and known RC4 key bytes. In 2015, Our previous work extended linear correlations to include unknown internal states as well as the keystream byte and known RC4 key bytes. They found more than 150 linear correlations experimentally, and proved only 6 cases theoretically. In this paper, we will provide theoretical proof of 15 cases out of their unproven linear correlations. These theoretical results demonstrated how TKIP key generation procedure in WPA induces biases on internal states different from generic RC4.

Keywords
RC4, WPA, linear correlation
[J-6] Steven Gordon, Atsuko Miyaji, Chunhua Su and Karin Sumongkayothin, "Analysis of Path ORAM toward Practical Utilization", 18th International Conference on Network-Based Information Systems(NBiS), 646-651, 2015.

Oblivious RAM is known as a secure protocol for hiding client's access pattern from an untrusted server. However, the current ORAM algorithms still incur large computation, storage and communication overheads. For this reason, investigation of the ORAM limitations and methods to improve efficiency in real-world environments is necessary. In this paper we focus on one of the leading algorithms, Path ORAM, and propose an efficient implementation. Specifically we analyse the selection of encryption algorithms, concluding the use of AES-GCM to avoid duplication of blocks on the server. Also we propose extending Path ORM by using local caching on the client to reduce communication overhead. Experimental results from our Python implementation show key tradeoffs for ORAM design.

Keywords
ORAM
[J-7] Jiageng Chen, Atsuko Miyaji, Hiroyuki Sato and Chunhua Su, "Improved Lightweight Pseudo-Random Number Generators for the Low-Cost RFID Tags", The 14th IEEE International Conference on Trust, Security and Privacy in Computing and Communications (IEEE TrustCom'15), IEEE, 500-508, 2015.

EPC Gen2 tags are working as international RFID standards for the use in the supply chain worldwide, such tags are computationally weak devices and unable to perform even basic symmetric-key cryptographic operations. For this reason, to implement robust and secure pseudo-random number generators (PRNG) is a challenging issue for low-cost Radio-frequency identification (RFID) tags. In this paper, we study the security of LFSR-based PRNG implemented on EPC Gen2 tags and exploit LFSR-based PRNG to provide a better constructions. We provide a cryptanalysis against the J3Gen which is LFSR-based PRNG and proposed by Sugei et al. for EPC Gen2 tags using distinguish attack and make observations on its input using NIST randomness test. We also test the PRNG in EPC Gen2 RFID Tags by using the NIST SP800-22. As a counter-measure, we propose two modified models based on the security analysis results. We show that our results perform better than J3Gen in terms of computational and statistical property.

Keywords
light weight pseudo random number generators,RFID tag,randomness test
[J-8] Atsuko Miyaji and Xiaonan Shi and Satoru Tanaka, "Extended Explicit Relations Between Trace, Definition Field, and Embedding Degree", 6th International Conference on Algebraic Informatics (CAI 2015), Lecture Notes in Computer Science, 9270(2015), Springer-Verlag, 165-175.

An elliptic curve cryptosystem (ECC) is one of public key cryptosystem, whose security is based on elliptic curve discrete logarithm problem (ECDLP). An elliptic curve is uniquely determined by mathematical parameters such as j-invariant of an elliptic curve. By giving trace of elliptic curve, t, a definition field Fp , and discriminant D , an elliptic curve with order E(Fp) = n is determined. Therefore it is an open problem to determine explicit relations between the mathematical parameters and the embedding degrees k. Hirasawa and Miyaji presented concrete relations between the mathematical parameters and the embedding degrees. In this research, a new explicit relation between elliptic-curve parameters and embedding degrees is investigated by generalizing their research.

Keywords
elliptic curve, embedding degree, trace
Secure data management group
Living safety testbed group
[A-1] Koji Kitamura, Kenta Imai, Yoshifumi Nishida, Hiroshi Takemura, Tatsuhiro Yamanaka, "Potential Risk Assessment System by Integrating Injury Data at Multiple Schools", The 6th International Conference on Applied Human Factors and Ergonomics (AHFE 2015), 1991-1998, July 2015.

A large number of injuries occur in Japanese school environments. To prevent injuries in schools, it is important to understand high-risk injuries based on injury data. In this paper, "high-risk" injuries indicate a high risk of leading to serious or fatal injuries. However, it is difficult to understand these injuries from the injury data of just a single school because a single school does accumulate much data. In this study, we developed a system for predicting serious injuries at individual schools by using injury data from multiple schools. The prediction process is as follows. First, the system registers injury situations with the feature values that express them by using a text mining technique to the database. Second, for a given injury data at target school, the system searches for similar injury situations in the registered data. Finally, it reports the particularly serious injuries from the viewpoint of medical cost from among the data covering similar situations. The effectiveness of the system was confirmed using the data of 5,817 school injuries.

Health testbed group

2014.4-2015.3 ===> 2013.4-2014.3

International Conference

Security core technology group
[J-1] Atsuko Miyaji and Mazumder Rashed, "A new (n, 2n) Double Block Length Hash Function based on Single Key Scheduling", The 29th IEEE International Conference on Advanced Information Networking and Applications (AINA 2015), IEEE, 1-8

In this paper we propose a double block length hash function called MR-MMO. Our scheme satisfies two calls of (n; 2n) blockcipher and can compress 3n bits to 2n bits (n = 128 bits). The Collision Resistance (CR) and Preimage Resistance (PR) of MR-MMO are respectively 2^126.70 and 2^252.5. Surprisingly, the collision security bound of our scheme is the best in compare with other existing schemes. We use a single key scheduling for each compression function which is great in respect of cost and time. Additionally, it can be said that the proof technique of Weimar-DM, Tandem-DM, Hirose-DM are based on Ideal Cipher Model (ICM while we use Weak Cipher Model (WCM) tool. Davies Meyer (DM) mode is used in the above all schemes, we also made a change using Matyas Meyer Oseas (MMO) mode. It is also obvious that the proof technique of our scheme is very simple, straightforward and easy to understand.

Keywords
Hash function, Blockcipher, SBL, DBL, Collision resistance (CR), Preimage resistance (PR), ICM, WCM
[J-2] Ryoma Ito and Atsuko Miyaji, "New Linear Correlations related to State Information of RC4 PRGA", The 22nd International Workshop on Fast Software Encryption (FSE 2015), Lecture Notes in Computer Science, Springer-Verlag, to appear.

RC4 is a stream cipher designed by Ron Rivest in 1987, and is widely used in various applications. WPA is one of these applications, where TKIP is used for a key scheduling procedure to avoid weak IV generated by WEP. In FSE 2014, two different attacks against WPA were proposed by Sen Gupta et al. and Paterson et al. Both focused correlations between the keystream bytes and the first three bytes of the RC4 key in WPA. In this paper, we focus on linear correlations between unknown internal state and the first three bytes of the RC4 key in both generic RC4 and WPA, where the first three bytes of the RC4 key is known in WPA. As a result, we could discover various new linear correlations, and prove these correlations theoretically.

Keywords
RC4, WPA, linear correlations
Secure data management group
[K-1] Kiyomoto, Y. Miyake, "Data Value Estimation for Privacy-Preserving Big/Personal Data Businesses", FMfI2014 Post-proceedings, 2015, accepted.

"Value Proposition" is a key factor when designing a business model. In personalized services, data value should be estimated using a certain model of data valuation. Generally, the data value depends on the size and precision of data, and it is expected to reflect the parameter $k$ in the size of $k$-anonymized data sets and its data precision. A data set is said to have \textit{$k$-anonymity} if each record is indistinguishable from at least $k-1$ other records with respect to certain identifying attributes called \textit{quasi-identifiers}. The parameter $k$ influences not only the re-identification risk of the published data but also its value. When $k$ is large, many attributes in the published data are replaced with uncharacteristic values in order to satisfy $k$-anonymity. On the other hand, a small $k$ involves a serious risk of re-identification. There is a trade-off between privacy level and data value in the generation of $k$-anonymized data sets. Based only on the privacy requirement for reducing the re-identification risk, many people may assent to distribution of their private data in the form of a $k$-anonymized table when $k$ is large enough or where as large $k$ as possible is chosen.

In this paper, we present a model for finding an appropriate $k$ in $k$-anonymization. The model suggests that an optimal $k$ exists that is appropriate to achieve a balance between value and anonymity when personal data are published.

Keywords
k-anonymity, Data Value, Personal Data
Living safety testbed group
[A-1] Y. Nishida, D. Nakazato, K. Kitamura, H. Mizoguchi, T. Yamanaka, "Childhood Home-Injury-Situation Simulation for Individual Environments Based on Child Physical Model and Injury Semantic Structure Model", the 6th International Conference on Applied Human Factors and Ergonomics (AHFE 2015) , 2015 (in press)

Most accidents involving children below the age of five occur within their homes. Since it is important to maintain a safe home environment for children, it is imperative to be able to predict what kinds of accidents may occur in a particular environment, and then to find ways to improve that environment. However, the various and scattered statistical data sources and scientific knowledge related to accident prediction have not been structured for integrative utilization. In this paper, the authors report on the development of a new simulation technology that can be used to predict the kinds of accidents that may occur in a particular environment by means of a hybrid memory- and model-based approach. The system consists of a graph-structuralized accident database created from large-scale accident data (which enables the memory-based approach), and a development behavior model which describes the statistical relationship between a body interaction abilities and the age of children.

Health testbed group