Pairing Type Optimization Problem and Its Hardness
○Fumitaka Hoshino(Secure Platform Laboratories, NTT Corporation)、Masayuki Abe(Secure Platform Laboratories, NTT Corporation)、Miyako Ohkubo(Security Fundamentals Laboratory, CSR, NICT)
An asymmetric pairing requires asymmetric input pair, namely there exist two input data types for an asymmetric pairing. This means crypto designers must choose a data type for each variables consistently in their cryptographic schemes. For some cases, it is actually impossible to satisfy such data type assignments. Even if it is possible, their choice drastically impacts on the efficiency of their schemes. Therefore it is interesting how to satisfy and optimize this assignment, but it becomes a complicated task when the scheme is large. Pairing type satisfiability and optimization problems are formalizations of such tasks. It is known that there exists a polynomial-time algorithm to solve the pairing type satisfiability problem. However it has been unclear how hard the pairing type optimization problem is. In this work, we provide a comprehensive theory of pairing type optimization problem, and show that there exists no algorithm to solve it in the worst case in time polynomial in the size of input, if P != NP.
Detection of Malicious JavaScript Contents Using Doc2vec Feature Learning
◎Sammie Ndichu Wangari(神戸大学)、小澤 誠一(神戸大学)、三須 剛史(セキュアブレイン)、岡田 晃市郎(セキュアブレイン)
To add more functionality and enhance usability of web applications, JavaScript (JS) is frequently used. Even with many advantages and usefulness of JS, an annoying fact is that many recent cyberattacks such as drive-by-download attacks exploit vulnerability of JS codes. In general, malicious JS codes are not easy to detect, because they sneakily exploit vulnerabilities of browsers and plugin software, and attack visitors of a web site unknowingly. To protect users from such threads, the development of an accurate detection system for malicious JS is soliciting. Conventional approaches often employ signature and heuristic-based methods, which are prone to suffer from zero-day attacks, i.e., causing many false negatives and/or false positives. For this problem, this paper adopts a machine-learning approach to feature learning called Doc2Vec, which is a neural network model that can learn context information of texts. The extracted features are given to a classifier model (e.g., SVM and neural networks) and it judges the maliciousness of a JS code. In the performance evaluation, we use the D3M Dataset (Drive-by-Download Data by Marionette) for malicious JS codes and JSUPACK for Benign ones for both training and test purposes. We then compare the performance to other feature learning methods. Our experimental results show that the proposed Doc2Vec features provide better accuracy and fast classification in malicious JS code detection compared to conventional approaches.
Homomorphic encryption allows us to perform various calculations on encrypted data without decryption. In this paper, we propose an efficient method for secure multiple matrix multiplications over the somewhat homomorphic encryption scheme proposed by Brakerski and Vaikuntanathan (CRYPTO 2011). Our method is a generalization of Duong et al.'s method (Tatra Mt. Publ. 2016), which computes only one multiplication between two matrices. Specifically, in order to minimize both the ciphertext size and the computation cost, our method enables us to pack every matrix into a single ciphertext so that it enables efficient matrix multiplications over the packed ciphertexts. We also propose several modifications to obtain practical performance of secure multiplications among matrices with large size and entries. Furthermore, we show implementation results of our packing method with modifications for secure multiplications among two and three matrices with 32 x 32 and 64 x 64 sizes and entries from 16-bit to 64-bit.
An Improvement on the Linear Algebraic Attack for the Indeterminate Equation Encryption Scheme
○Yasuhiko Ikematsu(九州大学)、Koichiro Akiyama(東芝)、Tsuyoshi Takagi(九州大学)
At SAC2017, Akiyama et al. proposed the indeterminate equation encryption scheme. It is an algebraic surface encryption based on a solution problem of indeterminate equations, and has been considered a candidate for post-quantum cryptosystems. A public key X for this scheme is a polynomial in two variables over a finite ring. Akiyama et al. also proposed two attacks, the linear algebraic attack (LAA) and the key recovery attack (KRA), by using the lattice structure associated with this scheme. In this paper, we give an improvement on LAA. Also we explain the relation between our improvement and the improvement on LAA proposed by Xagawa and examine parameters that those attacks fail by experiments. As a result, we conclude that if the total degree of the public key X is one, then KRA is more efficient than LAA and if that of X is two, then LAA is more efficient than KRA.
1B2-6
A Variant of Quantum Information Set Decoding Algorithms
○Hyungrok Jo(東京大学大学院新領域創成科学研究科)
The security of code-based cryptosystems such as the McEliece or the Niederreiter cryptosystems essentially relies on decoding a linear code. In other words, it has been studying on the difficulty of syndrome decoding problem to check their security. It is also important to find a suitable candidate even in the era of post-quantum cryptography. A decoding algorithm due to Prange in 1969 has improved the best known decoding algorithm named information set decoding techniques.
Bernstein in 2010 widen the research in a quantum version by combining Grover's quantum search with Prange's algorithm, which obtain a quadratic speed-up of its original algorithm. Kachigar-Tillich in 2017 improved Shamir-Schroeppel's and May-Meurer-Thomas's information set decoding algorithms by using Grover's quantum search and a quantum walk techniques which were devised for the subset-sum problem by Bernstein's et al. in 2013.
In this paper, we studied on the security of a variant of Kachigar-Tillich's algorithm by manipulating the graphs' structure and adjusting the number k of subsets for solving the generalised k-sum problem in quantum walk techniques.
A Security Model for Authenticated Automotive Networks
○Camille Vuillaume(Bosch Corporation)
The security of vehicles has been put in question, already back in 2010 with academic research on this topic, but also more recently with presentations at Black Hat and DEF CON that have been widely reported by the mass media every year since 2015.
In the meantime, the automotive industry has not been idle. One of the result of a joint effort by car makers and component suppliers was to a agree on a standard specification for a software module called SecOC aiming at authenticating messages in vehicular network. Indeed, as of now, most of these messages, which can control safety critical systems like brakes or steering, can be easily spoofed.
However, the SecOC specification does not define which cryptographic algorithm is used or which parameters are adequate. Moreover, the overall achievable security is limited by the length of messages, which can only have up to 8 bytes in the case of the CAN network. In this paper, we propose a new security model under which it is possible to derive a sufficient security level even under these limiting factors, and examine the security of some algorithms and parameters that have been suggested for the SecOC.
秘密計算の実用可能性
荒木俊則(日本電気株式会社)、五十嵐 大(NTTセキュアプラットフォーム研究所)、○高橋克巳(NTTセキュアプラットフォーム研究所)、竹之内隆夫(日本電気株式会社)、Mehdi Tibouchi(NTTセキュアプラットフォーム研究所)、花岡悟一郎(産業技術総合研究所)、古川潤(NEC Israel Research Center)
Ding Key Exchange -- A Proposal to NIST PQC Competition
Jintai Ding(University of Cincinnati)、Tsuyoshi Takagi(The University of Tokyo)、◎Xinwei Gao(Beijing Jiaotong University)、Yuntao Wang(Kyushu University)
In this paper, we introduce a new RLWE-based key exchange protocol, which has been submitted to NIST's post-quantum cryptography standardization competition. Our construction is an optimized variant of the RLWE key exchange proposed by Ding et al. in 2012. Our protocol is a RLWE variant of the classic Diffie-Hellman key exchange protocol, which can be regarded as a direct drop-in replacement for current widely-deployed Diffie-Hellman key exchange protocol (and its variants, e.g. elliptic curve Diffie-Hellman). We believe that our proposal is secure, efficient, simple and elegant with wide application prospect. We present two parameter choices ensuring $2^{-60}$ key exchange failure probability which cover different security levels. Concrete security level analysis on different parameter choices will be given in a companion paper.
2B1-2
Security Evaluation for Ding Key Exchange
◎Yuntao Wang(Kyushu University, University of Tokyo)、Xinwei Gao(Beijing Jiaotong University)、Jintai Ding(Cincinnati University)、Tsuyoshi Takagi(Kyushu University, University of Tokyo)
At the beginning of 2016, NIST started the post-quantum cryptography competition to prepare for the standardization of the next-generation cryptography. Ding et al. proposed a \lq\lq Ding Key Exchange" scheme, which is based on the Ring Learning With Errors Problem (RLWE).Since the number of samples in their scheme is just one, which is different from the case of normal integer LWE or other RLWE instances, we do the security analysis for Ding key exchange by primal attack which is reducing the RLWE to SIS. Hence we can expand the dimension of the attack basis to double. We adopt both the progressive BKZ simulator and the so called 2016 estimation in New Hope paper. Guaranteeing the error rate of key exchange protocol within $2^{-60}$, our parameter choices cover the security of AES-128/192/256 respectively, which satisfies NIST's security category \uppercase\expandafter{\romannumeral1}, \uppercase\expandafter{\romannumeral3} and \uppercase\expandafter{\romannumeral5} respectively.
In addition, we discussed the key reuse attack and claim that Ding key exchange should not execute key reuse. And we proposed a reconciliation-based key reusable RLWE key exchange protocol in the end.
2B1-3
AtLast: Another Three-party Lattice-based PAKE Scheme
◎Rakyong Choi(KAIST)、Hyeongcheol An(KAIST)、Kwangjo Kim(KAIST)
Password-based Authenticated Key Exchange (PAKE) protocol assumes that the parties share a low-entropy, easy-to-remember password to achieve the authentication with a high-entropy session key. PAKE protocols can be employed to hand-held devices for access control of sensitive personal data remotely.
For communication with more than one user, the user needs to remember all passwords between other users. To resolve this problem, a three-party PAKE (3PAKE) protocol, where user only shares a password with a server, is introduced.
In this paper, we construct a novel lattice-based three-party PAKE protocol, AtLast, based on the hardness of ring-LWE assumption, with a simple design and extend Ding et al.'s PAKE protocol with implicit server authentication, RLWE-PPK protocol, to three-party setting by modifying the generic approach by Abdalla et al. Then, we compare our protocol with Xu et al.'s three-party PAKE protocol, RLWE-3PAKE, over lattices.
2B1-4
Revisiting CK17 Linearly Homomorphic Ring Signature based on Ring-LWE
◎Rakyong Choi(KAIST)、Kwangjo Kim(KAIST)
In SCIS 2017, Choi and Kim introduced the new linearly homomorphic ring signature scheme (CK17 scheme) based on the hardness of SIS problem, which overcomes the limitation of Boneh and Freeman's scheme to implement homomorphic signatures to the real world scenario under multiple signers setting for a message.
They replace the original sampling algorithm SamplePre() by Gentry et al. with Wang and Sun's sampling algorithm GenSamplePre() to achieve the multiple-signer functionality but their work is lack of the rigorous security proof. Thus, this paper revisits the CK17 scheme and makes an advanced definition which is subring-identical linearly homomorphic signature, and suggests a security requirements on it.
Then, we show the correctness and subring-identical linear homomorphism of the proposed scheme.
QTL-128は2016年にLang Liらによって提案された変形Feistel構造を持つブロック暗号である。鍵長128ビット、段数20段、ブロック長は64ビットである。QTL-128の提案論文では線形解読、差分解読、代数攻撃に対する安全性評価が行われており、零相関線形攻撃(Zero-Correlation Linear Cryptanalysis=ZCLC)は行われていない。ZCLCとは、入出力における特定ビットの線形和がZero correlationとなる特性を利用して解読を行う方法である。この特性を利用しZero correlationとなった時の鍵を真の鍵候補とし、そうでない時の鍵を偽として、鍵推定を行う。本稿ではQTL-128に対しのSBOX入出力マスクが0に限られる場合と、1に限られる場合の特性を利用し、零相関線形トレイル(Zero-Correlation Linear Trail=ZCLT)を導出し、ZCLCを用いてQTL-128の解読を行った。その結果、4.5段のZCLTを発見し、このZCLTを利用して6.5段の鍵回復攻撃を行えることを発見した。
An Efficient Private Equality Test towards Big Data
◎Tushar Kanti Saha(Saitama University)、Takeshi Koshiba(Waseda University)
In this paper, we review the problem of private batch equality test (PriBET) that was proposed by Saha and Koshiba (3rd APWConCSE 2016). They described this problem to find the equality of an integer within a set of integers between two parties who do not want to reveal their information if they do not equal. For this purpose, they proposed the PriBET protocol along with a packing method using the binary encoding of data. Their protocol was secured by using ring-LWE based somewhat homomorphic encryption (SwHE) in the semi-honest model. But this protocol is not fast enough to address the big data problem in some practical applications. To solve this problem, we propose a base-$N$ fixed length encoding based PriBET protocol using SwHE in the same semi-honest model. Here we did our experiments for finding the equalities of 8~64-bit integers. Furthermore, our experiments show that our protocol is able to evaluate more than one million (resp. 862 thousand) of equality comparisons per minute for 8-bit (resp. 16-bit) integers with an encoding size of base 256 (resp. 65536). Besides, our protocol works more than 8~20 in magnitude than that of Saha and Koshiba.
MinematsuとIwata [Minematsu, Iwata, IMA CC 2011]は,nビットブロックtビットtweakのtweakableブロック暗号(ただし1<=t<=n)とハッシュ関数を用いて,(n+t)ビットブロック暗号を構成し,その安全性を証明した.またCoronら[Coron, et al., TCC 2010]はnビットブロックnビットtweakのtweakableブロック暗号のみを用いた2nビットブロック暗号の安全性を証明した.本稿ではこれらの先行研究から自然に得られる,nビットブロックtビットtweakのtweakableブロック暗号(ただし1<=t<n)のみを用いた(n+t)ビットブロック暗号に対し,その安全性証明をCoefficient-H技法を用いて行う.
Validating IGE Mode of Block Cipher from Quantum Adversaries
Sungsook Kim(School of Computing, KAIST)、◎Jeeun Lee(School of Computing, KAIST)、Rakyong Choi(School of Computing, KAIST)、Kwangjo Kim(School of Computing, KAIST)
The Telegram which is a very popular messenger uses a special mode called IGE(Infinite Garble Extension). IGE mode is not included in standard mode of operation recommended by National Institute of Standards and Technology(NIST) in 2001. Block cipher encrypts fixed length of plaintext into the corresponding fixed-length of ciphertext using a secret key shared by two parties and utilizes lots of mode of operation for various length of plaintext. Even though Telegram uses non-standard IGE mode, Telegram is claimed to be secure and demonstrate their security is stronger than other IM’s. Thus, we need to verify the security of IGE mode depending on underlying block ciphers. In this paper, we show that IGE mode block cipher used in Telegram assuming sPRF is not IND-qCPA, but assuming qPRF is IND-qCPA.
近年IoTを支える技術として,環境発電が注目されている.環境発電は,環境中の太陽光や電磁波,振動,風力,熱などのエネルギーを収集して,電力へ変換する技術である.一方で,半導体の偽造品の脅威が指摘されており,この対策としてPhysical Unclonable Function (PUF)が注目されている.今後,IoTなど幅広い分野で利用が期待される環境発電においても偽造品への対策について検討することは非常に重要である.そこで本研究では,環境発電を利用したPUFについての基本検討を行う.提案するPUFでは,環境発電デバイスの発電電力の違いをPUFとして利用する.そして,5つの太陽電池を用いた評価実験により提案するPUFの有効性について検証する.
Security in the Automotive Software Development Lifecycle
○Dennis Kengo Oka(Synopsys)
Modern vehicles are run on software containing more than 100 million lines of code. As a result of more advanced functionality such as ADAS and autonomous driving being introduced, vehicles contain more software being developed and assembled by a number of different parties such as OEMs and tier 1 and tier 2 suppliers. Moreover, as new use cases for the connected car such as controlling various vehicle functions from mobile apps, the addition of numerous communication interfaces as well as collecting and processing vehicle data in the OEM backend are developed, even more software is needed in the automotive industry. To ensure software security for above scenario, there is a need to secure the automotive software development lifecycle. This paper presents how to address security for each step in the software development lifecycle.
近年の車両は,車載制御ネットワークにより接続された70~100台のElectronics Control Unit(ECU)により制御されると共に,車両外の様々なサービスとネットワークを介して制御データを共有し利便性を向上させている.しかし,この様に複雑なシステムはセキュリティ上の脆弱性を招き,多くの研究により車両へのサイバー攻撃の可能性が指摘されている.このためのセキュリティ対策として,車両への未知のサイバー攻撃を検知可能な,車載ネットワークでのアノマリ型侵入検知システムが知られている.しかし従来の検知方式では,攻撃者がECUの周期的な送信を止めた後に異常フレームを挿入するケースの検知が難しい.本論では,この様なケースも検知可能とするため,相関データにより通信フレーム中のコンテキストデータを監視するアノマリ型侵入検知方式を提案する.本提案方式では,監視対象コンテキストデータの現在値を,学習済みの車両データモデルを用いて監視対象と相関関係にあるコンテキストデータから推定し,監視対象コンテキストデータの現在値と推定値の差異を評価して検知を行う.筆者達は,提案方式の有効性を試験車両で取得したCANトラフィックを用いて確認したので報告する.
Smart CAN cable, Another proposal of intrusion prevention system (IPS) for in-vehicle networks
○Kiyotaka ATSUMI(LAC Co., Ltd.)、Masaya UWATOKO(NetAgent Co., Ltd.)、Ryoichi KIDA(LAC Co., Ltd.)、Narumi HIRAI(NetAgent Co., Ltd.)、Yuki MIZUNO(NetAgent Co., Ltd.)
Many ideas of IDS for vehicles were already proposed so far. Most of them can only detect anomaly CAN messages, but they cannot detect which ECU is compromised because any ECUs can't identify the ECU who sends illegal messages for the specification of CAN protocol.
Now we propose the smart CAN cable that identifies the ECU who sends malicious messages.The smart CAN cable has two kinds of functions. One is a CAN IDS. The CAN IDS identifies an illegal message, and it broadcasts the hash value of the illegal message to CANBUS. Another is an identifying module. The identifying module is to memorize hash values of the messages and its sender ECU. When the identifying module receives the hash value from the CAN IDS, it broadcasts the sender ECU information to CANBUS if it finds the hash value in its own memory. We can cut the sender ECU from CANBUS, or control the stream of it, or handle other workarounds after we identify the sender ECU who sends illegal messages.
This paper shows how the smart CAN cable works, and its advantages and disadvantages.
Web Browser Fingerprinting と呼ばれる手法により, Web サーバが利用者の端末を追跡することができる.利用者を追跡することで,広告のマッチングなどを行っているが,利用者のプライバシが侵害される問題がある. Web Browser Fingerprinting では,主にブラウザから採取できるソフトウェアとハードウェアの特徴点を用いているが,ソフトウェア特徴点は変わりやすいためハードウェア特徴点を重要視するものが増えている .
そこで本論文では,仮想マシンを用いてハードウェア特徴点からの追跡を防ぐ Anti Browser Fingerprinting を提案する.その有効性を評価する実験を行った結果,同一の Fingerprint を生成できたが,端末の識別可能性は残った.
IoTシステムでは,センサが実世界のデータを収集し,その蓄積・解析を行い,結果を基にサービスの提供や制御を行っている.システムにはその用途に応じて一定のセキュリティが求められる.セキュアなシステムを構築するためには,データを収集する段階におけるセンサを対象とした「計測セキュリティ」を評価し,強化し,保証する技術の確立が必要である.
本稿では,一定の範囲にある物体の位置関係を点群として取得可能なTime of Flight(ToF)方式の距離画像カメラを対象とする計測セキュリティの一評価手法を提案する.ToF距離画像カメラに対しては,カメラが発射した測定光を攻撃者が観測し,それをもとに攻撃光(なりすまし光)を生成して測定対象物へ照射することにより,測定値の改ざんができる可能性のあることが確認されている.複数のToF距離画像カメラを比較した結果,カメラが発射する測定光パルスの種類や構造の違いが,この攻撃の難易度や必要コストに影響を与えることが分かった.そこでToF距離画像カメラの計測セキュリティを評価する方法として,外部から測定光を観測する手法を提案し,評価項目や課題について検討を行った.
Multiparty Key Agreement Scheme Using Partially Leaked Key Exchange Graphs
◎Bateh Mathias Agbor(Graduate School of Information Sciences, Tohoku University)、Tatsuya Sasaki(Graduate School of Information Sciences, Tohoku University)、Yu-ichi Hayashi(Nara Institute of Science and Technology)、Takaaki Mizuki(Cyberscience Center, Tohoku University)、Hideaki Sone(Cyberscience Center, Tohoku University)
We consider a scenario with n players (n>3), in which several pairs of players have agreed on individual one-bit keys. These pre-shared keys are assumed to be partially leaked to an eavesdropper, Eve. Given such a partially leaked key exchange graph and two qualified players, the existing protocol can make the qualified players share a one-bit key u in {0,1} with the help of other players such that Eve’s knowledge about u is as small as possible, where Eve overhears all communication between the players. As a natural extension, it is desirable to extend this two qualified players key agreement problem to the k qualified players case, where k>2. Because it seems difficult to resolve the problem comprehensively, we restrict our attention to a limited class of partially leaked key exchange graphs, called uniformly leaked key exchange complete graphs where every pair of players has a pre-shared key and each key has leaked independently with the same fixed probability. Thus, this paper deals with how any k qualified players can generate a one-bit common key u from a uniformly leaked key exchange complete graph. Specifically, we propose a one-round protocol that makes the k qualified players generate a common key u using edge disjoint Hamiltonian paths.
2A4-3
一般アクセス構造をもつ関数秘密分散のフーリエ基底を利用した構成
○小柴健史(早稲田大学)
Function secret sharing (FSS) scheme is a mechanism that calculates a function f(x) for x in {0,1}^n which is shared among p parties, by using distributed functions f_i : {0,1}^n --> G, where G is an Abelian group, while the function f : {0,1}^n --> G is kept secret to the parties. Ohsawa et al. in 2017 observed that any function f can be described as a linear combination of the basis functions by regarding the function space as a vector space of dimension 2^n and gave new FSS schemes based on the Fourier basis. All existing FSS schemes are of (p,p)-threshold type. That is, to compute f(x), we have to collect f_i(x) for all the distributed functions. In this paper, as in the secret sharing schemes, we consider FSS schemes with any general access structure. To do this, we observe that Fourier-based FSS schemes by Ohsawa et al. are compatible with linear secret sharing scheme. By incorporating the techniques of linear secret sharing with any general access structure into the Fourier-based FSS schemes, we show Fourier-based FSS schemes with any general access structure.
超特異楕円曲線間の同種写像を用いた認証鍵共有方式を提案する。我々の方式は、初めて1-ラウンドのDiffie-Hellman型ポスト量子認証鍵共有を実現しており、様々な(非自明な)秘密鍵漏えいに対する最大限の安全性(CK^+ モデル安全性)を実現する。その安全性は、ランダムオラクルモデルで gap Diffie-Hellman仮定の同種写像版に基づいて証明されている。また、量子ランダムオラクルモデルでの安全性についても論じる。
Non-interactive and Output Expressive Private Comparison from Homomorphic Encryption and the Applications
Wen-jie Lu(University of Tsukuba)、◎Jun-jie Zhou(University of Tsukuba)、Jun Sakuma(University of Tsukuba, RIKEN AIP Center, JST CREST)
Private comparison is about privately determining whether a > b, given two input
integers a and b which are held as private information. Private comparison is an import building block
for applications such as secure auctions and privacy-preserving decision tree evaluation.
In this paper, we consider a variant setting in which the inputs a and b as well as the result bit
1{a > b} are encrypted. Using a ring variant of a fully homomorphic encryption scheme, our solution
takes as input the ciphertexts of a and b and produces only one ciphertext which decrypts to the bit
1{a > b} without any interaction with the secret key holder. Our approach does not encrypt the
inputs bit-wisely and requires only one multiplicative depth, giving about 44 ? 150-fold speed up than
previous solutions. Also, the non-interactive property is useful for securely outsourcing computation to
an untrusted server. As a concrete usecase, we present a single round protocol for privacy preserving
decision tree evaluation.
3A1-2
Private Mann-Whitney U Test using Fully Homomorphic Encryption
◎Jun-jie Zhou(University of Tsukuba)、Wen-jie Lu(University of Tsukuba)、Jun Sakuma(University of Tsukuba, RIKEN AIP Center, JST CREST)
Mann-Whitney U test enables to compare two independent groups without the normal distribution assumption. This is particularly useful in psychological researches since the number of available samples in such field is usually too small to support the normal distribution assumption. Besides, special cares about the data privacy are necessary when to conduct the Mann-Whitney U test in an untrusted environment, such as cloud servers.
In this study, we build a privacy-preserving protocol for outsourcing the U test to an untrusted server. In our construction, all the private data are encrypted using a fully homomorphic encryption scheme, and only ciphertexts are uploaded to the server, and thus no private information about the data is leaked. We first design a new equality-to subprotocol which enables us to handle the rank of ties in the U test. By cooperating with our previous greater-than protocol, we present a private protocol that computes the U statistics from encrypted data. Also, we present an optimization to reduce the number of homomorphic multiplications from O(n^2) to O(n) where n is the size of data.
機微情報を含んだデータの計算をクラウドサーバなどの安全が保障されない環境上で行うため、準同型暗号の活用が考えられる。準同型暗号がサポートする加算・乗算などの基本的演算の組み合わせにより、種々の統計計算および機械学習に用いられる演算が安全に可能であると期待されている。本論文では、Ring-LWEベース暗号をはじめとする、多項式の加算・乗算をサポートする準同型暗号を用いた安全な内積演算[Wang et al. in NSS 2017]を応用した、安全かつ効率的な行列乗算手法について報告する。先行研究[Dung et al. in Tatra Mt. Math. Publ. 2016]においては、行列積ABの安全な計算のためにA、Bをそれぞれ異なる方法で多項式へとパッキングしていたのに対し、本研究では同一のパッキング手法で可能である。また、C言語を用いた実装実験の結果についても報告する。
3C1-2
Inproved Decoding Algorithm for Lattice Trapdoor Function
◎佐々木 健太郎(NEC)、太中 裕貴(NEC)、峯松 一彦(NEC)、寺西 勇(NEC)
Lattice based cryptography receives much attention because of its simplicity, quantum computer resistance and wide range of applications, for example, Hash then Signature, IBE and ABE. In many of these applications, a function named trapdoor one-way function plays an important role. We improve Micciancio Peikert's trappdoor one-way function, which is one of the most efficient trapdoor, in the point of parallelizability and give experimental evaluations.
QChain: Quantum-resistant and Decentralized PKI using Blockchain
○Hyeongcheol An(KAIST)、Kwangjo Kim(KAIST)
Blockchain was developed under public domain and distributed database using the P2P connection. Therefore, blockchain does not have any central administrator or Certificate Authority(CA). However, Public Key Infrastructure(PKI) must have CA which issues and signs the digital certificates. PKI CA must be fully trusted by all parties in a domain. Also, current public key cryptosystem can be broken using quantum computing attacks. The post-quantum cryptography (PQC) must be secure against the quantum adversary. We combine blockchain technique with one of post-quantum cryptography lattice-based cryptosystems. In this paper, we suggest QChain which is quantum-resistant decentralized PKI system using blockchain. We propose modified lattice-based GLP signature scheme. QChain uses modified GLP signature which uses Number Theoretic Transformation (NTT). We compare currently used X.509 v3 PKI and QChain certificate.
近年,住宅内の白物家電や設備機器のエネルギー管理システム(HEMS: Home Energy Management System)が急速に普及してきており,HEMSを構成する機器がネットワークに接続されるケースが増えている.一方でHEMS機器は,コストやそのハードウェア資源上の制約から十分なセキュリティ機能を実装していないものも散見される.HEMSのセキュリティ機能では,不正な機器による成りすましを防止するだけでなく,機器の状態変化通知等で多用されるマルチキャスト通信を保護できる必要がある.また,異なるメーカの機器で構成されるHEMSにおいては,機器の種別やアプリケーションごとにグループ管理できることが望ましい.本稿では, PANA/EAP-TLSとIEEE 802.21のグループ鍵管理をHEMSに応用することで,HEMSにおける機器認証,マルチキャスト通信の保護,およびグループ管理を実現する方法を提案する.
Mining for operation specific actionable cyber threat intelligence in publicly available information source
◎Otgonpurev Mendsaikhan(Nagoya University)、Hirokazu Hasegawa(Nagoya University)、Yukiko Yamaguchi(Nagoya University)、Hajime Shimada(Nagoya University)
In order to proactively monitor and prevent any security incident, the significance of the threat intelligence is increasing. However, the huge volume of the threat intelligence data makes incident responder of some organization difficult to utilize those cyber threat intelligence effectively.
In order to assist the incident response process, we are trying to develop the system that collects specific cyber threat intelligence related to the operation of one’s organization from publicly available information. To realize this system, we propose a machine learning and natural language processing techniques to generate actionable threat intelligence using social media and other publicly available information sources. In this paper, we tried to validate this approach with the prototype of the system.
We extracted 65 keywords from more than 800 CVE descriptions of National Vulnerability Database using TFIDF algorithm. With the help of these keywords, we have retrieved nearly 230,000 tweets using Twitter API during the period of 4 days, from which we were able to extract actionable intelligence.
これまで、通信相手や通信時刻などの通信のメタデータを秘匿して暗号通信を行うプロトコルが研究されてきた。しかし、それらはメタデータの定義が曖昧であったり、peer to peerの通信を対象としていた。本研究では、グループ間の通信を対象とし、通信のメタデータを秘匿したままでのグループ鍵交換(MH-GKE)の安全性モデルを定義する。また、MH-GKEプロトコルを提案する。
Security Notions for Random Oracle Model in Classical and Quantum Settings
◎Jeeun Lee(School of Computing, KAIST)、Seunghyun Lee(Department of Mathematical Sciences, KAIST)、Kwangjo Kim(School of Computing, KAIST)
The advent of quantum computers and their algorithms has opened the era of post-quantum and quantum cryptography. Accordingly, new security proof tools and notions in the quantum setting need to be settled in order to prove the security of cryptographic primitives appropriately. As the random oracle model is accepted as an efficient security proof tool, it has been suggested to extend it from classical to quantum setting by allowing adversary's access to quantum power. In this paper, we look at the background of classical, quantum-accessible, and quantum random oracle models for classical, post-quantum, and quantum cryptography, respectively, and how they are defined. Also, the security notions for random oracle model in classical and quantum settings are introduced such as IND-ATK, (IND/wqIND/qIND)-qATK, and cqIND-qATK, for ATK $\in$ {CPA, CCA1, CCA2}. Finally, comparison of different cryptography eras are provided.
A Hybrid HW-SW Solution for Protecting In-Vehicle Network Communications
○Yao Lu(Trillium Incorporated)、Hiroyuki Inoue(Hiroshima City University)、David M. Uze(Trillium Incorporated)
In-Vehicle Networks (IVN) were originally designed to be operated in a closed network environment. However, now they are increasingly connected directly or indirectly to the Internet. Due to its public access nature, connectivity creates several security vulnerabilities. In this paper we present a hybrid hardware-software security architecture for protecting in-vehicle communications. To validate and optimize this solution, an IVN facsimile has been created for extensive real world testing outside of vehicles. IVN consist of many ECU with different security capabilities. For this reason, we propose a series of different security strategies for different types of ECU and thus have architected a highly configurable testing platform.
3E2-4
JASO TP15002に基づく自動車システムのセキュリティ設計の考察
川西康之(産業技術総合研究所 情報技術研究部門)、○西原秀明(産業技術総合研究所 情報技術研究部門)、相馬大輔(産業技術総合研究所 情報技術研究部門)、吉田博隆(産業技術総合研究所 情報技術研究部門)、畑洋一(住友電気工業株式会社)
Google Play ストアより提供されるAndroidアプリケーションでは、同じアプリケーションでもデバイスごとに異なるアプリケーションパッケージ(APK)を配布するMutiple APK機能が利用可能である。DICOMO 2017で関岡らの調査により、Multiple APKではAPK間で全く異なる動作をするアプリケーションの受け入れが可能であることが示された。それにより特定の端末を対象とした悪意のあるAPK配布の脅威が指摘されていた。本稿では、その脅威の現実性を明らかにするためにGoogle Play上でMulitple APKの配布を実施しているアプリケーションに対してそれぞれのAPKを取得し、APK間の差異を調査し、実際のアプリケーションでAPK間に差異があることを明らかにする。また、MultipleAPKの設定を応用することで、特定端末の特定APIレベルに対してのみ展開が可能なAPKの可能性を示す。
Measurement Study of the Hijackable Internet Resources inside Mobile Apps
◎Elkana Pariwono(Waseda University)、Daiki Chiba(NTT Research)、Mitsuaki Akiyama(NTT Research)、Tatsuya Mori(Waseda University)
The ability to connect to the internet enables mobile application (app) to provide rich feature. The problem is that to keep Internet resources such as domain name and server in the cloud running, it requires the developer to pay and maintain the resource. Meanwhile, the trend in current mobile application development is that after the developer published the application, they do not maintain it afterwards. If the developer does not renew it then this resource will be released and obtainable by others. The potential victim of hijacking this resource is the remaining user that are still using the app. In addition to this, depending on the previous owner and how the developer use the resource, the changing ownership on this resource and the prevalence of the effect will vary. In order to shed light on this problem, we conduct an empirical study on it and investigate the threats that could emerge from abandoned resource inside mobile application. By searching through hundred thousand of Android applications, we confirmed the existence of such resource inside the code.
我々は、escar eu 2016において、擬似乱数を利用した車載CANの不正通信検出手法を発表した。提案手法は、CANのID領域に埋め込まれた秘密乱数をハードウェアで高速にフィルタリングして通信認証することにより、メッセージ認証子を用いる一般的な通信認証よりもDoS攻撃耐性が高いことが特長である。本講演は、本手法で用いるCANコントローラをRTLで試作した結果を報告する。
CAN(Controller Area Network)は,車載ネットワーク等に広く用いられるバス型ネットワーク規格である.CANに対する脅威として電気的データ改ざん攻撃が指摘されている.この攻撃は,攻撃ツールがバスの電位差を直接操作することで,送信ECUに検知されることなく改ざんされたメッセージをバス上のECUに受信させる攻撃である.CANには意図したデータがバス上に流れたことを送信側で確認するビットモニタリングの機構が規定されているが,送信側と受信側のCANバスの信号をサンプリングするタイミングの違いを利用することで,異なるメッセージを受信させることができる.電気的データ改ざんにおいて従来の手法では攻撃した際,エラーとなることが多かった.本論文では,従来手法で攻撃を行い攻撃が成功した際のCANバスの電圧波形を取得し,取得した波形で攻撃対象メッセージのデータフィールド以降の部分を置換する手法の提案を行う.また,自動車向けセキュリティテストベッドにおいて提案手法での攻撃成功確率が向上することを実証するとともに,セキュリティ強化策の導入が必要であることを指摘する.
APIコール列を分析対象とするマルウェアの動的解析手法において、近年 Word Embedding として知られる手法を用い、自然言語処理のアプローチを導入する研究が活発になされている。コール列を構成する各API関数をベクトルで表現することで、マルウェア検知など目的となるタスクにおける性能を向上することが期待されているのだが、そのベクトル表現の獲得は、バイナリからコールされる順序の情報のみを用いる方法がこれまで主だった。我々は、コール列以外の外部の情報をAPI間の関係構築に活かすことに着目し、コール順序のみではなく、仕様書におけるAPI関数の機能説明文の情報を用いてベクトル化する手法を提案する。また、シーケンス長が非常に長いデータからの特徴抽出方法として、1次元CNNとLSTMを複数段組む、階層時系列モデルを提案する。18個のマルウェアファミリーと、それ以外とする全19クラスの分類を実験を行い、従来のコール順序のみを使う手法による分類精度が30.4%に対し、提案手法では42.1%となった。
Performance Evaluation of liboqs in Open Quantum Safe Project (Part I)
○Hyeongcheol An(KAIST)、Rakyong Choi(KAIST)、Jeeun Lee(KAIST)、Kwangjo Kim(KAIST)
Famous public key cryptosystem such as RSA and Diffie-Hellman is not secure against quantum computer. Also, the emergence of quantum computers is not theoretical but is actually in practical. Post-Quantum Cryptography (PQC) means quantum-resistant cryptography. Lattice-based cryptography has been known as one of PQC. Learning with Errors (LWE), Ring Learning with Errors (Ring-LWE), and Module Learning with Errors(Module-LWE) are the mathematical hard problems in lattice-based cryptography. In public domain, Open Quantum Safe (OQS) project develops quantum-resistant cryptosystems such as lattice-based, code-based, and supersingular isogeny elliptic curve as open source. We focus on lattice-based OQS projects such as BCNS15, NewHope, MSrln, Kyber, and Frodo. In this paper, we check and compare the performance of OQS key exchange protocols using lattices. Then, we suggest future work in OQS project.
3A4-2
Prey on Lizard : Mining Secret Key on Lattice-based Cryptosystem
◎Seongho Han(KAIST)、Nakjun Choi(KAIST)、Hyeongcheol An(KAIST)、Rakyong Choi(KAIST)、Kwangjo Kim(KAIST)
With the development of quantum computers, post-quantum cryptography has been researched in the last decades. Lattice-based cryptography is one of the most fascinating candidates of post-quantum cryptography. This is due to the average and worst case provable security on lattice such as Learning with Errors(LWE) and Learning with Rounding(LWR). Lattice-based encryption scheme called Lizard based on LWE and LWR by Cheon et al. was suggested as a candidate public key cryptosystem for long-term security according to call-for-post quantum cryptography by NIST recently. Lizard was suggested to have great performance and high level of security. However, Lizard could be exploited because of its C implementation. In this paper, we investigate the way to break Lizard by side channel attacks such as timing and fault attacks. From these attacks, we can find secret key from source code. Finally, we propose countermeasures to protect Lizard from our attacks.
Portable implementation of post-quantum encryption schemes and key exchange protocols on JavaScript-enabled platforms
◎Ye Yuan(Graduate School of Mathematics, Kyushu University)、Junting Xiao(Graduate School of Mathematics, Kyushu University)、Kazuhide Fukushima(KDDI Research, Inc.)、Shinsaku Kiyomoto(KDDI Research, Inc.)、Tsuyoshi Takagi(Institute of Mathematics for Industry, Kyushu University)
Quantum computers have the potential to solve some difficult mathematical problems efficiently, thus will inevitably exert a greater impact on the traditional asymmetric cryptography. Therefore, NIST has opened a formal call for the submissions and proposals of quantum-resistant public-key cryptographic algorithms to set the next-generation cryptography standards.
Compared to web applications or high capacity hardware with more processors, IoT devices, including the massive number of microcontrollers, smart terminals and sensor nodes with very limited computing capacity, also should have some post-quantum cryptography features for security and privacy. In order to ensure the correct execution of encryption algorithms on any architectures, the portability of implementation becomes more important. As distinguished from C/C++, JavaScript is a well-known cross platform language that can be used for the web applications and some hardware directly, thus it could be one of the solutions of the portability.
Therefore, we investigate and implement several recent lattice-based encryption schemes and public-key exchange protocols such as Lizard, Kyber, Frodo, and NewHope, which are the strong candidates of post-quantum cryptography due to their applicabilities and efficiencies, and show the performance of our implementation on web browsers and an embedded device "Tessel2" in JavaScript. Our results indicate that the efficient implementation of lattice-based cryptography on JavaScript-enabled platforms are both desirable and achievable.
An Efficient Decryption Algorithm for Extension Field Cancellation
◎Yacheng Wang(Graduate School of Mathematics of Kyushu University)、Yasuhiko Ikematsu(Institute of Mathematics for Industry, Kyushu University)、Dung H. Duong(Institute of Mathematics for Industry, Kyushu University)、Tsuyoshi Takagi(Institute of Mathematics for Industry, Kyushu University)
Extension Field Cancellation (EFC) was proposed by Alan et al. at PQCrypto 2016 as a new trapdoor for constructing quantum resistant multivariate encryption cryptographic schemes. Along with this trapdoor, two schemes EFCp- and EFCpt2- that apply this trapdoor and some modifiers were proposed. Though their security seems to be high enough, their decryption efficiency has room for improvement. In this paper, we introduce a new and more efficient decryption approach for EFCp- and EFCpt2-, which manages to avoid all redundant computation involved in the original decryption algorithms, and theoretically speed up the decryption process of EFCp- and EFCpt2- by around 3.8 and 7.8 times respectively under 128-bit security parameters with our new designed private keys for them. Meanwhile, our approach does not interfere with the public key, so the security remains the same. The implementation results of both decryption algorithms for EFCp- and EFCpt2- are also provided.
Almost Fully Secured Fully Dynamic Lattice-based Group Signatures with Verifier-local Revocation
◎Perera M Nisansala S(Saitama University)、Koshiba Takeshi(Waseda University)
We present a lattice-based group signature scheme that provides both member registration and member revocation with verifier-local revocation mechanism. Verifier-local revocation (VLR) seems to be the most suitable revocation approach for any group since when a member is revoked VLR requires only to update verifiers who are smaller in number than members. In 2003 Bellare et al. (EUROCRYPT 2003) provided the currently strongest security model (BMW03 model) for group signature schemes. However, it serves only for static groups. In ACNS 2016 Bootel et al. provided a rigorous security model for dynamic groups. Yet, presenting a fully secured lattice-based group signature with verifier-local revocation is a significant challenge. Thus, we discuss two security notions to prove the security of VLR schemes without the member registration and to prove the security of VLR schemes with the member registration. As a result, we present an almost fully secure fully dynamic group signature scheme from lattices.
Boneh and Freeman proposed a homomorphic signature scheme based on lattice. After that, many homomorphic signature schemes have been proposed, but most of them are available for single user. Some applications need a homomorphic signature scheme between multi-users. Such signature scheme should be both homomorphic and aggregative, and it is called the homomorphic aggregate signature (HAS). As far as the authors' knowledge, there are only two HAS in the literature and both are linearly homomorphic. One was proposed by Jing, and the other was proposed by Zhang and Wang. In this paper, we propose HAS for polynomial funcitons. Our scheme is obtained by applying Boneh-Freeman's method on Jing's HAS.
様々なモノがネットワークに接続するInternet of Things(IoT)におけるサービスの安全性を高める上では,モノ同士の通信経路を暗号化することが有効である.センサなどにマイクロコントローラを搭載し通信を行うような計算資源の限られた環境では,計算資源豊富な環境向けの暗号ライブラリを用いることが難しいため,軽量で高速な暗号ライブラリが必要とされている.一方,公開鍵暗号方式として現在主流のRSA暗号や楕円曲線暗号は,量子計算機により安全性の根拠となる数学的問題が解かれてしまうとされている.これに対し,量子計算機を用いても暗号の解読ができないと期待されているRing-LWE暗号が注目されている.しかし計算資源の乏しい環境でRing-LWE暗号を利用するには鍵生成や暗号化の計算コストを減らす軽量化が必要となる.そこで,本論文ではセンサノードなどで用いられるARM Cortex-M0+マイクロコントローラを対象にRing-LWE暗号の軽量・高速な実装を行い,実行サイクル数やメモリ使用量等の性能を評価する.
プライバシポリシ自動要約のための完全性及びリスク評価に関する調査
○中村 徹(KDDI総合研究所)、ウェルデルファエル B. テスファイ(Goethe University Frankfurt)、清本 晋作(KDDI総合研究所)、ジュザベル サーナ-オルベラ(Goethe University Frankfurt)
BLS曲線における Optimal Ate Pairing の実装と評価
◎馬渕圭史(九州大学大学院数理学府)、横山俊一(九州大学数理学研究院)、齋藤恆和(NTTセキュアプラットフォーム研究所)
次世代の公開鍵暗号方式として任意のIDを公開鍵として利用できるIDベース暗号があり,実際のサービスへの利用が進んでいる.このIDベース暗号の多くは楕円曲線上のペアリングを用いて実装されており,安全性はそのペアリングについての離散対数問題の困難性が仮定となる.CRYPTO2016においてKim等は任意のペアリングについての離散対数問題に対する解析手法の改良を提案し,ペアリングの安全性レベルが下がった.この解析手法に耐えうるものとして,SCIS2017において清村等は256ビット安全なペアリングのパラメタとしてBLS48のパラメタを提案した.本稿では,IDベース署名のOSSであるlibsnarkを元にBLS48のパラメタを用いてOptimal Ate Pairing (OAP)を実装し,さらにlibsnark内のペアリングパラメタBN128とのOAPと比較評価した.
Google Home やAmazon Echoなど,音声認識機能を備えたスマートスピーカーの流行により,音声入力によるデバイスの制御がより身近なものとなっている.その一方で,セキュリティの国際会議では,声による個人認証を突破する攻撃や,人の耳では聞こえない超音波によるスマートスピーカーやスマートフォンへの攻撃の可能性が示唆され,話題となっている.
本論文では,パラメトリックスピーカーによって,利用者に聞こえないように遠隔で音声入力を行おうとする攻撃の可能性を指摘する.パラメトリックスピーカーとは,スピーカーの向いている方向にのみ音声を再生する指向性の鋭いスピーカーであり,この性質によって,利用者に気づかれないようにデバイスを操作できてしまう可能性がある.
今回の検証実験で,過去に示されていた超音波による攻撃よりも離れた位置からの攻撃ができることを示し,その成功確率を示した.また,指向性の鋭さから,雑音に対する耐性が強く,比較的雑音の大きい環境でも音声が認識されてしまうことを示した.最後に,攻撃の有効性を示すために簡易的な実験を行い,利用者が正面方向にいなければ秘密裏に攻撃が成立してしまうことを示した.
The research on secure poker protocols without trusted intermediaries has a long history that dates back to modern cryptography's infancy. Two main challenges towards bringing it into real-life are enforcing the distribution of the rewards, and penalizing misbehaving/aborting parties. Using recent advances on cryptocurrencies and blockchain technologies, Andrychowiczet al. (IEEE S&P 2014 and FC 2014 BITCOIN Workshop) were able to address those problems. Improving on these results, Kumaresan et al. (CCS 2015) and Bentov et al. (ASIACRYPT 2017) proposed specific purpose poker protocols that made significant progress towards meeting the real-world deployment requirements. However, their protocols still lack either efficiency or a formal security proof in a strong model. Specifically, the work of Kumaresan et al. relies on Bitcoin and simple contracts, but is not very efficient as it needs numerous interactions with the cryptocurrency network as well as a lot of collateral. Bentov et al. achieve further improvements by using stateful contracts and off-chain execution: they show a solution based on general multiparty computation that has a security proof in a strong model, but is also not very efficient.
The previous works left several gaps in terms of formalization and proof of security. In that matter, we present two improved protocols called KALEIDOSCOPE specifically designed for poker game, and ROYALE the protocol for card games in general.
Both of our protocols closes this formalization and security undesirable gap from the previous work as it concurrently: (1) enforces the rewards' distribution; (2) enforces penalties on misbehaving parties; (3) has efficiency comparable to the tailor-made protocols; (4) has a security proof in a simulation-based model of security. Combining techniques from the above works, from tailor-made poker protocols and from efficient zero-knowledge proofs for shuffles, and performing optimizations, we obtain a solution that satisfies all four desired criteria and does not incur a big burden on the blockchain.
Ouroboros and Ouroboros Praos: Provably Secure Proof-of-Stake Blockchain Protocols
◎Bernardo David(Tokyo Institute of Technology)、Peter Gazi(Input Output HK)、Aggelos Kiayias(University of Edinburgh)、Alexander Russel(University of Connecticut)
We present “Ouroboros” and "Ouroboros Praos", the first blockchain protocols based on proof-of-stake with rigorous security guarantees. We establish security properties for our protocols comparable to those achieved by the bitcoin blockchain protocol. As our protocols provide a “proof of stake” blockchain discipline, they offer qualitative efficiency advantages over blockchains based on proof of physical resources (e.g., proof of work). While Ouroboros only provides security against "semi-adaptive" adversaries in synchronous networks, “Ouroboros Praos” provides, for the first time, a robust distributed ledger that is provably secure in the semi-synchronous adversarial setting, i.e., assuming a delay in message delivery that is unknown to protocol participants, and fully adaptively secure, i.e., the adversary can choose to corrupt any participant of an ever evolving population of stakeholders at any moment as long the stakeholder distribution maintains an honest majority of stake at any given time. To achieve that, it puts to use forward secure digital signatures and a new type of verifiable random functions that maintains unpredictability under malicious key generation, a property we introduce and instantiate in the random oracle model. Our security proofs entail a combinatorial analysis of a class of forkable strings representing adversarial behavior (tailored to synchronous and semi-synchronous blockchains) that may be of independent interest in the context of security analysis of blockchain protocols. We showcase the practicality of Ouroboros in real world settings by providing experimental results on transaction processing time obtained with a prototype implementation in the Amazon cloud.