Santanu Sarkar
email: sarkar.santanu.bir@gmail.com

Sen Sourav
email: souravsgr@isical.ac.in

Subhamoy Gupta

Maitra

Reconstruction and Error Correction of RSA Secret Parameters from the MSB Side

Keywords: Error correction, Prime reconstruction, Random known bits, RSA

This paper discusses the factorization of the RSA modulus when some 'partial information' about the bits of the RSA secret parameters are known. Heninger and Shacham (Crypto 2009) considered the reconstruction of RSA secret parameters from a few randomly known bits, and Henecka, May and Meurer (Crypto 2010) studied the reconstruction of secret parameters when all the bits are known with some probability of error. Both the approaches attempted reconstruction from the least significant side of the parameters. In this paper we provide two new techniques for reconstruction and error correction that work from the most significant side of the parameters. Our idea uses adaptive filtering using a 'sliding window' technique. We provide theoretical as well as experimental results that are competitive with the existing works.

Introduction

RSA has been the most popular public key cryptosystem since its inception in 1978. The RSA modulus N = pq is constructed as a product of two large (usually 512 or 1024 bit) primes, and the Euler totient function φ(N ) is used to obtain the exponents e (coprime to φ(N )) and d = e -1 mod φ(N ). Encryption of plaintext M follows the rule C = M e mod N while the ciphertext C is decrypted as M = C d mod N . One can find a complete description of the RSA scheme in [START_REF] Rivest | A method for obtaining digital signatures and public key cryptosystems[END_REF]. To accelerate the decryption process of RSA, one can use CRT-RSA [START_REF] Quisquater | Fast decipherment algorithm for RSA public-key cryptosystem[END_REF], a variant of the original scheme that uses Chinese Remainder Theorem (CRT). In CRT-RSA, one uses d p = d mod p -1 and d q = d mod q -1, instead of d, for the decryption process. This is the most widely used variant of RSA in practice, and decryption becomes more efficient if one pre-calculates the value of q -1 mod p. Thus, in PKCS [START_REF]PKCS #1 Standard for RSA[END_REF] standard for the RSA cryptosystem, it is recommended to store the secret parameters as a tuple SK = (p, q, d, d p , d q , q -1 mod p), which we shall henceforth refer to as the secret key.

RSA and CRT-RSA have been put through extensive cryptanalysis over the last three decades. An important model of cryptanalysis is the side channel attack, such as fault attacks, timing attacks, power analysis etc., by which an adversary may obtain some information about the secret key SK.

In this paper, we concentrate on the partial information about the secret key SK retrieved using side channel attacks, and how this information may be exploited to mount an attack on RSA. This type of attacks on RSA or CRT-RSA is popularly known as 'partial key exposure' attacks. A majority of the partial key exposure attacks on RSA [START_REF] Boneh | Exposing an RSA Private Key Given a Small Fraction of its Bits[END_REF][START_REF] Coppersmith | Small solutions to polynomial equations and low exponent vulnerabilities[END_REF][START_REF] Herrmann | Solving Linear Equations Modulo Divisors: On Factoring Given Any Bits[END_REF][START_REF] Rivest | Efficient Factoring based on Partial Information[END_REF] consider the knowledge of contiguous blocks of bits in the secret parameters. While the knowledge of contiguous bits may be hard to obtain, one may gain the knowledge of random bits of the RSA secret parameters via some practical side channel attacks; namely the Cold-Boot attack introduced by Halderman et al. [START_REF] Halderman | Lest We Remember: Cold Boot Attacks on Encryption Keys[END_REF].

In Crypto 2009, the Cold-Boot attack was first exploited by Heninger and Shacham [START_REF] Heninger | Reconstructing RSA Private Keys from Random Key Bits[END_REF], who proved that the attacker can factor N in time poly(e, log 2 N ) if he/she has δ ≥ 0.27 fraction of random bits of p, q, d, d p , d q , or δ ≥ 0.42 fraction of random bits of p, q, d, or δ ≥ 0.57 fraction of random bits of p, q. In Africacrypt 2010, Maitra et al. [START_REF] Maitra | Factoring RSA modulus Using Prime Reconstruction from random known bits[END_REF] proposed a method for reconstructing p, q from the MSB side, when a few blocks of MSBs of the primes are known.

Recently, in Crypto 2010, Henecka et al. [START_REF] Henecka | Correcting Errors in RSA Private Keys[END_REF] studied the case when all the bits of SK were known, but with some probable error. In this case, one may consider that each bit of the secret parameters in SK is flipped with some probability γ ∈ [0, 1 2 ). In [START_REF] Henecka | Correcting Errors in RSA Private Keys[END_REF], the authors proved that one can correct the errors in the secret key SK in polynomial time (for small e) when the error rate is γ < 0.237 when p, q, d, d p , d q are known with error, or γ < 0.160 when p, q, d are known with error, or γ < 0.084 when p, q are known with error.

Our Contribution. In this paper, we propose an extension of the aforesaid ideas towards reconstruction and error correction of the RSA secret key SK, starting from the most significant bit (MSB) side, where some partial information about the parameters is known. We present two new algorithms:

-Algorithm 1 (RecSK): Reconstructs RSA secret parameters from the MSB side when random bits of the secret key (p, q, d, d p , d q , q -1 mod p) are known. -Algorithm 2 (CorSK): Corrects the bit-errors in RSA secret key, starting from the MSB side of the parameters, when all the bits of the secret key (p, q, d, d p , d q , q -1 mod p) are known, but with some probability of error.

The algorithms are described in Section 2 and Section 3 respectively, and we also present relevant experimental results to substantiate our claim.

Reconstruction of RSA Secret Key

In this section we propose the first algorithm RecSK which recovers the RSA secret key SK from its partial knowledge. We assume that some random bits of SK are known through some side channel attack on the system. We present a probabilistic polynomial time algorithm whose inputs are these random known bits of the secret parameters of RSA, and the output is the top half of one of the RSA primes (p, say). Our goal is to recover the top 1 2 log 2 p many MSBs of prime p and then use the lattice based approach of Coppersmith [START_REF] Coppersmith | Small solutions to polynomial equations and low exponent vulnerabilities[END_REF] to factor N .

It is clear if the attacker knows any one of {p, q, d, d p , d q }, he/she can easily factor N . Note that we have four RSA equations connecting these five variables:

N = pq, ed = 1 + kφ(N ), ed p = 1 + k p (p -1), ed q = 1 + k q (q -1) (1)
Now when e is small (within the range of a brute force search), one can capture k, k p , k q easily as each of these is smaller than e. Let us write d = d 1 + d 2 , where

d 2 = d mod 2 (log 2 N )/2 and d 1 = d -d 2 .
It is also well known that when e is small, one can find around half of the MSBs of d, that is the portion d 1 (see [START_REF] Boneh | Exposing an RSA Private Key Given a Small Fraction of its Bits[END_REF] for details). Hence in Equation (1), we are left with five unknowns p, q, d p , d q and d 2 . In the next subsection, we propose our algorithm to find these unknown parameters from the knowledge of some random bits.

The Idea for Reconstruction

Consider the case when few random bits are known from the upper halves of p, q, d 2 , d p , d q , and assume that we know the first a many contiguous MSBs of p. According to the algorithm proposed in [START_REF] Maitra | Factoring RSA modulus Using Prime Reconstruction from random known bits[END_REF], one can recover the first at many contiguous MSBs of q with probability greater than 1 -1 2 t . Our situation is, however, different than the one considered in [START_REF] Maitra | Factoring RSA modulus Using Prime Reconstruction from random known bits[END_REF]. Here, we only know a few random bits of the RSA parameters from the MSB side, not contiguous blocks. That is, in the parameters p, q, d, d p , d q , we know about δ fraction of the bits at random (where 0 ≤ δ ≤ 1). We further assume that the known bits of the secret parameters are distributed uniformly at random, i.e., we know δa many bits in each block of size a, and a(1δ) bits are unknown.

Our idea for reconstruction provides a two-part solution to this problem. We perform two steps iteratively over the bits of prime p, starting at the MSB:

-Guess the missing bits in a block (of size a, say) to obtain all possibilities.

-Filter using the known bits of q, d 2 , d p , d q to recover the correct option.

In the Guess routine, we consider all options for the unknown a(1δ) many bits in a specific block of p, and construct 2 a(1-δ) possibilities for the block. Using each of these options, we mimic the reconstruction idea of [START_REF] Maitra | Factoring RSA modulus Using Prime Reconstruction from random known bits[END_REF] to find the first (at) many MSBs of q, d p , d q , d 2 . In the Filter stage, we utilize the bits we know from q, d p , d q , d 2 to discard obvious wrong options. We first illustrate our methodology for p and q, and later extend this to utilize all RSA parameters.

Reconstruction using p and q

Suppose that we know δ fraction of the bits of p and q each, distributed uniformly at random, as discussed. Now, the reconstruction algorithm is as follows.

Step 0. In the Guess routine, we generate 2 a(1-δ) options for the first a MSBs of p, pad the remaining by 0's, and store in an array A, say. The Filter algorithm is performed on A = {p 1 , p2 , . . . , pk } where k = |A| = 2 a(1-δ) .

Step 1. For each option pi ∈ A, we reconstruct the first (at) MSBs of q using the idea of [START_REF] Maitra | Factoring RSA modulus Using Prime Reconstruction from random known bits[END_REF], i.e., qi = ⌊ N pi ⌋. Store these options in an array B. We expect the first block of at MSBs of qi to correctly correspond to pi with probability 1 -1 2 t in each of these cases (t is the offset). Step 2. Match the known bits of q from this block (first (at) MSBs of q) with the corresponding ones in each of these reconstructions qi . If for some 1 ≤ l ≤ at, the bit q[l] is known but q[l] = qi [l], then there is a mismatch, and we discard qi from B, and hence pi from A. If all the known bits of q match with those of qi , then only we retain pi in A. After this match-and-discard stage, the number of remaining options in A = {p 1 , p2 , . . . , px } is x, which we hope is considerably lower than the initial number of options k = 2 a(1-δ) .

Step 3. Each remaining option has some correctly recovered block of MSBs. We try to find the initial contiguous common portion out of the x options, i.e., we find the maximum value of c such that c many initial MSBs of all the options are same. If there is only a single option left in A (i.e., x = 1), we evidently get c = a. As we have chosen only the common bits of all possibilities, we can be certain that these c bits of p are correctly recovered. Iterate. Now, we take the next block of a bits of p starting at the (c + 1)-th MSB, and repeat the Guess and Filter routines using the first (c + a) MSBs of p.

0 c c + a log 2 p

Guess

Padding of 0's

The last two steps above (Step 3 and Iterate) constitute the 'sliding window' technique that filters adaptively over the length of p. This process is continued until half of p is recovered from the MSB side. We formalize the efficiency of the reconstruction algorithm in the next section.

Efficiency of Reconstruction using p and q

In this section, we find the fraction δ of the bits of the primes p and q that is required to be known for our reconstruction algorithm to recover the top half of p successfully. Before we prove the main result, we require the following.

Lemma 1. Suppose that in a contiguous block of a many bits of p, we know ν fraction of the bits. Also suppose that the first unknown bit of p in this block occurs at the y-th position, starting from the MSB side. Then, the expected value of y is given by

E(y) = 1 1-ν -aν a -ν a 1-ν .
Proof. Each bit of p in the block is known with probability ν. The range of values that y can assume within this block is y ∈ [1, a], and the probability distribution of y follows Pr(y = k) = ν k-1 (1ν). Thus, we obtain the expectation as

E(y) = a k=1 k • Pr(y = k) = (1 -ν) a k=1 k • ν k-1 = 1 1-ν -aν a -ν a 1-ν . ⊓ ⊔
Note that the expectation can be approximated as y = E(y) ≈ 1 1-ν when a is large. Now we can state and prove the main technical result of this section.

Theorem 1. Suppose that in each block of size a in the primes p and q, about ν fraction of bits are known. In this case, the reconstruction algorithm described above can successfully recover the top half of p, with probability 1 -1

2 t log p 2(a-t) , if ν ≥ 3 4 - 1 4(a -t) 1 + (a -t) 2 -6(a -t) + 1 ,
where block size a and offset t are used as the parameters for the algorithm.

Proof. In a block of size a in prime p, we know ν fraction of the bits. Thus, there are a(1ν) many unknown bits in the block. In Step 0 (Guess routine) of the reconstruction algorithm, this will result in 2 a(1-ν) options, i.e., k = |A| = 2 a(1-ν) . Each of these options are used to find an approximation for a block of at bits of q, following the idea in Step 1. This introduces the probability 1 -1 2 t in the result for each block of size (at), and there are log p 2(a-t) many such blocks in our target range, i.e., the top half of p.

In the Filter phase of the algorithm, Step 2 performs the match-and-discard operation using the known bits of this corresponding block of q. Now, we know (at)ν many bits in this block of q, but not all of the bits will be useful in filtering the options. Suppose that the first unknown bit of p in the block of size a occurs at a position y, starting from the MSB. Then, the known bits of q within the range [1, y] in the block of size (at) under consideration will have no effect on the unknown bits of p, and hence we will not be able to use about yν bits of q for reconstruction. pi q 0 Known Known/Guessed y a y at 0 Not usable Usable Bits of q not usable = yν Usable bits of q = (aty)ν

It is expected that we will be able to use about (aty)ν many bits of q in the Filter routine, where the mean value y ≈ 1 1-ν is as estimated in Lemma 1. Now, we use the following assumption for filtering through the options of p.

Assumption 1: Each useful bit of q is capable of correcting 1 bit of p, and hence reduces the number of options of p by a factor of 2.

The assumption allows us to estimate the number of remaining options after filtering is done. As we know (aty)ν many bits of q, the number of options of p reduces by a factor of 2 (a-t-y)ν . Thus, we are left with number of options

x = Initial options k Reduction using Filter = 2 a(1-ν) 2 (a-t-y)ν = 2 a(1-ν)-(a-t-y)ν
Note that we have used a block of at bits of q for filtering through a block of a bits of p. Thus, it is expected that we will be left with a block of t bits in p which is not corrected (the last t bits, to be specific). Within these t bits, the number of unknown bits of p is t(1ν), and hence the best the Filter routine can do is to keep around 2 t(1-ν) remaining options after the match-and-discard stage (Step 2). Thus, the desired outcome of

Step 2 is x ≈ 2 a(1-ν)-(a-t-y)ν ≈ 2 t(1-ν) , i.e., a(1 -ν) -(a -t -y)ν ≈ t(1 -ν).
Putting the estimated value of y ≈ 1 1-ν , as in Lemma 1, and simplifying the equation, we obtain the condition to be

ν 2 - 3 2 - 1 2(a -t) ν + 1 2 ≈ 0
Solving the quadratic equation in ν, we obtain the desired expression. ⊓ ⊔

Example 1. Suppose that we take a = 30 and t = 5 for the reconstruction, where p and q are of bitsize 512 each. From Theorem 1, we get ν ≥ 52.18%, which denotes the fraction of bits to be known from each block of size a in primes p, q. But our goal is to estimate δ, the overall fraction of bits to be known for p, q, such that 52.18% of bits are known in each block with a high probability.

If we know each bit of p or q with probability δ, then the probability that we know ν or more fraction of bits in each block of size a is given by a k=aν a k δ k (1δ) a-k . In our case with a = 30 and ν ≈ 52.18%, we observe that δ ≈ 64% ensures a probability greater than 0.9. Thus for δ = 64%, our reconstruction algorithm will recover the top half of p with approximately 90% chance of success.

⊓ ⊔ Experimental Data. We have implemented the code in Sage 4.1 (Linux Ubuntu 8.04) on a machine with Dual Core Intel Pentium D CPU (1.83 GHz, 2 GB RAM, 2 MB Cache). In these experiments, we have taken 1024 bit N and e = 2 16 + 1, as is the case in most practical situations. In all the experiments, we chose t = 5. 1. Experimental data for reconstruction using random known bits of p and q.

Blocksize

all RSA secret parameters in SK. Due to space constraints, we do not present the analysis here, but it will be a part of the extended full version of the paper.

However, we support our claim with the help of a few practical reconstructions, as presented in Table 2. In the full version of the paper, we will include the theoretical bounds on δ and more experimental results.

Comparison with Existing Work

In the existing literature of RSA secret key reconstruction, we can compare our work to those of Heninger and Shacham [START_REF] Heninger | Reconstructing RSA Private Keys from Random Key Bits[END_REF] and Maitra et al. [START_REF] Maitra | Factoring RSA modulus Using Prime Reconstruction from random known bits[END_REF].

Heninger and Shacham [START_REF] Heninger | Reconstructing RSA Private Keys from Random Key Bits[END_REF] were the first to propose the problem and solve it, starting from the LSB side of the RSA parameters. We provide the first solution to this problem starting from the MSB side, and we can compare with the result of [START_REF] Heninger | Reconstructing RSA Private Keys from Random Key Bits[END_REF] as in Table 3. The data clearly shows that our technique yields results of comparable quality to those in [START_REF] Heninger | Reconstructing RSA Private Keys from Random Key Bits[END_REF]. However, the fraction of bits required to be known for the reconstruction in [START_REF] Heninger | Reconstructing RSA Private Keys from Random Key Bits[END_REF] is slightly lower compared to that in case of our method. This is because our algorithm entails a certain probability of success, whereas the approach of [START_REF] Heninger | Reconstructing RSA Private Keys from Random Key Bits[END_REF] is deterministic in nature.

Bits known from

Bits required in [START_REF] Heninger | Reconstructing RSA Private Keys from Random Key Bits[END_REF] Bits required for RecSK p, q 57% 61% p, q, d 42% 46% p, q, d, dp, dq 27% 38% Table 3. Comparison of our reconstruction algorithm with that of [START_REF] Heninger | Reconstructing RSA Private Keys from Random Key Bits[END_REF].

Maitra et al. [START_REF] Maitra | Factoring RSA modulus Using Prime Reconstruction from random known bits[END_REF] were the first to consider the reconstruction of primes p, q from the MSB side, but only when small contiguous blocks of bits are known. The probability of correct reconstruction in our case is same as [START_REF] Maitra | Factoring RSA modulus Using Prime Reconstruction from random known bits[END_REF], but we can reconstruct from random bits, which could not be resolved in [START_REF] Maitra | Factoring RSA modulus Using Prime Reconstruction from random known bits[END_REF].

Error Correction Algorithm

In case of our second problem, instead of knowing a few bits, we consider the situation where all the bits of the secret key SK are known, but there is a probability of error associated with each bit. This is the scenario introduced in [START_REF] Henecka | Correcting Errors in RSA Private Keys[END_REF], where the authors proved that when error rate is less than 0.237, one can correct all errors with expected polynomial time, starting from the LSB side.

We consider the same, but starting with the MSB. Suppose that the upper half of all RSA secret parameters p, q, d 2 , d p , d q are given, but with some error probability γ associated with each bit. We call the available values of the parameters p ′ , q ′ , d ′ 2 , d ′ p , d ′ q , each of which is erroneous to some extent. We correct the errors from the MSB side of the parameters, and propose the following.

Idea for Error Correction [CorSK]. Choose the parameters a (blocksize) and t (offset) for reconstruction, as before, and also choose a threshold for error to be used in this approach.

Step 0. In the Guess routine, we generate 2 a (all possible) options for the first a MSBs of p, pad the remaining portion by 0's, and store in an array A, say.

Step 1. For each pi ∈ A, we reconstruct first (at) MSBs of other parameters:

qi = N pi , d2i = k(N -pi -qi ) e , dp i = k p pi e , dq i = k q qi e
Step 2. For each i, find the Hamming distance of pi , qi , d2i , dp i , dq i with the available values p ′ , q ′ , d ′ 2 , d ′ p , d ′ q and calculate the sum of all these Hamming distances. The Hamming distance is calculated only for the concerned block of size a in all the parameters, and the sum is considered to be a measure for error. If this sum is less than the predefined threshold, we retain pi in A, and otherwise we discard pi from A to reduce the number of options.

Step 3. Find the maximum value of c such that c many initial MSBs of all the options are same, i.e., p1 [l] = p2 [l] = • • • = px [l] for all 1 ≤ l ≤ c but not for c < l ≤ a. As we have chosen the common bits of all possibilities, these c bits of p are correctly recovered. Iterate. We take the next block of a bits of p starting at the (c + 1)-th MSB, and repeat the Guess and Filter routines using the first (c + a) MSBs of p.

As before, this process is continued until half of p is recovered from the MSB side, after which one can factorize N using the idea of Coppersmith [START_REF] Coppersmith | Small solutions to polynomial equations and low exponent vulnerabilities[END_REF]. We will present our error correction algorithm CorSK more formally in the full version of the paper. The efficiency analysis will follow similar lines to those in [START_REF] Henecka | Correcting Errors in RSA Private Keys[END_REF] and the idea of Theorem 1. We will present the complete analysis in the extended full version of the paper. In case of practical experiments with our idea for error correction, we have so far been successful in correcting approximately 14% bit error in the SK parameters, using a block size a = 14 and offset t = 4. Note that this result is competitive with respect to the results published in [START_REF] Henecka | Correcting Errors in RSA Private Keys[END_REF], which could correct 17% bit error with similar block size. In the full paper, we shall present more experimental results as well as the corresponding theoretical bounds.

Conclusion

In this paper, we have discussed the factorization of N = pq, where the encryption exponent e is small, and partial information about the bits of the RSA secret parameters (p, q, d, d p , d q , q -1 mod p) is known. We have provided two solutions for reconstruction of RSA secret key from MSB side when random bits are known, and also when all the bits are known with some probability of error. In the final (full) version of the paper, we will include the following as well.

-Complete theoretical analysis of the general reconstruction algorithm RecSK.

-Formal algorithm and analysis of the error correction algorithm CorSK.

-Detailed experimental results to support the algorithms and related results.

We will also provide a lattice based general solution to the case where a large chunk of bits of the RSA parameters are missing from the beginning at the MSB side. Note that in such a case (50 initial bits are missing, say) our solution RecSK does not prove effective anymore. Thus a comprehensive description of this proposed lattice based technique will complete our solution for reconstruction and error correction of RSA parameters from the MSB side.

Table 2 .

 2 Experimental data for reconstruction algorithm RecSK.

		Random bits known from p, q and d
	Blocksize a	Offset t	Known fraction of bits δ (%)	Time T (seconds)
	25	5	53	1517
	30	5	46	10376
		Random bits known from p, q, d, dp and dq
	Blocksize a	Offset t	Known fraction of bits δ (%)	Time T (seconds)
	25	5	50	1042
	30	5	41	15685
	35	5	38	259210

The General Reconstruction Algorithm

In this section, we extend our idea of reconstruction to all the RSA secret parameters p, q, d, d p , d q (except for q -1 mod p). Given δ fraction of bits for each parameter, the following algorithm attempts to reconstruct the top half of p.

Input: N, e, k, kp, kq, and the known bits of p, q, d2, dp, dq. Output: Top half of the MSBs of p.

Choose parameters a, t, b = 0, c old = 1;

For first (a + b) MSBs of p, choose all possible options p and store in an Input: N , the known bits of q, d 2 , d p , d q , array A and parameters a, t, b. Output: Modified array A of bit strings.

Compare the known bits from the first (a + bt) MSBs of q with q, The efficiency analysis for RecSK extends the analysis performed for primes, and we will obtain a generalized version of Theorem 1, using the known bits of


George Drettakis

Maria Roussou
email: m.roussou@cs.ucl.ac.uk

Alex Reche

Nicolas Tsingos

Design and Evaluation of a Real-World Virtual Environment for Architecture and Urban Planning

In this paper we present a user-centered design approach to the development of a Virtual Environment (VE), by utilizing an iterative, user-informed process throughout the entire design and development cycle. A preliminary survey was first undertaken with endusers, i.e., architects, chief engineers and decision makers of a real-world architectural and urban planning project, followed by a study of the traditional workflow employed. We then determined the elements required to make the VE useful in the real-world setting, choosing appropriate graphical and auditory techniques to develop audiovisual VEs with a high level of realism. Our user-centered design approach guided the development of an appropriate interface and an evaluation methodology to test the overall usability of the system. The VE was evaluated both in the laboratory and, most importantly, in the users' natural work environments. In this study we present the choices we made as part of the design and evaluation methodologies employed, which successfully combined research goals with those of a real-world project.

Among other results, this evaluation suggests that involving users and designers from the beginning improves the effectiveness of the VE in the context of the real world urban planning project. Furthermore, it demonstrates that appropriate levels of realism, in particular spatialized 3D sound, high-detail vegetation and shadows, as well as the presence of rendered crowds, are significant for the design process and for communicating about designs; they respectively enable better appreciation of overall ambience of the VE, perception of space and physical objects as well as the sense of scale. We believe this study is of interest to VE researchers, designers and practitioners, as well as professionals interested in using VR in their workplace.

Introduction

Many of the Virtual Reality (VR) applications developed today are products of research that are either prototypes created within very specific contexts or are used for presentation purposes. Despite the promise and the development activity of over two decades, the number of real-world applications has remained small. The issues regarding the deployment of VR in everyday work contexts have been discussed many times and continue to revolve around the familiar practical difficulties: setting up special and costly hardware within facilities that are not easily transportable, requiring special teams of developers and maintenance staff, but also providing the high-level tools that will support users in their complex tasks [START_REF] Neale | A Front-Ended Approach to the User-Centred Design of VEs[END_REF] and can succeed in establishing a collaborative VR work environment amongst individuals of different disciplines [START_REF] Mackay | HCI, Natural Science and Design: A Framework for Triangulation Across Disciplines[END_REF]. Some specific sectors, such as the oil and gas or the automotive industry, have already firmly established design processes in which VR has an integrated role. For typical urban planning and architecture projects, however, VR has not found widespread use.

Experienced practitioners in the field of VR have indicated that to work effectively in a virtual environment (VE), the application content must include the ability to access or change environmental/system/meta parameters, create and manipulate particular objects, perform analyses, and export changes to permanent storage [START_REF] Sowizral | Panel session on Performing Work within Virtual Environments[END_REF]. While the current state of VE development has advanced its techniques to support these tasks, rarely does one find complete VEs that achieve both a high-quality realistic, immersive real-time environment and the level of interactivity required to carry out sufficiently complex real-world tasks.

The main goal of our study was to design, develop, and evaluate an interactive VE environment (see Fig. 1) with a high level of audiovisual realism in the context of a real-world application, using a user-centered methodology.

We chose the domains of architectural design and urban planning (UP), where we considered both realism, due to the representational nature of the work, and interactivity to be requirements of the work process. A detailed user requirements analysis with architects and urban planners [START_REF] Roussou | Requirements Analysis on Cultural Heritage -Education and Urban -Architectural Planning and Design Case Studies[END_REF] confirmed the suitability of our choice and led to a thorough study of the existing workflow in these domains. A key element throughout this work has been the establishment of a close collaboration with the end-users of a real-world urban planning project, involving the redesign of public spaces as part of the construction of a new Tramway in the city of Nice in France.

Related Work

Virtual reality development for architectural design and urban planning applications can be roughly grouped into two categories: applications that are used to design and display detailed 3D CAD models of architectural spaces/structures and rapid prototyping systems. In the first case, the challenge has been to visualize large data sets in as photorealistic a fashion as possible. These environments are mostly used for presentation, recreation, and educational purposes (e.g. review of architecture before it is actually built, cultural heritage reconstructions, 3D entertainment rides, etc.) where complex 3D spaces are constructed so they can be explored in walkthroughs [START_REF] Brooks | Walkthrough: A dynamic graphics system for simulating virtual buildings[END_REF][START_REF] Houston | Visualizing dynamic architectural environments[END_REF]. The majority of these projects allow for little to no interactivity beyond the user's ability to freely navigate about the environment.

On the other hand, the virtual prototyping environments allow immersive VR to be used in earlier phases of a design process and are thus designed to incorporate a higher level of interactivity and object manipulability. In most cases, these capabilities are implemented at the expense of visual realism, as they have been developed by computer scientists in order to further advance research in VR tools. Furthermore, most of these environments have not been used in real-world situations. Nevertheless, many interesting ideas have been introduced by architectural prototyping projects that we can draw from. The CALVIN project [START_REF] Leigh | Multi-perspective Collaborative Design in Persistent Networked Virtual Environments[END_REF], for example, introduced the idea of different perspectives, the mortal (ground-level) viewpoint and the deity (global above-ground) viewpoint, either of which users can assume in order to interact collaboratively in designing a space in VR. In a more applied and realworld context, the Virtual Los Angeles project [START_REF] Jepson | A real-time visualization system for large scale urban environments[END_REF] achieved impressive visualizations of urban environments; the results reported here could easily be integrated into such a system.

Augmented reality projects related to construction and urban planning have also been studied. Systems such as the Augmented Round Table [START_REF] Broll | The Augmented Round Table: a new Interface to Urban Planning and Architectural Design[END_REF] or Build-IT [START_REF] Rauterberg | BUILD-IT: a video-based interaction technique of a planning tool for construction and design[END_REF], concentrate more on the user interface aspects of such projects. The work of Ishii's group [START_REF] Ishii | Augmented urban planning workbench: Overlaying drawings, physical models and digital simulation[END_REF][START_REF] Ben-Joseph | Urban simulation and the luminous planning table bridging the gap between the digital and the tangible[END_REF]) is a very interesting study in the combination of physical models and computer augmentation, involving both computer scientists and architects. While this body of work is intriguing, we have made the choice to work exclusively with synthetic environments, allowing a more immersive approach and avoiding the need for complex calibration between real and virtual elements.

Architects have long used specialized 3D commercial tools such as Autodesk Revit1 and ArchiCAD2 . However, the visualization, realism and immersive capabilities of these packages are currently limited, while audio support is completely absent. In the long term, we hope that some of the findings described here will be incorporated in integrated versions of such systems.

Design

The basic premise of our VE design approach has been to engage architects, designers and decision makers from the first steps of the design. Implementing such a usercentered approach requires collecting and analyzing as much information about our users as possible, through a detailed user requirements process [START_REF] Roussou | Requirements Analysis on Cultural Heritage -Education and Urban -Architectural Planning and Design Case Studies[END_REF] and a deep understanding of how they work.

The city of Nice and the Greater Nice-Cote d'Azur Urban Community (CANCA) recently decided to build a Tramway. The project involves 8 km of rail in the most dense parts of the city, requiring the re-design of several open spaces such as the main city squares, "Place Garibaldi" and "Place Massena". We established a working relationship with the officials and the company of architects in charge of the project. Initially, we presented a simple VE prototype of a section of "Place Massena" to the "Mission Tramway", the organization in charge of the overall project (images can be seen in (Roussou, Drettakis, Tsingos, Reche, & Gallo, 2004)).

The result of this contact led to a closer collaboration with the architects on the redesign of "Place Garibaldi", and enabled us to gain access to all the project data. The architectural design of this square was of major importance, since the "Place Garibaldi" is a historic landmark and, according to many "the most beautiful square of the city". As such, many stakeholders participated in the decision making process: local elected officials (principally the mayor), the officials of the city council in charge of open spaces and public works, as well as higher state authorities at a national level who generally have a definitive say in any modification of a historical space. There is also a public consultation which started at the beginning and continues throughout the design process.

Our collaboration was founded on the principle of mutual benefit. We were inter- ested in studying and understanding the workflow to allow us to design novel VE tools that combine realism and interactivity, and to apply them in a real-world setting. The architects and decision makers of the Mission Tramway were interested in using the resulting interactive VE as an aid in decision making and brainstorming, as well as a presentation tool.

Study of End-User Design Workflow

Multiple discussions and the study of the architects' workflow allowed us to understand the architectural design process and how decisions were made. In particular, for the re-design of the square, several different concepts were proposed, with significant variations: a "Place d'armes" (military, "stone-only" square) in which no additional vegetation was to be allowed; a modern design, with additional vegetation; a more traditional design, with additional vegetation. The architects had a complex balancing act to follow. According to our interviews, they spent a while debating in numerous meetings the different merits of each choice, without advancing much.

The initial design process took place mainly between the municipal administration and the architects. At this stage, architects used simple fast "sketches" to communicate their ideas and the different options (examples shown in Fig. 2). Using this initial stage where they iterate over many experimental sketches on paper, the architects get an overall feel for the design, and sometimes will draw details of part of the site to capture the essence of specific elements, or add humans to give a sense of scale (Fig. 3).

The next stage is the production of photo-montages which are shown to the decision makers and elected officials (Fig. 4). These montages are used to achieve agreement by the different parties and, after this process, the overall "look and feel" of the design converges (i.e., the overall "stone look" of the square, the fact that the trees and the statues are maintained, etc.).

Development of the Realistic VE

Urban planning scenes include existing elements which do not change (such as building facades, etc.), but also the elements of the new planned space. To be useful as a design and presentation aid, a convincing level of realism needs to be achieved in the VE, both for the representation of the existing buildings and for the new elements that will be added. In this context, realism includes high-quality geometry and textures for buildings, high-quality models and display for vegetation, accurate and consistent lighting and relighting with shadows, vehicles and traffic simulation, population with individual and crowd animation with simulated behavior, accurate 3D sound rendering etc. To be included in a VE, the display/rendering of all of the above needs to be sufficiently fast to still result in acceptable frame rates. In our system, we have chosen to concentrate on a set of enhancements that emerged as important through our initial user needs analysis and for which we were able to provide efficient and appropriate solutions.

In particular, our system, the technical details of which have been presented elsewhere (Drettakis, Roussou, Tsingos, Reche, & Gallo, 2004;Roussou, Drettakis, et al., 2004), provides solutions for photographic capture of existing buildings, shadows, display of vegetation, 3D sound and crowds. We have used novel image-based reconstruction techniques to provide accurate capture of buildings at a medium scale (i.e., the size of a 200m x 200m square in a city), including high-quality textures and moderately complex geometry. We have also adapted perspective shadow maps (Stamminger & Drettakis, 2002) for use in a VE system, allowing the display of high-quality sharp shadows in real time. Our solution for display of vegetation is based on a mixed approach using point-based rendering and polygons [START_REF] Deussen | Interactive visualization of complex plant ecosystems[END_REF], which we adapted to our VE display system. This allowed display of 70 trees modelled with 80,000 polygons, using a level-of-detail switching between points and polygons. As a result there is fluid display of trees, while providing highquality, polygon-based display when the user moves closer. We have also developed a novel solution for rendering of high-quality spatialized 3D sound (Tsingos, Gallo, & Drettakis, 2004), which allows spatialization of a large number (around 300) of sound sources, enabling the use of true 3D sound in complex outdoor environments.

Finally, we have added simple crowd simulation to our environments [START_REF] Tecchia | Agent Behaviour Simulator (ABS): A Platform for Urban Behaviour Development[END_REF][START_REF] Tecchia | Visualizing crowds in real-time[END_REF] allowing the rapid display of a large number of humans, using rule-based flow simulation [START_REF] Stylianou | Scalable pedestrian simulation for virtual cities[END_REF].

All of these enhancements are included in a complete system, based on the XP (Pape, Imai, Anstey, Roussou, & DeFanti, 1998) VR authoring layer, built upon OpenGL Performer T M and CAVELib T M , where these are added as new classes in the extensible core library; their parameters are all controllable by scripts which can be edited by the artists and programmers developing the VE.

Design of the VE Interface

The design of our interface was inspired by the workflow described in Sect. 3.1. The initial idea was to preserve the "top view" corresponding to the familiar existing workflow (Fig. 5). We also have a ground-level "perspective view" (Fig. 6 (left)), corresponding to that used for photo-montages. Following suggestions by the architects, we also introduced an intermediate "balcony view", shown in Fig. 6 (right), where the viewer is presented with a view as if she were standing on the balcony of one of the surrounding buildings in the square, corresponding to higher level sketches (see Fig. 3). The user can manipulate dynamic elements in the scene, such as benches, umbrellas etc. in the top view, inspired by the iterative sketches process (Fig. 2). The user has the ability to freely switch between top, perspective and balcony view at any time and perform manipulations in all three. The left hand side contains the "insert" menus, for inserting the 3D models of different elements. The right hand side contains the "operations" on the inserted items, such as "resize", "resize width", "move", "rotate", "select" and "apply". Motion and placement are snapped to a grid in the scene.

The immersive display interface includes a tracked game-controller, or wand, with 12 buttons and a joystick. The 3D model of a rod "extends" the device in the virtual space (Fig. 5). Four of the buttons are used. One is the "action" button used for selec-tion of the menu items and for all other selection/deletion/manipulation actions. The remaining three buttons are mapped to the top, perspective and balcony views. At any time during the design session the user can move around in the environment and evaluate the result of her work either in perspective view or "balcony view", allowing a more "overall" view of the current state of the design.

Evaluation

Our evaluation methodology draws from the structured framework proposed by [START_REF] Gabbard | User-centered design and evaluation of virtual environments[END_REF] [START_REF] Bowman | A survey of usability evaluation in virtual environments: Classification and comparison of methods[END_REF] for the design and evaluation of user activity in VEs. This includes the combination of user needs analysis, user task scenarios, and usability evaluation. The user needs analysis was carried out at the very beginning of the project and led to the definition of the user task scenarios that were used in the evaluation sessions.

We performed evaluation of the VE both in a controlled laboratory context and in the natural work environment of the various individuals involved in the real urban planning project. The goal of the controlled experiments was to specifically evaluate the combined effect of realism and interactivity for a real-world urban planning task, as well as the system's usability. The goal of the situated tests was more to observe how non-expert users used the system in the context of real-world usage.

Experiment

Participants

We have chosen to limit our testing to a small number of users and follow an in-depth qualitative approach. One of the reasons for this is the obvious difficulty in evaluations of real-world situations, i.e., getting busy, highly qualified professionals to agree in participating in experimentation, which requires a significant investment in time. Other reasons include the highly experimental nature of the prototypes and the use of innovative and relatively inaccessible equipment (tracked immersive VR displays) in contexts where these had not been used before.

Thus, we conducted a usability study in the controlled setting of our laboratory with three of the collaborating professional architects, all directly involved in the real Nice Tramway project, and specifically in the design of the new Garibaldi square. Prior to the sessions with the architects, we ran pilot studies with engineers who had no previous VR or computer graphics experience.

Method

Our evaluation instruments included direct observation, where users performed the various tasks whilst being observed (and videotaped) by a facilitator using a think-aloud pro-tocol [START_REF] Ericsson | Protocol Analysis: Verbal Reports as Data[END_REF], a post-experiment questionnaire and post-experiment interviews.

The questionnaire was developed to identify the effect of realism as well as the user's perception of the effectiveness and efficiency of the system, and their level of satisfaction with the interaction. It was constructed by merging a number of standard questionnaires, with questions on a 1-7 Likert scale.

The informal interview that followed the experience aimed at identifying the issues involved in the in situ usage of the system, where the use of a questionnaire does not make sense.

Tasks and Procedure

The experiment took place on a Barco Baron workbench3 with the tracked game controller operating as described previously (Fig. 7). The participant was head-tracked and wore active stereo glasses. The main experiment was preceded by training with a simple virtual environment, using the same interface as in the main experiment. The user practiced in the training environment until she felt comfortable with the interface, typically for 10-15 minutes.

The VE used for the main experiment included the entire environment of the new design of Place Garibaldi (Fig. 1). The users were asked to carry out a set of predefined tasks, which accurately represented the intended actual use of the application, as specified during the user needs analysis. The tasks involved placing, sizing and arranging special tents (umbrellas) and stone benches in three of the four corners of the Place, as seen from above (Fig. 5). Each of the three corners was color-coded with a different colored umbrella and represented, implicitly, a separate sub-task that included different realism features of the VE. In other words, each corner was displayed with a different set of realism enhancements, as follows:

• The sub-task in the lower right corner (blue umbrellas) was displayed with shadows, point-based trees and sound (i.e., visual enhancements and sound).

• The sub-task in the lower left corner (green umbrellas) used "standard" VR quality (i.e., no shadows, no sound, billboard trees, and no crowds).

• The sub-task in the upper left corner (mixed-color umbrellas) was displayed with all enhancements (shadows, point-based trees, sound and crowds).

In this way, the realistic VE enhancements that we developed and wished to evaluate (high-quality shadows, realistic point-based vegetation, 3D sound and crowds) were encoded into the same scene, as part of one experiment. Each user was presented with the top-view at the outset, and was asked to manipulate objects in each one of the corners/color codes in sequence, starting from the lower right. The order in which the levels of realism were tested was pre-determined; we chose to display with enhancements (except crowds) first, then no-enhancements and then all enhancements with crowds, in that order, to avoid an implicit ranking of quality. The user was not explicitly informed of the difference in realism elements, and we attempted to identify their relative importance in the questionnaire.

Field Deployment of the System

In addition to the controlled lab experiments, the system has been used at several different occasions in the context of the real Tramway project. We visited the authorities and the architectural offices at several occasions and report here only the most significant meetings. Specifically, we describe three cases of situated usage: a decision meeting at the city hall, a brainstorming session with the official project working group, and a public event in which different variants for the design of the "Place Garibaldi" were presented.

City Hall Decision Meeting

The first case was a discussion of a planned proposal for the choice of the type of trees to be used in the square. The choices included either the 3 meter-high orange trees or the 8-meter high oak (see Fig. 8). As the meeting took place at the Nice City Hall, our VE was presented on a portable system4 .

Figure 8: Snapshots of the different solutions for Place Garibaldi, used in the City Hall meeting and the brainstorming session with the architects. Left, the "orange tree" solution; right, the "oak tree" solution. Note how shadow coverage is very different in each.

The working group involved a total of ten persons, mainly high-ranking city officials in charge of public spaces and urban planning, and the architects in charge of the overall project.

The VE included all the realism features of the workbench system. The two scenarios (orange trees and oak trees) were mapped onto two different buttons on the gamepad device, which the members of the working group used in order to explore the different views and locations for the trees, test spatial relationships in the placement of other elements, review the different effect of shadows, etc.

Brainstorming session

Another example of field deployment involved the use of the full VE system (tracked stereo-vision workbench) for a brainstorming session. Two of the main architects and a designer participated in this session and used the system as an opportunity to discuss issues concerning the design of the square, most notably the choice of trees and ground elements.

The users visited different angles of the square, examined the different tree options as in the City Hall meeting, and discussed choice of material type and the placement of elements.

Presentation of Different Options to Officials

The third case of field deployment was the presentation of the results of the project in a public event. Several high-ranking officials of the project and the municipality were present. The public event coincided in time with a public hearing, held to discuss various options for the square, concerning the questions of vegetation and the presence or absence of cars.

Following sketches of the architects we created a virtual environment showing the four scenarios. These were a "Place d'armes" ("military-style", "stone-only" square) where no trees and no cars are present, a "stone-only" square with cars around the square, a pedestrian square with trees and no cars and a pedestrian square with trees and cars around it, all shown in Fig. 9. The politicians and engineers all used the system to navigate around the VE, both at ground level and in "balcony view", allowing them to evaluate the quality of the design, the effects of noise and sound in the presence/absence of traffic and crowds.

Evaluation Results and Discussion

Observations from the laboratory experiment

We classify our observations by learnability and ease of use, effectiveness and efficiency, user satisfaction, VE/interface features and realism. Our observations are summarised in Table 1 in the Appendix.

In terms of learnability and ease of use, the participants ranked the system highly (6.7 average on the Likert scale with a standard deviation of 0.6 for ease of use, 4.7 (2.5) for learning) and stated that they were able to use the tool without difficulty; 2 out of the 3 participants had no experience with interactive 3D systems or video games.

In terms of effectiveness and efficiency, there was strong approval (a mean of 5.0 (1.7) on the Likert scale) of the utility of the tool and the fact that the system would improve productivity in the workplace. The top view, although familiar, was judged useful (mean 5.0 (2.0) on the Likert scale for the top view), while the balcony view was rated as very useful (mean 6.0 (1.7)). However, from observing the videos and the interviews, it became clear that manipulation precision was insufficient due to the large distance from the object being manipulated. The solution of a mixed 2D-3D interface was suggested, where a "pen-like" device could be used to directly place objects onto the top-view, as is currently done in existing CAD tools. The need to have the same interface as CAD tools for these tasks was explicitly mentioned by one user. Another participant stated that the perception of ambience and scale were extremely useful and important for an architect in the evaluation of an urban planning project, and found that the tool had great potential for brainstorming.

In terms of user satisfaction, all users stated, both in the questionnaire and during the interviews, that they liked the tool. In the interviews, one user stated a preference for faster response time vs. enhanced realism; also, that one of the main values of the system was that it removes the "break" which exists between traditional 3D CAD systems and the resulting design.

In terms of VE interface features, the balcony view was used extensively. All users agreed that this was a particularly useful view of the environment, and that it helped in their judgement of the resulting design, but also during the design.

Concerning realism, the quality of realism offered by image-based facade textures and the mixed point/polygon-based vegetation were identified as being important, allowing users to better understand the final effect of the placement of trees on the overall design (see Fig. 10,right). The ability to have the true high-quality 3D leaves when zooming in was singled out as being important.

Differences in realism between billboards and point-based trees or the presence/absence of shadows did not show up in the questionnaire ranking. However, in the interviews the users responded that they were concentrating on the task and all identified the importance of shadows for placement and sense of scale but also in terms of appreciation of shadow/sun coverage.

The presence of human figures was judged central (see Fig. 10,left), in particular as a marker of scale. As mentioned before, human figures are used in traditional drawings in this manner (Fig. 3).

The inclusion of spatialized 3D sound was judged as very important to evaluate the overall ambience and atmosphere created by a certain design, in the presence of fountains, the tramway and buses. This was the one item of realism whose presence/absence was noticed by 2 out of 3 participants.

Observations from field deployment

The first interesting observation was that several people at the City Hall meeting considered the representation to be too realistic. The reason stated was that the public would believe that this would be the exact design thus removing all freedom for the realisation of the final project; with drawings, people are more aware of the level of abstraction of the design. Nonetheless, the group considered that this was an excellent tool to help with decision-making and that, with appropriate attention to accuracy in details (e.g., color of stones in the square etc.), it could be used for demonstration purposes. The participants used the different views, singling out the balcony view, and the views with different types of trees, shadows and vegetation and stated that use of the system had brought significant clarification to their understanding of the project.

In the brainstorming session the architects and designer also worked mainly on the choice of trees. However, more time was spent in details, for example the material used to represent ground elements (type of wood/stone etc.), or the spacing between the trees and the choice of their number (2 or 3 rows etc.) The tool, as evidenced by observation of their discussions, helped the architects to understand the space and ambience created by their design in a manner which was not previously possible.

In the public event, the engineers and politicians spent half the time at the ground level and half using the balcony view. The users switched between the different scenarios, and were interested in questions of sound and noise at given positions during their walkthroughs of the environment, the effect of shadow coverage, and the sense of scale given through the presence of crowds. At one point the municipal councillor in charge of all transportation issues, declared that things were much clearer and that he now understood the implications of placing trees or a road around the Square.

Discussion

Our experience reported here indicates that it is important to engage real users in the process of design and evaluation for real-world VEs, despite the difficulties of such a choice [START_REF] Swan | A Comparative Study of User Performance in a Map-Based Virtual Environment[END_REF]. Even though the formal experiment only involved 3 users, a total of about 25 different people used the system in the experiment and in the three in-situ usages described previously. Involving these users allowed us to make better choices, both in the design of the VE and its interface, and provided a wealth of feedback which would have been completely unavailable if we had limited the experiments to graduate students of our institutes.

The second element which we consider important is that of realism. At the outset of the project, we believed that realism is definitely desirable and important. What is more interesting is to see which combination of factors were identified by the users as being important. The sense of scale given by the combination of realistic vegetation and human figures/crowds was an important effect which we had not suspected initially. We were not completely sure how important the presence of 3D sound would be for architects, since they do not have access to such information in their traditional workflow. Our interviews and our observation of the videos indicate that 3D spatialized audio is a central element which allows the architect to better understand the ambience of the design, and better judge the overall result. The 3D sound simulation was also judged very important in the case of multiple scenarios, where the presence of vehicles was a variable of the design. The use of shadows and their importance for the judgement of sun coverage was also a factor whose importance we had initially underestimated. At the outset, we were mainly concerned with the importance of shadows as a good indicator of spatial relationships [START_REF] Wanger | Perceiving spatial relationships in computer-generated images[END_REF]; the above-mentioned issues were brought up during usage. In general, once attention is drawn to such a fact, high level stimuli can result: the users reported that they felt that the alternative with smaller trees conveyed a sense of being "hotter" than that with the large trees and larger shadows.

It may seem that the request for less realism, expressed in one of the in-situ meetings, contradicts the above. However, we believe that it simply reflects a question of appropriate use of realism, depending on the context. In the specific context where politicians or designers do not wish to make a firm commitment, an artistic depiction may be appropriate; for all other cases cited here, we believe that the need for realism is clear. The idea of conveying a sense of an image as an "artistic impression" rather than a reflection of a future reality, is central to the domain of non-photorealistic rendering [START_REF] Gooch | Non-photorealistic rendering[END_REF], and an interesting direction for future research.

In terms of VR capabilities, multiple views, and in particular the "balcony view" were considered very useful by all users, both in the controlled experiment and in the various in-situ usages. For the users who manipulated the scenes, our interface was judged useful (in particular when positioning and resizing the umbrellas and benches), but the limitations of our prototype design, both in terms of ease of use/precision and in terms of latency do not allow significant conclusions on these aspects.

Conclusions

In this paper we report on a user-centered design in the context of a real-world application. We argue for a combined approach to evaluation in such a context, which uses both "lab experiments" and in-situ real-world usage. Despite the small number of subjects for the controlled experiment, a reasonable number of people (around 25) actually used the system. We believe that we have acquired rich results because they involve an in-depth observation of a real work process, a VE design with the involvement of the actual non-IT domain expert users, and the in situ use in the decision making process of a real project.

To summarize, our study indicates the pertinence of our combined evaluation approach for real-world applications, and the utility of our VE in the context of an urban planning project; that both audio and visual realism, such as 3D sound, shadows and sun coverage, vegetation and crowds, all contribute to better understanding of the VE and aid in the tasks at hand, and finally that VE-specific aspects such as multiple views are important.

In terms of future work, there are many directions to pursue. The interface issues noted by the users (precision in the top-view, etc.) need to be resolved, as well as the issues of latency, by integrating and applying graphics acceleration algorithms (e.g., [START_REF] Luebke | Level of Detail for 3D Graphics[END_REF]). The physical calibration of colors and lighting, an issue brought up at the City Hall meeting, is a valid point for usage in real projects. There are known techniques for color calibration, which use photographs of calibration panels to gamma-correct the displays [START_REF] Fairchild | Color appearance models[END_REF]. Another interesting direction to explore is the investigation of the use of artistic renderings in VEs [START_REF] Roussou | Photorealism and Non-Photorealism in Virtual Heritage Representation[END_REF], as well as an equivalent and more challenging approach to rendering sound. Finally, an area of future research is the use of this environment for quantitative experiments investigating specific issues, for example related to audiovisual effects in VEs. The realistic quality of the VE may be important in inducing a strong sense of presence, and thus can be used to help the users concentrate on specific tasks, allowing us to isolate specific variables (for example sound source localization, speed of execution for each task, etc.).

Although this approach of engaging users in the design is time and resource intensive, we consider it to be worthwhile and will continue to explore the application of HCI models into the design of VEs. We believe that our approach, which combines a more controlled evaluation with field deployment, provides promise for the development of environments and tools that can be of real value to their users. This is reinforced by the fact that there has been strong interest in further usage of our VE for future developments in the Tramway project.

Figure 1 :

 1 Figure 1: The Virtual Environment of Place Garibaldi in Nice, France, constructed for the study of a future Tramway project.

Figure 2 :

 2 Figure 2: Fast architectural sketches of Place Garibaldi. Black circles correspond to trees; the curved tramway line is shown passing through the square. The large existing oaks are also shown, as well as different options for the statue, in a round or square casing.

Figure 3 :

 3 Figure 3: (Left) Perspectives can be used for an overall view of the design. (Right) More involved perspectives can be used to illustrate specific details in the scene.

Figure 4 :

 4 Figure 4: Detailed photo-montages are used to present the project to decision makers.

Figure 5 :

 5 Figure 5: The top view of the VE is displayed with two sets of menus for the insertion and manipulation of dynamic objects. An element (shown with the small circle) is attached to the end of the rod and can be moved and positioned freely.

Figure 6 :

 6 Figure 6: (Left) Simulator snapshot of the perspective view. Note the realism of the captured facades of the buildings, shadows and point-based rendering of trees. (Right) Balcony view of the Place Garibaldi, showing the Tramway passing through the square.

Figure 7 :

 7 Figure 7: View of a user of the system on the workbench during the experiment (the screen shows the actual stereo display).

Figure 9 :

 9 Figure 9: Screenshots of the 4 scenarios used during the presentation to officials.

Figure 10 :

 10 Figure 10: Left: an example with crowds in the Square. Right: Mixed pointbased/polygon trees.

Revit: Autodesk corporation, http://www.autodesk.com/.

ArchiCAD: Graphisoft corporation, http://www.graphisoft.com/.

The workbench runs on a dual-processor Xeon PC (2.4Ghz), with 1Gb of memory, in above-below stereo mode and an NVidia 5950 Ultra graphics card.

The system included a laptop with a GeForce4Go graphics card, a portable projector with a stereo loud-speaker based sound system and the standard gamepad-based controller.

Acknowledgements

We thank the CANCA, the City of Nice and the Mission Tramway, for accepting this collaboration and providing access to the data and the process. We are indebted to the AURA architects Marc Dalibard, André Jollivet and Emilie Hélardot, who worked with us and generously provided their valuable time and effort for the success of this project. Please note that the images presented in this work do not engage any of the authorities in any way, and that the decision process for the design of the Place is still far from complete. Special thanks are due to Manuel Asselot, Alexandre Olivier, and Franco Tecchia for their contribution in a previous version of this paper. Thanks also to David Geldreich, Emmanuel Gallo and Soteris Stylianou for systems and development help. Thanks also to the generous donation of the Maya software from Autodesk/Alias. This work is part of CREATE, a 3-year RTD project funded by the 5th Framework Information Society Technologies (IST) Programme of the European Union (IST-2001-34231), http://www.cs.ucl.ac.uk/create/http://www.cs.ucl.ac.uk/create/. The authors thank all the individuals from partner institutions that have contributed to the development of the project, and in particular the coordinator Céline Loscos.


Santanu Sarkar
email: sarkar.santanu.bir@gmail.com

Subhamoy Maitra

Cryptanalysis of Dual CRT-RSA

Keywords: RSA, CRT-RSA, Dual CRT-RSA, Cryptanalysis, Lattices

Several schemes under the framework of Dual RSA have been proposed by Sun et al (IEEE-IT, August 2007). We here concentrate on the Dual CRT-RSA scheme and present certain range of parameters for which this is insecure. As a corollary of our work, we prove that the Dual Generalized Rebalanced-RSA (Scheme III of Sun et al) can be efficiently broken for a significant region where the scheme has been claimed to be secure.

Introduction

The famous RSA public key cryptosystem has been proposed in [START_REF] Rivest | A Method for Obtaining Digital Signatures and Public Key Cryptosystems[END_REF] and this is possibly the most studied topic in cryptology research. In [START_REF] Sun | Dual RSA and its applications[END_REF], a variant of RSA, named Dual RSA, has been described. Dual RSA provides two different instances of RSA that share the same public and private exponents. Here we have two different RSA moduli N 1 = p 1 q 1 , N 2 = p 2 q 2 such that the public key e and the private key d satisfies ed ≡ 1 mod φ(N 1 ) as well as ed ≡ 1 mod φ(N 2 ). In general, p 1 , q 1 , p 2 , q 2 are taken to be of same bit size and we also follow that here. In [START_REF] Sun | Dual RSA and its applications[END_REF], the authors suggested relevant applications of Dual RSA that include blind signatures and authentication/secrecy.

To make the RSA decryption faster, the Chinese Remainder Theorem (CRT) has been exploited and the corresponding version is known as CRT-RSA [START_REF] Quisquater | Fast decipherment algorithm for RSA publickey cryptosystem[END_REF]. In this variant, there are two private exponents d p , d q such that ed p ≡ 1 mod (p-1) and ed q ≡ 1 mod (q -1). The encryption method is the same as it is done in RSA. To decrypt the ciphertext C, one needs to calculate C p ≡ C dp mod p and C q ≡ C dq mod q. From C p , C q one can get the plaintext M by the application of CRT.

As CRT-RSA is faster than RSA, with the similar motivation, a CRT variant of Dual RSA has been presented in [START_REF] Sun | Dual RSA and its applications[END_REF], which we refer as Dual CRT-RSA. This variant consists of two different RSA moduli N 1 = p 1 q 1 , N 2 = p 2 q 2 with same public exponent e and private exponents d p , d q . Hence in this case we have, ed p ≡ 1 mod (p 1 -1) ≡ 1 mod (p 2 -1) and ed q ≡ 1 mod (q 1 -1) ≡ 1 mod (q 2 -1). Throughout this paper we will consider N as an integer of same bit-size as of N 1 , N 2 .

The outline of the paper is as follows. Let e = N α , α > 1 4 and d p , d q ≈ N δ . One may note that both ed p and ed q are greater than √ N and thus we always have α + δ > 1 2 . In Section 2, we show that the Dual CRT-RSA scheme is insecure when (i) δ < 1-α 2ǫ for a very small quantity ǫ, and (ii) δ < 3-4α 5 and α + δ > 1 2 + ǫ ′ , for a very small quantity ǫ ′ . A method for generating a certain kind of Dual CRT-RSA keys has been presented in Scheme III of [START_REF] Sun | Dual RSA and its applications[END_REF] and it is referred as Dual Generalized Rebalanced-RSA (in short, we call it DGRR). This method can generate Dual CRT-RSA keys for e < N 1 2 . Applying our results in Section 2, it is shown that the keys generated in DGRR are completely insecure for N 1 3 < e < N 1 2 . Further, we improve some of the existing cryptanalytic results for e ≤ N 1 3 too. These are presented in Section 3. Detailed experimental results are presented in Section 4.

The Main Results

As N 1 = p 1 q 1 and N 2 = p 2 q 2 , we have the following four identities for Dual CRT-RSA.

ed p = 1 + k p1 (p 1 -1), ed q = 1 + k q1 (q 1 -1), ed p = 1 + k p2 (p 2 -1), ed q = 1 + k q2 (q 2 -1). (1)
In this section we present two cryptanalytic results on Dual CRT-RSA. Let us start with the first one.

Theorem 1. Let N 1 , N 2 be the public moduli of Dual CRT-RSA and e = N α , d p , d q < N δ . Consider that g = N γ , g 1 = N γ1 and g 2 = N γ2 be such that g = gcd(N 1 -1, N 2 -1), g 1 = gcd(e, N1-1 g ), and g 2 = gcd(e, N2-1 g ). Let ǫ = γ1+γ2+2γ 2 . Then, for α > 1 4 , one can factor

N 1 , N 2 in poly(log N) time if δ < 1-α 2 -ǫ.
Proof. From the first two equations of (1) we have

(ed p -1 + k p1 ) (ed q -1 + k q1 ) = k p1 k q1 N 1 .
From this we get,

e 2 d p d q + e (d p (k p1 -1) + d q (k q1 -1)) + (1 -k p1 -k q1 ) = (N 1 -1) k p1 k q1 . (2) Let, N ′ 1 = N1-1 gg1 and N ′ 2 = N2-1 gg2 . Now consider the polynomial f 1 (x 1 , x 2 , x 3 ) = e 2 x 1 + ex 2 + x 3 . Let y 1 = d p d q , y 2 = d p (k p1 -1) + d q (k q1 -1), and y 3 = 1-k p1 -k q1 . Clearly, f 1 (y 1 , y 2 , y 3 ) ≡ 0 mod N ′ 1 .
Similarly, from the last two equations of (1), we have e 2 d p d q + e (d p (k p2 -1)

+ d q (k q2 -1)) + (1 -k p2 -k q2 ) = (N 2 -1) k p2 k q2 . Now assume y 4 = d p (k p2 -1)+d q (k q2 -1) and y 5 = 1-k p2 -k q2 .
For the polynomial f 2 (x 1 , x 4 , x 5 ) = e 2 x 1 + ex 4 + x 5 , we have f 2 (y 1 , y 4 , y 5 ) ≡ 0 mod N ′ 2 . Now using the Chinese Remainder Theorem (CRT) over the coeffi-

cients of f 1 , f 2 , one can construct a polynomial f 3 (x 1 , x 2 , x 3 , x 4 , x 5 ) = a 1 x 1 + a 2 x 2 + a 3 x 3 + a 4 x 4 + a 5 x 5 , such that f 3 (y 1 , y 2 , y 3 , y 4 , y 5 ) ≡ 0 mod N ′ 1 N ′ 2 . Though the polynomials f 1 , f 2 are of the same form, their roots are different in differ- ent moduli N ′ 1 , N ′ 2 . Since gcd(e, N ′ 1 ) = gcd(e, N ′ 2 ) = 1 and a 1 ≡ e 2 mod N ′ 1 ≡ e 2 mod N ′ 2 , we have gcd(a 1 , N ′ 1 N ′ 2 ) = 1. So from f 3 , we can obtain another poly- nomial f 4 = x 1 + b 2 x 2 + b 3 x 3 + b 4 x 4 + b 5 x 5 , such that f 4 (y 1 , y 2 , y 3 , y 4 , y 5 ) ≡ 0 mod N ′ 1 N ′ 2 . Note that N ′ 1 N ′ 2 ≈ N 2 g 2 g1g2 = N 2-2γ-γ1-γ2 . Let, X 1 = N 2δ , X 2 = N α+2δ-1 2 , X 3 = N α+δ-1 2 , X 4 = N α+2δ-1 2 , X 5 = N α+δ-1 2 . Clearly X 1 , X 2 , X 3 , X 4 , X 5
are the upper bounds of y 1 , y 2 , y 3 , y 4 , y 5 neglecting the small constants. We want to find the modular solution of f 4 . Now f 4 is a linear polynomial of degree 1. Using "Basic Strategy" of [5, Section 3.3.1], one can solve f 4 in poly(log N) time by LLL [START_REF] Lenstra | Factoring Polynomials with Rational Coefficients[END_REF] algorithm if

X 1 X 2 X 3 X 4 X 5 < N ′ 1 N ′ 2 . (3)
Putting the values of X 1 , X 2 , X 3 , X 4 and X 5 in Inequality (3), we get

δ < 1 -α 2 - γ 1 + γ 2 + 2γ 8 . (4)
From the equation ( 2), we have

(N 1 -1)k p1 k q1 ≡ 1 -k p1 -k q1 mod e, i.e., N1-1 gg1 gg 1 k p1 k q1 ≡ 1 -k p1 -k q1 mod e.
Thus when

gg 1 k p1 k q1 < e, (5)
one can calculate gg 1 k p1 k q1 = N1-1 gg1 -1 (1 -k p1 -k q1 ) mod e. Hence it is possi- ble to obtain k p1 k q1 . Putting g = N γ , g 1 = N γ1 , k p1 ≤ N α+δ-1 2 , k p1 ≤ N α+δ-1 2 in (5), we have δ < 1 -α -γ -γ 1 2 . (6)
Since

1-α-γ1-γ2-2γ 2 ≤ min 1-α 2 -γ1+γ2+2γ 8 , 1-α-γ-γ1 2
, the conditions ( 4) and ( 6) on δ will be satisfied

if δ < 1-α-γ1-γ2-2γ 2 . Hence k p1 + k q1 and k p1 k q1 can be obtained if δ < 1-α-γ1-γ2-2γ 2 = 1-α 2 -ǫ, where ǫ = γ1+γ2+2γ 2 .
From the knowledge of k p1 + k q1 and k p1 k q1 , one gets k p1 , k q1 . Since

p 1 ≡ 1 -k -1
p1 mod e, one can factor N 1 in poly(log N) time obtaining half of the LSBs of p 1 (as explained in [2, Corollary 1]) when α > 1 4 . The proof for factoring N 2 is similar. ⊓ ⊔

In general g, g 1 , g 2 will be small, and so γ, γ 1 , γ 2 → 0, which gives ǫ → 0. We have also found that the experimental results support this claim.

Observation on experimental setup

In the proof of Theorem 1, we have studied the conditions when one can collect the roots efficiently. To actually collect the roots we use Gröbner basis techniques [START_REF] Jochemsz | Cryptanalysis of RSA Variants Using Small Roots of Polynomials[END_REF] and in all the experiments find polynomials of the form x 3 -

1-kp 1 -kq 1 1-kp 2 -kq 2 y 3 . In all these situations, gcd(1 -k p1 -k q1 , 1 -k p2 -k q2 ) is small, that helps us to collect 1 -k p1 -k q1 , 1 -k p2 -k q2 efficiently.
Directly one cannot obtain y 1 , y 2 , y 4 , but we use the following technique to factorize N 1 and N 2 in the experiments. Moreover, in Theorem 1, we have the constraint α > 1 4 . Using the following approach one can remove the lower bound on α.

Let g 3 = N γ3 and g 4 = N γ4 such that g 3 = gcd(e, N 1 -1) and g 4 = gcd(e, N 2 -1). From the knowledge of 1-k p1 -k q1 and 1-k p2 -k q2 , one can find k p1 k q1 ≡ a mod e g3 and k p2 k q2 ≡ b mod e g4 . So, we can write k p1 k q1 = a + e g3 z 1 and k p2 k q2 = b + e g4 z 2 , where z 1 , z 2 are unknown. Note that

z 1 ≈ N γ3+α+2δ-1 and z 2 ≈ N γ4+α+2δ-1 . Let z 3 = k p1 k q1 (N 1 -1) -k p2 k q2 (N 2 -1). It is clear that |z 3 | ≈ |k p1 k q1 (p 1 + q 1 )| ≈ N 2α+2δ-1 2
. Hence, we have to find the root (z 1 , z 2 , z 3 ) of the polynomial h(x 1 , x 2 , x 3 ) = (a+ e g3 x 1 )(N

1 -1)-(b+ e g4 x 2 )(N 2 - 1) -x 3 . Let, X 1 = N γ3+α+2δ-1 , X 2 = N γ4+α+2δ-1 and X 3 = N 2α+2δ-1 2 . Clearly, X 1 , X 2 , X 3 are the upper bounds of the z 1 , z 2 , z 3 . Note that W = ||h(x 1 X 1 , x 2 X 2 , x 3 X 3 )|| ∞ ≥ e g3 X 1 N = N 2α+2δ .
We can find the root of h in poly(log N) time if X 1 X 2 X 3 < W . Now putting the values of X 1 , X 2 , X 3 and the lower bound of W in X 1 X 2 X 3 < W , we have δ < 5 8 -α 2 -γ3+γ4 4 . Since γ 3 , γ 4 → 0 in general, the required upper bound on δ is δ < 5 8 -α 2 . Note that

5 8 -α 2 > 1-α 2
, so upper bound of δ in this case is better than the upper bound of δ in Theorem 1. After getting k p1 k q1 and k p2 k q2 , one can factor N 1 and N 2 using the approach of [4, Section 7.5.2] when α

+ δ > 1 2 + log N K ′ where K ′ = gcd(k p1 k q1 , k p2 k q2 ).
Remark 1. The experimental results, as presented in Section 4, are better than the theoretical upper bound on δ in Theorem 1. This is because the practical runs of the LLL algorithm [START_REF] Lenstra | Factoring Polynomials with Rational Coefficients[END_REF] tend to provide basis vectors that may be shorter than the estimated theoretical upper bound. Further, it may also provide one of the shortest vectors as the lattice dimension is quite small, i.e., 5. Thus, it may very well happen that we may cross the upper bound of δ in Theorem 1, i.e., 1-α 2 (considering ǫ → 0), during the experiments. Given this, one can use the approach described above to find k p1 k q1 , k p2 k q2 from the knowledge of k p1 + k q1 , k p2 + k q2 . This works for a higher upper bound of δ (than in Theorem 1), i.e., 5 8 -α 2 (considering γ3+γ4 4 → 0).

Better cryptanalytic bound for small e

Let us now show that one can get a better bound than that of Theorem 1 for smaller values of e.

Theorem 2. Let N 1 , N 2 be the public moduli of Dual CRT-RSA and e = N α , d p , d q < N δ . Then one can factor

N 1 , N 2 in poly(log N) time if δ < 3-4α 5 given α + δ > 1 2 + ǫ ′ , where ǫ ′ = log N (K ′ ), where K ′ = gcd(k p1 k q1 , k p2 k q2 ).
Proof. We have two identities:

e 2 d p d q + e (d p (k p1 -1) + d q (k q1 -1)) + (1 -k p1 -k q1 ) = (N 1 -1) k p1 k q1 , e 2 d p d q + e (d p (k p2 -1) + d q (k q2 -1)) + (1 -k p2 -k q2 ) = (N 2 -1) k p2 k q2 . From these we get, e (d q k p1 + d p k q1 -d q k p2 -d p k q2 ) + (-k p1 -k q1 + k p2 + k q2 ) + (N 2 -1)k p2 k q2 = (N 1 -1)k p1 k q1 . Now consider the polynomial f = ex + y + (N 2 -1)z. Clearly, f (d q k p1 + d p k q1 -d q k p2 -d p k q2 , -k p1 -k q1 + k p2 + k q2 , k p2 k q2 ) ≡ 0 mod (N 1 -1). Let X = N α+2δ-1 2 , Y = N α+δ-1 2
and Z = N 2α+2δ-1 . Then neglecting small constants, X, Y and Z will be upper bound of the modular root (

d q k p1 + d p k q1 - d q k p2 -d p k q2 , -k p1 -k q1 + k p2 + k q2 , k p2 k q2 ) of f . One can solve f 4 in poly(log N) time if XY Z < N 1 -1. Putting the values of X, Y, Z in XY Z < N 1 -1, we get δ < 3-4α
5 . As we have found k p2 k q2 as the last component of the root of f , one can similarly find k p1 k q1 . After getting k p1 k q1 and k p2 k q2 , one can factor N 1 and N 2 using the approach of [4, Section 7.5.2, Page 157] when α

+ δ > 1 2 + log N K ′ where K ′ = gcd(k p1 k q1 , k p2 k q2 ).
⊓ ⊔ Similar to our comment on ǫ in Theorem 1, we note that in general ǫ ′ → 0 and this is also confirmed experimentally. Thus in the following part of this paper we always consider that ǫ → 0 as well as ǫ ′ → 0. While implementing the idea of Theorem 2, we use Gröbner basis technique to collect the root and in all the experiments we obtain polynomials of the form y -

-kp 1 -kq 1 +kp 2 +kq 2 kp 2 kq 2 z.
Since in all the cases gcd(-

k p1 -k q1 + k p2 + k q2 , k p2 k q2
) is very small, we can successfully collect k p2 k q2 . Similarly, we can successfully collect k p1 k q1 as well.

From the Theorems 1, 2, we get the upper bound of δ as 1-α 2 and 3-4α 5 respectively. Now, 1-α 2 < 3-4α 5 iff α < 1 3 . Hence, Theorem 2 will be better than Theorem 1 for α < 1 3 . Later in Section 4, we will discuss the comparison with respect to the experimental results.

Comparison with Existing Results

Using continued fraction over N1-1 N2-1 , in [START_REF] Hinek | On the Security of Some Variants of RSA[END_REF], it is proved that when δ < 5 8α, one can find kp 2 kq 2 kp 1 kq 1 in the lowest terms. Using the knowledge of

kp 2 kq 2 kp 1 kq 1 , in the lowest term, one can factor N 1 , N 2 in polynomial time if α + δ > 1 2 + log N (K ′ )
, where K ′ = gcd(k p2 k q2 , k p1 k q1 ). Since in general K ′ will be of constant order, we can say one can factor N 1 , N 2 using continued fraction approach if δ < 5 8α. In Theorem 1, upper bound of δ is 1-α 2 . Thus when α > 1 4 , our approach is better than the idea of [START_REF] Hinek | On the Security of Some Variants of RSA[END_REF]. The upper bound of δ in Theorem 2 is 3-4α 5 . Hence, in this case, for α > 1 8 , bound of δ in Theorem 2 is better than that of [START_REF] Hinek | On the Security of Some Variants of RSA[END_REF]. It is clear that the existing results on cryptanalysis of CRT-RSA will directly work on Dual CRT-RSA. Thus the region of interest is where the existing state-of-the-art cryptanalytic results on CRT-RSA cannot be used for Dual CRT-RSA.

In [START_REF] Bleichenbacher | New attacks on RSA with small secret CRTexponents[END_REF] (improved results of [START_REF] May | Cryptanalysis of Unbalanced RSA with Small CRT-Exponent[END_REF]), it is proved that when δ < 2 5 (1α), one can factor CRT-RSA modulus efficiently. Thus as long as α < 1, our bound of δ in Theorem 1 is better than [START_REF] Bleichenbacher | New attacks on RSA with small secret CRTexponents[END_REF]. When α < 1 2 , our bound of δ in Theorem 2 is better than of [START_REF] Bleichenbacher | New attacks on RSA with small secret CRTexponents[END_REF]. For full bit size of e, i.e., for α = 1 both our ideas as well as that of [START_REF] Bleichenbacher | New attacks on RSA with small secret CRTexponents[END_REF] do not work successfully towards cryptanalysis of Dual CRT-RSA.

When δ < 1 2 -2 3 α, it is proved in [START_REF] Galbraith | Tunable balancing of RSA[END_REF] that one can factor the CRT-RSA modulus efficiently. Our bound of δ in Theorem 1 is always better than that of [START_REF] Galbraith | Tunable balancing of RSA[END_REF]. Also for α < 3 4 , our bound of δ in Theorem 2 is better than that of [START_REF] Galbraith | Tunable balancing of RSA[END_REF]. For α ≥ 3 4 , both our method of Theorem 2 and idea of [START_REF] Galbraith | Tunable balancing of RSA[END_REF] will not work. CRT-RSA is proved to be weak in [START_REF] Jochemsz | A polynomial time attack on RSA with private CRTexponents smaller than N 0.073[END_REF] in the cases when:

(i) δ < 5-4α+20τ -16ατ +18τ 2 -12ατ 2 14+56τ +66τ 2 +24τ 3 , (ii) δ < 5-4α+20τ -16ατ +27τ 2 -30ατ 2 +12τ 3 -24ατ 3 14+56τ +66τ 2 +24τ 3
, for some non-negative τ . The second bound works better than the first one for α < 1 2 . Towards larger values of α, the first one provides better cryptanalytic bound. One can check [5, Table 5.1, Page 87] that for α ∈ [0.31, 0.8], the optimal value of τ is zero and in that case both the bounds on δ are same, which is 5-4α 14 . For α ∈ [0.31, 2 3 ), our bound in Theorem 1 is better than that of [START_REF] Jochemsz | A polynomial time attack on RSA with private CRTexponents smaller than N 0.073[END_REF] as 1-α 2 > 5-4α 14 . Our ideas in both Theorem 1

Theory of [START_REF] Jochemsz | A polynomial time attack on RSA with private CRTexponents smaller than N 0.073[END_REF] Our upper bounds on δ α optimal τ upper bound of δ Theorem 1 Theorem and Theorem 2 are better than the approach of [START_REF] Jochemsz | A polynomial time attack on RSA with private CRTexponents smaller than N 0.073[END_REF] in this range as explained in Table 1. For α < 0.31, the optimal values of τ are not zero and hence we provide numerical results as in Table 1 for [START_REF] Jochemsz | A polynomial time attack on RSA with private CRTexponents smaller than N 0.073[END_REF]. In Figure 1, IA, JB, KC and LD represent the lines δ = 5 8α, δ = 3-4α 5 , δ = 1-α 2 , and δ = 5-4α 14 which are relevant to the upper bounds of δ in [4], Theorem 2, Theorem 1 and [START_REF] Jochemsz | A polynomial time attack on RSA with private CRTexponents smaller than N 0.073[END_REF] respectively. The area EF GHE shows the new region obtained from our result where Dual CRT-RSA is not secure. The line KM

We have implemented the idea of continued fraction (CF) of [START_REF] Hinek | On the Security of Some Variants of RSA[END_REF]. Its experimental results are almost same as its theoretical bounds. We have also implemented the approach of [START_REF] Jochemsz | A polynomial time attack on RSA with private CRTexponents smaller than N 0.073[END_REF] and in some cases its experimental results are better than the theoretical bound of itself. In all cases we take 1000-bit N 1 , N 2 . For the experiments, the Dual CRT-RSA keys are generated using Algorithm 1 [START_REF] Sun | Dual RSA and its applications[END_REF], and we note that g, g 1 , g 2 and K ′ are always very small. This justifies considering ǫ → 0 and ǫ ′ → 0. Let us consider the experiments corresponding to the idea of Theorem 2. When α ≤ 0.1, after lattice reduction, the coefficient of y in the first polynomial is equal to kp 2 kq 2 gcd(kp 1 kq 1 ,kp 2 kq 2 ) . Since gcd(k p1 k q1 , k p2 k q2 ) is small, one can easily obtain k p2 k q2 . In these cases corresponding to Theorem 2, we get better experimental results than the theoretical bound.

From Lemma 1, it is clear that for α = 0.315, the maximum possible bits of d p , d q is 369 (δ < 1 -2α = 0.370) for 1000-bit N . From table 2, one may note that in such a situation it is possible to factor N 1 , N 2 . Thus, although we have proved in Theorem 3 that DGRR is weak for α > 1 3 , in practice DGRR becomes insecure when α > 0.315.

DGRR Parameters

Upper bound δ when DGRR is not secure α 1 -2α (upper Result of [START_REF] Hinek | On the Security of Some Variants of RSA[END_REF] Result of [START_REF] Jochemsz | A polynomial time attack on RSA with private CRTexponents smaller than N 0.073[END_REF]

Fig. 1 .

 1 Fig. 1. New attack region is EF GHE.

Fig. 2 .

 2 Fig. 2. Attack regions: △CDE (theoretical), C ′ CDEC ′ (experimental).

Table 1 .

 1 Numerical comparison of our theoretical results with those of[START_REF] Jochemsz | A polynomial time attack on RSA with private CRTexponents smaller than N 0.073[END_REF].

	2

Table 2 .

 2 Theorem 1 (our) Theorem 2 (our) bound of δ) Theory/Expt. Theory Expt. Theory Expt. Theory Expt. Comparison our theoretical and experimental results with the existing works. Lattice Dimension in experiment of[START_REF] Jochemsz | A polynomial time attack on RSA with private CRTexponents smaller than N 0.073[END_REF] is 36. In our case, it is 5 for Theorem 1 and 3 for Theorem 2. For the * marked entries, we could not generate larger dp, dq as we do not have any other method other than DGRR to generate the Dual CRT-RSA keys.

	0.100	0.800	0.525	0.324 0.430 0.450	0.489	0.520	0.525
	0.150	0.700	0.475	0.314 0.400 0.425	0.477	0.480	0.478
	0.200	0.600	0.425	0.300 0.370 0.400	0.445	0.440	0.436
	0.250	0.500	0.375	0.286 0.333 0.375	0.410	0.400	0.398
	0.300	0.400	0.325	0.271 0.300 0.350	0.376	0.360	0.358
	0.315	0.370	0.310	0.267 0.285 0.342	0.369	0.348	0.347
	0.350	0.300	0.275	0.257 0.260 0.325	0.299 *	0.320	0.299 *

represents α + δ = 1 2 . All the CRT-RSA keys (as well Dual CRT-RSA keys) must stay above this line as ed p , ed q are greater than N 1 2 . In summary, the earlier results have pointed out that the region DEIKM D is insecure. In this paper, we add the region EF GHE to it. Adding our result, Dual CRT-RSA is insecure in the region DF GHIKM D.

3 Attack on DGRR [START_REF] Sun | Dual RSA and its applications[END_REF]Section III C] Let n B be the number of bits in the binary representation of an integer B. Also, in short, we write n N = n. The key generation algorithm of Dual Generalized Rebalanced RSA [START_REF] Sun | Dual RSA and its applications[END_REF] is as follows. The key generation algorithm of Dual CRT-

Output: The public key (e, N1, N2) and the private key (dp, dq, p1, q1, p2, q2

Otherwise, go back to step 3; Randomly select (k -1) n k -bit integers qa 1 , . . . , qa (k-1) and an even integer qa k such that 6 qa = qa 1 . . . qa (k-1) qa k has bit length (n/2 -ne) and gcd(e, qa) = 1;

Randomly select an n k -bit integer kq 1 such that gcd(e, kq 1 ) = 1; 7

Compute dq and q b such that edq = (kq 1 qa)q b + 1, where e < q b < 2e and

Otherwise, go back to step 7; Calculate N1 = p1q1 and N2 = p2q2; 10 Algorithm 1: Key Generation Algorithm for DGRR [START_REF] Sun | Dual RSA and its applications[END_REF].

RSA is not known for any range of values of e, d p .d q . Further, for any such choice of keys, it may not be possible to obtain N 1 , N 2 . The above algorithm for Dual CRT-RSA key generation provides keys in a certain range.

From the key generation algorithm 1, we have the following simple result.

Lemma 1. Let e = N α and d p , d q ≈ N δ be the public and private exponents generated by the Algorithm 1. Then, δ < 1 -2α. IV], the safe parameters for DGRR is as follows:

-

where l is the exhaustive search parameter;

n e + n d > 5n 8 + l 2 -1; this implies α + δ > 5 8 , neglecting l; -5n d + 2n e > 2n + l; this implies 5δ + 2α > 2, neglecting l.

Thus the parameters proposed in [START_REF] Sun | Dual RSA and its applications[END_REF] for which DGRR is secure is

The constraint α < 3 8 follows from n e < n 2n k and n k > n 8 . We neglect the exhaustive search parameter l and the small constants.

Next we show that DGRR is weak for α > 1 3 when one uses Algorithm 1 and thus DGRR is weak even when the safe parameters are chosen as in [START_REF] Lenstra | Factoring Polynomials with Rational Coefficients[END_REF].

Theorem 3. Given the safe parameters in [START_REF] Lenstra | Factoring Polynomials with Rational Coefficients[END_REF], the key generation Algorithm 1 for DGRR is insecure when -(using Theorem 1) (i) 1 3 < α < 3 8 , (ii) 1 4 < α ≤ 1 3 and δ < 1-α 2 ; -(using Theorem 2) (i) 1 3 < α < 3 8 , (ii) 1 8 < α ≤ 1 3 and δ < 3-4α 5 . Proof. From Lemma 1, we know that the key generation Algorithm 1 provides DGRR keys under the constraint δ < 1 -2α.

Using Theorem 1, one can factor N 1 , N 2 efficiently if δ < 1-α 2 . Hence, when 1 -2α < 1-α 2 , i.e., when α > 1 3 , one can break DGRR generated by the Algorithm 1. Hence given the safe parameters in [START_REF] Lenstra | Factoring Polynomials with Rational Coefficients[END_REF], the key generation Algorithm 1 for DGRR is insecure when 1 3 < α < 3 8 . Also [START_REF] Lenstra | Factoring Polynomials with Rational Coefficients[END_REF] requires δ > 5 8α and from Theorem 1, we need δ < 1-α 2 , which gives α > 1 4 . Using Theorem 2, one can factor N 1 , N 2 efficiently if δ < 3-4α 5 . Hence, when 1 -2α < 3-4α 5 , i.e., α > 1 3 , one can break DGRR generated by the Algorithm 1. This gives proof of item (i). Further [START_REF] Lenstra | Factoring Polynomials with Rational Coefficients[END_REF] requires δ > 5 8α and from Theorem 2, we need δ < 3-4α 5 . So, we need 5 8α < 3-4α 5 , which gives α > 1 8 .

⊓ ⊔

For DGRR, keys can be generated within △IAB in Figure 2. The shaded area represents the new region for which DGRR is weak. In Figure 2 respectively. Theoretically, △CDE represents our new attack region. Moreover, the experimental results show that even some regions outside △CDE can be vulnerable in practice and C ′ CDEC ′ is the extended region where DGRR is vulnerable. This is explained in more details in the following section. According to the analysis of [START_REF] Sun | Dual RSA and its applications[END_REF], the region, where DGRR was known to be weak, has been HDAIH.

Experimental Results

Let us now present the experimental results. We have implemented the programs in SAGE 3.1.1 over Linux Ubuntu 8.04 on a Compaq laptop with Dual CORE Intel(R) Pentium(R) D CPU 1.83 GHz, 2 GB RAM and 2 MB Cache. Since our polynomial f 4 in Theorem 1 is a linear polynomial on 5 variables, the lattice dimension in our approach is only 5. Also, the polynomial f in Theorem 2 is a linear polynomial on 3 variables and hence the lattice dimension in this approach is 3.