UnEncrypted

Uniform convergence for parabolic reaction-diffusion problems

respectively.

Theorem 2 Let U n be the numerical solution of (12) and un be the solution of (6), both

√

at time level tn. Let assume that σ0 ≥ 2/ β. Then, the error associated to the spatial discretization, on the Shishkin mesh satisfies

on the Vulanovic mesh.

Now, using a recursive argument, taking into account that (I + (τ /2)LNx,ε)−1 ∞ ≤ C and assuming that the maximum norm of all the powers of the transition parameter RN,τ is uniformly bounded, we can deduce that

for both the Shishkin and the Vulanovic meshes.

Finally, from the triangular inequality and (21), (22) the result trivially follows.

From Theorems 1 and 2, and using that Uin − u(xi, tn) ∞,ΩN ≤ Uin − un(xi) ∞,ΩN +un(xi) − u(xi, tn) ∞,ΩN , we can easily obtain the main result of this work, giving the

uniform convergence of the fully discrete scheme.

4Numerical experiments

We consider the test problem

ut − εuxx + (2 + x − cos(x))u = 4(e−t − 1) + 6txex, (x, t) (0, 1) × (0, 1], (25)

with homogeneous initial and boundary conditions, for which the exact solution is unknown. Figure 1 shows the numerical solution for ε = 10−4; from it we see the boundary layers at both sides x = 0, 1.

Note that in this problem the reaction term is non constant, but the numerical results show the same order of uniform convergence proved for the constant case.

To approximate the numerical errors we use a variant of the double mesh principle

where Uj,nε,N,M is the numerical solution given by the fully discrete method with a constant time step τ = 1/M and (N + 1) points in the spatial mesh, and Uj,nε,2N,2M is the numerical

Uniform convergence for parabolic reaction-diffusion problems

1

time

space

Figure 1: Solution for ε = 10−4 with N = M = 32

solution computed by using the time step τ /2 and (2N + 1) points in the spatial mesh, but with the same transition parameter than in the original mesh.

For each fixed value of ε, the maximum global errors are estimated by

Dε,N,M = max Dj,nε,N,M j,n

and therefore, in standard way, the numerical orders of convergence are given by

q = log (Dε,N,M /Dε,2N,2M )/log 2.

From these values we obtain the ε-uniform errors and the ε-uniform orders of convergence by

DN,M = max Dε,N,M , quni = log (DN,M /D2N,2M )/log 2.

ε

Table 1 displays the maximum and uniform errors and the numerical orders of convergence of scheme (12) defined on the Shishkin mesh (14), for the set of the values ε {2−4, . . . , 2−30}. From these results we clearly deduce almost second order convergence in agreement with Theorem 3. For this and other test problems, similar results, about the maximum errors and the orders of convergence, have been obtained when the Vulanovi´c mesh is used instead of the Shishkin mesh.

Table 2 displays the maximum matrix norm of the transition operator RN,τ for ε = 10−4, 10−6, 10−8 and some values of N and M . From it we can conclude that its maximum norm is less than 1. Nevertheless, taking a di erent range of values for the discretization

C. Clavero, J.L. Gracia, F. Lisbona

Table 1: Maximum errors and uniform orders of convergence

parameters (see Table 3), we observe that sometimes the maximum norm is greater than 1. Nevertheless, to obtain the bounds (23) and (24) for the error we only need that the norm of RN,τp be bounded. Table 4 displays the value obtained for some values of ε in the most unfavorable case when N is large and M is small; from it we see that in all cases the maximum norm of the discrete transition operator is bounded and it decreases as p increases. So, we can conclude that from numerical point of view the condition of Remark 1 for the powers of RN,τ holds.

Table 2: Maximum norm of the transition operator RN,τ

Acknowledgements

This research was partially supported by the project MEC/FEDER MTM 2010-16917 and by the Diputaci´on General de Arag´on

Uniform convergence for parabolic reaction-diffusion problems

Table 3: Maximum norm of the transition operator RN,τ for ε = 10−6

References

[1]B. Bujanda, C. Clavero, J.L. Gracia and J.C. Jorge, A high order uniformly convergent alternating direction scheme for time dependent reaction-di usion singularly perturbed problems, Num. Math. 107 (2007) 1–25.

[2]C. Clavero and J.L. Gracia, High order methods for elliptic and time dependent reaction-di usion singularly perturbed problems, Appl. Math. Comp. 168 (2005) 1109– 1127.

[3]C. Clavero and J.L. Gracia, On the uniform convergence of a finite di erence scheme for time dependent singularly perturbed reaction–di usion problems, Appl. Math. Comp. 216 (2010) 1478–1488.

[4]C. Clavero, J.L. Gracia and F.J. Lisbona, Second order uniform approximations for the solution of time dependent singularly perturbed reaction–di usion systems, Int. J. Numer. Anal. Mod. 7 (2010) 428–443.

[5]P.A. Farrell, A.F. Hegarty, J.J.H. Miller, E. O’Riordan, E. and G.I. Shishkin, Robust computational techniques for boundary layers, Chapman & Hall (2000).

C.Clavero, J.L. Gracia, F. Lisbona

[6]P.W. Hemker, G.I. Shishkin and L.P. Shiskina, ε-uniform schemes with highorder time accuracy for parabolic singular perurbation problems, IMA J. Numer. Anal.

20 (2000) 99–121.

[7]O.A. Ladyzhenskaya, V.A. Solonnikov and N.N. Ural’tseva, Linear and quasilinear equations of parabolic type, Transactions of Mathematical Monographs, 23, American Mathematical Society, 1968.

[8]H.-G. Roos, M. Stynes and L. Tobiska, Robust numerical methods for singularly perturbed di erential equations, Springer Series in Computational Mathematics 24, Springer-Verlag, Berlin, 2008.

[9]R. Vulanovic´, A high order scheme for quasilinear boundary value problems with two small parameters, Computing 67 (2001) 287–303.

[10]R. Vulanovic´, An almost sixth-order finite-di erence method for semilinear singular perurbation problems, Comp. Meth. Appl. Math. 4 (2004) 368–383.

Proceedings of the 12th International Conference on Computational and Mathematical Methods

in Science and Engineering, CMMSE 2012 July, 2-5, 2012.

A key agreement protocol for distributed secure multicast on a non-commutative ring

Joan-Josep Climent1, Juan Antonio L´opez-Ramos2, Pedro R. Navarro3

and Leandro Tortosa3

3 Departament de Ci`encia de la Computaci´ i Intel·lig`encia Artificial, Universitat d’Alacant

emails: jcliment@ua.es, jlopez@ual.es, prnr63@gmail.com, tortosa@ua.es

Abstract

We introduce a key agreement protocol for secure communications. The protocol shows to be e cient for large audiences, making it applicable for the nowadays widely extended secure multicast communications and allows users to join or leave the communication group preserving forward and backward secrecy in an e cient way.

Key words: Secure Communications, Key exchange

MSC 2000: 68P25 94A60

1Introduction

Key exchange protocols are a typical problem in Cryptography. Since Di e and Hellman in [5] introduced their elegant solution based on the Discrete Logarithm Problem (DLP), many authors have dealt with this main issue in Cryptography (cf. [6, 8] and their references). Nowadays the increasing interest in group-oriented applications and protocols have lead the researchers to find e cient protocols for group communications and specially secure protocols that provide privacy and integrity.

Multicast is an e cient way to send contents from a source to multiple receivers [4]. The e ciency of IP-multicast is due mainly to the fact that the information is transmitted only

A key agreement protocol on a non-commutative ring

once and this reaches all those receivers that have shown their interest in receiving the information from a determined IP-address, going through each connection between two of these nodes corresponding to the receivers [3]. Although this scheme for distributing information is able to extend its operations capability as the group of users grows without decreasing its quality and/or e ciency, does not provide security for accessing the distributed information only to the group of authorized users. Multicast schemes that take into account this property are known as secure multicast schemes [12]. Concerning the authority that is in charge of rekeying, multicast protocols are divided into three categories [7]: centralized, those with a central authority that changes and multicast the session key; decentralized, where there exists a group of “detached users” that act as local authorities for key distribution and distributed key management protocols, where the member themselves carry out the key generation and our aim in this paper is to focus in the latter case.

Dynamic Peer Group are common in many applications such as data bases, video conferencing, etc and distributed protocols for multicasting are quite appropriate in this setting where group could be continuously changing. Steiner et al. [10] introduce a protocol for group key agreement based on the two-party Di e-Hellman key exchange. This shows to behave much more e ciently than other protocols previously introduced and it is used later in a key agreement protocol, CLIQUES, in Dynamic Peer Groups [11].

However increasing of computing capabilities of actual computers and works as [1] and [9] have provoked that protocols and cryptosystems based on the Discrete Logarithm Problem (DLP) are no longer recommended.

Our aim in this paper is to introduce a solution for distributed key agreement over a non-commutative ring inspired by the two-party key exchange protocol given in [2], based on one of the currently considered problems for cryptography on non-commutative groups, more precisely, on the so-called Decomposition Problem (DP), i.e., given a pair of elements x and y in a noncommutative group G and S G, the problem is to find z1 and z2 in S such that y = z1xz2.

2A Distributed Secure Multicast Scheme

The target scenario is the following: private communications must be established within a restricted group. There is not a central server that manages the key management issues. Components of this restricted group will manage all rekeying operations by themselves. From now on, we will refer to the clients as members or users. We are assuming a typical pattern of many-to-many communications as noted above although we can also consider a setting where one-to-many communications take place. However, as usually in this type of protocols, the number of users cannot be as larger as in a typical one-to-many communication as an IP-TV service due to the nature of distributed secure multicast protocols.

J.-J. Climent, J.A. Lopez´ -Ramos, P.R. Navarro, L. Tortosa

So let us assume that the set of users is given by {U1, U2, . . . , Uh}. Users agree to use a noncommutative ring R and two elements r R and s R \ Z(R), where Z(R) denotes the center of the ring R. Therefore r and s are public. Furthermore, if we consider f (x), g(x) Z(R)[x] and u and v are positve integers, although R is not commutative, we have that

This property allows us to establish the following protocol.

Protocol 1: Every user Ui, for i = 1, 2, . . . , h chooses a polynomial fi(x) Z(R)[x] and a pair of positive integers mi and ni. Then the private key for the user Ui is (fi(x), mi, ni). Assume also that K0 = s.

(a) User U1 computes the element K1 of R given by

User U2 sends to user U3 the vector of elements in R given by (K1, K2).

(c) In general, for i = 3, 4, . . . , h − 2, h − 1, user Ui computes the element

Then, user Ui sends to user Ui+1 the vector (K1, K2, . . . , Ki−1, Ki) of elements in R.

(d)When user Uh receives the vector (K1, K2, . . . , Kh−2, Kh−1), he/she computes the elements of R given by

A key agreement protocol on a non-commutative ring

(f) In general, for i = 2, 3, . . . , h − 2, h − 1, when user Uh−i receives from user Uh−i+1 the

Proof: Assume that i = 0, 1, 2, . . . , h − 2, h − 1. From expressions (7), (6), (5), and (1) we have that

Now, from expressions (2), (3), (4), and (1) we have that

Kh−i−1 = fh−i−1(r)mh−i−1 Kh−i−2fh−i−1(r)nh−i−1

=fh−i−1(r)mh−i−1 (fh−i−2(r)mh−i−2 Kh−i−3fh−i−2(r)nh−i−2 ) fh−i−1(r)nh−i−1

=· · ·