# Analysis of the Perfect Table Fuzzy Rainbow Tradeoff

Authors: Byoung-Il Kim; Jin Hong
Journal: Journal of Applied Mathematics
 (2014)

---

## Abstract

Cryptanalytic time memory tradeoff algorithms are tools for inverting one-way functions, and they are used in practice to recover passwords that restrict access to digital documents. This work provides an accurate complexity analysis of the perfect table fuzzy rainbow tradeoff algorithm. Based on the analysis results, we show that the lesser known fuzzy rainbow tradeoff performs better than the original rainbow tradeoff, which is widely believed to be the best tradeoff algorithm. The fuzzy rainbow tradeoff can attain higher online efficiency than the rainbow tradeoff and do so at a lower precomputation cost.


---

## Body

## 1. Introduction

Cryptanalytic time memory tradeoff algorithms are tools for inverting generic one-way functions. They are actively used by law enforcement agencies and hackers to recover passwords protecting accesses to digital documents and to obtain system login passwords from the stored password hashes. After a one-time precomputation phase, whose computational complexity order is typical as that of an exhaustive computation of the one-way function on all inputs under consideration, a digest of the computation is written to a table of size that is of much smaller order than the complete dictionary. In the online phase, referencing the precomputation table, the input corresponding to a given inversion target is recovered with a computational complexity that is of much smaller order than that of an exhaustive trial of inputs. These algorithms allow tradeoffs to be made between the size of the precomputation table and the expected time for inversion through adjustments of various algorithm parameters.The first time memory tradeoff method was the classical algorithm by Hellman [1] and this was soon followed by the distinguished points variant. Rivest is given credit [2, page 100] for suggesting to apply the notion of distinguished points to the classical Hellman tradeoff. Currently, the rainbow tradeoff [3] is the most widely used algorithm.The fuzzy rainbow tradeoff [4, 5] is a more recent algorithm that combines the distinguished point and rainbow methods. The algorithm has already been used in the multitarget setting as an integral component of a fully functional attack [6, 7] on GSM phones, and an elementary analysis of the fuzzy rainbow tradeoff appeared in [8]. The latter work cites a work related to [6] and refers to the attack by the name Kraken, but none of these works cite the original publication [4, 5], indicating these to be an independent line of work. In fact, the analyses of [8] fall short of even the preliminary discussions given by [4, 5]. For now, the execution complexities of the fuzzy rainbow tradeoff are not known accurately enough for the purpose of comparing the performances of different tradeoff algorithms.The fuzzy rainbow tradeoff, as with most other tradeoff algorithms, comes in the nonperfect table and perfect table versions. The perfect table version is expected to perform better during the online phase than the nonperfect version, but this must be paid for with a larger precomputation effort. Our previous work [9] gave an accurate performance analysis of the nonperfect table fuzzy rainbow tradeoff and compared the results with the performances of the original nonperfect and perfect table rainbow tradeoffs, which are widely believed to be the best tradeoff algorithms. The conclusions made there were that the nonperfect fuzzy rainbow tradeoff was always advantageous over the nonperfect rainbow tradeoff and that, while the perfect rainbow tradeoff could achieve somewhat better online efficiency than the nonperfect fuzzy rainbow tradeoff, for online efficiency levels that could be reached by both algorithms, the nonperfect fuzzy rainbow tradeoff could do so with a smaller amount of precomputation.In this work, we analyze perfect table fuzzy rainbow tradeoff algorithm to present its performance accurately and compare this with the performances of the perfect rainbow tradeoff and the nonperfect fuzzy rainbow tradeoff. Our conclusion in rough terms is that the perfect fuzzy rainbow tradeoff outperforms the two comparison algorithms. This implies that the perfect fuzzy rainbow tradeoff, which has not yet received widespread recognition, is preferable to all the well-known tradeoff algorithms. We remark that the analysis given in this paper is completely different from that of our previous paper [9], which dealt with the nonperfect table case.One clarification must be made concerning the subject algorithm of this work. The fuzzy rainbow tradeoff, as originally presented by [4, 5], was a tradeoff algorithm designed to be used in the multitarget setting. This is where the attacker is given multiple inversion targets and is deemed successful if he is able to recover the input corresponding to at least one of targets. However, our analysis of the algorithm in this paper will be done under the single-target setting.Recall that a simple multitarget adaptation of the original rainbow tradeoff is quite inferior in performance [10] to the existing multitarget adaptations [11] of the classical Hellman and distinguished point tradeoffs and that the fuzzy rainbow tradeoff was designed to be a variant of the rainbow tradeoff that performs at a similar level. We have done some preliminary investigations and believe that it will not be difficult to transform the existing analysis results for the Hellman and distinguished point algorithms that were claimed for the single-target setting and the results of the present paper to the multitarget setting. In fact, we expect the existing equations concerning algorithm performances to remain essentially valid under the multitarget setting. Nevertheless, this transformation still requires a nontrivial amount of work and is relegated to a separate future work that focuses on the multitarget versions of the tradeoff algorithms. The current work will stay within the single-target setting.The rest of this paper is organized as follows. In Section2, we quickly review the fuzzy rainbow tradeoff algorithm and fix the notation. The execution behavior of the perfect table fuzzy rainbow tradeoff is fully analyzed in Section 3. This is a highly technical section and is the main contribution of this paper. Some experimental data that support the theoretical findings of this section are given in the appendix. In Section 4, we combine the results of our analysis with the existing analyses of other tradeoff algorithms to compare their performances. This could be more valuable to the practitioner than the details provided by Section 3. Finally, this paper is summarized in Section 5.


## 2. Preliminaries

Let us review the terminology concerning the fuzzy rainbow tradeoff algorithm and fix our notation. The reader is assumed to be familiar with the basic theory of the time memory tradeoff technique. In particular, we assume knowledge of the precomputation phase and online phase algorithms of the distinguished point (DP) and rainbow tradeoffs. The few sections in the beginning of [12] could be helpful in recalling these basics.Throughout this paper, the one-way functionf
:
N
→
H  to be inverted is taken to act on a search space  N  of size  N. We fixs-many reduction functionsr
i
:
H
→
N
(
i
=
1
,
…
,
s
) and letf
i
:
N
→
N  denote the composition of the one-way function f and the reduction functionr
iof theith color. The number of colorsswill typically be in the range30
≤
s
≤
150.The structure of the precomputation matrix for the fuzzy rainbow tradeoff is a combination of those of the rainbow tradeoff and the DP tradeoff. One fixes a distinguishing property of probability1
/
tand generates precomputation chains of the form
(1)
SP
→
f
1
∘
⋯
∘
→
f
1
DP
→
f
2
∘
⋯
∘
→
f
2
DP
→
f
3
∘
⋯
⋯
∘
→
f
s
-
1
DP
→
f
s
∘
⋯
∘
→
f
s
DP
=
EP
⁡
,
which could be referred to as a fuzzy rainbow chain. That is, one iterates the one-way functionf
iof a fixed coloriuntil the first appearance of a DP and the ending point of this DP subchain is used as the starting point for the next DP subchain. The color of the iteration function is changed at each intermediate DP until one reaches the end of thesth DP subchain. In short, each iteration of a rainbow chain is replaced by a DP chain, except that the number of colors used by each precomputation table issand that the expected chain length of each DP subchain ist.Any implementation of an algorithm that relies on DPs to terminate a task must employ a mechanism to detect chains falling into loops. Typically, a bound on the chain length is set, and chains reaching this bound are discarded, possibly to be replaced with newly generated chains. We will assume the chain length bound is large enough to make the discarding of chains very infrequent, so that any effect the discarding may have on the algorithm performance can be ignored.This paper deals with the perfect table version of the fuzzy rainbow tradeoff and the number of ending points for each perfect table is set tom. That is, one generates sufficiently many precomputation chains for each precomputation table, so thatmnonmerging precomputation chains can be collected. As with any tradeoff algorithm, themordered pairs, each consisting of a starting point and an ending point, are sorted according to the ending points and recorded as the precomputation table. A total of  l  precomputation tables are created during the precomputation phase.The reader is cautioned to distinguish between the terms precomputationtable and precomputationmatrix while reading this paper. A precomputation table consists of just the starting and ending point pairs of the precomputation chains, whereas a matrix consists of all points of the precomputation chains, including the intermediate points that are not written to the table. The precomputation matrix is mentally visualized as a collection of chains, with some of them possibly merging into each other in the nonperfect case, rather than as a structureless set of points.One can regard a single nonperfect fuzzy rainbow precomputation matrix as a concatenation ofs-many nonperfect DP submatrices. We will write  D
M
ito refer to theith DP submatrix (1
≤
i
≤
s) residing within a single nonperfect fuzzy rainbow matrix and use  |
D
M
i
|to denote the number of distinct points contained therein. The ending points of one DP submatrix become the starting points of the following DP submatrix, and the only difference between a standard nonperfect DP matrix and any  D
M
i  is that the latter may contain duplicate starting points that lead to completely identical chains, should one insist on treating them as separate chains. The expected number of distinct starting points and ending points for  D
M
iis written asm
i
-
1andm
i, respectively. In particular,m
0is the number of starting points that are initially used in creating a perfect fuzzy rainbow matrix, andm
s
=
mis the number of distinct terminal ending points of the fuzzy rainbow matrix.The process of removing chain merges during the precomputation phase requires further clarification. The creation of a precomputation table for the perfect fuzzy rainbow tradeoff begins with a choice ofm
0starting points and the generation of the first nonperfect DP submatrix  D
M
1. After the generation of each nonperfect DP submatrix  D
M
i, the chains are sorted according to the ending points of  D
M
iand duplicate ending points are located to remove chain merges. Specifically, from each group of merging chains, one retains the chain with the longestith color DP chain segment and discards the other chains. We denote the resulting (temporary) perfect DP submatrix as  D
M
~
i. The set of ending points from  D
M
~
iis identical to the set of ending points from  D
M
i, and these are used as the starting points for the next nonperfect DP submatrixD
M
i
+
1. For an appropriate choice ofm
0, which will be discussed later, the final perfect DP submatrix  D
M
~
sis expected to containm
=
m
snonmerging chains. The collection of all DP chains in  D
M
~
ithat eventually reach one of themDP chains that remain in  D
M
~
sis denoted byD
M
¯
i. In particular, we have  D
M
¯
s
=
D
M
~
s, and only the elements of the final perfect DP submatricesD
M
¯
ican contribute to the success of inversions.The method for handling merges explained above does not make reference to the total lengths of the chains and relies only on theith DP chain segment lengths. We chose to work with such a merge removal rule, because it allowed existing results concerning the perfect DP tradeoff to be used during our analysis of the perfect fuzzy rainbow tradeoff. However, since some readers may object that it is more reasonable to base the merge removal rule on the total chain lengths, let us present two remarks concerning this matter.First, we argue that the choice of merge removal method is not very important for the fuzzy rainbow tradeoff. Note that the rule for selecting one chain from a set of merging chains was an important issue for the perfect DP tradeoff that required attention because the chain lengths of a DP matrix form a geometric distribution. However, the lengths of the fuzzy rainbow chains form a distribution that very quickly approaches the normal distribution assis increased. Intuitively, this is to be expected, since the concatenation of multiple DP chains will create an averaging affect. In fact, it is not difficult to work out the distribution explicitly and verify the claim directly. Hence, the variation in fuzzy rainbow chain lengths is small, and the impact of choices based on chain lengths on the performance of the fuzzy rainbow tradeoff can only be limited. Furthermore, the averaging effect implies that, except at smallivalues, our merge removal rule that references just theith DP chain segment is likely to return the chain that is the longest in overall length.Second, we question whether it is reasonable to retain the longer chains in the first place. The practice is widely accepted with the perfect DP tradeoff, because it is expected to bring about higher success rate for the same amount of storage use. However, the approach also increases both the number of false alarms and the average cost of resolving each false alarm. Although we strongly believe that the positive effect of choosing longer chains on the success rate is likely to outweigh its negative effects on the online cost, currently, there is no publicly available theoretical argument or experimental evidence to support such a claim. A separate detailed study would be required to arrive at a definitive answer concerning this matter.This completes our description of the precomputation phase for the perfect fuzzy rainbow tradeoff. To the reader with some experience in the tradeoff technique, the online phase algorithm should now be mostly obvious from the structure of the precomputation matrix. Given an inversion target, for each precomputation table and starting color1
≤
i
≤
s, one generates a partial fuzzy rainbow chain that starts from theith color. If the terminal DP of this online chain can be found among the ending points of the precomputation table, the corresponding starting point is used to regenerate the precomputation chain, which could possibly return the correct input to the inversion target. However, most of the collisions will turn out to be false alarms, in which case the regeneration of the precomputation chain may be stopped at the DP for the color from which the online chain was started.Some clarifications must be made concerning the order in which the online chains are created. In short, the multiple precomputation tables of the fuzzy rainbow tradeoff are processed in parallel, in a manner similar to the approach taken by the rainbow tradeoff. In practice, a round-robin style method can be used to simulate the parallel treatment of tables with even a single CPU, and this modification will not have a visible effect on the computational complexity, unless a smallsis used.Let us make this more explicit. The online phase of the fuzzy rainbow tradeoff is performed insdiscrete steps. On the1st step, the online DP chains for thesth colors, corresponding to the  l  precomputation tables, are generated. All generated alarms are resolved before one moves onto the2nd step. On theith step, fuzzy rainbow chains that start from the(
s
-
i
+
1
)th colors, for the l  precomputation tables, are generated, and all resulting alarms are treated. The online phase is terminated when either the correct answer to the inversion target is found, or allssteps have been completed. Even though it is likely for the answer to be obtained in the middle of the processing of someith step, our analysis will assume that any step that has been initiated is fully completed, regardless of whether the answer has been secured. The effect of this simplification on the analysis results will be small, unless a smallsis used.Our analysis of the perfect fuzzy rainbow tradeoff will frequently utilize two approximation techniques. The first is the approximation(
1
-
(
1
/
b
)
)
a
≈
e
-
a
/
b. As explained in [12, Appendix A], this is appropriate whena
=
O
(
b
). The second technique is the approximation of a sum over a large index set into a definite integral. Both of these approximations will be very accurate, whenever we use them, as long as the tradeoff algorithm parameters are chosen reasonably. Throughout this paper, we will ignore multiplicative factors of1
+
O
(
1
/
t
)size and write approximations of such order as equalities.


## 3. Analysis of the Perfect Table Fuzzy Rainbow Tradeoff

In this section, we analyze the online efficiency and the storage optimization issues for the perfect table fuzzy rainbow tradeoff. The expected computational complexity, rather than the worst case complexity, is computed and the effects of false alarms are fully taken into account. We always assume that the parametersm,t, ands, for the perfect fuzzy rainbow tradeoff, are chosen to satisfym
t
2
s
=
F
¯
msc
N, with a matrix stopping constantF
¯
mscthat is neither too large nor very close to zero.


### 3.1. Number of Color Boundary Points

Let us consider a nonperfect fuzzy rainbow matrix created fromm
0starting points and its nonperfect DP submatricesD
M
i. For each0
≤
i
≤
s, the collection ofm
ipoints that form the boundaries of the nonperfect DP submatrices will be referred to as theithcolor boundary points of the nonperfect fuzzy rainbow matrix.Our previous work [9] stated the relation
(2)
|
D
M
i
|
=
m
i
t
and gave the iterative formula
(3)
m
i
m
0
=
m
i
-
1
m
0
2
1
+
1
+
2
(
(
F
msc
/
s
)
(
m
i
-
1
/
m
0
)
)
,
for computingm
i, whereF
msc
=
(
m
0
t
2
s
)
/
Nis the matrix stopping constant for the nonperfect fuzzy rainbow matrix. The work also derived the closed-form approximation
(4)
m
i
=
2
m
0
2
+
F
msc
(
i
/
s
)
,
under the assumption thatsis large, and claimed this to be accurate for even smallsvalues. The claimed accuracy is verified once more through experiments for parameters of our interest in the Appendix, and we will assume (4) is sufficiently accurate for the purpose of this work in the remainder of this paper.Let us rewrite (4) in terms of the perfect fuzzy rainbow tradeoff parameters, so that the expression is more suitable for this work.Lemma 1.
To create a perfect fuzzy rainbow matrix containingmnonmerging chains, one must expect to generatem
0
=
(
2
/
(
2
-
F
¯
m
s
c
)
)
mchains. Furthermore, the number ofith color boundary points in the nonperfect fuzzy rainbow matrix generated during this process is expected to be
(5)
m
i
=
2
m
(
2
-
F
¯
m
s
c
)
+
F
¯
m
s
c
(
i
/
s
)
,
fori
=
0,1
,
…
,
s.Proof.
Substitutingi
=
sinto (4), we know that a nonperfect fuzzy rainbow matrix created withm
0starting points is expected to containm
s
=
(
2
/
(
2
+
F
msc
)
)
m
0nonmerging chains, whereF
msc
=
(
m
0
t
2
s
)
/
N. The requirement ofm
=
m
s
=
(
2
/
(
2
+
F
msc
)
)
m
0may be written as
(6)
F
¯
msc
=
2
F
msc
2
+
F
msc
.
Solving this equation forF
msc, we can rewrite it as
(7)
F
msc
=
2
F
¯
msc
2
-
F
¯
msc
,
which is equivalent to the first statement of this lemma. Substituting the first claim and the above equation into (4), we find
(8)
m
i
=
2
(
2
/
(
2
-
F
¯
msc
)
)
m
2
+
(
(
2
F
¯
msc
/
(
2
-
F
¯
msc
)
)
(
i
/
s
)
)
,
and this is the second claim of this lemma.The first two displayed equations appearing in this proof both imply thatF
¯
msc
<
2is always satisfied, which is similar to the situation with perfect rainbow tradeoffs. The reader may have guessed that takingF
¯
mscvery close to2corresponds to making bad parameter choices. In fact, we will later observe in Section 4.4 thatF
¯
mscis bounded sufficiently away from2for any meaningful parameters and that the precomputation requirement grows unrealistically large asF
¯
mscapproaches2.Because of its frequent appearances in the remainder of this section, we will introduce the notation(9)
f
-
i
=
m
i
t
2
N
=
2
F
¯
msc
(
2
-
F
¯
msc
)
+
F
¯
msc
(
i
/
s
)
1
s
.
When a smallsis in use, the symbolf
-
ishould be understood as designating the middle term, with the second equality interpreted as an approximation. However, we will mostly take the final term as the definition off
-
i, assumingsto be sufficiently large, and use this notation even fori
=
s
+
1andi
=
s
+
2. SinceF
¯
mscis bounded away from2for all practical parameter sets, we may assumef
-
ito be ofΘ
(
1
/
s
)order. Our use of the lower case letterf
-, rather thanF
¯, is meant to serve as a reminder thatf
-
iis not ofΘ
(
1
)order.One can directly verify from the definition that(10)
f
-
i
f
-
j
=
1
+
j
-
i
2
f
-
i
=
1
1
+
(
(
(
i
-
j
)
/
2
)
f
-
j
)
.
Combination of the middle expression with the knowledge off
-
i
=
Θ
(
1
/
s
)implies(
f
-
i
/
f
-
j
)
=
Θ
(
1
), forj
≥
i, and the right-hand side expression similarly implies the same claim, fori
≥
j.


### 3.2. Probability of Success

An expression for the probability of success of the perfect fuzzy rainbow tradeoff is obtained in this subsection. We first define and present a formula for theprecomputation coefficient of the algorithm.Proposition 2.
The precomputation phase of the perfect table fuzzy rainbow tradeoff is expected to requireF
¯
p
c
N  iterations of the one-way function, where the precomputation coefficient is
(11)
F
¯
p
c
=
l
t
∑
i
=
0
s
-
1
‍
2
F
¯
m
s
c
(
2
-
F
¯
m
s
c
)
+
F
¯
m
s
c
(
i
/
s
)
1
s
.Proof.
Since each DP chain is expected to be of lengtht, on average, the computation of each temporary submatrixD
M
~
ifrom itsm
i
-
1distinct starting points requiresm
i
-
1
titerations of the one-way function. The effort of sorting the ending points ofD
M
~
i, so that duplicates can be removed and the distinct starting points for the next submatrix are obtained, is of m
log
⁡
⁡
m order, which is much smaller than the effort of generating the submatrix, and can be ignored. Taking account of the  l  tables, the cost of precomputation can be stated as
(12)
(
m
0
+
m
1
+
⋯
+
m
s
-
1
)
t
l
.
Applying Lemma 1, we can write this as
(13)
t
l
∑
i
=
0
s
-
1
‍
2
m
(
2
-
F
¯
msc
)
+
F
¯
msc
(
i
/
s
)
to obtain the claimed formula.Let us use the notation(14)
F
¯
cr
,
i
=
|
D
M
¯
i
|
m
t
,
where|
D
M
¯
i
|denotes the number of distinct points expected in theith submatrix of a perfect fuzzy rainbow matrix, and define thecoverage rate of a perfect fuzzy rainbow matrix to be
(15)
F
¯
cr
=
1
m
t
s
∑
i
=
1
s
‍
|
D
M
¯
i
|
=
1
s
∑
i
=
1
s
‍
F
¯
cr
,
i
.
Note that the definitions allow us to expect bothF
¯
cr
,
iandF
¯
crto be ofΘ
(
1
)order.The coverage rate (15) of a perfect fuzzy rainbow matrix may be computed fromsandF
¯
mscthrough the following formula.Lemma 3.
The coverage rate of the DP submatrixD
M
¯
iis given by
(16)
F
¯
c
r
,
i
=
2
N
m
i
t
2
ln
⁡
(
1
+
m
i
t
2
2
N
)
=
2
f
-
i
ln
⁡
(
1
+
f
-
i
2
)
.Proof.
Recall thatD
M
¯
iis a subcollection of the chains appearing inD
M
~
i. Note that the selection of chains fromD
M
~
ito be retained inD
M
¯
idepends on the behavior of the chains that extend out from the ending points ofD
M
~
iand is independent of theith submatrix itself. In other words, the chains ofD
M
¯
ihave been selected at random from the chains ofD
M
~
i. Hence, the averages of chain lengths contained inD
M
~
iandD
M
¯
iwill be the same, and we can make the crucial observation that
(17)
F
¯
cr
,
i
=
|
D
M
¯
i
|
m
t
=
|
D
M
~
i
|
m
i
t
.
In other words, the coverage rate ofD
M
¯
iis equal to the coverage rate ofD
M
~
i.
Now, recall that eachD
M
~
iis simply a normal perfect DP matrix and also recall from [13] that the coverage rate of a perfect DP matrixD
¯
crmay be computed as
(18)
D
¯
cr
=
2
D
¯
msc
ln
⁡
⁡
(
1
+
D
¯
msc
2
)
,
whereD
¯
msc
=
m
′
t
2
/
Nis the matrix stopping constant for the perfect DP matrix ofm
′ending points. Thus we can write
(19)
F
¯
cr
,
i
=
2
m
i
t
2
/
N
ln
⁡
⁡
(
1
+
m
i
t
2
/
N
2
)
,
as claimed.We are now ready to state the success probability of the perfect fuzzy rainbow tradeoff as a function of the algorithm parameters.Proposition 4.
Consider an input to the one-way function that is chosen uniformly at random from the input space. Given the image of this input under the one-way function as the inversion target, the online phase of the perfect table fuzzy rainbow tradeoff will succeed in recovering the original input with probability(20)
F
¯
p
s
=
1
-
exp
⁡
(
-
F
¯
m
s
c
F
¯
c
r
l
t
)
.Proof.
The probability of success one can expect from the online processing of a single DP submatrixD
M
¯
iis|
D
M
¯
i
|
/
N. Since the submatrices were generated by different reduction functions, we may treat them as being independent. Thus, the probability of success for the complete online phase, taking all the l tables into account, may be written as
(21)
F
¯
ps
=
1
-
∏
i
=
1
s
‍
(
1
-
|
D
M
¯
i
|
N
)
l
=
1
-
∏
i
=
1
s
‍
(
1
-
F
¯
msc
F
¯
cr
,
i
t
s
)
l
.
This can be approximated by
(22)
F
¯
ps
=
1
-
exp
⁡
⁡
(
-
F
¯
msc
∑
i
=
1
s
‍
F
¯
cr
,
i
l
t
s
)
=
1
-
exp
⁡
(
-
F
¯
msc
F
¯
cr
l
t
)
,
as claimed.Given any set of parameters, one can compute the success rate by combining the above formula with definition (15), Lemma 3, and notation (9). More precisely, the success rate may be seen as a function ofF
¯
msc,l
/
t, ands, rather than as a function of the more basic constant and parameters  N, m, t, l, ands.The proposition also shows that one can fix positive integersandF
¯
msc
<
2to any value and still attain any success rate requirementF
¯
psby adhering to the relation
(23)
l
t
=
{
-
ln
⁡
(
1
-
F
¯
ps
)
}
F
¯
msc
F
¯
cr
.
Note that this implies that, unless the requirement for the probability of successF
¯
psis unrealistically close to1, we will have  l
/
t
=
Θ
(
1
). In other words, the parameters  l  and  t  will be of the same order.


### 3.3. Online Complexity

The time memory tradeoff curve for the perfect fuzzy rainbow tradeoff is obtained in this subsection through a careful computation of the average case online execution complexities. This is the most complicated part of this paper.We start by assessing how likely each step of the online phase is to be executed.Lemma 5.
The probability for an online chain that starts from theith color of a perfect fuzzy rainbow matrix to be generated, that is, the probability for theith DP submatrixD
M
¯
ito be searched for the correct answer, is
(24)
exp
⁡
(
-
F
¯
m
s
c
l
t
1
s
∑
k
=
i
+
1
s
‍
F
¯
c
r
,
k
)
=
(
1
-
F
¯
p
s
)
(
∑
k
=
i
+
1
s
‍
F
¯
c
r
,
k
)
/
s
F
¯
c
r
,
whereF
¯
p
sis as given by Proposition 4.Proof.
The online chain that starts from theith color of a perfect fuzzy rainbow matrix will be generated if and only if the correct answer to the inversion target does not belong to the submatricesD
M
¯
i
+
1
,
…
,
D
M
¯
scontained in the  l  perfect fuzzy rainbow matrices. Hence, the probability under consideration is
(25)
∏
k
=
i
+
1
s
‍
(
1
-
|
D
M
¯
k
|
N
)
l
=
exp
⁡
(
-
F
¯
msc
l
t
1
s
∑
k
=
i
+
1
s
‍
F
¯
cr
,
k
)
.
The equality claimed in the lemma statement follows from an application of Proposition 4.The cost of generating the online chains is a direct corollary to this lemma. It suffices to realize that an online chain that starts from theith color is expected to be of lengtht
(
s
-
i
+
1
)and that there are  l  tables to consider.Proposition 6.
The generation of the online chains for the perfect fuzzy rainbow tradeoff is expected to require(26)
t
l
∑
i
=
1
s
‍
(
s
-
i
+
1
)
(
1
-
F
¯
p
s
)
(
∑
k
=
i
+
1
s
‍
F
¯
c
r
,
k
)
/
s
F
¯
c
r
iterations of the one-way function.Our next goal is to obtain the cost of resolving alarms that appear during the online phase. This part calls for very delicate arguments involving random functions and is very technical. The practice-oriented reader can skip the following few lemmas and jump to Proposition10.We will consider an online chain that starts from theith color and treat the case of it merging into the fuzzy rainbow matrix within theith color and the case of it merging at a strictly later color separately. As a preliminary result, we require the probability for an online chain to merge into a fuzzy rainbow matrix.Lemma 7.
An online DP chain segment of theith color will not merge into thenonperfect DP submatrixD
M
iwith probability(
1
/
(
1
+
f
-
i
)
)
=
(
f
-
i
+
2
/
f
-
i
). The probability for an online chain that starts from theith color not to merge into theperfect fuzzy rainbow precomputation matrix is∏
k
=
i
s
‍
(
1
/
(
1
+
f
-
k
)
)
=
(
f
-
s
+
1
/
f
-
i
)
(
f
-
s
+
2
/
f
-
i
+
1
).Proof.
An online DP chain segment of theith color will escape merging into the nonperfect DP submatrixD
M
iwith probability
(27)
∑
k
=
1
∞
‍
(
1
-
1
t
-
|
D
M
i
|
N
)
k
-
1
(
1
t
-
m
i
N
)
=
1
-
(
t
m
i
/
N
)
1
+
(
t
|
D
M
i
|
/
N
)
≈
1
1
+
(
t
|
D
M
i
|
/
N
)
,
where the approximation is justified by the facts(
t
m
i
/
N
)
=
Θ
(
1
/
t
s
)and(
t
|
D
M
i
|
/
N
)
=
Θ
(
1
/
s
). Substituting (2) into this expression and then applying (9), the probability can be written as
(28)
1
1
+
f
-
i
=
(
2
-
F
¯
msc
)
+
F
¯
msc
(
i
/
s
)
(
2
-
F
¯
msc
)
+
F
¯
msc
(
(
i
+
2
)
/
s
)
=
f
-
i
+
2
f
-
i
.
The probabilities for an online chain to merge intoD
M
¯
kandD
M
kare usually different, but the two are the same whenk
=
s. Now, an online chain that starts from theith color does not merge into the perfect precomputation matrix if and only if none of its DP chain segments merge into the submatricesD
M
¯
i
,
D
M
¯
i
+
1
,
…
,
D
M
¯
s, and this happens if and only if the online DP chain segments do not merge into the nonperfect submatricesD
M
i
,
D
M
i
+
1
,
…
,
D
M
s. Here, we emphasize that a series of submatrices ending at the terminalsth color is being considered. The claimed probability is the product of the term(
1
/
(
1
+
f
-
k
)
)
=
(
(
f
-
k
+
2
)
/
f
-
k
)overk
=
i
,
…
,
s.The following lemma gives the cost of dealing with an alarm from a possible delayed merge, assuming the generation of an online chain that starts from theith color.Lemma 8.
Consider a single perfect fuzzy rainbow precomputation matrix and its associatedscolors. Assume the generation of an online chain for this matrix that starts from theith color. The cost of resolving an alarm that may be induced by a possible merge of this online chain into the fuzzy rainbow matrix strictly after theith color is expected to be
(29)
t
(
∑
k
=
1
i
‍
F
¯
c
r
,
k
)
{
f
-
i
+
2
f
-
i
(
1
-
f
-
s
+
1
f
-
i
+
1
f
-
s
+
2
f
-
i
+
2
)
+
(
1
-
f
-
i
+
2
f
-
i
)
(
1
-
f
-
s
f
-
i
)
}
iterations of the one-way function.Proof.
We require the probability for an online chain that starts from theith color to merge into the perfect fuzzy rainbow precomputation matrix without merging into the submatrixD
M
¯
i. Such a merge could occur through the following two separate events. (a) Theith color online DP chain segment does not merge into the nonperfect submatrixD
M
i, but the online chain part that extends out from the ending DP of theith color segment merges into the perfect precomputation matrix. (b) Theith color online chain merges intoD
M
i, without merging intoD
M
¯
i, in which case the online chain is destined to merge into the perfect precomputation matrix at a later color.
If theith color online DP chain segment does not merge intoD
M
i, the chain that extends from its ending point may still be iterated with a random function. Hence, it is clear from Lemma 7 that the probability for the (a)-event to occur is
(30)
f
-
i
+
2
f
-
i
(
1
-
f
-
s
+
1
f
-
i
+
1
f
-
s
+
2
f
-
i
+
2
)
.
On the other hand, the extended part of the online chain is allowed no randomness in the (b)-event. We already know from the proof of Lemma3 that an ending point ofD
M
i, that is, an ending point ofD
M
~
i, has probability(
m
s
/
m
i
)
=
(
f
-
s
/
f
-
i
)of remaining among the ending points ofD
M
¯
i. Once again, Lemma 7 allows us to claim
(31)
(
1
-
f
-
i
+
2
f
-
i
)
(
1
-
f
-
s
f
-
i
)
as the probability for the (b)-event to occur. The probability for a merge to appear strictly after theith color is the sum of the above two probabilities.
A merge of the online chain into the precomputation matrix that appears strictly after theith color requires one to regenerate the associated precomputation chain up to the end of theith color. Note that (14) allows us to write the average chain length|
D
M
¯
i
|
/
mof each DP submatrixD
M
¯
iasF
¯
cr
,
i
t. Hence, to resolve the alarm from the merge discussed above, one must expect to compute(
F
¯
cr
,
1
+
⋯
+
F
¯
cr
,
i
)
titerations of the one-way function.
The claimed cost of resolving alarms is a simple product of the merge probability and the work factor we have already stated.The cost of dealing with an immediate merge of the online chain into the perfect precomputation matrix is given next.Lemma 9.
Consider a single perfect fuzzy rainbow precomputation matrix and its associatedscolors. Assume the generation of an online chain for this matrix that starts from theith color. The cost of resolving an alarm that may be induced by a possible merge of this online chain into the fuzzy rainbow matrix within theith color segment is expected to be approximately
(32)
t
(
1
+
∑
k
=
1
i
‍
F
¯
c
r
,
k
)
(
1
-
f
-
i
+
2
f
-
i
)
f
-
s
f
-
i
iterations of the one-way function.Proof.
Arguments given in the proof of Lemma8 already show that the probability for a merge to occur within theith color segment into the perfect DP submatrix is
(33)
(
1
-
f
-
i
+
2
f
-
i
)
f
-
s
f
-
i
.
Since the online chain will merge into at most one precomputation chain inD
M
¯
i, it only remains to find out how much work is required to resolve such a merge.
An alarm will require the associated precomputation chain to be regenerated at least up to the start of theith DP submatrix, and we saw during the proof of Lemma 8 that this costs(
F
¯
cr
,
1
+
⋯
+
F
¯
cr
,
i
-
1
)
titerations of the one-way function. The number of additionalith color segment iterations that are required must be handled more carefully. One can expect this to be larger thanF
¯
cr
,
i
t, because longer precomputation chains are more likely to be involved in merges.
The work [12] stated in its Lemma 12 that the cost of resolving alarms expected from the processing of a single nonperfect DP table is2
D
msc
titerations of the one-way function, whereD
mscis the matrix stopping constant of the nonperfect DP matrix. Following the arguments given in the proof of the same lemma, one can write the number of false alarms expected during the processing of a single DP table as
(34)
D
msc
∫
0
∞
‍
∫
0
∞
‍
exp
⁡
⁡
(
-
u
)
exp
⁡
(
-
v
)
{
exp
⁡
⁡
(
min
⁡
(
u
,
v
)
)
-
1
}
d
u
d
v
=
D
msc
.
Computing the ratio of these two numbers, we can conclude that, during the processing of a single nonperfect DP table, each alarm calls for2
titerations of the one-way function to resolve, on average.
Now, since (10) implies that(
m
i
/
m
i
-
1
)
=
1
-
Θ
(
1
/
2
s
), we know that only a small portion ofD
M
iis discarded in creatingD
M
~
i, so that the DP matricesD
M
iandD
M
~
imust be similar in their distributions of chain lengths. We also saw during the proof of Lemma 3 that the selection ofD
M
¯
ifromD
M
~
idoes not affect the distribution of chain lengths. Hence, it is reasonable to expect a merge of the online chain within theith color segment into eitherD
M
iorD
M
¯
ito call for approximately2
titerations of theith colored one-way function, on average.
We wish to add a small tweak to the2
tclaim. Note that the average chain length of a nonperfect DP matrix ist, whereas that ofD
M
¯
iisF
¯
cr
,
i
t. Since the average chain length may be understood as a concise representation of the distribution of chain lengths, one might expect chain lengths, and one might expect2
F
¯
cr
,
i
t, which take the average chain length ofD
M
¯
iinto account, to be a better approximation of the additional work than2
t. In any case, since Lemma 3 implies thatF
¯
cr
,
i
=
1
-
Θ
(
1
/
4
s
), we know that2
tknow that2
tand2
F
¯
cr
,
i
tare very close to each other. In similarity, wechoose to take(
1
+
F
¯
cr
,
i
)
tas the number of extraith color iterations required, since this will make our later formulas look slightly simpler.
The claimed cost of resolving alarms is a simple combination of the three factors(
1
-
(
f
-
i
+
2
/
f
-
i
)
)
(
f
-
s
/
f
-
i
),(
F
¯
cr
,
1
+
⋯
+
F
¯
cr
,
i
-
1
)
t, and(
1
+
F
¯
cr
,
i
)
tthat we have discussed so far.Combining Lemmas8 and 9, we can state that the cost of dealing with an alarm that may be induced by an online chain generated from theith color is
(35)
t
{
(
∑
k
=
1
i
‍
F
¯
cr
,
k
)
(
1
-
f
-
s
+
1
f
-
i
f
-
s
+
2
f
-
i
+
1
)
+
f
-
i
+
2
f
-
i
f
-
s
}
,
where we have relied on (10) to replace(
1
-
(
f
-
i
+
2
/
f
-
i
)
)
(
f
-
s
/
f
-
i
)with(
f
-
i
+
2
/
f
-
i
)
f
-
s. Since, unlike other results of this paper, we have stated Lemma 9 only as an approximation, let us briefly explain that this is still very accurate. Using relation (10) and the rough approximations∑
k
=
1
i
F
¯
cr
,
k
=
Θ
(
i
)andf
-
i
=
Θ
(
1
/
s
), it is easy to verify the facts
(36)
(
∑
k
=
1
i
‍
F
¯
cr
,
k
)
(
1
-
f
-
s
+
1
f
-
i
f
-
s
+
2
f
-
i
+
1
)
=
Θ
(
i
(
s
-
i
+
1
)
s
)
,
f
-
i
+
2
f
-
i
f
-
s
=
Θ
(
1
s
)
.
This shows that, unlesssis very small, the first factor of (35) is at leaststimes larger than the second factor. On the other hand, the proof of Lemma 9 shows that the error given by formula (35) will be more than sufficiently bounded by its second factor. Hence, we can expect (35) to be accurate up to a1
+
O
(
1
/
s
)factor, at the worst. In fact, our testing to be presented in the Appendix confirms that the accuracy of (35) is much higher than what we have claimed here.The computational cost of dealing with the alarms is now a direct corollary to Lemmas5, 8, and 9.Proposition 10.
The treatment of alarms during the online phase of a perfect fuzzy rainbow tradeoff is expected to require(37)
t
l
∑
i
=
1
s
‍
(
1
-
F
¯
p
s
)
(
∑
k
=
i
+
1
s
‍
F
¯
c
r
,
k
)
/
s
F
¯
c
r
×
{
(
∑
k
=
1
i
‍
F
¯
c
r
,
k
)
(
1
-
f
-
s
+
1
f
-
i
f
-
s
+
2
f
-
i
+
1
)
+
f
-
i
+
2
f
-
i
f
-
s
}
iterations of the one-way function.The online computational complexity of the perfect fuzzy rainbow tradeoff can be stated as the sum(38)
T
=
t
l
s
∑
i
=
1
s
‍
(
1
-
F
¯
ps
)
(
∑
k
=
i
+
1
s
‍
F
¯
cr
,
k
)
/
s
F
¯
cr
×
(
(
∑
k
=
1
i
‍
F
¯
cr
,
k
s
)
(
1
-
f
-
s
+
1
f
-
i
f
-
s
+
2
f
-
i
+
1
)
s
-
i
+
1
s
+
1
s
f
-
i
+
2
f
-
i
f
-
s
+
(
∑
k
=
1
i
‍
F
¯
cr
,
k
s
)
(
1
-
f
-
s
+
1
f
-
i
f
-
s
+
2
f
-
i
+
1
)
)
of its two components stated by Propositions 6 and 10. Recalling from the discussion given under (23) that(
l
/
t
)
=
Θ
(
1
), it is easy to argue thatTis ofΘ
(
t
2
s
2
)order. The following time memory tradeoff curve is a direct consequence of our knowledge secured of the online time complexityTand the observation that the storage complexity isM
=
m
l.Theorem 11.
The time memory tradeoff curve for the perfect table fuzzy rainbow tradeoff isT
M
2
=
F
¯
t
c
N
2, where the tradeoff coefficient is
(39)
F
¯
t
c
=
F
¯
m
s
c
2
(
l
t
)
3
1
s
∑
i
=
1
s
‍
(
1
-
F
¯
p
s
)
(
∑
k
=
i
+
1
s
‍
F
¯
c
r
,
k
)
/
s
F
¯
c
r
×
(
s
-
i
+
1
s
+
1
s
f
-
i
+
2
f
-
i
f
-
s
11111
+
(
∑
k
=
1
i
‍
F
¯
c
r
,
k
s
)
(
1
-
f
-
s
+
1
f
-
i
f
-
s
+
2
f
-
i
+
1
)
)
.As a corollary to Lemma5, we can state that the online phase of the perfect table fuzzy rainbow tradeoff is expected to call for
(40)
l
∑
i
=
1
s
‍
(
1
-
F
¯
ps
)
(
∑
k
=
i
+
1
s
‍
F
¯
cr
,
k
)
/
s
F
¯
cr
lookups to the precomputation table. One can easily verify that this is ofΘ
(
t
s
)order, which is much smaller than the online computational complexityT
=
Θ
(
t
2
s
2
).


### 3.4. Storage Optimization

The storage complexityM appearing in the tradeoff curve of Theorem 11 refers to the total number of entries that need to be stored in the precomputed tables. However, practical interest would be in the size of the required physical recording media expressed in number of bits. Hence, we need to discuss the number of bits occupied by each starting and ending point pair in the tables.The naive approach would allocate2
log
⁡
N  bits to each table entry, but there are more efficient methods. Each starting point can be recorded inlog
⁡
m
0bits [14–16] through the use of consecutive starting points. In storing the ending points, one need not record bits that can be recovered from the definition of the distinguishing property [15, 17]. One can create an index table [15] for each sorted table and remove almost log
⁡
⁡
m most significant bits from each ending point. Finally, one could simply truncate the ending points [5, 15] to a certain length before recording them, at the expense of dealing with additional false alarms arising from partial matches.We will not explain the details of the methods mentioned above, since readable descriptions may be found in [12, 13]. Let us just provide the explicit relation between the degree of truncation and the amount of online computation increased by the associated false alarms.Proposition 12.
Assume the use of the ending point truncation method in which the probability for two truncated randomly chosen DPs to be identical is1
/
r. Then, during the online phase of the perfect fuzzy rainbow tradeoff, one can expect to observe
(41)
t
l
m
r
∑
i
=
1
s
‍
(
1
-
F
¯
p
s
)
(
∑
k
=
i
+
1
s
‍
F
¯
c
r
,
k
)
/
s
F
¯
c
r
f
-
s
+
1
f
-
s
+
2
f
-
i
f
-
i
+
1
∑
k
=
1
i
‍
F
¯
c
r
,
k
extra invocations of the one-way function induced by truncation-related alarms.Proof.
The probability for thel  online chains that start from theith color for each precomputation matrix to be generated is given by Lemma 5. The probability for such a generated chain not to merge into the perfect fuzzy rainbow precomputation matrix is given by Lemma 7. The probability for a nonmerging online chain to cause a truncation-related alarm with any one of the truncated ending points is1
/
rand there aremof these ending points, each of which could require separate treatment. Each alarm will require(
F
¯
cr
,
1
+
⋯
+
F
¯
cr
,
i
)
titerations of the one-way function to resolve. Taking the  l  precomputation matrices into account, the claimed formula is a simple combination of the facts mentioned so far.The cost stated above can easily be checked to be ofΘ
(
t
2
s
2
(
m
/
r
)
)order. One can show, either by comparing this againstT
=
Θ
(
t
2
s
2
) or through heuristic arguments, that the additional cost of resolving alarms induced by the ending point truncation technique can be suppressed to a negligible level by having the truncation retain slightly more thanlog
⁡
mbits of information for each ending point. The arguments appearing in [12, 13] may then be repeated, almost word for word, to conclude that each entry of the perfect table fuzzy rainbow tradeoff can be recorded inlog
⁡
m
0
+
ɛbits, whereɛis a small positive integer.The final conclusion made in the previous paragraph has not appeared before in the literature for the perfect fuzzy rainbow tradeoff. However, this is an expected result that has been obtained through straightforward adaptations of the arguments given in [12, 13].


## 3.1. Number of Color Boundary Points

Let us consider a nonperfect fuzzy rainbow matrix created fromm
0starting points and its nonperfect DP submatricesD
M
i. For each0
≤
i
≤
s, the collection ofm
ipoints that form the boundaries of the nonperfect DP submatrices will be referred to as theithcolor boundary points of the nonperfect fuzzy rainbow matrix.Our previous work [9] stated the relation
(2)
|
D
M
i
|
=
m
i
t
and gave the iterative formula
(3)
m
i
m
0
=
m
i
-
1
m
0
2
1
+
1
+
2
(
(
F
msc
/
s
)
(
m
i
-
1
/
m
0
)
)
,
for computingm
i, whereF
msc
=
(
m
0
t
2
s
)
/
Nis the matrix stopping constant for the nonperfect fuzzy rainbow matrix. The work also derived the closed-form approximation
(4)
m
i
=
2
m
0
2
+
F
msc
(
i
/
s
)
,
under the assumption thatsis large, and claimed this to be accurate for even smallsvalues. The claimed accuracy is verified once more through experiments for parameters of our interest in the Appendix, and we will assume (4) is sufficiently accurate for the purpose of this work in the remainder of this paper.Let us rewrite (4) in terms of the perfect fuzzy rainbow tradeoff parameters, so that the expression is more suitable for this work.Lemma 1.
To create a perfect fuzzy rainbow matrix containingmnonmerging chains, one must expect to generatem
0
=
(
2
/
(
2
-
F
¯
m
s
c
)
)
mchains. Furthermore, the number ofith color boundary points in the nonperfect fuzzy rainbow matrix generated during this process is expected to be
(5)
m
i
=
2
m
(
2
-
F
¯
m
s
c
)
+
F
¯
m
s
c
(
i
/
s
)
,
fori
=
0,1
,
…
,
s.Proof.
Substitutingi
=
sinto (4), we know that a nonperfect fuzzy rainbow matrix created withm
0starting points is expected to containm
s
=
(
2
/
(
2
+
F
msc
)
)
m
0nonmerging chains, whereF
msc
=
(
m
0
t
2
s
)
/
N. The requirement ofm
=
m
s
=
(
2
/
(
2
+
F
msc
)
)
m
0may be written as
(6)
F
¯
msc
=
2
F
msc
2
+
F
msc
.
Solving this equation forF
msc, we can rewrite it as
(7)
F
msc
=
2
F
¯
msc
2
-
F
¯
msc
,
which is equivalent to the first statement of this lemma. Substituting the first claim and the above equation into (4), we find
(8)
m
i
=
2
(
2
/
(
2
-
F
¯
msc
)
)
m
2
+
(
(
2
F
¯
msc
/
(
2
-
F
¯
msc
)
)
(
i
/
s
)
)
,
and this is the second claim of this lemma.The first two displayed equations appearing in this proof both imply thatF
¯
msc
<
2is always satisfied, which is similar to the situation with perfect rainbow tradeoffs. The reader may have guessed that takingF
¯
mscvery close to2corresponds to making bad parameter choices. In fact, we will later observe in Section 4.4 thatF
¯
mscis bounded sufficiently away from2for any meaningful parameters and that the precomputation requirement grows unrealistically large asF
¯
mscapproaches2.Because of its frequent appearances in the remainder of this section, we will introduce the notation(9)
f
-
i
=
m
i
t
2
N
=
2
F
¯
msc
(
2
-
F
¯
msc
)
+
F
¯
msc
(
i
/
s
)
1
s
.
When a smallsis in use, the symbolf
-
ishould be understood as designating the middle term, with the second equality interpreted as an approximation. However, we will mostly take the final term as the definition off
-
i, assumingsto be sufficiently large, and use this notation even fori
=
s
+
1andi
=
s
+
2. SinceF
¯
mscis bounded away from2for all practical parameter sets, we may assumef
-
ito be ofΘ
(
1
/
s
)order. Our use of the lower case letterf
-, rather thanF
¯, is meant to serve as a reminder thatf
-
iis not ofΘ
(
1
)order.One can directly verify from the definition that(10)
f
-
i
f
-
j
=
1
+
j
-
i
2
f
-
i
=
1
1
+
(
(
(
i
-
j
)
/
2
)
f
-
j
)
.
Combination of the middle expression with the knowledge off
-
i
=
Θ
(
1
/
s
)implies(
f
-
i
/
f
-
j
)
=
Θ
(
1
), forj
≥
i, and the right-hand side expression similarly implies the same claim, fori
≥
j.


## 3.2. Probability of Success

An expression for the probability of success of the perfect fuzzy rainbow tradeoff is obtained in this subsection. We first define and present a formula for theprecomputation coefficient of the algorithm.Proposition 2.
The precomputation phase of the perfect table fuzzy rainbow tradeoff is expected to requireF
¯
p
c
N  iterations of the one-way function, where the precomputation coefficient is
(11)
F
¯
p
c
=
l
t
∑
i
=
0
s
-
1
‍
2
F
¯
m
s
c
(
2
-
F
¯
m
s
c
)
+
F
¯
m
s
c
(
i
/
s
)
1
s
.Proof.
Since each DP chain is expected to be of lengtht, on average, the computation of each temporary submatrixD
M
~
ifrom itsm
i
-
1distinct starting points requiresm
i
-
1
titerations of the one-way function. The effort of sorting the ending points ofD
M
~
i, so that duplicates can be removed and the distinct starting points for the next submatrix are obtained, is of m
log
⁡
⁡
m order, which is much smaller than the effort of generating the submatrix, and can be ignored. Taking account of the  l  tables, the cost of precomputation can be stated as
(12)
(
m
0
+
m
1
+
⋯
+
m
s
-
1
)
t
l
.
Applying Lemma 1, we can write this as
(13)
t
l
∑
i
=
0
s
-
1
‍
2
m
(
2
-
F
¯
msc
)
+
F
¯
msc
(
i
/
s
)
to obtain the claimed formula.Let us use the notation(14)
F
¯
cr
,
i
=
|
D
M
¯
i
|
m
t
,
where|
D
M
¯
i
|denotes the number of distinct points expected in theith submatrix of a perfect fuzzy rainbow matrix, and define thecoverage rate of a perfect fuzzy rainbow matrix to be
(15)
F
¯
cr
=
1
m
t
s
∑
i
=
1
s
‍
|
D
M
¯
i
|
=
1
s
∑
i
=
1
s
‍
F
¯
cr
,
i
.
Note that the definitions allow us to expect bothF
¯
cr
,
iandF
¯
crto be ofΘ
(
1
)order.The coverage rate (15) of a perfect fuzzy rainbow matrix may be computed fromsandF
¯
mscthrough the following formula.Lemma 3.
The coverage rate of the DP submatrixD
M
¯
iis given by
(16)
F
¯
c
r
,
i
=
2
N
m
i
t
2
ln
⁡
(
1
+
m
i
t
2
2
N
)
=
2
f
-
i
ln
⁡
(
1
+
f
-
i
2
)
.Proof.
Recall thatD
M
¯
iis a subcollection of the chains appearing inD
M
~
i. Note that the selection of chains fromD
M
~
ito be retained inD
M
¯
idepends on the behavior of the chains that extend out from the ending points ofD
M
~
iand is independent of theith submatrix itself. In other words, the chains ofD
M
¯
ihave been selected at random from the chains ofD
M
~
i. Hence, the averages of chain lengths contained inD
M
~
iandD
M
¯
iwill be the same, and we can make the crucial observation that
(17)
F
¯
cr
,
i
=
|
D
M
¯
i
|
m
t
=
|
D
M
~
i
|
m
i
t
.
In other words, the coverage rate ofD
M
¯
iis equal to the coverage rate ofD
M
~
i.
Now, recall that eachD
M
~
iis simply a normal perfect DP matrix and also recall from [13] that the coverage rate of a perfect DP matrixD
¯
crmay be computed as
(18)
D
¯
cr
=
2
D
¯
msc
ln
⁡
⁡
(
1
+
D
¯
msc
2
)
,
whereD
¯
msc
=
m
′
t
2
/
Nis the matrix stopping constant for the perfect DP matrix ofm
′ending points. Thus we can write
(19)
F
¯
cr
,
i
=
2
m
i
t
2
/
N
ln
⁡
⁡
(
1
+
m
i
t
2
/
N
2
)
,
as claimed.We are now ready to state the success probability of the perfect fuzzy rainbow tradeoff as a function of the algorithm parameters.Proposition 4.
Consider an input to the one-way function that is chosen uniformly at random from the input space. Given the image of this input under the one-way function as the inversion target, the online phase of the perfect table fuzzy rainbow tradeoff will succeed in recovering the original input with probability(20)
F
¯
p
s
=
1
-
exp
⁡
(
-
F
¯
m
s
c
F
¯
c
r
l
t
)
.Proof.
The probability of success one can expect from the online processing of a single DP submatrixD
M
¯
iis|
D
M
¯
i
|
/
N. Since the submatrices were generated by different reduction functions, we may treat them as being independent. Thus, the probability of success for the complete online phase, taking all the l tables into account, may be written as
(21)
F
¯
ps
=
1
-
∏
i
=
1
s
‍
(
1
-
|
D
M
¯
i
|
N
)
l
=
1
-
∏
i
=
1
s
‍
(
1
-
F
¯
msc
F
¯
cr
,
i
t
s
)
l
.
This can be approximated by
(22)
F
¯
ps
=
1
-
exp
⁡
⁡
(
-
F
¯
msc
∑
i
=
1
s
‍
F
¯
cr
,
i
l
t
s
)
=
1
-
exp
⁡
(
-
F
¯
msc
F
¯
cr
l
t
)
,
as claimed.Given any set of parameters, one can compute the success rate by combining the above formula with definition (15), Lemma 3, and notation (9). More precisely, the success rate may be seen as a function ofF
¯
msc,l
/
t, ands, rather than as a function of the more basic constant and parameters  N, m, t, l, ands.The proposition also shows that one can fix positive integersandF
¯
msc
<
2to any value and still attain any success rate requirementF
¯
psby adhering to the relation
(23)
l
t
=
{
-
ln
⁡
(
1
-
F
¯
ps
)
}
F
¯
msc
F
¯
cr
.
Note that this implies that, unless the requirement for the probability of successF
¯
psis unrealistically close to1, we will have  l
/
t
=
Θ
(
1
). In other words, the parameters  l  and  t  will be of the same order.


## 3.3. Online Complexity

The time memory tradeoff curve for the perfect fuzzy rainbow tradeoff is obtained in this subsection through a careful computation of the average case online execution complexities. This is the most complicated part of this paper.We start by assessing how likely each step of the online phase is to be executed.Lemma 5.
The probability for an online chain that starts from theith color of a perfect fuzzy rainbow matrix to be generated, that is, the probability for theith DP submatrixD
M
¯
ito be searched for the correct answer, is
(24)
exp
⁡
(
-
F
¯
m
s
c
l
t
1
s
∑
k
=
i
+
1
s
‍
F
¯
c
r
,
k
)
=
(
1
-
F
¯
p
s
)
(
∑
k
=
i
+
1
s
‍
F
¯
c
r
,
k
)
/
s
F
¯
c
r
,
whereF
¯
p
sis as given by Proposition 4.Proof.
The online chain that starts from theith color of a perfect fuzzy rainbow matrix will be generated if and only if the correct answer to the inversion target does not belong to the submatricesD
M
¯
i
+
1
,
…
,
D
M
¯
scontained in the  l  perfect fuzzy rainbow matrices. Hence, the probability under consideration is
(25)
∏
k
=
i
+
1
s
‍
(
1
-
|
D
M
¯
k
|
N
)
l
=
exp
⁡
(
-
F
¯
msc
l
t
1
s
∑
k
=
i
+
1
s
‍
F
¯
cr
,
k
)
.
The equality claimed in the lemma statement follows from an application of Proposition 4.The cost of generating the online chains is a direct corollary to this lemma. It suffices to realize that an online chain that starts from theith color is expected to be of lengtht
(
s
-
i
+
1
)and that there are  l  tables to consider.Proposition 6.
The generation of the online chains for the perfect fuzzy rainbow tradeoff is expected to require(26)
t
l
∑
i
=
1
s
‍
(
s
-
i
+
1
)
(
1
-
F
¯
p
s
)
(
∑
k
=
i
+
1
s
‍
F
¯
c
r
,
k
)
/
s
F
¯
c
r
iterations of the one-way function.Our next goal is to obtain the cost of resolving alarms that appear during the online phase. This part calls for very delicate arguments involving random functions and is very technical. The practice-oriented reader can skip the following few lemmas and jump to Proposition10.We will consider an online chain that starts from theith color and treat the case of it merging into the fuzzy rainbow matrix within theith color and the case of it merging at a strictly later color separately. As a preliminary result, we require the probability for an online chain to merge into a fuzzy rainbow matrix.Lemma 7.
An online DP chain segment of theith color will not merge into thenonperfect DP submatrixD
M
iwith probability(
1
/
(
1
+
f
-
i
)
)
=
(
f
-
i
+
2
/
f
-
i
). The probability for an online chain that starts from theith color not to merge into theperfect fuzzy rainbow precomputation matrix is∏
k
=
i
s
‍
(
1
/
(
1
+
f
-
k
)
)
=
(
f
-
s
+
1
/
f
-
i
)
(
f
-
s
+
2
/
f
-
i
+
1
).Proof.
An online DP chain segment of theith color will escape merging into the nonperfect DP submatrixD
M
iwith probability
(27)
∑
k
=
1
∞
‍
(
1
-
1
t
-
|
D
M
i
|
N
)
k
-
1
(
1
t
-
m
i
N
)
=
1
-
(
t
m
i
/
N
)
1
+
(
t
|
D
M
i
|
/
N
)
≈
1
1
+
(
t
|
D
M
i
|
/
N
)
,
where the approximation is justified by the facts(
t
m
i
/
N
)
=
Θ
(
1
/
t
s
)and(
t
|
D
M
i
|
/
N
)
=
Θ
(
1
/
s
). Substituting (2) into this expression and then applying (9), the probability can be written as
(28)
1
1
+
f
-
i
=
(
2
-
F
¯
msc
)
+
F
¯
msc
(
i
/
s
)
(
2
-
F
¯
msc
)
+
F
¯
msc
(
(
i
+
2
)
/
s
)
=
f
-
i
+
2
f
-
i
.
The probabilities for an online chain to merge intoD
M
¯
kandD
M
kare usually different, but the two are the same whenk
=
s. Now, an online chain that starts from theith color does not merge into the perfect precomputation matrix if and only if none of its DP chain segments merge into the submatricesD
M
¯
i
,
D
M
¯
i
+
1
,
…
,
D
M
¯
s, and this happens if and only if the online DP chain segments do not merge into the nonperfect submatricesD
M
i
,
D
M
i
+
1
,
…
,
D
M
s. Here, we emphasize that a series of submatrices ending at the terminalsth color is being considered. The claimed probability is the product of the term(
1
/
(
1
+
f
-
k
)
)
=
(
(
f
-
k
+
2
)
/
f
-
k
)overk
=
i
,
…
,
s.The following lemma gives the cost of dealing with an alarm from a possible delayed merge, assuming the generation of an online chain that starts from theith color.Lemma 8.
Consider a single perfect fuzzy rainbow precomputation matrix and its associatedscolors. Assume the generation of an online chain for this matrix that starts from theith color. The cost of resolving an alarm that may be induced by a possible merge of this online chain into the fuzzy rainbow matrix strictly after theith color is expected to be
(29)
t
(
∑
k
=
1
i
‍
F
¯
c
r
,
k
)
{
f
-
i
+
2
f
-
i
(
1
-
f
-
s
+
1
f
-
i
+
1
f
-
s
+
2
f
-
i
+
2
)
+
(
1
-
f
-
i
+
2
f
-
i
)
(
1
-
f
-
s
f
-
i
)
}
iterations of the one-way function.Proof.
We require the probability for an online chain that starts from theith color to merge into the perfect fuzzy rainbow precomputation matrix without merging into the submatrixD
M
¯
i. Such a merge could occur through the following two separate events. (a) Theith color online DP chain segment does not merge into the nonperfect submatrixD
M
i, but the online chain part that extends out from the ending DP of theith color segment merges into the perfect precomputation matrix. (b) Theith color online chain merges intoD
M
i, without merging intoD
M
¯
i, in which case the online chain is destined to merge into the perfect precomputation matrix at a later color.
If theith color online DP chain segment does not merge intoD
M
i, the chain that extends from its ending point may still be iterated with a random function. Hence, it is clear from Lemma 7 that the probability for the (a)-event to occur is
(30)
f
-
i
+
2
f
-
i
(
1
-
f
-
s
+
1
f
-
i
+
1
f
-
s
+
2
f
-
i
+
2
)
.
On the other hand, the extended part of the online chain is allowed no randomness in the (b)-event. We already know from the proof of Lemma3 that an ending point ofD
M
i, that is, an ending point ofD
M
~
i, has probability(
m
s
/
m
i
)
=
(
f
-
s
/
f
-
i
)of remaining among the ending points ofD
M
¯
i. Once again, Lemma 7 allows us to claim
(31)
(
1
-
f
-
i
+
2
f
-
i
)
(
1
-
f
-
s
f
-
i
)
as the probability for the (b)-event to occur. The probability for a merge to appear strictly after theith color is the sum of the above two probabilities.
A merge of the online chain into the precomputation matrix that appears strictly after theith color requires one to regenerate the associated precomputation chain up to the end of theith color. Note that (14) allows us to write the average chain length|
D
M
¯
i
|
/
mof each DP submatrixD
M
¯
iasF
¯
cr
,
i
t. Hence, to resolve the alarm from the merge discussed above, one must expect to compute(
F
¯
cr
,
1
+
⋯
+
F
¯
cr
,
i
)
titerations of the one-way function.
The claimed cost of resolving alarms is a simple product of the merge probability and the work factor we have already stated.The cost of dealing with an immediate merge of the online chain into the perfect precomputation matrix is given next.Lemma 9.
Consider a single perfect fuzzy rainbow precomputation matrix and its associatedscolors. Assume the generation of an online chain for this matrix that starts from theith color. The cost of resolving an alarm that may be induced by a possible merge of this online chain into the fuzzy rainbow matrix within theith color segment is expected to be approximately
(32)
t
(
1
+
∑
k
=
1
i
‍
F
¯
c
r
,
k
)
(
1
-
f
-
i
+
2
f
-
i
)
f
-
s
f
-
i
iterations of the one-way function.Proof.
Arguments given in the proof of Lemma8 already show that the probability for a merge to occur within theith color segment into the perfect DP submatrix is
(33)
(
1
-
f
-
i
+
2
f
-
i
)
f
-
s
f
-
i
.
Since the online chain will merge into at most one precomputation chain inD
M
¯
i, it only remains to find out how much work is required to resolve such a merge.
An alarm will require the associated precomputation chain to be regenerated at least up to the start of theith DP submatrix, and we saw during the proof of Lemma 8 that this costs(
F
¯
cr
,
1
+
⋯
+
F
¯
cr
,
i
-
1
)
titerations of the one-way function. The number of additionalith color segment iterations that are required must be handled more carefully. One can expect this to be larger thanF
¯
cr
,
i
t, because longer precomputation chains are more likely to be involved in merges.
The work [12] stated in its Lemma 12 that the cost of resolving alarms expected from the processing of a single nonperfect DP table is2
D
msc
titerations of the one-way function, whereD
mscis the matrix stopping constant of the nonperfect DP matrix. Following the arguments given in the proof of the same lemma, one can write the number of false alarms expected during the processing of a single DP table as
(34)
D
msc
∫
0
∞
‍
∫
0
∞
‍
exp
⁡
⁡
(
-
u
)
exp
⁡
(
-
v
)
{
exp
⁡
⁡
(
min
⁡
(
u
,
v
)
)
-
1
}
d
u
d
v
=
D
msc
.
Computing the ratio of these two numbers, we can conclude that, during the processing of a single nonperfect DP table, each alarm calls for2
titerations of the one-way function to resolve, on average.
Now, since (10) implies that(
m
i
/
m
i
-
1
)
=
1
-
Θ
(
1
/
2
s
), we know that only a small portion ofD
M
iis discarded in creatingD
M
~
i, so that the DP matricesD
M
iandD
M
~
imust be similar in their distributions of chain lengths. We also saw during the proof of Lemma 3 that the selection ofD
M
¯
ifromD
M
~
idoes not affect the distribution of chain lengths. Hence, it is reasonable to expect a merge of the online chain within theith color segment into eitherD
M
iorD
M
¯
ito call for approximately2
titerations of theith colored one-way function, on average.
We wish to add a small tweak to the2
tclaim. Note that the average chain length of a nonperfect DP matrix ist, whereas that ofD
M
¯
iisF
¯
cr
,
i
t. Since the average chain length may be understood as a concise representation of the distribution of chain lengths, one might expect chain lengths, and one might expect2
F
¯
cr
,
i
t, which take the average chain length ofD
M
¯
iinto account, to be a better approximation of the additional work than2
t. In any case, since Lemma 3 implies thatF
¯
cr
,
i
=
1
-
Θ
(
1
/
4
s
), we know that2
tknow that2
tand2
F
¯
cr
,
i
tare very close to each other. In similarity, wechoose to take(
1
+
F
¯
cr
,
i
)
tas the number of extraith color iterations required, since this will make our later formulas look slightly simpler.
The claimed cost of resolving alarms is a simple combination of the three factors(
1
-
(
f
-
i
+
2
/
f
-
i
)
)
(
f
-
s
/
f
-
i
),(
F
¯
cr
,
1
+
⋯
+
F
¯
cr
,
i
-
1
)
t, and(
1
+
F
¯
cr
,
i
)
tthat we have discussed so far.Combining Lemmas8 and 9, we can state that the cost of dealing with an alarm that may be induced by an online chain generated from theith color is
(35)
t
{
(
∑
k
=
1
i
‍
F
¯
cr
,
k
)
(
1
-
f
-
s
+
1
f
-
i
f
-
s
+
2
f
-
i
+
1
)
+
f
-
i
+
2
f
-
i
f
-
s
}
,
where we have relied on (10) to replace(
1
-
(
f
-
i
+
2
/
f
-
i
)
)
(
f
-
s
/
f
-
i
)with(
f
-
i
+
2
/
f
-
i
)
f
-
s. Since, unlike other results of this paper, we have stated Lemma 9 only as an approximation, let us briefly explain that this is still very accurate. Using relation (10) and the rough approximations∑
k
=
1
i
F
¯
cr
,
k
=
Θ
(
i
)andf
-
i
=
Θ
(
1
/
s
), it is easy to verify the facts
(36)
(
∑
k
=
1
i
‍
F
¯
cr
,
k
)
(
1
-
f
-
s
+
1
f
-
i
f
-
s
+
2
f
-
i
+
1
)
=
Θ
(
i
(
s
-
i
+
1
)
s
)
,
f
-
i
+
2
f
-
i
f
-
s
=
Θ
(
1
s
)
.
This shows that, unlesssis very small, the first factor of (35) is at leaststimes larger than the second factor. On the other hand, the proof of Lemma 9 shows that the error given by formula (35) will be more than sufficiently bounded by its second factor. Hence, we can expect (35) to be accurate up to a1
+
O
(
1
/
s
)factor, at the worst. In fact, our testing to be presented in the Appendix confirms that the accuracy of (35) is much higher than what we have claimed here.The computational cost of dealing with the alarms is now a direct corollary to Lemmas5, 8, and 9.Proposition 10.
The treatment of alarms during the online phase of a perfect fuzzy rainbow tradeoff is expected to require(37)
t
l
∑
i
=
1
s
‍
(
1
-
F
¯
p
s
)
(
∑
k
=
i
+
1
s
‍
F
¯
c
r
,
k
)
/
s
F
¯
c
r
×
{
(
∑
k
=
1
i
‍
F
¯
c
r
,
k
)
(
1
-
f
-
s
+
1
f
-
i
f
-
s
+
2
f
-
i
+
1
)
+
f
-
i
+
2
f
-
i
f
-
s
}
iterations of the one-way function.The online computational complexity of the perfect fuzzy rainbow tradeoff can be stated as the sum(38)
T
=
t
l
s
∑
i
=
1
s
‍
(
1
-
F
¯
ps
)
(
∑
k
=
i
+
1
s
‍
F
¯
cr
,
k
)
/
s
F
¯
cr
×
(
(
∑
k
=
1
i
‍
F
¯
cr
,
k
s
)
(
1
-
f
-
s
+
1
f
-
i
f
-
s
+
2
f
-
i
+
1
)
s
-
i
+
1
s
+
1
s
f
-
i
+
2
f
-
i
f
-
s
+
(
∑
k
=
1
i
‍
F
¯
cr
,
k
s
)
(
1
-
f
-
s
+
1
f
-
i
f
-
s
+
2
f
-
i
+
1
)
)
of its two components stated by Propositions 6 and 10. Recalling from the discussion given under (23) that(
l
/
t
)
=
Θ
(
1
), it is easy to argue thatTis ofΘ
(
t
2
s
2
)order. The following time memory tradeoff curve is a direct consequence of our knowledge secured of the online time complexityTand the observation that the storage complexity isM
=
m
l.Theorem 11.
The time memory tradeoff curve for the perfect table fuzzy rainbow tradeoff isT
M
2
=
F
¯
t
c
N
2, where the tradeoff coefficient is
(39)
F
¯
t
c
=
F
¯
m
s
c
2
(
l
t
)
3
1
s
∑
i
=
1
s
‍
(
1
-
F
¯
p
s
)
(
∑
k
=
i
+
1
s
‍
F
¯
c
r
,
k
)
/
s
F
¯
c
r
×
(
s
-
i
+
1
s
+
1
s
f
-
i
+
2
f
-
i
f
-
s
11111
+
(
∑
k
=
1
i
‍
F
¯
c
r
,
k
s
)
(
1
-
f
-
s
+
1
f
-
i
f
-
s
+
2
f
-
i
+
1
)
)
.As a corollary to Lemma5, we can state that the online phase of the perfect table fuzzy rainbow tradeoff is expected to call for
(40)
l
∑
i
=
1
s
‍
(
1
-
F
¯
ps
)
(
∑
k
=
i
+
1
s
‍
F
¯
cr
,
k
)
/
s
F
¯
cr
lookups to the precomputation table. One can easily verify that this is ofΘ
(
t
s
)order, which is much smaller than the online computational complexityT
=
Θ
(
t
2
s
2
).


## 3.4. Storage Optimization

The storage complexityM appearing in the tradeoff curve of Theorem 11 refers to the total number of entries that need to be stored in the precomputed tables. However, practical interest would be in the size of the required physical recording media expressed in number of bits. Hence, we need to discuss the number of bits occupied by each starting and ending point pair in the tables.The naive approach would allocate2
log
⁡
N  bits to each table entry, but there are more efficient methods. Each starting point can be recorded inlog
⁡
m
0bits [14–16] through the use of consecutive starting points. In storing the ending points, one need not record bits that can be recovered from the definition of the distinguishing property [15, 17]. One can create an index table [15] for each sorted table and remove almost log
⁡
⁡
m most significant bits from each ending point. Finally, one could simply truncate the ending points [5, 15] to a certain length before recording them, at the expense of dealing with additional false alarms arising from partial matches.We will not explain the details of the methods mentioned above, since readable descriptions may be found in [12, 13]. Let us just provide the explicit relation between the degree of truncation and the amount of online computation increased by the associated false alarms.Proposition 12.
Assume the use of the ending point truncation method in which the probability for two truncated randomly chosen DPs to be identical is1
/
r. Then, during the online phase of the perfect fuzzy rainbow tradeoff, one can expect to observe
(41)
t
l
m
r
∑
i
=
1
s
‍
(
1
-
F
¯
p
s
)
(
∑
k
=
i
+
1
s
‍
F
¯
c
r
,
k
)
/
s
F
¯
c
r
f
-
s
+
1
f
-
s
+
2
f
-
i
f
-
i
+
1
∑
k
=
1
i
‍
F
¯
c
r
,
k
extra invocations of the one-way function induced by truncation-related alarms.Proof.
The probability for thel  online chains that start from theith color for each precomputation matrix to be generated is given by Lemma 5. The probability for such a generated chain not to merge into the perfect fuzzy rainbow precomputation matrix is given by Lemma 7. The probability for a nonmerging online chain to cause a truncation-related alarm with any one of the truncated ending points is1
/
rand there aremof these ending points, each of which could require separate treatment. Each alarm will require(
F
¯
cr
,
1
+
⋯
+
F
¯
cr
,
i
)
titerations of the one-way function to resolve. Taking the  l  precomputation matrices into account, the claimed formula is a simple combination of the facts mentioned so far.The cost stated above can easily be checked to be ofΘ
(
t
2
s
2
(
m
/
r
)
)order. One can show, either by comparing this againstT
=
Θ
(
t
2
s
2
) or through heuristic arguments, that the additional cost of resolving alarms induced by the ending point truncation technique can be suppressed to a negligible level by having the truncation retain slightly more thanlog
⁡
mbits of information for each ending point. The arguments appearing in [12, 13] may then be repeated, almost word for word, to conclude that each entry of the perfect table fuzzy rainbow tradeoff can be recorded inlog
⁡
m
0
+
ɛbits, whereɛis a small positive integer.The final conclusion made in the previous paragraph has not appeared before in the literature for the perfect fuzzy rainbow tradeoff. However, this is an expected result that has been obtained through straightforward adaptations of the arguments given in [12, 13].


## 4. Algorithm Comparison

This section may be slightly difficult to understand in full if the reader is unfamiliar with the approach that was recently introduced by [12] to compare different tradeoff algorithms and its further developments made by [13, 18]. However, we will refrain from providing lengthy repetitive explanation and justification of the comparison approach and ask the more interested reader to refer to the cited articles.


### 4.1. Overview of the Comparison Method

Recall that the conclusion of [13], in overly simplified terms, was that the perfect rainbow tradeoff algorithm is superior to all the other widely known tradeoff algorithms. Also recall from our recent work [9] that the nonperfect version of the fuzzy rainbow tradeoff, which is not yet widely known, is preferable to the perfect rainbow tradeoff when one is constrained in precomputation resources. Hence, we wish to compare the performance of the perfect fuzzy rainbow tradeoff, which we have analyzed in this paper, against those of the perfect rainbow and the nonperfect fuzzy rainbow tradeoffs.In the remainder of this paper, we will use symbolsR
¯andFto extend the notation we had been using concerning the perfect fuzzy rainbow tradeoff to the perfect rainbow and nonperfect fuzzy rainbow tradeoffs, and we will use the symbol  X  when we wish to reference a coefficient without making the tradeoff algorithm specific. For example, symbolsR
¯
tcandF
tcdenote the tradeoff coefficients for the perfect rainbow and nonperfect fuzzy rainbow tradeoffs, respectively, andX
tcrefers to any tradeoff coefficient. The symbolsF
¯,R
¯, andFwill also be used as inm
F
¯,m
R
¯, andm
Fto clarify that the parameter or some complexity value is to be associated with a certain algorithm.We will follow the approach of [12] in comparing the performances of different tradeoff algorithms against each other. In short, a small number of success rate requirementsX
pswill be chosen, and a graph for each algorithm, displaying the upper level tradeoff between itsprecomputation cost andonline cost, will be plotted. The overall relative positions of the curves corresponding to different algorithms, subject to the sameX
ps, will allow certain conclusions to be made concerning algorithm performances. The curves themselves will also be of value when choosing algorithm parameters for implementation.It is clear that the precomputation costPof a tradeoff algorithm can be numerically represented in full by the precomputation coefficientX
pc
=
(
P
/
N
). In the perfect fuzzy rainbow tradeoff case, this can be computed from Proposition 2, and the corresponding results for our two comparison target algorithms can be found in [9, 13]. Note thatX
pcpresents the computational cost as the number of iterations, in multiplies of  N, required of the common target one-way function, regardless of the tradeoff algorithm.The online cost or efficiency of a tradeoff algorithm is mostly captured by its tradeoff coefficient. However, since theMappearing in the definitionX
tc
=
T
M
2
/
N
2represents the number of table entries, rather than the physical number of bits required to store the tables, the tradeoff coefficient cannot be used directly in comparing different algorithms. One must first adjustX
tcto account for the differences in number of bits required per table entry by the algorithms being compared. For example, the comparison of the nonperfect DP and rainbow tradeoffs by [12] was carried out with therelatively adjusted tradeoff coefficients(
1
/
4
)
D
tcandR
tc. The adjustment factor(
1
/
2
)
2reflects the fact that the DP tradeoff requires roughly half as many bits to store each precomputation table entry in comparison to the rainbow tradeoff, under parameter choices that are typically considered during theoretical analyses of the tradeoff algorithms.


### 4.2. Tradeoff Coefficient Adjustment

We wish to be slightly more careful in treating the tradeoff coefficient adjustment factors than focusing on just the theoretically typical parameters. In general, as a trivial extension of the approach given by [12], one can use theadjusted tradeoff coefficient
(42)
X
atc
=
(
3
2
log
⁡
N
)
2
(
number
of
bits
per
table
entry
for
X
)
2
X
tc
to represent the online cost of each algorithm, and plot theX
pcversusX
atccurves to obtain a fair comparison of different algorithms. Here, the constant(
3
/
(
2
log
⁡
N
)
)
2serves the purpose of bringing the adjustment factor toΘ
(
1
)order at typical parameters and is not an essential factor for the purpose of comparisons. The tradeoff coefficientsF
¯
tc,R
¯
tc, andF
tcmay be computed from Theorem 11 and the corresponding results from [9, 13], but more work is required before we can specify thenumber of bits part more concretely for each algorithm.Recalling the contents of Section3.4 and Lemma 1, the adjusted tradeoff coefficient for the perfect fuzzy rainbow tradeoff may be written more concretely in terms of algorithm parameters as
(43)
F
¯
atc
=
(
3
2
log
⁡
N
)
2
(
log
⁡
2
2
-
F
¯
msc
+
log
⁡
m
F
¯
+
ɛ
)
2
F
¯
tc
.
Referring to results from [9, 13], it is not difficult to work out similar adjustment factors for the perfect rainbow and nonperfect fuzzy rainbow tradeoffs to claim
(44)
R
¯
atc
=
(
3
2
log
⁡
N
)
2
(
log
⁡
2
l
R
¯
2
l
R
¯
+
ln
⁡
⁡
(
1
-
R
¯
ps
)
+
log
⁡
m
R
¯
+
ɛ
)
2
R
¯
tc
,
(45)
F
atc
=
(
3
2
log
⁡
N
)
2
(
log
⁡
m
F
+
ɛ
)
2
F
tc
as the more concrete expressions.The small positive integerɛcorresponds to the number of ending point bits remaining after applications of the truncation and index file techniques. Working with Proposition 12 and corresponding results from [13, 18], one can reasonably argue thatɛfor the three algorithms can be set to a common value, which is why we have not subscripted them with the algorithm symbols. The terms involvingF
¯
mscandl
R
¯, appearing in (43) and (44), have their roots in the merge removal process for producing perfect tables and reflect what fraction of the initially generated chains remains in the perfect table. Since theX
pc-X
atccurves are to be plotted usingF
¯
mscandl
R
¯as parameters, the existence of these terms will not cause any later difficulties. However, the threelog
⁡
mvalues require further attention.Note that one cannot hope to simply make independentlog
⁡
mvalue choices that achieveoptimality for each algorithm, since optimality cannot be defined objectively. The most favorable balance between precomputation costP, storage costM, and expected online inversion timeTis a subjective matter that would be different for every implementer and situation. For our algorithm comparison to be fair, the valueslog
⁡
m
F
¯,log
⁡
m
R
¯, andlog
⁡
m
Fneed to be left as choices to be made by the implementer. Nevertheless, we can still restrict the three choices to be made in a reasonably correlated manner. The natural approach is to correlate the choices through the requirement that theP,M, andTcomplexities for the three algorithms be made roughly comparable and with the strict restriction that the success rates of the three algorithms be identical. Since the performances of the three algorithms commonly satisfyT
M
2
≈
N
2, if an implementer under a specific situation is asked to produce parameters sets for the three algorithms that he deems favorable, his choices for the three algorithms would be roughly matching the performance figuresP,M, andT.Let us now choose to view each positive integersas presenting a separate version of the perfect fuzzy rainbow algorithm. That is, we treat the perfect fuzzy rainbow tradeoff as a series of infinitely many different algorithms. A similar view will be taken of the nonperfect fuzzy rainbow algorithm. Below, we will describe a rule for correlating the parameter sets among these two infinite series of algorithms and the perfect rainbow tradeoff algorithm, for each fixed common probability of successX
ps.We first take integersm
⋆andt
⋆such thatlog
⁡
m
⋆
+
2
log
⁡
t
⋆
≈
log
⁡
N  and set the perfect fuzzy rainbow parameters to
(46)
m
F
¯
,
s
≈
s
m
⋆
,
t
F
¯
,
s
≈
t
⋆
s
,
l
F
¯
,
s
=
-
ln
⁡
(
1
-
X
ps
)
F
¯
msc
F
¯
cr
t
F
¯
,
s
,
for eachs
≥
1, where the coverage rateF
¯
cr, corresponding to eachs, is to be computed through (9), Lemma 3, and (15). The perfect rainbow tradeoff parameters corresponding to the above are set to
(47)
m
R
¯
≈
m
⋆
t
⋆
,
t
R
¯
≈
t
⋆
,
l
R
¯
=
-
ln
⁡
(
1
-
X
ps
)
R
¯
msc
,
whereR
¯
msc
=
(
m
R
¯
t
R
¯
/
N
), and in such a way thatl
R
¯ is an integer. Finally, the nonperfect fuzzy rainbow parameters are set to
(48)
m
F
,
s
≈
s
m
⋆
,
t
F
,
s
≈
t
⋆
s
,
l
F
,
s
=
-
ln
⁡
(
1
-
X
ps
)
F
msc
F
cr
t
F
,
s
,
for eachs
≥
1, whereF
msc
=
(
m
F
,
s
t
F
,
s
2
s
/
N
)andF
cris the coverage rate for the nonperfect fuzzy rainbow tradeoff.Note that the requirementlog
⁡
m
⋆
+
2
log
⁡
t
⋆
≈
log
⁡
N does not affect the implementer’s control over theP-T-Mtradeoff in any way. Further note that one has sufficient control overF
¯
msc,l
R
¯, andF
msc, even whenlog
⁡
m
⋆andlog
⁡
t
⋆are fixed to approximate values. That is, one can vary theX
pc-X
tccurve parametersF
¯
msc,l
R
¯, andF
mscquite freely while keeping all thelog
⁡
m
Xvalues somewhat stable.Using (23) and similar claims from [9, 13], it is trivial to verify that all parameter sets achieve the same success rateX
ps. It is also easy to verify, using the factsP
F
¯
=
Θ
(
m
F
¯
t
F
¯
2
s
F
¯
),T
F
¯
=
Θ
(
t
F
¯
2
s
F
¯
2
), andM
F
¯
=
Θ
(
m
F
¯
t
F
¯
)and the corresponding facts from [9, 13], that the performance figuresP,M, andTare of similar order for all the above parameter sets. In fact, it is possible to argue that the above method is the only possible manner in which comparableP,T, andMcomplexities can be achieved by the different algorithms at a common success rate.The reasonable association between the parameter sets for different algorithms given by (46), (47), and (48) allows the adjusted tradeoff coefficients to be written as
(49)
F
¯
atc
,
s
=
(
3
2
log
⁡
N
)
2
(
log
⁡
2
2
-
F
¯
msc
+
log
⁡
s
+
log
⁡
m
⋆
+
ɛ
)
2
F
¯
tc
,
s
,
(50)
R
¯
atc
=
(
3
2
log
⁡
N
)
2
×
(
log
⁡
2
l
R
¯
2
l
R
¯
+
ln
⁡
⁡
(
1
-
R
¯
ps
)
+
1
2
log
⁡
N
+
1
2
log
⁡
m
⋆
+
ɛ
)
2
R
¯
tc
,
(51)
F
atc
,
s
=
(
3
2
log
⁡
N
)
2
(
log
⁡
s
+
log
⁡
m
⋆
+
ɛ
)
2
F
tc
,
s
,
where we have relied onlog
⁡
N
≈
log
⁡
m
⋆
+
2
log
⁡
t
⋆in writing (50). We have also additionally subscripted the (adjusted) tradeoff coefficients with the parametersto make their dependence onsmore explicit.To compare the performances of different tradeoff algorithms, it now suffices to fixX
ps, choose reasonable values forlog
⁡
m
⋆
+
ɛandlog
⁡
N, and plot theX
pc-X
atccurves, for all the algorithms.


### 4.3. Choosing the Color Counts

Before comparing the perfect fuzzy rainbow tradeoff with the other two algorithms, we wish to make comparisons among the many versions of the perfect fuzzy rainbow tradeoff corresponding to differentschoices. A small number of theF
¯
pc-F
¯
atccurves are given in Figure 1.The adjusted tradeoff coefficientF
¯
atc
,
sin relation to precomputation coefficientF
¯
pc
,
s, for a small number ofsvalues, at success rate90
%and withlog
⁡
m
⋆
+
ɛfixed to21and33(bottom:F
¯
pc
,
s; left:F
¯
atc
,
s).
(a)
(b)The left-hand side box contains plots of the(
F
¯
pc
,
s
,
F
¯
tc
,
s
)points, for the case when the success rate is set to90
%andlog
⁡
m
⋆
+
ɛis set to21. Each of the three curves is for specificsvalues. The right-hand side box contains similar curves for theF
¯
ps
=
90
%andlog
⁡
m
⋆
+
ɛ
=
33case. Note thatɛ
=
8would be a reasonable value in view of the discussions given by Section 3.4 and thatlog
⁡
m
⋆
=
13andlog
⁡
m
⋆
=
25are choices that would typically be made during theoretical discussions of the tradeoff technique for the very small  N
=
2
39and the very large  N
=
2
75search space sizes. Hence, ourlog
⁡
m
⋆
+
ɛ
=
21andlog
⁡
m
⋆
+
ɛ
=
33examples are representative of the behaviors at both ends of the realistic tradeoff application environments.Each curve has been plotted precisely to its lowest point. The curve points that would appear to the right of a lowest point are meaningless, since they correspond to parameter sets that call for higher precomputation efforts while achieving lower online efficiencies than the parameter sets corresponding to the lowest point.One may roughly associate overall better performance with a curve that is closer to the lower left corner of each figure box. However, it can be seen that curves corresponding to differentsvalues may cross over each other. In fact, we could verify that the lowest curve in each box crosses over the middle curve appearing in its box at a highX
atcvalue. Hence, one cannot claim onesvalue to be providing definitely superior performance over anothersvalue, at least not strictly logically.Nevertheless, if we restrict our attention to the lower parts of the curves, which are of higher practical interest than the highX
atcparts, it becomes clear that little harm will be done by simplifying matters and ranking the performances for differentschoices based only on the lowest point of each curve. In other words, for practical purposes, it is sufficiently reasonable to declare ansvalue to be optimal for a specific(
F
¯
ps
,
log
⁡
m
⋆
+
ɛ
)pair if
(52)
min
⁡
F
¯
msc
⁡
{
F
¯
atc
,
s
}
=
min
⁡
i
≥
1
,
F
¯
msc
{
F
¯
atc
,
i
}
.
We emphasize that such a simplification is possible only because of the nice relative positions of the many curves and that the same simplification may not be applicable to other comparison situations.The optimal number of colorss, as defined through comparisons at the lowest points of the curves, is given by Table 1, for various success rate requirementsF
¯
psand a wide range oflog
⁡
m
⋆
+
ɛvalues. TheF
¯
mscvalue that attains the minimum possibleF
¯
atc
,
svalue is listed under each optimals.Table 1
Optimals for the perfect fuzzy rainbow tradeoff, at various F
-
ps and log
⁡
m
⋆
+
ε values. The F
-
msc value listed below each s attains the minimum F
-
atc,
s value.
log
⁡
m
⋆
+
ε
50%
75%
90%
95%
99%
99.5%
99.9%
18
s
34
38
43
48
60
66
79
F
-
msc
1.6880
1.6882
1.6846
1.6813
1.6697
1.6647
1.6531
19
s
36
40
46
50
63
68
83
F
-
msc
1.6999
1.6996
1.6967
1.6921
1.6810
1.6754
1.6644
20
s
37
42
48
53
65
71
86
F
-
msc
1.7095
1.7103
1.7071
1.7030
1.6910
1.6858
1.6747
21
s
39
44
50
55
68
74
89
F
-
msc
1.7198
1.7202
1.7167
1.7126
1.7008
1.6955
1.6843
22
s
41
46
52
57
71
77
93
F
-
msc
1.7294
1.7293
1.7256
1.7215
1.7101
1.7046
1.6936
23
s
43
48
54
59
73
80
96
F
-
msc
1.7382
1.7379
1.7339
1.7298
1.7183
1.7133
1.7021
24
s
45
50
56
62
76
83
100
F
-
msc
1.7465
1.7459
1.7418
1.7381
1.7264
1.7214
1.7105
25
s
47
51
58
64
79
86
103
F
-
msc
1.7542
1.7527
1.7492
1.7454
1.7340
1.7290
1.7180
26
s
49
53
60
66
81
89
106
F
-
msc
1.7615
1.7598
1.7562
1.7523
1.7410
1.7362
1.7252
27
s
51
55
63
69
84
91
110
F
-
msc
1.7684
1.7665
1.7633
1.7593
1.7478
1.7427
1.7322
28
s
52
57
65
71
87
94
113
F
-
msc
1.7740
1.7728
1.7695
1.7655
1.7543
1.7492
1.7387
29
s
54
59
67
73
89
97
116
F
-
msc
1.7801
1.7788
1.7754
1.7713
1.7602
1.7554
1.7448
30
s
56
61
69
75
92
100
120
F
-
msc
1.7859
1.7845
1.7809
1.7769
1.7661
1.7612
1.7508
31
s
58
63
71
78
95
103
123
F
-
msc
1.7914
1.7898
1.7862
1.7825
1.7716
1.7668
1.7564
32
s
60
65
73
80
97
106
126
F
-
msc
1.7966
1.7949
1.7913
1.7875
1.7767
1.7720
1.7618
33
s
62
67
75
82
100
109
130
F
-
msc
1.8015
1.7998
1.7961
1.7923
1.7817
1.7771
1.7670
34
s
64
69
78
84
103
111
133
F
-
msc
1.8062
1.8044
1.8010
1.7969
1.7865
1.7818
1.7718
35
s
66
71
80
87
105
114
136
F
-
msc
1.8106
1.8088
1.8053
1.8015
1.7909
1.7864
1.7765


### 4.4. Some Observation

It can be seen from Table1 that the optimalsvalue becomes larger as the success rate requirement is increased and also as the number of bits per table entry becomes larger. The same trend could be observed from an analogous table presented by [18] for the nonperfect fuzzy rainbow tradeoff.An intuitive explanation for the trend concerning the success rate can be given as follows. Since the online phase of the fuzzy rainbow tradeoff processes the precomputations tables in parallel, a highersvalue, corresponding to higher segmentation of the precomputation matrix, allows for more immediate exit from the online phase upon an encounter with the correct answer. Early exits from the online phase are less common under low success rates, and the importance of highersvalue increases as the success rate requirement is increased. As for the trend related to the change inlog
⁡
m
⋆
+
ɛ, one could treat this as a natural scaling effect that accompanies the general increase in search space size associated with the increase inlog
⁡
m
⋆.Let us now return to the definition of the adjusted tradeoff coefficient. A careful reading of [13] shows that they had ignored the term involvingl
R
¯from (50) in comparing the perfect rainbow tradeoff with the other major tradeoff algorithms. This was justified in their work based on the observation that the term remains upper bounded by a small number, when parameters are restricted to those that do not call for impractically large precomputation efforts.Applying the same argument to the perfect fuzzy rainbow tradeoff, we can see that thelog
⁡
(
2
/
(
2
-
F
¯
msc
)
)term of (49) is likewise upper bounded for parameters that are reasonable in view of precomputation cost. Hence, we could consider the possibility of using the adjusted tradeoff coefficient defined as
(53)
F
¯
atc
,
s
′
=
(
3
2
log
⁡
N
)
2
(
log
⁡
s
+
log
⁡
m
⋆
+
ɛ
)
2
.
This definition could be favorable to the previous definition (49), in view of simplicity.The effect of removing thelog
⁡
(
2
/
(
2
-
F
¯
msc
)
)term can be seen from Figure 2. The curves forF
¯
atc
,
sandF
¯
atc
,
s
′are noticeably different from each other, and the use of the simpler (53) in place of the more accurate (49) cannot be justified.The adjusted tradeoff coefficientF
¯
atc
,
sand its simplified versionF
¯
atc
,
s
′in relation toF
¯
pc
,
s(bottom:F
¯
pc
,
s; left:F
¯
atc
,
sandF
¯
atc
,
s
′; top:F
¯
msc).
(a)
(b)An overview of Table1 reveals that any reasonable choice of parameters will mostly satisfy the boundF
¯
msc
≤
1.8, and this bound implies that the termlog
⁡
(
2
/
(
2
-
F
¯
msc
)
)
≤
3.32193is always somewhat small. However, referring once more to Table 1, we see thatlog
⁡
svalues of interest are not very large. Furthermore, practical values oflog
⁡
m
⋆
+
ɛare not very large either. Hence, unlike the situation with the perfect rainbow tradeoff, the bound onlog
⁡
(
2
/
(
2
-
F
¯
msc
)
)is not small enough, in comparison to the terms it is added together with, to be completely ignored.Our final comment is intimately connected to the above discussion. Combining the boundF
¯
msc
≤
1.8with Proposition 2 and (23), we can state the bound
(54)
F
¯
pc
≤
-
ln
⁡
(
1
-
F
¯
ps
)
F
¯
msc
F
¯
cr
2
F
¯
msc
2
-
F
¯
msc
≤
-
ln
⁡
(
1
-
F
¯
ps
)
Θ
(
1
)
10
,
concerning the precomputation coefficient. Hence, unless the success rate requirement is set unrealistically close to1, precomputation cost will be automatically bounded byΘ
(
N
)   for all meaningful parameters.


### 4.5. Algorithm Comparison

We are finally ready to compare the performance of the perfect fuzzy rainbow tradeoff with those of the perfect rainbow tradeoff and the nonperfect fuzzy rainbow tradeoff.The comparison at the90
%success rate is given by Figure 3, which presents theX
pc-X
atccurves for the three tradeoff algorithms. The left-hand side box was drawn with parameters that would be used with a very small search space and the right-hand side box represents the situation of a very large search space. Thesvalues for the perfect fuzzy rainbow tradeoffs were chosen to be the optimal ones given by Table 1. The corresponding table from [18] was used to decide on thesvalues for the nonperfect fuzzy rainbow tradeoff.The adjusted tradeoff coefficients in relation to the precomputation coefficients for the perfect fuzzy rainbow, perfect rainbow, and nonperfect fuzzy rainbow tradeoffs at90
%success rate (bottom:X
pc; left:X
atc).
(a)
(b)The comparisons at99
%and99.9
%success rates are given by Figures 4 and 5. As before, parameters typically considered during theoretical analyses of the tradeoff algorithms corresponding to a small search space and a large search space were used.The adjusted tradeoff coefficients in relation to the precomputation coefficients for the perfect fuzzy rainbow, perfect rainbow, and nonperfect fuzzy rainbow tradeoffs at99
%success rate (bottom:X
pc; left:X
atc).
(a)
(b)The adjusted tradeoff coefficients in relation to the precomputation coefficients for the perfect fuzzy rainbow, perfect rainbow, and nonperfect fuzzy rainbow tradeoffs at99.9
%success rate (bottom:X
pc; left:X
atc).
(a)
(b)In every comparison box, the curve for the perfect fuzzy rainbow tradeoff appears much closer to the lower left corner than the points for the perfect rainbow tradeoff. The perfect fuzzy rainbow tradeoff can attain better online efficiency than the perfect rainbow tradeoff for the same online cost and attain equal online efficiency at lower precomputation cost. Furthermore, the perfect fuzzy rainbow tradeoff can attain online efficiency that is not possible with the perfect rainbow tradeoff.Similar statements are true concerning the comparison between the perfect and nonperfect fuzzy rainbow tradeoffs, except that, at the lower end of the possible precomputation cost range, the two curves cross over each other, and the nonperfect fuzzy rainbow tradeoff can provide better online efficiency for the same precomputation effort. However, this is the region where the online efficiency is extremely bad, so that these parameters would be of limited practical interest.In all, we can state that the perfect fuzzy rainbow tradeoff displays better performance than both the perfect rainbow tradeoff and the nonperfect fuzzy rainbow tradeoff, over a wide range of tradeoff algorithm application situations.


## 4.1. Overview of the Comparison Method

Recall that the conclusion of [13], in overly simplified terms, was that the perfect rainbow tradeoff algorithm is superior to all the other widely known tradeoff algorithms. Also recall from our recent work [9] that the nonperfect version of the fuzzy rainbow tradeoff, which is not yet widely known, is preferable to the perfect rainbow tradeoff when one is constrained in precomputation resources. Hence, we wish to compare the performance of the perfect fuzzy rainbow tradeoff, which we have analyzed in this paper, against those of the perfect rainbow and the nonperfect fuzzy rainbow tradeoffs.In the remainder of this paper, we will use symbolsR
¯andFto extend the notation we had been using concerning the perfect fuzzy rainbow tradeoff to the perfect rainbow and nonperfect fuzzy rainbow tradeoffs, and we will use the symbol  X  when we wish to reference a coefficient without making the tradeoff algorithm specific. For example, symbolsR
¯
tcandF
tcdenote the tradeoff coefficients for the perfect rainbow and nonperfect fuzzy rainbow tradeoffs, respectively, andX
tcrefers to any tradeoff coefficient. The symbolsF
¯,R
¯, andFwill also be used as inm
F
¯,m
R
¯, andm
Fto clarify that the parameter or some complexity value is to be associated with a certain algorithm.We will follow the approach of [12] in comparing the performances of different tradeoff algorithms against each other. In short, a small number of success rate requirementsX
pswill be chosen, and a graph for each algorithm, displaying the upper level tradeoff between itsprecomputation cost andonline cost, will be plotted. The overall relative positions of the curves corresponding to different algorithms, subject to the sameX
ps, will allow certain conclusions to be made concerning algorithm performances. The curves themselves will also be of value when choosing algorithm parameters for implementation.It is clear that the precomputation costPof a tradeoff algorithm can be numerically represented in full by the precomputation coefficientX
pc
=
(
P
/
N
). In the perfect fuzzy rainbow tradeoff case, this can be computed from Proposition 2, and the corresponding results for our two comparison target algorithms can be found in [9, 13]. Note thatX
pcpresents the computational cost as the number of iterations, in multiplies of  N, required of the common target one-way function, regardless of the tradeoff algorithm.The online cost or efficiency of a tradeoff algorithm is mostly captured by its tradeoff coefficient. However, since theMappearing in the definitionX
tc
=
T
M
2
/
N
2represents the number of table entries, rather than the physical number of bits required to store the tables, the tradeoff coefficient cannot be used directly in comparing different algorithms. One must first adjustX
tcto account for the differences in number of bits required per table entry by the algorithms being compared. For example, the comparison of the nonperfect DP and rainbow tradeoffs by [12] was carried out with therelatively adjusted tradeoff coefficients(
1
/
4
)
D
tcandR
tc. The adjustment factor(
1
/
2
)
2reflects the fact that the DP tradeoff requires roughly half as many bits to store each precomputation table entry in comparison to the rainbow tradeoff, under parameter choices that are typically considered during theoretical analyses of the tradeoff algorithms.


## 4.2. Tradeoff Coefficient Adjustment

We wish to be slightly more careful in treating the tradeoff coefficient adjustment factors than focusing on just the theoretically typical parameters. In general, as a trivial extension of the approach given by [12], one can use theadjusted tradeoff coefficient
(42)
X
atc
=
(
3
2
log
⁡
N
)
2
(
number
of
bits
per
table
entry
for
X
)
2
X
tc
to represent the online cost of each algorithm, and plot theX
pcversusX
atccurves to obtain a fair comparison of different algorithms. Here, the constant(
3
/
(
2
log
⁡
N
)
)
2serves the purpose of bringing the adjustment factor toΘ
(
1
)order at typical parameters and is not an essential factor for the purpose of comparisons. The tradeoff coefficientsF
¯
tc,R
¯
tc, andF
tcmay be computed from Theorem 11 and the corresponding results from [9, 13], but more work is required before we can specify thenumber of bits part more concretely for each algorithm.Recalling the contents of Section3.4 and Lemma 1, the adjusted tradeoff coefficient for the perfect fuzzy rainbow tradeoff may be written more concretely in terms of algorithm parameters as
(43)
F
¯
atc
=
(
3
2
log
⁡
N
)
2
(
log
⁡
2
2
-
F
¯
msc
+
log
⁡
m
F
¯
+
ɛ
)
2
F
¯
tc
.
Referring to results from [9, 13], it is not difficult to work out similar adjustment factors for the perfect rainbow and nonperfect fuzzy rainbow tradeoffs to claim
(44)
R
¯
atc
=
(
3
2
log
⁡
N
)
2
(
log
⁡
2
l
R
¯
2
l
R
¯
+
ln
⁡
⁡
(
1
-
R
¯
ps
)
+
log
⁡
m
R
¯
+
ɛ
)
2
R
¯
tc
,
(45)
F
atc
=
(
3
2
log
⁡
N
)
2
(
log
⁡
m
F
+
ɛ
)
2
F
tc
as the more concrete expressions.The small positive integerɛcorresponds to the number of ending point bits remaining after applications of the truncation and index file techniques. Working with Proposition 12 and corresponding results from [13, 18], one can reasonably argue thatɛfor the three algorithms can be set to a common value, which is why we have not subscripted them with the algorithm symbols. The terms involvingF
¯
mscandl
R
¯, appearing in (43) and (44), have their roots in the merge removal process for producing perfect tables and reflect what fraction of the initially generated chains remains in the perfect table. Since theX
pc-X
atccurves are to be plotted usingF
¯
mscandl
R
¯as parameters, the existence of these terms will not cause any later difficulties. However, the threelog
⁡
mvalues require further attention.Note that one cannot hope to simply make independentlog
⁡
mvalue choices that achieveoptimality for each algorithm, since optimality cannot be defined objectively. The most favorable balance between precomputation costP, storage costM, and expected online inversion timeTis a subjective matter that would be different for every implementer and situation. For our algorithm comparison to be fair, the valueslog
⁡
m
F
¯,log
⁡
m
R
¯, andlog
⁡
m
Fneed to be left as choices to be made by the implementer. Nevertheless, we can still restrict the three choices to be made in a reasonably correlated manner. The natural approach is to correlate the choices through the requirement that theP,M, andTcomplexities for the three algorithms be made roughly comparable and with the strict restriction that the success rates of the three algorithms be identical. Since the performances of the three algorithms commonly satisfyT
M
2
≈
N
2, if an implementer under a specific situation is asked to produce parameters sets for the three algorithms that he deems favorable, his choices for the three algorithms would be roughly matching the performance figuresP,M, andT.Let us now choose to view each positive integersas presenting a separate version of the perfect fuzzy rainbow algorithm. That is, we treat the perfect fuzzy rainbow tradeoff as a series of infinitely many different algorithms. A similar view will be taken of the nonperfect fuzzy rainbow algorithm. Below, we will describe a rule for correlating the parameter sets among these two infinite series of algorithms and the perfect rainbow tradeoff algorithm, for each fixed common probability of successX
ps.We first take integersm
⋆andt
⋆such thatlog
⁡
m
⋆
+
2
log
⁡
t
⋆
≈
log
⁡
N  and set the perfect fuzzy rainbow parameters to
(46)
m
F
¯
,
s
≈
s
m
⋆
,
t
F
¯
,
s
≈
t
⋆
s
,
l
F
¯
,
s
=
-
ln
⁡
(
1
-
X
ps
)
F
¯
msc
F
¯
cr
t
F
¯
,
s
,
for eachs
≥
1, where the coverage rateF
¯
cr, corresponding to eachs, is to be computed through (9), Lemma 3, and (15). The perfect rainbow tradeoff parameters corresponding to the above are set to
(47)
m
R
¯
≈
m
⋆
t
⋆
,
t
R
¯
≈
t
⋆
,
l
R
¯
=
-
ln
⁡
(
1
-
X
ps
)
R
¯
msc
,
whereR
¯
msc
=
(
m
R
¯
t
R
¯
/
N
), and in such a way thatl
R
¯ is an integer. Finally, the nonperfect fuzzy rainbow parameters are set to
(48)
m
F
,
s
≈
s
m
⋆
,
t
F
,
s
≈
t
⋆
s
,
l
F
,
s
=
-
ln
⁡
(
1
-
X
ps
)
F
msc
F
cr
t
F
,
s
,
for eachs
≥
1, whereF
msc
=
(
m
F
,
s
t
F
,
s
2
s
/
N
)andF
cris the coverage rate for the nonperfect fuzzy rainbow tradeoff.Note that the requirementlog
⁡
m
⋆
+
2
log
⁡
t
⋆
≈
log
⁡
N does not affect the implementer’s control over theP-T-Mtradeoff in any way. Further note that one has sufficient control overF
¯
msc,l
R
¯, andF
msc, even whenlog
⁡
m
⋆andlog
⁡
t
⋆are fixed to approximate values. That is, one can vary theX
pc-X
tccurve parametersF
¯
msc,l
R
¯, andF
mscquite freely while keeping all thelog
⁡
m
Xvalues somewhat stable.Using (23) and similar claims from [9, 13], it is trivial to verify that all parameter sets achieve the same success rateX
ps. It is also easy to verify, using the factsP
F
¯
=
Θ
(
m
F
¯
t
F
¯
2
s
F
¯
),T
F
¯
=
Θ
(
t
F
¯
2
s
F
¯
2
), andM
F
¯
=
Θ
(
m
F
¯
t
F
¯
)and the corresponding facts from [9, 13], that the performance figuresP,M, andTare of similar order for all the above parameter sets. In fact, it is possible to argue that the above method is the only possible manner in which comparableP,T, andMcomplexities can be achieved by the different algorithms at a common success rate.The reasonable association between the parameter sets for different algorithms given by (46), (47), and (48) allows the adjusted tradeoff coefficients to be written as
(49)
F
¯
atc
,
s
=
(
3
2
log
⁡
N
)
2
(
log
⁡
2
2
-
F
¯
msc
+
log
⁡
s
+
log
⁡
m
⋆
+
ɛ
)
2
F
¯
tc
,
s
,
(50)
R
¯
atc
=
(
3
2
log
⁡
N
)
2
×
(
log
⁡
2
l
R
¯
2
l
R
¯
+
ln
⁡
⁡
(
1
-
R
¯
ps
)
+
1
2
log
⁡
N
+
1
2
log
⁡
m
⋆
+
ɛ
)
2
R
¯
tc
,
(51)
F
atc
,
s
=
(
3
2
log
⁡
N
)
2
(
log
⁡
s
+
log
⁡
m
⋆
+
ɛ
)
2
F
tc
,
s
,
where we have relied onlog
⁡
N
≈
log
⁡
m
⋆
+
2
log
⁡
t
⋆in writing (50). We have also additionally subscripted the (adjusted) tradeoff coefficients with the parametersto make their dependence onsmore explicit.To compare the performances of different tradeoff algorithms, it now suffices to fixX
ps, choose reasonable values forlog
⁡
m
⋆
+
ɛandlog
⁡
N, and plot theX
pc-X
atccurves, for all the algorithms.


## 4.3. Choosing the Color Counts

Before comparing the perfect fuzzy rainbow tradeoff with the other two algorithms, we wish to make comparisons among the many versions of the perfect fuzzy rainbow tradeoff corresponding to differentschoices. A small number of theF
¯
pc-F
¯
atccurves are given in Figure 1.The adjusted tradeoff coefficientF
¯
atc
,
sin relation to precomputation coefficientF
¯
pc
,
s, for a small number ofsvalues, at success rate90
%and withlog
⁡
m
⋆
+
ɛfixed to21and33(bottom:F
¯
pc
,
s; left:F
¯
atc
,
s).
(a)
(b)The left-hand side box contains plots of the(
F
¯
pc
,
s
,
F
¯
tc
,
s
)points, for the case when the success rate is set to90
%andlog
⁡
m
⋆
+
ɛis set to21. Each of the three curves is for specificsvalues. The right-hand side box contains similar curves for theF
¯
ps
=
90
%andlog
⁡
m
⋆
+
ɛ
=
33case. Note thatɛ
=
8would be a reasonable value in view of the discussions given by Section 3.4 and thatlog
⁡
m
⋆
=
13andlog
⁡
m
⋆
=
25are choices that would typically be made during theoretical discussions of the tradeoff technique for the very small  N
=
2
39and the very large  N
=
2
75search space sizes. Hence, ourlog
⁡
m
⋆
+
ɛ
=
21andlog
⁡
m
⋆
+
ɛ
=
33examples are representative of the behaviors at both ends of the realistic tradeoff application environments.Each curve has been plotted precisely to its lowest point. The curve points that would appear to the right of a lowest point are meaningless, since they correspond to parameter sets that call for higher precomputation efforts while achieving lower online efficiencies than the parameter sets corresponding to the lowest point.One may roughly associate overall better performance with a curve that is closer to the lower left corner of each figure box. However, it can be seen that curves corresponding to differentsvalues may cross over each other. In fact, we could verify that the lowest curve in each box crosses over the middle curve appearing in its box at a highX
atcvalue. Hence, one cannot claim onesvalue to be providing definitely superior performance over anothersvalue, at least not strictly logically.Nevertheless, if we restrict our attention to the lower parts of the curves, which are of higher practical interest than the highX
atcparts, it becomes clear that little harm will be done by simplifying matters and ranking the performances for differentschoices based only on the lowest point of each curve. In other words, for practical purposes, it is sufficiently reasonable to declare ansvalue to be optimal for a specific(
F
¯
ps
,
log
⁡
m
⋆
+
ɛ
)pair if
(52)
min
⁡
F
¯
msc
⁡
{
F
¯
atc
,
s
}
=
min
⁡
i
≥
1
,
F
¯
msc
{
F
¯
atc
,
i
}
.
We emphasize that such a simplification is possible only because of the nice relative positions of the many curves and that the same simplification may not be applicable to other comparison situations.The optimal number of colorss, as defined through comparisons at the lowest points of the curves, is given by Table 1, for various success rate requirementsF
¯
psand a wide range oflog
⁡
m
⋆
+
ɛvalues. TheF
¯
mscvalue that attains the minimum possibleF
¯
atc
,
svalue is listed under each optimals.Table 1
Optimals for the perfect fuzzy rainbow tradeoff, at various F
-
ps and log
⁡
m
⋆
+
ε values. The F
-
msc value listed below each s attains the minimum F
-
atc,
s value.
log
⁡
m
⋆
+
ε
50%
75%
90%
95%
99%
99.5%
99.9%
18
s
34
38
43
48
60
66
79
F
-
msc
1.6880
1.6882
1.6846
1.6813
1.6697
1.6647
1.6531
19
s
36
40
46
50
63
68
83
F
-
msc
1.6999
1.6996
1.6967
1.6921
1.6810
1.6754
1.6644
20
s
37
42
48
53
65
71
86
F
-
msc
1.7095
1.7103
1.7071
1.7030
1.6910
1.6858
1.6747
21
s
39
44
50
55
68
74
89
F
-
msc
1.7198
1.7202
1.7167
1.7126
1.7008
1.6955
1.6843
22
s
41
46
52
57
71
77
93
F
-
msc
1.7294
1.7293
1.7256
1.7215
1.7101
1.7046
1.6936
23
s
43
48
54
59
73
80
96
F
-
msc
1.7382
1.7379
1.7339
1.7298
1.7183
1.7133
1.7021
24
s
45
50
56
62
76
83
100
F
-
msc
1.7465
1.7459
1.7418
1.7381
1.7264
1.7214
1.7105
25
s
47
51
58
64
79
86
103
F
-
msc
1.7542
1.7527
1.7492
1.7454
1.7340
1.7290
1.7180
26
s
49
53
60
66
81
89
106
F
-
msc
1.7615
1.7598
1.7562
1.7523
1.7410
1.7362
1.7252
27
s
51
55
63
69
84
91
110
F
-
msc
1.7684
1.7665
1.7633
1.7593
1.7478
1.7427
1.7322
28
s
52
57
65
71
87
94
113
F
-
msc
1.7740
1.7728
1.7695
1.7655
1.7543
1.7492
1.7387
29
s
54
59
67
73
89
97
116
F
-
msc
1.7801
1.7788
1.7754
1.7713
1.7602
1.7554
1.7448
30
s
56
61
69
75
92
100
120
F
-
msc
1.7859
1.7845
1.7809
1.7769
1.7661
1.7612
1.7508
31
s
58
63
71
78
95
103
123
F
-
msc
1.7914
1.7898
1.7862
1.7825
1.7716
1.7668
1.7564
32
s
60
65
73
80
97
106
126
F
-
msc
1.7966
1.7949
1.7913
1.7875
1.7767
1.7720
1.7618
33
s
62
67
75
82
100
109
130
F
-
msc
1.8015
1.7998
1.7961
1.7923
1.7817
1.7771
1.7670
34
s
64
69
78
84
103
111
133
F
-
msc
1.8062
1.8044
1.8010
1.7969
1.7865
1.7818
1.7718
35
s
66
71
80
87
105
114
136
F
-
msc
1.8106
1.8088
1.8053
1.8015
1.7909
1.7864
1.7765


## 4.4. Some Observation

It can be seen from Table1 that the optimalsvalue becomes larger as the success rate requirement is increased and also as the number of bits per table entry becomes larger. The same trend could be observed from an analogous table presented by [18] for the nonperfect fuzzy rainbow tradeoff.An intuitive explanation for the trend concerning the success rate can be given as follows. Since the online phase of the fuzzy rainbow tradeoff processes the precomputations tables in parallel, a highersvalue, corresponding to higher segmentation of the precomputation matrix, allows for more immediate exit from the online phase upon an encounter with the correct answer. Early exits from the online phase are less common under low success rates, and the importance of highersvalue increases as the success rate requirement is increased. As for the trend related to the change inlog
⁡
m
⋆
+
ɛ, one could treat this as a natural scaling effect that accompanies the general increase in search space size associated with the increase inlog
⁡
m
⋆.Let us now return to the definition of the adjusted tradeoff coefficient. A careful reading of [13] shows that they had ignored the term involvingl
R
¯from (50) in comparing the perfect rainbow tradeoff with the other major tradeoff algorithms. This was justified in their work based on the observation that the term remains upper bounded by a small number, when parameters are restricted to those that do not call for impractically large precomputation efforts.Applying the same argument to the perfect fuzzy rainbow tradeoff, we can see that thelog
⁡
(
2
/
(
2
-
F
¯
msc
)
)term of (49) is likewise upper bounded for parameters that are reasonable in view of precomputation cost. Hence, we could consider the possibility of using the adjusted tradeoff coefficient defined as
(53)
F
¯
atc
,
s
′
=
(
3
2
log
⁡
N
)
2
(
log
⁡
s
+
log
⁡
m
⋆
+
ɛ
)
2
.
This definition could be favorable to the previous definition (49), in view of simplicity.The effect of removing thelog
⁡
(
2
/
(
2
-
F
¯
msc
)
)term can be seen from Figure 2. The curves forF
¯
atc
,
sandF
¯
atc
,
s
′are noticeably different from each other, and the use of the simpler (53) in place of the more accurate (49) cannot be justified.The adjusted tradeoff coefficientF
¯
atc
,
sand its simplified versionF
¯
atc
,
s
′in relation toF
¯
pc
,
s(bottom:F
¯
pc
,
s; left:F
¯
atc
,
sandF
¯
atc
,
s
′; top:F
¯
msc).
(a)
(b)An overview of Table1 reveals that any reasonable choice of parameters will mostly satisfy the boundF
¯
msc
≤
1.8, and this bound implies that the termlog
⁡
(
2
/
(
2
-
F
¯
msc
)
)
≤
3.32193is always somewhat small. However, referring once more to Table 1, we see thatlog
⁡
svalues of interest are not very large. Furthermore, practical values oflog
⁡
m
⋆
+
ɛare not very large either. Hence, unlike the situation with the perfect rainbow tradeoff, the bound onlog
⁡
(
2
/
(
2
-
F
¯
msc
)
)is not small enough, in comparison to the terms it is added together with, to be completely ignored.Our final comment is intimately connected to the above discussion. Combining the boundF
¯
msc
≤
1.8with Proposition 2 and (23), we can state the bound
(54)
F
¯
pc
≤
-
ln
⁡
(
1
-
F
¯
ps
)
F
¯
msc
F
¯
cr
2
F
¯
msc
2
-
F
¯
msc
≤
-
ln
⁡
(
1
-
F
¯
ps
)
Θ
(
1
)
10
,
concerning the precomputation coefficient. Hence, unless the success rate requirement is set unrealistically close to1, precomputation cost will be automatically bounded byΘ
(
N
)   for all meaningful parameters.


## 4.5. Algorithm Comparison

We are finally ready to compare the performance of the perfect fuzzy rainbow tradeoff with those of the perfect rainbow tradeoff and the nonperfect fuzzy rainbow tradeoff.The comparison at the90
%success rate is given by Figure 3, which presents theX
pc-X
atccurves for the three tradeoff algorithms. The left-hand side box was drawn with parameters that would be used with a very small search space and the right-hand side box represents the situation of a very large search space. Thesvalues for the perfect fuzzy rainbow tradeoffs were chosen to be the optimal ones given by Table 1. The corresponding table from [18] was used to decide on thesvalues for the nonperfect fuzzy rainbow tradeoff.The adjusted tradeoff coefficients in relation to the precomputation coefficients for the perfect fuzzy rainbow, perfect rainbow, and nonperfect fuzzy rainbow tradeoffs at90
%success rate (bottom:X
pc; left:X
atc).
(a)
(b)The comparisons at99
%and99.9
%success rates are given by Figures 4 and 5. As before, parameters typically considered during theoretical analyses of the tradeoff algorithms corresponding to a small search space and a large search space were used.The adjusted tradeoff coefficients in relation to the precomputation coefficients for the perfect fuzzy rainbow, perfect rainbow, and nonperfect fuzzy rainbow tradeoffs at99
%success rate (bottom:X
pc; left:X
atc).
(a)
(b)The adjusted tradeoff coefficients in relation to the precomputation coefficients for the perfect fuzzy rainbow, perfect rainbow, and nonperfect fuzzy rainbow tradeoffs at99.9
%success rate (bottom:X
pc; left:X
atc).
(a)
(b)In every comparison box, the curve for the perfect fuzzy rainbow tradeoff appears much closer to the lower left corner than the points for the perfect rainbow tradeoff. The perfect fuzzy rainbow tradeoff can attain better online efficiency than the perfect rainbow tradeoff for the same online cost and attain equal online efficiency at lower precomputation cost. Furthermore, the perfect fuzzy rainbow tradeoff can attain online efficiency that is not possible with the perfect rainbow tradeoff.Similar statements are true concerning the comparison between the perfect and nonperfect fuzzy rainbow tradeoffs, except that, at the lower end of the possible precomputation cost range, the two curves cross over each other, and the nonperfect fuzzy rainbow tradeoff can provide better online efficiency for the same precomputation effort. However, this is the region where the online efficiency is extremely bad, so that these parameters would be of limited practical interest.In all, we can state that the perfect fuzzy rainbow tradeoff displays better performance than both the perfect rainbow tradeoff and the nonperfect fuzzy rainbow tradeoff, over a wide range of tradeoff algorithm application situations.


## 5. Conclusion

The execution behavior of the perfect table version of the fuzzy rainbow tradeoff algorithm was analyzed in this paper. The average case online computational complexity that fully accounts for the effects of false alarms was accurately obtained. The expected number of precomputation table entries and the number of bits required to record each table entry were also obtained accurately.The results of our complexity analysis were used to compare the performance of the perfect fuzzy rainbow tradeoff with those of other tradeoff algorithms. The perfect rainbow tradeoff was recently argued by [13] to be advantageous over all other widely known tradeoff algorithms, and our recent work [9] had shown that the less widely known nonperfect fuzzy rainbow tradeoff outperforms the perfect rainbow tradeoff under certain circumstances. Hence, our comparison targets were set to the perfect rainbow tradeoff and the nonperfect fuzzy rainbow tradeoff.The comparison took the following aspects of the tradeoff algorithms into account: success rate of inversion, precomputation complexity, computational complexity of the online phase, and physical storage size of the precomputation table. The comparison called for a carefully designed rule that correlated the number of bits per table entry to be used by each algorithm in a fair manner. The current work is the first to include the effects arising from the merge removal process of the perfect table creation into this rule.We were able to conclude that the perfect fuzzy rainbow tradeoff is highly preferable to the perfect rainbow tradeoff. The perfect fuzzy rainbow tradeoff was also found to be superior to the nonperfect fuzzy rainbow tradeoff, except possibly at parameters that would have both of the algorithms performing very poorly during the online phase in exchange for a very small advantage in precomputation cost.



---

*Source: 765394-2014-06-12.xml*