石井 龍

• 博士課程

研究テーマ

• 暗号技術

Publications

• Ryu Ishii, Kyosuke Yamashita, Zihao Song, Yusuke Sakai, Tadanori Teruya, Takahiro Matsuda, Goichiro Hanaoka, Kanta Matsuura, Tsutomu Matsumoto. Constraints and Evaluations on Signature Transmission Interval for Aggregate Signatures with Interactive Tracing Functionality, IEICE Transactons on Fundamentals of Electronics, Communications and Computer Sciences, 2024 [detail]

abstract

Fault-tolerant aggregate signature (FT-AS) is a special type of aggregate signature that is equipped with the functionality for tracing signers who generated invalid signatures in the case an aggregate signature is detected as invalid. In existing FT-AS schemes (whose tracing functionality requires multi-rounds), a verifier needs to send a feedback to an aggregator for efficiently tracing the invalid signer(s). However, in practice, if this feedback is not responded to the aggregator in a sufficiently fast and timely manner, the tracing process will fail. Therefore, it is important to estimate whether this feedback can be responded and received in time on a real system. In this work, we measure the total processing time required for the feedback by implementing an existing FT-AS scheme, and evaluate whether the scheme works without problems in real systems. Our experimental results show that the time required for the feedback is 605.3 ms for a typical parameter setting, which indicates that if the acceptable feedback time is significantly larger than a few hundred ms, the existing FT-AS scheme would effectively work in such systems. However, there are situations where such feedback time is not acceptable, in which case the existing FT-AS scheme cannot be used. Therefore, we further propose a novel FT-AS scheme that does not require any feedback. We also implement our new scheme and show that a feedback in this scheme is completely eliminated but the size of its aggregate signature (affecting the communication cost from the aggregator to the verifier) is 144.9 times larger than that of the existing FT-AS scheme (with feedbacks) for a typical parameter setting, and thus has a trade-off between the feedback waiting time and the communication cost from the verifier to the aggregator with the existing FT-AS scheme.
• Kyosuke Yamashita, Ryu Ishii, Yusuke Sakai, Tadanori Teruya, Takahiro Matsuda, Goichiro Hanaoka, Kanta Matsuura, Tsutomu Matsumoto. Fault-Tolerant Aggregate Signature Schemes against Bandwidth Consumption Attack, IEICE Transactons on Fundamentals of Electronics, Communications and Computer Sciences, pp.1177-1188, 2023 [detail]

abstract

A fault-tolerant aggregate signature (FT-AS) scheme is a variant of an aggregate signature scheme with the additional functionality to trace signers that create invalid signatures in case an aggregate signature is invalid. Several FT-AS schemes have been proposed so far, and some of them trace such rogue signers in multi-rounds, i.e., the setting where the signers repeatedly send their individual signatures. However, it has been overlooked that there exists a potential attack on the efficiency of bandwidth consumption in a multi-round FT-AS scheme. Since one of the merits of aggregate signature schemes is the efficiency of bandwidth consumption, such an attack might be critical for multi-round FT-AS schemes. In this paper, we propose a new multi-round FT-AS scheme that is tolerant of such an attack. We implement our scheme and experimentally show that it is more efficient than the existing multi-round FT-AS scheme if rogue signers randomly create invalid signatures with low probability, which for example captures spontaneous failures of devices in IoT systems.
• Ryu Ishii, Kyosuke Yamashita, Yusuke Sakai, Tadanori Teruya, Takahiro Matsuda, Goichiro Hanaoka, Kanta Matsuura, Tsutomu Matsumoto. Aggregate Signature Schemes with Traceability of Devices Dynamically Generating Invalid Signatures, IEICE Transactons on Information and Systems, Vol.E105-D, No.11, pp.1845-1856, 2022 [detail]

abstract

Aggregate signature schemes enable us to aggregate multiple signatures into a single short signature. One of its typical applications is sensor networks, where a large number of users and devices measure their environments, create signatures to ensure the integrity of the measurements, and transmit their signed data. However, if an invalid signature is mixed into aggregation, the aggregate signature becomes invalid, thus if an aggregate signature is invalid, it is necessary to identify the invalid signature. Furthermore, we need to deal with a situation where an invalid sensor generates invalid signatures probabilistically. In this paper, we introduce a model of aggregate signature schemes with interactive tracing functionality that captures such a situation, and define its functional and security requirements and propose aggregate signature schemes that can identify all rogue sensors. More concretely, based on the idea of Dynamic Traitor Tracing, we can trace rogue sensors dynamically and incrementally, and eventually identify all rogue sensors of generating invalid signatures even if the rogue sensors adaptively collude. In addition, the efficiency of our proposed method is also sufficiently practical.
• Ryu Ishii, Kyosuke Yamashita, Zihao Song, Yusuke Sakai, Tadanori Teruya, Goichiro Hanaoka, Kanta Matsuura, and Tsutomu Matsumoto. Constraints and Evaluations on Signature Transmission Interval for Aggregate Signatures with Interactive Tracing Functionality, Lecture Notes in Computer Science (Attacks and Defenses for the Internet-of-Things 5th International Workshop, ADIoT 2022), Vol.13745, pp.51-71, 2022 [detail]

abstract

Fault-tolerant aggregate signature (FT-AS) is a special type of aggregate signature that is equipped with the functionality for tracing signers who generated invalid signatures in the case an aggregate signature is detected as invalid. In existing FT-AS schemes (whose tracing functionality requires multi-rounds), a verifier needs to send a feedback to an aggregator for efficiently tracing the invalid signer(s). However, in practice, if this feedback is not responded to the aggregator in a sufficiently fast and timely manner, the tracing process will fail. Therefore, it is important to estimate whether this feedback can be responded and received in time on a real system. In this work, we measure the total processing time required for the feedback by implementing an existing FT-AS scheme, and evaluate whether the scheme works without problems in real systems. Our experimental results show that the time required for the feedback is 605.3 ms for a typical parameter setting, which indicates that if the acceptable feedback time is significantly larger than a few hundred ms, the existing FT-AS scheme would effectively work in such systems. However, there are situations where such feedback time is not acceptable, in which case the existing FT-AS scheme cannot be used. Therefore, we further propose a novel FT-AS scheme that does not require any feedback. We also implement our new scheme and show that a feedback in this scheme is completely eliminated but the size of its aggregate signature (affecting the communication cost from the aggregator to the verifier) is 144.9 times larger than that of the existing FT-AS scheme (with feedbacks) for a typical parameter setting, and thus has a trade-off between the feedback waiting time and the communication cost from the verifier to the aggregator with the existing FT-AS scheme.
• 山下恭佑, 石井龍, 照屋唯紀, 坂井祐介, 花岡悟一郎, 松浦幹太, 松本勉. 追跡可能集約署名に対する潜在的な攻撃とその対処法に関する考察, 2022年暗号と情報セキュリティシンポジウム (SCIS2022）予稿集, 2022 [detail]

abstract

追跡可能集約署名(fault-tolerant aggregate signature schemes, Hartung ら, PKC ’16)とは， 集約署名に不正な署名が混入していた場合にその発信元を特定する能力を具備した方式である． 集約署名はセンサーネットワークや効率的なルーティングへの応用が期待されている暗号機能であり， そのためにも不正者特定は重要な機能として注目を浴びている． 追跡可能集約署名の一般的構成は既にいくつか提案されているが， 本稿では石井ら(ACNS SCI ’21)の提案した動的な不正者に耐性を持つマルチラウンドな追跡可能集約署名の拡張を考える． 彼らは安全性の定式化のために不正者が毎ラウンド少なくとも 1 人は現れるモデルを考えた． そのような仮定は先述のアプリケーションへの適用を考える際には非現実的であるため， 我々は不正者が不正をしないラウンドを許容するモデルを検討した． その結果，追跡可能集約署名を現実に利用する場合に潜在的に起こり得る効率性に対する新たな攻撃の可能性を発見し， それに効率的に対処するためのアルゴリズムを提案した．
• 石井龍, 山下恭佑, 宋子豪, 照屋唯紀, 坂井祐介, 花岡悟一郎, 松浦幹太, 松本勉. 対話的追跡機能付き集約署名における署名送信間隔に関する制約と評価, 2022年暗号と情報セキュリティシンポジウム (SCIS2022）予稿集, 2022 [detail]

abstract

集約署名は，複数のデジタル署名を1 つに集約する方式であり，全体署名長および署名検証時間の短縮という効率性を持つが， 不正署名を1 つでも含んで集約すると集約署名は不正となり，検証者はどのユーザやデバイスが不正署名を生成したかを特定できない． 対話的追跡機能付き集約署名は，多数のデバイスが定期的に署名付きデータを送信するシステムで， 時々刻々と変わる不正署名の生成デバイスを，集約者と検証者の対話によって特定する方式である． しかし，集約者は，デバイスからの署名を集約するために，検証者からのフィードバックを待つ必要があるため， システムの規模に応じて署名送信間隔に制約が生じる． 本研究では，集約者がフィードバック待機なしに集約署名を作成できる方式としてSequential Traitor Tracing を 構成要素とする対話的追跡機能付き集約署名を提案する． また，提案方式と既存方式であるDynamic Traitor Tracing を用いた対話的追跡機能付き集約署名について理論評価 および実装シミュレーションによる評価を行う.
• Ryu Ishii, Kyosuke Yamashita, Yusuke Sakai, Takahiro Matsuda, Tadanori Teruya, Goichiro Hanaoka, Kanta Matsuura, and Tsutomu Matsumoto. Aggregate Signature with Traceability of Devices Dynamically Generating Invalid Signatures, Lecture Notes in Computer Science (2nd ACNS Workshop on Secure Cryptographic Implementation: 2nd ACNS SCI Workshop), Vol.12809, pp.378-396, 2021 [detail]

abstract

Aggregate signature schemes enable us to aggregate multiple signatures into a single short signature. One of its typical applications is sensor networks, where a large number of users and devices measure their environments, create signatures to ensure the integrity of the measurements, and transmit their signed data. However, if an invalid signature is mixed into aggregation, the aggregate signature becomes invalid, thus if an aggregate signature is invalid, it is necessary to identify the invalid signature. Furthermore, we need to deal with a situation where an invalid sensor generates invalid signatures probabilistically. In this paper, we introduce a model of aggregate signature schemes with interactive tracing functionality that captures such a situation, and define its functional and security requirements and propose aggregate signature schemes that can identify all rogue sensors. More concretely, based on the idea of Dynamic Traitor Tracing, we can trace rogue sensors dynamically and incrementally, and eventually identify all rogue sensors of generating invalid signatures even if the rogue sensors adaptively collude. In addition, the efficiency of our proposed method is also sufficiently practical.
• 石井 龍, 照屋 唯紀, 坂井 祐介, 松田 隆宏, 花岡 悟一郎, 松浦 幹太, 松本 勉. 動的に不正署名を生成するデバイスを追跡可能な集約署名, 2021年暗号と情報セキュリティシンポジウム（SCIS2021）予稿集, 2021 [detail]

abstract

集約署名は，複数の署名を1つの署名に集約でき，全体署名長および署名検証時間の短縮という 効率性を持つため，センサーネットワークなど多数のユーザやデバイスが署名を送信するシステムでの 活用が期待されている． しかし，不正署名を 1 つでも含んで集約すると集約署名は不正となり， 検証者はどのユーザやデバイスが不正署名を生成したかを特定できない． さらに，上記のセンサー ネットワーク等の応用では，多数のデバイスが定期的にデータと署名を送信し，かつ (故障などにより) 不正署名を生成するデバイスが時々刻々と変わることが自然に想定される． 本研究では，そのような 状況を捉えた追跡可能集約署名のモデルを導入し，その機能的要件と安全性要件の定義を行う． さらに，(通常の) 集約署名とDynamic Traitor Tracingを用いた一般的構成を提案する．

五十嵐 太一

• 修士課程

研究テーマ

• ブロックチェーン, マルウェア

Publications

• Taichi Igarashi, Kanta Matsuura. Scam Token Detection Based on Static Analysis Before Contract Deployment, The 28th International Conference on Financial Cryptography and Data Security: FC2024, 8th Workshop on Trusted Smart Contracts: WTSC24, 2024 [detail]

abstract

In recent years, the number of crimes using smart contracts has increased. In particular, fraud using tokens, such as rug-pull, has become an ignorable issue in the field of decentralized finance because a lot of users have been scammed. Therefore, constructing a detection system for scam tokens is an urgent need. Existing methods are based on machine learning, and they use transaction and liquidity data as features. However, they cannot completely remove the risk of being scammed because these features can be extracted after scam tokens are deployed to blockchain. In this paper, we propose a scam token detection system based on static analysis. In order to detect scam tokens before deployment, we utilize code-based data, such as bytecodes and opcodes, because they can be obtained before contract deployment. Since N-gram includes information regarding the order of code sequences and scam tokens have the specific order of code-based data, we adopt N-gram of them as features. Furthermore, for the purpose of achieving a high detection performance, each feature is categorized into a scam-oriented feature or benign-oriented one to make differences in the values of feature vectors between scam and benign token. Our results show the effectiveness of code-based data for detection by achieving a higher F1-score compared to the methods of another field of fraud detection in Ethereum based on code-based data. In addition, we also confirmed that the position of effective code for detection is near the start position of runtime code in our experiments.
• 五十嵐太一, 松浦幹太. バイト列に着目した詐欺トークンコントラクトの検知, 2023年コンピュータセキュリティシンポジウム(CSS2023)予稿集, pp.735-742, 2023 [detail]

abstract

ブロックチェーン上のアプリケーションに応用されるスマートコントラクトを利用した犯罪が増加しており, 特にトークンコントラクトを用いた詐欺が問題となっているため, その検知が急務である. 従来 の詐欺トークンコントラクト検知に関する研究は, トランザクションデータと流動性の情報を基に機械学習によって検知を行っているが, これらの情報は詐欺トークンが使用されてから得られる情報であるため, ユーザが詐欺にあう危険性が高い. 一方, トークンコントラクトのコード情報は, ブロックチェーン上に展開される前に得られる情報であるが, コード情報に基づいた詐欺トークンコントラクト検知手法は存在しない. よって, 本稿では詐欺トークンコントラクトを, コントラクトのコード情報に着目し, バイト列から作成した特徴量と機械学習により検知を行う手法を提案する. 本手法は, Ethereum のエクスプローラであるEtherscan から得た詐欺トークンコントラクトと 正規のトークンコンラクトを用いた実験において92.9 % の正解率を記録し, コード情報が詐欺トークンコントラクトの検知に有効であることを示した.
• Taichi Igarashi, Hiroya Kato, Iwao Sasase, Kanta Matsuura. A Realtime IoT Malware Classification System Based on Pending Samples, 2023 IEEE International Conference on Communications (ICC): Communication and Information System Security Symposium (ICC2023), pp.4380-4385, 2023 [detail]

abstract

With the rapid growth of Internet of Things (IoT) devices, a lot of IoT malware has been created, and the security against IoT malware, especially the family classification, has become a more important issue. There exist three requirements which classification systems must achieve: detection of new families, precise classification for sequential inputs, and being independent of computer architectures. However, existing methods do not satisfy them simultaneously. In this paper, we propose a realtime IoT malware classification system based on pending samples. In order to detect new families and to classify sequential inputs precisely, we introduce the concept of "pending samples". This concept is useful when heterogeneous inputs which are difficult to classify instantly come into the system. This is because the system can postpone classifying them until similar samples come. Once similar samples are gathered, we regard these samples as a new cluster, meaning that detecting new families is achieved. Moreover, we use printable strings to satisfy the requirement of being independent of architectures because strings are common among different architectures. Our results show the ability to detect new families demonstrated by finding new clusters after applying our algorithm to the initial clusters. Furthermore, our new clustering algorithms achieves a 0.130 higher V-measure compared to the k-means algorithm, which is the representative clustering algorithm.
• Taichi Igarashi, Kanta Matsuura. A Refined Classification of Malicious Smart Contract, Lecture Notes in Computer Science (The 27th International Conference on Financial Cryptography and Data Security: FC2023, Posters presentation), 2023 [detail]

abstract

With the rapid growth of blockchain, smart contract, which is the computer program executed on blockchain systems, has played an important role especially in the trade of cryptcurrency. However, smart contracts are utilized to commit some crimes or attacks because they often hold a large amount of cryptcurrency. Thus, to enhance the security of smart contract is an urgent need. There exists three types of crimes regarding smart contract, namely, attack using vulnerabilities, trade between criminals, and fraud. Some researchers reported that many smart contracts have vulnerabilities, and attackers exploit them to steal cryptcurrency or attack system itself like DoS attack. Another type of crime is to trade criminal information for rewards between criminals using smart contracts. Especially in recent years, fraud acts including phishing have become a big problem on blockchain, and smart contracts are utilized to support them. These crimes have occured due to the presense of Malicious Smart Contract (MSC). Thus, the systems which detect MSC are needed to prevent these crimes. Though MSC is a smart contract which shows malicious activities, there does not exist a clear definition. As a result, the word "malicious" is used in different ways among researchers. In this situation, it is difficult to detect whole MSCs. This is because different types of MSC have different malicious activities, meaning that detection systems corresponded to each type of MSC are needed. Therefore, the classification of MSC is required. Some researchers classify MSC into two types: Vulnerable Smart Contract (VSC) related to vulnerability and Criminal Smart Contract (CSC) related to trade between criminals. In this classification model, however, there does not exist a type of MSC corresponded to fraud activities. To overcome this problem, we propose a new standpoint that MSC should be classified into VSC, CSC and Fraudulent Smart Contract (FSC), which supports frauds. By introducing this standpoint, to detect whole MSCs will be realized by constructing detection systems of each MSC simultaneously. While there exists a lot of works of detecting VSC and a few CSC works have also proposed, a field of FSC detection has not developed. Some researchers proposed detection systems of malicious accounts. In this field, "malicious" means fraud activities. Thus, we consider that these kinds of works are similar to detection of FSC and can be applied. These studies mainly use machine learning to detect malicious accounts. However, their models only consider graph-based features constructed from external transaction and address data, and not focus on other features. Therefore, as a future work, considering internal transaction and smart contract code-based feature like opcode is worth working.
• 五十嵐太一、松浦幹太. スマートコントラクトにおけるセキュリティに関する調査, 2023年暗号と情報セキュリティシンポジウム (SCIS2023）予稿集, 2023 [detail]

abstract

近年のブロックチェーンの発展に伴い, ブロックチェーンシステムの中で実行される コンピュータプログラムであるスマートコントラクトは, 特に暗号資産に関する取引を 行う際に重要な役割を担っている. しかし, スマートコントラクトがしばしば悪性な ユーザの攻撃対象となることや犯罪に利用される事例が発生しており, その安全性を高めることが急務である. 本稿では, スマートコントラクトを利用した攻撃や犯罪と, それらに利用されるMalicious Smart Contract(MSC)についての研究を紹介する. 従来の研究では, MSCはVulnerable Smart Contract とCriminal Smart contractの 二種類に分類されており, これらに対する研究動向と全体的な課題を示す. 特に,詐欺行為を行うような, 二種類の分類では含まれない悪性なスマートコントラクトが存在するため, 従来の分類ではこのようなMSCを精度良く検知することが困難である. よって, 従来の分類に Fraudulent Smart Contractを加えた三種類の分類の立場を新たに提案することで, 課題を解決するための方針を示す.

澤田 悠太郎

• 修士課程

研究テーマ

• ブロックチェーン技術

宮前 剛

• 博士課程

研究テーマ

• ブロックチェーン

Publications

• 宮前 剛, 松浦 幹太. ゼロ知識性の概念を応用したブロックチェーン匿名通貨のプライバシー解析, 日本セキュリティ・マネジメント学会(JSSM) 第35回全国大会, 2022
• Takeshi Miyamae, Kanta Matsuura. Coin Transfer Unlinkability Under the Counterparty Adversary Model, Ledger, Vol.7, pp.17-34, 2022 [detail]

abstract

Unlinkability is a crucial property of cryptocurrencies that protects users from deanonymization attacks. However, currently, even anonymous cryptocurrencies do not necessarily attain unlinkability under specific conditions. For example, Mimblewimble, which is considered to attain coin unlinkability using its transaction kernel offset technique, is vulnerable under the assumption that privacy adversaries can send their coins to or receive coins from the challengers. This paper first illustrates the privacy issue in Mimblewimble that could allow two colluded adversaries to merge a person's two independent chunks of personally identifiable information (PII) into a single PII. To analyze the privacy issue, we formulate unlinkability between two sets of objects and a privacy adversary model in cryptocurrencies called the counterparty adversary model. On these theoretical bases, we define an abstract model of blockchain-based cryptocurrency transaction protocols called the coin transfer system, and unlinkability over it called coin transfer unlinkability (CT-unlinkability). Furthermore, we introduce zero-knowledgeness for the coin transfer systems to propose a method to easily prove the CT-unlinkability of cryptocurrency transaction protocols. Finally, we prove that Zerocash is CT-unlinkable by using our proving method to demonstrate its effectiveness.
• 宮前剛，松浦幹太. ブロックチェーンを応用した暗号資産の匿名性に関する一考察, 2020年暗号と情報セキュリティシンポジウム（SCIS2020）予稿集, 2020 [detail]

abstract

本稿では, まず, ブロックチェーンを応用した暗号資産の匿名性に関する評価指標の意味と関係を整理する. 特に, 関連付け困難性(unlinkability)の評価指標としての汎用性を示す. 次に, 暗号資産の関連付け困難性をフェアに評価するために, 暗号資産の特徴に基づいて四つの関連付け攻撃モデルおよびそれぞれの攻撃モデルに対応する安全性を定義する. 最後に, 代表的な匿名暗号資産に対して本稿で定義した関連付け攻撃安全性評価を行い, それらの匿名暗号資産の匿名性を比較評価する.
• 宮前剛，松浦幹太. MWmessage: 追跡困難メッセージングを実現するためのMimblewimbleの拡張, 2019年コンピュータセキュリティシンポジウム（CSS2019）予稿集, pp.WEB, 2019 [detail]

abstract

暗号資産の代表であるBitcoinは、トランザクション分析技術の急速な進歩に伴い、追跡困難性が低下している。 そのような状況の中、追跡困難性とスケーラビリティを両立する匿名暗号資産プロトコルMimblewimbleが 注目されている。 しかし、現時点でMimblewimbleはメッセージングに関して多くの課題を抱えている。 そこで、 我々は、Mimblewimbleのメッセージングの課題を解決するために、Mimblewimble自身を拡張して ブロックチェーン形式の追跡困難メッセージングを実現するMWmessageを提案する。 本稿では、 まずMimblewimbleの仕組みと特徴およびそのメッセージングに関する課題を整理した上で、 課題を解決するためのMWmessage の仕組みを説明する。 特に、メッセージの改竄を困難にするための メッセージハッシュの仕組みと、Mimblewimbleのスケーラビリティを犠牲にすることなく追跡困難メッセージングを 実現するためのメッセージへの有効期限付与の仕組みに焦点を当てる。 最後に、MWmessageを一般の 匿名メッセージングシステムとして机上評価する。

Kittiphop Phalakarn

• 博士課程

研究テーマ

• 暗号技術

Publications

• Kittiphop Phalakarn, Nuttapong Attrapadung, Kanta Matsuura. Efficient Oblivious Evaluation Protocol and Conditional Disclosure of Secrets for DFA, Lecture Notes in Computer Science (Applied Cryptography and Network Security - ACNS 2022 - 20th International Conference on Applied Cryptography and Network Security), Vol.13269, No., pp.605-625, 2022 [detail]

abstract

In oblivious finite automata evaluation, one party holds a private automaton, and the other party holds a private string of characters. The objective is to let the parties know whether the string is accepted by the automaton or not, while keeping their inputs secret. The applications include DNA searching, pattern matching, and more. Most of the previous works are based on asymmetric cryptographic primitives, such as homomorphic encryption and oblivious transfer. These primitives are significantly slower than symmetric ones. Moreover, some protocols also require several rounds of interaction. As our main contribution, we propose an oblivious finite automata evaluation protocol via conditional disclosure of secrets (CDS), using one (potentially malicious) outsourcing server. This results in a constant-round protocol, and no heavy asymmetric-key primitives are needed. Our protocol is based on a building block called "an oblivious CDS scheme for deterministic finite automata" which we also propose in this paper. In addition, we propose a standard CDS scheme for deterministic finite automata as an independent interest.
• Kittiphop Phalakarn, Vorapong Suppakitpaisarn, Nuttapong Attrapadung, Kanta Matsuura. Evolving Homomorphic Secret Sharing for Hierarchical Access Structures, Lecture Notes in Computer Science (Advances in Information and Computer Security - IWSEC 2021 - 16th International Workshop on Security), Vol.12835, pp.77-96, 2021 [detail]

abstract

Secret sharing is a cryptographic primitive that divides a secret into several shares, and allows only some combinations of shares to recover the secret. As it can also be used in secure multi-party computation protocol with outsourcing servers, several variations of secret sharing are devised for this purpose. Most of the existing protocols require the number of computing servers to be determined in advance. However, in some situations we may want the system to be "evolving". We may want to increase the number of servers and strengthen the security guarantee later in order to improve availability and security of the system. Although evolving secret sharing schemes are available, they do not support computing on shares. On the other hand, "homomorphic" secret sharing allows computing on shares with small communication, but they are not evolving. As the contribution of our work, we give the definition of "evolving homomorphic" secret sharing supporting both properties. We propose two schemes, one with hierarchical access structure supporting multiplication, and the other with partially hierarchical access structure supporting computation of low degree polynomials. Comparing to the work with similar functionality of Choudhuri et al. (IACR ePrint 2020), our schemes have smaller communication costs.
• Kittiphop Phalakarn, Vorapong Suppakitpaisarn, Nuttapong Attrapadung, Kanta Matsuura. Constructive t-secure Homomorphic Secret Sharing for Low Degree Polynomials, Lecture Notes in Computer Science (Progress in Cryptology - INDOCRYPT 2020 - 21st International Conference on Cryptology in India), Vol.12578, pp.763-785, 2020 [detail]

abstract

This paper proposes t-secure homomorphic secret sharing schemes for low degree polynomials. Homomorphic secret sharing is a cryptographic technique to outsource the computation to a set of servers while restricting some subsets of servers from learning the secret inputs. Prior to our work, at Asiacrypt 2018, Lai, Malavolta, and Schroder proposed a 1-secure scheme for computing polynomial functions. They also alluded to t-secure schemes without giving explicit constructions; constructing such schemes would require solving set cover problems, which are generally NP-hard. Moreover, the resulting implicit schemes would require a large number of servers. In this paper, we provide a constructive solution for threshold-t structures by combining homomorphic encryption with the classic secret sharing scheme for general access structure by Ito, Saito, and Nishizeki. Our scheme also quantitatively improves the number of required servers from O(t^2) to O(t), compared to the implicit scheme of Lai et al. We also suggest several ideas for future research directions.

林田 淳一郎

• 博士課程

研究テーマ

• 暗号技術

Publications

• Junichiro Hayata, Jacob C. N. Schuldt, Goichiro Hanaoka, Kanta Matsuura. On Private Information Retrieval Supporting Range Queries, International Journal of Information Security (2023), pp.1-19, 2023 [detail]

abstract

Private information retrieval (PIR) allows a client to retrieve data from a database without the database server learning what data are being retrieved. Although many PIR schemes have been proposed in the literature, almost all of these focus on retrieval of a single database element, and do not consider more flexible retrieval queries such as basic range queries. Furthermore, while practically-oriented database schemes aiming at providing flexible and privacy-preserving queries have been proposed, to the best of our knowledge, no formal treatment of range queries has been considered for these. In this paper, we firstly highlight that a simple extension of the standard PIR security notion to range queries is insufficient in many usage scenarios, and propose a stronger security notion aimed at addressing this. We then show a simple generic construction of a PIR scheme meeting our stronger security notion, and propose a more efficient direct construction based on function secret sharing while the former has a round complexity logarithmic in the size of the database, the round complexity of the latter is constant. After that, we report on the practical performance of our direct construction. Finally, we extend the results to the case of multi-dimensional databases and show the construction of PIR scheme supporting multi-dimensional range queries. The communication round complexity of our scheme is O(klogn) in worst case, where n is the size of database and k is the number of elements retrieved by the query.
• 浅野泰輝, 林リウヤ, 林田淳一郎, 松田隆宏, 山田翔太, 勝又秀一, 坂井祐介, 照屋唯紀, シュルツヤコブ, アッタラパドゥンナッタポン, 花岡悟一郎, 松浦幹太, 松本勉. 「モノの電子署名」の複数物体への拡張, Extension of "Signature for Objects" to Multiple Objects, 2022年暗号と情報セキュリティシンポジウム (SCIS2022) 予稿集, 2022 [detail]

abstract

近年の偽造品や海賊版製品の取引の増加に伴い，取引の正当性を検証可能にする技術の必要性が高まっており，その1つとして電子署名がある． しかしながら，従来の電子署名方式では，電子データではない物体そのものに対しての署名作成はできない． そこで，林ら（CSS2021）により，物体の加工や電子データへの変換といった物理的な操作を取り扱うことが可能な枠組みを定式化することで， 任意の物体を対象とした「モノの電子署名」が提唱された． しかし，「モノの電子署名」は一物体のみに対して加工，変換を施すことを想定しているため， 本稿ではこの枠組みを複数物体においても動作するよう拡張し，より実システムに近い形での署名方式を与える． 特に，サプライチェーンの各ステップにおいて物体の生成，加工，組み合わせのいずれかが可能であるという状況のもとで， 各物体に対してそれがどのような変遷をたどってきたかを保証する署名を付与できるモデルを導入する． さらに，その安全性定義，およびAppend-Only署名と集約署名を用いた一般的構成を提案し，簡単な概念実証も行う．
• 林リウヤ, 浅野泰輝, 林田淳一郎, 松田隆宏, 山田翔太, 勝又秀一, 坂井祐介, 照屋唯紀, シュルツヤコブ, アッタラパドゥンナッタポン, 花岡悟一郎, 松浦幹太, 松本勉. モノの秘匿性を考慮した「モノの電子署名」. "Signature ofr Objects" with Object Privacy, 2022年暗号と情報セキュリティシンポジウム (SCIS2022) 予稿集, 2022 [detail]

abstract

物体の偽造に対する安全性の暗号学的な評価手法として「モノの電子署名」が提案されている． これは電子署名方式の一種であるが，従来の電子署名とは異なりメッセージだけでなく物体にも署名できる方式となっている． ここでは安全性として偽造不可能を表す EUF-COA が定義されている． モノの電子署名方式の特徴の一つに，署名された物体は物理空間で送られ，署名自体はサイバー空間で送信されることが挙げられる． ここで，署名を入手した悪意のある人が署名単体から対応する物体を特定できてしまうと， その署名を用いて検証が通過するような，署名されていない物体を生成可能である恐れがある． このとき生成された物体は検証者に正当なものとみなされてしまう． これを防ぐために新たな安全性としてモノの秘匿性を定義する． モノの秘匿性は署名単体から対応する物体が特定できないという安全性を表す． 本稿ではモノの秘匿性の安全性定義を行い，EUF-COA 安全性とモノの秘匿性の両方を満たす構成を示す． 具体的には，EUF-COA 安全性は基盤とする電子署名方式における EUF-CMA 安全性と確率的ハッシュにおける衝突困難性に帰着でき， モノの秘匿性は Relational Hash における偽造不可能性に帰着できることを示す．
• 林リウヤ, 浅野泰輝, 林田淳一郎, 松田隆宏, 山田翔太, 勝又秀一, 坂井祐介, 照屋唯紀, シュルツヤコブ, アッタラパドゥンナッタポン, 花岡悟一郎, 松浦幹太, 松本勉. モノの電子署名：物体に署名するための一検討, Signature for Objects: Formalization, Security Definition, and Provably Secure Constructions, 2021年コンピュータセキュリティシンポジウム（CSS2021）予稿集, pp.740-747, 2021 [detail]

abstract

従来の電子署名方式では，電子データでない物体に対して電子署名を作成することができない． そこで， 物体への操作を暗号学的に定式化することで， 任意の物体を対象として作成が可能な電子署名である「モノの電子署名」を提案する． 物体への操作は，物体を加工して新たな物体を作り出す操作であるコマンドと， 物体を加工することなく電子データに変換する操作であるセンシングの2つに分けられる． このうちセンシングは同じ物体からであっても実行されるたびに異なる電子データを返すが， それに左右されることなく物体に対する有効な電子署名を作成できる方式が構成可能である． 本稿では，この方式が満たすべき安全性定義とそれを満たす構成を示す． また，その構成の安全性が 基盤とする電子署名方式における選択文書攻撃に対する存在的偽造不可(EUF-CMA)に帰着できることも示す．
• Junichiro Hayata, Jacob C. N. Schuldt, Goichiro Hanaoka, Kanta Matsuura. On Private Information Retrieval Supporting Multi-dimensional Range Queries, 2021年暗号と情報セキュリティシンポジウム（SCIS2021）予稿集, 2021 [detail]

abstract

Private information retrieval (PIR) allows a client to retrieve data from a database without the database server learning what data is being retrieved. Most of the existing PIR schemes consider searching simple one-dimensional databases and the supported query types are often limited to index queries only, which retrieve a single element from the databases. However, most real-world applications require more complex databases and query types. In this paper, we build upon the notion of query indistinguishability by Hayata et al. (ESORICS2020), and formalize query indistinguishability for multi-dimensional range queries. We then give a construction of a secure multi-server scheme based on function secret sharing. This is the first instantiation of a PIR scheme supporting multi-dimensional range queries while being capable of hiding the type of query being made and, in the case of multi-dimensional range queries, the number of elements retrieved in each query, when considering a stream of queries.
• Junichiro Hayata, Fuyuki Kitagawa, Yusuke Sakai, Goichiro Hanaoka, Kanta Matsuura. Equivalence between Non-Malleability against Replayable CCA and Other RCCA-Security Notions, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, Vol.E104-A, No.1, pp.89-103, 2021 [detail]

abstract

Replayable chosen ciphertext (RCCA) security was introduced by Canetti, Krawczyk, and Nielsen (CRYPTO'03) in order to handle an encryption scheme that is "non-malleable except tampering which pre- serves the plaintext." RCCA security is a relaxation of CCA security and a useful security notion for many practical applications such as authentication and key exchange. Canetti et al. defined non-malleability against RCCA (NM-RCCA), indistinguishability against RCCA (IND-RCCA), and universal composability against RCCA (UC-RCCA). Moreover, they proved that these three security notions are equivalent when considering a PKE scheme whose plaintext space is super-polynomially large. Among these three security notions, NM-RCCA seems to play the central role since RCCA security was introduced in order to capture "non-malleability except tampering which preserves the plaintext." However, their definition of NM-RCCA is not a natural extension of that of original non-malleability, and it is not clear whether their NM-RCCA captures the requirement of original non- malleability. In this paper, we propose definitions of indistinguishability- based and simulation-based non-malleability against RCCA by extending definitions of original non-malleability. We then prove that these two notions of non-malleability and IND-RCCA are equivalent regardless of the size of plaintext space of PKE schemes.
• Junichiro Hayata, Jacob C. N. Schuldt, Goichiro Hanaoka, Kanta Matsuura. On Private Information Retrieval Supporting Range Queries, Lecture Notes in Computer Science (Computer Security - ESORICS 2020 - 25th European Symposium on Research in Computer Security, Proceedings, Part II), Vol.12309, pp.674-694, 2020 [detail]

abstract

Private information retrieval (PIR) allows a client to retrieve data from a database without the database server learning what data is being retrieved. Although many PIR schemes have been proposed in the literature, almost all of these focus on retrieval of a single database element, and do not consider more flexible retrieval queries such as basic range queries. Furthermore, while practically-oriented database schemes aiming at providing flexible and privacy-preserving queries have been proposed, to the best of our knowledge, no formal treatment of range queries has been considered for these. In this paper, we firstly highlight that a simple extension of the standard PIR security notion to range queries, is insufficient in many usage scenarios, and propose a stronger security notion aimed at addressing this. We then show a simple generic construction of a PIR scheme meeting our stronger security notion, and propose a more efficient direct construction based on function secret sharing - while the former has a round complexity logarithmic in the size of the database, the round complexity of the latter is constant. Finally, we report on the practical performance of our direct construction.
• 林田淳一郎, Jacob C. N. Schuldt, 花岡悟一郎, 松浦幹太. A Private Information Retrieval Scheme Supporting Range Queries, 2020年暗号と情報セキュリティシンポジウム（SCIS2020）予稿集, 2020 [detail]

abstract

Private information retrieval (PIR) allows a client to retrieve data from a database without the database server learning what data is being retrieved. Although many PIR schemes have been proposed in the literature, almost all of these focus on retrieval of a single database element, and do not consider more exible retrieval queries such as basic range queries. In addition to this, to the best of our knowledge, all PIR schemes that do support range queries, are not formally shown secure. In this paper, we formalize a security model for PIR schemes that support range queries and construct a secure multi-server scheme based on function secret sharing.
• Junichiro Hayata, Masahito Ishizaka, Yusuke Sakai, Goichiro Hanaoka, Kanta Matsuura. Generic Construction of Adaptively Secure Anonymous Key-Policy Attribute-Based Encryption from Public-Key Searchable Encryption, IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences, Vol.E103-A, No.1, pp.107-113, 2020 [detail]

abstract

Public-key encryption with keyword search (PEKS) is a cryptographic primitive that allows us to search for particular keywords over ciphertexts without recovering plaintexts. By using PEKS in cloud services, users can outsource their data in encrypted form without sacrificing search functionality. Concerning PEKS that can specify logical disjunctions and logical conjunctions as a search condition, it is known that such PEKS can be (generically) constructed from anonymous attribute-based encryption (ABE). However, it is not clear whether it is possible to construct this types of PEKS without using ABE which may require large computational/communication costs and strong mathematical assumptions. In this paper, we show that ABE is crucial for constructing PEKS with the above functionality. More specifically, we give a generic construction of anonymous key-policy ABE from PEKS whose search condition is specified by logical disjunctions and logical conjunctions. Our result implies such PEKS always requires large computational/communication costs and strong mathematical assumptions corresponding to those of ABE.
• Junichiro Hayata, Fuyuki Kitagawa, Yusuke Sakai, Goichiro Hanaoka, Kanta Matsuura. Equivalence Between Non-malleability Against Replayable CCA and Other RCCA-Security Notions, Lecture Notes in Computer Science (Advances in Information and Computer Security, The 14th International Workshop on Security: IWSEC2019), Vol.11689, pp.253-272, 2019 [detail]

abstract

Replayable chosen ciphertext (RCCA) security was introduced by Canetti, Krawczyk, and Nielsen (CRYPTO 03) in order to handle an encryption scheme that is "non-malleable except tampering which preserves the plaintext". RCCA security is a relaxation of CCA security and a useful security notion for many practical applications such as authentication and key exchange. Canetti et al. defined non-malleability against RCCA (NM-RCCA), indistinguishability against RCCA (IND-RCCA), and universal composability against RCCA (UC-RCCA). Moreover, they proved that these three security notions are equivalent when considering a PKE scheme whose plaintext space is super-polynomially large. Among these three security notions, NM-RCCA seems to play the central role since RCCA security was introduced in order to capture "non-malleability except tampering which preserves the plaintext." However, their definition of NM-RCCA is not a natural extension of that of classical non-malleability, and it is not clear whether their NM-RCCA captures the requirement of classical non-malleability. In this paper, we propose definitions of indistinguishability-based and simulation-based non-malleability against RCCA by extending definitions of classical non-malleability. We then prove that these two notions of non-malleability and IND-RCCA are equivalent regardless of the size of plaintext space of PKE schemes.
• 林田淳一郎, 北川冬航, 坂井祐介, 花岡悟一郎, 松浦幹太. 公開鍵暗号のReplayable CCA環境下での安全性概念間の等価性について, Relations among Notions of Security under Replayable CCA Environment for Public-Key Encryption, 2019年暗号と情報セキュリティシンポジウム（SCIS2019）予稿集, 2019 [detail]

abstract

Replayable CCA (RCCA) 安全性はCanetti らによって提案された安全性であり, CCA 安全性を緩めた安全性として知られている. このRCCA 安全性は, 暗号文の再ランダム化を許す定式化がされており, 認証や鍵交換などで使用される. 彼らはIND-RCCA, UC-RCCA とNM-RCCA を定義し, それらの等価性を証明した. 彼らの結果を用いることによって, ある公開鍵暗号方式がIND-RCCA 安全であることを証明できれば, その方式がRCCA 環境下で汎用結合可能性と頑強性のどちらも同時に満たす ことが保証される. 従って, 彼らの結果はRCCA 環境下において複数の安全性の取り扱いを容易にしたように見えた. しかし, 彼らのNM-RCCA の定式化はNM-CCA の自然な拡張になっておらず, その妥当性が不明である. そのため, IND-RCCA 安全性を証明することでRCCA 環境下での頑強性を同時に示せるかどうかは明らかではない. このような問題が生じているため, RCCA 環境下におけるより頑強性の直感を捉えた定式化を行う必要がある. 本稿では, RCCA 環境下におけるシミュレーションベースの頑強性及び, 識別不可能性ベースの頑強性の定式化を行い, その関係性を明らかにする.
• Junichiro Hayata, Masahito Ishizaka, Yusuke Sakai, Goichiro Hanaoka, Kanta Matsuura. Generic Construction of Adaptively Secure Anonymous Key-Policy Attribute-Based Encryption from Public-Key Searchable Encryption, Proceeding of the 2018 International Symposium on Information Theory and its Applications (ISITA2018), pp.739-743, 2018 [detail]

abstract

Public-key encryption with keyword search (PEKS) is a cryptographic primitive that allows us to search encrypted data for those of including particular keywords without decrypting them. PEKS is expected to be used for enhancing security of cloud storages. It is known that PEKS can be constructed from anonymous identity-based encryption (IBE), anonymous attribute-based encryption (ABE) and so on. It is believed that it is difficult to construct PEKS schemes that can specify a flexible search condition such as logical disjunctions and logical conjunctions from weaker cryptographic tools than ABE. However, this intuition has not been rigorously justified. In this paper, we formally prove it by constructing key-policy ABE from PEKS for monotone boolean formulas.
• 林田淳一郎, 石坂理人, 坂井祐介, 花岡悟一郎, 松浦幹太. 公開鍵型検索可能暗号を用いた適応的安全な匿名鍵ポリシー型属性ベース暗号の一般的構成, Generic Construction of Adaptively Secure Anonymous Key-Policy Attribute-Based Encryption from Public-Key Searchable Encryption, 2018年暗号と情報セキュリティシンポジウム（SCIS2018）予稿集, USBメモリ, 2018 [detail]

abstract

検索可能暗号は, 暗号化されたデータから特定のキーワードを含むデータのみを検索することができる手法である. 検索可能暗号には共通鍵型と公開鍵型の方式が存在する. 公開鍵型の検索可能暗号はID ベース暗号から一般的に構成可能であることが証明されている. このように暗号要素技術間の関係性を厳密に証明することは今後の方式設計の指針を与えるという点で重要である. 一方, より複雑な検索条件を利用可能な公開鍵型検索可能暗号について, 鍵ポリシー型属性ベース暗号からより複雑な検索条件を利用できる公開鍵型検索可能暗号を一般的に構成可能であることは証明されているが, 逆に, そのようなより複雑な検索条件を利用できる公開鍵型検索可能暗号から鍵ポリシー型属性ベース暗号が構成可能であるかについては知られていない. 本論文では, 論理積及び論理和を用いて検索条件を指定できる公開鍵型検索可能暗号から, 適応的安全な匿名鍵ポリシー型属性ベース暗号が一般的に構成可能であることを厳密に証明する.

浅野 泰輝

• 修士課程

研究テーマ

• 暗号技術

Publications

• 浅野泰輝, 林リウヤ, 林田淳一郎, 松田隆宏, 山田翔太, 勝又秀一, 坂井祐介, 照屋唯紀, シュルツヤコブ, アッタラパドゥンナッタポン, 花岡悟一郎, 松浦幹太, 松本勉. 「モノの電子署名」の複数物体への拡張, Extension of "Signature for Objects" to Multiple Objects, 2022年暗号と情報セキュリティシンポジウム (SCIS2022) 予稿集, 2022 [detail]

abstract

近年の偽造品や海賊版製品の取引の増加に伴い，取引の正当性を検証可能にする技術の必要性が高まっており，その1つとして電子署名がある． しかしながら，従来の電子署名方式では，電子データではない物体そのものに対しての署名作成はできない． そこで，林ら（CSS2021）により，物体の加工や電子データへの変換といった物理的な操作を取り扱うことが可能な枠組みを定式化することで， 任意の物体を対象とした「モノの電子署名」が提唱された． しかし，「モノの電子署名」は一物体のみに対して加工，変換を施すことを想定しているため， 本稿ではこの枠組みを複数物体においても動作するよう拡張し，より実システムに近い形での署名方式を与える． 特に，サプライチェーンの各ステップにおいて物体の生成，加工，組み合わせのいずれかが可能であるという状況のもとで， 各物体に対してそれがどのような変遷をたどってきたかを保証する署名を付与できるモデルを導入する． さらに，その安全性定義，およびAppend-Only署名と集約署名を用いた一般的構成を提案し，簡単な概念実証も行う．
• 林リウヤ, 浅野泰輝, 林田淳一郎, 松田隆宏, 山田翔太, 勝又秀一, 坂井祐介, 照屋唯紀, シュルツヤコブ, アッタラパドゥンナッタポン, 花岡悟一郎, 松浦幹太, 松本勉. モノの秘匿性を考慮した「モノの電子署名」. "Signature ofr Objects" with Object Privacy, 2022年暗号と情報セキュリティシンポジウム (SCIS2022) 予稿集, 2022 [detail]

abstract

物体の偽造に対する安全性の暗号学的な評価手法として「モノの電子署名」が提案されている． これは電子署名方式の一種であるが，従来の電子署名とは異なりメッセージだけでなく物体にも署名できる方式となっている． ここでは安全性として偽造不可能を表す EUF-COA が定義されている． モノの電子署名方式の特徴の一つに，署名された物体は物理空間で送られ，署名自体はサイバー空間で送信されることが挙げられる． ここで，署名を入手した悪意のある人が署名単体から対応する物体を特定できてしまうと， その署名を用いて検証が通過するような，署名されていない物体を生成可能である恐れがある． このとき生成された物体は検証者に正当なものとみなされてしまう． これを防ぐために新たな安全性としてモノの秘匿性を定義する． モノの秘匿性は署名単体から対応する物体が特定できないという安全性を表す． 本稿ではモノの秘匿性の安全性定義を行い，EUF-COA 安全性とモノの秘匿性の両方を満たす構成を示す． 具体的には，EUF-COA 安全性は基盤とする電子署名方式における EUF-CMA 安全性と確率的ハッシュにおける衝突困難性に帰着でき， モノの秘匿性は Relational Hash における偽造不可能性に帰着できることを示す．
• 林リウヤ, 浅野泰輝, 林田淳一郎, 松田隆宏, 山田翔太, 勝又秀一, 坂井祐介, 照屋唯紀, シュルツヤコブ, アッタラパドゥンナッタポン, 花岡悟一郎, 松浦幹太, 松本勉. モノの電子署名：物体に署名するための一検討, Signature for Objects: Formalization, Security Definition, and Provably Secure Constructions, 2021年コンピュータセキュリティシンポジウム（CSS2021）予稿集, pp.740-747, 2021 [detail]

abstract

従来の電子署名方式では，電子データでない物体に対して電子署名を作成することができない． そこで， 物体への操作を暗号学的に定式化することで， 任意の物体を対象として作成が可能な電子署名である「モノの電子署名」を提案する． 物体への操作は，物体を加工して新たな物体を作り出す操作であるコマンドと， 物体を加工することなく電子データに変換する操作であるセンシングの2つに分けられる． このうちセンシングは同じ物体からであっても実行されるたびに異なる電子データを返すが， それに左右されることなく物体に対する有効な電子署名を作成できる方式が構成可能である． 本稿では，この方式が満たすべき安全性定義とそれを満たす構成を示す． また，その構成の安全性が 基盤とする電子署名方式における選択文書攻撃に対する存在的偽造不可(EUF-CMA)に帰着できることも示す．

久野 朔

• 修士課程

研究テーマ

• 脆弱性調査関連

Publications

• 久野朔、松浦幹太. 深層強化学習によるWebアプリケーションのペネトレーションテストの自動化に向けて, 2022年暗号と情報セキュリティシンポジウム (SCIS2022）予稿集, 2022 [detail]

abstract

近年、サイバー攻撃による情報の流出やシステムの改竄などの危険性が問題視されている。 これに対抗する方策の一つとして、実際に対象環境に対して疑似的な攻撃を行い、 侵入につながりうる脆弱性を発見するペネトレーションテストは非常に有効であるとされる。 しかし、これには十分に訓練された人員が必要であり、大きなコストが要求される。 この問題を解消するために強化学習・深層学習・深層強化学習などを用いてペネトレーションテストを 自動化・効率化する研究が存在している。 しかし、実際のペネトレーションテストにおいて利用される 脆弱性および複数のツールの情報を直接利用し、なおかつ強化学習・深層強化学習の本領ともいえる 状態の遷移をペネトレーションテストに根差した形で取り入れた研究は確認した限りでは存在していない。 本稿では、多様な攻撃手法と対象の種類が存在しており、非常に使用頻度の高い web アプリケーションというカテゴリを対象とした ペネトレーションテストの効率化のために深層強化学習を用いて、既存のツールおよび exploit を統合することを目標とする。 最初に、単純なペネトレーションテスト環境の再現として、著名な web アプリケーション 15 種類の 現存しているバージョンと公開されている exploit を元に模擬環境を作成し、それぞれのアプリケーションに対し、 バージョンに適応する exploit を見つけ出すタスクを設定する。 その後、このタスクに PPO アルゴリズムを用いた 深層強化学習を適用し、学習を行ったエージェントが正しい exploit を見つけ出せることを示す。 次いで、exploit だけではない多数のツールの効力と、状態遷移の概念を導入した模擬環境を作成し、 これに対し同様に PPO 深層強化学習を行い、より複雑なペネトレーションテスト分野における深層強化学習の有効性について検討する。
• Hajime Kuno, Kanta Matsuura. Towards Automation of Penetration Testing for Web Applications by Deep Reinforcement Learning, Proceedings of the 37th Annual Computer Security Applications Conference (ACSAC '21), 2021 [detail]

abstract

Penetration testing (PT) that assesses vulnerabilities by considering and executing all possible attacks is important in security engineering but very expensive due to the need of experienced professionals. As a countermeasure, there are attempts to partially automate and improve the efficiency of PT. Their common feature is the use of existing PT tools (e.g. Metasploit) and machine learning (ML). Such approaches do not embed ML in PT tools, and would not improve the tools themselves. In this work, we use deep reinforcement learning to automate search and exploit executions for various vulnerabilities existing in Web applications so that a wide variety of PT tools can be integrated in an effective manner with such embedded ML. This poster will show two preliminary experiments in this direction.

碓井 利宣

• 博士課程

研究テーマ

• マルウェア対策技術

Publications

• Toshinori Usui, Yuto Otsuki, Yuhei Kawakoya, Makoto Iwamura, Kanta Matsuura. Script Tainting Was Doomed From The Start (By Type Conversion): Converting Script Engines into Dynamic Taint Analysis Frameworks, Proceedings of the 25th International Symposium on Research in Attacks, Intrusions and Defenses (RAID 2022), pp.380-394, 2022 [detail]

abstract

Data flow analysis is an essential technique for understanding the complicated behavior of malicious scripts. For tracking the data flow in scripts, dynamic taint analysis has been widely adopted by existing studies. However, the existing taint analysis techniques have a problem that each script engine needs to be separately designed and implemented. Given the diversity of script languages that attackers can choose for their malicious scripts, it is unrealistic to prepare taint analysis tools for the various script languages and engines. In this paper, we propose an approach that automatically builds a taint analysis framework for scripts on top of the framework designed for native binaries. We first conducted experiments to reveal that the semantic gaps in data types between binaries and scripts disturb our approach by causing under-tainting. To address this problem, our approach detects such gaps and bridges them by generating force propagation rules, which can eliminate the under-tainting. We implemented a prototype system with our approach called STAGER T. We built taint analysis frameworks for Python and VBScript with STAGER T and found that they could effectively analyze the data flow of real-world malicious scripts.
• 碓井 利宣, 大月 勇人, 川古谷 裕平, 岩村 誠, 松浦 幹太. スクリプト実行環境に対する動的バイトコード計装機能の自動付与手法, 2022年コンピュータセキュリティシンポジウム(CSS2022)予稿集, pp.1055-1062, 2022 [detail]

abstract

悪性スクリプトの動的解析を妨害する手法に，解析環境が特定の条件を満たさない場合に実行を停 止するものがある． こうした妨害を迂回する入力を与えるためには，どういった条件式を満たすべきかを 解明する必要がある． これを実現する技術に，実行時に解析用の処理をバイトコードの命令列に挿入する 動的バイトコード計装がある． しかし，スクリプトのバイトコードを構成する命令の仕様は一般に公開さ れておらず，手動解析で解明する必要があるため，計装の実現は困難である． この問題を解決するため，本研究では，スクリプトエンジンに動的バイトコード計装機能を自動付与する 手法を提案する． 提案手法では，命令の仕様を解明するために，テストスクリプトを用いてスクリプトエ ンジンの仮想機械を動的解析し，主要な命令の操作と入出力を明らかにする． そして，その結果に基づい て，バイトコードの各命令の実行をイベントとして監視し，その命令の入出力を引数に伴って解析用の関 数にコールバックすることで，計装の機能を実現する． この手法を Python，Ruby，VBScript のエンジン に適用し，計装を実現して，実際の攻撃の解析妨害を迂回できることを確認した．
• 碓井利宣, 幾世知範, 川古谷裕平, 岩村誠, 松浦幹太. スクリプト実行環境に対する実行遅延・実行停止を回避する機能の自動付与手法, Automatically Appending Execution Stall/Stop Prevention to Vanilla Script Engines, 2021年コンピュータセキュリティシンポジウム (CSS2021) 予稿集, pp.794-801, 2021 [detail]

abstract

マルウェアの動的解析を妨げる要因に，不要な命令の繰り返しによる実行の遅延や，例外による実行の停止がある． これらは，機械語形式のマルウェアでは，実行命令や実行状態を監視し，発生箇所を検出してスキップすることで回避できる． しかし，スクリプト形式のマルウェアでは，言語やエンジンごとに，未知のバイトコードの解析や仮想機械の監視の必要が生じるため， 実現が困難である． この問題を解決するため，本研究では，スクリプトエンジンに，実行遅延および実行停止を回避する機能を自動付与する手法を提案する． 提案手法では，仮想機械を解析して，実行状態の監視と制御を可能にするとともに，命令セットアーキテクチャを解析して， 未知のバイトコードに対しても，制御フローグラフおよびコールグラフを構築可能にする． これらに基づいて， 実行遅延・実行停止の発生箇所を検出してスキップする仕組みを付与する． これを Lua と VBScript のエンジンに適用し，本手法の解析結果が正しいことを確認した． さらに，実行遅延・実行停止を引き起こす 286 検体のうち 199 検体に対して，従来の解析環境では観測できない新たな挙動を観測できることを確認した．
• Toshinori Usui, Yuto Otsuki, Tomonori Ikuse, Yuhei Kawakoya, Makoto Iwamura, Jun Miyoshi, Kanta Matsuura. Automatic Reverse Engineering of Script Engine Binaries for Building Script API Tracers, Digital Threats: Research and Practice, Vol.2, No.1, pp.1-31, 2021 [detail]

abstract

Script languages are designed to be easy-to-use and require low learning costs. These features provide attackers options to choose a script language for developing their malicious scripts. This diversity of choice in the attacker side unexpectedly imposes a significant cost on the preparation for analysis tools in the defense side. That is, we have to prepare for multiple script languages to analyze malicious scripts written in them. We call this unbalanced cost for script languages asymmetry problem. To solve this problem, we propose a method for automatically detecting the hook and tap points in a script engine binary that is essential for building a script Application Programming Interface (API) tracer. Our method allows us to reduce the cost of reverse engineering of a script engine binary, which is the largest portion of the development of a script API tracer, and build a script API tracer for a script language with minimum manual intervention. This advantage results in solving the asymmetry problem. The experimental results showed that our method generated the script API tracers for the three script languages popular among attackers (Visual Basic for Applications (VBA), Microsoft Visual Basic Scripting Edition (VBScript), and PowerShell). The results also demonstrated that these script API tracers successfully analyzed real-world malicious scripts.
• 碓井利宣, 幾世知範, 川古谷裕平, 岩村誠, 三好潤, 松浦幹太. 『スクリプト実行環境に対するテイント解析機能の自動付与手法』, 2020年コンピュータセキュリティシンポジウム (CSS2020) 予稿集, pp.932-939, 2020 [detail]

abstract

悪性スクリプトの挙動を詳細に解析するには，制御フローの解析のみならず， データフローの解析も求められる． このデータフローの解析には，テイント解析 がよく利用されるが，既存のスクリプト向けのテイント解析手法はスクリプトエ ンジンごとに設計，実装する必要がある． この問題を解決するため，本研究では，バイナリ（機械語のプログラム）向けの テイント解析機能を，スクリプトにも適用可能にすることで，言語やエンジンに 非依存でテイント解析機能を自動付与する手法を提案する． まず，バイナリの データ型とスクリプトのデータ型の間に生じるセマンティックギャップがこの実 現を妨げる問題だと実験的に示す． そして，こうした型のセマンティックギャッ プによって起こる伝播漏れを検出し，テイントの強制伝播によってそれを解消す ることで，テイント解析機能を実現する． PythonとVBScriptのスクリプトエンジ ンに対して提案手法を適用し，テイント解析を実現できることを確認した． さら に，それを用いて悪性スクリプトを解析し，データフローを追跡可能になったこ とも確認した．
• Toshinori Usui, Tomonori Ikuse, Yuto Otsuki, Yuhei Kawakoya, Makoto Iwamura, Jun Miyoshi, Kanta Matsuura. ROPminer: Learning-based Static Detection of ROP Chain Considering Linkability of ROP Gadgets, IEICE Transactions on Information and Systems, Vol.E103-D, No.7, pp.1-17, 2020 [detail]

abstract

Return-oriented programming (ROP) has been crucial for attackers to evade the security mechanisms of recent operating systems. Although existing ROP detection approaches mainly focus on host-based intrusion detection systems (HIDSes), network-based intrusion detection systems (NIDSes) are also desired to protect various hosts including IoT devices on the network. However, existing approaches are not enough for network-level protection due to two problems: (1) Dynamic approaches take the time with second- or minute-order on average for inspection. For applying to NIDSes, millisecond-order is required to achieve near real time detection. (2) Static approaches generates false positives because they use heuristic patterns. For applying to NIDSes, false positives should be minimized to suppress false alarms. In this paper, we propose a method for statically detecting ROP chains in malicious data by learning the target libraries (i.e., the libraries that are used for ROP gadgets). Our method accelerates its inspection by exhaustively collecting feasible ROP gadgets in the target libraries and learning them separated from the inspection step. In addition, we reduce false positives inevitable for existing static inspection by statically verifying whether a suspicious byte sequence can link properly when they are executed as a ROP chain. Experimental results showed that our method has achieved millisecond-order ROP chain detection with high precision.
• Toshinori Usui, Yuto Otsuki, Yuhei Kawakoya, Makoto Iwamura, Jun Miyoshi, Kanta Matsuura. My Script Engines Know What You Did In The Dark: Converting Engines into Script API Tracers, Proceedings of the 35th Annual Computer Security Applications Conference (ACSAC '19), pp.466-477, 2019 [detail]

abstract

Malicious scripts have been crucial attack vectors in recent attacks such as malware spam (malspam) and fileless malware. Since malicious scripts are generally obfuscated, statically analyzing them is difficult due to reflections. Therefore, dynamic analysis, which is not affected by obfuscation, is used for malicious script analysis. However, despite its wide adoption, some problems remain unsolved. Current designs of script analysis tools do not fulfill the following three requirements important for malicious script analysis. (1) Universally applicable to various script languages, (2) capable of outputting analysis logs that can precisely recover the behavior of malicious scripts, and (3) applicable to proprietary script engines. In this paper, we propose a method for automatically generating script API tracer by analyzing the target script engine binaries. The method mine the knowledge of script engine internals that are required to append behavior analysis capability. This enables the addition of analysis functionalities to arbitrary script engines and generation of script API tracers that can fulfill the above requirements. Experimental results showed that we can apply this method for building malicious script analysis tools.
• 碓井利宣, 古川和祈, 大月勇人, 幾世知範, 川古谷裕平, 岩村誠, 三好潤, 松浦幹太. スクリプト実行環境に対するマルチパス実行機能の自動付与手法, 2019年コンピュータセキュリティシンポジウム（CSS2019）予稿集, pp.961-968, 2019 [detail]

abstract

悪性スクリプトの挙動の解析には，難読化の影響を受けにくい動的解析が用いられてきた． しかし，悪性スクリプトには，特定の条件を満たさなければ実行されない実行経路が存在し， 単一の経路のみを解析する方式では挙動を把握しきれない． こうした問題への対策として， 条件分岐の発生時に両方の経路を実行するマルチパス実行が存在する． しかし，マルチパス実行は スクリプトエンジンごとに設計，実装が必要であり，悪性スクリプトの用いる多様なスクリプト エンジンに対して実現するのは現実的でない． この問題を解決するため，本研究では，スクリプト エンジンに共通する構造に着目したマルチパス実行機能の自動付与手法を提案する． 複数のテスト用の スクリプトを用いてスクリプトエンジンの持つ仮想機械の挙動の差分を抽出することで アーキテクチャの情報を取得し，それに基づいて仮想機械に解析用コードを付加することで， マルチパス実行を実現する． LuaとVBScriptのスクリプトエンジンに対して本手法を適用し， 必要な情報が得られることを確認した． さらに，それを用いてマルチパス実行基盤を構成し， 解析妨害を具備する検体に対しても，従来の解析環境では実行されない経路を実行できることを確認した．

田村 研輔

• 協力研究員

研究テーマ

• デジタルフォレンジック、制御システムセキュリティ

Publications

• 田村研輔, 松浦幹太. 制御システムにおける通信の規則性を利用した異常検知, 2018年暗号と情報セキュリティシンポジウム（SCIS2018）予稿集, USB, 2018 [detail]

abstract

重要インフラ事業者等が運用する制御システムに対するサイバー攻撃が発生し、早期に異常を検知する 仕組みが必要となっている。 制御システムにおける異常検知手法は、システムの動作に不可欠なプロセスや 通信のみ許可するホワイトリストを使用したものや単位時間当たりの通信量に着目したものが提案されてきた。 これらの手法は、制御システムのプロセスや通信が周期的であることや通信量の変動が微小であるという 特徴を利用している。 しかし、制御システムに対するサイバー攻撃は、稼働中の機器や構成を把握する ための調査が長時間かけて行われ、その結果に応じて深刻な攻撃が行われるケースが想定されている。 この場合、制御システムのプロセスには影響を与えず、通信量も大きく変動させずに攻撃が行われるため、 従来の手法での検知は困難である。 そこで、本稿では、時系列的に規則性を有する制御システムの通信を 自然言語に見立て、単語の類似性を評価するword2vecを制御システムの通信に適用して異常検知を行う。 具体的には、学習データから予測される通信及びそれに類似した通信と実際の通信が異なる場合に異常 として検出する手法を評価する。
• Kensuke Tamura, Kanta Matsuura. Improvement of Anomaly Detection Performance using Packet Flow Regularity in Industrial Control Networks, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, Vol.E102-A, No.1, pp.65-73, 2019 [detail]

abstract

Since cyber attacks such as cyberterrorism against Industrial Control Systems (ICSs) and cyber espionage against companies managing them have increased, the techniques to detect anomalies in early stages are required. To achieve the purpose, several studies have developed anomaly detection methods for ICSs. In particular, some techniques using packet flow regularity in industrial control networks have achieved high-accuracy detection of attacks disrupting the regularity, i.e. normal behavior, of ICSs. However, these methods cannot identify scanning attacks employed in cyber espionage because the probing packets assimilate into a number of normal ones. For example, the malware called Havex is customized to clandestinely acquire information from targeting ICSs using general request packets. The techniques to detect such scanning attacks using widespread packets await further investigation. Therefore, the goal of this study was to examine high performance methods to identify anomalies even if elaborate packets to avoid alert systems were employed for attacks against industrial control networks. In this paper, a novel detection model for anomalous packets concealing behind normal traffic in industrial control networks was proposed. For the proposal of the sophisticated detection method, we took particular note of packet flow regularity and employed the Markov-chain model to detect anomalies. Moreover, we regarded not only original packets but similar ones to them as normal packets to reduce false alerts because it was indicated that an anomaly detection model using the Markov-chain suffers from the ample false positives affected by a number of normal, irregular packets, namely noise. To calculate the similarity between packets based on the packet flow regularity, a vector representation tool called word2vec was employed. Whilst word2vec is utilized for the calculation of word similarity in natural language processing tasks, we applied the technique to packets in ICSs to calculate packet similarity. As a result, the Markov-chain with word2vec model identified scanning packets assimilating into normal packets in higher performance than the conventional Markov-chain model. In conclusion, employing both packet flow regularity and packet similarity in industrial control networks contributes to improving the performance of anomaly detection in ICSs.

角田 大輔

• 協力研究員

研究テーマ

• デジタルフォレンジック

Publications

• 角田大輔,　松浦幹太. Androidアプリケーションにおける暗号化API利用に関する静的解析手法の考察, A Study on Analysis Methods of Crypto API Usages on Android Apps using a Static Analysis Framework, 2019年コンピュータセキュリティシンポジウム（CSS2019）予稿集, pp.Online, 2019 [detail]

abstract

近年，デジタルフォレンジックと呼ばれる電磁的記録に対する科学的調査技術の重要性が高まっている． 特にスマートフォンに関しては，比較的短期間で急速に普及したこともあってフォレンジックの対象 となる機会が非常に多く，スマートフォンに対するフォレンジック技術の向上が望まれている． スマートフォンについては従来よりアプリケーションのセキュリティ向上に関する様々な研究がなされている． デジタルフォレンジックに関する研究は従来のアプリケーションセキュリティに関する研究と比較すると まだ少ないものの，最近では従来のセキュリティを目的としたAndroidアプリの解析手法に関する研究を デジタルフォレンジックの研究に応用する動きがある． デジタルフォレンジックにおける課題の1つには 電磁的記録として保存されるデータに暗号化処理が施されてる場合への対処があり，そのような場合に おいては復号方法の解明が重要となるケースがある． 本稿では，セキュリティ診断を目的として作られている 既存のAndroidアプリの静的解析フレームワークを利用し，Androidアプリにおける暗号化APIの利用状況を 解析する手法の検討を行った．
• 角田大輔,　松浦幹太. Androidアプリケーションにおける静的解析を使用した暗号化API利用の特定, Identifying Crypto API Usages in Android Apps using a Static Analysis Framework, 2020年コンピュータセキュリティシンポジウム (CSS2020) 予稿集, pp.80-87, 2020 [detail]

abstract

デジタル・フォレンジック調査において，携帯デバイスを調査対象とすることは 必要不可欠な作業である． 特にスマートフォンに関しては様々なデータが保存され， その中には有用なデータが含まれている． しかしながら，最近の傾向としてアプリケーションにより データが暗号化される場合が少なくない． そのようなデータの暗号化は迅速な調査の障害となり， スマートフォン・フォレンジックにおける大きな課題の1つである． 従来の研究の多くは特定の1つのアプリに対する手動解析で暗号化処理の特定を行っているが， そのような作業はアプリ解析の知識や経験が必要な手間のかかる作業である． 保存データを 暗号化するアプリは数多く存在するが，その中でも多くのアプリが標準的な暗号化APIを使用している． 本稿では，既存のAndroidアプリの静的解析フレームワークを使用し，アプリにおいて 標準的な暗号化APIがどのように利用されているかを特定するツールの開発を行った． 本ツールでは自動的にアプリを解析することが可能であり，暗号化処理の特定を容易に行うことができる． その結果，アプリによって暗号化されたデータの解析を迅速に行うことが可能となる．

宮里 俊太郎

• 修士課程

研究テーマ

• ブロックチェーン、攻撃検知

Publications

• 宮里俊太郎, 松浦幹太. 内部のバイトコード実行を悪用したスマートコントラクトへの攻撃の早期検知, 2020年コンピュータセキュリティシンポジウム (CSS2020) 予稿集, pp.478-485, 2020 [detail]

abstract

ブロックチェーン上でコントラクトと呼ばれるプログラムを動かすシステムである スマートコントラクトに対する攻撃として, コントラクトの脆弱性を利用した, Reentrancy攻撃やTransaction Ordering Dependence攻撃が現在報告されている. 既存研究では, コントラクトの脆弱性を検知する技術が盛んに開発されているが, 攻撃に利用されるコントラクトやトランザクションを悪性として検知する研究は少数である. 現状の攻撃検知技術の問題点として, 検知出来る攻撃の種類がReentrancy攻撃だけである事と, トランザクション全てを実行時に監視する事によるオーバーヘッドが挙げられる. 本研究では, 攻撃の別種であるTransaction Ordering Dependence攻撃も考慮し, Reentrancy攻撃に関しては, トランザクションのごく一部である, コントラクトを定義する トランザクションのみを静的解析する手法を提案し, それら2点の改善を図る.

石 为之

• 研究生*

研究テーマ

• ブロックチェーン

長嶺 隆寛

• 修士課程

研究テーマ

• ブロックチェーン

Publications

• 長嶺隆寛，松浦幹太. 非協力的なペイメントチャネル終了時の公平な手数料追加プロトコル, 2020年暗号と情報セキュリティシンポジウム（SCIS2020）予稿集, pp.オンライン, 2020 [detail]

abstract

ビットコインのペイメントチャネルで使用される，タイムロックを使用してトランザクションを置換する手法は， タイムロックの影響によりトランザクションを作成してからそれが有効になるまで時間差があるという特徴を持つ． チャネルを非協力的に終了する場合，過去のトランザクションを置換した最新のトランザクションが ブロックに追加されることが期待される． しかし，トランザクション作成後にビットコインネットワークが混雑し手数料相場が上昇すると， 相対的に低い手数料を持つ最新のトランザクションは優先的にブロックに追加されず， タイムロックを使用したトランザクションの置換が失敗する可能性がある． この問題は最新のトランザクションに手数料を追加することで解決することができるが， 非協力的な終了により，追加する手数料をチャネルに参加しているユーザー間で分担することが難しい． 本稿では，一方のユーザーが単独で，2者間で公平に負担される手数料を追加することができるプロトコルを提案する.
• 長嶺隆寛，松浦幹太. ビットコインにおける手数料を考慮したオフチェーントランザクションの管理, 2019年コンピュータセキュリティシンポジウム（CSS2019）予稿集, pp.オンライン, 2019 [detail]

abstract

ビットコインは単位時間当たりに処理できるトランザクション数が少ないというスケーラビリティ 問題を抱えている． スケーラビリティ問題改善に向けて, 一部のトランザクションをブロックチェーンの 外で管理することでブロックチェーン上に記載するトランザクション数を減らすペイメントチャネルという 手法が提案されている． 先行研究にて，トランザクションに時間制約を設けるタイムロックという機能を 利用してトラザクション置換を行うペイメントチャネルが提案されているが，これはトランザクションの 優先度を決定付ける手数料を考慮していない． 本稿では，適切な手数料を設定しないとタイムロックを 利用したオフチェーントランザクションの管理が期待通りに動作せず，チャネル利用者の資金が奪われる 可能性があることを指摘する． また，これを解決するために必要な手数料を追加する手法について述べ， チャネル利用者が支払う手数料の公平性について検討する．
• Takahiro Nagamine, Kanta Matsuura. A New Protocol for Fair Addition of a Transaction Fee When Closing a Payment Channel Uncooperatively, 24th International Conference on Financial Cryptography and Data Security (FC'20), Poster presentation, 2020 [detail]

abstract

A technique called transaction replacement using timelocks is used in payment channels for Bitcoin. When closing a payment channel uncooperatively, the latest time-locked transaction is broadcasted to the Bitcoin network. However, if the Bitcoin network is crowded, the latest one with a lower fee might not be added to a block preferentially, and hence the transaction replacement might fail. This problem can be solved by adding a fee to the latest one (e.g. using SIGHASH_ANYONECANPAY). However, it is difficult to divide the additional fee cooperatively because this scenario happens in the uncooperative case. We propose a protocol that allows the transaction fee added by a single party to be divided equally between two parties. In this protocol, each party deposits funds for the additional fee to the payment channel in advance. A party can add the transaction fee alone by creating a child transaction referring to the funds (Child Pays for Parent). Then, the remains of the funds are returned to each party on two outputs of the child transaction. Regarding these two outputs, one party decides the values of outputs, and the other has a right to choose either output. As a result, a party who decides the values is motivated to specify the same value.

黄 珂

• 修士課程

研究テーマ

• 暗号技術

Publications

• Ke Huang, Satsuya Ohata, Kanta Matsuura. An Approximate Privacy Preserving Top-k Algorithm with Reduced Communication Rounds, 2020年暗号と情報セキュリティシンポジウム（SCIS2020）予稿集, 2020 [detail]

abstract

The top-k algorithm is to search for k smallest(largest) numbers in the given dataset. In some situations, the dataset is distributed to two or more parties to keep the privacy of the data. In previous research, privacy preserving algorithms are considered in low-latency networks, and the computation cost of the algorithms are more important than the communication cost in data transmission between different parties. In high-latency networks, both time complexity and round complexity should be taken into consideration. In this paper, we focus on privacy preserving algorithm in high-latency network such as wireless network. We proposed a kind of approximate method for privacy preserving top-k algorithm based on secure multi-party computation. This method has lower communication rounds than the previous methods and has better performance in high-latency networks.
• Ke Huang, Satsuya Ohata, Kanta Matsuura. Privacy-Preserving Approximate Nearest Neighbor Search: A Construction and Experimental Results, 2019年コンピュータセキュリティシンポジウム（CSS2019）予稿集, pp.online, 2019 [detail]

abstract

Secure multi-party computation (MPC) allows a set of parties to jointly compute a function, while keeping their inputs private. MPC has many applications, and we focus on privacy-preserving nearest neighbor search (NNS) in this paper. The purpose of the NNS is to find the closest vector to a query from a given database, and NNS arises in many fields of applications such as computer vision. Recently, some approximation methods of NNS have been proposed for speeding up the search. In this paper, we consider the combination between approximate NNS based on "short code" (searching with quantization) and MPC. We implement a short code-based privacy-preserving approximate NNS on secret sharing-based secure two-party computation and report some experimental results. These results help us to explore more efficient privacy-preserving approximate NNS in the future.

石坂 理人

• 博士課程

研究テーマ

• 暗号技術

Publications

• Masahito Ishizaka, Kanta Matsuura. Identity/Attribute-Based Signature Resilient to Hard-to-Invert Leakage under Standard Assumptions, 2018年コンピュータセキュリティシンポジウム（CSS2018）予稿集, USBメモリ, 2018 [detail]

abstract

If a cryptographic scheme is resilient to some leakage, its security is guaranteed to be maintained even if secret information, e.g., the secret-key, is partially leaked. Various security models considering leakage-resilience have been proposed. Hard-to-invert leakage (HL) model, a.k.a. auxiliary (input) leakage model, proposed by Dodis et al. in STOC’09 is especially meaningful since it can deal with leakage caused by a function which information-theoretically determines the secret-key, e.g., a one-way permutation. In this paper, we generically construct identity-based signature (IBS) and attribute-based signature (ABS) which are adaptively secure in the HL model. By instantiating them, we give the first concrete constructions of IBS and ABS which are adaptively secure in the HL model under standard assumptions, i.e., the decisional linear assumption.
• Masahito Ishizaka, Kanta Matsuura. Identity-Based Encryption Resilient to Auxiliary Leakage under the Decisional Linear Assumption, Lecture Notes in Computer Science (The 17th International Conference on Cryptology and Network Security: CANS2018), Vol.11124, pp.417-439, 2018 [detail]

abstract

Leakage-resilience guarantees that even if some information about the secret key is partially leaked, the security is maintained. Several security models considering leakage-resilience have been proposed. Among them, auxiliary leakage model proposed by Dodis et al. in STOC'09 is especially important, since it can deal with a leakage caused by a function which information-theoretically reveals the secret key, e.g., one-way permutation. Contribution of this work is two-fold. Firstly, we propose an identity based encryption (IBE) scheme and prove that it is fully secure and resilient to the auxiliary leakage under the decisional linear assumption in the standard model. Secondly, although the IBE scheme proposed by Yuen et al. in Eurocrypt'12 has been considered to be the only IBE scheme resilient to auxiliary leakage, we prove that the security proof for the IBE scheme is defective. We insist that our IBE scheme is the only IBE scheme resilient to auxiliary leakage.
• Masahito Ishizaka, Kanta Matsuura. Strongly Unforgeable Signature Resilient to Polynomially Hard-to-Invert Leakage under Standard Assumptions, Lecture Notes in Computer Science (The 21st Information Security Conference), Vol.11060, pp.422-441, 2018 [detail]

abstract

A signature scheme is said to be weakly unforgeable, if it is hard to forge a signature on a message not signed before. A signature scheme is said to be strongly unforgeable, if it is hard to forge a signature on any message. In some applications, the weak unforgeability is not enough and the strong unforgeability is required, e.g., the Canetti, Halevi and Katz transformation. Leakage-resilience is a property which guarantees that even if secret information such as the secret-key is partially leaked, the security is maintained. Some security models with leakage-resilience have been proposed. The auxiliary (input) leakage model, or hard-to-invert leakage model, proposed by Dodis et al. in STOC'09 is especially meaningful one, since the leakage caused by a function which information-theoretically reveals the secret-key, e.g., one-way permutation, is considered. In this work, we propose a generic construction of a signature scheme strongly unforgeable and resilient to polynomially hard-to-invert leakage which can be instantiated under standard assumptions such as the decisional linear assumption. We emphasize that our signature scheme is not only the first one resilient to polynomially hard-to-invert leakage under standard assumptions, but also the first one which is strongly unforgeable and has hard-to-invert leakage-resilience.
• 石坂理人，松浦幹太. Continual Auxiliary Leakageに耐性を持つ適応的安全な述語署名, 2017年コンピュータセキュリティシンポジウム（CSS2017）予稿集, USBメモリ, 2017 [detail]

abstract

暗号プロトコルが満たすべき性質の中で，秘密鍵に関する情報が部分的に漏洩しても安全性が 保持されることを保証する漏洩耐性(Leakage Resilience)は，実用性の観点から重要である． 漏洩耐性を考慮した安全性モデルの中で代表的なモデルは，Bounded Leakageモデル(TCC'09)， Auxiliary Leakageモデル(ALM)(STOC'09)，Continual Leakageモデル(FOCS'10)である． 本研究では，Continual AuxiliaryLeakageモデル(CALM)において適応的安全な述語署名(Predicate Signature) の構成法を提案する． 本研究の成果により，具体的には以下のOpen Problemが肯定的に解決される． 1.CALMにおいてEUF-CMA安全な電子署名の構成． 2.ALM(CALM)において適応的EUF-CMA安全なIDベース署名の構成． 3.ALM(CALM)において適応的EUF-CMA安全な属性ベース署名の構成
• 石坂理人，松浦幹太. IDベース暗号方式(黒澤・Phong, ACNS'13)の補助漏洩耐性の証明, 2017年暗号と情報セキュリティシンポジウム（SCIS2017）予稿集, USBメモリ, 2017 [detail]

abstract

暗号方式が満たす性質の中で，秘密鍵等を始めとする秘密情報に関係した情報が部分的に漏洩しても 秘匿性が保持されることを保証する，漏洩耐性(Leakage Resilience)は重要な性質である． これまでに 様々な漏洩耐性を考慮した安全性モデルが考えられているが，中でも以下の二つのモデルは特に重要である． 第一に，Bounded Retrieval Model(TCC'09)(BRモデル)である． 第二に， Auxiliary Inputs Model (TCC'10)(AIモデル)である． Kurosawaら(ACNS'13)はIDベース暗号(Identity-Based Encryption, IBE) 方式を提案し，当該方式がDLIN仮定の下で，BRモデルで漏洩耐性的(Leakage Resilient)であり，特定の パラメータをlとして1-3/2l-o(1)のLeakage Rateを達成可能であり，かつ適応的選択ID安全であることを 証明した． 一方で，Yuenら(EUROCRYPT'12)のIBE方式は，静的な(Static)仮定の下で，AIモデルで 漏洩耐性的であり，かつ適応的選択ID安全であることが証明された，唯一のIBE方式として知られている． 本研究では，KurosawaらのIBE方式が，パラメータlを調整することで，DLIN仮定の下で，AIモデルで 漏洩耐性的であり，適応的選択ID安全であることを証明できることを示した． また，Yuenらの安全性証明は 誤りである可能性があることを指摘する．
• Masahito Ishizaka, Satsuya Ohata, Kanta Matsuura. Generic Construction of Ciphertext-Policy Attribute-Based Signcryption Secure in the Adaptive Predicate Model, IPSI Transactions on Advanced Research, Special issue - "Advances in Cryptology and Information Security", Vol.12, No.2, pp.16-26, 2016 [detail]

abstract

Ciphertext-policy attribute-based signcryption (CP-ABSC) is a cryptographic primitive which performs simultaneously both the functionalities of ciphertext-policy attribute-based encryption and signature-policy attribute-based signature. CP-ABSC guarantees both message confidentiality and authenticity and is considered to be a useful tool for fine-grained data access control in attribute-based environments such as a cloud service. In this paper, we provide a generic construction of CP-ABSC which achieves ciphertext indistinguishability under adaptively chosen ciphertext attacks in the adaptive predicate model (AP-IND-CCA), strongly existentially unforgeability of signcryptext under adaptively chosen message attacks in the adaptive predicate model (AP-sEUF-CMA) and perfect privacy. Our generic construction uses as building blocks, ciphertext-policy attribute-based key encapsulation mechanism, signature-policy attribute-based signature and data encapsulation mechanism.
• 石坂理人，大畑幸矢，松浦幹太. 適応的述語安全な暗号文ポリシー型属性ベースSigncryptionの一般的構成法, 2016年暗号と情報セキュリティシンポジウム（SCIS2016）予稿集, USBメモリ, 2016 [detail]

abstract

属性情報を利用した公開鍵暗号技術である暗号文ポリシー型属性ベース暗号と署名ポリシー型属性ベース署名に 関して活発な研究が行われている． また，この両者の機能を実現可能な暗号文ポリシー型属性ベース Signcryption (Ciphertext-Policy Attribute-Based Signcryption, CP-ABSC) と呼ばれる暗号技術に 関して様々な構成法の提案が現在までになされている． 本稿では，適応的述語安全性モデルでの適応的 選択暗号文攻撃に対する識別不可能性，及び適応的選択文書攻撃に対する強偽造不可能性を達成可能な CP-ABSC 方式の一般的構成法の提案を行う． 当該構成法は構成要素として，暗号文ポリシー型属性ベース 鍵カプセル化方式，署名ポリシー型属性ベース署名方式，データカプセル化方式を用いる．
• 石坂理人，松浦幹太. DLIN仮定下で強偽造困難性及び多項式的逆変換困難漏洩耐性を持つ電子署名, 2019年暗号と情報セキュリティシンポジウム（SCIS2019）予稿集, USBメモリ, 2019 [detail]

abstract

電子署名方式が強（存在的）偽造困難であるとは，全文書（過去に署名が生成された文書を含む）に 関する署名偽造が困難である場合をいう． 強偽造困難署名方式は，様々な応用例が知られている （例: Canetti-Halevi-Katz 変換）． 漏洩耐性（Leakage-Resilience）は，秘密鍵等の秘匿情報に 関する何らかの情報が漏洩しても安全性が維持される事を保証する． 種々ある漏洩耐性モデルの内， 逆変換困難漏洩（Hard-to-Invert Leakage, HL）関数に対する安全性を保証するHL モデル（STOC’09） は，特に重要とされる． それは，当該モデルが秘密鍵を情報理論的に決定するような関数 （例: 一方向性置換）による漏洩さえも考慮している等の理由による． 本稿では，強偽造困難性及び 多項式的逆変換漏洩関数耐性を持つ署名方式の一般的構成法を提案し，Decisional Linear（DLIN） 仮定の下で具体化する． 当該署名方式は，標準的な仮定の下で多項式的逆変換困難漏洩耐性を持つ最初の 方式であり，かつ，強偽造困難性とHL耐性を同時に達成する最初の方式である． なお，当該論文は[15]の 邦訳短縮版である．

Arnaud PIRIOU

• 交換留学生

研究テーマ

• 暗号技術、 ステガノグラフィー

先崎 佑弥

• 修士課程

研究テーマ

• 機械学習、マルウェア

Publications

• 先崎佑弥,大畑幸矢,松浦幹太. 深層学習に対する効率的なAdversarial Examples生成によるブラックボックス攻撃とその対策, 2018年暗号と情報セキュリティシンポジウム（SCIS2018）予稿集, USBメモリ, 2018 [detail]

abstract

ニューラルネットワークの発展に伴い、その脆弱性とも理解できる Adversarial Examples に 関する研究が盛んに行われている。 これは、元の入力サンプルに対しわずかな改変を加えることで 学習器の出力を大きく誤らせるものであり、今後ニューラルネットワークが広く利用されるように なった際に問題になると考えられる。 これまでの研究でこのようなサンプルの生成手法はいくつも 提案されてきたが、その多くは生成の際に対象となる学習器の内部情報が必要なホワイトボックス 攻撃であった。 もしくは内部情報が不必要なブラックボックス攻撃であったとしても学習器への 問い合わせ回数というものは考慮されていない。 しかし、より現実的なシナリオとしては攻撃者が 内部情報を得られない上に時間的な制約等から問い合わせ回数に制限があるということが十分考えられる。 そこで本稿ではブラックボックスな学習器に対し、より少ない問い合わせ回数でAdversarial Examples を 生成する手法を提案する。 また、このような攻撃の存在を考慮した上で防御側が行うべき対策の提言を行う。
• 先崎佑弥,大畑幸矢,松浦幹太. 深層学習におけるAdversarial Trainingによる副作用とその緩和策, 2017年コンピュータセキュリティシンポジウム（CSS2017）予稿集, CD-ROM, 2017 [detail]

abstract

畳み込みニューラルネットワーク（ Convolutional Neural Network, CNN ）は画像認識や音声認識、 自然言語処理などへ応用した際に高い精度を出すことがわかってきたため注目を集めている。 しかし一方 で、 CNN への入力データに微小な改変を加えることで出力を大きく誤らせることが可能な敵対的入力の存 在が報告されており、 CNN を実社会で用いる際に大きな脅威となることが予想される。 この問題に対し て頑健な識別器を構成するテクニックとして、敵対的入力も学習用データに加えて学習する「敵対的訓練 （ Adversarial Training ）」と呼ばれる手法が提案されており、敵対的入力に対する耐性を向上させる ことが 確認されている。 本稿ではこの敵対的訓練における問題点を指摘し、その対策法を提案する。 具体的には、 CNN に対して敵対的訓練を行うと（本来高い精度で識別できるはずの）ランダムノイズが 乗ったデータに 対する識別率が大きく減少してしまうことを指摘する。 その問題を解決するためにランダム ノイズを付加 した画像も教師データに加えて学習する手法を提案し、計算機実験により提案手法の有用性を実証する。
• 先崎佑弥, 松浦幹太. 深層学習に対し意図的に誤判定を起こさせる入力の検知手法, 2017年暗号と情報セキュリティシンポジウム（SCIS2017）予稿集, USBメモリ, 2017 [detail]

abstract

近年、画像認識や言語の翻訳など様々な分野で深層学習を用いたアプローチが導入されており、 めざましい成果をあげている。 これらの技術は今後も様々な応用が考えられている一方で、 これらの学習器に対する攻撃も報告されている。 この攻撃手法を用いると、画像認識を行う 学習器に対し人間の目では正常に識別できるが学習器は誤った識別結果を返してしまうといった 画像を作成することが可能になる。 このような改変が行われた画像とただランダムにノイズを のせた画像を見た目で区別することは大変困難である。 そこで本研究では、入力画像に対する 学習器の出力からjacobian を計算して利用することで深層学習を用いた画像分類器に対し 意図的に誤ったクラスに分類させるような入力画像を検知する手法を提案する。
• Yuya Senzaki, Satsuya Ohata, Kanta Matsuura. Simple Black-box Adversarial Examples Generation with Very Few Queries, IEICE Transactions on Information and Systems, Vol.E103-D, No.2, pp.212-221, 2020 [detail]

abstract

Research on adversarial examples for machine learning has received much attention in recent years. Most of previous approaches are white-box attacks; this means the attacker needs to obtain before-hand internal parameters of a target classifier to generate adversarial examples for it. This condition is hard to satisfy in practice. There is also research on black-box attacks, in which the attacker can only obtain partial information about target classifiers; however, it seems we can prevent these attacks, since they need to issue many suspicious queries to the target classifier. In this paper, we show that a naive defense strategy based on surveillance of number query will not suffice. More concretely, we propose to generate not pixel-wise but block-wise adversarial perturbations to reduce the num ber of queries. Our experiments show that such rough perturbations can confuse the target classifier. We succeed in reducing the number of queries to generate adversarial examples in most cases. Our simple method is an untargeted attack and may have low success rates compared to previous results of other black-box attacks, but needs in average fewer queries. Surprisingly, the minimum number of queries (one and three in MNIST and CIFAR-10 dataset, respectively) is enough to generate adversarial examples in some cases. Moreover, based on these results, we propose a detailed classification for black-box attackers and discuss countermeasures against the above attacks.

今田 丈雅

• 修士課程

研究テーマ

• 公開分散台帳

Publications

• 今田丈雅, 松浦幹太. 仮想通貨を用いたワンショット型の公平なストレージサービス, 2018年暗号と情報セキュリティシンポジウム（SCIS2018）予稿集, USBメモリ, 2018 [detail]

abstract

今日, クラウドストレージサービスは急速な普及をみせている. クラウドは便利である一方で, ユーザー側からすればクラウドは他人であり信頼できない. そのような安全性の懸念を解消するために, 外界にあるデータの完全性を検証するプロトコルが提案されてきた. しかし, 特に有料のクラウドサービスについては依然として安全性の懸念が残っている. 一つは, ユーザーがクラウドに預けたデータが改ざんされていないのかということ. 二つ目は, ユーザーがクラウドに対して適切に利用料金を支払っているかということ. 三つ目は, ユーザーが不当に利用料を支払わされていないかということである. これらの問題を解決するには, ストレージサービスがユーザーと合意した一定期間ユーザーから預けられたデータを保持した場合に, それに対する報酬としてユーザーが公平に利用料金を支払うような仕組みを考えなければならない. 本研究では, ユーザーとクラウドストレージ双方に公平なサービスを定義し, 必要となる安全性についてモデル化を行う. さらに, 仮想通貨を用いてワンショット型の公平なストレージサービスのプロトコルを実現する.
• 今田丈雅, 松浦幹太. ブロックチェーンと秘密分散法を用いた情報ライフサイクル制御, 2017年コンピュータセキュリティシンポジウム（CSS2017）予稿集, CD-ROM, 2017 [detail]

abstract

われわれは今日なんらかのコミュニケーションツールを使って情報の伝達をしている. 情報伝達に あたっては中央サーバーを経由しており, ユーザーからはデータの制御権が離れてしまう. このため 後から政府の検閲によってセンシティブなデータが見られてしまう可能性がある. そのような脅威に 対抗するためにはデータに期限を設定し, 自動で消去されるような仕組みが必要である. 本研究では 公開分散型台帳と秘密分散法を組み合わせることによって上記の要請を満たす仕組みを提案する. このシステムは従来研究と異なり, 信頼できる第三者機関やセキュアなハードウエアを必要とせず シビル攻撃にも耐性があるという性質を持つ.

竹之内 玲

• 修士課程

研究テーマ

• 匿名通信

Publications

• 竹之内玲, 松浦幹太. ダミーパケット挿入がTor秘匿サービスの匿名性に与える影響について, 2016年コンピュータセキュリティシンポジウム（CSS2016）予稿集, CD-ROM, 2016 [detail]

abstract

近年，インターネットを通じて個人情報を集めることが用意になっており，プライバシーエンハンシング 技術の重要性が高まっている． 匿名通信システムTorはユーザとサーバーの繋がりを秘匿することで， 通信に匿名性を持たせる実システムである． TorはサーバーのIPアドレスを隠す，Tor秘匿サービスと 呼ばれるシステムも提供している． このTor秘匿サービスのプロトコルには4つのTorネットワーク上の リンクが含まれるが，TorクライアントとEntry Guardまたは，Tor秘匿サービスとEntry Guardの間の 通信パケットを観測することでそれぞれを区別出来るということが報告されている． 本論文では，Tor秘匿 サービスの通信に加えるノイズがリンク分類推定精度にどう影響するか調べた結果について報告する．
• 竹之内玲, 松浦幹太. Tor秘匿サービスへの攻撃に対抗する偽装トラフィック生成, 2017年暗号と情報セキュリティシンポジウム（SCIS2017）予稿集, USBメモリ, 2017 [detail]

abstract

近年,インターネットを通じて個人情報を集めることが容易になっており, プライバシーエンハンシング 技術の重要性が高まっている. 匿名通信システムTorは,ユーザとサーバの繋がりを秘匿することで通信に 匿名性を持たせる実システムである. TorはサーバのIP アドレスを隠す,Tor秘匿サービスと呼ばれるシステムも 提供している. このTor秘匿サービスのプロトコルには4つのTorネットワーク上のリンクが含まれるが, TorクライアントとEntry Guardまたは, Tor秘匿サービスとEntry Guardの間の通信パケットを観測する ことでそれぞれを区別出来るということが報告されている. 本研究ではTor秘匿サービスのトラフィックを分析し, Tor秘匿サービスが発生させるサーバ側のトラフィックと紛らわしいトラフィックを生成した. このトラフィックを偽装トラフィックと呼ぶ. 偽装トラフィックの紛らわしさや効果を機械学習を用いて 評価したところ, 偽装トラフィックを誤ってTor秘匿サービスのトラフィックと分類した割合が最高で35% となった. 本論文では偽装トラフィックの目的や生成手法について述べ, この実験結果について報告する.
• 竹之内玲, 松浦幹太. 学習データに加えられた偽装トラフィックがTor秘匿サービスへの攻撃に与える影響について, 第22回セキュリティ心理学とトラスト研究発表会, 2017 [detail]

abstract

匿名通信システムTorは，ユーザとサーバの繋がりを秘匿することで通信に匿名性を持たせる実システムである． Torを用いてサーバのIP アドレスを隠すTor秘匿サービスでは，プロトコルに4種類のTorネットワーク上の サーキットが含まれる． しかし，機械学習を用いてトラフィック分析をすることで，それぞれを区別出来る ということが報告されている． これに対し我々は，Tor秘匿サービスが発生させるサーバ側のトラフィックと 紛らわしいトラフィックである，偽装トラフィックをTorネットワークに流すことで，有効なデータセットの割合を 下げることを提案している． 本論文では，Tor秘匿サービスの通信データセットの他に一般のTor通信も混ぜた データセットに対し偽装トラフィックを加える． 偽装トラフィックの元となるトラフィックの傾向や，加える量 よって分類精度にどのような影響があらわれるのか実験し，Torクライアントが生成するトラフィックのデータ量 の40%程の量の偽装トラフィックが存在すれば分類精度を大きく下げることが可能であることと，偽装 トラフィックの生成元になるトラフィックデータの多様さは分類精度に大きい影響を与えないことを明らかにした． さらに偽装トラフィックの運用法について検討し，DHSノードごとに偽装トラフィックを生成する量を決めることが 出来るようにし，また偽装トラフィックの生成元となるTorクライアントのトラフィックは公開情報にしておく ことが適切であると結論付けた．

林 昌吾

• 修士課程

研究テーマ

• WEBアプリケーションセキュリティ

Publications

• 林昌吾, 松浦幹太. オブジェクト指向のWebアプリケーションに対するXSS攻撃脆弱性の静的解析, コンピュータ・セキュリティ研究会2016 (CSEC2016), 2016 [detail]

abstract

Webアプリケーションは日常の様々な場面で利用されるが、その中には脆弱性が存在するものも多い。 中でもクロスサイトスクリプティング(XSS)攻撃は数多くの研究がなされてきているにも関わらず常に 首位を争う脅威となっている攻撃であり、攻撃手法は多様化している。 防御策について、Open Web Application Project(OWASP)のようにチェックシートを公開している組織も存在するが、開発者全員が これらを基に安全な実装するのは困難である。 それ故、脆弱性を自動で検知するツールがあれば大いに 役に立つと言え、そのような研究も存在する。 しかし、既存研究では精度が低い。 特に、スクリプト言語に 適用可能なオブジェクト指向に対する研究はあまりされていない。 そこで本研究では２方向後方脆弱分析と クラスキャッシュという概念を導入して、オブジェクト指向で実装されたソースコードのXSS攻撃脆弱性を 静的解析するための手法の提案と実装を行う。
• 林昌吾,松浦幹太. スクリプト言語によるオブジェクト指向のWEBアプリケーションにおけるXSS攻撃脆弱性に対するクラスキャッシュを用いた静的解析, 2017年暗号と情報セキュリティシンポジウム（SCIS2017）予稿集, CD-ROM, 2017 [detail]

abstract

クロスサイトスクリプティング(XSS)攻撃は数多くの研究がなされてきているにもかかわらず常に 首位を争う脅威となっている攻撃であり, 攻撃手法は多様化している. 防御策について, Open Web Application Project(OWASP) のようにチェックシートを公開している組織も存在するが, 開発者全員がこれらを基に安全な実装をするのは困難である. それ故, 脆弱性を自動で検知するツールが あれば大いに役に立つと言え, そのような研究も存在する. しかし, 既存研究では精度が低い. 特に, スクリプト言語に 適用可能なオブジェクト指向に対する研究はあまりなされていない, そこで本研究では 2方向後方脆弱性分析とクラスキャッシュという概念を導入して, 解析手法の提案と実装を行う.
• 林昌吾,松浦幹太. ソースコード中のXSS攻撃脆弱性に関する評価指標の提案と実装, 2017年暗号と情報セキュリティシンポジウム（SCIS2017）予稿集, CD-ROM, 2017 [detail]

abstract

クロスサイトスクリプティング (XSS) 攻撃は Web アプリケーションにおいて主要な脆弱性の1つで, これまでに数多くの研究がなされてきている. 静的解析や動的解析など様々な解析手法が考案されている. しかし, ソースコード中の脆弱性箇所周辺の文脈やWebアプリケーションの利用環境などによる脆弱性判定の 基準が解析ツールの利用者には不明瞭であることが多い. 本研究では, 解析における脆弱性の危険度の評価, 脆弱性箇所周辺の文脈に応じて的確に判定できる陽性の判定基準の明確化, 対策の優先度判定に貢献する ための脆弱性のメトリクスの提案と実装を行う.

孫 達

• 修士課程

研究テーマ

• コンピューターセキュリティ、ネットワークセキュリティ

大畑 幸矢

• 博士課程

研究テーマ

• 暗号学

Publications

• 大畑幸矢, 松田隆宏, 松浦幹太. パスワード再発行プロトコルの安全性について, 2016年暗号と情報セキュリティシンポジウム（SCIS2016）予稿集, USBメモリ, 2016 [detail]

abstract

パスワードに基づくオンラインユーザ認証は現在でも広く用いられているが、ユーザがパスワードを 忘れてしまうとサービスを利用できなくなってしまうという問題があり、多くのウェブサイトにおいては 何らかの方法でパスワードを再発行するためのプロトコルが用意されている。 著者らはCSS2014及び2015に おいてこのパスワード再発行プロトコルに証明可能安全性の考え方を導入し、モデルと安全性の定義、 一般的構成の提案、及びその方式の安全性証明を行った。 本稿では安全性モデルの再考、及び性能評価に 関して報告する。
• 大畑幸矢, 松田隆宏, 松浦幹太. 証明可能安全なパスワード再発行プロトコル・改, 2015年コンピュータセキュリティシンポジウム（CSS2015）予稿集, pp.1313-1320, 2015 [detail]

abstract

IDとパスワードを用いたオンラインユーザ認証はこれまでいくつかの問題点が指摘されている一方、 その利便性の高さを理由に現在でも頻繁に用いられている認証手法である。 人間の記憶力には限度が あるためユーザはパスワードを忘れてしまうこともあるが、そのような場合でもサービスを利用 できるよう、何らかの方法でパスワードを再発行するためのプロトコルが用意されている場合が多い。 著者らはCSS2014において、このパスワード再発行プロトコルに証明可能安全性の考え方を導入し、 モデルと安全性の定義、一般的構成の提案、及びその方式の安全性証明を行った。 本稿ではその結果を 拡張し、パスワード再発行プロトコルの新たなモデル、安全性定義、及び構成法について論じる。
• Satsuya Ohata, Takahiro Matsuda, Kanta Matsuura. On Rigorous Security of Password Recovery Protocols, The Tenth International Workshop on Security (IWSEC2015), Poster Session, 2015 [detail]

abstract

Many online services adopt a password-based user authentication system because of its usability. However, several problems have been pointed out on it, and one of the well-known problems is that a user forgets his/her password and cannot login the services. To solve this problem, most online services support a mechanism with which a user can recover a password. In this poster, we discuss rigorous security for a password recovery protocol.
• Satsuya Ohata, Yutaka Kawai, Takahiro Matsuda, Goichiro Hanaoka, Kanta Matsuura. Re-encryption Verifiability: How to Detect Malicious Activities of a Proxy in Proxy Re-encryption, Lecture Notes in Computer Science (Topics in Cryptology: CT-RSA2015), Vol.9048, pp.410-428, 2015 [detail]

abstract

In this paper, we introduce a new functionality for proxy re-encryption (PRE) that we call re-encryption verifiability. In a PRE scheme with re-encryption verifiability (which we simply call verifiable PRE, or VPRE), a receiver of a re-encrypted ciphertext can verify whether the received ciphertext is correctly transformed from an original ciphertext by a proxy, and thus can detect illegal activities of the proxy. We formalize the security model for a VPRE scheme, and show that the single-hop uni-directional PRE scheme by Hanaoka et al. (CT-RSA 2012) can be extended to a secure VPRE scheme.
• 大畑幸矢, 松浦幹太. 識別不可性難読化に基づく復号の速い代理再暗号化について, 2015年暗号と情報セキュリティシンポジウム（SCIS2015）予稿集, CD-ROM, 2015 [detail]

abstract

代理再暗号化技術（Proxy Re-Encryption, PRE）はBlazeらによって提案された、 受信者が生成する再暗号化鍵を用いて第三者が暗号文の宛先を変更することが可能な高機能公開鍵暗号である。 また、Gargらによって構成法（の候補）が提案された識別不可性難読化(Indistinguishability Obfuscation, \iO)と呼ばれる回路の難読化技術は、Sahaiらによって提案された穴あき擬似ランダム関数(Punctured PseudoRandom Function, PPRF)と組み合わせることによって、様々な暗号技術の構成に有用であることが わかってきた。 本稿では、識別不可性難読化を用いて代理再暗号化技術を構成することを試みる。 提案する方式は 再暗号化が一方向、事前に回数上限を指定することなく複数回の再暗号化が可能、再暗号化によって暗号文サイズ が変化しない、復号が速いなどといった特長を持つ。
• 大畑幸矢, 松田隆宏, 松浦幹太. 証明可能安全なパスワード再発行プロトコルについて, 2014年コンピュータセキュリティシンポジウム（CSS2014）予稿集, CD-ROM, 2014 [detail]

abstract

IDとパスワードを用いたオンラインユーザ認証はこれまでいくつかの問題点が指摘されている一方、 その利便性の高さを理由に現在でも頻繁に用いられている認証手法である。 人間の記憶力には限度があるため ユーザはパスワードを忘れてしまうこともあるが、そのような場合でもサービスを利用できるよう、 何らかの方法でパスワードを再発行するためのプロトコルが用意されている場合が多い。 本稿では 暗号技術研究において用いられる証明可能安全性の考え方に着目し、証明可能安全なパスワード再発行 プロトコルについて考察する。
• Satsuya Ohata. On the Key Re-splittability of Threshold Public Key Encryption, 2014
• Satsuya Ohata, Takahiro Matsuda, Goichiro Hanaoka, Kanta Matsuura. More Constructions of Re-splittable Threshold Public Key Encryption, Lecture Notes in Computer Science (Advances in Information and Computer Security, The 9th International Workshop on Security: IWSEC2014), Vol.8639, pp.109-118, 2014 [detail]

abstract

The concept of threshold public key encryption (TPKE) with the special property called key re-splittability (re-splittable TPKE, for short) was introduced by Hanaoka et al.(CT-RSA 2012), and used as one of the building blocks for constructing their proxy re-encryption scheme. In a re-splittable TPKE scheme, a secret key can be split into a set of secret key shares not only once, but also multiple times, and the security of the TPKE scheme is guaranteed as long as the number of corrupted secret key shares under the same splitting is smaller than the threshold. In this paper, we show several new constructions of re-splittable TPKE scheme by extending the previous (ordinary) TPKE schemes. Our results suggest that key re-splittability is a very natural property for TPKE.
• 大畑幸矢, 松田隆宏, 花岡悟一郎, 松浦幹太. 閾値公開鍵暗号の鍵再分割可能性について, 2014年暗号と情報セキュリティシンポジウム（SCIS2014）予稿集, CD-ROM, 2014 [detail]

abstract

閾値公開鍵暗号(Threshold Public Key Encryption, TPKE)はDesmedtらによって1989年に提案された 高機能公開鍵暗号である。 閾値公開鍵暗号においては、秘密鍵をn個の秘密鍵に分割し、そのうち異なるt個の 秘密鍵から得られる復号シェアを集めると復号が可能となる。 Hanaokaらはこの閾値公開鍵暗号における 鍵再分割可能性(Key Re-splittability)という性質を提案し、その性質を持つ閾値公開鍵暗号の安全性モデルを 定義するとともに、鍵再分割可能な閾値公開鍵暗号を用いた代理再暗号化技術(Proxy Re-Encryption, PRE)の 一般的構成を示した。 その際、鍵再分割可能な閾値公開鍵暗号についてはAritaらの既存の構成が鍵再分割可能な構成に 拡張できることを示しているが、示されたのはその一構成のみであり、またその安全性証明もなされていなかった。 本稿では、Aritaらの方式以外にも既存のいくつかの閾値公開鍵暗号方式が鍵再分割可能な構成に拡張できることを 示し、その安全性を証明する。
• 大畑幸矢, 松田隆宏, 花岡悟一郎, 松浦幹太. 検証可能代理人再暗号化方式の安全性について, 2013年暗号と情報セキュリティシンポジウム（SCIS2013）予稿集, CD-ROM, 2013 [detail]

abstract

代理人再暗号化方式（Proxy Re-Encryption，PRE）はBlaze らによって提案された高機能公開鍵暗号である。 代理人再暗号化方式においては、受信者Aが自分宛の暗号文を受信者B宛に変更するための再暗号化鍵を作成する ことができる。 代理人と呼ばれる第三者は、その再暗号化鍵を用いてA宛の暗号文を復号することなく、B宛の 暗号文に変換することが可能である。 受信者Bが受け取った暗号文が本当に受信者Aに送られた暗号文を再暗号化した ものなのか、受信者Bには検証ができないという問題が川合らによって2012年に提唱され、その問題を解決するための 安全性定義やそれを満たす方式提案がなされた。 川合らは新たに再暗号化検証アルゴリズムを導入し、その健全性を 新たな安全性として定義したが、そのように定義された検証可能代理人再暗号化方式は、同じく川合らによって 2012年のCT-RSAにて発表された既存の代理人再暗号化方式より弱い安全性しか達成していなかった。 本稿では その検証可能代理人再暗号化方式の安全性について議論し、安全性定義を再考する。 具体的には、SCIS2012で 提案された安全性モデルがCT-RSA2012の安全性モデルより真に強いわけではないことを指摘し、検証の健全性の 定義を変更することでCT-RSA2012の安全性モデルよりも真に強くなるように改良し、それを証明する。
• Satsuya Ohata, Takahiro Matsuda, Goichiro Hanaoka, Kanta Matsuura. More Constructions of Re-Splittable Threshold Public Key Encryption, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, Vol.E101-A, No.9, pp.1473-1483, 2018 [detail]

abstract

The concept of threshold public key encryption (TPKE) with the special property called key re-splittability (re-splittable TPKE, for short) was introduced by Hanaoka et al. (CT-RSA 2012), and used as one of the building blocks for constructing their proxy re-encryption scheme. In a re-splittable TPKE scheme, a secret key can be split into a set of secret key shares not only once, but also multiple times, and the security of the TPKE scheme is guaranteed as long as the number of corrupted secret key shares under the same splitting is smaller than the threshold. In this paper, we show several new constructions of re-splittable TPKE scheme by extending the previous (ordinary) TPKE schemes.

中田 謙二郎

• 修士課程

研究テーマ

• 匿名通信

Publications

• 中田謙二郎， 松浦幹太. 匿名通信システムTorに対する指紋攻撃の判定評価の拡張, 2016年暗号と情報セキュリティシンポジウム（SCIS2016）予稿集, USBメモリ, 2016 [detail]

abstract

匿名通信システムTorは送信者と受信者のつながりの匿名性の保護を目的とする． しかし その匿名性を脅かす攻撃も発見されつつあり，中でも指紋攻撃は攻撃に必要な資源が少なく 現実的な脅威となりうるものとして注目されている． 近年の代表的な指紋攻撃は，主に二つの シナリオで攻撃を評価する． 一つ目は，ユーザは攻撃者が予め定めた監視対象のサイト群のうちの どれかにのみアクセスすると仮定し，アクセス先を一意に特定する． 二つ目は，攻撃者はユーザが 監視対象のサイト群にアクセスしたか否かを判定し，監視対象の場合にはそれを一意に特定する． しかしこれらのシナリオは指紋攻撃の脅威を評価するのに十分ではない． 多くの攻撃者にとって， ユーザのふるまいを完全に把握する必要はなく，ユーザが監視対象にアクセスしているか否かさえ 知ることができれば十分であると考えられるからである． そこで我々は，指紋攻撃の新たな 評価手法を提案する． 監視対象のサイト群について，従来の一意特定に対し，本研究では推定の 候補を複数列挙し，この中に正解が存在すれば攻撃成功とみなす． 本稿では，従来の二つのシナリオに対し， 提案する評価指標を用いて評価の拡張を行う．
• 中田謙二郎，松浦幹太. 匿名通信システムTorにおけるウルフウェブサイトの提案, 第70回コンピュータセキュリティ・第14回セキュリティ心理学とトラスト合同研究発表会, pp.電子版のみ, 2015 [detail]

abstract

A model of an encryption approach is analyzed from an information-theoretic point of view. In the model, an attacker faces the problem of observing messages through a concatenation of a binary symmetric channel and a channel with randomly inserted bits. The paper points out to a number of security related implications resulting from employing an insertion channel. It is shown that deliberate and secret-key-controlled insertions of random bits into the basic ciphertext provide a security enhancement of the resulting encryption scheme.

篠田 詩織

• 修士課程

研究テーマ

• 情報セキュリティマネジメント

Publications

• Shiori Shinoda, Kanta Matsuura. Empriical Investigation of Threats to Loyalty Programs by Using Models Inspired by the Gordon-Loeb Formulation of Security Investment, Journal of Information Security (JIS), Vol.7, No.2, pp.29-48, 2016 [detail]

abstract

Loyalty program (LP) is a popular marketing activity of enterprises. As a result of firms' effort to increase customers' loyalty, point exchange or redemption services are now available worldwide. These services attract not only customers but also attackers. In pioneering research, which first focused on this LP security problem, an empirical analysis based on Japanese data is shown to see the effects of LP-point liquidity on damages caused by security incidents. We revisit the empirical models in which the choice of variables is inspired by the Gordon-Loeb formulation of security in-vestment: damage, investment, vulnerability, and threat. The liquidity of LP points corresponds to the threat in the formulation and plays an important role in the empirical study because it particu-larly captures the feature of LP networks. However, the actual proxy used in the former study is ar-tificial. In this paper, we reconsider the liquidity definition based on a further observation of LP security incidents. By using newly defined proxies corresponding to the threat as well as other re-fined proxies, we test hypotheses to derive more implications that help LP operators to manage partnerships; the implications are consistent with recent changes in the LP network. Thus we can see the impacts of security investment models include a wider range of empirical studies.
• 篠田詩織, 松浦幹太. ロイヤルティプログラムのセキュリティに対するネットワーク分析指標に着目した考察, 2015年コンピュータセキュリティシンポジウム（CSS2015）予稿集, CD-ROM, 2015 [detail]

abstract

ロイヤルティプログラムとは顧客の忠実な購買行動に対して報酬を与えるマーケティング施策のことである。 現在日本においてロイヤルティプログラム（LP）は、LP同士相互のポイント交換を可能にする交換 ネットワークが広がっているが、それによって利用者の利便性は上がったものの、正当なユーザのポイント 資産が攻撃者によって不正交換され盗まれる事件が多発している。 本研究では、ネットワーク分析で用いられる 指標を利用し、ポイント交換ネットワークの特徴とセキュリティインシデントとの関係をロジスティック回帰 によって分析した。 Loyalty programs (LPs) are popular marketing activities. In Japan, in order to increase usability, LPs are affiliating each other and customers became able to redeem their points or miles from one LP to another. However, this additional system unintentionally enabled attackers to steal legitimate user's point asset via redemption and in fact there is a lot of incidents exploiting it. In this paper, we empirically studied these incidents using logistic regression with network analysis metrics of LP partnership network.
• 篠田詩織, 松浦幹太. ロイヤルティプログラムのセキュリティインシデントに関する実証分析および制度設計の検討, 日本セキュリティ・マネジメント学会 第29回全国大会発表予稿集, pp.51-58, 2015 [detail]

abstract

近年，日本では企業のロイヤルティプログラム(LP)同士の連携が盛んで，ユーザが1つのLPから 他のLPポイントへ交換できるネットワークが発達してきている． このシステムは顧客にとって 便利である一方，なりすましによりポイントが奪われるインシデントが多発している． 本研究では， インシデントを実証分析し，より安全で便利なLP設計のための連携ポリシを検討する．
• 篠田詩織，松浦幹太. ロイヤルティプログラムのセキュリティインシデントインパクト分析に向けたポイント流動性の定義に対する考察, 2015年暗号と情報セキュリティシンポジウム（SCIS2015）予稿集, CD-ROM, 2015 [detail]

abstract

ロイヤルティプログラム(LP)を導入してポイントを発行する企業とその利用者は先進国において 年々増加しているが，特にポイント利用の進んでいる日本では，近年では顧客層の広範化などを 目的とした企業間連携により他社のポイントとの交換を可能にするネットワークの構築が進んでいる． 新たにLPを導入する企業，あるいは現状のLPの付随的用途を広げる企業は今後も増えていくと 予測されるが，LPによって発行されるポイントは金銭的価値を持っており，かつLPはWEBを用いて 認証を行っているためそのセキュリティリスクはシステム導入前に十分に考慮する必要がある． 実際， LPの認証システムはパスワードリスト攻撃によりポイントや個人情報が窃盗され金銭的被害が発生する ケースが発生している． Jenjarrussakulらはその脅威と脆弱性に関して，セキュリティ被害額， セキュリティ投資額，認証のセキュリティ要件，そして現金との交換しやすさを表す流動性を得られる 範囲のデータを用いて定量化し実証分析を行ったが，その流動性の定義の考察がまだ不十分である． 本稿では，LPのポイントの流動性の定義を再検討し，その評価を行った．

Tobias Fuchs

• 訪問学生

研究テーマ

• 暗号技術、匿名通信

Bongkot Jenjarrussakul

• 博士課程

研究テーマ

• 情報セキュリティマネジメント

Publications

• Bongkot Jenjarrussakul, Kanta Matsuura. Impact from Security Incidents and Partnership in Japanese Loyalty Program (日本のロイヤルティ・プログラムにおける企業間連携とそのセキュリティインシデントによるインパクト), 2015年暗号と情報セキュリティシンポジウム（SCIS2015）予稿集, CD-ROM, 2015 [detail]

abstract

The expansion of partnership between loyalty programs (LP) introduces the liquidity to the LP system. The higher partnership with other LPs and popularity of the LP, the more liquid of the system. This expansion also motivates malicious parties to break into well-known LP system. Several security cybercrime where LP is involved are reported worldwide. Our work at WEIS2014 shows that the liquidity of the LP is an important factor and strong security-related requirements in the LP systems would significantly reduce the impact from security incident. In this paper, we consider more about impact from security incident in each side of LP. We found that security incident at both origin and destination LPs affect their partners. In addition, stronger security in origin LP would indirectly reduce the impact on its partner.
• Bongkot Jenjarrussakul, Kanta Matsuura. Japanese Loyalty Program: An Empirical Analysis on their Liquidity, Security Efforts, and Actual Security Levels, 日本セキュリティ・マネジメント学会誌, Vol.28, No.3, pp.17-32, 2015 [detail]

abstract

In cyberspace, virtual currency is an important medium of exchange. Due to the usage of loyalty program (LP), it is also considered as a type of virtual currency. Loyalty program is widely used in many countries. In the U.S., according to a report in COLLOQUY talk [3], the total number of LP memberships is more than 2.6 billion in 2012 after 26.7% growth from 2010. LPs are very popular in Japan, too; there are more than 200 LPs in Japan and the use of them is widespread among Japanese people. With variety of redemption options, LPs in Japan are getting more and more popular and liquid virtual currencies. This situation can motivate malicious people to abuse such increasingly useful LPs for crimes, and in fact, there are some reports of such crimes. However, the security issues of LPs have not been well studied. In this paper, we empirically investigate Japanese LPs with focuses on their liquidity, their operating firms' security efforts, and the LP systems' actual security levels. Our preliminary and advance analyses show that liquidity is an important factor and strong security-related requirements in the LP systems would significantly reduce the impact from security incident.
• Bongkot Jenjarrussakul, Kanta Matsuura. Analysis of Japanese Loyalty Programs Considering Liquidity, Security Efforts, and Actual Security Levels, 13th Workshop on the Economics of Information Security (WEIS2014), on web, 2014 [detail]

abstract

Virtual currency is an important medium of exchange in cyber space, and loyalty program (LP) can be considered as a type of virtual currency. In the U.S., according to a report in COLLOQUY talk[5], the total number of LP memberships is more than 2.6 billion in 2012 after 26.7% growth from 2010. In addition, the number of LPs is also reported to show a clear increasing trend. LPs are very popular in Japan, too; there are more than 200 LPs in Japan and the use of them is widespread among Japanese people. People collect their LP points and redeem them to obtain goods and enjoy services. In addition, many LP points can be converted into points of different LPs. LPs in Japan are thus increasing redemption options, and getting more and more popular and liquid virtual currencies. This situation can motivate malicious people to abuse such increasingly useful LPs for crimes, and in fact, there are some reports of such crimes. However, the security issues of LPs have not been well studied. In this paper, we investigate Japanese LPs with focuses on their liquidity, their operating firms' security efforts, and the LP systems' actual security levels.
• Bongkot Jenjarrussakul, Hideyuki Tanaka, Kanta Matsuura. Sectoral and Regional Interdependency of Japanese Firms Under the Influence of Information Security Risks, The Economics of Information Security and Privacy, pp.115-134, 2013 [detail]

abstract

Although there are some studies on inter-sectoral information security interdependency, the lack of regional interdependency analysis is one of their limitations. In this empirical study, we used an inter-regional input-output table in order to analyze both sectoral and regional interdependencies under the influence of information technology and the information security of Japanese firms. Our analysis showed that the economic scale of a region has a great influence on the characteristics of the interdependency. Furthermore,we found that the demand-side sectors can be classified into five classes based on the characteristics. Among them, the groups with high self-dependency get more benefits from simultaneous understanding of regional characteristics; for the sectors in these classes, investment advice obtained from sectoral characteristics only is very limited, whereas they can obtain much more from regional characteristics. Since these classes include a majority of the sectors, we can recognize the importance of regional interdependency analysis. In the above basic study, what we see is the situation before the Great East Japan Earthquake on March 11, 2011. As an extended study, we estimated the impact of the earthquake on the interdependency. Our main finding from the regional perspective is that the interdependency characteristics of the most damaged region (Tohoku) and of the economically largest region (Kanto) are impacted most significantly. This feature is not changed by the limitation of damage through prior security investment. Both in the basic study and in the extended study, we can see that considering not only sectoral but also regional characteristics is an effective approach to the task of empirically deriving implications related to the interdependency. There are many possibilities of more extended studies based on our methodology.
• Bongkot Jenjarrussakul, Kanta Matsuura. Another class of function for the productivity space of information security investment, 2013年暗号と情報セキュリティシンポジウム（SCIS2013）予稿集, CD-ROM, 2013 [detail]

abstract

One of the concerns in economics of information security is about optimal investment in information security. In Gordon-Loeb's model, the general economic model which determines the optimal amount to invest in order to protect a given set of information security is introduced. Here they focus on optimal investment regarding reduction of vulnerability. An extension work by Matsuura shows productivity space of information security by considering productivity regarding threat and vulnerability reduction according to class-II of security breach probability function in Gordon-Loeb's model. Here we try to work on a gap by considering productivity regarding both threat and vulnerability reductions with a focus on class-I of security breach probability function stated in Gordon-Loeb's model. As a result, we found that when consider security breach probability function and security threat probability function which form as class-I of Gordon-Loeb's model, the optimal level of information security investment equals zero until a specific value of v, and then this optimal level of the investment increases at a decreasing rate.

keywords

Information security investment, optimal investment model, threat reduction, vulnerability reduction
• Bongkot Jenjarrussakul, Hideyuki Tanaka, Kanta Matsuura. Sectoral and Regional Interdependency of Japanese Firms under the Influence of Information Security Risks, 11th Workshop on the Economics of Information Security (WEIS2012), on web, 2012 [detail]

abstract

Although there are some studies on inter-sectoral information security interdependency, the lack of regional interdependency analysis is one of their limitations. In this empirical study, we used an inter-regional input-output table in order to analyze both sectoral and regional interdependencies under the influence of information technology and information security of Japanese firms. Our analysis showed that the economic scale of a region has a great influence on the characteristics of the interdependency. Furthermore, we found that the demand-side sectors can be classified into five classes based on the characteristics. Among them, the groups with high self-dependency get more benefits from simultaneous understanding of regional characteristics; for the sectors in these classes, investment advice obtained from sectoral characteristics only is very limited, whereas they can obtain much more from regional characteristics. Since these classes include a majority of the sectors, we can recognize the importance of regional interdependency analysis. In the above basic study, what we see is the situation before The Great East Japan Earthquake on March 11, 2011. As an extended study, we estimated reductions in interdependency resulting from investment-dependent economic damages in order to study how security investment can change the impact of the earthquake. Our main finding in regional perspective is that the interdependency characteristics of the most damaged region (Tohoku) and of the economically largest region (Kanto) are impacted most significantly. Both in the basic study and in the extended study, we can see that considering not only sectoral but also regional characteristics is an effective approach to the task of empirically deriving implications related to the interdependency. There are many possibilities of more extended studies based on our methodology.

keywords

Interdependency, Backward dependency, Empirical analysis, Supply chain, Input-output table, The Great East Japan Earthquake
• 飛鋪亮太, Bongkot Jenjarrussakul, 田中秀幸, 松浦幹太, 今井秀樹. 日本における情報セキュリティの相互依存性の分析, 電子情報通信学会情報セキュリティ研究会 (電子情報通信学会技術研究報告), Vol.111, No.455, pp.23-29, 2012 [detail]

abstract

現代の経済活動において、インターネットによる取引や他社との情報共有など情報分野における活動は どの産業分野でも必須である。 そのため、インターネット上のトラブルや攻撃を防ぐ、または損害を 減少させるための情報セキュリティ対策の実施も同様にあらゆる産業分野で欠かせない活動となっている。 また、一企業内での情報漏洩などのトラブルは、その企業が関わっていた他企業にも不利益を被らせるため、 このような被害の伝播に関する研究も必要と考えられる。 私の研究では日本の地域を９分割、産業分野を ５３分割し、それぞれの間の情報セキュリティがどのような相互依存性を持っているかを分析する。 この研究により、情報セキュリティに関する問題が生じた際に被害が伝播しやすい地域・産業分野が特定でき、 セキュリティ対策を講じる助けとして役立てることができる。 分析結果は地域間と産業分野間ごとに 依存性・被依存性に分けてまとめている。 また、自らの地域・産業分野内での相互依存性とそれ以外との 相互依存性の割合を計算して分析することで、より広い範囲に被害を伝播させる地域・産業分野を見つける。

links

• pdf
• Bongkot Jenjarrussakul, Hideyuki Tanaka, Kanta Matsuura. Information Security and the Impact from the Great East Japan Earthquake, 2012年暗号と情報セキュリティシンポジウム（SCIS2012）予稿集, CD-ROM, 2012 [detail]

abstract

The Great East Japan Earthquake on March 11, 2011 introduced vast impact on supply chain in Tohoku region. Although there are some reports regarding impact in economic viewpoint as well as information, communication and telecommunication (ICT) viewpoint, non of them shows relation to information security (IS). The methodology in here is applied to simulate the possible outcome with impact from the earthquake. We observe impacts that relate to information technology(IT) and IS. In addition, assumption that investment in IS helps reducing impact from the earthquake is also applied. With this concept, Japanese official statistical economic data, offcial data regarding IT and IS are used. The results show that limited effect from the loss in IT-related capital stock due to the earthquake likely affects some regions and industrial sectors such as sector of other manufacturing and services.

keywords

The Great East Japan Earthquake, Information Security, Regional and Sectoral Impact
• Bongkot Jenjarrussakul, Hideyuki Tanaka, Kanta Matsuura. Impact on Information Security from the Great East Japan Earthquake on March 11, 2011, Eighth Annual Forum on Financial Information Systems and Cybersecurity: A Public Policy Perspective, 2012 [detail]

abstract

The Great East Japan Earthquake on March 11, 2011 introduced vast impact on supply-chain in Tohoku region. Although there are some reports regarding impact in economic viewpoint as well as information, communication, and telecommunication (ICT) viewpoint, non of them shows possibility about impact on information security. Here we simulate the possible effect from the impact of the earthquake. The methodology is applied to predict impact from the earthquake. With this concept, Japanese offcial statistical economic data as well as offcial data regarding information technology and information security are used. The results show that limited effect from the loss in IT-related capital stock due to the Great East Japan Earthquake likely affects some regions and industrial sectors such as other manufacturing(6) and services(12).
• Bongkot Jenjarrussakul, Kanta Matsuura. A Survey on Information Security Economics, 日本セキュリティ・マネジメント学会誌, Vol.24, No.3, pp.53-60, 2011 [detail]

abstract

Information security plays a significant role in information systems due to their higher adoption rate in basic infrastructures. This widespread usage of information technology brings higher probability of risks and attacks to information systems. Moreover, higher number of firms and organizations concern more about expenditure on information security. From this fact, just understanding technologies is insufficient for appropriate adoption of information security. Hence understanding other aspects such as economics is also required. This paper introduces existing studies on information security economics and discusses some future directions; existing analyses based on economics theories have successfully explained a number of problems related to information security, and future steps would need more synthesis-oriented approaches as well as empirical studies.
• Bongkot Jenjarrussakul, Hideyuki Tanaka, Kanta Matsuura. Empirical study on Interdependency of Information Security between Industrial Sectors and Regions, 2011年暗号と情報セキュリティシンポジウム（SCIS2011）予稿集, CD-ROM, 2011 [detail]

abstract

This paper broadens the concept of measurement methodology of information security interdependency in industrial sectoral perspective into industrial regional perspective to analyze inter-regional and inter-sectoral interdependency in specific industrial sectors and regions on demand-side perspective. Previous study of cross-sectoral information security interdependency showed that industrial sector is one of the factors that affect interdependency in information security. Nevertheless, regional interdependency analysis was one of their limitations. In our implementation, we apply methodology to the statistical economic data of Japanese industrial sectors separated into regions in order to show their information security interdependency influenced by information technology and the level of information security measure.
• Bongkot Jenjarrussakul, Hideyuki Tanaka, Kanta Matsuura. Empirical Study on Interdependency of Information Security Between Industrial Sectors and Regions, Seventh Annual Forum on Financial Information Systems and Cybersecurity: A Public Policy Perspective, 2011 [detail]

abstract

This paper broadens the concept of measurement methodology of information security interdependency in industrial sectoral perspective into industrial regional perspective to analyze inter-regional and inter-sectoral interdependency between specific industrial sectors and regions on demand-side perspective. Previous study of cross-sectoral information security interdependency demonstrated that different industrial sectors is one of the factors that affect interdependency in information security. Nevertheless, regional interdependency analysis was one of their limitations. In our implementation, we apply methodology to the statistical economic data of Japanese industrial sectors separated into regions in order to show their information security interdependency influenced by information technology and the level of information security measure.

馮 菲

• 修士課程

研究テーマ

• 匿名通信

Publications

• 馮菲, 松浦幹太. Stronger Bridge Mechanisms of Tor Considering Exhaustive Adversarial Models, 情報処理学会　論文誌, Vol.59, No.9, pp.電子版のみ, 2015 [detail]

abstract

Tor is the most popular anonymous communication tool in the world. Its anonymity, however, has not been thoroughly evaluated. For example, it is possible for an adversary to restrict access to the Tor network by blocking all the publicly listed relays. In response, Tor utilizes bridges, which are unlisted relays, as alternative entry points. However, the vulnerabilities of the current bridge mechanism have not been thoroughly investigated yet. We first investigate the vulnerabilities of the current bridge mechanism under different adversarial models. Then we compare the current bridge mechanism with our two proposals and discuss their effects on the security and performance of Tor.
• 馮菲, 松浦幹太. Evaluation of Anti-enumeration Defenses for Tor Bridges, 2015年暗号と情報セキュリティシンポジウム（SCIS2015）予稿集, CD-ROM, 2015 [detail]

abstract

Tor is the most popular anonymous communication tool in the world. Its anonymity, however, is not perfect. For example, it is possible for an adversary to restrict access to the Tor network by blocking all the publicly listed relays. In response, designers of Tor introduced a new method of accessing the Tor network: bridges, which are unlisted relays, as alternative entry points. Bridges are effective against censors only as long as an adversary cannot easily enumerate their IP addresses. However, the current bridge design causes it easy for an adversary who controls or observes middle relays to enumerate IP addresses of bridges. As a countermeasure, the Tor community has discussed the idea of bridge guards, but the effectiveness of bridge guards has not yet been thoroughly verified and evaluated. What's more, the concrete design of bridge guards has not yet been proposed. We first evaluate the vulnerability of Tor under the adversarial model that the attacker controls or eavesdrops Tor relays to enumerate bridges, and then discuss and compare two possible designs of bridge guards in this research.
• 馮菲, 松浦幹太. 網羅的な攻撃者モデルを考慮したTorブリッジ機構の強化, Stronger Bridge Mechanisms of Tor Considering Exhaustive Adversarial Models, 2014年コンピュータセキュリティシンポジウム（CSS2014）予稿集, CD-ROM, 2014 [detail]

abstract

Torは世界中で広く使われている匿名通信ツールであるが、その匿名性は十分に分析されていない。 公開されている中継リレーをブロックすることによるアクセス制限もTorへの脅威となりえるが、 この脅威に対処するためにTorはエントリーポイントとしてブリッジと呼ばれる非公開リレーを利用することができる。 しかし、現在のブリッジ機構の脆弱性はまだ十分に調査されているとは言えない。 本研究ではさまざまな攻撃モデルのもとでブリッジ機構の脆弱性評価を行う。 そして、現在のブリッジ機構を我々が提案する新たな二種類のブリッジ機構と比較し、 Torのセキュリティとパフォーマンスの与える影響について論ずる。 Tor is the most popular anonymous communication tool in the world. Its anonymity, however, has not been thoroughly evaluated. For example, it is possible for an adversary to restrict access to the Tor network by blocking all the publicly listed relays. In response, Tor utilizes \textit{bridges}, which are unlisted relays, as alternative entry points. However, the vulnerabilities of the current bridge mechanism have not been thoroughly investigated yet. We first investigate the vulnerabilities of the current bridge mechanism under different adversarial models. Then we compare it with two different methods and discuss their effects on security and performance of Tor.
• 馮菲, 松浦幹太. Towards Better Parameters of Tor's Entry Guard Mechanism, 2014年暗号と情報セキュリティシンポジウム（SCIS2014）予稿集, CD-ROM, 2014
• 馮菲, 松浦幹太. Torネットワークに対する戦略的攻撃とその脅威の検証, Towards an Analysis of a Strategic Attack against the Tor Network, コンピュータセキュリティシンポジウム 2013 論文集, CD-ROM, 2013

碓井 利宣

• 修士課程

研究テーマ

• マルウェア対策技術、不正検知

Publications

• 包含，碓井利宣，松浦幹太. 特徴選択によるマルウェアの最適化レベル推定精度向上, 2015年暗号と情報セキュリティシンポジウム（SCIS2015）予稿集, CD-ROM, 2015 [detail]

abstract

マルウェアの亜種は増加し続けているため，マルウェアを挙動別に自動分類するのは静的解析の 効率化の上で重要である． ところが，マルウェアの元のソースコードが同じでも，コンパイラが 出力する機械語命令列の類似度はコンパイラ自体やその最適化レベルを変えることによって大きく 低下し得る． マルウェアを機械語命令列ベースに分類する場合，この影響は看過できない． 本研究ではマルウェアの最適化レベルの推定を行う際に． 特徴選択によってその精度を向上させる 手法を提案する． 分類実験の対象として MinGW の最適化レベル (O0～O3) を扱い，オペコード列に 対する N-gram を特徴として機械学習で推定した． 実際に異なる最適化レベル間で出現頻度が顕著に 変化する命令はそれほど多くないので，各命令パターンの出現頻度に着目して特徴選択を行った． 実験の結果，特徴選択を行わなかった場合と比べて精度は向上し，95%以上の精度で最適化レベルを推定できた．
• 碓井利宣，松浦幹太. マルウェア検知および分類に向けたコンパイラ再最適化, 2015年暗号と情報セキュリティシンポジウム（SCIS2015）予稿集, CD-ROM, 2015 [detail]

abstract

増加するマルウェアの脅威に対応するために，マルウェアの検知や分類を自動で行うことは重要である． マルウェアの検知や分類は，ソフトウェアの類似性に基づいて行われる． 同種や亜種のマルウェア同士 であれば，その類似性は十分に高いという仮定のもとで，類似度が高く算出されたものを検知，分類 する． しかし，たとえ同じソースコードから生成されたマルウェアであっても，生成に用いられた コンパイラや最適化レベルの違いによって機械語命令列は異なるという問題がある． それにより， 類似度の算出も影響を受けるため，検知や分類の精度は低下してしまう． 本研究では，マルウェアの 実行ファイルを再び最適化することで，生成に用いられたコンパイラおよび最適化レベルによる差異を 吸収する手法を提案する． まず，マルウェアの機械語命令列から中間表現を生成する． そして，マルウェアの 生成に用いられたコンパイラおよび最適化レベルを推定し，それに合わせた中間表現の最適化やコード生成を 実施する． このシステムを，バイナリ解析プラットフォームであるBAP とコンパイラ基盤であるLLVM によって実現した． 実験を通して，本手法の有効性を示した．
• 碓井利宣，松浦幹太. 機械語命令列の差異によるマルウェア対策技術への影響の削減を目的とした隠れマルコフモデルに基づくコンパイラ推定手法, 2014年暗号と情報セキュリティシンポジウム（SCIS2014）予稿集, CD-ROM, 2014
• 碓井利宣，松浦幹太. マルウェア対策技術の精度向上を目的としたコンパイラおよび最適化レベルの推定手法, マルウェア対策研究人材育成ワークショップ 2013 (MWS 2013), CD-ROM, 2013 [detail]

abstract

マルウェアによる脅威が増加している． これらに対して効果的な対策を実施していくに は，マルウェアの実行ファイルが持つ様々な情報を最大限に利用することが必要である． 機械語命 令列は，マルウェアの動作に関わる重要な情報である． しかし，コンパイラの種類や最適化レベ ルなどの要素によって性質を大きく変え得るため，マルウェア対策に用いることが難しい． 本研 究では，実行ファイルの生成に用いられたコンパイラの種類および最適化レベルを推定する手法 を提案する． 実装したシステムを用いてマルウェア検体に対して実験を行う． その結果を通して， 本研究がコンパイラがマルウェア対策に与える影響をどのように削減できるかについて，論じる． For effective countermeasures against malwares, we need to utilize all the utilizable information which belongs to malwares’ executable files. Machine instruction sequence is an important information which is relevant to malwares’ behavior. However, utilizing the information is difficult because varieties of compilers and optimization levels tend to affect strongly. In this paper, we propose a method to specify the compiler and optimization level that are adopted to generate the executable files of malwares. Additionally, experimentations are conducted with the datasets of malware samples. This paper also discusses how the proposed method decreases ill effects against anti-malware technologies caused by compilers.
• Toshinori Usui, Tomonori Ikuse, Yuto Otsuki, Yuhei Kawakoya, Makoto Iwamura, Jun Miyoshi, Kanta Matsuura. ROPminer: Learning-based Static Detection of ROP Chain Considering Linkability of ROP Gadgets, IEICE Transactions on Information and Systems, Vol.E103-D, No.7, pp.1-17, 2020 [detail]

abstract

Return-oriented programming (ROP) has been crucial for attackers to evade the security mechanisms of recent operating systems. Although existing ROP detection approaches mainly focus on host-based intrusion detection systems (HIDSes), network-based intrusion detection systems (NIDSes) are also desired to protect various hosts including IoT devices on the network. However, existing approaches are not enough for network-level protection due to two problems: (1) Dynamic approaches take the time with second- or minute-order on average for inspection. For applying to NIDSes, millisecond-order is required to achieve near real time detection. (2) Static approaches generates false positives because they use heuristic patterns. For applying to NIDSes, false positives should be minimized to suppress false alarms. In this paper, we propose a method for statically detecting ROP chains in malicious data by learning the target libraries (i.e., the libraries that are used for ROP gadgets). Our method accelerates its inspection by exhaustively collecting feasible ROP gadgets in the target libraries and learning them separated from the inspection step. In addition, we reduce false positives inevitable for existing static inspection by statically verifying whether a suspicious byte sequence can link properly when they are executed as a ROP chain. Experimental results showed that our method has achieved millisecond-order ROP chain detection with high precision.

片山 慶介

• 研究生

研究テーマ

• 生体認証

村上 隆夫

• 博士課程

研究テーマ

• 生体認証

Publications

• Kenta Takahashi, Takao Murakami. A Measure of Information Gained through Biometric Systems, Elsevier Image and Vision Computing, Vol.32, No.12, pp.1194-1203, 2014 [detail]

abstract

We propose a measure of information gained through biometric matching systems. Firstly, we discuss how the information about the identity of a person is derived from biometric samples through a biometric system, and define the "biometric system entropy" or BSE based on mutual information. We present several theoretical properties and interpretations of the BSE, and show how to design a biometric system which maximizes the BSE. Then we prove that the BSE can be approximated asymptotically by the relative entropy D(fG(x) || fI(x)) where fG(x) and fI(x) are probability mass functions of matching scores between samples from individuals and among population. We also discuss how to evaluate the BSE of a biometric systemand show experimental evaluation of the BSE of face, fingerprint and multimodal biometric systems.
• 村上隆夫，高橋健太，松浦幹太. IDレス生体認証における最適な逐次融合判定に向けて—ゆう度比判定方式の最適性の証明と実験的評価—, 電子情報通信学会和文論文誌A, Vol.J97-A, No.12, pp.710-725, 2014 [detail]

abstract

IDレス認証では，ユーザが（IDやカードを提示せずに）生体情報のみを入力することで認証が行われるため， 利便性の非常に高い認証サービスを実現できる． しかしながら，IDレス認証では登録ユーザ数の増加に伴って 認証精度が劣化し，大規模ユーザシステムに適用する上での課題となっている． IDレス認証の精度を利便性を 保ったまま高めるため，生体情報が入力される度に得られた生体情報を融合してユーザを判定する逐次融合 判定方式が提案されている． 本論文ではIDレス認証における逐次融合判定方式として，高速に実行可能な 尤度比判定方式に着眼し，この方式が持つ精度と利便性の観点での最適性を理論的に証明する． 具体的には， 尤度比判定方式が精度に関する要求値を満たしつつ，生体情報の平均入力回数を最小化できることを， 多重仮説検定においてデータの平均観測回数を最小化できるMSPRT（Multi-hypothesis Sequential Probability Ratio Test）との等価性を証明することによって示す． また，尤度比判定方式の有効性を， OR判定方式とFAR積判定方式との比較を通して実験的にも示す．
• Takao Murakami, Kenta Takahashi, Kanta Matsuura. A General Framework and Algorithms for Score Level Indexing and Fusion in Biometric Identification, IEICE Transactions on Information and Systems, Vol.E97-D, No.3, pp.510-523, 2014 [detail]

abstract

Biometric identification has recently attracted attention because of its convenience: it does not require a user ID nor a smart card. However, both the identification error rate and response time increase as the number of enrollees increases. In this paper, we combine a score level fusion scheme and a metric space indexing scheme to improve the accuracy and response time in biometric identification, using only scores as information sources. We firstly propose a score level indexing and fusion framework which can be constructed from the following three schemes: (I) a pseudo-score based indexing scheme, (II) a multi-biometric search scheme, and (III) a score level fusion scheme which handles missing scores. A multi-biometric search scheme can be newly obtained by applying a pseudo-score based indexing scheme to multi-biometric identification. We secondly propose the NBS (Naive Bayes search) scheme as a multi-biometric search scheme and discuss its optimality with respect to the retrieval error rate. We evaluated our proposal using the datasets of multiple fingerprints and face scores from multiple matchers. The results showed that our proposal significantly improved the accuracy of the unimodal biometrics while reducing the average number of score computations in both the datasets.
• Takao Murakami, Kenta Takahashi, Kanta Matsuura. Toward Optimal Fusion Algorithms with Security against Wolves and Lambs in Biometrics, IEEE Transactions on Information Forensics and Security (IEEE TIFS), Vol.9, No.2, pp.259-271, 2014 [detail]

abstract

It is known that different users have different degrees of accuracy in biometric authentication, and claimants and enrollees who cause false accepts against many others are referred to as wolves and lambs, respectively. The aim of this paper is to develop a fusion algorithm, which has security against both of the animals while minimizing the number of query samples a genuine claimant has to input. To achieve our aim, we first introduce a taxonomy of wolves and lambs, and propose a minimum log-likelihood ratio-based sequential fusion scheme (MLR scheme). We prove that this scheme keeps wolf attack probability and lamb accept probability, the maximum of the claimant-specific false accept probability (FAP), and the enrolleespecific FAP, less than a desired value if log-likelihood ratios are perfectly estimated, except in the case of adaptive spoofing wolves. We also prove that this scheme is optimal with regard to false reject probability (FRP), and asymptotically optimal with respect to the average number of inputs (ANIs) under some conditions. We further propose an input order decision scheme based on the Kullback.Leibler (KL) divergence, which maximizes the expectation of a genuine log-likelihood ratio, to further reduce ANI of the MLR scheme in the case where the KL divergence differs from one modality to another. The results of the experimental evaluation using a virtual multimodal (one face and eight fingerprints) data set showed the effectiveness of our schemes.
• 加賀陽介，高橋健太，村上隆夫. GLMMに基づくテンプレートの品質推定と融合判定による生体認証の高精度化, 電子情報通信学会和文論文誌A, Vol.J96-A, No.12, pp.815-828, 2013 [detail]

abstract

生体認証システムの精度向上を目的とし，複数のテンプレートを認証に用いる手法が研究されている． 中でも，デバイスや認証手順を変えることなく精度を向上する手法として，同一生体から取得した複数の テンプレートを認証に用いる手法がある． これらの手法は，複数のテンプレートと，利用者から取得した 認証サンプルとを照合し，得られた複数の類似度を融合することで本人か否かの判定を行う． 従来手法では， 融合方式として各類似度に対する平均値等，各類似度を等価に扱う演算を採用しており，各類似度が同一分布に 従うことを前提としていた． しかしながら，テンプレートの品質に大きなばらつきがある場合，類似度分布に同一性が 仮定できないため，従来の融合判定では十分な認証精度が達成できない可能性がある． そこで本稿では， 一般化線形混合モデルを用いてテンプレートの品質を推定し，その品質を用いて融合判定を行う方式を提案する． 提案手法では，類似度が従う確率分布の差を混合効果としてモデル化することで，テンプレートの品質に大きな差が ある場合でも高精度な認証を実現する． また，指紋画像を用いた評価実験を行い，提案手法の有効性を確認する．
• 村上隆夫，高橋健太，松浦幹太. 大規模IDレス生体認証に向けた逐次索引融合判定の提案, 電子情報通信学会和文論文誌A, Vol.J96-A, No.12, pp.801-814, 2013 [detail]

abstract

ユーザが生体情報のみを入力することで認証が行われるIDレス認証の利便性の高さが注目を集めている． しかしながら，IDレス認証では登録ユーザ数の増加に伴って認証時間と認証誤り率が増加し，大規模ユーザ システムに適用する上での課題となっている． 本論文は，あらゆる種類の生体情報に適用可能で，かつ複数の 生体情報を用いながらも入力回数を抑制可能なIDレス認証の高速・高精度化技術の実現を目的とする． まず（I）擬似スコアに基づく距離索引法，（II）逐次検索法，（III）欠損スコアを扱う逐次融合判定法の 3つから構成される逐次索引融合判定法の一般的フレームワークを提案する． このうち逐次検索法は， 本フレームワークを実現するために新たに必要となる手法である． 次に，検索誤り率の最小化を目的として， 認証ユーザ本人のものである事後確率の大きい順にテンプレートとの照合を行なうベイズ逐次検索法と， 距離索引法における最適なpivot数の自動決定法を提案する． 顔と指紋の大規模データセットを用いた評価実験を行い， 提案手法によって生体情報の平均入力回数を抑えつつ，照合回数と認証誤り率を大幅に削減できることを示す．
• 村上隆夫，高橋健太，松浦幹太. IDレス生体認証における最適な逐次融合判定について, バイオメトリクス研究会（BioX研究会）, pp.34-39, 2013 [detail]

abstract

IDレス認証では，ユーザが（IDやカードを提示せずに）生体情報のみを入力する ことで認証が行われるため，非常に利便性の高い認証サービスを実現できる． し かしながら，IDレス認証では登録ユーザ数の増加に伴って認証誤り率が増加し， 大規模ユーザシステムに適用する上での課題となっている． IDレス認証の認証精 度を利便性を保ったまま高めるため，生体情報が入力される度に得られたスコア を融合してユーザを判定する逐次融合判定が提案されている． 本稿では，IDレス 認証の精度と利便性を両立する理論的基盤の構築を目的とし，逐次融合判定の一 つである尤度比判定方式が持つ精度と利便性の観点での最適性を証明する． 具体 的には，尤度比判定方式が多重仮説検定においてデータの平均観測回数を最小化 できるMSPRT（Multi-hypothesis Sequential Probability Ratio Test）と等価 であることを示すことで，生体情報の平均入力回数を最小化できることを特定の 条件下で証明する．
• Takao Murakami, Kenta Takahashi, Susumu Serita, Yasuhiro Fujii. Probabilistic Enhancement of Approximate Indexing in Metric Spaces, Elsevier Information Systems, Vol.38, No.7, pp.1007-1018, 2013 [detail]

abstract

Some approximate indexing schemes have been recently proposed in metric spaces which sort the objects in the database according to pseudo-scores. It is known that (1) some of them provide a very good trade-off between response time and accuracy, and (2) probability-based pseudo-scores can provide an optimal trade-off in range queries if the probabilities are correctly estimated. Based on these facts, we propose a probabilistic enhancement scheme which can be applied to any pseudo-score based scheme. Our scheme computes probability-based pseudo-scores using pseudo-scores obtained from a pseudo-score based scheme. In order to estimate the probability-based pseudoscores, we use the object-specific parameters in logistic regression and learn the parameters using MAP (Maximum a Posteriori) estimation and the empirical Bayes method. We also propose a technique which speeds up learning the parameters using pseudo-scores. We applied our scheme to the two state-of-the-art schemes: the standard pivot-based scheme and the permutation-based scheme, and evaluated them using various kinds of datasets from the Metric Space Library. The results showed that our scheme outperformed the conventional schemes, with regard to both the number of distance computations and the CPU time, in all the datasets.
• 加賀陽介，高橋健太，村上隆夫，高田治，坂崎尚生. 一般化線形混合モデルに基づく生体認証システムに関する検討, 第1回バイオメトリクス研究会（BioX研究会）, 2012 [detail]

abstract

生体認証システムの精度向上を目的とし，複数の生体情報を登録して認証に用 いる手法が研究されている． これらの手法は，複数の登録生体情報と利用者から 取得した生体情報とを照合し，得られた類似度に対して 統計処理を行うことで本 人か否かの判定を行う． 従来手法では，この統計処理が各類似度に対する平均値等， 各類似度を等価に扱う演算となっており，各類似度が従う確率分布の差を考 慮していなかった． しかしながら， 登録生体情報の品質に大きなばらつきがある 場合，各登録生体情報から算出された類似度が従う確率分布が異なるため， この ような判定処理では十分な認証精度が達成できない可能性がある． 筆者らは，こ の問題を解決するため， 一般化線形混合モデルを活用して高精度に判定を行う認 証方式を提案した． しかしながら，この方式は生体情報を 追加登録する度に一般 化線形混合モデルによるパラメータ推定をやり直す必要があり，計算量が多いと いう課題が あった． そこで本稿では，一般化線形混合モデルに基づくパラメータ 推定を事前に行い，生体情報を追加登録する 際には，一部のパラメータを最尤推定により高速に求める方式を提案する． 本稿の最後では，指紋画像を用いた評価 実験を行い，提案手法の有効性を確認する．
• 村上隆夫，高橋健太，松浦幹太. WolfとLambに対する安全性と最適性を持つ融合判定の理論的考察, 第1回バイオメトリクス研究会（BioX研究会）, 2012 [detail]

abstract

生体認証において，数多くのユーザに対して高い類似度スコアを実現する認証 ユーザ，登録ユーザはそれぞれWolf， Lambと呼ばれており，生体認証の安全性を 大きく低下させる要因として知られている． 本稿では，WolfとLambによる 他人受 入率を一定値以下に保ちつつ，生体情報の入力回数を最小化することを目的とし た逐次的融合判定方式を 提案する． まず，スコア分布が完璧に学習できるという 条件の下で，提案手法がWAP（Wolf Attack Probability） とLAP（Lamb Accept Probability）を一定値以下に抑えられることを証明する． 次に，より理想的な 条件の下で， 提案手法が持つ生体情報の平均入力回数（ANI：Average Number of Input）の観点での最適性を証明する． 最後に， 提案手法の安全性と最適性を満 たすための条件や，登録時のLamb対策，Anti-spoofingなどの他のWolf，Lamb対策 との組合せについて考察を行う．
• Takao Murakami, Kenta Takahashi, Kanta Matsuura. Towards Optimal Countermeasures against Wolves and Lambs in Biometrics, Proceedings of the IEEE Fifth International Conference on Biometrics: Theory, Applications and Systems (BTAS 2012), 2012 [detail]

abstract

Claimants and enrollees who have high similarity scores against many others are referred to as wolves and lambs, respectively. These animals can cause false accepts against many others and compromise the security of the system. The aim of this paper is to develop a fusion algorithm which has security against both of them while minimizing the number of query samples the genuine claimant has to input. To achieve this aim, we first propose a minimum log-likelihood ratio based sequential fusion scheme (MLR scheme). We prove that the MLR scheme keeps WAP (Wolf Attack Probability) and LAP (Lamb Accept Probability), the maximum of the claimant-specific FAR and the enrollee-specific FAR, less than the desired value if the score distributions are perfectly estimated, except in the case of adaptive spoofing wolves. We also prove that the MLR scheme is nearly optimal with respect to the average number of inputs (ANI) of the genuine claimant under some conditions. We secondly propose an input order decision scheme based on the KL (Kullback-Leibler) divergence which maximizes the expectation of the genuine loglikelihood ratio, to further reduce ANI of the MLR scheme in the case where the KL divergence differs from one modality to another. The results of the experimental evaluation using the CASIA-FingerprintV5 showed the effectiveness of our schemes.
• 高橋健太，村上隆夫，加賀陽介，松原佑生子，米山裕太，本部栄成， 西垣正勝. テンプレート公開型生体認証基盤, 2012年暗号と情報セキュリティシンポジウム（SCIS2012）予稿集, CD-ROM, 2012 [detail]

abstract

ネットワーク社会の拡大や行政サービスの電子化に伴い，個人認証基盤の重要性が高まっている． 従来，個人認証基盤としてはPKI を用いることが一般的であったが，PKI はIC カードや暗証番号を 前提とするため，利便性（紛失，忘失の可能性），安全性（盗用によるなりすまし），コスト （カードライフルサイクル管理）の問題があり，普及が進んでいない． 本稿ではまず，持物・記憶が 不要な個人認証基盤として，公開可能な認証情報（テンプレート）に基づくセキュリティ基盤 （テンプレート公開型生体認証基盤）の概念を提案し，機能要件を明らかにするとともに，これを 実現する要素技術を提案する．
• 加賀陽介，高田治，村上隆夫，高橋健太. 一般化線形混合モデルに基づく生体認証に関する検討, 2012年暗号と情報セキュリティシンポジウム（SCIS2012）予稿集, CD-ROM, 2012 [detail]

abstract

生体認証システムの精度向上を目的とし，複数の生体情報を登録して認証に用いる手法が研究されている． これらの手法は，複数の登録生体情報と利用者から取得した生体情報とを照合し，得られた類似度に対して 統計処理を行うことで本人か否かの判定を行う． 従来手法では，この統計処理が各類似度に対する平均値等， 各類似度を等価に扱う演算となっており，各類似度が従う確率分布の差を考慮していなかった． しかしながら， 登録生体情報の品質に大きなばらつきがある場合，各登録生体情報から算出された類似度が従う確率分布が 異なるため，このような判定処理では十分な認証精度が達成できない可能性がある． そこで本稿では， 一般化線形混合モデルに基づく登録生体情報の品質評価を導入し，得られた各登録生体情報の品質に基づき 融合判定を行うことで，登録生体情報の品質を考慮した高精度な認証を行う手法を提案する． 本稿の最後では， 指紋画像を用いた評価実験を行い，提案手法の有効性を確認する．
• 高橋健太，村上隆夫. 情報量に基づく生体認証システムの個人識別性能評価指標, 第1回バイオメトリクスと認識・認証シンポジウム（SBRA2011）, 2011 [detail]

abstract

指紋や静脈，虹彩などを用いた生体認証技術の普及が進んでいる． 本発表では，個人識別情報とし て生体情報が持つ情報量について考察し，その評価指標を提案する． まず生体情報の情報量を相互情報 量として定義し，その漸近的な近似として，本人同士の照合スコア分布と他人同士の照合スコア分布の Kullback-Leibler 情報量が導かれることを示す． また従来の精度評価指標である ROC カーブとの関係や， マルチモーダルバイオメトリクスにおける情報量について考察する． 最後に，提案する指標に基づく具体 的な評価手順を述べ，指紋，顔，マルチモーダル認証システムに対する実験的評価を行う．
• Takao Murakami, Kenta Takahashi. Fast and Accurate Biometric Identification Using Score Level Indexing and Fusion, Proceedings of IEEE/IAPR International Joint Conference on Biometrics (IJCB 2011), CD-ROM, 2011 [detail]

abstract

Biometric identification provides a very convenient way to authenticate a user because it does not require the user to claim an identity. However, both the identification error rates and the response time increase almost in proportion to the number of enrollees. A technique which decreases both of them using only scores has the advantage that it can be applied to any kind of biometric system that outputs scores. In this paper, we propose such a technique by combining score level fusion and distance-based indexing. In order to reduce the retrieval error rate in multibiometric identification, our technique takes a strategy to select the template of the enrollee whose posterior probability of being identical to the claimant is the highest as a next to be matched. The experimental evaluation using the Biosecure DS2 dataset and the CASIA-FingerprintV5 showed that our technique significantly reduced the identification error rates while keeping down or even reducing the number of score calculations, compared to the unimodal biometrics.
• Takao Murakami, Kenta Takahashi, Susumu Serita, Yasuhiro Fujii. Versatile Probability-based Indexing for Approximate Similarity Search, Proceedings of 4th International Conference on SImilarity Search and APplications (SISAP 2011), pp.51-58, 2011 [detail]

abstract

We aim at reducing the number of distance computations as much as possible in the inexact indexing schemes which sort the objects according to some promise values. To achieve this aim, we propose a new probability-based indexing scheme which can be applied to any inexact indexing scheme that uses the promise values. Our scheme (1) uses the promise values obtained from any inexact scheme to compute the new probability-based promise values. In order to estimate the new promise values, we (2) use the object-specific parameters in logistic regression and learn the parameters using MAP (Maximum a Posteriori) estimation. We also propose a technique which (3) speeds up learning the parameters using the promise values. We applied our scheme to the standard pivot-based scheme and the permutation-based scheme, and evaluated them using various kinds of datasets from the Metric Space Library. The results showed that our scheme improved the conventional schemes, in all cases.

横手 健一

• 修士課程

研究テーマ

• ネットワークセキュリティ、ソフトウェアセキュリティ

Publications

• 横手 健一, 松浦 幹太 . 匿名通信システムTorの安全性を低下させるトラフィック逆加工, コンピュータセキュリティシンポジウム2012論文集, Vol.2012, No.3, pp.624-631, 2012 [detail]

abstract

匿名通信システムTor はトラフィックに様々な加工を施した上で通信を行うため，トラ フィックに着目した指紋攻撃に対してある程度の耐性を保持している． 本研究ではこの加工を打ち 消すような逆加工によって，Tor の安全性が更に低下することを示す． そして，この逆加工の潜在 的な脅威について議論し，Tor が解決すべき今後の課題について考察する．

高木 哲平

• 修士課程

研究テーマ

• ネットワークセキュリティ、機械学習

Publications

• 高木哲平　松浦幹太. DoS攻撃検知に向けたパケット単位コルモゴロフ複雑性差分の特性分析, コンピュータセキュリティシンポジウム2013 (CSS2013), 2013

Andreas Gutmann

• 訪問学生

研究テーマ

• 公開鍵暗号、証明可能安全性

Publications

• Andreas Gutmann, Kanta Matsuura. The use of linguistics in cryptography and its application to improve the HB protocol, コンピュータセキュリティシンポジウム2013 (CSS2013), CD-ROM, 2013 [detail]

abstract

1991年に松本と今井によって提案された人間識別プロトコル(Human Identification Protocol, HIP)は、 20年経った現在においても挑戦的な課題である。 HIPの最終的な目標は信頼されたハードウェアやソフトウェアを 用いずに証明者が人間かどうかを識別することであり、HopperとBlumによって2001年にLPN仮定に基づく最初のHIP (HBプロトコル)が提案された。 本研究ではHBプロトコルの改良を試みる。 具体的にはまず、より強力な攻撃モデルの 導入及び安全性モデルの拡張を行う。 その後、その安全性モデルを満たす改良方式を示す。 本研究の核となる アイディアは、人間の持つ識別能力と言語学的な知識の利用である。 More than 20 years after the introduction by Matsumoto and Imai, human identification protocols (HIP) are still a challenging task for the cryptographic community. One much-noticed HIP was designed by Hopper and Blum (HB) in 2001. In this paper, we provide a novel improvement to the HB protocol. As our main result, we first extend the HIP security model by assuming an attacker who predicts random decisions made by the human. Then we suggest an improvement--based on human cognitive abilities--to the HB protocol and prove it secure under the LPN assumption in this new threat model.

市川 顕

• 修士課程

研究テーマ

• ネットワークセキュリティ、ソフトウェアセキュリティ

Publications

• 市川顕, 松浦幹太. 実行プロセス分離によるJITシェルコード実行防止, 情報処理学会論文誌, Vol.53, No.9, pp.2302-2312, 2012
• 市川顕, 松浦幹太. 実行プロセス分離によるJITシェルコード実行防止とその実装・評価, 2012年暗号と情報セキュリティシンポジウム（SCIS2012）予稿集, CD-ROM, 2012 [detail]

abstract

JITコンパイラは従来のインタプリタよりもかなり高速に動作するため， 近年多くのアプリケーションに採用されるようになっている． しかし，JITコンパイラを悪用したJIT Sprayingという手法が公表されており問題となっている． JIT Spraying攻撃を利用すると，従来バッファオーバーフローなどの脆弱性攻撃対策に効果的であった Data Execution Prevention(DEP)やAddress Space Layout Ramdomization(ASLR)といった セキュリティ機構を回避することができてしまう． 本稿では，JIT Spraying攻撃を防止するための 手段として我々の提案したJITコンパイルされたコードの実行直前に新たなプロセスを生成し そのプロセス上でJITコンパイルされたコードを走らせる手法について説明し，その実装と評価について述べる． この手法はJITエンジンの修正を必要とするが，時間により脆弱になることがなく，生成されるコードの 変更も必要としない． また，実行時間のオーバーヘッドも実用上問題とならない程度である．
• Ken Ichikawa, Kanta Matsuura. Preventing execution of JIT shellcode by isolating running process, Annual Computer Security Applications Conference 2011, 2011
• 市川顕, 松浦幹太. 実行プロセス分離によるJITシェルコード実行防止, Computer Security Symposium2011 (CSS2011), CD-ROM, 2011 [detail]

abstract

JITコンパイラを悪用したJIT Sprayingという攻撃を利用すれば、DEPやASLRといった セキュリティ機構を突破し、バッファオーバーフロー攻撃などが可能になるとして話 題となっている。 JIT SprayingはJITコンパイラが仕様としてデータ領域に実行属性 を付加することにより生成コードがシェルコードとして使用され得ることを利用する。 本稿では、JITコンパイラにより生成されたコードを走らせるためにデータ領域に実 行属性を付けるプロセスをメインのプロセスとは分離し、メインのプロセスではデー タ領域に実行属性を付加させず、容易に攻撃ができないようなJITコンパイラの実装 方法について紹介する。
• 市川顕, 松浦幹太. 実行監視によるJIT Spraying攻撃検知, 第52回情報処理学会コンピュータセキュリティ研究会 (CSEC52）（情報処理学会研究報告）, Vol.2011, No.46, pp.download, 2011 [detail]

abstract

近年のウェブアプリケーションの興隆により、ウェブブラウザ上で動作する言語のエ ンジンにJITコンパイラが搭載される例が増えている。 しかし、JITコンパイラで生成 された実行コードはWindowsのセキュリティ機構であるDEPとASLRを回避することがで きるJIT Spraying攻撃に悪用される例が示されており、対策が必要とされている。 本 稿では、ユーザレベルでの実行監視によりJIT Spraying攻撃を検知し、攻撃コードが 実行される前にプログラムを停止させる手法について述べる。

松田 隆宏

• 博士課程

研究テーマ

• 暗号技術, 証明可能安全性, コンピュータセキュリティ

Publications

• Takao Murakami, Kenta Takahashi, Susumu Serita, Yasuhiro Fujii. Probabilistic Enhancement of Approximate Indexing in Metric Spaces, Elsevier Information Systems, 2012 [detail]

abstract

Some approximateindexing schemes have been recently proposed in metricspaces which sort the objects according to pseudo scores. It is known that (1) some of them provide a very good trade-off between response time and accuracy, and (2) the probability-based pseudo scores can provide an optimal trade-off in range queries if the probability is correctly estimated. Based on these facts, we propose a probabilistic enhancement scheme which can be applied to any approximateindexing scheme that computes a pseudo score for each object. Our scheme uses the pseudo scores obtained from the approximate scheme to compute the new probability-based pseudo scores. In order to estimate the new pseudo scores, we use the object-specific parameters in logistic regression and learn the parameters using MAP (Maximum a Posteriori) estimation and the empirical Bayes method. We also propose a technique which speeds up learning the parameters using the pseudo scores. We applied our scheme to the two state-of-the-art schemes: the standard pivot-based scheme and the permutation-based scheme, and evaluated them using various kinds of datasets from the MetricSpace Library. The results showed that our scheme outperformed the conventional schemes in all the datasets.
• Takahiro Matsuda, Goichiro Hanaoka, Kanta Matsuura. Relations between Constrained and Bounded Chosen Ciphertext Security for Key Encapsulation Mechanisms, Lecture Notes in Computer Science (Public Key Cryptography - PKC 2012, 15th International Conference on Practice and Theory in Public Key Cryptography: PKC 2012), Vol.7293, pp.576-594, 2012 [detail]

abstract

In CRYPTO 2007, Hofheinz and Kiltz formalized a security notion for key encapsulation mechanisms (KEMs), called constrained chosen ciphertext (CCCA) security, which is strictly weaker than ordinary chosen ciphertext (CCA) security, and showed a new composition paradigm for CCA secure hybrid encryption. Thus, CCCA security of a KEM turned out to be quite useful. However, since the notion is relatively new and its definition is slightly complicated, relations among CCCA security and other security notions have not been clarified well. In this paper, in order to better understand CCCA security and the construction of CCCA secure KEMs, we study relations between CCCA and bounded CCA security, where the latter notion considers security against adversaries that make a-priori bounded number of decapsulation queries, and is also strictly weaker than CCA security. Specifically, we show that in most cases there are separations between these notions, while there is some unexpected implication from (a slightly stronger version of) CCCA security to a weak form of 1-bounded CCA security. We also revisit the construction of a KEM from a hash proof system (HPS) with computational security properties, and show that the HPS-based KEM, which was previously shown CCCA secure, is actually 1-bounded CCA secure as well. This result, together with the above general implication, suggests that 1-bounded CCA security can be essentially seen as a "necessary" condition for a CCCA secure KEM.
• Anil Mundra, Anish Mathuria, Naveen Kumar, Takahiro Matsuda, Kanta Matsuura. Two Views on Hierarchical Key Assignment Schemes, 日本セキュリティ・マネジメント学会誌, Vol.25, No.3, pp.40-51, 2012 [detail]

abstract

A hierarchical key assignment scheme is a cryptographic mechanism for enforcing access control in hierarchies. Its role is fundamentally important in some computer security applications but its provable security is hard to achieve in the case of dynamic schemes. Therefore, in order to alleviate problems resulting from solely heuristic approaches, we need systematic views regarding design and implementation both from technical viewpoints and from managerial viewpoints. In this commentary, we aim at providing those views in the following manner. The first one is from technical viewpoints: we describe a progressive construction of hierarchical key assignment schemes to make design issues as systematic as possible. The constructed schemes are basically from existing literatures but with some refinements for security reasons and/or to make the construction more instructive. The second one is from managerial viewpoints: based on security economics, we suggest the importance of deterrents to attacks in system implementations. Our discussions include the applications in which a large hierarchy is required like secure outsourcing of data on cloud.
• Takahiro Matsuda, Kanta Matsuura. On Black-Box Separations among Injective One-Way Functions, Lecture Notes in Computer Science (Theory of Cryptography, 8th Theory of Cryptography Conference: TCC 2011), Vol.6597, pp.597-614, 2011
• Takahiro Matsuda, Kanta Matsuura. Parallel Decryption Queries in Bounded Chosen Ciphertext Attacks, Lecture Notes in Computer Science (Public Key Cryptography - PKC 2011, 14th International Conference on Practice and Theory in Public Key Cryptography: PKC 2011), Vol.6571, pp.246-264, 2011 [detail]

abstract

Whether it is possible to construct a chosen ciphertext secure (CCA secure) public key encryption (PKE) scheme only from a chosen plaintext secure (CPA secure) one is a well-known fundamental open problem, and the best known positive results regarding this problem are the construction of so-called bounded CCA secure schemes. Since we can achieve the best possible security in the bounded CCA security notions, in order to further tackle this problem, we would need other new security notions that capture intermediate security notions that lie between CPA and CCA security. Motivated by this situation, in order to provide a theoretical foundation for further tackling the above problem, we focus on ''parallel'' decryption queries (originally introduced by Bellare and Sahai[BS99]) for the extension of bounded CCA security, and introduce a new security notion which we call mixed CCA security. It captures the security against adversaries that make single and parallel decryption queries in a predetermined order, where each parallel query can contain unboundedly many ciphertexts. Moreover, how the decryption oracle is available before and after the challenge is also taken into account in this new security definition, which enables us to capture existing major security notions that lie between CPA and CCA security, including complex notion like non-malleability against bounded CCA, in a unified security notion. We investigate the relations among mixed CCA security notions, and show a necessary and sufficient condition regarding implications/separations between any given two notions in mixed CCA security. We then show two black-box constructions of PKE schemes from CPA secure ones, one of which satisfies strictly stronger security notions than the security notions achieved by the existing constructions of PKE schemes constructed only from a CPA secure one. We also discuss the consequences of our results regarding security with parallel decryption queries, give several observations, and leave some open problems.
• 松田隆宏, 花岡悟一郎, 松浦幹太. KEMのConstrained CCA安全性と回数制限付きCCA安全性の関係, 2011年暗号と情報セキュリティシンポジウム（SCIS2011）予稿集, CD-ROM, 2011 [detail]

abstract

CRYPTO’07 において、Hofheinz と Kiltz は、伴カプセル化メカニズム (Key Encapsulation Mechanism, KEM) について、 選択暗号文攻撃 (Chosen Ciphertext Attack, CCA) に対する安全性よりも弱い安 全性である”Constrained CCA”(以下 CCCA) 安全性を定義し、それを用いたハイブリッド暗号の構成法を 示した。 しかし、CCCA 安全性は導入されてから歴史が浅く、また定義がやや難解であるため、CCA 安 全性よりは弱い安全性であることは明らかだが、“どの程度” 弱いのかが分かりにくい。 そこで本稿では、 CCCA 安全性とは別の意味で CCA 安全性よりも弱い安全性である回数制限付き CCA (Bounded CCA) 安全性との包含/隔離の関係を示し、CCCA 安全性と他の既存の安全性との関係を明らかにする。 また、本 稿では CCCA 安全な KEM と関係が深い “(計算量的) ハッシュ証明システム”(Hash Proof System, HPS) について、過去の文献では不足していると思われる定義を導入し、HPS と Bounded CCA 安全な KEM の 関係を示す。 これらの成果は、CCCA 安全な KEM や HPS を構成するための必要条件を示すものであり、 今後 KEM や HPS を構成する際に良い知見を与えると考えられる。
• 松田隆宏, 松浦幹太. 単一型と並行型の復号クエリを考慮した回数制限付き選択暗号文攻撃に対する安全性定義間の関係, 2011年暗号と情報セキュリティシンポジウム（SCIS2011）予稿集, CD-ROM, 2011 [detail]

abstract

公開鍵暗号(Public Key Encryption、PKE)の安全性として望ましいとされるのは、選択暗号文攻撃に対する安全性(CCA 安全性)である。 我々は過去の研究において、より基礎的な要素技術(特に、選択平文攻撃に対してのみしか安全でないPKE方式)や計算量的仮定からCCA安全なPKEを構成できるかどうかを明らかにする研究の理論的基盤として、 ''事前に決められた回数、順序で、''単一型''と'' 並行型''の復号クエリを行う攻撃者に対する安全性(単一型と並行型の復号クエリの両方を行う攻撃者を考えるため、''Mixed'' CCA安全性と呼ぶ)を定義した。 しかし、過去のMixed CCA安全性の定義については、Bounded CCA安全性の様に、チャレンジ前後にまたがる復号クエリが用いられる安全性は直接扱えず、安全性の組み合わせを考えねばならないという問題点があり、また、 安全性定義間の包含/隔離の関係などは未知であった。 本稿ではPKEとその類似技術である鍵カプセル化メカニズム(Key Encapsulation Mechanism、KEM)について、過去のMixed CCA安全性の定義をチャレンジ前と後にまたがって行える復号クエリを考慮した定義へと改良し、さらに、2つのMixed CCA安全性を与えられたとき、片方の安全性がもう片方の安全性を包含/隔離する必要十分条件を明らかにする。 これによって、どの様な複雑なMixed CCA安全性を2つを考えても、その2つがMixed CCA安全性の枠組みに当てはまる限りは、必ず包含/隔離の関係を示せる。 興味深いことに、PKEの場合、平文空間のサイズによって安全性定義間の関係が異なる。
• 松田隆宏, 松浦幹太. 単写の一方向関数のブラックボックス構成の不可能性について, 2011年暗号と情報セキュリティシンポジウム（SCIS2011）予稿集, CD-ROM, 2011 [detail]

abstract

一方向置換(One-Way Permutation、OWP)は最も基礎的な暗号要素技術の一つであり、大部分の''共通鍵系''の要素技術や、公開鍵系の要素技術である電子署名など、これまで''OWPのみを用いて何を一般的に構成できるか''については多くのことが明らかにされてきた。 しかしそれに比べ、''何からOWPを構成できる(できない)のか''についての研究はそれほど多くない上に、いくつかの要素技術からは、''ブラックボックス構成''と呼ばれる構成が不可能性であると明らかにされている。 本稿でも後者の''何からOWPを構成できる(できない)のか''という問題について取り組む。 具体的な成果として、本稿ではOWPと非常に近い性質を持つ要素技術である''単写かつ長さ増加(出力長が入力長より真に大きい)''の一方向関数(One-Way Function、OWF)からは、例えその関数の出力長と入力長の差が1(ビット)しかなく、かつ通常より強い一方向性を満たしていても、OWPをブラックボックス構成することが不可能であることを示す。 その結果の系として、正則性が1より大きい正則OWFからOWPのブラックボックス構成が不可能であることも示す。 OWPが長さ保存(入力長と出力長が等しい)、単写、かつ正則性が1のOWFであることを考えると、本稿の成果により、例えOWPと非常に近い性質を持つ要素技術を用いても、(ブラックボックス構成以外の構成法が可能かもしれないとは言え)OWPを構成することは絶望的に難しいことが分かる。 また、上記の成果を拡張し、どれだけ出力長と入力長の差があるかに基づいて、単写OWFの間のある制限されたクラスのブラックボックス構成不可能性を示す。 後者の成果により、OWPを含む単写OWFの中にはブラックボックス構成による階層が存在することが分かる。
• Takahiro Matsuda, Yasumasa Nakai, Kanta Matsuura. Efficient Generic Constructions of Timed-Release Encryption with Pre-open Capability, Lecture Notes in Computer Science (Pairing-Based Cryptography, 4th International Conference on Pairing-Based Cryptography: Pairing 2010), Vol.6487, pp.225-245, 2010 [detail]

abstract

Timed-release encryption with pre-open capability (TRE-PC), introduced by Hwang et al.[HYL05], is a cryptosystem with which a sender can make a ciphertext so that a receiver can decrypt it by using a timed-release key provided from a trusted agent called time-server at a predetermined release-time, or by using a special information called pre-open key provided from the sender before the release-time, and thus adds flexibility to ordinary TRE schemes in many practical situations. Recently, Nakai et al.[NMKM09] proposed a generic construction of a TRE-PC scheme from a public-key encryption scheme, an identity-based encryption scheme (with some special property), and a signature scheme. Although their construction enables us to construct many TRE-PC schemes based on existing primitives, Concrete TRE-PC schemes derived via their generic construction are, however, not so practical because of the used building block primitives. Motivated by this situation, in this paper we propose two new generic consructions of TRE-PC schemes. Both of our generic constructions employ the KEM/DEM structure, are quite generic in the sense that they enable us to construct TRE-PC schemes from a combination of ordinary KEMs, identity-based KEMs, and symmetric-key primitives, and do not use a one-time signature scheme. Our first construction utilizes a [tag-KEM] as one of main building blocks, which has been widely studied since it was introduced by Abe et al.[AGK08] and can also be built from any ordinary KEM, and is suitable for constructing standard model TRE-PC schemes. Our second construction uses a random oracle, and is suitable for constructing TRE-PC schemes based on existing building block primitives that already use random oracles. Concrete TRE-PC schemes derived from our generic constructions are comparable to or more efficient than the currently known TRE-PC schemes in terms of ciphertext overhead size and computation costs.
• 松田隆宏, 松浦幹太. 開封時刻の秘匿性を持つ事前開封機能付きタイムリリース暗号の一般的な構成法, 情報処理学会コンピュータセキュリティシンポジウム2010(CSS2010), pp.681-686, 2010 [detail]

abstract

本稿では、事前開封機能付きタイムリリース暗号(Timed-Release Encryption with Pre-Open Capability, TRE-PC)の、既存の要素技術の組み合わせによる新たな一般的構成法を提案する。 また、この構成法を元に、構成要素を追加したり効率を落としたりせずに、''開封時刻の秘匿性'' (Release-time Confidentiality)を持つTRE-PCの一般的構成法も示す。 開封時刻の秘匿性とは、暗号文が正当な受信者以外にはいつの時刻に向けて暗号化されたかという情報を漏らさないという性質である。 これまでの一般的構成法とは異なり、提案構成から、既存の具体的なTRE-PC方式と比べて同等か、それ以上の効率を持つスタンダードモデルの方式を得られる。 提案する2つの構成はタイムサーバ(時刻ごとの暗号文開封情報を発行する機関)と利用者の鍵ペアを共有できるため、利用者が目的やアプリケーションに応じて開封時刻の秘匿性が必要かどうかを柔軟に選ぶことができるようなTRE-PCシステムの実装も可能である。
• 松田隆宏, 松浦幹太. Mixed CCA安全性: より強い安全性を持つ公開鍵暗号方式のCPA安全な方式のみを用いた構成, 2010年暗号と情報セキュリティシンポジウム（SCIS2010）予稿集, CD-ROM, 2010 [detail]

abstract

あらまし選択平文攻撃に対して安全(CPA 安全) な公開鍵暗号(PKE) 方式のみを組み合わせて構成 できるPKE 方式が達成可能な安全性の中で、現在知られる最も強い安全性は回数制限付き選択暗号文攻 撃に対する安全性(Bounded CCA 安全性)、あるいは一回の並行型の復号クエリのみが可能な選択暗号 文攻撃に対する安全性(1-Bounded Parallel CCA 安全性) である。 これらの安全性よりもさらに強い安 全性を持つPKE 方式の構成が可能なことを示すため、本稿ではまずBounded CCA 安全性とBounded Parallel CCA 安全性を一般化した“Mixed CCA 安全性” を導入する。 Mixed CCA では、攻撃者は通常 の単一暗号文のみの復号クエリと並行型の復号クエリを事前に決められた順序で行うことができる。 こ の定義を用い、CPA 安全な方式のみを用いて構成したPKE 方式の中で、既存のどの構成法よりも真に 強い安全性を持つPKE 方式を示す。

keywords

PKE、KEM、回数制限付きCCA 安全性、Mixed CCA 安全性
• 松田隆宏, 松浦幹太. 公開鍵暗号の回数制限付き選択暗号文攻撃に対する安全性, 2010年暗号と情報セキュリティシンポジウム（SCIS2010）予稿集, CD-ROM, 2010 [detail]

abstract

あらまし選択平文攻撃に対する安全性(CPA 安全性) しか持たない公開鍵暗号(PKE) 方式のみから 選択暗号文攻撃に対する安全性(CCA 安全性) を持つPKE 方式を構成できるかどうかは未解決の問題と して知られている。 CPA 安全な方式のみから構成できるPKE 方式が達成可能な安全性の中で、現在知 られる最も強いものは回数制限付き選択暗号文攻撃に対する安全性(Bounded CCA 安全性) である。 そ の一方で、一部の不可能性が分かっている以外は、CPA 安全なPKE 方式から(無制限の)CCA 安全性を 持つ方式を構成する方法は知られていない。 本稿ではこの問題に対するさらなる可能性及び不可能性の 議論のため、PKE 方式及び鍵カプセル化メカニズム(KEM) に対して、Bounded CCA 安全性を拡張し た回数制限付き「並行型」選択暗号文攻撃に対する安全性(Bounded Parallel CCA 安全性) を導入する。 この攻撃では、攻撃者は複数の暗号文を一度の復号クエリとして問い合わせることができる。 本稿では まずBounded Parallel CCA 安全性と既存の安全性との関係をPKE とKEM の各々の場合について調べ る。 次に1 回の並行型クエリに耐性を持つ(1-Bounded Parallel CCA 安全性を持つ)PKE 方式を、CPA 安全な方式のみから構成できることを示す。 さらに、本稿での結果から導かれることについて議論する。

keywords

PKE、KEM、Bounded CCA 安全性、Bounded Parallel CCA 安全性、並行型復号クエリ
• Takahiro Matsuda, Kanta Matsuura, Jacob C. N. Schuldt. Efficient Constructions of Signcryption Schemes and Signcryption Composability, Lecture Notes in Computer Science (Progress in Cryptology, 10th International Conference on Cryptology in India: INDOCRYPT 2009), Vol.5922, pp.321-342, 2009 [detail]

abstract

In this paper, we investigate simple, but efficient constructions of signcryption schemes. Firstly, we show how symmetric primitives can be used to efficiently achieve outsider security, leading to a signcryption scheme with the currently lowest ciphertext and computational overhead. This scheme provides outsider multi-user security. For the mixed security notions outsider confidentiality/insider unforgeability and insider confidentiality/outsider unforgeability, this approach yields lower ciphertext overhead and a higher level of security, respectively, compared to the current schemes. Secondly, we show a simple optimization to the well known ``sign-then-encrypt'' and ``encrypt-then-sign'' approaches to the construction of signcryption schemes, by using tag-based encryption. Instantiations with our proposed tag-based schemes yield multi-user insider secure signcryption schemes in the random oracle model which is at least as efficient as any other existing scheme both in terms of ciphertext overhead and computational cost. Furthermore, very efficient standard model signcryption schemes are achieved as well. Lastly, we show how signatures and encryption can be combined in a non-black-box manner to achieve higher efficiency than schemes based on the above approach. We refer to signature and encryption schemes which can be combined in this way as signcryption composable, and we show that a number of the most efficient standard model encryption and signature schemes satisfy this, leading to the most efficient standard model signcryption schemes. Since all of our constructions are fairly simple and efficient, they provide a benchmark which can be used to evaluate future signcryption schemes.
• 松田隆宏, シュルツ ヤコブ, 松浦幹太. 多人数環境を考慮したSigncryptionの簡潔な一般的構成法, 情報処理学会コンピュータセキュリティシンポジウム2009（CSS2009）論文集, pp.283-288, 2009 [detail]

abstract

本稿では、多人数環境での安全性を考慮した Signcryption の、既存の要素技術の組み合わせによる 簡潔な一般的構成法を複数提案する。 本稿で提案する外部者に対する安全性を持つ方式では、共通伴系の 要素技術 (共通伴暗号、MAC) が如何に有効かを示す。 また、公開伴暗号と署名方式の Sign-then-Encrypt 及び Encrypt-then-Sign による非常に有名で直感的な Signcryption の構成法において、”タグベース暗号” を用いることで、多人数環境における内部者安全を持つ Signcryption 方式を達成できることを示す。 我々 の提案手法は非常に直感的かつ簡潔であり、今後、個別の計算困難性に基づいて構成される Signcryption との比較のためのよい”ベンチマーク”となると考えられる。
• Takahiro Matsuda, Goichiro Hanaoka, Kanta Matsuura, Hideki Imai. An Efficient Encapsulation Scheme from Near Collision Resistant Pseudorandom Generators and Its Application to IBE-to-PKE Transformations, Lecture Notes in Computer Science (Topics in Cryptology: CT-RSA2009), Vol.5473, pp.16-31, 2009 [detail]

abstract

In [BK05], Boneh and Katz introduced a primitive called encapsulation scheme, which is a special kind of commitment scheme. Using the encapsulation scheme, they improved the generic transformation by Canetti, Halevi, and Katz[CHK04] which transforms any semantically secure identity-based encryption (IBE) scheme into a chosen-ciphertext secure public key encryption (PKE) scheme (we call the BK transformation). The ciphertext size of the transformed PKE scheme directly depends on the parameter sizes of the underlying encapsulation scheme. In this paper, by designing a size-efficient encapsulation scheme, we further improve the BK transformation. With our proposed encapsulation scheme, the ciphertext overhead of a transformed PKE scheme via the BK transformation can be that of the underlying IBE scheme plus 384-bit, while the original BK scheme yields that of the underlying IBE scheme plus at least 704-bit, for 128-bit security. Our encapsulation scheme is constructed from a pseudorandom generator (PRG) that has a special property called near collision resistance, which is a fairly weak primitive. As evidence of it, we also address how to generically construct a PRG with such a property from any one-way permutation.
• 松田隆宏, 花岡悟一郎, 松浦幹太, 今井秀樹. 効率の良いEncapsulation方式とIBE-to-PKE変換への応用, 2009年暗号と情報セキュリティシンポジウム（SCIS2009）予稿集, CD-ROM, 2009 [detail]

abstract

[BK05]において、BonehとKatzは 特殊なコミットメント方式のような ''Encapsulation''と呼ばれる要素技術を導入し、 それを用いることで Canettiら[CHK04]が 提案したIDベース暗号(IBE)から選択暗号文攻撃に対して安全な公開鍵暗号(PKE) を得るための変換手法の効率を改善した(BK変換と呼ぶ)。 BK変換によって得られるPKEの暗号文サイズは 変換に使われるEncapsulation方式のパラメータに大きく依存するが、 BonehとKatzが示した具体的なEncapsulation方式はパラメータサイズがやや大きいものだったため、 彼らのEncapsulation方式を使うBK変換によって得られるPKEの 暗号文サイズは十分実用的であるとは言い難い。 本稿では、パラメータサイズの効率的なEncapsulation方式を提案することで BK変換のさらなる効率化を図る。 128ビット安全性が要求される場面において、 BonehとKatzによるEncapsulationを用いる場合は、 BK変換で得られるPKEの暗号文サイズと変換前のIBEの暗号文サイズの差 は少なくとも 704ビット必要であるが、 提案するEncapsulation方式を使えば 384ビットとできる。 (これ以上の改善を望むのは難しい)。 提案するEncapsulationは''近衝突困難性''と呼ばれる 特殊な性質を持つ擬似乱数生成器を用いて構成されるが、 これは非常に弱い仮定から実現できる要素技術である。 これを確認するために、 このような性質を持つ擬似乱数生成器を、 一方向置換のみから実際構成できることにも言及する。
• Takahiro Matsuda, Goichiro Hanaoka, Kanta Matsuura, Hideki Imai. Simple CCA-Secure Public Key Encryption from Any Non-Malleable Identity-Based Encryption, Lecture Notes in Computer Science (The 11th International Conference on Information Security and Cryptology: ICISC2008), Vol.5461, pp.1-19, 2008 [detail]

abstract

In this paper, we present a simple and generic method for constructing public key encryption (PKE) secure against chosen ciphertext attacks (CCA) from identity-based encryption (IBE). Specifically, we show that a CCA-secure PKE scheme can be generically obtained by encrypting (m||r) under identity ``f(r)'' with the encryption algorithm of the given IBE scheme, assuming that the IBE scheme is non-malleable and f is one-way. In contrast to the previous generic methods (such as Canetti-Halevi-Katz), our method requires stronger security for the underlying IBE schemes, non-malleability, and thus cannot be seen as a direct improvement of the previous methods. However, once we have an IBE scheme which is proved (or can be assumed) to be non-malleable, we will have a PKE scheme via our simple method, and we believe that the simpleness of our proposed transformation itself is theoretically interesting. Our proof technique for security of the proposed scheme is also novel. In the security proof, we show how to deal with certain types of decryption queries which cannot be handled by straightforwardly using conventional techniques.
• Takahiro Matsuda, Nuttapong Attrapadung, Goichiro Hanaoka, Kanta Matsuura, Hideki Imai. A Strongly Unforgeable Signature under the CDH Assumption without Collision Resistant Hash Functions, IEICE Transactions on Information and Systems, Vol.E91-D, No.5, pp.1466-1476, 2008 [detail]

abstract

Unforgeability of digital signatures is closely related to the security of hash functions since hashing messages, such as hash-and-sign paradigm, is necessary in order to sign (arbitrarily) long messages. Recent successful collision finding attacks against practical hash functions would indicate that constructing practical collision resistant hash functions is difficult to achieve. Thus, it is worth considering to relax the requirement of collision resistance for hash functions that is used to hash messages in signature schemes. Currently, the most efficient strongly unforgeable signature scheme in the standard model which is based on the CDH assumption (in bilinear groups) is the Boneh-Shen-Waters (BSW) signature proposed in 2006. In their scheme, however, a collision resistant hash function is necessary to prove its security. In this paper, we construct a signature scheme which has the same properties as the BSW scheme but does not rely on collision resistant hash functions. Instead, we use a target collision resistant hash function, which is a strictly weaker primitive than a collision resistant hash function. Our scheme is, in terms of the signature size and the computational cost, as efficient as the BSW scheme.
• 松田隆宏,　花岡悟一郎,　松浦幹太,　今井秀樹. 任意の頑強なIDベース暗号に基づくCCA安全な公開鍵暗号の効率的構成方法, 2008年暗号と情報セキュリティ・シンポジウム（SCIS2008）予稿集, CD-ROM, 2008 [detail]

abstract

本稿では、頑強性を持つIDベース暗号からCCA安全性を持つ公開鍵暗号の構成法を示す。 2005年に提案されたBonehとKatzによる方法(BK変換)では、 構成要素としてMACと特殊なコミットメント方式が必要であり、 暗号文サイズの変換によるオーバーヘッドが704ビット程度生じてしまう。 これに対し本稿で提案する方法では、IDベース暗号に従来の変換で用いられる識別不可能性よりも 強い頑強性を仮定することで、構成要素は、一方向性及びターゲット衝突困難性を同時に満たす 一つのハッシュ関数のみとでき、暗号文サイズのオーバーヘッドは256ビット程度である。 これまで、安全性の帰着をある種の暗号方式の頑強性に帰着させるような方式はあまり 提案されていないが、本稿での証明は、 新しい証明技法として、他の暗号技術の安全性をある種の暗号方式の頑強性へと 帰着する必要がある場合に有用な可能性がある。

links

• pdf
• Takahiro Matsuda, Nuttapong Attrapadung, Goichiro Hanaoka, Kanta Matsuura, Hideki Imai. A CDH-Based Strongly Unforgeable Signature Without Collision Resistant Hash Function, Lecture Notes in Computer Science (Provable Security-First International Conference: ProvSec 2007), Vol.4784, pp.68-84, 2007 [detail]

abstract

Unforgeability of digital signatures is closely related to the security of hash functions since hashing messages, such as hash-and-sign paradigm, is necessary in order to sign (arbitrarily) long messages. Recent successful collision finding attacks against practical hash functions would indicate that constructing practical collision resistant hash functions is difficult to achieve. Thus, it is worth considering to relax the requirement of collision resistance for hash functions that is used to hash messages in signature schemes. Currently, the most efficient strongly unforgeable signature scheme in the standard model which is based on the CDH assumption (in bilinear groups) is the Boneh-Shen-Waters (BSW) signature proposed in 2006. In their scheme, however, a collision resistant hash function is necessary to prove its security. In this paper, we construct a signature scheme which has the same properties as the BSW scheme but does not rely on collision resistant hash functions. Instead, we use a target collision resistant hash function, which is a strictly weaker primitive than a collision resistant hash function. Our scheme is, in terms of the signature size and the computational cost, as efficient as the BSW scheme.

links

• Link (SpringerLink)
• Takahiro Matsuda, Goichiro Hanaoka, Kanta Matsuura, Hideki Imai. A Practical Provider Authentication System for Bidirectional Broadcast Service, Lecture Notes in Computer Science (11th International Conference on Knowledge-Based and Intelligent Information & Engineering Systems:KES 2007), Vol.4694, pp.967-974, 2007 [detail]

abstract

Several content distribution services via the Internet have been developed, and a number of bidirectional broadcasting services will be provided in the near future. Since such bidirectional broadcasting treats personal information of the users, provider authentication is necessary. Taking the currently existing broadcasting system using CAS cards into account, Ohtake et al. recently proposed the provider authentication system which utilizes key-insulated signature (KIS) schemes. However, the authors did not refer to details of what kind of KIS should be used. In this paper we supplement their works in terms of KIS specification. We carefully identify what kind of KIS should be used and propose concrete KIS schemes which realize both the reliability and the robustness required for the bidirectional broadcasting service.

links

• Link (SpringerLink)
• 松田隆宏, アッタラパドゥン　ナッタポン, 花岡悟一郎, 松浦幹太, 今井秀樹. スタンダードモデルでのCDH仮定に基づく衝突困難ハッシュ関数を用いない強偽造不可能性を持つ署名方式, 2007年暗号と情報セキュリティシンポジウム（SCIS2007）予稿集, 2007 [detail]

abstract

電子署名において、 入力が任意長の衝突困難ハッシュ関数を用いて ハッシュ値に対し署名を付けるHash-and-Signパラダイムを用いる方式は、 ハッシュ関数の衝突困難性が破れると安全ではなくなってしまう。 また、実用の際は計算時間などを考慮し、 SHA-1などの標準ハッシュ関数を衝突困難であるとして利用することが多いが、 近年それらの標準ハッシュ関数に対する衝突発見攻撃の報告が相次いでおり、 実際には標準ハッシュ関数を使うとしても、 ハッシュ関数に必要な仮定を弱めることは重要なことである。 そこで衝突困難ハッシュ関数の代わりとして汎用一方向ハッシュ関数の利用を考える。 Hash-and-Signパラダイムに代わる一般的な方式は存在するが、 署名長が長くなるという問題がある。 また、任意長のメッセージの署名を可能にする用途以外には使えるかどうか分からない。 本稿では、2006年Bonehらによって提案された署名方式に変形を加え、 安全性の証明に必要とされる衝突困難ハッシュ関数を用いずに、 それより弱い仮定で実現できる汎用一方向ハッシュ関数を利用し、署名長を伸ばすことなく、 元の方式と同じCDH仮定で適応的選択文書攻撃に対し強存在的偽造不可能性を持つ方式を示した。

links

• pdf

千葉 大輝

• 修士課程

研究テーマ

• ネットワークセキュリティ, 暗号技術

Publications

• Daiki Chiba, Takahiro Matsuda, Jacob C.N. Schuldt, Kanta Matsuura. Efficient Generic Constructions of Signcryption with Insider Security in the Multi-user Setting, Lecture Notes in Computer Science (9th International Conference on Applied Cryptography and Network Security: ACNS 2011), Vol.6715, pp.220-237, 2011
• 千葉大輝, 松田隆宏, シュルツ・ヤコブ, 松浦幹太. 多人数モデルで内部者安全なSigncryptionの一般的構成法, 2011年暗号と情報セキュリティシンポジウム（SCIS2011）予稿集, CD-ROM, 2011 [detail]

abstract

公開鍵暗号と電子署名の機能を併せ持つSigncryptionの2種の安全性である秘匿性と偽造不可能性には 想定される攻撃者の種類によりそれぞれ\lq\lq 外部者'',\lq\lq 内部者''という分類がある. さらに, 公開鍵暗号や署名の場合とは異なり, 一人の送信者と一人の受信者からなる\lq\lq 2人モデル''での安全性は, 多人数でのモデルの安全性を包含しないため, 多人数モデルでの安全性を考えるのが望ましい. しかし, 我々の知る限り, 多人数を考慮した内部者に対する識別不可能性と\lq\lq 強''偽造不可能性を スタンダードモデルで達成する手法がこれまでに存在しなかった. そこで我々はそれらを達成する最初の手法として, Signcryptionの一般的構成法を2つ提案する. 1つ目の手法ではタグベースKEMを用い,2つ目の手法ではKEMを用いる. これらの手法により, 多人数モデルで内部者安全なSigncryptionを具体的に数多く構成できる.
• 千葉大輝，松田隆宏, 松浦幹太. タグベースKEMの選択的タグ安全性から適応的タグ安全性へのカメレオンハッシュを用いた強化手法とSigncryption への応用, 2010年暗号と情報セキュリティシンポジウム（SCIS2010）予稿集, CD-ROM, 2010 [detail]

abstract

タグベースKEM(TBKEM)とは,暗号化と復号アルゴリズムに補助入力として任意のタグを入力できるKEMである． TBKEMのCCA安全性は,攻撃者がタグを選ぶタイミングにより,選択的タグ版と適応的タグ版の二種類が考えられる． 本稿では,カメレオンハッシュを用いた選択的タグCCA安全な TBKEMを適応的タグCCA安全なTBKEMへの強化手法を提案する． 既に同目的を達成する自明な手法が存在するが,本手法は自明な手法と比べ変換後の暗号文サイズを小さくできる． また,最近\cite{MMS09}においてTBKEMのうち特殊な性質を持つものを構成要素の一つとするSigncryptionの構成法が提案されたが, 本手法では彼らのSigncryption方式でTBKEMに必要とされる性質が保存されることを示す． 従って本手法は Signcryptionの構成にも有用である．

北川 隆

• 特任研究員

研究テーマ

• 情報セキュリティ

Publications

• Peng Yang, Takashi Kitagawa, Goichiro Hanaoka, Rui Zhang, Hajime Watanabe, Kanta Matsuura, Hideki Imai. A new approach to evaluate Fujisaki-Okamoto conversions in identity based encryption, Proceeding of the 32th Symposium on Information Theory and Its Application (SITA’09), pp.e-proceeding, 2009
• 北川隆, 楊鵬, 花岡悟一郎, 張鋭, 松浦幹太, 今井秀樹. 藤崎・岡本変換とREACTのIDベース暗号への適用, 2006年暗号と情報セキュリティ・シンポジウム（SCIS2006）予稿集(CD-ROM), 2006

Jacob Schuldt

• 博士課程

研究テーマ

• Cryptography, Provable Security

Publications

• Jacob C.N. Schuldt, Kanta Matsuura. On-line Non-transferable Signatures Revisited, Lecture Notes in Computer Science (Public Key Cryptography - PKC 2011, 14th International Conference on Practice and Theory in Public Key Cryptography: PKC 2011), Vol.6571, pp.369-386, 2011 [detail]

abstract

Undeniable signatures, introduced by Chaum and van Antwerpen, and designated confirmer signatures, introduced by Chaum, allow a signer to control the verifiability of his signatures by requiring a verifier to interact with the signer to verify a signature. An important security requirement for these types of signature schemes is nontransferability which informally guarantees that even though a verifier has confirmed the validity of a signature by interacting with the signer, he cannot prove this knowledge to a third party. Recently Liskov and Micali pointed out that the commonly used notion of non-transferability only guarantees security against an off-line attacker which cannot influence the verifier while he interacts with the signer, and that almost all previous schemes relying on interactive protocols are vulnerable to online attacks. To address this, Liskov and Micali formalized on-line nontransferable signatures which are resistant to on-line attacks, and proposed a generic construction based on a standard signature scheme and an encryption scheme. In this paper, we revisit on-line non-transferable signatures. Firstly, we extend the security model of Liskov and Micali to cover not only the sign protocol, but also the confirm and disavow protocols executed by the confirmer. Our security model furthermore considers the use of multiple (potentially corrupted or malicious) confirmers, and guarantees security against attacks related to the use of signer specific confirmer keys. We then present a new approach to the construction of on-line non-transferable signatures, and propose a new concrete construction which is provably secure in the standard model. Unlike the construction by Liskov and Micali, our construction does not require the signer to issue ``fake'' signatures to maintain security, and allows the confirmer to both confirm and disavow signatures. Lastly, our construction provides noticeably shorter signatures than the construction by Liskov and Micali.

links

• pdf
• Jacob Schuldt, Kanta Matsuura. Efficient Convertible Undeniable Signatures with Delegatable Verification, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, Vol.94-A, No.1, pp.71-83, 2011
• Jacob Schuldt, Kanta Matsuura. On-line Non-transferable Signatures Revisited, 2011年暗号と情報セキュリティシンポジウム（SCIS2011）予稿集, CD-ROM, 2011
• Jacob C. N. Schuldt, Kanta Matsuura. An Efficient Convertible Undeniable Signature Scheme with Delegatable Verification, Lecture Notes in Computer Science (6th International Conference on Information Security Practice and Experience: ISPEC2010), Vol.6047, pp.276-293, 2010
• Jacob C.N. Schuldt, Kanta Matsuura. A Convertible Undeniable Signature Scheme with Delegatable Verification, 2010年暗号と情報セキュリティシンポジウム（SCIS2010）予稿集, CD-ROM, 2010
• Jacob C. N. Schuldt, Kanta Matsuura. On Identity-based Proxy Signatures and Hierarchical Signature Aggregation, 2009年暗号と情報セキュリティシンポジウム（SCIS2009）予稿集, CD-ROM, 2009
• Jacob C. N. Schuldt, Kanta Matsuura, Kenneth G. Paterson. Proxy Signatures Secure Against Proxy Key Exposure, Lecture Notes in Computer Science (11th International Workshop on Practice and Theory in Public Key Cryptography : PKC'08), Vol.4939, pp.141-161, 2008 [detail]

abstract

We provide an enhanced security model for proxy signatures that captures a more realistic set of attacks than previous models of Boldyreva et al. and of Malkin et al. Our model is motivated by concrete attacks on existing schemes in scenarios in which proxy signatures are likely to be used. We provide a generic construction for proxy signatures secure in our enhanced model using sequential aggregate signatures; our construction provides a benchmark by which future specific constructions may be judged. Finally, we consider the extension of our model and constructions to the identity-based setting.
• James Birkett, Alexander W. Dent, Gregory Neven, Jacob C. N. Schuldt. Efficient Chosen-Ciphertext Secure Identity-Based Encryption with Wildcards, Lecture Notes in Computer Science (12th Australasian Conference on Information Security and Provacy: ACISP 2007), Vol.4586, pp.274-292, 2007 [detail]

abstract

We propose new instantiations of chosen-ciphertext secure identity-based encryption schemes with wildcards (WIBE). Our schemes outperform all existing alternatives in terms of efficiency as well as security. We achieve these results by extending the hybrid encryption (KEM?DEM) framework to the case of WIBE schemes. We propose and prove secure one generic construction in the random oracle model, and one direct construction in the standard model.

施 屹

• 修士課程

研究テーマ

• 匿名通信, ネットワークセキュリティ

Publications

• 施屹, 松浦幹太. Extended Fingerprinting Attack on Tor with Time Characteristics and Defense Mechanism, 情報処理学会コンピュータセキュリティシンポジウム2010(CSS2010), Vol.2, pp.819-824, 2010 [detail]

abstract

By using interval classifications, we had proposed a novel way to implement a fingerprinting attack against Onion Routing anonymity systems such as Tor. Our motivation of previous work was to provide a realistic threat against existing popular anonymity systems. Through the simple threat model where an adversary could be mounted by nothing but controller of an entrance router, we had achieved our object. The attack we had proposed had a very good robustness against greatly-varied Internet conditions but the resolution is not so satisfactory to us. By employing time characteristics, we present an extended fingerprinting attack on anonymity systems here. Our new method has better performance, but still keeps the fingerprinting attack’s advantage of being realistic in terms of the required small resource. We give experimental evaluation by comparing the extended attack with our earlier work. Also, we discuss defense mechanisms against fingerprinting attacks.

links

• pdf
• 施屹, 松浦幹太. A Collusion Threat Model for Fingerprinting Attack on the Tor, 2010年暗号と情報セキュリティシンポジウム（SCIS2010）予稿集, CD-ROM, 2010 [detail]

abstract

Tor is a state-of-art low-latency anonymous communication system and provides TCP services for applications on the Internet. It involves several techniques to defend the attacks. We have presented a paper to introduce the fingerprinting attack on the Tor system. In this paper, we present a modified threat model towards the leaky pipe technique which Tor used, to achieve higher success rate. In this model, the malicious attacker could collude with a malicious onion router. If this onion router is not an exit router, we may still achieve higher success rate by fingerprinting attack. We also make some discussions towards the defending methods.
• 施屹, 松浦幹太. 匿名通信システムTorに対する指紋攻撃, 情報処理学会コンピュータセキュリティシンポジウム2009(CSS2009), 2009 [detail]

abstract

We present a novel way to implement a fingerprinting attack against Onion Routing anonymity systems such as Tor. Our attack is a realistic threat in the sense that it can be mounted by nothing but controller of entrance routers; the required resource is very small. However, the conventional fingerprinting attack based on incoming traffic does not work straightforwardly against Tor due to its multiplex and quantized nature of traffic. By contrast, our novel attack can degrade this Tor’s anonymity by a metric based on both incoming and outgoing packets. In addition, our method keeps the fingerprinting attack’s advantage of being realistic in terms of the required small resource. Regarding more evaluation, the effectiveness of our method is discussed in a comprehensive manner: experimentally and theoretically. In order to enhance further studies and show the significance of our idea, we also discuss methods for defending against our attack and other applications of our idea.
• Yi Shi, Kanta Matsuura. Fingerprinting Attack on the Tor Anonymity System, Lecture Notes in Computer Science (11th International Conference on Information and Communications Security: ICICS 2009), Vol.5927, pp.425-438, 2009 [detail]

abstract

We present a novel way to implement a fingerprinting attack against Onion Routing anonymity systems such as Tor. Our attack is a realistic threat in the sense that it can be mounted by nothing but controller of entrance routers; the required resource is very small. However, the conventional fingerprinting attack based on incoming traffic does not work straightforwardly against Tor due to its multiplex and quantized nature of traffic. By contrast, our novel attack can degrade this Tor's anonymity by a metric based on both incoming and outgoing packets. In addition, our method keeps the fingerprinting attack's advantage of being realistic in terms of the required small resource. Regarding more evaluation, the effectiveness of our method is discussed in a comprehensive manner: experimentally and theoretically. In order to enhance further studies and show the significance of our idea, we also discuss methods for defending against our attack and other applications of our idea.

付 紹静

• 訪問学生

研究テーマ

• コーディング, 共通鍵暗号

Publications

• Shaojing Fu, Kanta Matsuura, Chao Li, Longjiang Qu. Construction of highly nonlinear resilient S-boxes with given degree, Designs, Codes and Cryptography, Vol.64, No.3, pp.241-253, 2012 [detail]

abstract

We provide two new construction methods for nonlinear resilient S-boxes with given degree. The first method is based on the use of linear error correcting codes together with highly nonlinear S-boxes. Given a [u,m, t+1] linear code where u = n-d-1, d > m, we showthat it is possible to construct (n,m, t, d) resilient S-boxes which have currently best known nonlinearity. Our second construction provides highly nonlinear (n,m, t, d) resilient S-boxes which do not have linear structure, then an improved version of this construction is given.

keywords

Cryptography, Linear code, Resiliency, Linear structure, Nonlinearity
• Shaojing Fu, Chao Li, Kanta Matsuura, Longjiang Qu. Construction of Even- variable Rotation Symmetric Boolean Functions with Maximum Algebraic Immunity, SCIENCE CHINA Information Sciences, Vol.56, No.3, pp.1-9, 2013 [detail]

abstract

Rotation symmetric Boolean functions (RSBFs) have been used as components of different cryptosystems. In this paper, we investigate n-variable (n even and n >= 12) RSBFs to achieve maximum algebraic immunity (AI), and provide a construction of RSBFs with maximum AI and nonlinearity. These functions have higher nonlinearity than the previously known nonlinearity of RSBFs with maximum AI. We also prove that our construction provides high algebraic degree in some case.

keywords

Boolean function, rotation symmetry, algebraic immunity, nonlinearity
• Shaojing Fu, Chao Li, Kanta Matsuura, Longjiang Qu. Blanced 2p-variable Rotation Symmetric Boolean Functions with Maximum Algebraic Immunity, Applied mathematical Letters, Vol.24, No.12, pp.2093-2096, 2011 [detail]

abstract

In this paper, we study the construction of Rotation Symmetric Boolean Functions (RSBFs) which achieve a maximum algebraic immunity (AI). For the first time, a construction of balanced 2p-variable (p is an odd prime) RSBFs with maximum AI was provided, and the nonlinearity of the constructed RSBFs is not less than 2^(2p-1)-(2p-1)C(p)+(p-2)(p-3)+2; this nonlinearity result is significantly higher than the previously best known nonlinearity of RSBFs with maximum AI.

keywords

Stream cipher, Rotation symmetry, Boolean function, Algebraic immunity
• Shaojing Fu, Chao Li, Kanta Matsuura, Longjiang Qu.. Construction of Odd- variable Resilient Boolean Functions with Optimal Degree, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, Vol.VE94-A, pp.265-267, 2011 [detail]

abstract

Constructing degree-optimized resilient Boolean functions with high nonlinearity is a significant study area in Boolean function. In this letter, we provide a construction of degree-optimized n-variable (n odd and n>=35) resilient Boolean functions, and it is shown that the resultant functions achieve the currently best known nonlinearity.

keywords

stream cipher, boolean function, resiliency, nonlinearity
• Shaojing Fu, Chao Li, Kanta Matsuura, Longjiang Qu. Enumeration of Balanced Symmetric Functions over GF(p), Information Processing Letters, Vol.110, pp.544-548, 2010
• Shaojing Fu, Kanta Matsuura, Chao Li. Construction of High Nonlinearity Resilient S-Boxes with Given Degree, 2010年暗号と情報セキュリティシンポジウム（SCIS2010）予稿集, CD-ROM, 2010
• Shaojing Fu, Kanta Matsuura, Chao Li, Longjiang Qu. Construction of Rotation Symmetric Boolean Functions with Maximum Algebraic Immunity, Lecture Notes in Computer Science (The 8th International Conference on Cryptology and Network Security: CANS 2009), Vol.5888, pp.402-412, 2009

楊 鵬

• 博士課程

研究テーマ

• 情報セキュリティ, 高機能暗号方式, 安全性定義.

Publications

• 松浦幹太, 楊鵬. セキュリティ投資モデルとTrust-but-verifyアプローチによるモジュール選択, 情報処理学会コンピュータセキュリティ研究会（情報処理学会研究報告）, Vol.2010, No.50, 2010 [detail]

abstract

情報セキュリティ経済学では，理論研究の進展は著しいが，問題分析以外の応用があまりなされて いない． 本研究では，最適投資理論を応用して，製品認証を受けた情報セキュリティモジュールのユーザ （モジュールを用いてシステムを開発するベンダ）向けガイドラインを試作した． 経験的選択を信頼してモ ジュール選択を重ねてから投資理論で検証することにより PDCA サイクルを構成し，理論と実践を融合し た点に，特徴がある．

links

• pdf
• 楊鵬, 松浦幹太. JCMVPに関するユーザ向けガイドライン試作, 第72回情報処理学会全国大会, 2010
• Peng Yang, Kanta Matsuura. An Introduction of A Users' Guideline to Japan Cryptographic Module Validation Program, ASIACCS 2010 (5th ACM Symposium on Information, Computer and Communications Security), 2010
• Peng Yang, Takashi Kitagawa, Goichiro Hanaoka, Rui Zhang, Hajime Watanabe, Kanta Matsuura, Hideki Imai. A new approach to evaluate Fujisaki-Okamoto conversions in identity based encryption, Proceeding of the 32th Symposium on Information Theory and Its Application (SITA’09), pp.e-proceeding, 2009
• Peng Yang, Rui Zhang, Kanta Matsuura, Hideki Imai. Stateful Key Encapsulation Mechanism, 情報処理学会コンピュータセキュリティ研究会, Vol.2009-CSEC-046, No.43, pp.e-proceeding, 2009
• Peng Yang, Rui Zhang, Kanta Matsuura, Hideki Imai. Generic Construction of Stateful Identity Based Encryption, Lecture Notes in Computer Science (Information Security, 12th International Conference: ISC2009), Vol.5735, pp.338-346, 2009
• Peng Yang, Rui Zhang, Kanta Matsuura, Hideki Imai. Generic Construction of Stateful Identity Based Encryption, 2009年暗号と情報セキュリティシンポジウム（SCIS2009）予稿集, CD-ROM, 2009
• 楊　鵬,　松浦幹太. A Forward Secure Identity Based Encryption Scheme with Master Key Update, The 31st Symposium on Information Theory and its Applications (SITA2008), CD-ROM, 2008 [detail]

abstract

We propose an identity based encryption scheme with forward security. Especially in our scheme, the top secret, called the master key, evolves through time. Our scheme is provably secure in the sense of FS-IND-ID-CPA based on DBDH assumption in standard model.

keywords

Foward Security, identity based encryption, master key update.
• Peng Yang, Kanta Matsuura. A Forward Secure Identity Based Encryption Scheme with Master Key Update, Proceedings of 2008 International Symposium on Information Theory and its Applications (ISITA2008), CD-ROM, 2008 [detail]

abstract

We propose an identity based encryption scheme with forward security. Especially in our scheme, the top secret, called the master key, evolves through time. Our scheme is provably secure in the sense of FS-IND-ID-CPA based on DBDH assumption in standard model.

keywords

Foward Security, identity based encryption, master key update.
• Peng Yang, Kanta Matsuura. Stateful Public Key Encryption: How to Remove Gap Assumptions and Maintaining Tight Reductions, Proceedings of 2008 International Symposium on Information Theory and its Applications (ISITA2008), CD-ROM, 2008 [detail]

abstract

Stateful public key encryption schemes are introduced recently with much efficiency improvement over traditional stateless schemes. However, previous proposals are either based on strong assumptions, or admitting loose security reductions (a barrier for the proofs being practically-meaningful). In this paper, we present a stateful public key encryption scheme with tight security reduction to the computational Diffie Hellman assumption (cf. gap Diffie-Hellman), as well as a stateful identity based encryption scheme with tighter security reduction to the computational bilinear Diffie-Hellman problem.

keywords

Stateful public key encryption, security reduction.
• Peng Yang, Goichiro Hanaoka, Yang Cui, Rui Zhang, Nuttapong Attrapadung, Kanta Matsuura, Hideki Imai. Relations among Notions of Security for Identity Based Encryption Schemes, 情報処理学会論文誌, Vol.47, No.8, pp.2417-2429, 2006 [detail]

abstract

Identity based encryption (IBE) schemes have been flourishing since the very beginning of this century. In IBE it is widely believed that proving the security of a scheme in the sense of IND-ID-CCA2 is sufficient to claim the scheme is also secure in the senses of both SS-ID-CCA2 and NM-ID-CCA2. The justification for this belief is the relations among indistinguishability (IND), semantic security (SS) and non-malleability (NM). But these relations are proved only for conventional public key encryption (PKE) schemes in previous works. The fact is that between IBE and PKE, there exists a difference of special importance, i.e. only in IBE the adversaries can perform a particular attack, namely the chosen identity attack. This paper shows that security proved in the sense of IND-ID-CCA2 is validly sufficient for implying security in any other sense in IBE. This is to say the security notion, IND-ID-CCA2, captures the essence of security for all IBE schemes. To achieve this intention, we first describe formal definitions of the notions of security for IBE, and then present the relations among IND, SS and NM in IBE, along with rigorous proofs. All of these results are proposed with the consideration of the chosen identity attack.

keywords

Identity based encryption, security notions.
• Takashi Kitagawa, Peng Yang, Goichro Hanaoka, Rui Zhang, Hajime Watanabe, Kanta Matsuura, Hideki Imai. Generic Transforms to Acquire CCA-Security for Identity Based Encryptions: The Cases of FOpkc and REACT, Lecture Notes in Computer Science (11th Australasian Conference on Information Security and Provacy: ACISP 2006), Vol.4058, pp.348-359, 2006 [detail]

abstract

Fujisaki-Okamoto (FOpkc) conversion [13] and REACT[17] are widely known to be able to generically convert a weak public key encryption scheme to a strong encryption scheme. In this paper, we discuss applications of FOpkc conversion and REACT to Identity Based Encryptions (IBE). It has not been formally verified yet that whether these conversions are generic in the IBE setting. Our results show that both conversions are effective in the IBE case: plain REACT already achieves a good security reduction while the plain FOpkc conversion results in bad running time of the simulator. We further propose a simple modification to the plain FOpkc that solves this problem. Finally, we choose some concrete parameters to explain (visually) the effect of how the modified FOpkc substantially improves reduction cost regarding the plain conversion.

keywords

Fujisaki-Okamoto, identity based encryption, security enhancement.
• Nuttapong Attrapadung, Yang Cui, David Galindo, Goichiro Hanaoka, Ichiro Hasuo, Hideki Imai, Kanta Matsuura, Peng Yang, Rui Zhang. Relations among Notions of Security for Identity Based Encryption Schemes, Lecture Notes in Computer Science (LATIN 2006: Theoretical Informatics: 7th Latin American Symposium), Vol.3887, pp.130-141, 2006 [detail]

abstract

This paper shows that the standard security notion for iden- tity based encryption schemes (IBE), that is IND-ID-CCA2, captures the essence of security for all IBE schemes. To achieve this intention, we first describe formal definitions of the notions of security for IBE, and then present the relations among OW, IND, SS and NM in IBE, along with rigorous proofs. With the aim of comprehensiveness, notions of security for IBE in the context of encryption of multiple messages and/or to mul- tiple receivers are finally presented. All of these results are proposed with the consideration of the particular attack in IBE, namely the adaptive chosen identity attack.

keywords

Identity based encryption, security notions.
• Peng Yang, Takashi Kitagawa, Goichiro Hanaoka, Rui Zhang, Kanta Matsuura, Hideki Imai. Applying Fujisaki-Okamoto to Identity-Based Encryption, Lecture Notes in Computer Science (Applied Algebra, Algebraic Algorithms and Error-Correcting Codes: 16th International Symposium: AAECC-16), Vol.3857, pp.183-192, 2006 [detail]

abstract

The Fujisaki-Okamoto (FO) conversion is widely known to be able to generically convert a weak public key encryption scheme, say one-way against chosen plaintext attacks (OW-CPA), to a strong one, namely, indistinguishable against adaptive chosen ciphertext attacks (IND-CCA). It is not known that if the same holds for identity-based encryption (IBE) schemes, though many IBE and variant schemes are in fact specifically using the FO conversion. In this paper, we investigate this issue and confirm that the FO conversion is generically effective also in the IBE case. However, straightforward application of the FO conversion only leads to an IBE scheme with a loose (but polynomial) reduction. We then propose a simple modification to the FO conversion, which results in considerably more efficient security reduction.

keywords

Fujisaki-Okamoto, identity based encryption, security enhancement.
• Peng Yang, Takashi Kitagawa, Goichiro Hanaoka, Rui Zhang, Hajime Watanabe, Kanta Matsuura, Hideki Imai. A Simple Approach to Evaluate Fujisaki-Okamoto Conversion in Identity Based Encryption, Proceedings of the 2006 International Symposium on Information Theory and Its Applications (ISITA'06), pp.507-512, 2006 [detail]

abstract

The Fujisaki-Okamoto (FO) conversion is a very powerful security enhancement method in public key encryption (PKE) schemes. The generality of the plain FO in identity based encryption (IBE) schemes was verified, and a slightly different version, the modified FO, was proposed. Both of the plain FO and the modified FO could achieve the goal of converting a weak IBE scheme, i.e., one-way against adaptive chosen identity and chosen plaintext attacks ({\sf OW-ID-CPA}), to the strongest one, namely, indistinguishability against adaptive chosen identity and adaptive chosen ciphertext attacks (\textsf{IND-ID-CCA}). This work aims to evaluate the plain FO and the modified FO by substituting proper concrete values. By mainly focusing on the time costs of security reductions, we show the modified FO is better than the plain one.

keywords

Fujisaki-Okamoto, identity based encryption, security enhancement.

中井 泰雅

• 修士課程

研究テーマ

• 暗号技術, コンピューターセキュリティ

Publications

• 小林鉄太郎, 中井泰雅. タイムリリース暗号における鍵発行サーバについて, 第11回ペアリングフォーラム, 2010
• 小林鉄太郎, 中井泰雅. 汎用IBEに基づくタイムリリース暗号の実装と評価, 第11回ペアリングフォーラム, 2010
• 中井泰雅、松田隆宏、松浦幹太. 時間前復号機能付き時限式暗号の効率的な一般的構成法, 2010年暗号と情報セキュリティシンポジウム（SCIS2010）予稿集, CD-ROM, 2010 [detail]

abstract

あらまし時間前開封機能付き時限式暗号(Timed-Release Encryption with Pre-open Capability, TREPC) とは，送信者の指定した時刻になるか，もしくは時間前開封鍵を受信者に送信するまで復号するこ とのできない暗号文を作る手法である． [12] において，我々は公開鍵暗号(PKE)，ID ベース暗号(IBE)， およびOneTime 署名から成るTRE-PC の一般的構成法を示した． しかし，この構成法は暗号文サイズ が大きく，十分実用的であるとは言いづらい． そこで本論文では，タグベース暗号(TB)-KEM, IB-KEM, およびEncapsulation, MAC を用いたTRE-PC の一般的構成法，およびPK-KEM, IB-KEM を用いた ランダムオラクルモデルで安全なTRE-PC KEM の構成法を提案し，[12] との比較を行う．
• 小林鉄太郎, 中井泰雅. タイムリリース暗号システムの設計と実装, 第10回ペアリングフォーラム, 2009
• Yasumasa Nakai, Takahiro Matsuda, Wataru Kitada, Kanta Matsuura. A Generic Construction of Timed-Release Encryption with Pre-open Capability, Lecture Notes in Computer Science (Advances in Information and Computer Security, The 4th International Workshop on Security: IWSEC2009), Vol.5824, pp.53-70, 2009 [detail]

abstract

In 2005, Hwang et al. proposed a concept of timed-release encryption with pre-open capability (TRE-PC), where a receiver can decrypt a ciphertext not only by using a time-release key which is provided after its release-time, but also using a secret information called a preopen key provided from a sender even before the release-time. Though there are several concrete constructions of TRE-PC proposed so far, no generic construction has been known. In this paper, we show a generic construciton of TRE-PC. Specifically, we construct a TRE-PC scheme from a chosen-ciphertext secure public key encryption scheme (PKE), a chosen plaintext secure identity-based encryption (IBE) scheme with specific property that we call target collision resistance for randomness, and a one-time signature scheme. Interestingly, our proposed construction of TRE-PC is essentially the same as the generic construciton of (normal) TRE based on multiple encryption of IBE and PKE. As one of the consequences of our result, we can build a TRE-PC scheme secure in the standard model based on weaker assumptions than the ones used by the existing standard model TRE-PC scheme.
• 中井泰雅, 松田隆宏, 北田亘, 松浦幹太. 時間前開封機能付き時限式暗号の一般的構成法, 2009年暗号と情報セキュリティシンポジウム（SCIS2009）予稿集, CD-ROM, 2009 [detail]

abstract

あらまし時間前開封機能付き時限式暗号(Timed-Release Encryption with Pre-open Capability, TREPC) とは，送信者の指定した時刻になるか，もしくは時間前開封鍵を受信者に送信するまで復号するこ とのできない暗号文を作る手法である． 本論文では，TRE-PC の一般的構成法を示し，また，その安全 性についての証明を行う． 具体的には，提案手法は，公開鍵暗号，ID ベース暗号，およびOneTime 署 名から成る． 興味深いことに，時間前開封機能のない通常のTRE の公開鍵暗号，ID ベース暗号の多重 暗号化法による時限式暗号の一般的構成法と本質的には変わらないため，特別なコストをかけることの なく一般的構成を行うことができる． また，本稿の構成手法のアイデアを既存の具体的な数論的問題の 困難性に基づく(時間前開封機能のない)TRE に適応することで，新たなTRE-PC を容易に実現するこ とが可能になることも期待される．

橋詰 直子

• 秘書

研究テーマ

渡邉 悠

• 修士課程

研究テーマ

• コンピュータセキュリティ, 脆弱性対策, 並列分散コンピューティング

Publications

• 渡邉悠, 松浦幹太. ホワイトリストコーディングによるSQLインジェクション攻撃耐性保証方法と実装, 情報処理学会論文誌, Vol.50, No.9, pp.2048-2061, 2009
• 渡邉悠, 松浦幹太. ホワイトリストコーディングによるSQLインジェクション攻撃耐性保証方法と実装, 2009年暗号と情報セキュリティシンポジウム（SCIS2009）予稿集, CD-ROM, 2009
• 渡邉悠, 松浦幹太. SQLインジェクション攻撃を防止するためのプログラミング方法とデータベース拡張, Computer Security Symposium2008 (CSS2008), 2008
• 渡邉悠, 松浦幹太. インジェクション系脆弱性を持つコードの記述が不可能なフレームワーク, 2008年暗号と情報セキュリティ・シンポジウム（SCIS2008）予稿集, CD-ROM, 2008 [detail]

abstract

Web アプリケーションの利用が拡大している昨今、Web アプリケーションの脆弱性の大き な割合を占めるインジェクション系の脆弱性に対する対策技術は非常に重要である。 しかし既存の研究 は、攻撃もしくは脆弱性の検知を行いシステムのセキュリティを保とうとするものが多く、それゆえ誤検 知や検知漏れが発生するという問題抱えている。 本論文では、攻撃や脆弱性を検出するのではなく、プ ログラマに対して安全なコードを記述することを強制することによってシステムの安全性を保つアーキ テクチャの考案した。 また、この考えを取り入れたSQL インジェクション対策用フレームワークを設計 し、実装を行った。

keywords

脆弱性対策, Web セキュリティ, インジェクション攻撃, SQL インジェクション攻撃, クロスサイトスクリプティング

links

• pdf (Japanese)
• presentation (Japanese)
• 渡邉悠, 松浦幹太. SQLの条件節が動的に構成されることを考慮したデータベース接続APIの設計, コンピュータセキュリティシンポジウム(CSS2007), pp.571-576, 2007 [detail]

abstract

ある言語の中で文字列処理によって他の言語をユーザの入力から構築することがインジェクショ ン攻撃に対する脆弱性が生じる原因の本質であるため、文字列操作による言語の構築はできるかぎり避け なくてはならない。 本研究では、既存の手法では文字列操作なしに取り扱うのが難しい“実行時に有無が決 定される条件” と“条件の繰り返し” を含むSQL を文字列操作を用いずに効率的かつ安全に構築することが 可能なデータベース接続API の拡張について考察を行った。

links

• ppt (Japanese)

北田 亘

• 修士課程

研究テーマ

• 暗号学

Publications

• 北田亘,　松浦幹太. フォワードセキュア属性ベース暗号に関する一考察, The 31st Symposium on Information Theory and its Applications (SITA2008), CD-ROM, 2008
• 北田亘,　松浦幹太. ブラインド属性ベース暗号 , 2008年暗号と情報セキュリティ・シンポジウム（SCIS2008）予稿集, CD-ROM, 2008 [detail]

abstract

公開鍵暗号における鍵のすり替えの問題を解決する方法として， エンティティの識別子等を利用するという方法がある． しかし，これらの方式を用いる場合，受信者は鍵生成に必要な情報を鍵生成センターに送り， それに対応する秘密鍵を要求しなければならない． この際，鍵生成センターは，受信者の鍵に関する情報を得ることができるという問題が生じる． 本研究では，この問題を解消するために，属性ベース暗号を基にし， 受信者の鍵情報のすべてをセンターに知らせることなく，鍵導出が可能な暗号方式を提案する．
• 北田亘,　松浦幹太. 柔軟な識別子評価可能な暗号化方式, 第30回情報理論とその応用シンポジウム(SITA2007), 2007 [detail]

abstract

In identity based encryption (IBE), each entity has one identity to specify one entity. In IBE, a sender picks an identity of one entity which he wants to send to and a receiver has one entity which specifies himself. IBE works if the two identities are evaluated to be equal. In this paper, we show an encryption scheme that allows not only equal relation but more general relations. In particular, our scheme allows any bitwise operations which can be expressed in combinational circuit when we evaluate labels, generalized notions of identities.
• Wataru Kitada, Goichiro Hanaoka, Kanta Matsuura, Hideki Imai. Unconditionally Secure Chaffing-and-Winnowing for Multiple Use, Lecture Notes in Computer Science (International Conference on Information Theoretic Security: ICITS 2007), Vol.4883, pp.133-145, 2007 [detail]

abstract

Chaffing-and-winnowing is a cryptographic technique which does not require encryption but instead use a message authentication code (MAC) to provide the same function as encryption. Hanaoka et al. showed that an unconditionally secure chaffing-and-winnowing with one-time security can be constructed from any authentication code (A-code) (with one-time security). In this paper, we show a construction of unconditionally secure chaffing-and-winnowing for multiple use and prove the security of perfect secrecy and non-malleability. Additionally, we investigate a relation between encryption and authentication in more detail. Particularly, we show through chaffing-and-winnowing that a fully secure A-code with a specific property can be converted to a non-malleable one-time pad with a short ciphertext size. Interestingly, when applying this method to a known A-code, this becomes a known construction of a non-malleable one-time pad. This fact implies that the notions of authentication and encryption can be seamlessly connected by chaffing-and-winnowing mechanism.
• 北田亘、Nuttapong Attrapadung、花岡悟一郎、松浦幹太、今井秀樹. IBE-PKE変換の広がりの限界への更なる考察, 2007年暗号と情報セキュリティシンポジウム（SCIS2007）予稿集, 2007 [detail]

abstract

2004年に，Canetti, Halevi, Katzによって，IDベース暗号方式から，適応的選択暗号文攻撃に耐え得る公開鍵暗号方式への一般的な変換方法が提案された． しかし，2006年にKiltzは，この変換方法は，異なるIDベース暗号方式から同じ公開鍵暗号方式が得られる可能性があることを示唆した． 具体的には，ある２つのIDベース暗号方式に対し，この変換を適用し，簡素化を行った結果が，非常に似ていたのである． そこで，今回我々は，Kiltzと同様に変換，簡素化を行った結果，全く同じ結果が得られるような１組のIDベース暗号方式を示す． このことにより，この変換方式の単射性への反例を示すことができるようになる．
• 北田亘, 花岡悟一郎, Nuttapong Attrapadung, 張鋭, 松浦幹太, 今井秀樹. BDDH仮定とSquare BDDH仮定の関係の考察, 第29回情報理論とその応用シンポジウム (SITA2006) 予稿集, Vol.Ⅰ, pp.299-302, 2006 [detail]

abstract

At Eurocrypt'04, Canetti, Halevi, and Katz (CHK) proposed a generic transformation that converts any selectively secure identity-based encryption (IBE) scheme to a chosen-ciphertext secure public-key encryption scheme (PKE) scheme. At PKC'06, Kiltz showed the limitation of this transformation. He showed that when applying the CHK conversion (together with some equivalent simplification) to two different IBE schemes both proposed by Boneh and Boyen, the resulting schemes are nearly the same in their structures, not two completely different PKE as expected. Nevertheless, the two PKE schemes are different in their underlying assumptions. One is based on Bilinear Decision Diffie-Hellman (BDDH) assumption, while the other is based on Square Bilinear Decision Diffie-Hellman (sBDDH) assumption. To emphasize the limitation in a stronger sense, it is desirable to show the similarity of not only their structures, but also their underlying assumptions. We argues that the BDDH and the sBDDH assumptions are related in essential way by showing the equivalence of their computational versions.

Vadim Jefte Zendejas Samano

• 修士課程

研究テーマ

• Mail Security

Publications

• Vadim Jefte Zendejas Samano, Takuro Hosoi, Kanta Matsuura. Time Categorization in a Social-Network-Analysis Spam Filter, Workshop on Information Security Applications (WISA2008), CD-ROM, 2008 [detail]

abstract

In this article, the introduction of a new method of language- independent e-mail classification using Social Network Analysis (SNA) for spam filtering is proposed. Our approach uses a time categorization of different instances of the e-mail to improve the classification of the filter. The proposal reduced the complexity of the classification and increases the accuracy of the filter. Although the naive SNA suffers from a high unclassification rate, our proposal decreases the number of unclassified e-mails.
• Vadim Jefte Zendejas Samano, Kanta Matsuura. Social Network Analysis Spam Filtering using Time Categorization, 2008年暗号と情報セキュリティ・シンポジウム（SCIS2008）予稿集, CD-ROM, 2008
• Vadim Jefte Zendejas Samano, Kanta Matsuura. Using time to classify spam, 第39回情報処理学会コンピュータセキュリティ研究会（情報処理学会研究報告）, Vol.2007, No.126, pp.19-24, 2007

Phan Thi Lan Anh

• 修士課程

研究テーマ

• Cryptography

Publications

• Thi Lan Anh Phan, Goichiro Hanaoka, Kanta Matsuura, Hideki Imai. Key-Insulated Public Key Encryption with Auxiliary Helper Key: Model, Construcrtions and Formal Security Proofs, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, Vol.E90-A, No.9, pp.1814-1829, 2007 [detail]

abstract

To deal with the problem of secret key exposure, Dodis, Katz, Xu and Yung [6] proposed a key-insulated public key encryption (KIE), which uses the secure helper key to update the secret key more often and helps to minimize the damage overall. We take this idea further in improving the helper key security by introducing an auxiliary helper key besides of the main helper key. The auxiliary helper key is used less than the main helper key and can help the system to reduce the damage even in case of helper key exposure. This paper give two different schemes of KIE with auxiliary helper key. There are trade-offs between public key length and ciphertext size, as well as between encryption algorithms and decryption algorithms in these two schemes. With these trade-offs, it is flexible to choose an efficient one to implement in reality. We also show concrete constructions with chosen-ciphertext security. The formal security proofs for all schemes are given in this paper, based on the CBDH assumption [2] in the random oracle model.
• Thi Lan Anh Phan, Goichiro Hanaoka, Kanta Matsuura, Hideki Imai. Formal Security Proofs of Key-Insulated Public Key Encryption with Auxiliary Helper Key, Proceedings of The 2007 Symposium on Cryptography and Information Security (SCIS2007), 2007
• Thi Lan Anh Phan, Goichiro Hanaoka, Kanta Matsuura, Hideki Imai. A New Key-Insulated Public Key Encryption Scheme with Auxiliary Helper Key, Proceeding of the 29th Symposium on Information Theory and Its Application (SITA’06), Vol.Ⅱ, pp.477-480, 2006
• Thi Lan Anh Phan, Yumiko Hanaoka, Goichiro Hanaoka, Kanta Matsuura, Hideki Imai. Reducing the Spread of Damage of Key Exposure in Key Insulated Encryption, Lecture Notes in Computer Science (First International Conference on Cryptology in Vietnam: VietCrypt 2006), Vol.4341, pp.366-384, 2006 [detail]

abstract

A proposal for key exposure resilient cryptography called, key-insulated public key encryption (KIPE), has been proposed by Dodis, Katz, Xu, and Yung [6] in which the secret key is changed over time so that the exposure of current key minimizes the damage overall. We take this idea further toward betterment by introducing new schemes with improved helper key security: in our schemes, we introduce an auxiliary helper key to update the secret key less frequently than the main helper key (and only one of these keys is used at each key updates,) as a result, this gives added protection to the system, by occasional auxiliary key updates, reducing the spread of further harm that may be caused by key exposure when compared to the original KIPE. Our proposed schemes are proven to be semantically secure in the random oracle model.