研究者詳細 - 伊東　利哉

2026/04/28 更新

写真a

イトウ　トシヤ

伊東　利哉

ITO TOSHIYA

所属

戦略本部特命教授

外部リンク

研究分野

情報通信 / 情報学基礎論 / 離散アルゴリズム
情報通信 / 情報学基礎論 / オンラインアルゴリズム
情報通信 / 計算科学 / 確率的手法
情報通信 / 計算科学 / 線形代数法

学歴

東京工業大学工学博士

1988年12月

　詳細を見る

researchmap
東京工業大学大学院理工学研究科電気・電子工学専攻

1982年4月 - 1984年3月

　詳細を見る

researchmap
東京工業大学工学部電気・電子工学科

1978年4月 - 1982年3月

　詳細を見る

researchmap

経歴

東京科学大学情報理工学院教授

2024年10月 - 現在

　詳細を見る

researchmap
東京工業大学副学長(情報基盤担当)

2019年4月 - 現在

　詳細を見る

researchmap
東京工業大学数理・計算科学系教授

2016年4月 - 現在

　詳細を見る

researchmap
東京工業大学学術国際情報センター教授

2001年4月 - 2016年3月

　詳細を見る

researchmap
東京工業大学物理情報工学専攻助教授

1992年4月 - 2001年3月

　詳細を見る

researchmap
東京工業大学物理情報工学専攻講師

1990年3月 - 1992年3月

　詳細を見る

researchmap
東京工業大学電気電子工学科助手

1985年12月 - 1990年2月

　詳細を見る

researchmap

▼全件表示

論文

A Nearly Optimal Deterministic Algorithm for Online Transportation Problem 査読

Tsubasa Harada, Toshiya Itoh

International Colloquium on Automata, Languages, and Programming (ICALP) 2025年6月

　詳細を見る

記述言語：英語掲載種別：研究論文（国際会議プロシーディングス）

DOI： 10.4230/LIPIcs.ICALP.2025.94

researchmap
Popularity on the 3D-Euclidean Stable Roommates 査読

Steven Ge, Toshiya Itoh

Lecture Notes in Computer Science 196 - 214 2025年2月

　詳細を見る

記述言語：英語掲載種別：研究論文（国際会議プロシーディングス）出版者・発行元：Springer Nature Singapore

DOI： 10.1007/978-981-96-2845-2_13

researchmap
Popularity on the roommate diversity problem 査読

Steven Ge, Toshiya Itoh

Theoretical Computer Science 1023 114903 - 114903 2025年1月

　詳細を見る

記述言語：英語掲載種別：研究論文（学術雑誌）出版者・発行元：Elsevier BV

DOI： 10.1016/j.tcs.2024.114903

researchmap
Capacity-insensitive algorithms for online facility assignment problems on a line 査読

Tsubasa Harada, Toshiya Itoh, Shuichi Miyazaki

Discrete Mathematics, Algorithms and Applications 16 ( 05 ) 2350057-1 - 2350057-39 2024年5月

　詳細を見る

記述言語：英語掲載種別：研究論文（学術雑誌）出版者・発行元：World Scientific Pub Co Pte Ltd

In the online facility assignment problem [Formula: see text], there exist [Formula: see text] servers [Formula: see text] on a metric space where each [Formula: see text] has an integer capacity [Formula: see text] and a request arrives one-by-one. The task of an online algorithm is to irrevocably match a current request with one of the servers with vacancies before the next request arrives. As special cases for [Formula: see text], we consider [Formula: see text] on a line , which is denoted by [Formula: see text] and [Formula: see text], where the latter is the case of [Formula: see text] with equidistant servers. In this paper, we perform the competitive analysis for the above problems. As a natural generalization of the greedy algorithm grdy, we introduce a class of algorithms called MPFS (Most Preferred Free Servers) and show that any MPFS algorithm has the capacity-insensitive property, i.e., for any MPFS algorithm alg for [Formula: see text], if alg is [Formula: see text]-competitive when [Formula: see text], then alg is [Formula: see text]-competitive for general [Formula: see text]. By applying the capacity-insensitive property of the greedy algorithm grdy, we derive the matching upper and lower bounds [Formula: see text] on the competitive ratio of grdy for [Formula: see text]. To investigate the capability of MPFS algorithms, we show that the competitive ratio of any MPFS algorithm alg for [Formula: see text] is at least [Formula: see text]. Then, we propose a new MPFS algorithm idas (Interior Division for Adjacent Servers) for [Formula: see text] and show that the competitive ratio of idas for [Formula: see text] is at most [Formula: see text], i.e., idas for [Formula: see text] is best possible in all the MPFS algorithms. We also give numerical experiments to investigate the performance of idas and grdy and show that idas performs better than grdy for distribution of request sequences with locality.

DOI： 10.1142/s179383092350057x

researchmap
Mechanism Design for Mobility

Tsubasa Harada, Toshiya Itoh, Shigeo Matsubara, Shuichi Miyazaki, Makoto Yokoo

Advanced Mathematical Science for Mobility Society 187 - 215 2024年3月

　詳細を見る

掲載種別：論文集(書籍)内論文出版者・発行元：Springer Nature Singapore

Abstract

This chapter presents the development of matching theory toward implementing the next-generation car-sharing systems, consisting of three topics: (1) online facility assignment problems on a line, (2) two-sided matching with flexible quotas: student-project-resource matching-allocation problem, and (3) formalizing station-based one-way car sharing as three-sided matching. The first two relate to developments in basic research, while the last one is application-oriented.

DOI： 10.1007/978-981-99-9772-5_10

researchmap
How to Physically Verify a Rectangle in a Grid: A Physical ZKP for Shikaku 査読

Suthee Ruangwises, Toshiya Itoh

Fun with Algorithms 226 24:1 - 24:12 2022年5月

　詳細を見る

記述言語：英語掲載種別：研究論文（国際会議プロシーディングス）

DOI： 10.4230/LIPIcs.FUN

researchmap
Physical zero-knowledge proof for Ripple Effect 査読

Suthee Ruangwises, Toshiya Itoh

Theoretical Computer Science 895 115 - 123 2021年12月

　詳細を見る

掲載種別：研究論文（学術雑誌）出版者・発行元：Elsevier BV

DOI： 10.1016/j.tcs.2021.09.034

researchmap
Competitive analysis for two variants of online metric matching problem 査読

Toshiya Itoh, Shuichi Miyazaki, Makoto Satake

Discrete Mathematics, Algorithms and Applications 13 ( 06 ) 2150156-1 - 2150156-16 2021年12月

　詳細を見る

記述言語：英語掲載種別：研究論文（学術雑誌）出版者・発行元：World Scientific Pub Co Pte Ltd

In the online metric matching problem, there are servers on a given metric space and requests are given one-by-one. The task of an online algorithm is to match each request immediately and irrevocably with one of the unused servers. In this paper, we pursue competitive analysis for two variants of the online metric matching problem. The first variant is a restriction where each server is placed at one of two positions, which is denoted by OMM([Formula: see text]). We show that a simple greedy algorithm achieves the competitive ratio of 3 for OMM([Formula: see text]). We also show that this greedy algorithm is optimal by showing that the competitive ratio of any deterministic online algorithm for OMM([Formula: see text]) is at least 3. The second variant is the online facility assignment problem on a line. In this problem, the metric space is a line, the servers have capacities, and the distances between any two consecutive servers are the same. We denote this problem by OFAL([Formula: see text]), where [Formula: see text] is the number of servers. We first observe that the upper and lower bounds for OMM([Formula: see text]) also hold for OFAL([Formula: see text]), so the competitive ratio for OFAL([Formula: see text]) is exactly 3. We then show lower bounds on the competitive ratio [Formula: see text] [Formula: see text], [Formula: see text] [Formula: see text] and [Formula: see text] [Formula: see text] for OFAL([Formula: see text]), OFAL([Formula: see text]) and OFAL([Formula: see text]), respectively.

DOI： 10.1142/s1793830921501561

researchmap
Physical ZKP for Connected Spanning Subgraph: Applications to Bridges Puzzle and Other Problems 査読国際誌

Suthee Ruangwises, Toshiya Itoh

Unconventional Computation and Natural Computation 12984 149 - 163 2021年10月

　詳細を見る

記述言語：英語掲載種別：研究論文（国際会議プロシーディングス）出版者・発行元：Springer International Publishing

DOI： 10.1007/978-3-030-87993-8_10

researchmap
Securely computing the n-variable equality function with 2n cards 査読

Suthee Ruangwises, Toshiya Itoh

Theoretical Computer Science 887 99 - 110 2021年10月

　詳細を見る

記述言語：英語掲載種別：研究論文（学術雑誌）出版者・発行元：Elsevier BV

DOI： 10.1016/j.tcs.2021.07.007

researchmap
Unpopularity Factor in the Marriage and Roommates Problems 査読

Suthee Ruangwises, Toshiya Itoh

Theory of Computing Systems 65 ( 3 ) 579 - 592 2021年4月

　詳細を見る

記述言語：英語掲載種別：研究論文（学術雑誌）出版者・発行元：Springer Science and Business Media LLC

DOI： 10.1007/s00224-020-09978-5

researchmap

その他リンク： https://link.springer.com/article/10.1007/s00224-020-09978-5/fulltext.html
Competitive Analysis for Two Variants of Online Metric Matching Problem 査読

Toshiya Itoh, Shuichi Miyazaki, Makoto Satake

Lecture Notes in Computer Science 12577 468 - 498 2020年12月

　詳細を見る

担当区分：筆頭著者記述言語：英語掲載種別：研究論文（国際会議プロシーディングス）出版者・発行元：Springer

DOI： 10.1007/978-3-030-64843-5_33

researchmap

その他リンク： https://dblp.uni-trier.de/db/conf/cocoa/cocoa2020.html#ItohMS20
Physical Zero-Knowledge Proof for Numberlink 査読

Suthee Ruangwises, Toshiya Itoh

10th International Conference on Fun with Algorithms 157 22:1 - 22:11 2020年9月

　詳細を見る

記述言語：英語

DOI： 10.4230/LIPIcs.FUN.2021.22

researchmap
Securely Computing the n-Variable Equality Function with 2n Cards

Suthee Ruangwises, Toshiya Itoh

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 12337 25 - 36 2020年

　詳細を見る

記述言語：英語掲載種別：研究論文（国際会議プロシーディングス）出版者・発行元：Springer Science and Business Media Deutschland GmbH

DOI： 10.1007/978-3-030-59267-7_3

Scopus

researchmap
Random Popular Matchings with Incomplete Preference Lists 査読

伊東利哉

Journal of Graph Algorithms and Applications 23 ( 5 ) 815 - 835 2019年10月

　詳細を見る

記述言語：英語掲載種別：研究論文（学術雑誌）

DOI： 10.7155/jgaa.00513

researchmap
On the Competitive Analysis for the Multi-Objective Time Series Search Problem 査読

Toshiya Itoh

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences E102-A ( 9 ) 1150 - 1158 2019年9月

　詳細を見る

記述言語：英語掲載種別：研究論文（学術雑誌）

DOI： 10.1587/transfun.E102.A.1150

researchmap
AND Protocols Using only Uniform Shuffles 査読

Suthee Ruangwises, Toshiya Itoh

Lectue Notes in Computer Science 11532 349 - 358 2019年7月

　詳細を見る

記述言語：英語掲載種別：研究論文（国際会議プロシーディングス）

DOI： 10.1007/978-3-030-19955-5_30

researchmap
Stable Noncrossing Matchings 査読

Suthee Ruangwises, Toshiya Itoh

Lectue Notes in Computer Science 11638 405 - 416 2019年7月

　詳細を見る

記述言語：英語掲載種別：研究論文（国際会議プロシーディングス）

DOI： 10.1007/978-3-030-25005-8_33

researchmap
Unpopularity Factor in the Marriage and Roommates Problems 査読

Suthee Ruangwises, Toshiya Itoh

Lectue Notes in Computer Science 11532 337 - 348 2019年7月

　詳細を見る

記述言語：英語掲載種別：研究論文（国際会議プロシーディングス）

DOI： 10.1007/978-3-030-19955-5_29

researchmap
On Aggregating Two Metrics with Relaxed Triangle Inequalities by the Weighted Harmonic Mean. 査読

Toshiya Itoh, Yoshinori Takei

IEICE Transactions 101-A ( 9 ) 1404 - 1411 2018年9月

　詳細を見る

記述言語：英語掲載種別：研究論文（学術雑誌）

DOI： 10.1587/transfun.E101.A.1404

researchmap
Optimal online algorithms for the multi-objective time series search problem

Shun Hasegawa, Toshiya Itoh

Theoretical Computer Science 718 58 - 66 2018年3月

　詳細を見る

記述言語：英語掲載種別：研究論文（学術雑誌）出版者・発行元：Elsevier B.V.

DOI： 10.1016/j.tcs.2017.01.008

Scopus

researchmap
Random popular matchings with incomplete preference lists 査読

Suthee Ruangwises, Toshiya Itoh

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 10755 106 - 118 2018年

　詳細を見る

記述言語：英語掲載種別：研究論文（国際会議プロシーディングス）出版者・発行元：Springer Verlag

DOI： 10.1007/978-3-319-75172-6_10

Scopus

researchmap
Optimal online algorithms for the multi-objective time series search problem 査読

Shun Hasegawa, Toshiya Itoh

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 9627 ( C ) 301 - 312 2016年

　詳細を見る

記述言語：英語掲載種別：研究論文（国際会議プロシーディングス）出版者・発行元：Springer Verlag

DOI： 10.1007/978-3-319-30139-6_24

Scopus

researchmap
Buffer management of multi-queue QoS switches with class segregation 査読

Toshiya Itoh, Seiji Yoshimoto

THEORETICAL COMPUTER SCIENCE 589 ( C ) 24 - 33 2015年7月

　詳細を見る

記述言語：英語掲載種別：研究論文（学術雑誌）

DOI： 10.1016/j.tcs.2015.04.010

Web of Science

researchmap
Weighted Random Popular Matchings 査読

Toshiya Itoh, Osamu Watanabe

RANDOM STRUCTURES & ALGORITHMS 37 ( 4 ) 477 - 494 2010年12月

　詳細を見る

記述言語：英語掲載種別：研究論文（学術雑誌）

DOI： 10.1002/rsa.20316

Web of Science

researchmap
Improved Constructions for Query-Efficient Locally Decodable Codes of Subexponential Length 査読

Toshiya Itoh, Yasuhiro Suzuki

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS E93D ( 2 ) 263 - 270 2010年2月

　詳細を見る

記述言語：英語掲載種別：研究論文（学術雑誌）

DOI： 10.1587/transinf.E93.D.263

Web of Science

researchmap
Approximation Algorithms for the Highway Problem under the Coupon Model

HAMANE Ryoso, ITOH Toshiya, TOMITA Kouhei

IEICE transactions on fundamentals of electronics, communications and computer sciences 92 ( 8 ) 1779 - 1786 2009年8月

　詳細を見る

記述言語：英語出版者・発行元：The Institute of Electronics, Information and Communication Engineers

When a store sells items to customers, the store wishes to decide the prices of items to maximize its profit. Intuitively, if the store sells the items with low (resp. high) prices, the customers buy more (resp. less) items, which provides less profit to the store. So it would be hard for the store to decide the prices of items. Assume that the store has a set V of n items and there is a set E of m customers who wish to buy the items, and also assume that each item i ∈ V has the production cost d_i and each customer e_j ∈ E has the valuation v_j on the bundle e_j ⊆ V of items. When the store sells an item i ∈ V at the price r_i, the profit for the item i is p_i = r_i - d_i. The goal of the store is to decide the price of each item to maximize its total profit. We refer to this maximization problem as the item pricing problem. In most of the previous works, the item pricing problem was considered under the assumption that p_i ≥ 0 for each i ∈ V, however, Balcan, et al. [In Proc. of WINE, LNCS 4858, 2007] introduced the notion of "loss-leader, " and showed that the seller can get more total profit in the case that p_i < 0 is allowed than in the case that p_i < 0 is not allowed. In this paper, we consider the line highway problem (in which each customer is interested in an interval on the line of the items) and the cycle highway problem (in which each customer is interested in an interval on the cycle of the items), and show approximation algorithms for the line highway problem and the cycle highway problem in which the smallest valuation is s and the largest valuation is l (this is called an [s, l]-valuation setting) or all valuations are identical (this is called a single valuation setting).

DOI： 10.1587/transfun.E92.A.1779

CiNii Books

researchmap
Approximation Preserving Reductions among Item Pricing Problems 査読

Ryoso Hamane, Toshiya Itoh, Kouhei Tomita

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS E92D ( 2 ) 149 - 157 2009年2月

　詳細を見る

記述言語：英語掲載種別：研究論文（学術雑誌）

DOI： 10.1587/transinf.E92.D.149

Web of Science

researchmap
Improved approximation algorithms for item pricing with bounded degree and valuation 査読

Ryoso Hamane, Toshiya Itoh

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS E91D ( 2 ) 187 - 199 2008年2月

　詳細を見る

記述言語：英語掲載種別：研究論文（学術雑誌）

DOI： 10.1093/ietisy/e91-d.2.187

Web of Science

researchmap
On (ε,k)-Min-Wise Independent Permutations 査読

Noga Alon, Toshiya Itoh, Tatsuya Nagatani

Random Structures and Algorithms 31 ( 3 ) 384 - 389 2007年10月

　詳細を見る

記述言語：英語掲載種別：研究論文（学術雑誌）

DOI： 10.1002/rsa.20184

Web of Science

researchmap
Competitive analysis of multi-queue preemptive QoS algorithms for general priorities 査読

Toshiya Itoh, Noriyuki Takahashi

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES E89A ( 5 ) 1186 - 1197 2006年5月

　詳細を見る

記述言語：英語掲載種別：研究論文（学術雑誌）

DOI： 10.1093/ietfec/e89-a.5.1186

Web of Science

researchmap
Constructing families of epsilon-approximate k-wise independent permutations 査読

T Itoh, Y Takei, J Tarui

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES E87A ( 5 ) 993 - 1003 2004年5月

　詳細を見る

記述言語：英語掲載種別：研究論文（学術雑誌）

Web of Science

researchmap
On the Sample Size of k-Restricted Min-Wise Independent Permutations and Other k-Wise Distributions 査読

Toshiya Itoh, Yoshinori Takei, Jun Tarui

ACM Annual Symposium on Theory of Computing 710 - 719 2003年6月

　詳細を見る

記述言語：英語掲載種別：研究論文（国際会議プロシーディングス）

DOI： 10.1145/780542.780645

researchmap
A note on the relationships among certified discrete log cryptosystems 査読

E Chida, T Itoh, H Shizuya

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES E86A ( 5 ) 1198 - 1202 2003年5月

　詳細を見る

記述言語：英語掲載種別：研究論文（学術雑誌）

Web of Science

researchmap
A nearly linear size 4-min-wise independent permutation family by finite geometries 査読

J Tarui, T Itoh, Y Takei

APPROXIMATION, RANDOMIZATION, AND COMBINATORIAL OPTIMIZATION 2764 396 - 408 2003年

　詳細を見る

記述言語：英語掲載種別：研究論文（学術雑誌）

DOI： 10.1007/978-3-540-45198-3_33

Web of Science

researchmap
Online Algorithms for Convex Case Capital Investment 査読

Toshiya Itoh

Interdisciplinary Information Sciences 8 ( 1 ) 77 - 88 2002年1月

　詳細を見る

記述言語：英語掲載種別：研究論文（学術雑誌）出版者・発行元：東北大学

In a factory, we need to make capital investments in machines for manufacturing a product. In this paper, we deal with the convex case capital investment such that more expensive machines have cheaper production costs. What we with to achieve is to design a good online algorithm that minimizes the sum of the production and capital costs when the production request and investment opportunities in the future are unknown. Azar, et al. proposed an (online) algorithm Convex for the convex case capital investment and showed that it is (4+2√2)-competitive. In this paper, we investigate the competitive ratio of the convex case capital investment more precisely and show that (1) for the convex case capital investment, the competitive ratio of the algorithm Convex is at least 4+2√2-ε for any ε>0 (Theorem 3.3). In the practical point of view, we introduce a notion of "γ-restricted" to the convex case capital investment and show that (2) for the γ-restricted convex case capital investment, the competitive ratio of the algorithm Convex is at most 5+4/(γ?4) for any γ?6 (Theorem 4.3); (3) for the γ-restricted convex case capital investment, the competitive ratio of the algorithm Convex is at least 5?ε for any ε>0 (Theorem 4.4). Finally, we also show that the competitive ratio of the γ-restricted convex case capital investment is at least 2?ε for any ε>0 (Theorem 5.4).

DOI： 10.4036/iis.2002.77

CiNii Books

researchmap

その他リンク： https://jlc.jst.go.jp/DN/JALC/00162126877?from=CiNii
Improved Approximation Lower Bounds for TSP with Distances One and Two 査読

Ryo Hirade, Toshiya Itoh

Interdisciplinary Information Sciences 8 ( 1 ) 63 - 76 2002年1月

　詳細を見る

記述言語：英語掲載種別：研究論文（学術雑誌）出版者・発行元：東北大学

The metric travelling salesman problem Δ-Tsp is the traveling salesman problem in which the distances among cities satisfy the triangle inequality. In this paper, we consider the matric traveling salesman problem Δ(1,2)-Tsp with distances one and two and Δ(1,2,3)-Tsp with distances one, two, and three as the special cases of Δ-Tsp. Since Δ(1,2)-Tsp is NP-complete, it is NP-hard to find an optimal solution for Δ(1,2)-Tsp. So in polynomial time, we with to find an approximate solution for Δ(1,2)-Tsp. owever Δ(1,2)-Tsp is APX-complete, there is a nontrivial approximation lower bound for Δ(1,2)-Tsp. For any ε>0, Engebretsen showed that it is NP-hard to approximate the symmetric Δ(1,2)-Tsp within 5381/5380-ε; the asymmetric Δ(1,2)-Tsp within 2805/2804-ε, and Bochenhauer, et al. showed that it is NP-hard to approximate the symmetric Δ(1,2,3)-Tsp within 3813/3812-ε. In this paper, we improve those lower bounds and show that for any ε>0, it is NP-hard to approximate the symmetric Δ(1,2)-Tsp within 1027/1026-ε (Corollary 4.5); the asymmetric Δ(1,2)-Tsp within 535/534-ε (Corollary 4.7); the symmetric Δ(1,2,3)-Tsp within 817/816-ε (Theorem 5.2); the asymmetric Δ(1,2,3)-Tsp within 364/363-ε (Theorem 5.3). We also show that for any ε>0, it is NP-hard to approximate Shortest-Superstring within 1279/1278-ε (Corollary 6.3).

DOI： 10.4036/iis.2002.63

CiNii Books

researchmap

その他リンク： https://jlc.jst.go.jp/DN/JALC/00162126860?from=CiNii
Constructing an optimal family of min-wise independent permutations

Yoshinori Takei, Toshiya Itoh, Takahiro Shinozaki

IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E83-A ( 4 ) 747 - 754 2000年4月

　詳細を見る

記述言語：英語出版者・発行元：一般社団法人電子情報通信学会

Scopus

CiNii Books

researchmap
A general construction of min-wise independent permutations 査読

Y Takei, T Itoh

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES E83A ( 4 ) 646 - 655 2000年4月

　詳細を見る

記述言語：英語掲載種別：研究論文（学術雑誌）

Web of Science

researchmap
On permutations with limited independence 査読

T Itoh, Y Takei, J Tarui

PROCEEDINGS OF THE ELEVENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS 137 - 146 2000年

　詳細を見る

記述言語：英語掲載種別：研究論文（国際会議プロシーディングス）

DOI： 10.1145/338219.338245

Web of Science

researchmap
A general construction of min-wise independent permutations

Yoshinori Takei, Toshiya Itoh

IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E83-A ( 4 ) 646 - 654 2000年

　詳細を見る

記述言語：英語掲載種別：研究論文（学術雑誌）出版者・発行元：Institute of Electronics, Information and Communication, Engineers, IEICE

Scopus

researchmap
Divertible and subliminal-free zero-knowledge proofs for languages 査読

Mike Burmester, Yvo G. Desmedt, Toshiya Itoh, Kouichi Sakurai, Hiroki Shizuya

Journal of Cryptology 12 ( 3 ) 197 - 223 1999年

　詳細を見る

記述言語：英語掲載種別：研究論文（学術雑誌）出版者・発行元：Springer New York LLC

DOI： 10.1007/s001459900053

Scopus

researchmap
A language-dependent cryptographic primitive 査読

Toshiya Itoh, Yuji Ohta, Hiroki Shizuya

Journal of Cryptology 10 ( 1 ) 37 - 49 1997年

　詳細を見る

記述言語：英語掲載種別：研究論文（学術雑誌）出版者・発行元：Springer New York

DOI： 10.1007/s001459900018

Scopus

researchmap
Simulating fair dice with biased coins 査読

T Itoh

INFORMATION AND COMPUTATION 126 ( 1 ) 78 - 82 1996年4月

　詳細を見る

記述言語：英語掲載種別：研究論文（学術雑誌）

DOI： 10.1006/inco.1996.0036

Web of Science

researchmap
A progress report on subliminal-free channels

Mike Burmester, Yvo G. Desraedt, Toshiya Itoh, Kouichi Sakurai, Hiroki Shizuya, Moti Yung

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 1174 157 - 168 1996年

　詳細を見る

記述言語：英語掲載種別：研究論文（国際会議プロシーディングス）出版者・発行元：Springer Verlag

DOI： 10.1007/3-540-61996-8_39

Scopus

researchmap
A Low Communication Competitive Interactive Proof System for Promised Quadratic Residuosity 査読

Toshiya Itoh, Masafumi Hoshi, Shigeo Tsujii

Journal of Cryptology 9 ( 2 ) 101 - 109 1996年

　詳細を見る

記述言語：英語掲載種別：研究論文（学術雑誌）

DOI： 10.1007/BF00190804

researchmap
On the Discrepancy Between Serial and Parallel of Zero-Knowledge Protocols 査読

Kouichi Sakurai, Toshiya Itoh

Lectue Notes in Computer Science 740 246 - 359 1994年8月

　詳細を見る

記述言語：英語掲載種別：研究論文（国際会議プロシーディングス）

DOI： 10.1007/3-540-48071-4_17

researchmap
A NOTE ON AM LANGUAGES OUTSIDE NP BOOLEAN-OR CO-NP 査読

H SHIZUYA, T ITOH

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES E77A ( 1 ) 65 - 71 1994年1月

　詳細を見る

記述言語：英語掲載種別：研究論文（学術雑誌）

Web of Science

researchmap
SUBLIMINAL CHANNELS FOR TRANSFERRING SIGNATURES - YET ANOTHER CRYPTOGRAPHIC PRIMITIVE 査読

K SAKURAI, T ITOH

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES E77A ( 1 ) 31 - 38 1994年1月

　詳細を見る

記述言語：英語掲載種別：研究論文（学術雑誌）

Web of Science

researchmap
A low communication competitive interactive proof system for promised quadratic residuosity

Toshiya Itoh, Masafumi Hoshi, Shigeo Tsujii

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 773 61 - 72 1994年

　詳細を見る

記述言語：英語掲載種別：研究論文（国際会議プロシーディングス）出版者・発行元：Springer Verlag

DOI： 10.1007/3-540-48329-2_6

Scopus

researchmap
Language dependent secure bit commitment

Toshiya Itoh, Yuji Ohta, Hiroki Shiauya

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 839 188 - 201 1994年

　詳細を見る

記述言語：英語掲載種別：研究論文（国際会議プロシーディングス）出版者・発行元：Springer Verlag

DOI： 10.1007/3-540-48658-5_20

Scopus

researchmap
On the Complexity of Constant Round ZKIP of Possession of Knowledge 査読

Toshiya Itoh, Kouichi Sakurai

Lectue Notes in Computer Science 739 331 - 345 1993年11月

　詳細を見る

記述言語：英語掲載種別：研究論文（国際会議プロシーディングス）

DOI： 10.1007/3-540-57332-1_28

researchmap
Any Language in IP Has a Divertible ZKIP 査読

Toshiya Itoh, Kouichi Sakurai, Hiroki Shizuya

Lectue Notes in Computer Science 739 382 - 396 1993年11月

　詳細を見る

DOI： 10.1007/3-540-57332-1_33

researchmap
CONSTANT ROUND PERFECT ZKIP OF COMPUTATIONAL ABILITY 査読

T ITOH, K SAKURAI

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES E76A ( 7 ) 1225 - 1233 1993年7月

　詳細を見る

記述言語：英語掲載種別：研究論文（学術雑誌）

Web of Science

researchmap
PRACTICAL CONSEQUENCES OF THE DISCREPANCY BETWEEN ZERO-KNOWLEDGE PROTOCOLS AND THEIR PARALLEL EXECUTION 査読

K SAKURAI, T ITOH

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES E76A ( 1 ) 14 - 22 1993年1月

　詳細を見る

記述言語：英語掲載種別：研究論文（学術雑誌）

Web of Science

researchmap
On bit correlations among preimages of “many to one” one-way functions: — A new approach to study on randomness and hardness of one-way functions —

Kouichi Sakurai, Toshiya Itoh

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 718 435 - 446 1993年

　詳細を見る

記述言語：英語掲載種別：研究論文（国際会議プロシーディングス）出版者・発行元：Springer Verlag

DOI： 10.1007/3-540-57220-1_81

Scopus

researchmap
Subliminal channels for signature transfer and their application to signature distribution schemes

Kouichi Sakurai, Toshiya Itoh

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 718 231 - 243 1993年

　詳細を見る

記述言語：英語掲載種別：研究論文（国際会議プロシーディングス）出版者・発行元：Springer Verlag

DOI： 10.1007/3-540-57220-1_65

Scopus

researchmap
ON THE COMPLEXITY OF HYPERELLIPTIC DISCRETE LOGARITHM PROBLEM 査読

H SHIZUYA, T ITOH, K SAKURAI

IEICE TRANSACTIONS ON COMMUNICATIONS ELECTRONICS INFORMATION AND SYSTEMS 74 ( 8 ) 2129 - 2135 1991年8月

　詳細を見る

記述言語：英語掲載種別：研究論文（学術雑誌）

Web of Science

researchmap
LANGUAGE MEMBERSHIP VERSUS POSSESSION OF KNOWLEDGE IN CONSTANT ROUND ZKIP 査読

K SAKURAI, T ITOH

IEICE TRANSACTIONS ON COMMUNICATIONS ELECTRONICS INFORMATION AND SYSTEMS 74 ( 8 ) 2118 - 2123 1991年8月

　詳細を見る

記述言語：英語掲載種別：研究論文（学術雑誌）

Web of Science

researchmap
ON THE COMPLEXITY OF HYPERELLIPTIC DISCRETE LOGARITHM PROBLEM 査読

H SHIZUYA, T ITOH, K SAKURAI

ADVANCES IN CRYPTOLOGY - EUROCRYPT 91 547 337 - 351 1991年

　詳細を見る

記述言語：英語掲載種別：研究論文（国際会議プロシーディングス）

Web of Science

researchmap
Provably secure key-updating schemes in identity-based systems 査読

S. Shinozaki, T. Itoh, A. Fujioka, S. Tsujii

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 473 ( 3 ) 16 - 30 1991年

　詳細を見る

記述言語：英語掲載種別：研究論文（国際会議プロシーディングス）出版者・発行元：Springer Verlag

DOI： 10.1007/3-540-46877-3_3

Scopus

researchmap
ON THE COMPLEXITY OF HYPERELLIPTIC DISCRETE LOGARITHM PROBLEM 査読

H SHIZUYA, T ITOH, K SAKURAI

LECTURE NOTES IN COMPUTER SCIENCE 547 337 - 351 1991年

　詳細を見る

記述言語：英語掲載種別：研究論文（学術雑誌）

DOI： 10.1007/3-540-46416-6_29

Web of Science

researchmap
Demonstrating possession without revealing factors and its application 査読

Hiroki Shizuya, Kenji Koyama, Toshiya Itoh

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 453 273 - 293 1990年

　詳細を見る

記述言語：英語掲載種別：研究論文（国際会議プロシーディングス）出版者・発行元：Springer Verlag

DOI： 10.1007/BFb0030368

Scopus

researchmap
STRUCTURE OF PARALLEL MULTIPLIERS FOR A CLASS OF FIELDS GF(2M) 査読

T ITOH, S TSUJII

INFORMATION AND COMPUTATION 83 ( 1 ) 21 - 40 1989年10月

　詳細を見る

記述言語：英語掲載種別：研究論文（学術雑誌）

DOI： 10.1016/0890-5401(89)90045-X

Web of Science

researchmap
GENERALIZED FAST ALGORITHM FOR COMPUTING MULTIPLICATIVE INVERSES IN GF(2M) 査読

Y ASANO, T ITOH, S TSUJII

ELECTRONICS LETTERS 25 ( 10 ) 664 - 665 1989年5月

　詳細を見る

記述言語：英語掲載種別：研究論文（学術雑誌）

DOI： 10.1049/el:19890449

Web of Science

researchmap
AN ID-BASED CRYPTOSYSTEM BASED ON THE DISCRETE LOGARITHM PROBLEM 査読

S TSUJII, T ITOH

IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS 7 ( 4 ) 467 - 473 1989年5月

　詳細を見る

記述言語：英語掲載種別：研究論文（学術雑誌）

Web of Science

researchmap
An efficient algorithm for deciding quadratic residuosity in finite fields GF(pm) 査読

Toshiya Itoh, Shigeo Tsujii

Information Processing Letters 30 ( 3 ) 111 - 114 1989年2月

　詳細を見る

記述言語：英語掲載種別：研究論文（学術雑誌）

DOI： 10.1016/0020-0190(89)90127-0

Scopus

researchmap
NEW NONINTERACTIVE IDENTITY-BASED KEY DISTRIBUTION-SYSTEM 査読

S TSUJII, K KUROSAWA, T ITOH

ELECTRONICS LETTERS 24 ( 22 ) 1356 - 1357 1988年10月

　詳細を見る

記述言語：英語掲載種別：研究論文（学術雑誌）

Web of Science

researchmap
A FAST ALGORITHM FOR COMPUTING MULTIPLICATIVE INVERSES IN GF(2M) USING NORMAL BASES 査読

T ITOH, S TSUJII

INFORMATION AND COMPUTATION 78 ( 3 ) 171 - 177 1988年9月

　詳細を見る

記述言語：英語掲載種別：研究論文（学術雑誌）

DOI： 10.1016/0890-5401(88)90024-7

Web of Science

researchmap
EFFECTIVE RECURSIVE ALGORITHM FOR COMPUTING MULTIPLICATIVE INVERSES IN GF(2M) 査読

T ITOH, S TSUJII

ELECTRONICS LETTERS 24 ( 6 ) 334 - 335 1988年3月

　詳細を見る

記述言語：英語掲載種別：研究論文（学術雑誌）

DOI： 10.1049/el:19880226

Web of Science

researchmap
A public‐key cryptosystem based on the difficulty of solving a system of nonlinear equations 査読

Shigeo Tsujii, Toshiya Itoh, Atsushi Fujioka, Kaoru Kurosawa, Tsutomu Matsumoto

Systems and Computers in Japan 19 ( 2 ) 10 - 18 1988年

　詳細を見る

記述言語：英語掲載種別：研究論文（学術雑誌）

DOI： 10.1002/scj.4690190202

Scopus

researchmap
ID-BASED CRYPTOSYSTEM USING DISCRETE LOGARITHM PROBLEM 査読

S TSUJII, T ITOH, K KUROSAWA

ELECTRONICS LETTERS 23 ( 24 ) 1318 - 1320 1987年11月

　詳細を見る

記述言語：英語掲載種別：研究論文（学術雑誌）

Web of Science

researchmap
Efficient probabilistic algorithm for solving quadratic equations over finite fields 査読

T. Itoh

Electronics Letters 23 ( 17 ) 869 - 870 1987年

　詳細を見る

記述言語：英語掲載種別：研究論文（学術雑誌）

DOI： 10.1049/el:19870615

Scopus

researchmap

▼全件表示

MISC

Advanced Mathematical Science for Mobility Society

Tsubasa Harada, Toshiya Itoh, Shigeo Matsubara, Shuichi Miyazaki, Makoto Yokoo

Springer 2024年3月

　詳細を見る

記述言語：英語掲載種別：記事・総説・解説・論説等（学術雑誌）出版者・発行元：Springer Nature Singapore

DOI： 10.1007/978-981-99-9772-5

researchmap

その他リンク： https://link.springer.com/content/pdf/10.1007/978-981-99-9772-5
Closed Formulas of the Arithmetic Mean Component Competitive Ratio for the 3-Objective and 4-Objective Time Series Search Problems.

Toshiya Itoh, Yoshinori Takei

CoRR abs/1712.00214 2017年

　詳細を見る

掲載種別：機関テクニカルレポート，技術報告書，プレプリント等

researchmap
不完全選好リストに対する乱拓最適優先マッチング

ルワングウィセススティー, 伊東利哉

電子情報通信学会技術研究報告 = IEICE technical report : 信学技報 116 ( 262 ) 1 - 8 2016年10月

　詳細を見る

記述言語：日本語出版者・発行元：電子情報通信学会

CiNii Books

researchmap
2011年度冬のLAシンポジウム Greedy Algorithms for Multi-Queue Buffer Management with Class Segregation (アルゴリズムと計算理論の新展開 : RIMS研究集会報告集)

伊東利哉, 吉本聖司

数理解析研究所講究録 1799 84 - 91 2012年6月

　詳細を見る

記述言語：英語出版者・発行元：京都大学

CiNii Books

researchmap

その他リンク： http://hdl.handle.net/2433/172997
キャンパス共通認証認可システムの構築と運用

飯田勝吉, 新里卓史, 伊東利哉, 渡辺治

電子情報通信学会論文誌. B, 通信 = The transactions of the Institute of Electronics, Information and Communication Engineers. B 92 ( 10 ) 1554 - 1565 2009年10月

　詳細を見る

記述言語：日本語出版者・発行元：一般社団法人電子情報通信学会

東京工業大学及び多くの大学において,様々なアプリケーションで認証が必要となり,各部局の担当者がこれまで個別に各アプリケーションごとに認証システムを構築されることが多かった.一方,今後多数の認証が必要なウェブアプリケーションの導入が期待されており,大学で共通の認証システムの構築が極めて重要となる.本論文では東京工業大学において平成18年3月に導入したキャンパス共通認証認可システムの構築と運用について述べる.キャンパス共通認証認可システムは,大学の重要なICT(Information Communication Technology)基盤として設計された.主な特徴としては,すべての学内ユーザに対し基本情報環境権という考え方でICカード身分証と連動してアカウントを発行すること,PKI(Public Key Infrastructure)技術などを用いた高いセキュリティを提供すること,ウェブシングルサインオンの導入によりユーザに対し高い利便性を提供すること,学術国際情報センターと事務組織等の作業分担による高い運用管理性を提供することが挙げられる.要求仕様,設計,構築などを述べた後に東京工業大学の経験によって得られた技術的及び運用体制構築の知見を明らかにする.

CiNii Books

researchmap
重み付き乱択最適選好マッチング

伊東利哉, 渡辺治

電子情報通信学会技術研究報告. COMP, コンピュテーション 107 ( 127 ) 41 - 48 2007年6月

　詳細を見る

記述言語：英語出版者・発行元：一般社団法人電子情報通信学会

人数nのユーザ集合をA,要素数mの商品集合をIとする.ユーザ集合AはA_1,A_2,...,A_kのようにk分割されており,各A_iにはw_1>w_2>…>w_k>Oを満たす重みw_iが割り当てられているものとする.各ユーザに各商品を割り当てる問題-k重み付き商品割り当て問題-を考える.各ユーザx∈Aは商品に対する選好ベクトルを持つ.ユーザxが商品qより商品pを好むとは,選好ベクトルにおいてpが9より上位に位置することであり,任意のマッチングMとM'に対して,M&sc;_xM'であるとは,ユーザxがM'(x)よりM(x)を好むことを言う.マッチングMがマッチングM'より"選好的である"とは,M&sc;_xM'を満たすユーザx∈Aの重みの総和がM&sc;_xM'を満たすユーザy∈Aの重みの総和より大きいことを言い,マッチングMが"最適選好である"とは,Mより選好的であるM'≠Mが存在しないことを言う.Mahdianはk=1の場合,m>1.42nであるならが,商品割り当て問題の乱択入力が高い確率で最適選好的マッチングを持つことを示したが,一般のk&ge;2に関して,その詳細は未解明であっ

CiNii Books

researchmap
商品価格設定問題に対する近似アルゴリズム

浜根良壮, 伊東利哉

電子情報通信学会技術研究報告. COMP, コンピュテーション 107 ( 24 ) 1 - 8 2007年4月

　詳細を見る

記述言語：日本語出版者・発行元：一般社団法人電子情報通信学会

商品に対する顧客の購入可能金額(見積り価格)が既知であるとする.このとき,売り手が商品の価格を高く設定すると,顧客は商品の購入を控えるため,売り手の利益は減少する.一方,売り手が商品の価格を安く設定すると,顧客は商品を積極的に購入するが商品あたりの利益が減少するため,売り手の利益は減少する.このように,各商品に対する顧客の購入可能金額(見積り金額)が既知である場合に,売り手が自らの利益を最大化するように商品の価格設定を行なう問題を"商品価格設定問題"という.商品価格設定問題については,その状況-各商品の供給量が有限(あるいは無限)であるか,各顧客が個別に特定(あるいは不特定)の商品群の購入を希望するか-に応じて,さまざまな問題設定が可能となる.BalcanとBlumは,各商品の供給量が無限であり,各顧客が個別に特定の商品群の購入を希望する場合の商品価格設定問題をグラフにより定式化し,効率的な近似アルゴリズムを構成するとともにその近似比の解析を行った.本論文では,入力グラフの最大次数や顧客の最大見積もり価格比に注目することにより,各商品の供給量が無限であり,各顧客が個別に特定の商品群の購入を希望する場合の商品価格設定問題に大して新しい近似アルゴリズムを提案し,本論文で提案するアルゴリズムが良好な近似比を有することを示す.

CiNii Books

researchmap
大学内の業務・システムと連携するキャンパス共通認証認可システムの構築と運用

新里卓史, 飯田勝吉, 岸本幸一, 太刀川博之, 昆野長典, 山崎孝治, 伊東利哉, 渡辺治

電子情報通信学会技術研究報告. NS, ネットワークシステム 106 ( 577 ) 201 - 206 2007年3月

　詳細を見る

記述言語：日本語出版者・発行元：一般社団法人電子情報通信学会

近年,大学内での情報資源のアクセス制御が問題となっている.たとえば成績情報や給与情報などをオンラインで取り扱うシステムは,扱う情報の機密性が高いため,認証技術によるアクセス制御が必須になる.様々なシステムごとに個々に認証を行うと,ユーザの利便性,セキュリティ,そしてシステムの保守性の全てが低下する.そこで,様々なシステムの認証を共通化するキャンパス共通認証認可システムが重要となる.そのようなキャンパス共通認証認可システムを設計する際には,大学内の業務やシステムとの連携が重要となる.本稿では,東京工業大学に構築し,現在運用中のキャンパス共通認証認可システムの設計を紹介し,特に業務やシステムとの連携の詳細を記す.また,システム運用を開始することによって明らかになった課題とその解決案を示す.これらによって,当該システム導入を検討している組織に対しての有用な情報提供を目指す.

CiNii Books

researchmap
ε-近似κ-制限最小値独立置換族のサイズの下界

伊東利哉, 永谷達也

電子情報通信学会技術研究報告. COMP, コンピュテーション 105 ( 680 ) 23 - 30 2006年3月

　詳細を見る

記述言語：英語出版者・発行元：一般社団法人電子情報通信学会

最小値独立置換族(とその拡張概念であるε-近似k-制限最小値独立置換族)は,インターネット上に存在する類似した文書の特定に有用であることが知られており,それらの構成法,置換族のサイズに関する(非)構成的上界・下界が数多く示されている.任意の整数n>0に対し,集合[numerical formula]上の置換全体の集合をS_nとするとき,置換族F⊆S_nがε-近似k-制限最小値独立であるとは,任意の(空でない)部分集合[numerical formula]と任意のx∈Xに対し,置換π∈Fを一様且つ無作為に選んだ場合,[numerical formula]が成り立つことを言う(ただし,∥A∥は有限集合Aの要素数を表すものとする).これまでにε-近似k-制限最小値独立置換族F⊆S_nのサイズに関して,以下のことが知られている:(構成的上界)[numerical formula];(非構成的上界)[numerical formula];(下界)[numerical formula],[numerical formula],[numerical formula].本論文では,まず始めに完全グラフの多色枝塗りに関するラムゼー数の上界を評価し,さらに代数的手法を用いることで,より厳密なε-近似k-制限最小値独立置換族F⊆S_nのサイズの下界[numerical formula]を導出する.

CiNii Books

researchmap
無線LANにおけるセキュリティ技術の動向

友石正彦, 吉田真一, 伊東利哉

電子情報通信学会技術研究報告. SITE, 技術と社会・倫理 104 ( 96 ) 1 - 6 2004年5月

　詳細を見る

記述言語：日本語出版者・発行元：一般社団法人電子情報通信学会

本稿では、現在広く運用されている、既存の無線LANシステムの問題点をまとめ、次世代規格に用いられている技術について述べる。特に、組織等において既存の無線LANを利用する際の問題点となっていた無線LANクライアント(利用者)認証について、新しい無線LAN規格で採用される、IEEE802.1X、EAP、RADIUSなどの認証技術について説明する。また、これらの技術を用いたシステム構築例について説明し、現状の運用上の問題点、管理・運用上の注意点について説明する。

CiNii Books

researchmap
フェイステル変換を用いた近似的κ-対ランダム置換族の構成

伊東利哉, 永谷達也, 垂井淳

電子情報通信学会技術研究報告. COMP, コンピュテーション 104 ( 16 ) 45 - 52 2004年4月

　詳細を見る

記述言語：英語出版者・発行元：一般社団法人電子情報通信学会

一般にk-対ランダム置換族は,偽造不可能な署名方式の設計や確率的アルゴリズムの決定性アルゴリズムヘの変換等の応用を待つことが知られている.しかし,実用的な状況ではε-近似的k-対ランダム置換族で代用可能な場合が想定され,そのような条件緩和によってより効率的な置換族の実現が期待される.任意の整数n>0に対してS_nを集合{0,1,...,n-1}上の置換全体とする.本論文では共通鍵暗号方式DES (Data Encryption Standard)の設計において本質的な役割を果たすフェイステル変換を繰り返し用いて置換族を構成し,任意のn=p^<2h>(p: 素数;h>O)に対してk = O(log n)であるならば|F|=(n^<k^<k>>/ε^k)^<3+o>(1)を満たすε-近似的k-対ランダム置換族F⊆S_nが構成可能であることを示す(これはε-近似的κ-対ランダム置換族F⊆S_nの非自明な最初の構成法である).さらに,本論文で構成された置換族がO(log n)-領域要素別法本可能であることを示す.

CiNii Books

researchmap
ビデオ配信スケジューリングの競合比の解析

丸地康平, 伊東利哉

電子情報通信学会技術研究報告. COMP, コンピュテーション 103 ( 723 ) 33 - 40 2004年3月

　詳細を見る

記述言語：英語出版者・発行元：一般社団法人電子情報通信学会

ビデオ・オン・デマンド(VoD)とは,クライアントの配信要求に応じてサーバが即座に映像の配信を行う応答するシステムであり,サーバの帯域負荷-最大帯域量・総帯域量-がVoDシステムにおける最も重要な尺度の一つと考えられる.実際ストリーム同士をオンラインアルゴリズムによってマージ(合流)する手法により,サーバの帯域負荷が軽減可能であることが知られている.最近Chanらは,追随係数λ[>!_]1を持つオンラインアルゴリズムとして,修正貪欲アルゴリズムを提案し,任意のλ[>!_]1に対して-最大帯域量に関する競合比が(2+ε)以下であること;総帯域量に関する競合比が2.5以下であること-を示した.本論文では,修正貪欲アルゴリズムの動作をより精密に解析することにより,最大帯域量に関する結果-(1)任意のλ[>!_]1に対して,競合比が2以下となること;(2)任意のλ[>!_]1に対して,競合比が2以上となること-を示すとともに,総帯域量に関する結果-(3)任意のλ[>!_]2に対して,競合比が2以下となること;(4)任意のλ[>!_]1に対して,競合比が(5λ+4)/(3λ+3)以上となること-を明らかにする.

CiNii Books

researchmap
決定性QoS問題の競合比の下界について

伊東利哉, 南雲隆伸

電子情報通信学会技術研究報告. COMP, コンピュテーション 103 ( 723 ) 25 - 32 2004年3月

　詳細を見る

記述言語：英語出版者・発行元：一般社団法人電子情報通信学会

近年のインターネットの爆発的な普及に伴い,ネットワーク機器に過剰な負荷がかかり,また帯域損失・バケット消失・応答遅延などの通信品質の劣化が深刻化している.このような通信品質の劣化を防ぐためにQuality of Service (QoS)の概念が注目されている.一般にQoSスイッチは複数のキューを持ち,各キューは到来するパケットを格納するための複数のスロットを有する.また各パケットはその優先順位を表ず""優先度"が割り当てられている.ネットワーク上の通信量はしばしば変化するため, QoSスイッチは転送パケットの優先度の総和を最大にするように到来するパケットの制御を行う.本論文では,優先度が1とα[>!_]1に制限された決定性QoS問題に関して,その競合比の下界の解析を行い,任意のα[>!_]1に対して-もしα[>!_]α^*ならば1+/αln((α-1)/α)以上;もし1[>!_]α<α^*ならば1/(1-e^<-γ0>)以上-が成り立つことを示す.ただしα^* [〜!〜] 1.657でありγ_0は方程式e^<-γ>(1/α+γ)=1-e^γの根とする.またこの結果より,単一優先度決定性QoS問題に関して,その競合比の下界が1.466以上となることが容易に導出される(これは単一優先度決定性QoS問題の競合比に関する既知の下界1.366を改善するものである).

CiNii Books

researchmap
チュートリアル講演 Recent Progress on Min-Wise Independent Permutations

伊東利哉, 武井由智, 垂井淳

電子情報通信学会技術研究報告 103 ( 394 ) 41 - 50 2003年10月

　詳細を見る

記述言語：英語出版者・発行元：一般社団法人電子情報通信学会

Broderらによって提案された"最小値独立置換族"は,電子文書の類似度を効率的に判定する際の基本的な概念であり,WEB上の類似文書の検出・確率的アルゴリズムの効率化などの応用を持つことが知られている.本稿では,最小値独立置換族(及びその拡張概念であるε-近似的最小中国財務局長独立置換族・k-制限最小値独立置換族など)に関する最近の成果-(1)最小値独立置換族を用いた電子文書の類似性判定法 : (2)最小値独立置換族のサイズに関する上界と下界 ; (3)ε-近似的最初値独立置換族のサイズに関する上界と下界 ; (4)k-制限最小値独立置換族のサイズに関する上界と下界-について述べ,最小値独立置換族(及びその拡張概念)の構成方法の現状を概観する.

CiNii Books

researchmap
B-7-48 零知識証明を用いた分散個人認証システム

本橋賢二, 角田貢, 山岡克式, 伊東利哉, 曽根原登

電子情報通信学会ソサイエティ大会講演論文集 2003 ( 2 ) 229 - 229 2003年9月

　詳細を見る

記述言語：日本語出版者・発行元：一般社団法人電子情報通信学会

CiNii Books

researchmap
有限幾何を用いた線形サイズ4-制限最小値独立置換族の構成

垂井淳, 伊東利哉, 武井由智

電子情報通信学会技術研究報告. COMP, コンピュテーション 103 ( 119 ) 35 - 42 2003年6月

　詳細を見る

記述言語：英語出版者・発行元：一般社団法人電子情報通信学会

伊東・武井・垂井[7, STOC'03]は,置換族〓⊆S_nがk-制限最小値独立であならば|〓|=Ω(n^<[(k-1)/2]>)が成り立ち,k-順位独立であるならば|〓|=Ω(n^<[(k-1)/2]>)が成り立つことを示した.本論文では,アフィン幾何を用いて,そのサイズが|〓|= O(nlg^2n)となる3-制限最小値独立置換族〓⊆S_nおよび|〓|=O(nlg^3n)となる4-制限最小値独立置換族〓⊆S_nを構成するとともに,射影幾何を用いて,そのサイズが|〓|= O(n^3lg^6n)となる4-順位独立置換族〓⊆S_nを構成する.定義より,k-順位独立はk-制限最小値独立より強い概念であることは明らかであるが,本論文で構成する4-制限最小値独立置換族は,4-順位独立が4-制限最小値独立より真に強い概念であることを保証する.

CiNii Books

researchmap
近似的κ-対独立置換族の構成

伊東利哉, 武井由智

電子情報通信学会技術研究報告. COMP, コンピュテーション 103 ( 31 ) 15 - 22 2003年4月

　詳細を見る

記述言語：英語出版者・発行元：一般社団法人電子情報通信学会

本論文ではε-近似k-対独立置換族のサイズの上界・下界に関して考察し,以下の結果を示す:(1)任意のε>0に対して,置換族F⊆S_nがε-近似k-対独立であるとき,ε<1ならば|F|≥n(n-1)…(n-k+1),一方ε≥1ならば|F|≥{n(n-1)…(n-k+1)}/(1+ε)が成り立つ;(2)任意のε>0に対して,|F|=O((klnn)/εn(n-1)…(n-k+1)))を満たすε-近似k-対独立置換族F⊆S_nが存在する;(3)任意のεと任意の整数n=P^m-1(p:素数;m:正整数)に対して,|F|=O(n(n-1)/ε)を満たす(多項式時間標本可能な)ε-近似2-対独立置換族F⊆S_nが構成可能である;(3)任意のεと任意の整数n=P^m(p: 素数; m: 正整数)に対して,|F|=O(n(n-1)(n-2)/ε)を満たす(多項式時間標本可能な)ε-近似3-対独立置換族F⊆S_nが構成可能である

CiNii Books

researchmap
k-制限最小値独立置換族, その他 k-wise 独立性のサンプルサイズ下界

伊東利哉, 武井由智, 垂井淳

電子情報通信学会技術研究報告. COMP, コンピュテーション 102 ( 343 ) 25 - 32 2002年9月

　詳細を見る

記述言語：英語出版者・発行元：一般社団法人電子情報通信学会

集合{0,1,...,n-1}上の置換族Fがk-制限最小値独立であるとは,置換πをFからランダムにサンプルするとき,|X|≤kを満たす任意のX⊆{0,1,_,n-1}と任意のx∈Xに対して,Pr[min{π(X)}=π(x)]=1/|X|を満たすことをいう.本稿では,k-制限最小値独立置換族Fに対して|F|≥m(n-1,k-1)が成り立つことを示す.ただし,m(n,d)=Σ^<d/2>_<i=0>( ^n_i)(d:偶数);m(n,d)=Σ^<(d-i)/2>_i=0 ( ^n_i) + ( ^<n-1>_(d-1)/2)(d:奇数)・この下界は,F上の分布と無関係に成立する.これは,既知の事実-確率変数X_1,X_2,...,X.:Ω→{0,1}のどのd個も独立でかつPr[X_i=1]≠0,1であるとき,|Ω|≥m(n,d)-を一般化し,以下のように導出される.確率変数X_1,X_2,...,X_n:Ω→{0,1}が,任意のd個組みにおいて,確率変数Y_1,Y_2,...,Y_nと同一の分布に従い,さらにn個組み(Y_1,Y_2,...,Y_n)が2^n個の全ての値において正の確率を持つとき,|Ω|≥m(n,d)が成り立つ.k-制限最小値独立置換族Fから誘導される確率変数X_1,X_2,...,X_n:F→{0,1}に関して,このような確率変数Y_1,Y_2,...,Y_nの存在は明らかである.

CiNii Books

researchmap
On Lower Bounds for the Communication Complexity of Private Information Retrieval

ITOH Toshiya

IEICE transactions on fundamentals of electronics, communications and computer sciences 84 ( 1 ) 157 - 164 2001年1月

　詳細を見る

記述言語：英語出版者・発行元：一般社団法人電子情報通信学会

Private information retrieval for k 〓 1 databases (denoted by (k, l)-PIR for short) is a protocol that (1) a user sends an l tuple query to each of k noncommunicating replicated databases; (2) each database responds the user with an answer corresponding to the l tuple query; (3) the user privately retrieve any single bit out of the n bits of data stored in k databases. In this model, "privacy" implies that the user retrieves the bit he is interested in but releases to each database nothing about which bit he wishes to get. In general, the efficiency of (k, l)-PIR is measured by the total amount of bits exchanged between the user and the k databases, but few about its lower bounds are known except for restricted cases. In this paper, we classify (k, l)=PIR into a linear type, a multilinear type, and an affine type with respect to the relationship between queries to each database (made by the user) and answers to the user (made by each database), and show that (1) the lower bound for the communication complexity of any multilinear type (k, l)-PIR is Ω([chemical formula])(Theorem 3.1);(2) the lower bound for the communication complexity of any linear type (k, l)-PIR is Ω(√<n>)(Corollary 3.2); (3) the lower bound for the communication complexity of any affine type (k, l)-PIR is Ω([chemical formula])(Theorem 4.2).

CiNii Books

researchmap
最小値独立置換族と3点独立置換族

伊東利哉

電子情報通信学会技術研究報告. COMP, コンピュテーション 100 ( 402 ) 49 - 56 2000年10月

　詳細を見る

記述言語：英語出版者・発行元：一般社団法人電子情報通信学会

最小値独立置換族は, インターネット上に存在する多数の類似した文書の特定に有用であることが知られている.任意の整数n0に対し, 集合{0, 1, ..., n-1}上の置換全体をS_nとするとき, 置換族F⊆S_nが最小値独立であるとは, 任意の(空でない)部分集合X⊆{0, 1, ..., n-1}と任意のx∈Xに対し, π∈Fを一様且つ無作為に選んだ場合, Pr_<π∈F>[min{π(X)}=π(X)]=∥X∥^<-1>が成り立つことを言う(ただし, ∥A∥は有限集合Aの要素数を表すものとする).一方, 任意の整数d≥1に対し, 置換族F⊆S_nがd点独立であるとは, 任意の異なるx_1, x_2, ..., x_d∈{0, 1, ..., n-1}と任意の異なるy_1, y_2, ..., y_d∈{0, 1, ..., n-1}に対し, π∈Fを一様且つ無作為に選んだ場合, Pr_<π∈F>[Λ^d_<i=1>π(x_i)=y_i]=1/{n(n-1)・・・(n-d+1)}が成り立つことを言い, d=2, 3に対してのみ、非自明な-対称群あるいは交代群とは異なる-d点独立置換族の構成法が知られている.これまでに, Broderらによって, 任意の2点独立置換族F⊆S_nの振舞は, 最小値独立置換族の振舞を概ね良好に近似する-任意のX⊆{0, 1, ..., n-1}と任意のx∈Xに対して, 3≤∥X∥=k≤n-2とすると, (下界)Pr_<π∈F>[min{π(X)}=π(x)]≥1/{2(k-1)};(上界)Pr_<π∈F>[min{π(X)}=π(x)]≤2/√<k>-3/(2k)-ことが示されている.本論文では, これを3点独立置換族に拡張し, 任意の3点独立置換族F⊆S_nの振舞は, 最小値独立置換族の振舞をより良好に近似する-任意のX⊆{0, 1, ..., n-1}と任意のx∈Xに対して, 4≤∥X∥=k≤n-3とすると, (下界)Pr_<π∈F>[min{π(X)}=π(x)]≥1/{2(k-2)}-1/{6(k-2)^2};(上界)Pr_<π∈F>[min{π(X)}]≤2/√<k>-2/k+1(3k√<k>)-ことを示す.

CiNii Books

researchmap
A-7-10 プライバシーを考慮した情報獲得の最近の動向

伊東利哉

電子情報通信学会ソサイエティ大会講演論文集 2000 168 - 168 2000年9月

　詳細を見る

記述言語：日本語出版者・発行元：一般社団法人電子情報通信学会

CiNii Books

researchmap
プライバシーを考慮した情報獲得プロトコルの通信量の下界

伊東利哉

電子情報通信学会技術研究報告. COMP, コンピュテーション 100 ( 52 ) 25 - 32 2000年5月

　詳細を見る

記述言語：英語出版者・発行元：一般社団法人電子情報通信学会

プライバシーを考慮したκ≥1個のデータベースからの情報獲得(Private) Information Retrieval with κ databases:(κ, l)-PIR)とは-(1)ユーザが互いに通信を行なわないκ個の同一データベースに対してl項組の質問を送信する;(2)各データベースはそれに対応する答えをユーザに送信する;(3)ユーザがデータベースに"どのデータを獲得したか"を一切漏らすことなく必要なデータを獲得する-ようなプロトコルのことを言う.このようなプロトコルにおいてその効率を評価する際に, ユーザとデータベース間の通信量が重要な意味を持つが, その下界については(極めて特殊な場合を除き)全く未解明である.そこで本論文では, ユーザのデータベースに対する質問とそれに対応するデータベースの答えの間の関係に注目し, (κ, l)-PIRを線形型・多重線形型・アフィン型に分類する.そして, それぞれの型に関して, (κ, l)-PIRの通信量の下界-(1)多重線形型(κ, l)-PIRの通信量の下界はΩ(^l+1√<n>)である(Theorem3.1);(2線形型)κ-PIRの通信量の下界はΩ(√<n>)である(Corollary3.2);(3)アフィン型(κ, l)-PIRの通信量の下界はΩ(^l+1√<n>)である(Theorem4.2)-を示す.

CiNii Books

researchmap
Approximating the Maximum Weight of Linear Codes APX-Complete

ITOH Toshiya

IEICE transactions on fundamentals of electronics, communications and computer sciences 83 ( 4 ) 606 - 613 2000年4月

　詳細を見る

記述言語：英語出版者・発行元：一般社団法人電子情報通信学会

The minimum distance of a linear code C is a useful metric property for estimating the error correction upper bound of C and the maximum likelihood decoding of a linear code C is also of practical importance and of theoretical interest. These problems are known to be NP-hard to approximate within any constant relative error to the optimum. As a problem related to the above, we consider the maximization problem MAX-WEIGHT: Given a generator matrix of a linear code C, find a codeword c &isinsv;C with its weight as close to the maximum weight of C as possible. It is shown that MAX-WEIGHT&notion;PTAS unless P=NP, however, no nontrivial approximation upper and lower bounds are known. In this paper, we investigate the complexity of MAX-WEIGHTto make the approximation upper and lower bounds more precise, adn show that (1) MAX-WEIGHTis APX-complete; (2) MAX-WEIGHTis approximable within relative error 1/2 to the optimum; (3) MAX-WEIGHTis not approximabler within relative error 1/10 to the optimum unless P=NP.

CiNii Books

researchmap
巡回セールスマン問題に対する近似の下界

平出涼, 伊東利哉

電子情報通信学会技術研究報告. COMP, コンピュテーション 99 ( 724 ) 41 - 48 2000年3月

　詳細を見る

記述言語：英語出版者・発行元：一般社団法人電子情報通信学会

任意の2点間の枝の重みに関して三角不等式が成り立つようなグラフ上の巡回セールスマン問題は, 代表的な組合せ最適化問題である.本稿では, その特殊な場合として, 任意の2点間の枝の重みが"1"または"2"に制限された巡回セールスマン問題(1, 2)-TSPについて考察する.実際, (1, 2)-TSPはNP完全であるので, その最適解(全ての点を一度ずつ通る最短閉路)を求めることはNP困難である.そこで(1, 2)-TSPを最小化問題MIN-(1, 2)-TSPとして定式化し, その近似解(全ての点を一度ずつ通る閉路)を求めることを考える.しかしMIN-(1, 2)-TSPはAPX完全であり, MIN-(1, 2)-TSPに関して, 非自明な近似の下界が存在する.最近Engebretsenは, 任意のε>0に対して-(1)無向MIN-(1, 2)-TSPを5381 / 5380-ε以内で近似するのはNP困難;(2)有向MIN-(1, 2)-TSPを2805 / 2804-ε以内で近似するのはNP困難-であることを示した.本稿ではこれらを改良し, 任意のε>0に対して-(Corollary 4.4)無向MIN-(1, 2)-TSPを1027 / 1026-ε以内で近似するのはNP困難;(Corollary 4.6)有向MIN-(1, 2)-TSPを535 / 534-ε以内で近似するのはNP困難-であることを示すとともに, 任意のε>0に対して, 最短超系列問題を2983 / 2982-ε以内で近似するのはNP困難(Corollary 5.3)であることを示す.

CiNii Books

researchmap
凸型資本投資問題に対するオンラインアルゴリズムの設計と解析

伊東利哉, 川上秀司

電子情報通信学会技術研究報告. COMP, コンピュテーション 99 ( 724 ) 33 - 40 2000年3月

　詳細を見る

記述言語：英語出版者・発行元：一般社団法人電子情報通信学会

工場で生産を行なう際に, 生産に必要な設備投資を行ない, その設備を用いて受注生産を開始するものとする.ただし, 設備の価格が高ければ高い程, その生産単価が安くなるものと仮定する.このような状況で, 投資効率を最大化する問題を"凸型資本投資問題"という.これまでに, Azarらにより凸型資本投資問題に対するオンラインアルゴリズムCONVEXが提案されており, その競争比が7であることが知られている.本論文では凸型資本投資問題に関して-(1)アルゴリズムCONVEXの競争比は4+2√<2>以下である(Theorem 3.2);(2)任意のε>0に対し, アルゴリズムCONVEXの競争比は4+2√<2>-ε以下である(Theorem 3.4);(3)任意のε>0に対し, 凸型資本投資問題の競争比は2-ε以上である(Theorem 4.1);(4)γ-制限された凸型資本投資問題に関して, アルゴリズムCONVEXの競争比は5+4 / (γ-4)以下である(Theorem 5.3);(5)任意のε>0に対し, γ-制限された凸型資本投資問題に関して, アルゴリズムCONVEXの競争比は5-ε以上である(Theorem 5.4)-を示す.(

CiNii Books

researchmap
最適な最小値独立置換族の構成

武井由智, 伊東利哉, 篠崎隆宏

電子情報通信学会技術研究報告. COMP, コンピュテーション 98 ( 432 ) 89 - 98 1999年11月

　詳細を見る

記述言語：英語出版者・発行元：一般社団法人電子情報通信学会

最小値独立置換族は, インターネット上に存在する多数の類似した文書の特定に有用であることが知られている.整数n>0に対し, 集合{1, 2, ..., n}上の置換族Cが最小値独立であるとは, 任意の(空でない)部分集合X⊆{1, 2, ..., n}と任意のx∈Xに対し, π∈Cを一様且つ無作為に選んだ場合, Pr{min{π(X)}=π(x)}=∥X∥^<-1>が成り立つことを言う.ただし, ∥A∥は有限集合Aの要素数を表すものとする.これまでに, 集合{1, 2, ..., n}上の最小値独立置換族に関して, 以下の結果-(1)任意の最小値独立置換族Cに対して, ∥C∥>1cm(n, n-1, ..., 2, 1)=e^<n-o(n)>;(2)∥C∥<4^nとなるような最小値独立置換族Cが存在する-が知られているが, ∥C∥=1cm(n, n-1, ..., 2, 1)を満たす最小値独立置換族Cの存在さらにその構成法は未解決であった.本論文では, 全ての整数n>0に対し, ∥F_n∥=1cm(n, n-1, ..., 2, 1)を満たす極小な最小値独立置換族F_nの構成法を与え, その詳細な解析を行なう.

CiNii Books

researchmap
線形符号の最大重みに対する近似アルゴリズム

伊東利哉

電子情報通信学会技術研究報告. IT, 情報理論 99 ( 56 ) 1 - 8 1999年5月

　詳細を見る

記述言語：英語出版者・発行元：一般社団法人電子情報通信学会

線形符号Cが与えられたとき, その最小距離を求める問題は, 符号Cの誤り訂正の限界を知る上で重要である. また, 線形符号C⊆{0, 1}^nとy∈{o, 1}^nが与えられたとき, ベクトルyに最も近い符号語c∈Cを求める問題(最尤復号)は, 符号Cの性能を最大限利用する意味でも応用上極めて重要である. しかし, これら問題はNP-困難であることが知られており, P≠NPである限り, これらに対する効率的なアルゴリズムは存在しない. 本論文では, これらに関連する問題として, 線形符号Cに対する"最大重み:MAX-WEIGHT"について考察する. 最大重みに対して, これまでにMAX-WEIGHT notin PTASが知られているものの, その近似に関する非自明な上界・下界は知られていない. 従って, 本論文では, MAX-WEIGHTの計算量的な位置付け(1) MAX-WEIGHTはAPX完全である. (2) MAX-WEIGHTは2-近似可能である; (3) P bne NPの仮定のもとでMAX- WEIGHT は(10/9)-近似不可能である-を示す.

CiNii Books

researchmap
A Characterization of Min-Wise Independent Permutations Families (Models of Computation and Algorithms)

武井由智, 伊東利哉

数理解析研究所講究録 1093 68 - 73 1999年4月

　詳細を見る

記述言語：英語出版者・発行元：京都大学

CiNii Books

researchmap
A Polynomial Time Sampling Algorithm for an Optimal Family of Min-Wise Independent Permutations (Models of Computation and Algorithms)

篠崎隆宏, 伊東利哉

数理解析研究所講究録 1093 74 - 80 1999年4月

　詳細を見る

記述言語：英語出版者・発行元：京都大学

CiNii Books

researchmap
Efficient Private Information Retrieval

ITOH Toshiya

IEICE transactions on fundamentals of electronics, communications and computer sciences 82 ( 1 ) 11 - 20 1999年1月

　詳細を見る

記述言語：英語出版者・発行元：一般社団法人電子情報通信学会

Informally, private information retrieval for k≧1 databases (k-PIR) is an interactive scheme that enables a user to make access to (separated) k replicated copies of a database and privately retrieve any single bit out of the n bits of data stored in the database. In this model, "privacy" implies that the user retrieves the bit he is interested in but releases to each database nothing about which bit he really tries to get. Chor et.al. proposed 2-PIR with communication complexity 12n^<1/3>+2 that is based on the covering codes. Then Ambainis recursively extended the scheme by Chor et. al. and showed that for each k≧2, there exists k-PIR with communication complexity at most c_k・n^<1/(2k-1)> some constant c_k>0. In this paper, we relax the condition for the covering codes and present time-efficient 2-PIR with communication complexity 12n^<1/3>. In addition, we generally formulate the recursive scheme by Ambainis and show that for each k≧4, there exists k-PIR witla communication complexity at most c'_k・n^<1/(2k-1)> for some constant c'_k≪c_k.

CiNii Books

researchmap
RSA暗号の安全性に基づくID-NIKSの安全性について

伊東利哉

電子情報通信学会技術研究報告. ISEC, 情報セキュリティ 98 ( 228 ) 1 - 10 1998年7月

　詳細を見る

記述言語：英語出版者・発行元：一般社団法人電子情報通信学会

大規模ネットワークにおいて暗号通信を行なう場合, 各ユーザの鍵管理は極めて重要な問題となる.これを軽減する有力な方法として, 各ユーザの個人識別情報をそのユーザの公開鍵として用いる"個人識別情報に基づく"公開鍵暗号方式(あるいは公開鍵共有方式:ID-NIKSが知られている.これまでに数々のID-NIKSが提案されているが, 残念ながらその殆んどは何人かのユーザの結託による攻撃が可能であることが示されている.最近, 村上らはRSA暗号に基づく新しいID-NIKSを提案し, その安全性の解析を行なっている.本論文では, 村上らによるID-NIKSを詳細に解析し, 結託による攻撃-(1)任意の単一ユーザによるセンターの公開する合成数の因数分解;(2)適当な3人のユーザの結託による特定の第三者に対するなりすまし;(3)n人のユーザの結託による任意の第三者に対するなりすまし;(4)n人のユーザの結託によるセンターの秘密鍵の導出-が可能であることを示す.

CiNii Books

researchmap
プライバシーを考慮した効率的な情報獲得

伊東利哉

電子情報通信学会技術研究報告. ISEC, 情報セキュリティ 98 ( 48 ) 49 - 60 1998年5月

　詳細を見る

記述言語：英語出版者・発行元：一般社団法人電子情報通信学会

プライバシーを考慮したk(&ges;1)個のデータベースからの情報獲得(Private Information Retrieval with k databases: k-PIR)とは, 以下のような手法のことを言う:(1)ユーザが互いに通信を行なわないk個の同一データベースにアクセスし;(2)ユーザがデータベースに"どのデータを獲得したか"を一切漏らすことなく必要なデータを獲得する.このような手法においてその効率を評価する際に, ユーザとデータベース間の通信量と時間計算量が重要な意味を持つ.これまでに, Chorらは被覆符合の概念を導入することにより, 通信量12n^<1/3>+2の2-PIRを提案している(ただしnはデータベースに保存されている全データのビット長を表すものとする).一方, AmbainisはChorらの方法を再帰的に拡張し, 全てのk&ges;2に対して, 高々通信量c_k・n^<1/(2k-1)>のk-PIRを提案している.本研究では, 被覆符合の条件を緩和することにより, Chorらの方法に比べ時間計算量の少ない通信量12n^<1/3>の2-PIRを提案する.また本論文では, Ambainisの再帰的構成法を一般的に定式化し, その最適化を行うことによって, 全てのk&ges;4に対して, 高々通信量c^l_k・n^<1/(2k-1)>のk-PIR(ただしc^l_k≪c_k)を提案する.

CiNii Books

researchmap
非線形符号の半径及び被覆半径に対する近似アルゴリズム

伊東利哉

電子情報通信学会技術研究報告. ISEC, 情報セキュリティ 97 ( 612 ) 103 - 114 1998年3月

　詳細を見る

記述言語：英語出版者・発行元：一般社団法人電子情報通信学会

符号の性能評価において重要な(幾何学的)量である被覆半径及び半径を求める問題の複雑さについて検討する.これまでに, (適当な定式化のもとで)これらの問題は極めて困難であることが知られている.実際, 線形符号が生成行列で与えられるとき, その半径及び被覆半径を求める問題はΣ^p_<2->完全であることが示されており, また, (ある種の)非線形符号がその符号語の全体で与えられるとき, その半径及び被覆半径を求める問題はNP-完全であることが示されている.そこで, 本研究では, まずこれらの問題を"最小化問題"として定式化し, それに対する近似解を求めることについて考察する.そして, P≠NPという仮定のもとで, ある種の非線形符号に関しては, いかなる定数に対しても, 半径及び被覆半径の値をその最適解の定数倍以下で求める多項式時間アルゴリズムは存在しないことを示す.

CiNii Books

researchmap
On the Oracle Entropy and the Average Case Oracle Measure of Knowledge Complexity

ITOH Toshiya

IEICE transactions on fundamentals of electronics, communications and computer sciences 80 ( 1 ) 90 - 97 1997年1月

　詳細を見る

記述言語：英語出版者・発行元：一般社団法人電子情報通信学会

In this paper, we investigate statistical and perfect Knowledge Complexity (KC) with respect to oracle entropy and average case oracle measures. As main results, we show the following: (1) for any k(n) ≧1/poly(n), if a language L has perfect KC k(n) + n^<-ω(1)> with respect to oracle entropy measure, then L has perfect KC k(n) with respect to oracle entropy measure (Theorem 3.1); (2) for any k(n) ≧1/poly(n), if a language L has perfect KC k(n) + n^<-ω(1)> with respect to average case oracle measure, then L has perfect KC k(n) with respect to average case oracle measure (Theorem 3.2); (3) if a language L has statistical KC k(n) ∈ o(1) with respect to oracle entropy measure, then for any ε> 0, L has statistical KC k(n) + 1 +ε with respect to average case oracle measure (Theorem 4.1); and (4) if a language L has perfect KC k(n) ∈ o(1) with respect to oracle entropy measure, then for any ε > 0, L has perfect KC k(n) + 2 + ε with respect to average case oracle measure (Theorem 4.2).

CiNii Books

researchmap
自己検査器及び自己修正器の関係について

森啓悦, 伊東利哉

電子情報通信学会技術研究報告. ISEC, 情報セキュリティ 95 ( 240 ) 75 - 86 1995年9月

　詳細を見る

記述言語：英語出版者・発行元：一般社団法人電子情報通信学会

ある関数fを計算するプログラムP_fを書いたとき「そのP_fが正しくfを計算していることを如何にして保証するか?」という問題は,工学上重要であるとともに,理論上極めて困難な問題であることが知られている.この問題に対して,プログラムの正当性を確率的に検証する方法として,検証器・自己検査器・自己修正器が知られている.本研究では,新たな概念として"自己修復器"を提案し,検証器・自己検査器・自己修正器が構成可能となような関数の特長付けを目的に,組合せ論及び計算量理論の議論を通じて,以下の結果-(1)一方向性置換が存在するとき,検証器は構成可能であるが,自己修正器は構成不可能であるような関数が存在すること;(2)自己検査器/修正器対から,高性能な自己検査器が構成可能であること;(3)自己検査器/修正器対から,高性能な自己修復器が構成可能であること-を示す.

CiNii Books

researchmap
統計的及び完全な知識の複雑さについて

伊東利哉

電子情報通信学会技術研究報告. ISEC, 情報セキュリティ 95 ( 172 ) 1 - 17 1995年7月

　詳細を見る

記述言語：英語出版者・発行元：一般社団法人電子情報通信学会

本稿では,対話型証明及び暗号プロトコルの安全性を議論する上で,重要な意味を持つ知識の複雑さ(Knowledge Complexity: KC)の尺度-Oracle Entropy及びAverage Case Oracle-について考察を行なう.そして主要結果として-(1)k(n)≥1/poly(n)であるとき,Oracle Entropyの尺度のもとで完全な知識の複雑さk(n)+n^<-w(1)>を持つ言語は,Oracle Entropyの尺度のもとで完全な知識の複雑さk(n)を持つこと;(2)k(n)≥poly(n)であるとき,Average Case Oracleの尺度のもとで完全な知識の複雑さk(n)^<-w(1)>を持つ言語は,Average Case Oracleの尺度のもとで完全な知識の複雑さk(n)を持つこと;(3)Oracle Entropyの尺度のもとで統計的な知識の複雑さk(n)∈o(1)を持つ言語は,任意のε>0に対しAverage Case Oracleの尺度のもとで統計的な知識の複雑さk(n)+1+εを持つこと,(4)Oracle Entropyの尺度のもとで完全な知識の複雑さk(n)∈o(1)を持つ言語は,任意のε>0に対しAverage CaseOracleの尺度のもとで完全な知識の複雑さk(n)+2+εを持つこと-を示す.

CiNii Books

researchmap
Alternative Necessary and Sufficient Conditions for Collision Intractable Hashing

ITOH Toshiya, HAYASHI Kei

IEICE transactions on fundamentals of electronics, communications and computer sciences 78 ( 1 ) 19 - 26 1995年1月

　詳細を見る

記述言語：英語出版者・発行元：一般社団法人電子情報通信学会

Damgard defined the notion of a collision intractable hash functions and showed that there exists a collection of collision intractable hash functions if there exists a collection of claw-free permutation pairs. For a long time, the necessary and sufficient condition for the existence of a collection of collision intractable hash functions has not been known, however, very recently Russell finally showed that there exists a collection of collision intractable hash functions iff there exists a collection of claw-free pseudo-permutation pairs. In this paper, we show an alternative necessary and sufficient condition for the existence of a collection of collision intractable hash functions, i.e., there exists a collection of collision intractable hash functions iff there exists a collection of distinction intractable pseudo-permutations.

CiNii Books

researchmap
言語に依存した安全なビット・コミットメント

伊東利哉, 太田雄士, 静谷啓樹

電子情報通信学会技術研究報告. ISEC, 情報セキュリティ 94 ( 137 ) 11 - 22 1994年7月

　詳細を見る

記述言語：英語出版者・発行元：一般社団法人電子情報通信学会

本稿では2種類の言語のクラスを定義する.その第一は,不透明, 透明な性質を持つビット・コミットメントを誘導する言語のクラスであり,その第二は,透明/不透明な性質を持つビット・コミットメントを誘導する言語のクラスである.またこの応用として-(1)言語Lが不透明/透明な性質を持つビット・コミットメントを誘導するならば,その言語Lは完全零知識証明を持つ;(2)言語Lが透明/不透明な性質を持つビット・コミットメントを誘導するならば,その言語Lは対話制限された完全零知識証明を持つ-を示す.

CiNii Books

researchmap
On checkers, Self-Testers, and Self-Debuggers

森啓悦, 伊東利哉

数理解析研究所講究録 871 138 - 144 1994年5月

　詳細を見る

記述言語：英語出版者・発行元：京都大学

CiNii Books

researchmap
Simulating Fair Dice with a Small Set of Rationally Biased Coins

伊東利哉, 望月貴裕

数理解析研究所講究録 871 130 - 137 1994年5月

　詳細を見る

記述言語：英語出版者・発行元：京都大学

CiNii Books

researchmap
Demonstrating Possession without Revealing Factors (Special Section on Cryptography and Information Security)

Shizuya Hiroki, Koyama Kenji, Itoh Toshiya

IEICE transactions on fundamentals of electronics, communications and computer sciences 77 ( 1 ) 39 - 46 1994年1月

　詳細を見る

記述言語：英語出版者・発行元：一般社団法人電子情報通信学会

This paper presents a zero-knowledge interactive protocol that demonstrates two factors a and b of a composite number n (=ab) are really known by the prover, without revealing the factors themselves. Here the factors a and b need not be primes. The security of the protocol is based on the difficulty of computing discrete logarithms modulo a large prime.

CiNii Books

researchmap
A Note on AM Languages Outside NP &xcup; co-NP (Special Section on Cryptography and Information Security)

Shizuya Hiroki, Itoh Toshiya

IEICE transactions on fundamentals of electronics, communications and computer sciences 77 ( 1 ) 65 - 71 1994年1月

　詳細を見る

記述言語：英語出版者・発行元：一般社団法人電子情報通信学会

In this paper we investigate the AM languages that seem to be located outside NP &xcup; co-NP. We give two natural examples of such AM languages, GIP and GH, which stand for Graph Isomorphism Pattern and Graph Heterogeneity, respectively. We show that the GIP is in &xutri;^2&xcap; AM &xcap; co-AM but is unlikely to be in NP &xcup; co-NP, and that GH is in &xutri;^2&xcap; AM but is unlikely to be in NP &xcup; co-AM. We also show that GIP is in SZK. We then discuss some structural properties related to those

CiNii Books

researchmap
Crypto報告

伊東利哉

電子情報通信学会技術研究報告. ISEC, 情報セキュリティ 93 ( 208 ) 83 - 86 1993年8月

　詳細を見る

記述言語：英語出版者・発行元：一般社団法人電子情報通信学会

Crypto'93について報告する

CiNii Books

researchmap
簡便なハッシュ関数族の構成法

伊東利哉, 武田真

電子情報通信学会論文誌. A, 基礎・境界 76 ( 6 ) 844 - 849 1993年6月

　詳細を見る

記述言語：日本語出版者・発行元：一般社団法人電子情報通信学会

計算機ネットワークにおいて意図的なデータの書換えを防止することは,信頼性の高いシステム設計・運用の意味からも極めて重要である.これを実現する一つの方法として一方向性ハッシュ関数族を利用することの有効性が指摘されている.一方向性ハッシュ関数族は,UOHF(universal oneway hash function family)とCIHF(collision intractable hash function family)の二つに分類される.UOHFについてはこれまでに多くの理論的成果が知られているが,CIHFに関しては十分な理論的な解明がなされていないのが現状である.そこで本論文では,CIHFの構成に関してこれまでとは全く異なった観点から検討する.そして,素因数分解の困難さに基づいた簡便なCIHFの具体的な構成法を提示し,その有効性・意義等について考察する.

CiNii Books

researchmap
数論アルゴリズムとその応用：有限体上のアルゴリズムと多倍長・剰余演算の高速演算法

伊東利哉, 佐古和恵

情報処理 34 ( 2 ) 170 - 179 1993年2月

　詳細を見る

記述言語：日本語出版者・発行元：一般社団法人情報処理学会

CiNii Books

researchmap

その他リンク： http://id.nii.ac.jp/1001/00004334/
On the Complexity of Composite Numbers (Special Section on Cryptography and Information Security)

Itoh Toshiya, Horikawa Kenji

IEICE transactions on fundamentals of electronics, communications and computer sciences 76 ( 1 ) 23 - 30 1993年1月

　詳細を見る

記述言語：英語出版者・発行元：一般社団法人電子情報通信学会

Given an integer N, it is easy to determine whether or not N is prime, because a set of primes is in ZPP. Then given a composite number N, is it easy to determine whether or not N is of a specified form? In this paper, we consider a subset of odd composite numbers +1MOD4 (resp. +3MOD4), which is a subset of odd composite numbers consisting of prime factors congruent to 1 (resp. 3) modulo 4, and show that (1) there exists a four move (blackbox simulation) perfect ZKIP for the complement of +1MOD4 without any unproven assumption; (2) there exists a five move (blackbox simulation) perfect ZKIP for +1MOD4 without any unproven assumption; (3) there exists a four move (blackbox simulation) perfect ZKIP for +3MOD4 without any unproven assumption; and (4) there exists a five move (blackbox simulation) statistical ZKIP for the complement of +3MOD4 without any unproven assumption. To the best of our knowledge, these are the first results for a language L that seems to be not random self-reducible but has a constant move blackbox simulation perfect or statistical ZKIP for L and L^^-without any unproven assumption.

CiNii Books

researchmap
ゼロ知識証明とその応用：ゼロ知識証明モデルと計算量理論

静谷啓樹, 伊東利哉, 桜井幸一

情報処理 32 ( 6 ) p673 - 681 1991年6月

　詳細を見る

記述言語：日本語出版者・発行元：一般社団法人情報処理学会

CiNii Books

researchmap

その他リンク： http://id.nii.ac.jp/1001/00004661/
修正された選択離散対数問題の難しさについて

伊東利哉, 細川知巳

電子情報通信学会論文誌. A, 基礎・境界 75 ( 4 ) 801 - 805 1991年4月

　詳細を見る

記述言語：日本語出版者・発行元：電子情報通信学会基礎・境界ソサイエティ

CiNii Books

researchmap
MODIFIED ID-BASED CRYPTOSYSTEM USING DISCRETE LOGARITHM PROBLEM - COMMENT

S TSUJII, T ITOH, H TANAKA

ELECTRONICS LETTERS 25 ( 1 ) 77 - 78 1989年1月

　詳細を見る

記述言語：英語

Web of Science

researchmap
有限体上の2次方程式を解く効率的な確率的アルゴリズム

伊東利哉

電子情報通信学会論文誌 A 基礎・境界 71 ( 1 ) p95 - 101 1988年1月

　詳細を見る

記述言語：日本語出版者・発行元：電子情報通信学会基礎・境界ソサイエティ

CiNii Books

researchmap

▼全件表示

共同研究・競争的資金等の研究課題

最小記述量の計算困難さの解析

研究課題/領域番号：18H04090 2018年4月 - 2022年3月

日本学術振興会科学研究費助成事業基盤研究(A)

渡辺治, 伊東利哉, 天野一幸, 玉置卓, 森立平, 平原秀一, 清水伸高

　詳細を見る

配分額：38480000円（直接経費：29600000円、間接経費：8880000円）

これまでの研究の中から最小記述量計算問題の計算困難さに関連する様々な結果が出始めてきたが，本年度は，それをさらに進めて，最小記述量計算問題をコルモゴロフ記述量ならびに機械学習可能性（正確にはPAC学習複雑度）と関連付け，それにより，NP問題全般（あるいはもう少し広い多項式時間階層，クラスPH）の平均時複雑度へ関連付ける研究を進めた。その中で得られた結果のうちで主要なものを以下に述べる。
１．多項式時間階層クラスPHの平均時計算複雑度を小記述長問題の最悪時計算複雑度により特徴づけることに成功した。その結果として，PHに対する困難性増幅定理を得た。たとえば，PHの代表的な問題に対して，その1%の入力が効率的に解けることとPHのすべての問題に対して，その99%の入力が効率的に解けることが同値であることがわかった。
２．PHの最悪時計算複雑度を平均時計算複雑度に結び付ける重要な手法の一つに，PHの最悪時計算困難性をもとに計算論的暗号素（computationally secure cryptographic primitive）を作り出す手法が考えられる。しかし，そのような手法は，通常の計算論的解析（より正確には，black-box的な並列乱択還元を用いた解析）では不可能であることを示した。その証明においては，PHの構造的困難さ（より正確には密でない集合への還元可能性）について，既存の特徴づけを大幅に改良する特徴づけを与える技法を開発した。
３．従来の学習の枠組みならびに暗号の枠組みを拡張することにより，（その枠組みの上での）PAC学習困難性と計算論的暗号素の構成可能性間の同値性を示すことができた。なお，これは本研究課題でRAとして雇用している博士課程学生の独自研究である。
４．3SAT問題に対して，指数関数時間ではあるが（その時点での）世界最速の乱択アルゴリズムを得た。

researchmap
統計力学からの計算限界解明へのアプローチ

研究課題/領域番号：24106008 2012年6月 - 2017年3月

日本学術振興会科学研究費助成事業新学術領域研究(研究領域提案型)

渡辺治, 安藤映, 伊東利哉, 小柴健史, 山本真基, 森立平, 樺島祥介, 福島孝治

　詳細を見る

配分額：81120000円（直接経費：62400000円、間接経費：18720000円）

統計力学的な観点で提案されてきた計算の解析手法や計算に関する問題について，計算論的な観点から検討を行った。その結果，問題例の計算困難さの変化に関して，これまでの枠組みでは捉えられていなかった困難さの変化を明らにすることに成功し，計算困難さの変化を研究するための新しい，より頑健な枠組みを提案した。この結果は，暗号の安全性の基礎にもなる。一方，解の構造の特徴付けや，解の数え上げ問題など，統計力学の基本問題に関しても，効率的アルゴリズムの開発や，その基礎となる知見を得ることができた。

researchmap
代教的および確率的手法による離散構造の限界の究明

研究課題/領域番号：16092205 2004年 - 2007年

日本学術振興会科学研究費助成事業特定領域研究

伊東利哉, 上野修一

　詳細を見る

配分額：13800000円（直接経費：13800000円）

本研究では、代数的手法および確率的手法を用いて、置換族の構成、電子商取引、 VLSI計算、可逆計算、および耐故障計算などに関する離散構造の限界を解明した、置換族の構成に関しては、電子文書間の高速な類似性ツールとして応用が知られているκ限定ε近似的最小値独立置換族Fに対して、一般分布上で定義される置換族Fを行列Uにより定式化し、その行列Uの階数を評価することにより置換族Fのサイズの良好な下界を導出した。電子商取引に関しては、最適選好マッチング問題において、顧客集合が複数の重み付きグループに分割されているとき、顧客数n商品数mの比に関して、乱択化最適選好マッチングが存在するためのほほ合致する上界と下界を導出した(これは、既に知られている顧客集合が1つグループである場合の乱択化最適選好マッチングが存在するための顧客数nと商品数mの比に関する上界・下界の拡張である)。まだ、商品価格設定問題に関しては、正価格モデルおよび無損失割引モデルにおいて見積価格が制限された場合に対して、確率的手法を用いることで,グラフ価格設定問題・線状高速道路問題・環状高速道路問題の良好な近似アルゴリズムを提案した。VLSI計算に関しては、3次元チャネル配線問題がNP困難であることを明らかにした。可逆計算に関しては、可逆回路の縮退故障に対する最小完全テスト集合生成問題がNP困難であることを示した。耐故障計算に関しては、様々なネットワークに対して効率的な確率的耐故障ネットワークを構成する統一的な手法を提案した。

researchmap
零知識証明を用いた分散認証システムの研究開発

研究課題/領域番号：15300015 2003年 - 2005年

日本学術振興会科学研究費助成事業基盤研究(B)

伊東利哉, 山岡克式, 角田貢

　詳細を見る

配分額：16300000円（直接経費：16300000円）

ネットワークを利用して様々なサービスを行うためには,個人の特定を行いながらも,それぞれの個人ユーザーが属するグループ単位での承認も行えるような分散認証システムが,必要である,この承認は,認証によって,利用者を識別し,ネットワークリソースの利用権を与えることである.
本研究では,零知識証明を用いて上記の承認を行える分散認証法について検討を行った.まず,公開鍵暗号によるシステムと零知識証明によるシステムの提案を行った.そして,零知識証明及び公開鍵暗号のそれぞれに基づいたシステムの設計を行った,更に,これら2つによるシステムについて,セキュリティレベル,時間計算量,空間計算量,通信量の観点から比較検討を行った.実験結果から,零知識証明によるシステムは,公開鍵によるものと比較して,計算時間による影響が大きいため,通信のビットレートが小さい場合には有利であると言えないが,通信のビットレートが大きい場合には通信時間の影響が小さくなるため有利であるという知見が得られた.今後,計算時間については,コンピュータの性能向上に伴い鍵長が増大するため,推奨される鍵長を用いて暗号化を行う時間は将来においてもそれ程変化しないと予想されるのに対して,通信時間については,ネットワークの高速化に伴い,将来,小さくなることが見込まれるため,零知識証明によるシステムが優位にあるという結論を得た.

researchmap
フレキシブルな暗号システムの研究

研究課題/領域番号：11694140 1999年 - 2000年

日本学術振興会科学研究費助成事業基盤研究(B)

多田充, 櫻井幸一, 伊東利哉, 篠田陽一

　詳細を見る

配分額：5700000円（直接経費：5700000円）

本研究では、閾値秘密分散法において1度構築したシステムを再編することなしに、パラメータである閾値およびメンバ数、さらに秘密情報を効率的かつ安全に更新する方式を提案した。田村らとの共同研究で提案した手法においては、パラメータの変更前、変更後のシステムはともに完全な安全性をもつ。しかし、システムの初期設定において安全な通信路を使って分散情報保持者に送る情報量が多くなる。前田らとの共同研究では、変更後のシステムの完全な安全性は犠牲にするが、安全な通信路を使って送る情報量を削減できる閾値変更可能秘密分散法を提案し、さらにその方式を検証可能にした。
岡本らとの共同研究では、「岡本-田中鍵共有方式(OT方式)」において、効率的にメンバの秘密情報を更新できるシステムを提案し、安全性の評価を行った。またKimらとの共同研究では、OT方式の様々な種類の能動的攻撃に対する安全性を評価した。
多重署名方式において、署名だけでなくその付加的な情報も検証できる多重署名方式を「機能付き多重署名」と呼ぶことにする。Burmesterらとの共同研究では、署名者および署名順序を検証できる機能付き多重署名として「順序付き多重署名」を提案し、その安全性を評価した。湊らとの共同研究では、署名者および、文書に対する「賛成/反対」などの署名者の意思を検証できる機能付き多重署名として「意思付き多重署名方式」を提案し、その安全性を評価した。
小出らとの共同研究では、電子現金方式に関する研究を行った。その方式においては、発行機関である銀行の秘密鍵が漏洩しても、正当な電子現金と漏洩した秘密鍵によって偽造された電子現金を識別することができる。

researchmap
プログラムの正当性の確率的検証法に関する基礎的研究

研究課題/領域番号：07650457 1995年

日本学術振興会科学研究費助成事業一般研究(C)

伊東利哉

　詳細を見る

配分額：1600000円（直接経費：1600000円）

これまでにchecker,self-tester及びself-correctorに関して-(1)関数fがcheckerを持つならば,任意の0<δ【less than or equal】1に対してfは(1,δ)-self-testerを持つ;(2)任意の0【less than or equal】ε_1<ε_2【less than or equal】ε【less than or equal】1に対して,関数fが(ε_1,ε_2)-self-testerとε-self-correctorを持つならば,任意の0<δ【less than or equal】1に対してfは(0,δ)-self-testerを持つ-が知られている.関数fに対して(ε_1,ε_2)-self-testerを設計する際に-(a)要求されるプログラム品質に応じてε_1は任意の設定できること;(b)self-testerの信頼性の意味から|ε_1-ε_2|はできるだけ小さな値をとるいこと-が実用上重要である.従って上記の結果(2)は,δ【similar or equal】0とすることで要求事項(b)は満たすが,本質的に要求事項(a)は満たしていないことが分かる.
そこで本研究では,先ず上記の結果(1)に関連して「関数fがcheckerを持つならば,任意の0<ε【less than or equal】1に対してfはε-self-correctorを持つか?」という問題を提起し,以下のような
主要結果1:一方向性置換が存在するならば,checkerを持つが,任意の0<ε【less than or equal】1に対してε-self-correctorを持たないような関数f
次に要求事項(a)及び(b)を満たすようなself-testerの構成法を確立するために,“self-improver"という新しい概念を提案し,それに基づいて以下のような結果を導出した.
主要結果2:任意の0<ε´_1<ε´_2【less than or equal】ε´<1に対して,関数fが(ε´_1,ε´_2)-self-testerとε´-self-correctorを持つならば,ε_1【less than or equal】ε´を満たす任意の0<ε_1<ε_2【less than or equal】1に対して,fは(ε_1,ε_2)-self-testerを持つ,
主要結果3:任意の0<ε´_1<ε´_2【less than or equal】ε´<1に対して,関数fが(ε´_1,ε´_2)-self-testerとε´-self-correctorを持つならば,δ【less than or equal】ε´を満たす任意のδ>0に対して,fは(ε´,δ)-self-improverを持つ.

researchmap
プログラム・チェッカーに関する基礎的研究

研究課題/領域番号：06650440 1994年

日本学術振興会科学研究費助成事業一般研究(C)

伊東利哉

　詳細を見る

配分額：1200000円（直接経費：1200000円）

静的なプログラム・チェッカーが構成可能な関数fのクラスは,"関数制限対話型証明"を用いることで特徴付られることが知られている.この特徴付けは,関数fに対するプログラムP_fが静的に動作するという条件に強く依存しており,同様な方法でこれを動的なプログラム・チェッカーが構成可能な関数fのクラスの特徴付けに拡張することは極めて困難である.
そこで我々は,動的なプログラム・チェッカーが構成可能な関数のクラスを特徴付けるために,(1)最も自然な計算モデルとして"競合的対話型証明"を取り上げ;(2)競合的対話型証明を"関数型"競合的対話型証明に変換する手法-より具体的には,競合的対話型証明における証明者が言語Lに問い合わせる質問を検証者に代行させ,証明者は言語Lの所属問題のみに対してその解を返すというプロトコル変化-を開発した.そしてこの関数型競合的対話型証明を用いることで,動的なプログラム・チェッカーが構成可能な言語Lのクラスは,言語Lとその補言語L^^-がともに関数型競合的対話型証明を持つことであることを明らかにした.
ここで,静的なプログラム・チェッカーを持つことが動的なプログラム・チェッカーを持たない関数fの存在が考えられることから,そのような関数fに対して動的なプログラム・チェッカーが構成可能となるような新しい計算モデル-関数fに対する動的なプログラムP_fのコピーをk【greater than or equal】2個用意し,関数fに対するプログラム・チェッカーC_fがそのk【greater than or equal】2個のプログラムP_fをサブルーチンとする-を導入した.そしてこのモデル上で,動的なプログラム・チェッカーが構成可能な言語のクラスの特徴付け-(3)全ての静的なプログラム・チェッカーが構成可能な言語に対して,k【greater than or equal】2個のプログラムを持つ動的なプログラム・チェッカーが構成可能であること;(4)関数fに対し,k【greater than or equal】2個のプログラムを持つ動的なプログラム・チェッカーC_f存在するならば,2個のプログラムを持つ動的なプログラム・チェッカーC'_fが存在すること-を与え,上記のモデルの

researchmap
ID情報を公開鍵とする新しい暗号通信方式に関する研究

研究課題/領域番号：63550246 1988年

日本学術振興会科学研究費助成事業一般研究(C)

辻井重男, 伊東利哉, 植松友彦

　詳細を見る

配分額：2100000円（直接経費：2100000円）

申請者らが提案しているID情報を公開鍵とする暗号通信方式に関して、その信頼性について詳細な検討を行うとともに、その信頼性の向上及び処理速度の高速化について考察した。
申請者らが提案しているID情報を公開鍵とする暗号通信方式は、有限体GF(P)上で構成されるEl-Gamalの公開鍵暗号方式に基づいて構成される。まず、信頼できるセンターを仮定する。センターはセンター秘密〓を生成し、各エンティティ、IDに対応し、そのエンティティの秘密鍵Sを生成し秘密に配送する。また、センターはセンター秘密〓より、gai(modP)(g:GF^*(p)の生成元)をシステム全体に公開する。以下、各エンティティはセンターと通信することなく、任意のエンティティに対して、El-Gamalの公開鍵暗号方式を用いて暗号通信をすることができる。
ID情報を公開鍵とする暗号方式の場合、センターの秘密情報が各エンティティに配付されているため、複数のエンティティが結託し、各々の秘密鍵からセンターの秘密情報を算出することが可能となる場合がある。この点に関し、本システムはエンティティの結託に対し有限のしきい値があることが今回の検討で明らかになった。一方、本システムを整数環Zn(N=pq,p,q:素数)上で構成する方式を提案し、その信頼性を検討した結果、若干そのしきい値が向上することが明らかとなった。さらに、局番概念を導入することで、そのしきい値が局番数に比例して増加すること、また同時に、処理速度の高速化が可能となること等が明らかとなった。

researchmap
ID情報を公開鍵とする新しい暗号通信方式に関する研究

研究課題/領域番号：62550236 1987年

日本学術振興会科学研究費助成事業一般研究(C)

辻井重男, 伊東利哉, 植松友彦

　詳細を見る

配分額：1900000円（直接経費：1900000円）

申請者らが提案しているID情報と公開鍵とする暗号通信方式に関して, その信頼性について詳細な検討を行うとともに, その信頼性の向上及び処理速度の高速化について考察した.
申請者らが提案しているID情報を公開鍵とする暗号通信方式は, 有限体GF(P)上で構成されるElgamalの公開鍵暗号方式に基づいて構成される. まず, 信頼できるセンターを仮定する. センターはセンタ秘密aを生成し, 各エンティティのIDに対応し, そのエンティティの秘密鍵Sを隠密に配送する. またセンターはセンター秘密aからg^<ai>(modP)(g:GF(P)の原始根)をシステム全体に公開する. 以下, 各エンティティはセンターと通信することなく, 任意のエンティティとElGamalの公開鍵暗号方式を用いて, 暗号通信をすることができる.
ID情報を公開鍵とする暗号通信方式の場合, センターa秘密情報が各エンティティに配付されているため, 数エンティティが結託し, 各々の秘密鍵からセンターの秘密情報を算出することが可能となる場合がある. この点に関し, 本システムはエンティティの結託に対し有限のしきい値があることが今回の検討で明らかになった. これに対し, 本システムを整数環Z_NCN=Pg, Pg:素数)上で構成する方式を提案し, その信頼性を検討した結果, 若干そのしきい値が向上することが明らかとなった. さらに, 局番の概念を導入することで, そのしきい値が局番数に比例して増加すること, また同時に処理速度の高速化が可能となること等が明らかとなった.

researchmap

▼全件表示

その他

関心のあるテーマ [3]

　詳細を見る

private information retrieval protocols

researchmap
関心のあるテーマ [1]

　詳細を見る

popular matchings

researchmap
関心のあるテーマ [2]

　詳細を見る

min-wise independent permutations

researchmap
関心のあるテーマ [4]

　詳細を見る

locally decodable codes

researchmap
関心のあるテーマ [5]

　詳細を見る

online algorithms

researchmap