New Secret Sharing Schemes with Detection and Identification of Rushing Cheaters
Avishek Adhikari(Department of Pure Mathematics, University of Calcutta)、○Kirill Morozov(School of Computing, Tokyo Institute of Technology)、Satoshi Obana(Faculty of Computer and Information Sciences, Hosei University)、Partha Sarathi Roy(Faculty of Information Science and Electrical Engineering, Kyushu University)、Kouichi Sakurai(Faculty of Information Science and Electrical Engineering, Kyushu University)、Rui Xu(KDDI Research Inc.)
We study detection and identification of rushing cheaters in $(k,n)$-threshold secret sharing schemes. At the reconstruction, rushing cheaters are allowed to provide their input {\em after} observing shares of the honest users. Our first scheme is capable of detecting at most $(k-1)/3$ cheaters, and it has the share size $|S|/\epsilon^3$, where $S$ is a set of possible secrets, and $\epsilon$ is the cheaters success probability. The second scheme detects up to $n-1$ cheaters, with share size $|S|/\epsilon^{k+1}$. The third scheme identifies at most $(k-1)/3$ cheaters, with share size $|S|/\epsilon^k$. To our best knowledge, this is the first scheme in this model such that the share size does not grow linearly with $n$ (but only with $k$). The forth scheme identifies up to $(k-1)/2$ cheaters (optimal cheater resilience in the public identification model) with share size $(n-t)^{n+2t}|S|/\epsilon^{n+2t}$. Its advantage is {\em flexibility} (in the security level), i.e., the cheaters success probability is independent of the secret size. Each of our proposals has the smallest share size among the existing schemes in the respective models; specifically for the forth one, we are referring to the schemes with flexibility property.
Robust Hierarchical Secret Sharing Scheme
○Partha Sarathi Roy(Faculty of Information Science and Electrical Engineering, Kyushu University)、Sabyasachi Dutta(Department of Pure Mathematics, University of Calcutta)、Kirill Morozov(School of Computing, Tokyo Institute of Technology)、Avishek Adhikari(Department of Pure Mathematics, University of Calcutta)、Kouichi Sakurai(Faculty of Information Science and Electrical Engineering, Kyushu University)
A hierarchical access structure divides participants into different levels of hierarchy. This particular type of generalization of threshold access structures occurs in real life scenario. There are few constructions of secret sharing schemes realizing such access structures.
Robust secret sharing schemes constitute an important class of basic building blocks for the multi-party computation. Though there are several constructions for robust secret sharing schemes but all of them only consider threshold access structures. To define robustness for secret sharing schemes that realize access structures more general than the threshold ones is not easy. In this paper, we take the initiative to define robustness for hierarchical secret sharing. We consider robust hierarchical secret sharing scheme secure against computationally unbounded rushing adversary who are allowed to submit (possibly forged) shares after observing shares of the honest users in the reconstruction phase.
To the best of our knowledge, this is the first information theoretic construction of robust hierarchical secret sharing scheme secure against malicious adversary.
1A1-6
Steganalysis of Bit Replacement Steganography for a Proactive Secret Image Sharing
○Angelina Espejel Trujillo(電気通信大学)、Mitsugu Iwamoto(電気通信大学)
An ordinary (k,n)-threshold proactive secret image sharing scheme (PSIS) permits that n generated stego-images preserve a secret image, the stego-images can be renewed frequently while these remains stored. The secret image can be reconstructed with k or more stego-images. However its implementation causes high accuracy detection of steganalysis due to the high payload and the use of least significant bit replacement (LSBR) steganography. To reduce the accuracy detection we explore the securely embedding data by using least significant bit matching (LSBM) and least significant bit matching revisited (LSBM-R). In addition we use a (k, L, n)-threshold ramp secret sharing scheme, which allows to reduce the amount of embedded data. The results of the evaluation show effectiveness of the proposal in terms of high payload and reduction of steganalysis detection, as well as accurate recovery of the secret. Moreover we present an evaluation of the bit replacement steganography methods showing the most reliable for our PSIS.
Scalar multiplication over higher degree rational point groups is one of the major challenges for faster implementation of pairing-based cryptography.
In this paper, we have presented a skew Frobenius mapping technique in the sub-field isomorphic sextic twisted curve of Kachisa-Schaefer-Scott (KSS) pairing-friendly curve of embedding degree 18 in the context of Ate based pairing.
Exploiting the skew Frobenius map along with multi-scalar multiplication technique, an efficient scalar multiplication method for KSS curve is proposed in the paper.
Along with the theoretic proposal, this paper has also presented a comparative simulation of the proposed approach with the left-to-right binary method, Montgomery ladder, sliding window method and non-adjacent form (NAF) for scalar multiplication.
The simulation result shows that the proposed method is about 60 times faster than a plain implementation of other compared methods.
An Introduction to Adversarial Machine Learning from Perspective of Information Security
◎Jiawei Su(九州大学)、Danilo V. Vargas(九州大学)、Kouichi Sakurai(九州大学)
Machine learning have been widely utilized for security sensitive applications such as spam filtering, intrusion detection, malware classification and biometric authentication. Although machine learning technique can bring advantages such as automation and intelligentization compared to previous rule-based security solutions, it also incurs additional vulnerabilities according to its complicated principle compared with latter. In this paper, we briefly introduce where and why machine learning security systems are vulnerable, and induce an introduction of a new domain called adversarial machine learning, which is an intersection between machine learning and information security and currently hasn’t been focused in Japanese cybersecurity and machine learning community. We then suggest some possible direction to extend current works from perspectives of cyber-security. The paper is aim to give a rough introduction, especially to cyber-security researchers who don’t familiar with and are interesting in adversarial machine learning and considering to extend their previous work to this domain.
車載ネットワークのセキュリティが重要課題になっており,車載ネットワークとして広く普及しているController Area Network(CAN)を保護するための異常検知手法が多く提案されてきた.異常検知の精度を高めるためには,CANメッセージに含まれるペイロードを検査する必要があるものの,CANメッセージの仕様はメーカや車種ごとに独自に設計されているため,異常検知システムを個別に設計しなくてはならなかった.特にペイロードに含まれる,車速などのセンサー情報や,シフトポジションなどの状態情報を示すフィールド単位で異常検知を行うためには,ペイロードから該当フィールドを抽出する必要がある.そこで本稿では,CANメッセージに含まれるフィールドを車種に依存せずに抽出する汎用的な手法を提案する.さらに実車から得られた通信ログに適用した結果として,提案手法が従来手法よりも精度良くCANメッセージのフィールドを抽出できることを示す.これにより,低コストかつ精度の高い異常検知システムの自動構築を実現することが期待できる.
近年車両のメンテナンスポートや無線回線からなりすましメッセージを車載制御ネットワークに注入して不正に車両を制御する研究事例が報告されておりこれらの攻撃に対する対策が急がれている.未知の攻撃へ対抗するために振る舞いベースの侵入検知を用いてネットワーク中に侵入したなりすましメッセージを検出することが知られているが,誤検知率(偽陽性、偽陰性)が高いためこの抑制が望まれている.本論文では,車載制御ネットワークに広く使用されるController Area Network(CAN) プロトコルにおいて周期的に受信される制御上重要なメッセージのなりすましを予め推定した受信周期の確率密度分布上での逸脱より検出し,車両の状況毎(オプション,走行状態,時間等)に変動する受信周期の確率密度分布を各々推定することで誤検知率を抑制する手法を提案する.また,実車で取得したネットワークトラフィックを用いた提案手法の評価結果を示すと共に,応用例を示す.
近年,自動車に対するサイバー攻撃として,遠隔から車載ネットワークに侵入し自動車を不正に制御する攻撃事例が報告されており,車載ネットワークとして広く普及するCAN(Controller Area Network)の通信を保護する研究がなされている.CANを流れるメッセージの異常検知手法として,値が連続的に変化するセンサ型データの振る舞いに基づいた手法が提案されている.しかしながら既存手法は,値が離散的に変化するフラグ型データに対して適用することができないという課題があった.本稿では,この課題に対し,フラグ型データの関係に基づいた異常検知手法を提案し,実車データを用いた評価により有効性を示す.
近年,産業用制御システム(ICS: Industrial Control Systems)を防御するためのセキュリティ対策としてホワイトリストが着目されている.ホワイトリストは正常なプロセスをリスト化しリスト外のプロセスを異常と判断するため,未知のマルウェアやサイバー攻撃に対応できる.すなわち,ICSのどんなプロセスをリスト化するかが重要である.ICSは停止状態から起動を経て運転状態へと状態遷移するライフサイクルが存在し,通信内容や動作プロセスはライフサイクル毎に異なる.すなわち,ある状態では正常なプロセスでも別の状態ではインシデントの可能性がある.そこで本稿ではプロセス制御システムの防御対策として,ライフサイクルに基づいたホワイトリストを利用する手法を提案する.本稿で提案する手法の特徴としてホワイトリストをモデルベースで作成する点,ライフサイクルを推定する機能を作成する点の二点が挙げられる.本手法を利用することで,ライフサイクルを考慮しないホワイトリストよりもインシデントの検出性能が向上する.本稿では気液プラントシステム及びシステムを監視する監視装置のモデルを作成した.監視装置にホワイトリストを適用し数値実験を行った結果,本手法の有用性を確認した.
産業用制御システム(ICS : Industrial Control Systems)に対するサイバー攻撃の増加に伴い,対策の必要性が一層高まっている.一方で,ICSでは,可用性重視の観点から従来のIT系セキュリティ技術をそのまま適用することは難しい.その中で,ICSはIT系のシステムに比べ通信パターンが固定的であることから,正常な通信を定義しそれ以外を異常とみなすホワイトリスト型侵入検知システム(IDS)が注目されている.そこで我々は,ICSの制御状態の遷移,停止,起動いったライフサイクルに応じて,正常な通信を定義するホワイトリストを切り替えることで,高精度な攻撃検知を実現するライフサイクルに応じたホワイトリスト型IDSを提案している.本稿では,MATLAB/Simulinkでモデル化した気液プラントシステムを対象に,提案するライフサイクルに応じたホワイトリスト型IDSのモデル化とシミュレーション評価を行った.そこで,提案するIDSは,正常操作に見せかけた高度なサイバー攻撃であっても検知可能であることを示す.本稿の寄与は,ライフサイクルに応じたホワイトリスト型IDSの実現性検証とその効果を示す点にある.また,既設のシステムへの導入を考慮したライフサイクル推定によるホワイトリスト型IDS方式について提案する.
SINDbAD: Stateful-INspection-Driver based Anomaly Detection System for In-Vehicle CAN Network
○Feiyu CHEN(Automotive & Industrial Systems Company, Panasonic Corporation)、Masato TANABE(Automotive & Industrial Systems Company, Panasonic Corporation)、Jun ANZAI(Automotive & Industrial Systems Company, Panasonic Corporation)、Tohru WAKABAYASHI(Automotive & Industrial Systems Company, Panasonic Corporation)、Manabu MAEDA(Advanced Research Division, Panasonic Corporation)、Takeshi KISHIKAWA(Advanced Research Division, Panasonic Corporation)
Due to the trend of connected cars, many automobiles have become interacting with exterior environments through both wired and wireless connections. While bringing convenience to vehicle users, such connections may provide possibilities for malicious parties to sneak into. Several white hackers have already proven that it is possible to send malicious messages into the in-vehicle CAN (Controller Area Network) network from outside by exploiting the connections and CAN protocol vulnerabilities. In this paper, we propose a CAN anomaly detection system (SINDbAD) composed of GMI (General Message Inspection) and SMI (Stateful Message Inspection), respectively for general and advanced attack detection. And we also evaluated the effectiveness of the system against several advanced attacks targeted to ADAS (Advanced Driver Assistance System).
車載ネットワークのプロトコルであるCAN(Controller Area Network)の脆弱性をねらった攻撃事例が複数報告されている.2016年にCho氏らがDoS攻撃の1種として,送信エラーを誘発させることによりECUをCANから離脱させるバスオフ攻撃を提案した.しかし,このバスオフ攻撃はCANコントローラを用いて,攻撃ターゲットECUと同じ送信開始タイミング,同じ周期でデータを送る必要があり,攻撃難易度が高い.本稿では,ラズベリーパイのような安価なデバイスを用いて,送信開始タイミングや周期といった時間的な制約がなくても,バスオフ攻撃を引き起こせる手法を提案する.提案手法は,CANバス上に流れているデータを監視し,ターゲットIDを検知すると,CANバスの差動電圧を強制的に制御させてスタッフエラーを引き起こすことを特徴とする.そして,CANバスプロトタイプ及び実自動車に対して攻撃を実施して,ECUの離脱と自動車の機能停止の動作を無効化させた結果を報告する.本手法は,攻撃でなく悪意あるCANパケットの侵入防御システムへの応用も可能である.
近年の自動車は電子制御により高度な機能が提供されている.これは,多数のECU(Electronic Control Unit)が自動車内部に組込まれ,それらが制御ネットワークを通じて相互に通信を行うことにより実現されている.この制御ネットワークとして現在広く用いられているのがCAN(Controller Area Network)である.しかし,CANではセキュリティを担保する機能が備わっていないため,数多くの攻撃事例が報告されている.その中に電気的データ改竄という攻撃がある.これは,CANメッセージを送信するECUと受信するECUがCANバスの信号をサンプリングするタイミングの違いを利用して,送信側のECUには攻撃を気付かれずに受信側に改竄されたデータを受信させる攻撃である.この攻撃はアナログな信号に対して直接攻撃を行うため,ディジタルなデータを対象としているセキュリティ手法では攻撃を検知・防御できない可能性もある.しかし,この攻撃は実験用のバスでしか攻撃が実証されておらず,多数のECUが互いに干渉し合っている実際の自動車のCANバスにてこの攻撃が脅威となるかは分かっていない.そこで,本論文では,電気的データ改竄を実際の自動車のCANバスで検証した結果を報告する.
CAN(Controller Area Network)は,組込み機器向けのバス型ネットワーク規格であり,車載ネットワーク等に広く用いられている.CANにおいて,バス上の電位差を適切なタイミングで意図的に変化させることで,送信側には受信側にデータが正しく送信されたと認識させ,受信側には攻撃者が改ざんしたデータを受信させるという電気的データ改ざん攻撃が指摘されている.この攻撃に対するセキュリティ強化策のひとつとして電圧波形を解析する手法があり,その中でも本来の1bitの送信よりも明らかに短い信号がないかを調べる長さ違反検知は実装が容易であり検知精度が良好である手法として提案されている.これまでこの手法はFPGAでのハードウェア実装を行い有効性が実証されているが,ハードウェア実装は導入のコストが大きい.本論文では,この長さ違反検知に着目し,ハードウェア実装よりも実装コストの小さいマイコンでの実装について複数の方法を述べる.さらに実験用のCANバスを用いて実証することにより,マイコン実装の有効性を示す.また,それぞれの実装方法について考察を行いまとめる.
現在の自動車に重要視される省エネ化や安全性,快適性を実現するための電子制御技術には,ECU(Electronic Control Unit)が欠かせない存在である.それらのECUは有機的に結合して車載ネットワークを構築している.CAN(Controller Area Network)は,その代表的な通信プロトコルである.ところが近年,Bluetoothや携帯電話などを介して外部より車載ネットワークに侵入し,自動車の制御を乗っ取る攻撃がいくつも報告されている.それに伴い車載ネットワークに対するセキュリティ技術の研究が急速に広がった.例えば,CANパケットのデータフレームが最長64ビットであるという制約のため,インターネットで利用されているプロトコルを単純に導入すると,結果的に複数のパケットが必要となり,バストラヒックが増加する問題がある.我々はCANプロトコルの変更を必要としないセキュリティ技術の提案に主眼を置き研究を進めている.本稿では,導入に伴うパケット数の増加を起こさないような,改ざんや再送攻撃に対するセキュアプロトコルについて議論する.
Time of Flight(ToF)方式距離画像カメラは,測定対象物へ向け光を照射し,反射して戻るまでの時間から対象物との距離を計測する.一定の範囲にある物体の位置関係を同時に取得可能なことから,将来はジェスチャー検知や障害物検知などの用途に利用することが期待される.しかし,外部からの攻撃により測定値が改ざんされると,存在する物体の認識が不可能となる,存在しない物体の誤認識が発生するなどの問題が発生する恐れがある.本稿では,ToF方式距離画像カメラの測定光をフォトダイオードで受け生成した攻撃光(なりすまし光)を,測定対象物へ照射することによって,測定値の改ざんが可能であることを実験にて確認した.また改ざんした測定値は,攻撃者が攻撃光の位相を変化させることで操作可能であることも確認した.
On Succinctness and Collusion-Resistance of Secret Key Functional Encryption
○北川 冬航(東京工業大学)、西巻 陵(NTT セキュアプラットフォーム研究所)、田中 圭介(東京工業大学)
In this work, we show how to construct a sub-exponentially secure secret key functional encryption (SKFE) scheme supporting a-priori unbounded number of decryption keys based only on a sub-exponentially secure SKFE scheme that supports only 1 decryption key and the size of whose encryption circuit is sub-linear in the size of functions.
2F1-4
All You Need is Slight Compression
○北川 冬航(東京工業大学)、西巻 陵(NTT セキュアプラットフォーム研究所)、田中 圭介(東京工業大学)
We propose a very simple method to achieve indistinguishability obfuscation (IO). Our key tool
is exponentially-efficient indistinguishability obfuscation (XIO), which is a weaker variant of IO. XIO provides an obfuscated circuit whose size is just slightly smaller than that of the entire truth table of an input circuit. We show how to construct IO from XIO and standard cryptographic primitives such as public-key encryption and identity-based encryption. As a corollary of our result, we can construct IO from single-key weakly succinct secret-key functional encryption and identity-based encryption.
Improved Authenticity Bounds of Sponge-Based Authenticated Encryption Schemes
○内藤 祐介(三菱電機)
In the security bounds of sponge-based authenticated encryption (AE) schemes there are four terms with security parameters: permutation size b, capacity c, key length, and tag length. Since the capacity term influences the efficiency and the security, it has mainly been improved. The first security bound of sponge-based authenticated encryption schemes was given by Bertoni et al. (SAC~2011), and later improved by Jovanovic et al. (ASIACRYPT~2014). For the privacy, the capacity term is independent of encryption and decryption queries, while not for the authenticity, where
the authenticity bound is $(\sigma_E+\sigma_D+Q)\sigma_D/2^c$, where $Q$ is the number of primitive queries, $\sigma_E$ the total input length by encryption queries, and $\sigma_D$ the total input length by decryption queries. This paper improves the authenticity bound so that the influences of encryption query and message length are removed,
that is, the capacity term is improved as $q_D Q/2^c$, where $q_D$ is the number of decryption queries. Applying our result to 3rd-round CAESAR candidates, Ascon and NORX, the capacity of Ascon can be reduced while keeping its security, and the security level of NORX is improved.
Weighted Feature Selection Techniques for Detecting Impersonation Attacks in Wi-Fi Networks
◎Muhamad Erza Aminanto(KAIST)、Harry Chandra Tanuwidjaja(KAIST)、Paul Yoo(Bournemouth University)、Kwangjo Kim(KAIST)
As Internet-of-Things (IoT) devices enable pervasive computing in our daily lives, more and more devices are connected to Wi-Fi networks. Public access to Wi-Fi networks leads to exploitable vulnerabilities that can be converted into attacks. The impersonation attack is an active, malicious action where unauthorized users masquerade as authorized users to gain privileges. Detecting impersonation attacks remains a challenging task due to properties similar to benign packets. Moreover, the pervasiveness of IoT devices connected to Wi-Fi networks generates complex, large-scale, and high-dimensional data, which leads to difficulties in real-time detection and mitigation. Selecting the best features is one of the challenging issues for improving the performance of the classifier. In this study, we examine the feature weighting methods in existing machine learners and look at how they could be used for accurate selection of impersonation attack features. We test and validate the utility and usefulness of the selected features using a standard neural network. This study demonstrates that the proposed weight-based machine learning model can outperform other filter-based feature selection models. We evaluated the proposed model on a well-referenced Wi-Fi network benchmark dataset, the Aegean Wi-Fi Intrusion Dataset (AWID). The experimental results not only demonstrate the effectiveness of the proposed model, achieving 99.86% accuracy, but they also prove that combining a weight-based feature selection method with a light machine-learning classifier leads to significantly better performance, compared to the best result reported in the literature.
A study on secure system design of IoT systems
○Yasuyuki Kawanishi(Sumitomo Electric Industries, Ltd.)、Hideaki Nishihara(SEI-AIST Cyber Security Cooperative Research Laboratory, AIST)、Daisuke Souma(National Institute of Advanced Industrial Science and Technology (AIST))、Hirotaka Yoshida(SEI-AIST Cyber Security Cooperative Research Laboratory, AIST)
In this paper, we discuss the status and problems in secure system design of IoT
systems. We explain how the known approaches work and present what we observe these
approaches from our own perspectives. By conducting case studies referring to ISO/IEC 15408
and JASO TP 15002 on secure designs of publicly available IoT systems such as the IPA-car
system which the IPA agency defined as the next-generation car model and so on, we attempt to
identify what problems can be found in the currently known methods. As a result, we classify the
major problems that are three-fold: ovarall optimization, third-party confirmation, and
consistency to the to-be-followed security design. One of the instances of these problems is that it
is not clear to find good trade-offs between work cost and output quality during secure system
design process. We finally discuss what challenges are there in the secure system design research.
近年,自動車の安全支援システムや自動運転システムに向けた技術開発が急速に進められている.これらのシステムでは,自動車外部の情報を取得するために,様々なセンサが搭載されており,その情報をもとに車載ECU(Electronic Control Unit)が自動車の重要な制御を行う.しかし近年,センシング段階において車載測距センサに対して測距不能にする攻撃(DoS攻撃)や測距値を短く偽装する攻撃事例が多数報告されている.本研究室も昨年に車載測距センサである赤外線センサとソナーセンサに対してDoS攻撃を行った結果と逆位相波で正規反射波を減衰させる方法について報告した.今回は正規反射波を減衰させる簡易な手法として,吸音材を用いる手法を採用した.その結果,実験室では攻撃波の送信周期を制御することで,実際の距離より小さい値及び大きい値を安定して改竄できることを確認した.本知見をもとに実車に対して攻撃を行い同様の改竄が可能であることを確認した.対策手法に関しても考察した結果を発表する.
ToF(Time of Flight)方式距離測定機器として用いられている距離計の一つに,超音波距離計がある.超音波距離計は自動車用障害物検知装置や,ヘリコプターの障害物センサなど,身近なところに用いられている.これらの機器の測定距離が改竄されると,障害物への衝突や急ブレーキの誘発による事故が引き起こされる可能性があり,攻撃されることを想定した対策を行う必要があると考えられる.先行研究として,超音波距離計の測定距離を,直接波を打ち消すことにより意図的に長く改竄させる攻撃手法がある.しかし,この攻撃手法の実現のためには,攻撃回路と攻撃対象の測定回路がほぼ同位置にあり同期して動作する必要があり現実的でない.そこで本論文では,測定回路から発せられた測定超音波の反射波を打ち消すことにより,測定距離を長く改竄する手法について提案し実験結果を示す.さらに,この提案手法の対策についての考察を行う.
A Classification of Lattice-based Trapdoor Functions
◎Rakyong Choi(KAIST)、Kwangjo Kim(KAIST)
A trapdoor function is a one-way function with trapdoor, which is indispensable to get the preimage of the function. In lattice-based cryptography, trapdoor function is needed to construct the secure cryptographic schemes like identity-based encryption, homomorphic encryption, or homomorphic signature.
There are three categories of trapdoor functions as standard trapdoor function, lossy trapdoor function, and homomorphic trapdoor function. Lossy trapdoor function is a trapdoor function that behaves in two ways. One behaves as a standard trapdoor function, whereas the other is losing information from the input. Homomorphic trapdoor function can make an evaluation on the computation of trapdoor function results.
In this paper, we survey the literature on lattices studying lattice-based trapdoor functions and preimage sampling algorithm of them. Then, we classify these trapdoor functions into aforementioned three categories.
Design of New Linearly Homomorphic Signatures on Lattice
◎Rakyong Choi(KAIST)、Kwangjo Kim(KAIST)
This paper introduces two designs to enhance the Boneh and Freemans linearly homomorphic signature over binary fields, to overcome the limitations to implement homomorphic signatures to the real world scenario due to the heavy calculation and under multiple signers setting for a message.
Based on our concurrent work on classification on lattice-based trapdoor functions in SCIS 2017, we modify some algorithms from the original signature. We design the linearly homomorphic ring signature by adopting Wang and Sun's sampling algorithm GenSamplePre() instead of the original sampling algorithm SamplePre() by Gentry et al. Also, we adopt the mixing and vanishing technique of trapdoors by Boyen to design more efficient linearly homomorphic signature scheme with short signatures.
Timing and Fault Attacks on Lattice-based Cryptographic Libraries
◎Hyeongcheol An(KAIST)、Sungsook Kim(KAIST)、Jeeun Lee(KAIST)、Rakyong Choi(KAIST)、Kwangjo Kim(KAIST)
Lattice-based cryptography is based on mathematical hard problem such as Learning with Error(LWE) and Ring-Learning with Error(Ring-LWE). These problems can be used for Fully Homomorphic Encryption(FHE) which attracts a lot of attention in the field of cloud computing environment and big data processing. On the other hand, side-channel attacks on a lot of cryptographic libraries have been tried except lattice-based cryptosystems. We first try to timing attack in lattice-based cryptographic libraries such as FHEW and HElib. Timing attack is simple and relatively easy to approach than other hardware-based side-channel attacks. In this paper, we compare and analyze four lattice-based open cryptographic libraries such as FHEW, HElib, Λ o λ, and LatticeCyrpto. In particular, aftter checking the time traces of the FHEW and HElib libraries, we investigate to determine if timing and fault attacks are feasible. As a countermeasure against timing attacks, we present a method for a padding to make of a message constant time encryption.
ブラウザやプラグイン等のクライアントを識別するブラウザフィンガープリンティングは,一般的にクライアントへの最適なコンテンツの配布に使用されるが,ドライブバイダウンロード攻撃によるマルウェア感染の脅威にも悪用されている.従来,攻撃者は主に JavaScript の機能を用いてクライアントを識別していたため,多くの研究者はこれらの機能を監視して,ブラウザフィンガープリンティングを解析する手法を提案してきた.しかしながら攻撃者は,ブラウザ実装の差異を悪用してクライアントを巧妙に識別するとともに,既存手法による解析を回避するようになった.そこで本稿では,実装方式の異なる実ブラウザとブラウザエミュレータで取得した Web サイトアクセスログを解析することによって,ブラウザ実装の差異を悪用する解析回避コードを抽出,分類する手法を提案する.1,710 件の悪性 Web サイトで実行された62,591 個のコードに本手法を適用した結果,JavaScript エンジンの実装差異を悪用するコードを発見した.これら発見を基に既存手法を改善することにより,解析性能の向上に寄与できる.
FC 2016において,Abadi らは検証可能委譲秘匿共通集合演算(VD-PSI)を提案した.クライアント間でクラウドに預けた暗号化データベースの共通集合を情報を漏らさぬまま求め,またクラウドの不正を検証することができる.しかし,彼らの方式にはクライアント間の安全通信路を必要とするという問題がある.本稿では,全ての通信をクライアントとクラウド間での公開通信路で行うことができるVD-PSI方式を提案する.クライアント間の通信が必要無いため,様々なクラウド環境に対応できる.既存方式に比べて,暗号文一個の送受信と暗号化・復号のコストが追加で必要となるが,計算量・通信量はほぼ同等である.
2D3-2
LEGO protocol with freeXOR gate
◎張 亜棟(埼玉大学)、小柴 健史(埼玉大学)
In the mid 1980’s, Yao presented a constant-round protocol for securely computing any two-party functionality in the presence of semi-honest adversaries.In Yao's protocol it have a problem that in the protocol we need to keep the Garbled Table to make sure that the computation of the gate is safe. The Garbled Table will cost many time to computation.Then in 2008, the freeXOR gate solved this problem for some class of functions.We can use the XOR gate to instead the previous gate, then we can omitted the Garbled Table.On the other hand, the Yao’s protocol only secure in the presence of relatively weak semi-honest adversaries. Now a number of protocols have been proposed for the efficient construction of two-party computation secure in the presence of malicious adversaries, and the most popular method is use the cut-and-choose way. At TCC 2009, Nielsen and Orlandi suggested to apply cut-and-choose at the gate level called LEGO, while previously cut-and-choose was applied on the circuit as a whole. My proposal is that, the freeXOR gate can be worked in the Yao’ protocol Garbled circuit, and the Garbled circuit in LEGO is same to the Yao’ protocol. So we want to use the XOR gate to instead the previous gate in the LEGO protocol.The new LEGO protocol with the freeXOR gate will be more efficient then the original LEGO.
2D3-3
Garbled circuitの暗号文サイズの下限を回避したgarbling schemeの提案
Carmen Kempka(NTTセキュアプラットフォーム研究所)、◎菊池亮(NTTセキュアプラットフォーム研究所)、鈴木幸太郎(NTTセキュアプラットフォーム研究所)
Garbling schemeとは,入力を秘匿しつつ回路計算を行うために,通常の回路を暗号文で構成されたgarbled circuitに変換する手法である.Zahurらはlinear garbling schemeと呼ばれる効率的な手法において,ANDゲートを1つgarblingするために最低kビットの暗号文2つが必要になることを示し,さらにこの下限を満たす手法を提案した.本論文では,この下限が回避できることを示し,実際にkビットの暗号文が2つ未満となるgarbling schemeを提案する.提案手法はZahurらの文脈においてlinear garbling schemeに含まれるため,Zahurらの下限を回避し更なる暗号文サイズの削減が可能であることを示している.また,提案手法はゲートの種類を秘匿するsemi-private function evaluationにも応用可能である.
車載ネットワークのセキュリティ対策として,AUTOSAR(AUTomotive Open System Architecture)では,MAC認証を用いたセキュアな通信プロトコルの標準仕様が策定されているが,認証に用いる暗号鍵の管理に関しては言及されていない.そこで,本稿ではECUの初期鍵K_IM,車両のマスター鍵K_M,セッション鍵K_SとAES暗号アルゴリズムを利用する鍵交換プロトコルを提案する.提案する手法では,ECUの初期鍵と型番を対応付けるデータベースをセキュリティゲートウェイに搭載する必要があり,このデータベースのセキュアな保管にPUFを利用する.当研究室では,サイドチャネル攻撃耐性を有するAES暗号回路のSBox演算で使用しているMDR(Masked Dual-Rail)-ROMに,少ない面積の追加で実装可能なMDR-ROM PUFを開発している.本PUFの車載向け応用を意識して,試作チップを-40℃~105℃という環境下で評価を行った.評価の結果,異なる環境でのPUF出力のエラー率が15%以下となり,誤り訂正を利用したシステムを用いて動作可能である事を確認した.
Experimental Analysis of LWE Problem
◎Yuntao Wang(Graduate School of Mathematics, Kyushu University)、Yoshinori Aono(NICT, Tokyo)、Tsuyoshi Takagi(IMI, Kyushu University)
The learning with errors (LWE) problem is considered as the one of the most powerful candidates as the security base for the post-quantum cryptographic schemes. The hardness of LWE depends on three parameters: the dimension n, moduli q and the deviation \sigma. For the application of LWE based cryptographic schemes, the concrete parameters are necessary. In the middle of 2016, Germany TU Darmstadt group initiated the LWE challenge in order to assess the hardness of LWE problems.
There are two algorithms to solve variants of closest vector problem(CVP) and study the experimental performances using published instances of LWE challenge: (1) Liu-Nguyen's algorithm to solve the bounded distance decoding (BDD) problem, which is an improvement of Babai's NearestPlane algorithm, and (2) Kannan's embedding technique. In this paper, we consider Kannan's embedding technique. The lattice reduction and enumeration algorithm we use is the progressive BKZ, which was proposed by Aono et al. in 2016. We will give an preliminary analysis for the running time and give a rough estimation for the proper size of parameters.
New variants of DeepLLL for decreasing squared-sum of Gram-Schmidt lengths
○安田雅哉(九州大学マス・フォア・インダストリ研究所)、山口純平(九州大学数理学府)
In cryptography, lattice basis reduction algorithms have been used as a tool for cryptanalysis. The most famous one is the LLL algorithm, and one of its typical improvements is LLL with deep insertions (DeepLLL). In both LLL and DeepLLL, at every time to replace a basis, we recompute the Gram-Schmidt vectors of the new basis. Compared with LLL, the formula of the new Gram-Schmidt vectors is complicated in DeepLLL, and no formula is currently known. In this paper, we present its explicit formula. We then propose new variants of DeepLLL with our formula. The squared-sum of Gram-Schmidt lengths of a basis are related with various lattice problems, such as the shortest vector problem (SVP) and the short diagonal problem (SDP). Once we find a basis with small squared-sum, we can solve several lattice problems with high probability. Given a basis, our variants can strictly decrease the squared-sum at every time of deep insertions.
Walter (ICITS 2015)は,slide簡約格子基底に対する最短ベクトル探索の最悪時計算量を見積もった.この結果によると,slide簡約基底のブロックサイズが格子の次元と近いときには計算量が$¥sqrt{n}^{n+o(n)}$となり,ほぼ最適な解析となっていると主張されていた.だが,高安と國廣(ISEC)により,Walterの解析はslide簡約基底の性質を正しく用いておらず,適切に評価し直すと計算量は$¥sqrt{n}^{3n+o(n)}$となり,Walterが主張したように最適な解析とはなっていないことを示した.ただし,この論文において高安と國廣はWalterの手法を評価し直しただけで,最適な解析を与えきれていなかった.本稿では,slide簡約基底のブロックサイズが格子の次元と近いときには計算量が$¥sqrt{n}^{n+o(n)}$となることを導く.これは,Walterが主張していた条件を達成するほぼ最適な結果となっている.
我々は,ブロックサイズが格子の次元を割り切れないときに,適切にその部分格子の体積を見積もることでこの結果を得る.
2B4-5
Attacks against search Poly-LWE
◎Momonari Kudo(Graduate School of Mathematics, Kyushu University)
The Ring-LWE (RLWE) problem is expected to be a computationally-hard problem even with quantum algorithms.
The Poly-LWE (PLWE) problem is closely related to the RLWE problem, and in practice a security base for various recently-proposed cryptosystems.
In 2014, Eisentraeger et al. proposed attacks against the decision-variant of the PLWE problem.
Their attacks succeed with sufficiently high probability in polynomial time under certain assumptions, one of which is that the defining polynomial of the PLWE scheme splits completely over the ground field.
In this paper, we present polynomial-time attacks against the search-variant of the PLWE problem.
Our attacks are viewed as search-case variants of the previous attacks, but can deal with more general cases where the defining polynomial of the PLWE problem does not split completely over the ground field.
Machine Learning on Whois: A Novel Approach to Classify Landing and Exploit Domains in Drive-by-download Attack
Tran Phuong Thao(株式会社KDDI総合研究所)、◎Akira Yamada(株式会社KDDI総合研究所)、Yukiko Sawaya(株式会社KDDI総合研究所)、Kosuke Murakami(株式会社KDDI総合研究所)、Ayumu Kubota(株式会社KDDI総合研究所)
Detection of drive-by-download attack has gained a focus in security research since the attack has turned into the most popular and serious threat to web infrastructure. The attack is triggered when a user visits a benign webpage that is compromised by the attacker (called landing page) and is inserted some malicious code inside. The user then is automatically redirected to an actual page that installs malware on the user’s computer (called exploit page) without his/her consent or even knowledge. While there is a large body of works targeting on detection of drive-by-download attacks, there is little attention on the redirection characteristic of the attacks. Even some works focus on this characteristic, they are inefficient or have smaller dataset than ours. In this paper, for the first time, we propose an approach to the classification of landing and exploit domains in the attack. The methodology used in our approach is to use machine learning to the registered information of the domain called whois. We intensively implemented our approach with several supervised learning models, compared the results and concluded that Decision Tree is the best model for our dataset which gives 91.83% accuracy, 93.44% precision, 93.44% for recall, and 93.44% for F1 score in merely 0.24 seconds of execution time both training and testing phases.
Potentially Unwanted Program (PUP)は従来のマルウェアとは区別され,ユーザのプライバシーやコンピュータのセキュリティの脅威となっている.PUPは広告の配信やPay Per Install,ソフトウェアのバンドルなどにユーザが同意していることが考えられ,一概にその通信先をブロックすることが適切であるとは限らない.そこで,49種類のPUPを動的解析しDNSクエリを抽出したところ,895ドメインに対するクエリがあり,公開ブラックリスト14,086件と一致したのは6ドメインにすぎないことが判明した.また,種類毎に一定数以上のサンプルを対象とし,DNSクエリのホスト名とDNSレスポンスのIPアドレスについて,全種類のサンプル間でJaccard係数を用いて類似性を評価した.その結果,1種類につき10サンプルのPUPを収集・解析することで,19種類中15種類のPUPは類似性があることがわかった.調査結果をもとに,感染PUP判定に特化したブラックリストを作成することができ,多種多様なブラックリストの中でも,PUPのブロック要否に応じたブラックリスト運用ができる.
2C4-5
Suspicious FQDN Evaluation based on Variations in Malware Download URLs
○Yasuyuki Tanaka(IISEC)、Atsuhiro Goto(IISEC)
Today's increasing Internet use is plagued by malicious activity. Drive-by download attacks have become a serious problem. As part of an exploit-as-a-service ecosystem for drive-by download attacks, malware download sites play a particularly important role in malicious attack. This paper examines the lifetimes of malware download sites in terms of their URLs and FQDNs. We found that malware download sites are longer-lived than exploit sites. We defined the malicious FQDN score and thereby analyzed top-scoring FQDN, time-series, score distributions, and VirusTotals. Our analytical results are useful for deciding appropriate methods or periods for blacklisting malware download sites.
Software vulnerabilities mitigations using automotive HSMs
◎Camille Gay(ESCRYPT)、Dennis Kengo Oka(ESCRYPT)
Automotive software has reached a high level of complexity, and although there are many ways to improve software security, vulnerabilities are to be expected. Mitigations of such vulnerabilities are needed at a hardware level, and that is why HSMs are increasingly being introduced in automotive microcontrollers. This paper demonstrates how an HSM can improve several automotive security applications’ resistance to software vulnerabilities by making use of hardware features, such as hardware-key encryption. Example applications such as Secure Flashing, Secure Onboard Communications and Secure Boot are compared with their software-only counterpart.
2E4-2
How to Enable Cyber Security Testing of Automotive ECUs by Adding Monitoring Capabilities
○Dennis Kengo Oka(ESCRYPT)、Stephanie Bayer(ESCRYPT)、Tobias Kreuzinger(ETAS)、Camille Gay(ESCRYPT)
Software in automotive ECUs is becoming larger and more complex; a modern vehicle contains more than 100 million lines of code. With increasing connectivity and advanced functionalities cyber threats targeting vehicles are becoming more prevalent. Attackers can exploit software vulnerabilities in automotive software to take control of a vehicle and potentially cause serious safety damage by, for example, disabling the brakes. Therefore, it is imperative to perform security testing during software development of automotive components to find and fix software vulnerabilities. We propose a method to enable cyber security testing of automotive ECUs by adding monitoring capabilities. We have built a test bench where a Security Testing Tool sends security test messages over an automotive network such as CAN to the ECU under test, and a Test and Validation Tool measures and monitors various values from the ECU to detect exceptions in the ECU behavior. We conducted experiments using an engine ECU and a gateway ECU. Using monitoring capabilities we were able to detect exceptions in the behavior on both ECUs. Based on the detected exceptions and corresponding information recorded by the Test and Validation Tool, it is possible for software developers to remedy software vulnerabilities before the ECU software is released and used in production.
2E4-3
Security Functional Testing of Automotive ECUs: Verifying the correct implementation of security features
○Dennis Kengo Oka(ESCRYPT)、Julian Wittmann(ESCRYPT)、Stephanie Bayer(ESCRYPT)、Camille Gay(ESCRYPT)
As emerging trends such as connected car and automated driving allow external communications and input to interact with internal vehicle components, automotive cyber security has become a requirement. To this end, several security solutions have been designed and deployed in the automotive domain. Secure in-vehicle communication and gateway filtering are two such examples. In this paper, we present a method for performing security functional testing of automotive ECUs with the purpose of verifying the correct implementation of security features. We implement our security testing module on top of LABCAR, which is an ECU test and validation tool typically used for functional testing of ECUs. We showcase two examples of security functional testing: 1) verifying correct implementation of MAC generation/verification on an ECU, and 2) verifying correct implementation of filtering functions on a Gateway ECU. The results show that we are able to reuse existing ECU test and validation environments and add a security testing module on top of LABCAR to perform the security testing. The security module is flexible and could be extended to cover additional test cases and scenarios in the future. With the suggested approach, it is possible to detect potential implementation flaws or configuration mistakes in the security solution on an ECU at an early stage in the development phase, and thus the security testing can assist in providing assurance of a correct implementation of security features.
仮想環境を用いて自動車制御ソフトのセキュリティ脆弱性の解析・評価手法を提案する.車載制御ネットワークに広く利用されているController Area Network(CAN)プロトコルは,成り済まし等の攻撃に対して耐性を示すことがあり,ランダムな攻撃方法を用いてセキュリティ上の欠陥を見つける場合には効率が悪いことがある.仮想環境による検証では,制御ソフトの設計情報とソースコードを利用することが可能であり,この情報に基づいて,脆弱性を特定することができる.本論では,より効率的に脆弱性を特定するためにモデル検査技術を用いた上で,仮想環境上にて実ソースコードに対して行った評価実験の結果を報告する.
改ざん耐性と唯一性を持つ暗号要素技術の不可能性
◎Yuyu Wang(Tokyo Institute of Technology/AIST)、Takahiro Matsuda(AIST)、Goichiro Hanaoka(AIST)、Keisuke Tanaka(Tokyo Institute of Technology/JST CREST)
CCA2 Key-Privacy for Code-Based Encryption in the Standard Model
◎吉田 雄祐(東京工業大学)、Kirill Morozov(東京工業大学)、田中 圭介(東京工業大学)
Code-based public-key encryption schemes by McEliece and Niederreiter are the famous candidates for the post-quantum world.
In this work, we study key-privacy (or anonymity) for these schemes in the standard model.
Specifically, we show that the following two paradigms for constructing IND-CCA2 encryption yield IK-CCA2 encryption, if the underlying primitive satisfies IK-CPA under k-repetition:
1) The Rosen-Segev construction (TCC 2009), we instantiate it with the Niederreiter scheme;
2) The Dottling et al. construction (IEEE Transactions on Information Theory 2012), we instantiate it with both the McEliece scheme and the Niederreiter scheme.
In our proof, we rely on an important observation by Yamakawa et al. (AAECC 2007) that the randomized McEliece encryption is IK-CPA in the standard model.
As a side result, we show that the randomized Niederreiter encryption is IK-CPA as well.
2F4-5
Perfectly Binding Code-Based Commitment Schemes
Kirill Morozov(School of Computing, Tokyo Institute of Technology)、○Partha Sarathi Roy(Faculty of Information Science and Electrical Engineering, Kyushu University)、Kouichi Sakurai(Faculty of Information Science and Electrical Engineering, Kyushu University)
With the aim to reduce the commitment size in code-based commitment schemes, we constructed a dual version of statistically binding scheme by Jain et al. (Asiacrypt 2012). Our scheme is proven secure under hardness of syndrome decoding. We also pointed out that perfectly binding variants of the above schemes follow directly from the Randomized McEliece encryption by Nojima et al. (Designs Codes and Cryptography 2008), assuming hardness of learning parity with noise as well as indistinguishability of permuted Goppa codes. Our key observation here is that perfect binding (as opposed to statistical binding) requires exact knowledge of the minimal distance of the underlying code. In addition, we provide a security evaluation of our proposals, and compare their performance to that of Jain et al.'s scheme.
2F4-6
Conversion from $1$-out-$2$ to $k$-out-$n$ Oblivious Transfer Protocol using Combinatorial Design
Samiran Bag(School of Computing Science, Newcastle University)、○Partha Sarathi Roy(Faculty of Information Science and Electrical Engineering, Kyushu University)、Kouichi Sakurai(Faculty of Information Science and Electrical Engineering, Kyushu University)
Oblivious transfer (OT) is an important primitive in the arsenal of distributed protocols. The concept of ``oblivious transfer" (OT) was introduced by Rabin in [Technical Report TR-81, Aiken Computation Laboratory, Harvard University, 1981], while $1$-out-$2$ OT was suggested by Even, Goldreich and Lempel in [Communications of the ACM, 1985]. In $1$-out-$2$, the sender sends an ordered pair of elements $(x_0, x_1)$ into the $1$-out-$2$ OT machine. The receiver gives the machine a bit $\sigma$, indicating which input he would like to receive. The machine outputs $x_{\sigma}$ to the receiver and discards $x_{1 - \sigma}$. The sender knows that receiver has one of the bits but does not know exactly which one. Crepeau [Crypto 1987] showed that Rabin's OT is equivalent to $1$-out-$2$ OT. There are several variants of OT in the literature and some of them were proved to be equivalent by Brassard et. al. [FOCS 1986]. $1$-out-$2$ OT is directly extend to $1$-out-$n$ OT and $k$-out-$n$ OT. To state informally, in an $k$-out-$n$ OT, $receiver$ can receive only $k$ messages out of $n$ messages $(n > k)$ sent by $sender$; and $sender$ has no idea about which $k$ messages have been received. Thus, for $sender$ all combinations of $k$ messages are equally likely possible for $receiver$ to receive. It has various security applications. For example, in on-line transactions, a $k$-out-$n$ OT allows a buyer to privately choose $k$ out of $n$ digital goods from a merchant without learning information about other $n-k$ goods. $1$-out-$n$ OT is a special case of $k$-out-$n$ OT where $k = 1$. Combinatorial design is used in secret sharing and other crypto graphic primitive. According to the best of our knowledge, combinatorial design has never been used in the literature of oblivious transfer protocol. We are the first to use combinatorial design to construct $k$-out of $n$ Oblivious Transfer protocol. Combinatorial designs are very powerful tools that have long been used in the field of security and cryptography. It deals with the construction and study of structures built from elements of a finite set that follow a definitive pattern or symmetry. This specific pattern makes them interesting and is exploited in every applications of combinatorial designs. Combinatorial designs are well studied and there are many different constructions of the same available in the literature. In this paper we have made use of a $t-(n,k,\lambda)$ Symmetric Balanced Incomplete Block design for which there are many efficient construction available in the literature. In a nutshell, in this paper we present a conversion from $1$-out-$2$ OT to $k$-out-$n$ OT using combinatorial design. Moreover, this conversion is unconditional i.e., we do not use any cryptographic assumption.
A Comparison of Three-Dimensional Sieve Methods for Number Field Sieve over GF(p^6)
◎WANG KUN(九州大学数理学府)、林 卓也(NICT)、高木 剛(九州大学 マス・フォア・インダストリ研究所)
The discrete logarithm problem (DLP) over GF(p^6) has been investigated for estimating the security of torus-based cryptography and pairing-based cryptography. The number field sieve (NFS) is known as the asymptotically fastest algorithm for solving the DLP. It is also known that, in the NFS, the sieving step takes most of the running time in practice, and much effort has been made for efficient algorithms and implementations. On the NFS for the DLP over GF(p^6), the optimal sieving dimension would be three, so three-dimensional sieve methods became more important. The line sieve and lattice sieve has been investigated for two-dimensional sieve, and extended for multi-dimension. The Franke-Kleinjung sieve, which is known as the fastest sieve method in practice, has been developed for two-dimensional sieve. In 2014, Hayasaka et al. proposed a 3D variant of Franke-Kleinjung sieve, but since they do not provide precise comparisons, it is still not clear the new method is more efficient than the others. In this paper, we shed light on that point. We implement line, lattice, and 3D Franke-Kleinjung sieve, and experiment on the DLP of some moderate sizes for precise comparisons.
3A1-2
Extended Tower Number Field Sieve with Application to Finite Fields of Arbitrary Composite Extension Degree
◎Taechan Kim(NTT Secure Platform Laboratories)、Jinhyuck Jeong(Seoul National University, Korea)
We propose a generalization of exTNFS algorithm recently introduced by Kim and Barbulescu (CRYPTO 2016). The algorithm, exTNFS, is a state-of-the-art algorithm for discrete logarithm in ¥mathbb{F}_{p^n} in the medium prime case, but it only applies when $n=¥eta¥kappa$ is a composite with nontrivial factors ¥eta and ¥kappa such that ¥gcd(¥eta,¥kappa)=1. Our generalization, however, shows that exTNFS algorithm can be also adapted to the setting with an arbitrary composite n maintaining its best asymptotic complexity. We show that one can solve discrete logarithm in medium case in the running time of L_{p^n}(1/3, ¥sqrt[3]{48/9}) (resp. L_{p^n}(1/3, 1.71) if multiple number fields are used), where n is an ¥textit{arbitrary composite}. This should be compared with a recent variant by Sarkar and Singh (Asiacrypt 2016) that has the fastest running time of L_{p^n}(1/3, ¥sqrt[3]{64/9}) (resp. L_{p^n}(1/3, 1.88)) when n is a power of prime 2. When p is of special form, the complexity is further reduced to L_{p^n}(1/3, ¥sqrt[3]{32/9}). On the practical side, we emphasize that the keysize of pairing-based cryptosystems should be updated following to our algorithm if the embedding degree n remains composite.
3A1-3
On the Computational Complexity of the DLP with Low Hamming Weight Product Exponents
○Jason Ying(東京大学)、Noboru Kunihiro(東京大学)
In this work, we describe an improved method of solving certain parameters of the discrete logarithm problem with low Hamming weight product exponents and its application.
3A1-4
特別な形の素因数を持つ合成数の楕円曲線法による素因数分解II
○白勢 政明(公立はこだて未来大学)
先行研究では、合成数Nがp=(DV^2+1)/4, D in {3, 11, 19, 43, 67, 163}という形の素因数を持つ場合Nは楕円曲線法により簡単にpを見つけることができることを示した。なおこのDは類多項式が1次となる判別式である。今回の発表では、類多項式が2次となるD in {35, 51, 91, 115, 123, 187, 235, 267, 403, 427}の場合も、多項式環の剰余環上で楕円曲線を考えることで、簡単にpを見つけることができることを示す。
3A1-5
Improved Factoring Attacks on Multi-Prime RSA with Small Prime Difference
◎Mengce Zheng(University of Science and Technology of China/The University of Tokyo)、Noboru Kunihiro(The University of Tokyo)、Honggang Hu(University of Science and Technology of China)
In this paper, we study the security of multi-prime RSA with small prime difference and propose two improved factoring attacks. This variant modifies the modulus N to be the product of r distinct prime factors of same bit-size. At ACISP 2013, Zhang and Takagi showed a Fermat-like factoring attack that can directly factor N. In order to improve the previous bound, we utilize the information on all prime factors to derive r simultaneous modular equations. The first attack is based on combining r equations to solve one multivariate modular equation. Furthermore, since our factoring problem is formulated similar to multi-prime Φ-hiding problem introduced by Kiltz et al. (CRYPTO 2010), we can apply the optimal linearization technique presented by Tosu and Kunihiro (ACISP 2012). It is showed that our attacks can achieve better bounds than previous attack.
Universal Scoring Functions for Bias-Based Fingerprinting Code under Relaxed Marking Assumption
○栗林 稔(岡山大学)、舩曵 信生(岡山大学)
The study of universal detector for fingerprinting code is strongly dependent on the design of scoring function. The best detector is known as the MAP detector that calculates an optimal correlation score, but the number of colluders and their collusion strategy are inevitable. We have proposed the scoring function equalizing the bias between symbols, which is called bias equalizer. In this study, we further investigate an efficient scoring function based on the bias equalizer under the relaxed marking assumption such that white Gaussian noise is added to a pirated codeword. The performance is compared with MAP detector as well as some existing universal scoring functions.
Edge-side Security Event Management for Plug-and-Play IoT
○Fumiko Satoh(IBM Research - Tokyo)、Takuya Mishina(IBM Research - Tokyo)、Naoto Sato(IBM Research - Tokyo)、Yoichi Hatsutori(IBM Research - Tokyo)
Security attacks on IoT devices have been increasing explosively because many of these devices have not been well designed to consider security features. Security Information and Event Management (SIEM) technology is one of the solutions to tackling attacks on IoT devices. This paper proposes an edge-side SIEM for IoT with a Plug-and-Play manner. IoT environments are faced with specific challenges: 1) device-specific security and logging design, and 2) limited bandwidth with a large number of devices. We introduce an IoT SIEM Gateway to the SIEM platform to tackle these challenges. The Gateway is implemented by Data Format Description Language (DFDL), which is a key technology to receive device-specific event logs and detect anomaly situations with common rules. DFDL also enables auto-installation of various IoT devices to the platform by deploying DFDL schemas for each device. The Gateway can preprocess detected events at the edge before transferring them to Cloud. So the scalability of the SIEM platform can be improved even in limited bandwidth. We evaluate the Gateway’s connectivity and scalability with our first prototype. Additionally, we also prototype practical solutions on top of this SIEM platform which are applied to both network cameras and connected cars. It shows that our Gateway is extensible for a broad range of objectives.
検証者ローカル失効グループ署名(Group signature with verifier-local revocation, VLR-GS)[Boneh et al., CCS 2004]は,
失効機能付きグループ署名の一種であり,失効ユーザ情報を用いることなく署名を作成できるという利点を持つ.
しかしながら,既存のVLR-GS方式は,グループ署名における標準的な安全性(完全匿名性)より弱い安全性しか満たさない.
そこで本研究では,完全匿名性を満たす初めてのVLR-GS方式を提案する.
より詳細には,完全匿名性を満たすVLR-GS方式を電子署名方式,鍵秘匿性を満たす公開鍵暗号方式,非対話型ゼロ知識証明システムから構成する.
また,本結果はVLR-GS方式に対する初めての一般的構成を与えるものであるため,
我々の構成はVLR-GS方式を構成するための指針の一つになると期待される.
3F1-6
Fully Secure Lattice-based Group Signatures with Verifier-local Revocation
◎M Nisansala S Perera(Saitama University)、Takeshi Koshiba(Saitama University)
In PKC 2014, Langlois et al. proposed the first lattice-based group signature scheme with the verifier-local revocability. The security of their scheme is selfless anonymity, which is weaker than the security model defined by Bellare, Micciancio and Warinschi (EUROCRYPT 2003). By using the technique in the group signature scheme proposed by Ling et al. (PKC 2015), we propose a group signature scheme with the verifier-local revocability. For the security discussion of our scheme, we adapt the BMW03 model to cope with revocation queries since the BMW03 model is for static groups. Then, we show that our scheme achieves the full anonymity in the adapted BMW03 model.
Numerical Analysis of Elias's and Peres's Deterministic Extractors
◎Amonrat Prasitsupparote(Yokohama National University)、Norio Konno(Yokohama National University)、Junji Shikata(Yokohama National University)
Generating truly random numbers is important in cryptography. Von Neumann proposed the simple procedure for extracting truly random bits from a sequence of independent, identically distributed random biased bits about half century ago. The improved algorithms of the von Neumann's extractor were later proposed by Elias and Peres. In this paper, our experimental results show that the theoretical and empirical redundancy are almost the same in each extractor. Furthermore, we show the redundancy function of Peres's extractor with iterations more than or equal to 5 is not concave. Next, we show that the redundancy of Peres's extractor is much better than Elias's extractor under the same input size and the almost same running time.
本稿では、ハイブリッドクラウドにおけるプライバシー情報の漏洩防止方法を考察する。パブリッククラウドは処理能力が高いがセキュリティが弱い部分があるので、情報漏えいの可能性を考慮して、機密情報の処理はプライベートクラウドで行うという、ハイブリッドクラウド処理が提案されている。このハイブリッドクラウド上での大規模データ分析の手法としてSEMROD(Secure and Efficient HybriD Clouds)がある。SEMRODを用いたMapReduceフレームワークおよび、その高速化手法が考案されているが、いずれの手法においても、パブリック側のデータが流出した場合に、パブリック側にデータが存在しないという事実から、機密情報が一部漏れるという問題が存在する。この問題を解決するために、機密情報のみを持つデータには、パブリック側にダミーデータを挿入することで、機密情報の暴露を防ぐ方法を考察する。
近年,顧客のモバイル端末にインストールされた専用のアプリケーション・ソフトウェアを使って,顧客の取引金融機関からデータを取得し,それらを集計・加工して当該顧客に提供するサービスなどが提供されるようになってきた.こうしたサービスの提供主体は「TPPs(Third Party Providers)」と呼ばれている.一部の金融機関では,TPPsの取込みに向けて,自社のAPI(Application Programming Interface)を既にオープン化している.各国の金融当局も金融機関のAPIのオープン化について検討を進めている.TPPsが介在すると,金融機関が保有する顧客のデータに,TPPsもアクセスすることになる.また,金融機関サイドでは,APIのオープン化に伴い,通信路を新設する必要がある.このため,TPPsと金融機関は,新たなセキュリティ上のリスクを考慮し,その対応策を検討する必要がある.本稿では,APIを介してサービスを実施するシステムの基本的なモデルを想定し,そのリスクやセキュリティ対策について考察する.
近年IoT(Internet of Thing)に関する研究が活発になってきている。IoTにおいては、低負荷な処理で安全にデータを通信できなければならない。従来のセンサネットワークにおける暗号通信では、ノード同士が鍵を共有して収集した情報を転送し、中間ノードで復号をしてデータ集約しながら基地局までデータを送っていた。しかしIoT環境ではネットワーク構造の変更が頻繁に起こる可能性があるため、その度に鍵共有を行うのはノードに余計な負荷がかかってしまい電池消耗を早めてしまう。また、中間ノードでのデータ復号処理なども同様に電池消耗を早めてしまう。本稿では非対称秘密分散を用い、ノード間で鍵共有をする必要がなく、中間ノードにおけるデータの復号処理をする必要のないIoTに適したデータ集約の方式を提案する。
3E2-2
IoT向けの堅牢な鍵管理システム
○大塚 浩昭(NTTセキュアプラットフォーム研究所)、永井 彰(NTTセキュアプラットフォーム研究所)、小林 鉄太郎(NTTセキュアプラットフォーム研究所)、奥山 浩伸(NTTセキュアプラットフォーム研究所)、山本 剛(NTT Innovation Institute, Inc.)
Efficient packing method for secure matrix multiplication over Ring-LWE somewhat homomorphic encryption
Doung Hoang Duong(Institute of Mathematics for Industry, Kyushu university)、○Pradeep Kumar Mishra(Graduate School of Mathematics, Kyushu university)、Masaya Yasuda(Institute of Mathematics for Industry, Kyushu university)
Homomorphic encryption allows us to perform various calculations on encrypted data. In this paper, we propose efficient packing method for secure and fast matrix multiplication over Ring-LWE using somewhat homomorphic encryption scheme proposed by Brakerski and Vaikuntanathan (CRYPTO 2011). Packing method is an excellent way to make encryption scheme more efficient. To achieve the efficiency for the matrix multiplication in cloud computing , we propose a new method to pack a matrix into a single ciphertexts so that it also enables efficient matrix multiplication over the packed ciphertexts. Our packing method generalizes Yasuda et al.’s methods (Security Comm. Networks 2015 and ACISP 2015), which are for secure inner product moreover we implement our method as well as previous method to give a comparison side by side for encryption, multiplication of ciphertext and decryption.
Subring Homomorphic Encryption
Seiko Arita(Institute of Information Security)、○Sari Handa(Institute of Information Security)
In this paper, we construct "subring homomorphic encryption scheme" that is a homomorphic encryption scheme build on the decomposition ring which is a subring of cyclotomic ring. In the scheme, each plaintext slot contains an integer in Z/p^l Z, rather than an element of GF(p^d) as in conventional homomorphic encryption schemes on cyclotomic rings. Our benchmark results show that the subring homomorphic encryption scheme is several times faster than HElib for plaintexts composed of modulo p^l slots, due to its high parallelism of slot structure. We believe in that the plaintext structure composed of modulo p^l slots will be more natural, easy to handle, and much more efficient for many applications such as outsourced data mining.
Revisiting the Efficient Key Generation of ZHFE
◎Yasuhiko Ikematsu(Institute of Mathematics for Industry, Kyushu University)、Dung H. Duong(Institute of Mathematics for Industry, Kyushu University)、Albrecht Petzoldt(National Institute of Standards and Technology)、Tsuyoshi Takagi(Institute of Mathematics for Industry, Kyushu University)
ZHFE, proposed by Porras at el. at PQCrypto’14, is one of the very few existing multivariate encryption schemes and a very promising candidate for post-quantum cryptosystems. The only one drawback is its slow key generation. At PQCrypto’16, Baena et al. proposed an algorithm to construct the private ZHFE keys, which is much faster than the original algorithm, but still inefficient for practical parameters. Recently, Zhang and Tan proposed another private key generation algorithm, which is very fast but not necessarily able to generate all the private ZHFE keys. In this paper we propose a new efficient algorithm for the private key generation of the ZHFE scheme. Our algorithm is in practice very fast compared to that of Baena et al. We also estimate the number of possible keys generated by all existing private key generation algorithms for ZHFE. Our algorithm generates as many private ZHFE keys as the original and the Baena et al.’s one. This makes our algorithm be the best appropriate for the ZHFE scheme.
On Gu's Attack Against Simple Matrix Scheme
◎Yacheng Wang(Graduate School of Mathematics, Kyushu University)、Dung Hoang Duong(Institute of Mathematics for Industry, Kyushu University)、Tsuyoshi Takagi(Institute of Mathematics for Industry, Kyushu University)
As we know that currently widely used public key cryptosystems such as RSA, DSA and ECC can not stay secure forever, and especially with emergence of quantum computers, they are even more threatened. So we need alternatives to resist those computers, multivariate public key cryptosystems, as one of the quantum resisting cryptosystems, have been researched since 1980's. Among the multivariate signature schemes that were proposed, a lot of them are proved to resist all kinds of attacks, however, even many attempts about multivariate encryption schemes have been proposed, but unfortunately they were all proved insecure against some known attacks, such as rank attacks, linearization attack, differential attacks, etc. At PQCRYPTO '13 in Limoges, Tao, Diene, Tang, and Ding proposed a very simple and efficient multivariate public key encryption scheme based on matrix multiplication, which seems to avoid all known attacks. Later in 2016, it appeared a attack by Gu, which asks to reconstruct and solve a linear system that yields from regarding elements in private key as variables. In addition, he claims that breaking simple matrix can be achieved in polynomial time. In our paper, we take a closer look at Gu's attack, and reanalyze the complexity of this attack and give the experiment results of this attack.
3A3-5
SVSv - A New Multivariate Signature Scheme with Vinegar
○Dung Hoang Duong(Institute of Mathematics for Industry, Kyushu University)、Albrecht Petzoldt(Institute of Mathematics for Industry, Kyushu University)、Yacheng Wang(Graduate School of Mathematics, Kyushu University)、Tsuyoshi Takagi(Institute of Mathematics for Industry, Kyushu University)
Multivariate public key cryptography is one of the main candidates for cryptosystems
in the era of large-scale quantum computers. At Inscrypt 2015, Nie et al. proposed a new multivariate
signature scheme called CUOV, whose public key consists both of quadratic and cubic polynomials.
However, the scheme was broken by an attack of Hashimoto. In this paper we revisit the CUOV
scheme and propose a new multivariate signature scheme SVSv whose public key consists of only
quadratic polynomials. Our scheme SVSv is secure against Hashimoto’s attack and all other known
attacks on multivariate schemes. Especially SVSv is very efficient and outperforms current multivariate
signature schemes such as UOV and Rainbow in terms of key and signature size.
Privacy-Enhancing Trust Infrastructure for Process Mining
Sven Wohlgemuth(Austr. 5, 71665 Vaihingen an der Enz, Germany)、○Kazuo Takaragi(National Institute of Advanced Industrial Science and Technology)
Threats to a society and its social infrastructure are inevitable and endanger human life and welfare. Resilience is a core concept to cope with such threats in strengthening risk management in spite of incidents of any kind. This paper discusses the secondary use of personal information as a key element in such conditions and the relevant process mining. It realizes a completeness in an acceptable manner to mitigate a usability problem by secondary use of personal information. Even though, acceptable soundness is still realized in our scheme for a fundamental privacy-enhancing trust infrastructure. Our work approaches the Ground Truth for a personal predictive IT risk management by process mining with the block chain technology and privacy-enhancing mechanisms.
RSA暗号の秘密鍵が,アナログ情報として漏洩したときの安全性に関して議論する.CHES2014で,Kunihiro and Hondaは,まず,漏洩モデルを確率分布を用いて定義し,その確率分布が完全にわかっている時に有効なアルゴリズムおよび,何もわかっていない時に,有効なアルゴリズムを提案している.前者のアルゴリズムには,実際の攻撃の状況では,確率分布が正確にわかるとは限らないという問題点がある.この論文では,確率分布の正確な分布ではなく,その近似がわかっている場合でも,少しの修正でアルゴリズムは動作すること,近似の精度が悪くなると,解読できるための条件が悪化することを示した.後者には,漏洩が非対称に行われる時には性能が悪いという問題点があった.SCIS2015で,高橋と國廣は,確率分布の分散を用いることにより,非対称の場合でも動作するアルゴリズムを提案し,数値実験により有効性を示している.この論文では,解読できるための条件を理論的に導出し,SCIS2015で示した方式が最適であることを証明する.
Anonymizing Train History using Hierarchical Clustering
◎Seongun Choi(Graduate School of Information Science and Technology The University of Tokyo)、Toshiro Hikita(Graduate School of Information Science and Technology The University of Tokyo)、Rie Shigetomi Yamaguchi(Graduate School of Information Science and Technology The University of Tokyo)
Recently, data is utilized in various fields. Data publication can even enlarge the use of data by allowing secondary use of data. For data publication, privacy preserving is necessary because data is usually collected from individuals, i.e., it involves personal information. k-anonymity is a famous privacy notion for preserving privacy on data publication. It is known that high dimensional data such as trajectory data is hard to k-anonymize. So it has been challenged for trajectory data to retain its utility while satisfying privacy notions. In this paper, we propose a k-anonymizing method for trajectory which use hierarchy clustering method to cluster trajectories. To retain the best data utility after publishing, we set the specific purpose of data analysis. For marketing purpose, we fix get off stations and generalize get on stations. We show that our proposal algorithm effectively minimizes the utility loss.
Low Bit Error Rate Latch PUF with EE Structure
○劉時宇(早稲田大学大学院情報生産システム研究科)、鄭佰昆(早稲田大学大学院情報生産システム研究科)、朴延浩(早稲田大学大学院情報生産システム研究科)、劉昆洋(早稲田大学大学院情報生産システム研究科)、謝榮豪(早稲田大学大学院情報生産システム研究科)、篠原尋史(早稲田大学大学院情報生産システム研究科)
Abstract: Reducing BER (Bit Error Rate) is a hot topic in PUF field for key generation. In this paper, a new type of PUF with low BER called EE (Enhancement-Enhancement) Read Only PUF is presented. This new type of is researched in three dimension as follow: First, analyzed the performance and operation of EE structure. The structure of EE Read Only PUF is based on SRAM PUF. Compared to SRAM PUF bit cell, EE Read Only PUF bit cell consist of only NMOS. This structure has much more stable performance against noise. Meanwhile, in order to stabilize output of EE bit cell, two additional NMOS transistors are added. Second, verified the EE Read Only PUF performance by simulation and measurement. According to the Monte Carlo noise & Vth simulation, BER of EE Read Only PUF is 0.79%. Afterward, the measurement result of BER is 0.68%. Third, analyze a probability model of output data of EE PUF.
?
Abstract: Reducing BER (Bit Error Rate) is a hot topic of PUF for security application. In this paper, a new type of PUF with low BER called EE (Enhancement-Enhancement) Read Only PUF is presented. The key idea of this PUF is that CMOS inverter is replaced by EE NMOS inverter in conventional SRAM cell, so that butterfly curve in data power up phase changes and the output becomes less sensitive to noise. In order to stabilize output of EE bit cell in data read phase, two read NMOS transistors are added. Result of Monte Carlo noise & Vth simulation with 180nm CMOS technology, BER of EE Read Only PUF is 0.79%. The low BER is verified by the measurement result (0.68%) using the fabricated circuits with the same technology. Finally, a probability model of output data of EE PUF is analyzed.
Security Analysis of End-to-End Encryption in Telegram
◎Jeeun Lee(KAIST)、Rakyong Choi(KAIST)、Sungsook Kim(KAIST)、Kwangjo Kim(KAIST)
Telegram is known as one of the most popular instant messaging (IM) services for secure communications. It features end-to-end encryption (E2EE) in secret chats based on their customised protocol called MTProto. This brand new protocol is believed as a safe alternative among the public, however, it is in doubt and has not been fully reviewed by cryptanalytic experts. It is theoretically demonstrated in 2015 that MTProto does not meet indistinguishability under chosen ciphertext attack (IND-CCA) and integrity of ciphertexts (INT-CTXT). In this paper, we start to analyse the security vulnerabilities of E2EE in simplified Telegram in a heuristic manner and suggest typical building blocks for E2EE in general IM system.
With the rapid development of cloud computing, storage function has been greatly improved. Cloud storage as a service,take great convenience to the clients who want to outsource their data to the cloud storage. Thus, clients can take advantage of unlimited virtualized storage space and the low management cost. However, because of the possibility of public access in cloud, the security of the sensitive data becomes an urgent problem to be solved. Client upload the data to the cloud server, makes the client lose the control of the data. To prevent illegal access to data and protect the confidentiality of the data, the client encrypted the data before they upload the data to the cloud. But it is hard for the other clients to search the data among the numerous encrypted data. As a solution, many searchable encrypted schemes have been proposed recently. They allow the clients to search for a certain keyword over the encrypted data without revealing the content.
In this paper we propose a searchable re-encryption scheme with multi-user. We combine a searchable scheme and the ID-Based proxy re-encryption scheme. It can supports multi-user security, efficient retrieval of encrypted data. It also can reduce the computational complexity of the client in the decryption process.
3F4-2
Non-Transferable Proxy Re-Encryption for Group Membership/Non-Membership
◎Lwin San(Saitama University)、Ei Mon Cho(Saitama University)、Takeshi Koshiba(Saitama University)
In proxy re-encrytpion (PRE) scheme, the message is sent by a delegator to a delegatee
with a help of the trusted third party proxy without knowing the existing plaintext. PRE schemes
are widely used in various applications. However, the standard PRE scheme has some proxy problems
called private key generator despotism (PKG despotism) problem. This means that PKG can make
re-encryption key without permission from delegator. And also, this PRE scheme have the key-escrow
problem. If someone can attack PKG in a PRE scheme, they can decrypt both the original ciphertext
and the re-encrypted ciphertext which means the key-escrow problem. A solution for these two problems
is to use non-transferable PRE scheme. Non-transferable PRE scheme solved the above PKG despotism
problem and key-escrow problem. We would like to introduce our PRE scheme with a new approach.
In our scheme, there are three sub-processes, which are based on a non-transferable PRE scheme and
group signature. Our scheme will provide the security for delegator i, delegatee j (who is in the same
group with delegator i), and delegatee k (who is in a different group with delegator i).
A refinement of quantum mechanics by algorithmic randomness and its application to quantum cryptography
○只木孝太郎(中部大学工学部情報工学科)
The notion of probability plays a crucial role in quantum mechanics. It appears in quantum mechanics as the Born rule. In modern mathematics which describes quantum mechanics, however, probability theory means nothing other than measure theory, and therefore any operational characterization of the notion of probability is still missing in quantum mechanics. We present an alternative rule to the Born rule based on the toolkit of algorithmic randomness by specifying the property of the results of quantum measurements in an operational way. Algorithmic randomness is a field of mathematics which enables us to consider the randomness of an individual infinite sequence. We then present an alternative rule to the Born rule for mixed states based on algorithmic randomness. In particular, we give a precise definition for the notion of mixed state. We then show that all of the alternative rules for both pure states and mixed states can be derived from a single postulate, called the principle of typicality, in a unified manner. We do this from the point of view of the many-worlds interpretation of quantum mechanics. Finally, we make an application of our framework to the BB84 quantum key distribution protocol in order to demonstrate how properly our framework works in a practical problem.
量子鍵配送 (QKD) は秘密鍵を配送する際に証明可能な安全性を担保する技術として1984年から注目を浴びてきた。2005年には QKD の安全性は、実際に配送される量子状態と配送されるべき理想的な量子状態との間のトレース距離により評価されるべきであるとされてきた。このときそのトレース距離には量子鍵配送に失敗する最大確率という解釈が与えられたが、2009年には H. P. Yuen により前記トレース距離にはそのような意味はないとする批判がなされ、以後、Yuen 自身と O. Hirota、 K. Kato, T. Iwakoshiらの批判を経て、2015年にはIwakoshiによりYuen の批判についての詳細な理由が解説された。その後、Yuen は2016年にこれまでの彼の批判をまとめた論文を提出し、量子鍵配送理論が証明可能な安全性を保証するために何が不足しているかについて指摘した。今回はその Yuen の論文の内容とそれ以降のトピックについて解説する。
量子計算能力を持たないAliceが量子計算能力を持つBobに量子計算を委託するプロトコルで、更にAliceの情報をBobに漏らさないブラインド性を持つものをBQC(Blind Quantum Computaiton)プロトコルと呼ぶ。BQCプロトコルにはBobの不正をAliceが検知できる検証可能性を持つものがある。しかし、一般には公開検証可能性を持たない。公開検証可能性がない場合、プロトコルの途中で不正があったときに、第三者がどちらが不正をしたのか検知することができない。実用性を考えれば公開検証可能性の付与は必要である。既存の研究成果として、Hondaが公開検証可能性を持たないBQCプロトコルであるFKプロトコルに第三者検証可能性を付与したプロトコルであるHondaプロトコルを提案した。しかしそのプロトコルの安全性は計算量仮定に基づくものであった。本論文ではFKプロトコルと同様に公開検証可能性を持たないBQCプロトコルであるHM(Hayashi-Morimae)プロトコルに公開検証可能性を付与した。Quantum de finettiの性質を利用することで、安全性を情報理論的に保つことに成功した。
Extension of the GLV/GLS Recomposition Method of Aranha et al.
◎キム・ウンギョン(梨花女子大学校)、ティブシ・メディ(NTTセキュアプラットフォーム研究所)
The GLV/GLS technique speeds up scalar multiplications on elliptic curves endowed with an efficiently computable endomorphism: a scalar multiplication by a full-size scalar becomes a double scalar multiplication by half-size scalars, which is significantly faster. However, this requires to first decompose the original scalar into an appropriate linear combination of half-size scalars using reduction in a low-dimensional lattice. Since a reduced basis of the lattice can be precomputed, this is typically fast, but it tends to leak a lot of side-channel information about the scalar.
To avoid this problem, Aranha et al. (ASIACRYPT 2014) proposed to use "recomposition" instead, i.e. choose the two half-sized scalars at random in a suitable interval, defining a corresponding full-size scalar implicitly. If the statistical distance to uniform of the distribution of that scalar is negligible, the recomposition method is secure and avoids any of the leakage of GLV/GLS decomposition.
The original paper obtained the statistical distance result for GLS curves of prime order. In this work, we extend their proof to GLS curves with a small cofactor, including twisted Edwards GLS curves. We also consider a possible generalization to certain GLV curves, such as the Bitcoin curve secp256k1.
Androidスマートフォンを用いたRho法によるECDLPへの並列攻撃
◎梶谷 翔馬(岡山大学)、野上 保之(岡山大学)、城市 翔(岡山大学)、Duquesne Sylvain(University of Rennes 1)、Austin Thomas(San Jose State University)
An approach to protecting sensitive items with maintaining data size
○Dedi Gunawan(Kanazawa University)、Masahiro Mambo(Kanazawa University)
Recently, sharing a database to other parties is becoming a common way with harvest more benefit from it. Since the database often contains sensitive information, it is important to protect the sensitive information before data is shared among parties. To guarantee the protection of the sensitive information, one tends to modify the database excessively. After such excessive modification other parties will distrust the released database and its data size is often reduce a lot. In this paper we propose a method for preserving sensitive value by data modification while at the same time decreasing the number of changes in database.
Deduplication based on Verifiable Hash Convergent Group Signcryption
◎Ei Mon Cho(Saitama University)、Takeshi Koshiba(Saitama University)
As cloud storage servers are becoming popular the shortage of disk space in the cloud becomes a problem. Deduplication is a method to control the disk size of the storage and most of the storage providers are finding more secure and efficient methods for their sensitive data. Recently, an interesting technique called signcryption has been proposed, in which both the properties of signature (ownership) and encryption are simultaneously implemented, with better performance than the traditional signature-then-encryption approach. According to the deduplication, we introduce a new method for a group of usersthat can eliminate redundant encrypted data owned by different
users. We propose a new primitive group signcryption for deduplication called verifiable hash convergent group signcryption (VHCS) by adding the properties of group signcryption and the verification facilities for the storage server (third party).
4F1-2
Efficient Hash-based One-Time Signature Scheme based on D-Tree Authentication Structure
○Minseon Lee(Graduate School of Informatics, Kyoto University)、Masayuki Abe(NTT Secure Platform Laboratories, NTT Corporation)、Tatsuaki Okamoto(NTT Secure Platform Laboratories, NTT Corporation)
In this paper, we propose a hash-based one-time signature (OTS) scheme which is more efficient than the Lamport-Diffie OTS scheme in terms of secret and public key sizes. Our construction is based on a new form of two binary hash trees, D-tree, that consists of the Merkle authentication tree and the Soshi and Waseda signature tree. Compared to the Lamport-Diffie OTS scheme, our scheme enjoys optimal public and secret-key sizes. Our scheme is proven to be secure under preimage and second-preimage resistance hash functions and pseudorandom generators. We can also apply this D-tree methodology to another OTS scheme, e.g., the Merkle OTS, to construct a more efficient OTS scheme.
4F1-3
A Constant-Size Signature Scheme with a Tighter Security Reduction from the CDH Assumption
◎梶田海成(東京工業大学)、藤崎英一郎(NTTセキュアプラットフォーム研究所)
We present a signature scheme with the tightest security reduction than ever known constant-size signature schemes from the Computational Diffie-Hellman (CDH) assumption.
To the best of our knowledge, the tightest security reduction so far from the CDH assumption to a constant-size signature scheme was O(q), shown by Hofheinz et al, where q is the number of signing queries.
They proposed a signature scheme by applying an error correcting code to Waters signatures.
In addition, they also proved that security loss of O(q) is optimal if signature schemes (including theirs) are “Re-Randomizable".
In this paper, we revisit a non-Re-Randomizable signature scheme proposed by Bohl et al.
Their proposal has compact public keys at the price of security reduction.
We observe that there is a tradeoff between public key size and the security reduction loss in their scheme. Moreover, by removing the usage of a pseudo-random generator and instead adopting a general transformation from extended random message attack security to chosen message attack security, we can obtain a signature scheme with security loss of O(q/d), where d is the number of group elements in a verification key, which is a-priori bounded polynomial in security parameter k.
近年,Infrastructure as a Service (IaaS)が注目を集めている.多くのIaaS環境では各資源にURLが割り当てられ,REST API経由で各資源へのアクセスや操作を行う.IaaSにおけるシステムに登録されていないユーザに対してアクセス権限を委譲する場合は,事前署名付きURL(Pre-Signed URLs, PSURL)が利用されている.PSURLとは,資源へのURLと有効期限とを連結した文字列に対し,資源保持者のデジタル署名やメッセージ認証符号を付与したPSURLトークンを生成する方式を指す.PSURLトークンの受領者は,資源に対する一時的なアクセス権限を委譲されたことになる.しかし既存のPSURLでは,悪意のある受領者がPSURLトークンを不正配信したとき,資源に対する不正アクセスが発生する懸念がある.本稿では,不正配信を抑制するPSURLとして,受領者指定事前署名付きURLを提案する.提案方式を用いた場合,不正配信を行うには受領者が指定されたPSURLトークンとともに受領者の秘密情報も配信する必要があるため,不正配信の抑制が期待できる.