PWS Cup 2018における履歴データの最適な2-匿名化手法
◎飯田 泰興(三菱電機株式会社)、服部 充洋(三菱電機株式会社)、藤田 真浩(三菱電機株式会社)、伊藤 隆(三菱電機株式会社)、平野 貴人(三菱電機株式会社)、清水 りな(三菱電機株式会社)
情報処理学会コンピューターセキュリティ研究会(CSEC)のプライバシーワークショップ(PWS)では,パーソナルデータの匿名加工技術を競う匿名加工・再識別コンテスト(PWS Cup)が2015年から毎年開催されている.本年開催されたPWS Cup 2018では,購買履歴データに対する一般化による匿名加工,および加工データに対する再識別の技術力が争われた.本稿では,我々のチームが採用した匿名加工と再識別の各フェイズにおける戦略と,その理論的根拠を述べる.匿名加工フェイズでは,我々は2-匿名化を行うことを基本方針とし,データ加工による誤差を最小限にするべく,2-匿名化の組み合わせ問題をよく知られたグラフの最適化問題に帰着させ,最適化を行う手法を考案した.その結果,2-匿名化を実施したチームとしては最良の有用性評価値を達成した.一方,再識別フェイズでは,本コンテストで実施可能な加工方式の性質を生かし,加工前後の値の包含関係から真の顧客候補絞り込む手法を考案した.その結果,想定通りの再識別結果が得られることを確認した.
A First Step towards Statistical Disclosure Control on Multiple Linked Tables
○Kazuhiro Minami(The Institute of Statistical Mathematics)、Yutaka Abe(National Statistics Center)
To perform statistical disclosure control (SDC) on multiple tables is a challenging task because sensitive information can be revealed from intersections of multiple tables involving a common set of variables. This task is particularly difficult when each table contains a subset of the common variables because the intersection of those tables could form a subspace of any shape in the multi-dimensional domain space. To address this issue, we extend our SDC tool for solving a cell suppression problem of a two-dimensional table to support multi-dimensional ones. Our approach is to construct a single consolidated high-dimensional table from lower-dimensional multiple linked tables so that we can represent the constraints of each input table in an integrated way. In this paper, we describe the extended SDC tool for detecting possible sensitive cells, which could be overlooked if each table is examined separately.
近年の自動車は、車載ネットワークに接続されたElectronic Control Unit(ECU)により制御される。また、自動運転化などに伴い、ECUや車載ネットワークの高度化が進み、車載システムが急激に複雑化するため、セキュリティを担保する事が困難となってきている。事実、多くの研究者がセキュリティ上の脆弱性を狙ったサイバー攻撃の可能性を示唆している。一方でこれらのサイバー攻撃に対する対策手法として、通信周期やコンテキストデータの急激な変化を捉えて検知する手法があるが、攻撃者がECUの送信を停止し、異常フレームを挿入する攻撃の検知が困難である。本論文では、この様な攻撃への対策として、複数の推定値から検知を行う手法を提案する。また、本提案手法により、特定の深層学習モデルに入力するデータがなりすまされ、推定値が悪化した際も、他のモデルが推定した良好な値を用いる事で、正確な攻撃の検知が可能となる事を示す。
Legendre記号を用いて生成される2値幾何系列一様化のためのパラメータ選択に関する考察
○多田羅友也(岡山大学工学部)、小寺雄太(岡山大学大学院自然科学研究科)、日下卓也(岡山大学大学院自然科学研究科)、野上保之(岡山大学大学院自然科学研究科)、Robert H. Morelos-Zaragoza(Department of Electrical Engineering, San Jose State University, USA)
The general Frobenius additive fast Fourier transform
Wen-Ding Li(Academia Sinica)、○Chen-Mou Cheng(Osaka University)
The discrete Fourier transform evaluates a polynomial on roots of unity in a field, possibly of nonzero characteristic. As it turns convolution into pointwise multiplication, one important application of the discrete Fourier transform is thus to multiply polynomials, especially with coefficients in a finite field Fq. When q is small, we need to go to an appropriate extension field F to find enough roots of unity to work with. In this case, we typically use the Kronecker segmentation technique to encode the multiplicand polynomials in F[t]. In 2017, van der Hoeven and Larrieu showed how to avoid the factor-of-two overhead of Kronecker segmentation by embedding, rather than encoding, the multiplicand polynomials into F[t]. Specifically, they restrict the evaluation to a cross section of the set of roots of unity and then use the Frobenius map to recover the results outside of it. In this paper, we will show that this idea beautifully generalizes to a class of "additive" Fourier transforms first developed by Cantor and subsequently optimized by Gao-Mateer for an important special case. In particular, we will construct an explicit cross section for the Frobenius additive fast Fourier transform.
Hiding Personal Tendency in Set-valued Database Publication
○Dedi Gunawan(Kanazawa University)、Masahiro Mambo(Kanazawa University)
Set-valued database publication has been studied recently due to its benefit for various applications such as marketing analysis and advertising. Such databases have different characteristics compared to relational databases, where record's owner can be directly associated with his/her values or items. Therefore, publishing raw set-valued database to other parties or to the public may cause individual privacy breach such as the leakage of sensitive information about individual characteristics or individual tendencies when data recipients perform data analysis. To thwart such privacy breach, we propose a data anonymization method which protects individual tendencies while maintaining structure of records in the database. The proposed method employs swapping technique where an individual's items in a record are swapped to items of the other record. Our swapping technique is distinct from existing one yielding much structure distortion. We firstly compute individual tendency for each record and calculate jaccard coefficient between records to measure their similarity. Then we select the record that results in the minimum jaccard coefficient for swapping. Such a strategy allows one to maintain records in the database so as to avoid excessive structure distortion. Since the swapping strategy only moves some items from a record to another one, we can guarantee that the individual tendency can be hidden effectively without causing structure distortion immensely.
近年モデルの自動車に対するInformative CAN Messagesによる攻撃の有効性検証
○高橋 順子(NTTセキュアプラットフォーム研究所)、田中 政志(NTTセキュアプラットフォーム研究所)
本稿では、車載通信プロトコルCAN上での不正メッセージ挿入方法の工夫により、車載モジュール内部の異常発生に対する対策が搭載された近年モデルの自動車においても、既存研究のInformative CAN Messagesのみを用いる攻撃が有効であることを報告する。ハードウェアセキュリティに関する国際会議HOST 2018において、車内部の状態を伝達するため Informative CAN Messagesのみを利用することにより、運転支援機能作動中に不正な加減速を誘発する攻撃手法が提案された。しかし、車載モジュール内部で異常が起きた時に運転支援機能が解除される仕組みが搭載されている場合は、既存手法を単純に適用して攻撃を成功させることが困難であった。そこで本稿では、不正メッセージ挿入方法の工夫により、車載モジュール内部で異常が起きた場合の対策が実装された2017年製の自動車においても、攻撃が有効であることを報告する。具体的には、クルーズコントロールが解除されないように、不正なInformative CAN Messagesのバスへの挿入回数やタイミングの調整を行った。結果、本実験で用いた自動車においても、クルーズコントロール設定速度を上回る/下回る、不正な加速/減速が可能であることを示す。
自動車の車載ネットワークに標準的に用いられているCAN(Controller Area Network)の仕様上,メッセージ内に送信元の情報を含まないためにメッセージの送信元を識別することは難しい.CANメッセージがどのECU (Electronic Control Unit)から送信されているかを識別することができれば,インシデント発生時に不正ECUのみの隔離等,より効果的な対応を取ることが可能になる.本研究では,CANプロトコルの特性より起こるメッセージの送信遅延がECU内のCANコントローラ毎に特徴があることを利用する.トラフィックデータからID間の相関関係を抽出し階層的クラスタリングを行うことで,CANにおける送信元ECUを識別する方式を提案する.これにより,CANに流れるトラフィック情報を受信するだけで送信元識別が可能である.評価には実車のトラフィックデータ使用し,CANコントローラの状態遷移の一つであるバスオフ状態の特性を利用したアクティブな送信元識別の結果を正解データとして提案方式を評価した.その結果,一部のECUに対して有効であることが分かった.
An Efficiently Secure Comparison Scheme Using Homomorphic Encryption
○Lihua Wang(Kobe University)、Takuya Hayashi(NICT)、Tushar Kanti Saha(Jatiya Kabi Kazi Nazrul Islam University)、Yoshinori Aono(NICT)、Takeshi Koshiba(Waseda University)、Shiho Moriai(NICT)
Comparing two integers under encrypted form is useful for privacy preserving data mining, secure auction, and so on. Saha-Koshiba approach [NBiS2017] is practical, and its security is based on the ring-learning with errors (Ring-LWE) assumption. In this study, we propose an enhanced scheme that is more efficient compared with Saha-Koshiba scheme, in detail, the computation cost can be reduced over 1/3.
2A1-3
準同型暗号を用いたプライバシ保護型のクラスタリングプロトコル
◎三本知明(株式会社KDDI総合研究所)、清本晋作(株式会社KDDI総合研究所)、Jacob C. N. Schuldt(産業技術総合研究所)、Nuttapong Attrapadung(産業技術総合研究所)、花岡 悟一郎(産業技術総合研究所)
Three-Party Private Set Operation Protocols Using Polynomials and OPPRF
◎Wenjia Wang(The University of Electro-Communications)、Yoshiki Abe(The University of Electro-Communications)、Mitsugu Iwamoto(The University of Electro-Communications)、Kazuo Ota(The University of Electro-Communications)
A Private Set Operation (PSO) protocol is a secure multi-party computation protocol (MPC) that allows participants to know the result of set operations (union, intersection, difference etc.) of their inputs but learn nothing else. Although PSO protocols have many applications, previous work on PSO protocols mainly focused on the Private Set Intersection (PSI) protocols. One exception would be the work by Blanton and Aguiar, which is inefficient since it consists of consecutive PSO protocols for two sets. On the other hand, a PSI protocol based on polynomials is known to be efficient due to the homomorphic encryption for two parties. However, the computation cost becomes heavier if it is extended for three parties due to the cost of homomorphic encryption. In this work, we propose a new PSO protocol for three parties by combining polynomials with the Oblivious Programmable PRF (OPPRF) proposed by Kolesnikov et al. The proposed scheme is efficient even if three-party cases since OPPRF is constructed by a symmetric key encryption combining with polynomials.
Limitations of Privacy-Preserving for Confidential Data Training by Deep Learning
◎Harry Chandra Tanuwidjaja(KAIST)、Rakyong Choi(KAIST)、Kwangjo Kim(KAIST)
There is a challenging issue when machine learning algorithm needs to access highly confidential data for the training process. In order to address this problem, several privacy-preserving deep learning, including secure multi-party computing and homomorphic encryption in neural network have been developed. There are also several methods to modify the neural network, so that it can be used in privacy-preserving environment. However, there is trade-off between privacy and performance among various approaches. In this paper, we want to discuss state-of-the-art of privacy-preserving deep learning, evaluate all methods, and compare pros and cons of each approach.
2C1-3
Support Vector Machineを用いたプライバシー保護型データ分類方式の改良
◎齋藤吉史(東京工業大学)、尾形わかは(東京工業大学)
Implementing Post-Quantum Key Exchange Protocols on a Smartwatch using Multithreading Approach in JavaScript
◎Ye Yuan(Graduate School of Mathematics, Kyushu University)、Junting Xiao(Graduate School of Mathematics, Kyushu University)、Tsuyoshi Takagi(Department of Mathematical Informatics, The University of Tokyo)
According to our previous research, we found that JavaScript also can deliver high-performance IoT implementation of post-quantum cryptography. In this article, we aim to implement several LWE based key exchange protocols on small devices in parallel using JavaScript. We design the processes of multi-threaded implementation for Ding Key Exchange on a dual-core smartwatch. We use the concurrency and parallelism in HTML5 to improve the implementation performance. We also investigate the JavaScript implementation of other recent post-quantum key exchange protocols Frodo and NewHope, and report the performance comparison. The result shows that our implementation runs about 30% faster compared with single-threaded execution.
自動運転やコネクテッドカーの普及に伴い,車載ネットワークセキュリティの重要性が高まっている.車載ネットワークプロトコルとしてデファクトとなっているController Area Network (CAN)に対する攻撃手法や対策がこれまでに多く提案されてきた.一方で,CANよりも高速・高信頼の通信プロトコルとしてFlexRayが提案され,主に欧州車の走る・曲がる・止まるの基本機能を実現するようになっている.しかし,FlexRayのセキュリティに関する先行研究は非常に少なく,FlexRayに対する実際の脅威は明らかになっていない.FlexRayのセキュリティ対策を検討する上でFlexRayに対する脅威の理解は必要不可欠である.そこで本稿では,実環境におけるFlexRayの脆弱性を明らかにする.具体的には,攻撃者が正常なECUになりすまして,不正なFlexRayフレームを送信可能となる条件を示す.実際に,不正なFlexRayフレームの送信により,特定の車両に対してステアリング,ブレーキ,加速の不正制御を引き起こせることを確認した.さらに得られた実験結果をもとに,FlexRayに対するなりすまし攻撃への対策手法を考察する.
Open-Source Software in Your Car - What Can Go Wrong?
○Dennis Kengo Oka(Synopsys)、Camille Gay(Synopsys)
Open-source software is already in your car; however, have you considered what the security risks are? Obviously, there are several benefits with open-source software that allows innovation while reducing costs for non-competitive technologies. However, with more than 100 million lines of code in a modern vehicle and a complex supply chain involving multiple software suppliers it is imperative to understand what can go wrong. To get a better understanding of actual risks, we performed practical evaluation based on software composition analysis of 14 automotive software packages (in-vehicle infotainment software and mobile apps) with the focus on analyzing open-source software risks. All 14 software contain open-source components with critical vulnerabilities. We present the results of the analysis identifying vulnerabilities in popular components such as zlib, libpng, and curl. Finally, we discuss best practices for managing open-source risk across the automotive supply chain.
あらゆるモノがインターネットに接続するIoT (Internet of Things)社会が本格的に到来しようとしている.これにより,多様で有益なサービスがインターネットを介して受けられる一方, インターネット上で攻撃の標的となる機器が増加している問題は無視できない.こうした問題への対処には,インターネット上で発生した攻撃動向を迅速に提供する,ダークネット観測システムの活用が知られている.このシステムは,未使用のIPアドレス帯で攻撃パケットを観測・分析し,ネットワーク管理者及び一般ユーザ向けに,セキュリティ対策情報を提供する.本稿では,日々複雑化するダークネット上の攻撃パケットを新たな観点から解析するため,近年注目を集める位相的データ解析 (TDA: Topological Data Analysis)の1手法,TDA Mapperを解析に利用する.評価実験では,実際のダークネットによって観測された攻撃パケットに位相的データ解析を適用することで,攻撃パケットの可視化を行った.可視化された攻撃パケットの全体像や攻撃パケット間の関係を抽出した例を考察し,提案手法の有効性を報告する.
Verifiable Sequential Work with Trusted Generator
◎Xiangyu Su(Tokyo Institute of Technology)、Mario Larangeira(IOHK, Tokyo Institute of Technology)、Keisuke Tanaka(Tokyo Institute of Technology)
Verifiable delay functions (VDF) proposed by Boneh et al. (Crypto'18) has several applications on blockchain based systems, random beacons and etc. Although the highly practical applications, less than a handful of constructions are known due to the need of efficient public verifiability. In the best of our knowledge, the only two constructions are from Pietrzak (EPRINT' 18) and Wesolowski (EPRINT' 18).
In this paper, we define a VDF variant, which we denote by verifiable sequential work (VSW). The main idea is to take the sequential computations in VDF to reduce the difficulty of a hard problem to a moderated hard level.
We construct a weakened VSW which needs a trusted third-party to run the generation phase: the VSW with trusted generator (VSWTG). The construction achieves a simple, one message and one group exponentiation publicly verifiable VSWTG. It is a more computational efficient verification procedure than the known VDF verification constructions. We regard the need for a trusted party as a necessary trade-off, however, we conjecture our variant may be easier to find other candidate constructions than the VDF definition.
Finally, we formalize the idea of the Rivest-Shamir-Wagner (RSW) time-lock puzzle to a new primitive that we call trapdoor iterated sequential functions (TDISF) and investigate on its possible candidates.
Deep Learning が画像認識の分野で人間に近い性能を達成して以来,多くの手法が提案され,様々な分野で Deep Learning を用いた手法が利用されている.生体認証においても Deep Learning を用いた手法が数多く提案されているが,必ずしも全ての生体認証の問題において利用されているわけではない.過去6年の生体認証に関する研究動向から Deep Learning と生体認証の関係性を示す.
近年、センサに対する意図的な取得データを改ざんするなどの脅威に関するセキュリティを扱う計測セキュリティの研究が盛んとなっている。攻撃者がセンサに対して攻撃を行う場合にセンサの動作情報を取得することが考えられる。セキュリティの分野では非接触な情報取得手法として電磁波による情報漏洩が検討されている。センサからの放射電磁波の強度はEMCの規格を満たしているが、微弱な放射電磁波であっても時間変化を観測することにより内部動作の推定できる可能性がある。放射電磁波による動作タイミングの取得が可能な場合、超音波より高速に伝搬することによる攻撃の容易化や、超音波の届かない範囲での攻撃による検知困難化によりセキュリティのリスクが高まると考えられる。本発表ではTime of Flight方式の距離センサに対して放射電磁波からなりすまし攻撃に必要な動作タイミング情報が抽出可能であるかを検討する。
Security Analysis of DST40 Automobile Protocol
○Ei Mon Cho(AIST)、Hirotaka Yoshida(AIST)、Yuhei Watanabe(AIST)、Hideki Yamamoto(Sumitomo Electric Industries, Ltd.)、Akira Mori(AIST)
Passive Keyless Entry and Start (PKES) system are widely used in smart car systems allowing unlock and start a car within a range of a paired key fob; no user interaction is required. It is one of the famous IoT application in the automobile sector. This work presents DST 40 cipher(40 bit) security protocol between a car and key bob. We will discuss that these systems to be vulnerable to relay attacks or time-memory trade-off attacks (TMTO). Our research aims to resist a modernized PKES system to possible attacks.
UDS (Unified Diagnostic Services, ISO 14229-1) の規格としてAuthentication Serviceが規定された。本稿では、その実装方法として、SHE (Secure Hardware Extension) を活用した共通鍵ベースの認証手法を提案する。また、本手法における事前共有鍵の運用方法について考察する。
Authentication Service is newly defined in UDS, ISO 14229-1. We propose a symmetric key based authentication scheme using SHE. And also we discuss about an initial key distribution of this scheme.
Electronic Control Unit(ECU)に対する強制駆動やリプログラミングなどの重要な診断機能を保護するために,ISO/DIS 14229-1準拠のAuthentication Service $29(以下,サービス$29)の拡がりが期待されている.ここで,もしサービス$29が悪用されると,未公認の診断ツールがController Area Network(CAN)に接続されたり,想定外の診断作業が行われてしまう懸念がある.そこで本稿では,ECUの診断において,作業員を認証し,その属性と作業内容を鑑みた認可データを発行・検証する仕組みを提案する.これは,ECU側でサービス$29における認証用の共通鍵,もしくは公開鍵証明書を1つ管理しておき,認証と認可データの完全性を検証する方式である.車両単位で発行される1つの鍵で,従来からのセキュリティアクセス・レベル(以下,認可レベル)の制御も担えるようになり,タクトタイムの厳しい生産ラインでの鍵書込みの実現を目指す.
Dice Rolls for Online Games using Blockchain with Provable Properties
寺西 勇(NEC)、○佐古 和恵(NEC)
The paper proposes a protocol to perform fair dice rolls in online games with help of public blockchain. Typically the outcome of dice rolls in online games are generated solely by game servers, making players suspicious about its fairness. Our protocol exploits a pseudorandom number generator for the outcome of dice rolls, where its random seed is jointly generated by the server and player(s). The choices of random seed chosen by the server and players are cryptographically committed on a public blockchain to prevent deviation from honest execution of the protocol. The players can verify the correctness of the outcome of dice rolls. If there is a dispute, a judge can determine who is to blame. We further prove the protocol satisfies desirable properties.
A Fair Anonymous Auction Scheme Utilizing Trusted Hardware and Blockchain
◎Batnyam Enkhtaivan(NEC Corporation)、Takao Takenouchi(NEC Corporation)、Kazue Sako(NEC Corporation)
In this paper, we propose an anonymous English auction scheme that utilizes trusted hardware and blockchain for the enhancement of the privacy of the participants and the correctness of the auction. We use group signature to provide anonymity to the bidders. The hardware-based trusted execution environment (TEE) is utilized to ensure that the group manager de-anonymizes a group member only once for deciding the winner. To combine with the group signature, blockchain transactions are modified to contain group signature instead of digital signature.
本稿で,我々は,適応的に安全な鍵失効機能付きIDベース暗号(RIBE)のより効率的な構成法を提案する.現在知られている方式で最も効率が良いものとして,Watanabeらの方式と高安の方式がある.これらの方式は,ほぼ同じ効率だが,高安の方式には二つの長所がある.Watanabeらの方式の安全性は,標準的でないSXDH仮定の亜種に基づいているが,高安の方式の安全性は,標準的なk-linear仮定に基づいている.さらに,高安の方式は,Watanabeらの方式より帰着ロスが小さい.これらの差が出た要因として,高安は,RIBEの安全性証明においてdual system encryptionを用いたことが挙げられる.そのため,本稿で,Watanabeらの方式の安全性証明を,高安と同様の方法で行う.そして,技術的な理由で,暗号文・更新鍵・復号鍵サイズが大きくなるが,Watanabeらの方式は,k-linear仮定に基づいて高安の方式と同等の帰着ロスで安全であることを示す.さらに,高安の証明法をより精密に解析することで,両方式ともにマスター公開鍵サイズを削減できることを示す.
Another Look at One-More Discrete Logarithm Problem in Generic Model
○Bagus Santoso(University of Electro-Communications)、Kazuo Ohta(University of Electro-Communications)
“One-more” problems have been used widely for proving the security of various cryptographic schemes. However, the existing works have claimed that for computational problems with random self-reducibility such as discrete logarithm problem and RSA, the following black-box separation holds: it is impossible for any black-box reduction to prove the hardness of a “one-more” problem based on the hardness of its “regular” one if the regular problem itself is hard. Hence, it has been believed that it is unlikely that we can validate the hardness of “one-more” problems even though we can guarantee the hardness of their “regular” ones.
In this paper, we provide a proof that the hardness of one-more discrete logarithm problem in the generic model can be guaranteed by the hardness of the regular discrete logarithm problem in the generic model, under a certain assumption. We show that the assumption we use is reasonable in the real world based on the work by Yun at Eurocrypt ’15 on the hardness of “multiple” discrete logarithm problem. The center of our technique is a reduction algorithm, which might be interesting in its own right since it can bypass the existing black-box separations using some subtlety which seems overlooked in the existing works so far.
Fault Injection, Simple Power Analysis, and Power Glitch Attacks against FPGA-implemented Xoroshiro128+
◎Nakjun Choi(KAIST)、Jeeun Lee(KAIST)、Kwangjo Kim(KAIST)
Random Number Generators (RNGs) are playing an important role in providing a uniqueness of many protocols in various fields such as IoT, Artificial Intelligence, Database, and Information Security in ICT systems. However, since most of the RNGs are implemented in a physical chip, they are always vulnerable to the risk of side channel attack such as timing attack and fault injection attack, etc. In this paper, we attempt to execute side channel attacks on Xoroshiro128+ which is a Pseudo-Random Number Generator (PRNG) designed by Vigna and Blackman. Using the Xoroshiro128+ source code, we implemented this PRNG over the Field Programmable Gate Array (FPGA). We also verify the security of Xoroshiro128+ and suggest countermeasures against side channel attacks using ChipWhisperer-Pro
BPT: How to Establish Trusted Vehicular Fog Computing Service on Rural Area
◎Favian Dewanta(Kanazawa University)、Masahiro Mambo(Kanazawa University)
Passing through a rural area with limited network infrastructure may disrupt fog computing support for several vehicles. As a result, some applications on vehicles may turn off and bother the performance of the vehicular systems. In order to escape from this kind of situation, vehicular fog computing is discussed in the recent times as the alternative of fog computing support while passing blank spot of network infrastructure. However, without mutual trust, it is not feasible to establish trusted vehicular fog computing service among vehicles. To deal with this situation, this paper proposes a method called Bidding-price and Payoff-based Transaction (BPT) for vehicular fog computing service on rural areas. This method comprises of bidding-price based mutual trust establishment between vehicle client and vehicle-as-a-infrastructure of fog computing and also issuing payoff based on transaction evaluation. By applying this method, trusted transaction between two vehicles can be achieved without the direct assistance of any trusted third party as the validating entity. As a result, this method may attract vehicles with rich computational resources to participate in sharing their resources for helping vehicles that possess limited computational resources.
A Method to Estimate the Time Duration of Potential Attacks in a Cyber Physical System
◎Taniya Singh(NEC Corporation)、Kazuya Kakizaki(NEC Corporation)、Masafumi Watanabe(NEC Corporation)、Hirofumi Ueda(NEC Corporation)
Security risk assessment of cyber physical systems (CPS) is of utmost importance due to the increasing number of cyber-attacks on such systems. In one possible assessment approach, potential attack scenarios from the assessment are helpful for plant operators in order to take the appropriate counter measures to protect the CPS from damage. Attack duration is crucial for the plant operator so that he can decide which attacks to handle urgently. However, the existing research does not provide the time duration of an attack until damage. To solve this problem, we propose a method to calculate the time duration of an attack. In addition, we have used data from an existing water treatment testbed for evaluation. Comparison between the time estimated by our method and the manually calculated time from the data of the testbed shows the efficacy of our method.
2F3-2
脆弱性データベース National Vulnerability Database (NVD)の現状調査
○小池 竜一(東芝デバイス&ストレージ)、坪田 忠直(東芝デバイス&ストレージ)、松井 伸郎(東芝デバイス&ストレージ)
Adding Authenticity into Tree-based Group Key Agreement by Public Ledger
◎Seongho Han(KAIST)、Rakyong Choi(KAIST)、Kwangjo Kim(KAIST)
With the development of communication technologies and embedded devices, the importance of group communication among various parties is growing. Group key agreement (GKA) is playing an important role in sharing critical information in a group. GKA protocol is divided into four categories: tree-based, star-based, link-based, and ring-based. Tree-based GKA has greater flexibility in membership management and is easier to achieve decentralization than other GKA protocols. Tree-based GKA protocols, which are based on Diffie-Hellman Key Exchange (DHKE), become vulnerable to active attacks since DHKE does not check the identity of the user. To solve the problem, authenticated key exchange (AKE) protocols were suggested. Most AKE papers solve the authentication problem based on an existence of trusted third party (TTP). However, relying on TTP has a risk of a single point-of-failure which paralyzes the protocols. In this paper, we suggest two protocols to add authenticity into a typical tree-based GKA protocol TGDH by public ledger: PLAKE and dPLAKE. PLAKE uses Proof of Work (PoW)-based public ledger and dPLAKE uses Delegated Proof of Stake (DPoS)-based public ledger not to depend on TTP for authentication. We discuss the security of PLAKE and dPLAKE.
2G3-4
Decentralizing the Role of Root Authority in CP-ABE by the Help of Blockchain
◎Dongyeon Hong(KAIST)、Kwangjo Kim(KAIST)
Attribute-based encryption (ABE) is classified as an extended public key cryptosystem which replaces the public key of a user with his/her attributes in order to reduce the management overhead of their public keys. Another advantage of ABE is to handle monotonic access control with attributes. Nevertheless, ABE has some disadvantages like a fully trustness on the central component. In this paper, we propose a novel way of Ciphertext-Policy Attribute-based encryption (CP-ABE) by applying features of the decentralized ledger in the blockchain to overcome the current disadvantages of CP-ABE. We provide the role distribution of the central component to achieve a more reliable system and prevent a single point of failure from strong adversaries.
2G3-5
Generic Analysis of E-voting Protocols by Simplified Blockchain
◎Seunggeun Baek(KAIST)、Nabi Lee(KAIST)、Kwangjo Kim(KAIST)
Upon blockchain technology gains popularity, lots of attempts have been made to adopt this into all ICT systems. One notable example is to apply blockchain to e-voting protocols. However, careful analysis on the requirements and side effects should be scrutinized before the adoption of the new technology. We analyze whether blockchain-based e-voting protocols still satisfy their security requirements, by deriving generic transformations from blockchain-based e-voting protocols to classical e-voting protocols, while preserving the knowledge set for the public. Compared to classical e-voting protocols, we claim that blockchain-based e-voting protocols have generically weaker confidentiality and generically stronger universal verifiability, judged by the point of our generic analysis.
Towards Multi-hop extension of PRE+
◎Lwin San(Waseda University)、Takeshi Koshiba(Waseda University)、EiMon Cho(National Institude of Advanced Indrustrial Science and Technology)
Blaze et al. introduced the concept of proxy re-encryption (PRE) in 1998. It allows a
semi-trusted proxy to transform a ciphertext encrypted under one key into another ciphertext of the
same plaintext under another key, without revealing any information of the plaintext.PRE has found
many applications, such as in encrypted e-mail forwarding [8], distributed secure le systems [1,2],
multicast [10]cloud computation etc. However, all the PRE schemes until now require the delegator (or
the delegator and the delegatee cooperatively) to generate the re-encryption keys. In 2013, X. A. Wang
et al.[17] observe that this is not the only way to generate the re-encryption keys, the encrypter also has
the ability to generate re-encryption keys. Based on this observation, they introduce a new primitive:
PRE+, which is almost the same as the traditional PRE except the re-encryption keys generated by
the encrypter. Interestingly, this PRE+ can be viewed as the dual of the traditional PRE. Compared
with PRE, PRE+ can easily achieve the non-transferable property and message-level based negrained
delegation, while these two properties are very desirable in practical applications. In this paper, we
extended to double-hop scheme based on their single-hop schem by giving the denition and security
model for PRE+.
Experimental discussion on the distinguishing based attack against HFEv-
○Shuhei Nakamura(College of Industrial Technology, Nihon University)、Yacheng Wang(The Department of Mathematical Informatics, University of Tokyo)、Yasuhiko Ikematsu(The Department of Mathematical Informatics, University of Tokyo)
At PQCrypto 2018, Ding et al. proposed a new attack called distinguishing based attack against the multivariate signature scheme HFEv-, that reduces HFEv- to HFE-. This attack distinguishes whether the vector space generated by random linear polynomials, that are added to the public key, intersects with the vinegar space by looking at the behavior of the step degrees of the $F_4$ Groebner basis algorithm. When the vector space intersects with the vinegar space, we can construct a linear polynomial in the vinegar space. And the public key plus this linear polynomial behaves similarly to HFEv- with one less vinegar variables. By repeatedly finding such a linear polynomial, we can remove the effect of the vinegar variant.
The $F_4$ Groebner basis algorithm using more linear polynomials increases the probability of intersection with the vinegar space and reduces the complexity. However, when the number of added linear equations exceeds a certain value, it becomes impossible to distinguish whether having the intersection with the vinegar space. Ding et al. provided several formulas for estimating this optimal value in their paper. In this paper, we experimentally investigate the gap between practical and estimated value of this optimal value.
Visual Cryptograms of Random Grids for Color Image
○Sabyasachi Dutta(Kyushu University)、Md Kutubuddin Sardar(University of Calcutta)、Avishek Adhikari(University of Calcutta)、Kouichi Sakurai(Kyushu University)
Random Grids are used for e?cient visual secret sharing. The e?ciency lie in the fact that no codebook construction is needed and size of the share images equal the size of the secret image. However, it makes the reconstruction of the secret image probabilistic. A lot of research has been carried out to construct visual cryptograms of random grids for black and white images. Although some papers [1, 5, 6] have given constructions and shown some experimental results on constructing random grids for color images, their works do not address an explicit and concrete theoretical development and background of the model. We give a concrete de?nition of visual cryptograms of random grids for color images in the Same-Color model and give constructions for general access structures.
A Classification Model For Visual Homograph Attack
◎Tran Phuong Thao(KDDI Research, Inc.)、Yukiko Sawaya(KDDI Research, Inc.)、Nguyen Son Hoang Quoc(KDDI Research, Inc.)、Akira Yamada(KDDI Research, Inc.)、Kazumasa Omote(Tsukuba University)、Ayumu Kubota(KDDI Research, Inc.)
Visual homograph attack is a way that the attackers deceive victims about what domain they are communicating with by exploiting the fact that many characters look alike. The attack is growing into a serious problem and raising broad attention in reality when recently many brand domains have been attacked such as apple.com (Apple Inc.), lloydsbank.co.uk (Lloyds Bank), adobe.com (Adobe Systems Incorporated), etc. Therefore, how to detect visual homograph becomes a hot topic both in industry and research community. Several existing tools and papers have been proposed to find some homographs of a given domain based on different subsets of certain look-alike characters, or based on an analysis on the registered International Domain Name (IDN) database. However, we still lack a scalable and systematic approach that can detect sufficient homographs registered by attackers with a high accuracy and low false positive rate. In this paper, we construct a classification model to detect homographs and potential homographs registered by attackers using machine learning on feasible and novel features such as visual similarity on each character and some selected information from Whois. The implementation results show that our approach can bring up to 95.90% accuracy with merely 3.27% false positive rate. Furthermore, we also make an empirical analysis on the collected homographs and found some interesting statistics along with concrete misbehaviours and purposes of the attackers.
Secure Offline Payments in Bitcoin
◎高橋 大成(情報セキュリティ大学院大学)、大塚 玲(情報セキュリティ大学院大学)
Double-spending attacks on fast payments is one of the fatal architectural problems in Cryptocurrencies. Dmitrienko et al. proposed an offline fast payment scheme that relies on tamper-proof wallets pro- duced by trustworthy manufacturers. With the wallets, payee can imme- diately trust the transactions generated by the wallets without waiting for their registration to the blockchain. Secure coin-preloading to the wallet is important, while illegal coin-preloading can cause over/double- spending by the trusted wallets. For this, they proposed an interesting protocol that makes use of a fragment of the main blockchain to prove to the wallets the legitimacy of preloaded coins. One drawback is that, in proving that the fragment stems from the mainchain, their protocol requires a trusted online time-stamp server so that the wallets can verify the timestamps to see if the blocks in the fragment is mined with suffi- ciently large amount of computing resources. In order to eliminate such an online trustee, in this paper we took the opposite approach that the payee (not the wallets) verifies the legitimacy of preloaded coins at the time of offline payment. As a consequence, our result shows that, with light-weight tamper-proof wallets, completely decentralized offline pay- ment is possible with only a slight modification to the existing Bitcoin network.
DHL: Dynamic Key Exchange from Homomorphic Encryption based on Lattice
◎Rakyong Choi(School of Computing, KAIST)、Kwangjo Kim(School of Computing, KAIST)
Group key exchange protocol produces a common secret key between n parties for secure (group) communication in insecure channel over the internet. In ProvSec Workshop 2018, Choi and Kim designed a novel multi-party key exchange protocol with homomorphic encryption in static setting. In this paper, we discuss the limitation of their scheme and extend this protocol to dynamic setting for managing group membership issue in terms of graph theory. We use the similar graph structure from Kim et al.'s key management solution called Tree-based Group Diffie-Hellman (TGDH,) for necessary algorithms providing dynamic key exchange from homomorphic encryption based on lattice problems.
In an asymmetric fingerprinting, a cryptographic protocol is executed between a seller and buyer in order not to cause a dispute when a pirated copy is found. However, the tracing protocol has not been studied from the security point of view though the collusion resistance is considered by employing a collusion secure fingerprinting code. In this paper, we propose a secure tracing protocol jointly executed by a seller and a delegated server to reduce burdens at a trusted center. Our main idea is to delegate authority to a server so that the center is required to operate only at the initialization phase in the system. When a pirated copy is found, a seller calculates a level of suspicion for each user's codeword in an encrypted domain and sends its ciphertext to the server. The server returns identities of illegal users by checking the ciphertexts if they satisfy three conditions. The information leakage from the server can be managed at the restriction of response from the server to check the maliciousness of the queries.
On the security of Cayley hash functions based on LPS-type Ramanujan graphs
◎Hyungrok Jo(The University of Tokyo)、Yoshinori Yamasaki(Ehime University)
In 2009, Charles, Goren, and Lauter suggest the cryptographic hash functions based on the explicit Ramanujan graphs of Lubotzky et al.(LPS for short) and Pizer. LPS-based Cayley hash functions has been crytpanalyzed immediately by Petit et al. However, Pizer-based hash functions has survived and it developed in the era of Post-Quantum Cryptography (PQC for short), now it called isogeny-based cryptography is one of the main candidates for PQC standardization which is announced by NIST (National Institute of Standards and Technology).
In this paper, we focus on Cayley hash functions based on LPS-type Ramanujan graphs, which is a generalized construction from LPS's Ramanujan graphs. We analyze the security of Cayley hash functions based on LPS-type Ramanujan graphs against a lifting attack for finding their collisions and we also suggest the possible ways to improve its scheme and explicit constructions of graphs.
3B1-2
Proposals of Message-Dependent Transformation and Its Application For Augmenting MVPKC and CBPKC
○Kasahara Masao(Research Institute for Science and Engineering, Waseda University)
In this paper we present a message-dependent transformation scheme, K(I)Scheme. Based on K(I)Scheme, we present a new class of augmented MVPKC(Multi-Variate PKC), referred to as K(I)Sch・MVPKC. We show that K(I)Sch・MVPKC would be secure against the various attacks such as LLL attack. Based on K(I)Scheme, we also present a new class of augmented CBPKC(Code Base PKC), K(I)Sch・CBPKC. Both K(I)Sch・MVPKC and K(I)Sch・CBPKC enable the coding rate of exactly 1.0.
3B1-3
Experimental Analysis for Linear Algebraic Attack on a Variant of Indeterminate Equation Public-Key Cryptosystems
○Yasuhiko Ikematsu(The University of Tokyo)、Yuntao Wang(The University of Tokyo)、Koichiro Akiyama(Corporate R&D Center, Toshiba Corporation)、Tsuyoshi Takagi(The University of Tokyo)
Akiyama et al. proposed some encryption schemes based on the problem of finding a solution to indeterminate equations over a finite ring until now. One of them uses the finite ring F_{q}[t]/(t^n-1) as a base ring. Its underlying hard problem can be reduced to a bounded distance decoding (BDD) problem and there are several attacks using its lattice structure.
In this paper, we consider the scheme with the base ring F_{q}[t]/(t^{n}+1) instead of F_{q}[t]/(t^n-1). Moreover, we experimentally study the linear algebraic attack using its linear algebraic structure, via applying lattice methods on the corresponding BDD problem.
インターネットはIPアドレスの枯渇等の問題からIP Version 4(IPv4)からIP Version 6(IPv6)に移りつつある。現在では互換性のない両者を同時に利用可能なIPv4/IPv6の混在環境(デュアルスタック)での提供が広くされているが、いずれIPv6だけの環境(IPv6 Single Stack)へと移行していく。インターネット上で稼働するOSやアプリケーションはすべてIPv6へと移行がされて行かなければならない。一方で、IPv6 Single Stackで多くのアプリケーションが正確に動作することへの疑念が残る。アプリケーション製作者が意図的にIPv4のみ対応を明言しているアプリは仕様通りと考えられるが、多くのアプリはIPv4、IPv6の対応状況を明記していないため、その動作が不具合なのか仕様どおりなのかが不明である。このような動作が不明な状況は接続の制御がうまく行っておらず、サービス可用性の侵害や悪意のある第3者の介在など未知の脅威の発生につながりかねないと懸念する。本研究では今後のIPv6時代に対応し得るAndroidアプリケーション開発及び改善等に役立てるため、なぜ正しくアプリケーションが動作しないのかをOSやライブラリそしてアプリケーションの視点からIPv6 Single Stack対応を調査そして分析した。
Revisiting Threshold Secret Sharing Schemes Using Exclusive-OR Operations from the point of view of Fine-Grained Cryptography
○Sabyasachi Dutta(Kyushu University)、Kouichi Sakurai(Kyushu University)
Shamir secret sharing scheme provides an efficient method for encoding a secret of arbitrary length among any n players such that for a threshold parameter t, the knowledge of any (t-1) shares does not reveal any information about the secret but any choice of t shares fully reveals the secret. However, Shamir secret sharing scheme and also most of the classical schemes require either linear algebraic computation over finite fields or XOR-operation e.g. [Kurihara et al. ISC'08] over binary field for implementation. Neither of these operations belong to the complexity class AC0 which was conjectured as possibly the lowest complexity class in which secret sharing schemes can be implemented. Recent advancements [Bogdanov et al. in CRYPTO'16] show the possibility of existence of such schemes. The research along this direction is still in its early stage and mostly the results are of great theoretical importance. We pose the question of practicality of using such schemes. Secret sharing schemes based on linear algebraic/ XOR computations are well implemented and are quite practical (almost to the point of optimality to achieve information theoretic security). We focus/ discuss circuit complexity of Kurihara et al.'s design (which is in NC1) and compare the two approaches from the point of view of practical measure.
A New Family of Isomorphism of Polynomials and Its Applications to Public Key Encryption Scheme
○Bagus Santoso(電気通信大学)
In this paper, we propose a new family of computational problems based on a generalization of Isomorphism of Polynomials with Two Secrets (IP2S) problem. Our generalized problem is as hard as the original IP2S problem and provides more freedom on setting the structure and the size of the solutions. Since IP2S problem is supposed to be hard against quantum adversaries, our generalized problem is also supposed to be hard against quantum adversaries.
Furthermore, we develop several new computational problems derived from the generalized problem and based on these derived problems, we propose a new paradigm to construct public key cryptographic scheme and identification scheme by making use the commutative property of circulant matrices. The robustness of our proposed problems allows us to use them with circulant matrices without degrading the hardness of the problems too much, in contrast to the original IP2S problem which becomes easy when it is used with circulant matrices.
ICICS 2015で安田らは多変数多項式ベース暗号方式SRPを提案した。暗号方式SRPは、多変数多項式ベース暗号方式Squareを、多変数多項式ベース署名方式Rainbowを暗号方式に応用したRainbow-Plus(RP)構造と組み合わせたものである。しかし、暗号方式SRPは、SAC 2017でPerlnerらが提案したMin-Q-Rank攻撃によって破られた。PQCrypto 2018で池松らは多変数多項式べース暗号HFEをRP構造と組み合わせた暗号方式HFERPを提案した。単体の暗号方式HFEはMin-Q-Rankによって破られているにも関わらず、暗号方式HFERPは実験でMin-Q-Rank攻撃に対して安全であると示された。本研究は、RP構造を暗号方式の安全性強化手法とみなし、符号ベース暗号方式McElieceとRP構造を組み合わせた新たな暗号方式McEliece-RPを提案した。提案方式に対してグレブナー基底攻撃を行い、攻撃時間とグレブナー基底の計算におけるDegree of Regularityを計測し、グレブナー基底攻撃に対する安全性を評価した。
3B2-4
Parallel Implementation and Comparison of Lattice-based Digital Signature Schemes using JavaScript
○Junting Xiao(Graduate School of Mathematics, Kyushu University)、Ye Yuan(Graduate School of Mathematics, Kyushu University)、Tsuyoshi Takagi(Department of Mathematical Informatics, The University of Tokyo)
The final release of HTML5 led the development of web applications to a new stage. Not only personal computers or Smart phones, even IoT devices can access to web applications which are based on HTML5. A secure digital signature scheme is indispensable to protect the communications. National Institute of Standards and Technology (NIST) had concluded the collection of quantum-resistant public-key cryptography algorithms since November 2017. As one of the submissions, qTESLA digital signature scheme is a kind of lattice-based public-key cryptosystem proposed by Nina Bindel et al. Its security is based on the decisional ring learning with errors (Ring-LWE) problem. However, most lattice-based cryptosystems are computationally expensive and hence practical implementation becomes a crucial issue. Web Workers allows a parallel execution that some script operations can be accomplished in background threads rather than the main thread of a web application from the specifications of HTML5. The cross-platform language JavaScript is used to complete this operation. In this paper, we propose a parallel implementation of two lattice-based digital signature schemes, qTESLA and well-known BLISS by Web Workers and compare the performances on mainstream browsers.
3B2-5
Practical Attack on RaCoSS-R
○Keita Xagawa(NTT Secure Platform Laboratories)
RaCoSS is a signature scheme based on the syndrome decoding problem over the random linear code and proposed by Fukushima, Roy, Xu, Kiyomoto, Morozov, and Takagi. This scheme is cryptanalyzed Bernstein, H?lsing, Lange, and Panny (pqc-forum on 23 Dec. 2017). Roy, Morozov, Fukushima, Kiyomoto, and Takagi recently gave a patch and call the patched scheme as RaCoSS-R (ISEC Conf. on 25 Jul. 2018). This short note describes how to break RaCoSS-R by modifying the forgery attack against RaCoSS.
Fuzzing the filesystem layer of IoT devices over USB
Camille Gay(Synopsys)、○Dennis Kengo Oka(Synopsys)
We introduce how we developed a tool to fuzz filesystems over USB, and how we used it to uncover bugs in Windows, Android, and some Linux distributions.
It is very common for IoT devices to load and save files from a removable memory device. For example, infotainment systems in cars can load media files from a USB drive, and some medical devices save logs in external SD cards. The filesystem layer might contain critical bugs. Using an embedded Linux Board (BeagleBone Black), we emulate a USB drive, and alter some bytes randomly after a few memory reads have occurred. Using this approach, we were able to uncover various bugs in filesystem parsers (Exfat, NTFS, etc.) of different Operating Systems, usually at kernel level. In the worst case, such bugs could enable attackers to abuse USB/SD ports to run arbitrary code on IoT devices. We conclude that filesystem fuzzing should be part of the security evaluation of IoT devices.
On the Power of Security Reduction in the Quantum-accessible Random Oracle Model
◎Jeeun Lee(School of Computing, KAIST)、Kwangjo Kim(School of Computing, KAIST)
The advent of quantum computers and their algorithms has opened the era of post-quantum cryptography. Accordingly, new security proof models and proof techniques in a quantum setting need to be settled. As the classical random oracle (CRO) model is widely accepted as an efficient security proof tool, quantum-accessible random oracle (QaRO) model has been suggested by allowing the adversary's access to quantum computation. In this paper, we examine the features of CRO model and how they are applied to the QaRO model. Compared to the classical case, QaRO model has advantages such as quantum parallelism, but also weaknesses due to no-cloning theorem and collapse during measurement, e.g. adaptive programmability, rewinding, extractability, challenge injection, and oracle simulation. We review and compare the attempts to extend classical features to quantum one and how they overcome weaknesses, by introducing new quantum proof techniques.
Card-based cryptographic protocols for several Boolean functions using private operations
○Yoshifumi Manabe(Kogakuin University)、Hibiki Ono(Kogakuin University)
This paper shows new card-based cryptographic protocols using private operations. Private operations were shown to be powerful primitives to calculate logical functions in card-based cryptographic protocols. This paper shows efficient computation of three-input Boolean functions using private operations. The number of cards used in the protocols are rescued than the ones by Nishida, Hayashi, Mizuki, Sone(2015).
Elliptic curves are widely used in both Encryption Schemes and Signature protocols because of its obvious advantages. It can preserve security of system with shorter key and thus using less memory space. For this reason, Elliptic curves are always used in Embedded Systems recently. In Elliptic curves Encryption Schemes and Signature protocols based on DLP problem, the security and efficiency of scale multiplication Q= kP,P∈E_(F_q ) is of great importance.
It is naive to expand powering ladder proposed by prior researches, Montgomery Ladder or Joye’s Ladder, to Elliptic curves scale multiplication by just combining addition formula of Elliptic curves. It doesn’t take account of Side Channel Attack (SCA) which is well studied recently. Combing complete addition formula of Elliptic curves with prior powering ladder can protect from SCA but with low efficiency. In this paper, we proposed new powering ladder improving and adjusting prior powering ladder to Elliptic curves scale multiplication to resist SCA. Moreover, we combine 2-bit scanning with our powering ladder to improve efficiency.
We evaluated our powering ladder from computation cost and memory cost. And do analysis about its security. It shows that our powering ladder resist SCA with high performance.
最短ベクトル問題やLearning with Errors (LWE)問題などの格子問題の計算量困難性を安全性の根拠に持つ格子暗号は,量子計算機でも容易に解読できないポスト量子暗号候補の一つとして注目されている.本稿では,LWEにおける剰余パラメータを変更するModulus Switchingを用いたLWE問題の求解法を紹介すると共に,理論と実験の両面からその求解法を解析する.特に,LWE問題の亜種であるLearning with Rounding (LWR)問題に対する求解実験結果とModulus Switchingによる効果を報告する.さらに,2017年11月末に米国標準技術研究所NISTに提出されたLWE/LWRベースのポスト量子暗号候補方式の安全性に対し,Modulus Switchingによる求解法がどう影響するのか議論する.
4B1-2
Sample-Time Trade-off for the Arora-Ge Attack on Binary-Error LWE
◎Sun Chao(Kyoto University)、Mehdi Tibouchi(NTT Secure Platform Laboratories)、Masayuki Abe(NTT Secure Platform Laboratories)
Binary-Error LWE is the particular case of the learning with errors problem in which errors are chosen uniformly in {0,1}. It has various cryptographic applications, and in particular, has been used to construct
efficient encryption schemes for use in constrained devices.
Arora and Ge showed that the problem can be solved in polynomial time given a number of samples quadratic in the dimension n, but is known to be hard given only slightly more than n samples. It can also be solved in slightly subexponential time given a slightly superlinear number of samples, by applying Gr?bner basis techniques to the system arising from Arora and Ge's approach.
In this paper, we examine more generally how the hardness of the problem varies with the number of available samples, using a simpler (but asymptotically equivalent) variant of the Gr?bner basis algorithm. In
particular, under standard heuristics on the Arora-Ge polynomial system, we show that, for any ε>0, Binary-Error LWE can be solved in polynomial time n^O(1/ε) given εn^2 samples. Similarly, it can be solved in subexponential time 2^{\tilde O(n^{1-α})} given n^{1+α} samples, for 0<α<1. It is also easy to derive concrete complexity estimates for any given set of parameters, so as to evaluate the security of cryptographic schemes based on Binary-Error LWE.
Current Status and Challenges of Enhancing Trust Management on IT-enabled Supply Chain
○Haibo Zhang(Kyushu University)、Toru Nakamura(Advanced Telecommunications Research Institute International)、Kouichi Sakurai(Kyushu University and ATR)
Diversified goods and complicated customers’ demands require the supply chain to collaborate with information technology, called IT-enabled supply chain, for solving some stubborn physical delivery issues, such as proving the authenticity of the goods received by customers, and efficiently tracking or monitoring transportation states or items’ condition in real-time. However, supply chain has to face more security issues, especially the integrity, confidentiality and availability of assets and processes, come with information technology enablement due to its vulnerability for various cyberattacks. This exploratory investigation aims to show an explicit summarization of applying blockchain, cloud computing, data-provenance and IoT technologies to supply chain systems for enhancing its trust management and improving various security-related properties, i.e. transparency, visibility, accountability, trace-ability and reliability. It introduces general histories and definitions, in terms of information science, of the supply chain and related technologies which have been applied to supply chain management systems with purpose of facilitating its security and convenience. It provides a comprehensive review of current related research work and industrial cases. It also illustrates complementary relationships among those technologies while working on supply chain, discusses the applicability about why they are suitable and efficient for establishing a trust supply chain management. Finally, this paper concludes several potential or existing security issues and challenges which supply chain management is facing.
Notes on Offchain Protocols
◎Maxim Jourenko(Tokyo Institute of Technology)、Kanta Kurazumi(Tokyo Institute of Technology)、Mario Larangeira(Tokyo Institute of Technology and IOHK)、Keisuke Tanaka(Tokyo Institute of Technology)
Blockchain based systems, in particular cryptocurrencies, face a serious limitation: scalability. This holds especially in terms of number of transactions per second. There are still technical challenges that do not allow these systems to substantially increase the number of processed transactions. Several alternatives are currently being pursued by both the research and practitioner communities. One venue for exploration is on protocols that do not constantly add transactions on the blockchain and therefore do not consume the blockchain's resources. This is done using off-chain transactions, via payment channels.
This work revisits and relates the several existing off-chain channels, payment and state, payment networks and their respective network management algorithms. The main goal of this survey is to provide a comprehensive list of the state-of-art protocols available in the literature, outlining their respective approaches, advantages and disadvantages.
4E1-2
Lightweight Virtual Payment Channels
◎Maxim Jourenko(Tokyo Institute of Technology)、Mario Larangeira(Tokyo Institute of Technology and IOHK)、Keisuke Tanaka(Tokyo Institute of Technology)
Payment channel networks are one of the latest attempts on improving the scalability of blockchains in the number of transactions per second. Nodes within such a network can exchange funds without the necessity of interacting with the blockchain except during setup, closure or eventual dispute of their mutual channel. Payments can be executed across a path of payment channel using hashed time lock contracts. However, for each individual payment all nodes within a path need to be interacted with it during setup, execution or tear-down phases, and therefore they need to be online. This is a limitation of payment networks especially for long payment paths. A recent proposal by Dziembowski et al. (CCS'18) that enables payments across multiple payment channel without the necessity of intermediate nodes being online is using virtual payment channel. As of now the only construction for virtual payment channel requires smart contracts as those implemented on the Ethereum blockchain. Our work proposes a construction for virtual payment channel without requiring smart contracts, but instead it is built upon only time locks and threshold signatures. This enables implementation of virtual payment channel on a larger range of blockchain implementations such as Bitcoin.
4E1-3
A Timeout Anonymous Payment Channel for Decentralized Currencies
◎Kanta Kurazumi(Tokyo Institute of Technology)、Maxim Jourenko(Tokyo Institute of Technology)、Mario Larangeira(Tokyo Institute of Technology / IOHK)、Keisuke Tanaka(Tokyo Institute of Technology)
Anonymous payment channel (APC) was introduced by Green and Miers (CCS'17) with the Bolt protocol. This work contributes with the growing body of work on off-chain channels aiming to enhance the scalability of cryptocurrencies in the number of (in this case, anonymous) transactions per second. Although Bolt presents a secure formulation, we observe that it requires cooperation between costumer/merchant, the protocol players, in order to complete the protocol. More concretely, in its current form, if the costumer does not cooperate, the protocol cannot complete. The reason is that the costumer is required to start the channel closing procedure and it is not clear what happens if it does not. In this work we address this problematic situation with a variant definition for APC, which takes into account a timeout parameter, and present a protocol construction.
4E1-4
Account Management and Stake Pools in Proof of Stake Ledgers
Dimitris Karakostas(University of Edinburgh/IOHK)、Aggelos Kiayias(University of Edinburgh/IOHK)、○Mario Larangeira(東京工業大学/IOHK)
Blockchain protocols based on the Proof of Stake (PoS) paradigm are ---by nature--- dependent on the active participation of the owners of the assets maintained in the ledger.
This suggests a duality of the asset management functionality, which typifies PoS ledgers:
assets may be transferred between entities, whereas they
are also involved in the PoS protocol's execution. As a result, PoS account management schemes are required to offer both functionalities, a feature that has not been thoroughly investigated in the existing literature so far.
Moreover, it is often the case that not all stakeholders consistently take part in the protocol's execution and engage in the PoS mechanism. Given the security risks that such behaviour introduces, a countermeasure is to allow stake representation, thus giving the stakeholders the option to delegate their ``staking'' rights to other participants, thus forming ``stake pools.'' The core idea is that stake pool leaders are online and perform the required actions, whilst the stakeholders retain the ownership of their assets. Although this is a seemingly simple solution, the inner workings of such mechanism have yet to be fully investigated. Our work fills these gaps by thoroughly presenting all desiderata for account management and stake pools in the PoS setting. We formalize the requirements and present a framework which can be used to build stake pools for any PoS protocol. We introduce the first ideal functionality for a PoS wallet's core, which captures the capabilities that a PoS wallet should possess, and show how it can be realised based on standard cryptographic primitives. In describing the construction of PoS addresses, we distill and explore a novel property that PoS addresses should possess: non-malleability. We also specify the actions that a generic PoS wallet should offer, such as payment and staking, as well as formalize the security of the ``stake-pooled'' variant of any PoS protocol.
昨今の規模が拡大し複雑化したソフトウェアにおいて,人間によるレビューにより脆弱性を見つけるのは,工数や開発者の負担といった観点からも,容易ではない.ツールを用いた静的コード解析では,ソースコード内の脆弱性を,開発者の負担が少なく見つけることができる. 既存の静的コード解析ツールには,モデル検査やデータフロー解析などを用いたものが知られている.本論文では,それらとは異なるアプローチである深層学習によるソースコードの静的解析を試みた.より具体的には,C/C++のソースコードにおけるスタック及びヒープバッファオーバーフロー脆弱性を対象とし,Juliet Test Suite内の当該脆弱性を含むソースコードを用いてCharacter-level CNNによる学習と予測を行った.その際,学習に不要な情報を削減することを目的として,プログラムスライシングの技術を用いてソースコードを細分化したものを入力とした.その結果,90%以上の精度を実現した.
Challenges for Transparent and Trustworthy Machine Learning
○Vanessa Bracamonte(KDDI Research, Inc.)、Seira Hidano(KDDI Research, Inc.)、Shinsaku Kiyomoto(KDDI Research, Inc.)
Currently, many machine learning models are black boxes and the reasons for their predictions are difficult to understand. This lack of transparency makes it difficult for stakeholders ?from users to regulators? to decide whether the models and results are trustworthy and fair, and whether the models can be safely used in decisions that affect people. On the other hand, adding transparency could also make machine learning models vulnerable to manipulation and attacks. This paper will summarize current research on machine learning model transparency, in particular approaches such as model interpretability, and discuss challenges from a technical and social perspective.
Recent studies have demonstrated that neural network classifiers are susceptible to adversarial examples, which are crafted by adding some perturbations into original samples. So far, there are several defense methods against adversarial examples, but these methods have some limitations. In this paper, we propose an effective method for detecting adversarial examples, which does not need any prior knowledge about adversarial examples for the detection procedure, and is easily implementable. We utilize prediction inconsistency of several assistant neural networks for effectively detecting adversarial examples. Our method is evaluated by 30,000 adversarial examples, and it is shown that our method successfully achieves 90% detection accuracy.
ID ベース暗号や検索可能暗号などの高機能な暗号プロトコルの実用化が進んでいるが,中でもペアリング暗号の計算コストが問題となっており,ペアリングの効率化が求められている.非超特異楕円曲線を用いるペアリングにおける体の標数や楕円曲線の位数は,多くの場合整数$\chi$を変数とする多項式によって与えられる.本研究では,パラメータ$\chi$の条件がペアリングと密接な関わりをもつことに着目し,Kachisa-Schaefer-Scott (KSS) 曲線を用いるペアリングについて,とくに効率的な実装が可能となるパラメータの条件を提案する.この条件の下では,著者らの先行研究で提案したペアリングに対する計算効率の良い18次拡大体が構成可能であり,KSS曲線の係数を効率的に決定することができる.また,提案する条件の下ではツイスト曲線の係数も決定できると予想され,KSS曲線とツイスト曲線のペアの中には,とくにMillerのアルゴリズムを効率的に計算することができるものが存在する.
Trace Equivalence and Epistemic Logic to Express Security Properties
◎Kiraku Minami(Kyoto University)
In process algebras, security properties are expressed as equivalences between processes, but which equivalence is suitable is not clear. Appropriate formalization is essential for verification. We provide an epistemic logic for the applied pi calculus and use it to show that trace equivalence is pertinent to capture security notions in the presence of a non-adaptive attacker. At first, we prove that trace equivalence is a congruence. Secondly, we give an epistemic logic that characterizes trace equivalence. Thirdly, in this logic, we define multiple security properties such as role-interchangeability proposed by Mano et al. in 2010. Finally, we prove that satisfaction problems for the epistemic logic are decidable under some conditions. Our results imply that trace equivalence is more suitable to express security notions than lebelled bisimilarity.
多様かつ大量のデータが利用されつつある中、それらのデータを効率的に保管する仕組みが求められている。また個人や重要なデータの中には、長期間の保護が必要となる場合がある。これらのデータを長期間、効率的に保護する仕組みとして、Evidence Record Syntax(ERS)が存在する。ERSを用いれば、暗号アルゴリズムの移行も効率的に行うことが可能となる。そのため、ERSは量子コンピュータによる暗号アルゴリズム危殆化に備える上でも有用となる。そこで本研究では、XMLに特化したERSの一つであるXMLERSを実装した。加えて、データの公開時に一部を隠蔽する伝統的な方法である「墨塗り加工」に相当する機能を実装した。本研究は、墨塗り加工機能とERSを両立させるための実装上の課題と解決方法に関するものである。
インターネットでは、Botによるアカウントの大量取得やチケットの買い占めなどへの対策としてCAPTCHA(Completely Automated Public Turing test to tell Computers and Humans Apart)という仕組みが利用されている。中でも、人間の高度な画像認識能力に基づき、利用者に画像内容や画像の共通性などを解答させる画像型CAPTCHAが普及している。一方で、画像認識技術の進化に伴い、Google逆画像検索や画像内容を分類するアノテーションサービスを利用したそれらのCAPTCHAへの攻撃事例が報告されており、早急な対策が求められている。そこで、本稿では、そのような攻撃に耐性のある新しい画像型CAPTCHAを提案する。提案方式では、人間は正しく識別できるが、機械はその内容を「錯視」する画像を作成し、それを利用することで、高い攻撃耐性と高いユーザビリティが実現できることを示す。