Isamu Furuya

Mr. Isamu Furuya

orcid

Research Focus & Metrics

Academic Career Length

10Years (2017-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
23 April 2020 in Algorithms
Verified
Journal Article
Open access
PDF file
IFIsamu Furuya
Isamu Furuya
TTTakuya Takagi
Takuya Takagi
YNYuto Nakashima
Yuto Nakashima
Shunsuke InenagaShunsuke Inenaga
Shunsuke Inenaga
HBHideo Bannai
Hideo Bannai
TKTakuya Kida
Takuya Kida
This study presents an analysis of RePair, which is a grammar compression algorithm known for its simple scheme, while also being practically effective. First, we show that the main process of RePair, that is, the step by step substitution of the most frequent symbol pairs, works within the corresponding most frequent maximal repeats. Then, we reveal the relation between maximal repeats and grammars constructed by RePair. On the basis of this analysis, we further propose a novel variant of RePair, called MR-RePair, which considers the one-time substitution of the most frequent maximal repeats instead of the consecutive substitution of the most frequent pairs. The results of the experiments comparing the size of constructed grammars and execution time of RePair and MR-RePair on several text corpora demonstrate that MR-RePair constructs more compact grammars than RePair does, especially for highly repetitive texts.

24 August 2023
Verified
Book Chapter
Closed access
PDF file
IFIsamu Furuya
Isamu Furuya
HKHayato Kasahara
Hayato Kasahara
AIAkiko Inoue
Akiko Inoue
KMKazuhiko Minematsu
Kazuhiko Minematsu
TITetsu Iwata
Tetsu Iwata

8 August 2019 in Algorithms
Verified
Journal Article
Open access
PDF file
IFIsamu Furuya
Isamu Furuya
TKTakuya Kida
Takuya Kida
In this study, we address the problem of compaction of Church numerals. Church numerals are unary representations of natural numbers on the scheme of lambda terms. We propose a novel decomposition scheme from a given natural number into an arithmetic expression using tetration, which enables us to obtain a compact representation of lambda terms that leads to the Church numeral of the natural number. For natural number n, we prove that the size of the lambda term obtained by the proposed method is O ( ( slog 2 n ) ( log n / log log n ) ) . Moreover, we experimentally confirmed that the proposed method outperforms binary representation of Church numerals on average, when n is less than approximately 10,000.

25 September 2025 in IACR Transactions on Symmetric Cryptology
Verified
Journal Article
Open access
PDF file
IFIsamu Furuya
Isamu Furuya
KMKazuhiko Minematsu
Kazuhiko Minematsu
At Eurocrypt 2006, Rogaway and Shrimpton (RS06) presented the idea of vector-input MAC that accepts a vector consisting of variable-length bit strings. A vector-input MAC could be built on a conventional (bit) string-input MAC, e.g., CMAC, with an injective encoding. RS06 pointed out an efficiency loss in this method and presented a general construction S2V that is more efficient than the encodingbased method. RS06 made significant scientific and practical impacts on the field of mode constructions, in particular for the invention of deterministic authenticated encryption. However, despite its potential, their work on vector-input MAC has been largely overlooked for more than 18 years. We revisit RS06’s treatment of vector-input MAC and show that the topic is more subtle than initially considered. We first formally define the problem of vector-input MAC and propose a natural efficiency goal for vector-input MACs as a counterpart of what has been considered for string-input MACs. Since S2V with any string-input MAC mode never achieves this efficiency goal, we propose a family of new MAC modes, VecMAC, that achieves this goal. VecMAC has a similarity to the popular PMAC, in particular its idea of tweak. However, the purpose of introducing tweak is different from PMAC and tweak is tailored to handle vectors without redundant block cipher calls. We also provide implementation results that show an advantage over the conventional method.

25 December 2020 in Algorithms
Verified
Journal Article
Open access
PDF file
Dominik KöpplDominik Köppl
Dominik Köppl
TITomohiro I
Tomohiro I
IFIsamu Furuya
Isamu Furuya
YTYoshimasa Takabatake
Yoshimasa Takabatake
KSKensuke Sakai
Kensuke Sakai
KGKeisuke Goto
Keisuke Goto
Re-Pairis a grammar compression scheme with favorably good compression rates. The computation of Re-Pair comes with the cost of maintaining large frequency tables, which makes it hard to compute Re-Pair on large-scale data sets. As a solution for this problem, we present, given a text of length n whose characters are drawn from an integer alphabet with size σ=nO(1), an O(min(n2,n2lglogτnlglglgn/logτn)) time algorithm computing Re-Pair with max((n/c)lgn,nlgτ)+O(lgn) bits of working space including the text space, where c≥1 is a fixed user-defined constant and τ is the sum of σ and the number of non-terminals. We give variants of our solution working in parallel or in the external memory model. Unfortunately, the algorithm seems not practical since a preliminary version already needs roughly one hour for computing Re-Pair on one megabyte of text.

1 January 2026 in IET Information Security
Verified
Journal Article
Open access
IFIsamu Furuya
Isamu Furuya
AIAkiko Inoue
Akiko Inoue
KMKazuhiko Minematsu
Kazuhiko Minematsu
We have developed a corruption‐correctable message authentication code (CCMAC) that enables data integrity to be verified and corruptions of data to be corrected up to a certain threshold. As in a previous technique for identifying corrupted points, called corruption detectable MAC (CDMAC), the proposed scheme utilizes a system model composed of two types of storage: general and secure. General storage is vulnerable, that is, data stored in it could be attacked by a malicious third party, whereas secure storage is not vulnerable. In this study, we present two methods of the proposed scheme, each of which has a trade‐off relationship regarding the data size requirements between general and secure storage. We also define security notions for our methods and prove that they can be reduced to those of the MAC or CDMAC used as an internal component.