Factoring assumption

We shall be referring to these prescriptions for dichotomous noise as the Dichotomous Factorization (DF) assumption. We notice that the factorization assumption is widely used regardless of whether the correlation function is an exponential or not. See, for instance, the work of Fulinski [62] for the use of this assumption in the non-Poisson case. We shall come back to these important issues in later sections. For the time being, let us limit ourselves to noticing that in the Poisson case,... 

Because TPH is a complex and highly variable mixture, assessment of health impacts depends on several factors, assumptions, and circumstances. Of prime importance is the specific exposure scenario. For example, immediately following a large release of a lighter petroleum product (e.g., automotive gasoline), central nervous system depression could occur in people in the immediate vicinity of the spill if... 

The main underlying cryptologic assumption is therefore that factoring large integers is infeasible. Concrete versions have later been called the factoring assumption (see Section 8.4).. To this day, it has remained one of the two most important assumptions to base asymmetric cryptologic schemes on. 

The factoring assumption implies that nobody except for the signer can compute 0(n) = (p-l)( -l), Euler s totient function [RiSA78]. 

There are concrete cryptologic assumptions, such as the factoring assumption, and more general abstract ones, such as a one-way function exists . 

This implies that all types of schemes also exist both on the factoring assumption and on a discrete-logarithm assumption (with [Damg88]). 

Nowadays, more efficient constructions based directly on either of these two concrete assumptions exist [HePe93, HePP93] (see also [PePf95], and Section 9.4 contains a new variant with 2-message initialization based on the factoring assumption). 

Most of the following facts are only needed in the constructions based on the factoring assumption. There, the basic structure used is the ring of integers modulo n, where n is a chosen number that is hopefully hard to factor. Particular attention is paid to quadratic residues and square roots, because the squaring function plays an important part in the following schemes. 

As far as number-theoretic properties are concerned, one could permit generalized Williams integers, similar to generalized Blum integers, of the form p qK However, in a factoring assumption, large exponents s and t would mean small prime factors if n is always of approximately the same length, and numbers with small prime factors are easier to factor. 

If one wants a deterministically polynomial-time algorithm that only outputs prime numbers, and where the corresponding factoring assumption follows from that made above, one has to rely on Cramer s conjecture (see above) and search for each prime from some random number upwards in steps of two, and test each number with the pure Miller primality test [Mill76], which relies on the extended Riemann hypothesis. 

Other possible variations in the factoring assumption concern the number of prime factors of n and the congruence classes and length of these factors. 

Blum integers and Williams integers are often used, too. Because of Dirichlet s prime-number theorem, asymptotically about half of all prime numbers are congruent to 3 mod 4, and among these, about half are congruent to 3 mod 8. Hence the factoring assumption made above is a consequence of one for arbitrary numbers with two prime factors. 

The condition that the length of the factors is exactly equal is rather strict. In practice, one might fix the length in words only or even start with the required length I of n (i.e., I = 2k here) and a bound a and require only p 2, q Of/ see [Maur95]. This would require a more general factoring assumption for each a. 

The algorithm group verification, on input ( 1 , q,p), first tests if I l2 Ipl2 2 len p(lc) this can be done in time polynomial in k. If yes, it continues and tests if > 2 and q I (p-1), and if p and q are prime. As discussed with the factoring assumption, the Rabin-Miller test is used in practice, although it introduces an exponentially small error probability into some properties (but not into availability of service). These tests take time polynomial in the length of q and p, which were already verified to be polynomial in k. 

All the classes of function families shown in Figure 8.5 can be constructed both on the abstract discrete-logarithm assumption (see Section 8.5.3) and on the factoring assumption (see Section 8.5.5), and those without homomorphism properties also on the abstract assumption that a claw-intractable family of permutation pairs exists (see Section 8.5.4). An overview of these constractions is given in Figures 8.6 and 8.7. The top layer of both figures is identical to the bottom layer of Figure 8.5. 

Signs c denote inclusion arrows denote constructions. The diagram at the bottom commutes, i.e., iterated squaring and doubling is the special case of iterated permutations where the construction of claw-intractable permutation pairs on the factoring assumption is used. 

This section contains the constructions of function families, as defined in Section 8.5.2, on the factoring assumption. An overview is given in the right half of the constructions in Figure 8.7, and some details are summarized in Table 8.3. 

Lemma 8.65. (Adapted from [G0MR88].) On the factoring assumption (Definition 8.18), Construction 8.64 defines a strong and a weak claw-intractable family of permutation pairs. ... 

Theorem 8.67 (Iterated squaring and doubling as bundling homomor-phisms). On the factoring assumption. Construction 8.66 defines a collision-intractable family of bundling homomorphisms. ... 

The following table summarizes the most important parameters of the constructions of collision-intractable families of bundling homomorphisms, hiding homomor-phisms, and hash functions based on the factoring assumption. 

Theorem 9.18. On the factoring assumption, the two schemes from Definition 9.17 are secure for any function rho. ... 

This is a slightly simplified comparison, because k is not directly comparable between schemes relying on different cryptologic assumption. However, the two schemes just mentioned do rely on the same assumption, and it was shown in Section 9.5 that with choices of security parameters that seem reasonable at present, the secret keys in the constructions based on the factoring assumption are longer. 

---