著者

トム アルトマン 五十嵐 善英 小保方 幸次

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション

巻号頁・発行日

vol.93, no.123, pp.9-18, 1993-06-25

---

グラフG=(V,E)が,V={0,…,N-1},E={{u,v}|v-u modulo Nが2の冪乗}であるときこのグラフを頂点数Nのハイパーリング(N-HR)という。本稿では,HRの構成法,特性,埋め込み,スパナについて論じる。頂点数Nのハイパーキューブや,a×b格子,頂点数Nの完全二分木を,N-HRに部分グラフとして埋め込む.また,HRのスパナの構成方法を3タイプ紹介する.これらのタイプのスパナの伸び率は,HRの頂点数をNとすると高々[log_2N],任意の1【less than or equal】k【less than or equal】[log_2N]に対し2k-1,任意の2【less than or equal】k【less than or equal】[log_2N]-1に対し2k-1である.また,これらのタイプのスパナを構成する辺の数は,N-1,高々N[log_2N), k],高々N(log_2N-k)/2k+Nkである.最後に,HRのγシンクロナイザに関する伸び率と辺の数の表を示す.

著者

酒井 秀晃 中村 雅子 五十嵐 善英

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)

巻号頁・発行日

vol.99, no.388, pp.41-48, 1999-10-25

参考文献数

7

---

公開鍵暗号に対するSemantic Securityの新しい定義を提案する.Semantic Securityとは,平文に関するどのような部分情報も部分解読困難であることをいう.従来のSemantic Securityの定義はChosen-Plaintext Attackに対しての定義であり,Chosen-Ciphertext Attackに対しては定義されていなかった.そこでChosen-Plaintext Attackに対してもChosen-Ciphertext Attackに対しても有効な定義を提案する.また,公開鍵暗号に対してSemantic SecurityとIndistinguishabilityが等価であることを示す.新しいSemantic Securityの定義とGoldwasserとMicaliによるSemantic Securityの定義の関係を示す.Chosen-Plaintext Attackに対して,ある公開鍵暗号が新しい定義の意味でSemantic Securityを満たしているならばGoldwasserとMicaliによる定義の意味でもSemantic Securityを満たしているが,その逆は成り立たない.

著者

高村 政孝 五十嵐 善英

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)

巻号頁・発行日

vol.101, no.376, pp.61-68, 2001-10-12

被引用文献数

1

---

本論文ではsingle-writer/multi-reader共有変数モデル上で相互排他問題を解く2つのアルゴリズム提案する.これらのアルゴリズムはBakery algorithmの改良である.まず, ある特殊な条件が成り立っている元で, 有限サイズの共有変数で相互排他が実現されるようBakery algorithmを変更する.次に, この特殊な条件を取り除くために, どのユーザーにも属さない追加のプロセスを用いたアルゴリズムを提案する.この追加のプロセスを用いた相互排他アルゴリズムはlock-out-freeを満足する.さらに, このアルゴリズムの共有変数のサイズを減らすよう改良したアルゴリズムも提案する.これらのアルゴリズムの時間計算量は, ユーザーの数をn, atomic stepの時間の上限をl, ユーザーが資源を利用する時間の上限をcとすると, いずれも(n-1)c+Ο(nl)である.共有変数のサイズは, 最初のアルゴリズムが(n+1)(1+⌈log(n+2)⌉bits, 二つ目のアルゴリズムがn(1+⌈log(n+1)⌉)+1bitsである.