Alexandre Gondran
email: alexandre.gondran@enac.fr

Michel Gondran
email: michel.gondran@polytechnique.org

Heads or tails in zero gravity: an example of a classical contextual "measurement"

Playing the game of heads or tails in zero gravity demonstrates that there exists a contextual "measurement" in classical mechanics. When the coin is flipped, its orientation is a continuous variable. However, the "measurement" that occurs when the coin is caught by clapping two hands together gives a discrete value (heads or tails) that depends on the context (orientation of the hands). It is then shown that there is a strong analogy with the spin measurement of the Stern-Gerlach experiment, and in particular with Stern and Gerlach's sequential measurements. Finally, we clarify the analogy by recalling how the de Broglie-Bohm interpretation simply explains the spin "measurement".

Introduction

Understanding measurement in quantum mechanics has always been a major problem. This is especially the case of the "measurement" of the spin in the Stern-Gerlach experiment, which is considered the archetype of a so-called contextual measurement. In Modern Quantum Mechanics [START_REF] Sakurai | Modern Quantum Mechanics[END_REF], Jun John Sakurai calls attention to this point in his opening remarks: "This experiment illustrates in a dramatic manner the necessity for a radical departure from the concepts of classical mechanics. [...] A solid understanding of problems involving two-state systems will turn out be rewarding to any serious student of quantum mechanics." Many physicists (primarily those related to the Copenhagen school) have interpreted this experiment as if "the measurement creates reality" or more explicitly, as Albert Einstein famously put it, as if "the moon doesn't exist when no one looks at it". The purpose of this article is to show that contextual measurements also exist in classical mechanics and that they are not mysterious. Section 2 defines the specific case of heads or tails in zero gravity, which presents a certain analogy with the measurement of spin in the Stern-Gerlach experiment. This "measurement" corresponds in fact to the orientation of a continuous variable to a discrete two-state value. This analogy continues with Stern and Gerlach's sequential measurements in section 3. Finally, section 4 clarifies the analogy by recalling how the de Broglie-Bohm interpretation [START_REF] De Broglie | La mécanique ondulatoire et la structure atomique de la matière et du rayonnement[END_REF][START_REF] Bohm | A Suggested interpretation of the quantum theory in terms of hidden variables[END_REF] simply explains the spin "measurement" and we conclude in section 5.

Heads or tails in zero gravity

Have you ever tossed a coin in space? You'll run into a small problem once the coin has been tossed into the air: it won't drop into your palm but will remain twirling in the air. The absence of gravity adds a complication to coin tossing. New rules are required when playing heads or tails in space: the tosser has to clap his hands together so that the coin is caught between his right and left palms. Then he will ask his opponent to choose heads or tails. The coin tosser then withdraws his hands. The coin still does not fall, it remains motionless in weightlessness. The side of the coin that was on the tosser-clapper's right palm designates the winner. It is understood in this experiment that the heads/tails orientation of the coin is not determined before the measurement (the clapping together of hands). The orientation of the coin is a variable with non-predetermined values (before measurement), unlike the mass, color, value or size of the coin which are variables with predetermined values. This is what is described as a contextual measurement, i.e. the measurement of a variable with a continuous value (orientation of the coin) that only gives discrete values (heads or tails) depending on the context (the orientation of the hands).

Analogy with Stern-Gerlach spin measurement In quantum mechanics, the orientation of the spin of a particle is also a variable whose values are non-predetermined before measurement. When measuring the spin; let us consider the example of a 1/2 spin particle passing through a Stern-Gerlach type measuring device, that is to say a very powerful magnetic field (cf. figure 1), there can only be two possible results: either spin up (i.e. a deviation of the particle upwards with respect to the Stern-Gerlach device) or spin down (i.e. a deviation of the particle downwards). This is the analog of the measurement of heads or tails by clapping hands in space. In both cases, it is possible to say that the orientation of the coin (or the spin) before the measurement is in a superposition of the state of heads and the state of tails (respectively state of up and state of down); mathematically a superposition of states is simply a state that is linear combination of several states. These are variables with continuous values (all superpositions are possible) but whose measurement produces only discrete values.

Figure 1: Schematic configuration of the historic Stern-Gerlach experiment: a beam of silver atoms [START_REF] Gerlach | Der experimentelle Nachweis der Richtungsquantelung im Magnetfeld[END_REF], from the source (oven E , collimator hole T) passes through an inhomogeneous magnetic field (magnet A 1 ), then separates into two distinct beams before condensing on the screen P 1 on two distinct spots of identical intensity N + et N -.

Sequential measurements of heads or tails

It is interesting to do measurements in space because it is possible to extend the spin up/down analogy of a particle with the heads/tails orientation of a coin. Indeed, to measure spin, it is possible to orient the measuring instrument (the air gap of the Stern-Gerlach device) in any direction in space; the direction z classically denotes the vertical direction and x and y the other two horizontal directions.

In the coin toss game on Earth, the heads or tails orientation is only measured on the vertical axis because of gravity. In zero gravity, there is no longer any specific direction and it is possible to orient the measuring device (i.e. the clapping hands) in all possible directions, and therefore also the measurement of the spin. This could be described as a game of heads or tails in three dimensions. The experiment is schematically represented in Figure 2, where it is shown that there is a 50/100 chance of obtaining the heads orientation and a 50/100 chance of obtaining the tails orientation, regardless of the orientation of the measuring device. There is therefore a 50/50 superposition of the states of heads and tails.

If, after measuring the coin in the heads state on the ẑ axis, a second measurement is made in the same direction, as shown in Figure 3 , and the hands are again clapped on the ẑ axis, it is obvious that the measurement of the orientation once again results in heads. A second measurement is now made, but on the ŷ axis. The first measurement was a vertical clapping of the hands: the coin was forced to orient itself vertically in relation to heads and tails (it is assumed that heads was found, for example); after this measurement, it no longer spins but remains oriented vertically. Now a second measurement is made by clapping hands horizontally this time (see Figure 4). The coin is once again forced to orient itself but horizontally this time. Since it is on its side, due to the horizontal orientation, it has a 50 % chance of being measured heads and a 50% chance of being measured tails. One final experiment is conducted to understand the behavior of a variable with non-predetermined values. As shown in Figure 5, after the first two measurements in relation to ẑ and ŷ, a third measurement is carried out, again in relation to ẑ. After the second measurement, the coin floats horizontally in the air and the third hand clap straightens it again. The first measurement in this same direction resulted in heads, but now there is a 50 % chance that its will be heads again and 50 % it will be tails. The latter experiment shows that a variable with non-predetermined values of a given object can be measured in the same direction and not result in the same value. The four experiments (Figures 2, 3, 4 and5) are characteristic of variables with non-predetermined values before measurement. The spin of a particle (or the polarization of a photon) follows these same patterns.

Difference between zero gravity heads and tails and quantum heads and tails (Stern and Gerlach) The main difference relates to experiments 3 and 4 (Figures 4 et 5) where at least one second measurement is carried out in an orientation perpendicular to the first one. For these experiments, the result of the second measurement (Figure 4) gives a 50% chance of obtaining heads and a 50% chance of obtaining tails, because the second measurement is perpendicular to the first. If it were not perpendicular, that is to say oriented by 90 • in relation to the first hand clap, but merely oriented by 45 • , for example, then the second measurement would in all cases yield the same result as the first. In fact, the hand clap cannot flip over the coin but simply straighten it in the axis of the hands. This results in a 50/50 chance of heads or tails because the orientation of the two measuring devices is 90 • and therefore the coin is on its side during the second measurement. In quantum heads or tails, each orientation between the two measuring devices corresponds to a different up/down frequency of occurrence. All up/down frequencies of occurrence are possible. The frequency 50/50 is found when the orientation between the two measurement devices is perpendicular.

Although the question of the non-contextuality of the measurement of the game of heads or tails in space does not pose any problem of interpretation, the question of the non-contextuality of the spin measurement is the source of the divergences that exist among the main interpretations of quantum mechanics.

• The Copenhagen interpretation (orthodox interpretation) refutes the existence of the spin orientation before its measurement by an observer; it is the measurement that creates the spin orientation; before measurement, the spin orientation is indeterminate. This assumption is extended to other properties such as a particle's position or velocity, which are assumed to be non-existent until they are measured.

• Everett's multiple worlds interpretation explains non-contextuality by splitting the world in two; each new world has a different context that gives a different result.

• In the de Broglie-Bohm interpretation, the non-contextuality of the spin measurement is explained in the same way as the non-contextuality of the measurement in the game of heads or tails in space: the measuring device guides the spin (resp. the coin orientation) to a discrete value, but the spin orientation (resp. the coin orientation) exists throughout the experiment.

Let us recall that these three approaches share the same equations (those of quantum mechanics) and therefore have the same physical predictions. All that distinguishes them is the interpretation of the equations.

In the following section, we present the dBB interpretation, extends the analogy of the interpretation of the measurement of heads or tails in zero gravity to "the quantum world".

Spin "measurement" in Broglie-Bohm interpretation

Finally, we recall how the de Broglie-Bohm interpretation provides a simple explanation for the spin "measurement" according to the different axes. The measurement of the spin of a silver atom is carried out by a Stern-Gerlach apparatus: an electromagnet A 1 , where there is a strongly inhomogeneous magnetic field B, followed by a screen P 1 (Fig. 1). The magnetic field B is directed along the Oz axis and the atomic beam is directed along the Oy axis.

Point source or spatial extension: spinor

The state of a spin 1/2 particle is given by the wave function Ψ(x, t), called a Pauli spinor, which has two complex components Ψ + (x, t) and Ψ -(x, t). At the moment of entering the magnetic field (t = 0), we Figure 6: Orientation of the spin of a pure state. θ 0 and ϕ 0 are the polar angles characterizing the spinor. They correspond to the angles of the Bloch sphere. can associate to each silver atom a spinor corresponding to a pure state, as in many textbooks of quantum mechanics [START_REF] Feynman | Quantum Mechanics and Paths Integrals[END_REF][START_REF] Cohen-Tannoudji | Quantum mechanics, Quantum Mechanics[END_REF][START_REF] Sakurai | Modern Quantum Mechanics[END_REF] :

Ψ 0 = Ψ(t = 0) = cos θ 0 2 e i ϕ 0 2 sin θ 0 2 e -i ϕ 0 2 (1)
where θ 0 and ϕ 0 are the polar angles characterizing the pure state (cf. figure 6). The angles θ 0 and ϕ 0 are unknown and each atom of the beam has angles (θ 0 , ϕ 0 ) which a priori are different; we only suppose that θ 0 is uniformly distributed on [0; π] and ϕ 0 on [0; 2π[. The beam passing through the magnetic field is a statistical mixture of pure states, that is, a random mixture of atoms in different spinors.

To analyze the evolution of the spinor during the experiment and to understand how the spin is measured, it is absolutely necessary to represent an individual particle with spin by a spinor with a spatial extension as follows:

Ψ 0 (x, z) = (2πσ 2 0 ) -1 2 e -x 2 +z 2 4σ 2 0 cos θ 0 2 e i ϕ 0 2 sin θ 0 2 e -i ϕ 0 2 (2)
We consider the beam of silver atoms as a Gaussian beam along the Oz and Ox axes of standard deviation σ 0 = 10 -4 m. The atomic propagation axis Oy is treated classically, knowing that the velocity of the atoms in this direction is approximately v y = 500m/s.

Pauli equation

The evolution of the spinor Ψ(x, t) = Ψ + (x,t) Ψ -(x,t) , for a neutral spin-1/2 particle (silver atom) is given by the Pauli equation:

i ∂Ψ ∂t (x, t) = - 2 2m ∇ 2 + µ B Bσ Ψ(x, t) (3)
where m = 1.8 × 10 -25 kg is the the mass of the silver atom, B is the magnetic field, µ B = e 2me is the Bohr magneton and σ = (σ x , σ y , σ z ) corresponds to the three Pauli matrices.

Without the initial spatial extension of the spinor (equation 1), the spatial resolution of the Pauli equation is impossible and we lose the possibility of taking into account the evolution of the spin during the measurement process as shown by Takabayasi, [START_REF] Takabayasi | The Vector Representation of Spinning Particle in Quantum Theory[END_REF] Bohm et al. [START_REF] Bohm | A causal interpretation of the pauli equation (A)[END_REF] and Dedwey et al. [START_REF] Dewdney | What happens in a spin measurement?[END_REF] Indeed, the differing evolutions of the two components of the spinor play a key role in understanding the measurement process.

Solution without Pauli's equation and with measurement postulates

Using measurement postulates, it is very easy to infer the result of the measurement without using the Pauli equation. We rewrite the initial spinor (equation 1) with no spatial extension Ψ 0 (the reasoning is similar whether or not spatial extension is considered) in the form:

Ψ 0 = cos θ 0 2 e i ϕ 0 2 |+ + sin θ 0 2 e -i ϕ 0 2 |-, (4)
where |+ = 1 0 and |-= 0 1 are the eigenvectors of the operator σ z . From the measurement postulates, | cos θ 0 2 e i ϕ 0 2 | 2 = cos 2 θ 0 2 is the probability of measuring the spin + /2 (the eigenvalue of the projection operator S z = 2 σ z ) and sin 2 θ 0 2 of measuring the spin -/2. The θ 0 is unknown at the output of the source and the probability of measuring the spin 1/2 when we do not know the initial spinor of the incident atom is equal to: π 0 cos 2 θ 0 2 dθ 0 = 0.5. The probability of measuring the spin -1/2 is equal to: π 0 sin 2 θ 0 2 dθ 0 = 0.5. We thus find the two distinct spots of identical intensity N + and N -. It is easy to understand the practical relevance of the postulates of the measurement: they allow the experimental results to be retrieved simply and quickly. However, they do not provide an accurate understanding of the measurement phenomenon.

The de Broglie-Bohm theory

In the de Broglie-Bohm (dBB) theory, the wave function does not completely represent the state of a quantum particle and it is necessary to add to its description the position of the particle X(t). The evolution of the spinor is always given by the Pauli equation ( 3) and the evolution of the position is given by the following equation [START_REF] Bohm | A causal interpretation of the pauli equation (A)[END_REF][START_REF] Takabayasi | The Vector Representation of Spinning Particle in Quantum Theory[END_REF]:

dX(t) dt = 2mρ Im(Ψ † ∇Ψ)| x=X(t) (5)
where

Ψ † = (Ψ + * , Ψ - * ) and ρ = Ψ † Ψ.
The atom is both a wave and a particle. Wave and particle coexist, the first guiding the second by the equation ( 5), hence the name of "pilot wave" given by de Broglie in 1927 [START_REF] De Broglie | La mécanique ondulatoire et la structure atomique de la matière et du rayonnement[END_REF]. Bohm et al. [START_REF] Bohm | A causal interpretation of the pauli equation (A)[END_REF] also define s a spin vector field as:

s(x, t) = 2ρ Ψ † (x, t)σΨ(x, t) = 2 (sinθ sinϕ, sinθ cosϕ, cosθ). (6)
The spin vector of an individual particle is evaluated along its trajectory as s = s(X(t), t). This spin vector is totally defined by the spinor and the position of the particle.

Pure state

We solve the Pauli equation for a single atom corresponding to a pure state with (θ 0 , ϕ 0 ). In the free space, at the end of the field, at the time t + ∆t (t ≥ 0 and ∆t = ∆l/v y being the crossing time of the field), one obtains [START_REF] Gondran | A complete analysis of the Stern-Gerlach experiment using Pauli spinors[END_REF] :

Ψ(x, z, t + ∆t) (2πσ 2 0 ) -1 2 e -x 2 2σ 2 0    cos θ 0 2 e - (z-z ∆ -ut) 2 2σ 2 z e i muz+ ϕ + i sin θ 0 2 e - (z+z ∆ +ut) 2 2σ 2 z e i -muz+ ϕ -    (7)
where

z ∆ = µ B B 0 (∆t) 2 2m = 10 -5 m, u = µ B B 0 (∆t) m = 1m/s, B =   B 0 x 0 B 0 -B 0 z   , (8)
and where ϕ -et ϕ + are constants. Figures 7 and8 represent the evolution of ρ(z, t) = Ψ † (x, z, t)Ψ(x, z, t)dx, the probability density of the presence of the silver atom in a pure state for the values θ 0 = π/3 and φ 0 = 0. The axis Oy, along which the beam is propagated, is on the abscissa (y = v y t) and the axis Oz is on the ordinate (the variable x is not represented because the wave remains Gaussian according to this axis). The magnet A 1 is represented in the figure by the two white rectangles, its length is ∆l = 1cm and there is D = 20cm of free path before the atom is measured on the detection screen P 1 . The numerical data comes from the textbook by Cohen-Tannoudji et al. [START_REF] Cohen-Tannoudji | Quantum mechanics, Quantum Mechanics[END_REF]. For the electromagnetic field B, we have: B 0 = 5 Tesla, B 0 = ∂B ∂z = -∂B ∂x = 10 3 Tesla/m. The dBB theory provides a more detailed explanation than the usual quantum mechanics explanation because, as seen in figure 8, it shows how the initial position of the particle explains in a causal way the final position usually justified by the reduction of the wave packet (figure 7). In this framework, there is no measurement problem because the continuation of quantum mechanics towards classical mechanics is done in a natural way by the position of the particle.

Figure 9 represents the evolution of the density ρ(z, t) for the pure state θ 0 = π/2 as well as six trajectories of atoms whose initial position z 0 was drawn at random.

The Pauli equation only provides the probability ρ of the impact of the atom. Experimentally, one does not directly measure the spin of an atom, but ( x, z) the position of the impact of the atom on P 1 .

If z ∈ N + , the term ψ -of ( 7) is numerically zero and the spinor Ψ is proportional to 1 0 , one of the eigenvectors of σ z . If z ∈ N -, the term ψ + of ( 7) is numerically zero and the spinor Ψ is proportional to 0 1 , the other eingenvector of σ z . Therefore, the spin measure corresponds to an eigenvalue of the spin operator S z = 2 σ z . It is a demonstration of the postulate of quantification by the dBB theory. Equation [START_REF] Takabayasi | The Vector Representation of Spinning Particle in Quantum Theory[END_REF] gives the probabilities cos 2 θ 0 2 (resp. sin 2 θ 0 2 ) to measure the particle in the spin state + 2 (resp. -2 ). It is a demonstration of the postulate of spatial decomposition by the dBB theory. The "measured" value is not a pre-existing value. It is contextual and conforms to the Kochen and Specker theorem [START_REF] Kochen | The Problem of Hidden Variables in Quantum Mechanics[END_REF].

Statistical mixture of pure states

Since the beam of silver atoms is a mixture of pure states, the atomic density ρ(z, t + ∆t) is determined by integrating ρ(x, z, t + ∆t) on x and on (θ 0 , ϕ 0 ); we find: Figure 10 represents this density ρ(z, t) as well as six trajectories of atoms whose initial position z 0 and the orientation of the initial spinor θ 0 are drawn at random. We note the difference with the results of figure 9 for the pure state θ 0 = π/2 which gives statistically the same results. For a statistical mixture of pure states, the trajectories of the atoms of a beam can cross.

ρ(z, t + ∆t) = (2πσ 2 0 ) -1 2 1 2 e - (z-z ∆ -ut) 2 2σ 2 0 + e - (z+z ∆ +ut) 2 2σ 2 0 . (9)

Conclusion

By introducing the game of heads or tails in weightlessness, we have shown that there is a contextual measure in classical mechanics and that there are no mysteries. The "measured" value is not a pre-existing value. It is discretized by the measuring device (the clapping of hands). We find the same property for the "measurement" of the spin in de Broglie-Bohm's interpretation of the Stern and Gerlach experiment.

The "measurement" of the spin along the Oz axis corresponds to the rectification of the orientation of the spin either in the direction of the gradient of the magnetic field or in the opposite direction. The result depends on the position of the particle in the wave function. The duration of the measurement is the time required for the particle to straighten its spin in the final direction. The "measured" value (the spin) is not a pre-existing value such as the mass and the charge of the particle but a contextual value conforming to the Kochen and Specker theorem.

We have also shown [START_REF] Gondran | Replacing the Singlet Spinor of the EPR-B Experiment in the Configuration Space with Two Single-Particle Spinors in Physical Space[END_REF] that, for the two entangled particles of the EPR-B experiment, it is possible to replace the singlet spinor in configuration space by two single-particle spinors in physical space. The "measurement" of the two spins is contextual and verifies Bell's inequalities. The wave function of the singlet state alone introduces a non-local influence on the the spin orientation, but not on the motion of the particles themselves. This is a key point in the search for a physical understanding of this non-local influence.

Figure 2 :

 2 Figure 2: Measuring the orientation of a coin by clapping hands.

Figure 3 :

 3 Figure 3: Two successive measurements of the orientation of the coin with measuring devices oriented in the same direction.

Figure 4 :

 4 Figure 4: Two successive measurements of the orientation of the coin with measuring devices oriented in perpendicular directions.

Figure 5 :

 5 Figure 5: Three successive measurements of the orientation of the coin with measuring devices oriented respectively in relation to ẑ then ŷ then again ẑ.

Figure 7 :

 7 Figure 7: Orthodox quantum mechanics: Pauli equation + reduction of the wave packet (final position).The notion of trajectory does not exist; only the position at the time of the measurement is defined using the postulate of reduction of the wave packet. The atom is either a wave (during all the experiment) or a particle (at the moment of impact).

Figure 8 :

 8 Figure 8: dBB theory (quantum mechanics taken one step further): Pauli equation + initial position. The arrows indicate the θ orientation of the spin vector s (initially θ 0 = π/3). The position of the particle exists before the measurement; the particle follows a deterministic trajectory and the impact on the screen only reveals its position. The atom is both a wave and a particle during all the experiment.

Figure 9 :

 9 Figure 9: Six trajectories of silver atoms from the same pure state θ 0 = π/2. The arrows indicate the evolution of θ, initially all θ = π/2.

Figure 10 :

 10 Figure 10: Six trajectories of silver atoms resulting from a statistical mixture of pure states. The initial arrows indicate the θ 0 of the pure state (i.e. of the spinor) of each particle.


Attila A Yavuz
email: attila.yavuz@us.bosch.com

Practical Immutable Signature Bouquets (PISB) for Authentication and Integrity in Outsourced Databases

Keywords: Applied cryptography, outsourced databases, immutable digital signatures, distributed systems, public key cryptography. Low-bandwidth Data Queriers

Database outsourcing is a prominent trend that enables organizations to offload their data management overhead (e.g., query handling) to the external service providers. Immutable signatures are ideal tools to provide authentication and integrity for such applications with an important property called immutability. Signature immutability ensures that, no attacker can derive a valid signature for unposed queries from previous queries and their corresponding signatures. This prevents an attacker from creating his own de-facto services via such derived signatures. Unfortunately, existing immutable signatures are very computation and communication costly (e.g., highly interactive), which make them impractical for task-intensive and heterogeneous applications. In this paper, we developed two new schemes that we call Practical and Immutable Signature Bouquets (PISB ), which achieve efficient immutability for outsourced database systems. Both PISB schemes are very simple, non-interactive, and computation/communication efficient. Our generic scheme can be constructed from any aggregate signature coupled with a standard signature. Hence, it can flexibly provide performance trade-offs for various types of applications. Our specific scheme is constructed from Condensed-RSA and Sequential Aggregate RSA. It has a very low verifier computational overhead and end-to-end delay with a small signature size. We showed that PISB schemes are secure and also much more efficient than previous alternatives.

Introduction

It is a growing trend that the data is outsourced and being managed (e.g., query handling, maintenance) on remote servers, which are maintained by third party outsourcing vendors. One such data outsourcing approach is "database as a service" (DAS) model [START_REF] Hacigumus | Providing database as a service[END_REF], in which clients outsource their data to a database service provider 1,2 that offers a reliable maintenance and access for the hosted data [START_REF]Secure data outsourcing[END_REF].

Data outsourcing can significantly reduce the cost of data management (e.g., via continuous service, expertise, upgrade/maintanence) and therefore it is highly beneficial for entities with limited management capabilities such as small to medium businesses [START_REF]Secure data outsourcing[END_REF][START_REF] Mykletun | Authentication and integrity in outsourced databases[END_REF][START_REF] Patel | Security and availability of data in the cloud[END_REF]. However, despite its merits, data outsourcing brings various security challenges, since the sensitive data is hosted in a (semi or fully) untrusted environment. These security challenges include but not limited to the confidentiality [START_REF] Wang | Proceedings of the 32nd international conference on Very large data bases[END_REF], access privacy [START_REF] Goodrich | Privacy-preserving group data access via stateless oblivious ram simulation[END_REF], authentication and integrity [START_REF] Mykletun | Signature bouquets: Immutability for aggregated/condensed signatures[END_REF]. Another challenge is to provide the security efficiently such that the data outsourcing still remains practical and cost efficient.

In this paper, we focus on providing authentication and integrity of outsourced data via aggregate signatures (e.g., [START_REF] Boneh | Aggregate and verifiably encrypted signatures from bilinear maps[END_REF]), while also guaranteeing a vital security property called signature immutability in a practical manner.

In Section 1.1, we give our data and system models. In Section 1.2, we describe the signature mutability problem and limitations of existing solutions. In Section 1.3, we summarize our contributions and highlight the desirable properties of our schemes.

System and Data Model

We follow Mykletun et al.'s Outsourced Database Model (ODB) [START_REF] Mykletun | Authentication and integrity in outsourced databases[END_REF][START_REF] Mykletun | Signature bouquets: Immutability for aggregated/condensed signatures[END_REF], which is a variant of traditional "database as a service" model [START_REF] Hacigumus | Providing database as a service[END_REF].

System Model: There are three types of entities in the system; data owners, server (database service provider) and data queriers (clients). These entities behave as follows.

• Data Owners: A data owner can be a single or a logical entity such as an organization. Each data owner in the system signs her database elements (e.g., each tuple separately) and then outsources them along with their signatures to the server. This protects the integrity and authentication of outsourced data against both the server and outside adversaries (e.g., in the case of the server is compromised).

The data owner computes the individual signature of each database element (e.g., each tuple) with an aggregate signature scheme (e.g., [START_REF] Boneh | Aggregate and verifiably encrypted signatures from bilinear maps[END_REF]), which allows the combination of these signatures according to the content of a query. This enables the server to reply any query on the outsourced data with a compact constant size signature (instead of sending a signature for each element in the query, which entails a linear communication overhead). This outsourcing step is performed offline, and therefore its cost is not the main concern.

• Server (Service Provider): The server maintains the data and handles the queries of data queriers. The server is trusted with these services, but it is not trusted with the integrity and authentication of the hosted data. Hence, each data owner digitally signs her data before outsourcing it as described previously.

Once a data querier (i.e., clients who perform data queries) queries the server, the server computes a constant size signature by aggregating the corresponding individual signatures of database elements associated with this query. Recall that the server knows these individual signatures, since the data owner provided all individual signatures to the server at the offline phase. The server then performs necessary cryptographic operations to ensure the immutability of this aggregate signature. Observe that the server faithfully follows the immutability operations, since the immutability prevents external parties to offer similar services free of charge. The query handling phase is performed online. The server is expected to handle larger number of queries simultaneously with a minimum end-to-end delay. Therefore, the cost of signature immutability operations are highly critical.

• Data Queriers (Clients): Queriers are heterogeneous entities, which may be resourceconstrained in terms bandwidth, battery and/or computation (e.g., a mobile device or a PDA). A querier can make a query on the database elements belonging to a single or multiple data owners. The former is called non-cross signer queries while the latter is called cross signer queries. The data querier verifies the corresponding aggregate signature of her query, along with cryptographic tokens transmitted for the immutability.

Figure 1 summarizes the ODB model described above. Data Model and Scope: We assume that the data is managed with a traditional relational database management system and the queries are formulated with SQL. Our work handles SQL queries involving SELECT clauses, which return the selection of a set of records or fields matching a given predicate. Our work does not address SQL queries involving data aggregation that return a single value for a given query.

The granularity of data integrity and authentication may vary according to the application (e.g., attribute level). One possible choice is to provide them at the tuple level (i.e., sign each tuple individually), which offers a balance between the storage, transmission and computation overheads introduced by the cryptographic scheme [START_REF] Mykletun | Authentication and integrity in outsourced databases[END_REF].

Problem Statement and Limitations of Existing Solutions

Ability to aggregate different signatures into a single signature is advantageous, but it also allows any party to derive new aggregate signatures from the existing ones. For instance, assume that the server provides signatures (σ 1,l , σ 1,k ) on queries (m 1 , . . . , m l ) and (m 1 , . . . , m k ), respectively, where 1 < k < l and the aggregation operation is addition (e.g., [START_REF] Boneh | Aggregate and verifiably encrypted signatures from bilinear maps[END_REF]). Any querier can derive a valid signature on query elements m k+1 , . . . , m l (that have not been queried before) by simply computing σ k+1,l = σ 1,l -σ 1,k .

This property has undesirable effects on many real-life applications. One example is content access control mechanisms for outsourced databases. Assume that the data owner requires the server to enforce an access control policy, in which each client can access only certain parts of the database via an access token (i.e., a signature). A group of clients can possess different access privileges from those owned by each client in isolation. Figure 2 exemplifies how three colluding clients can derive a valid token (i.e., signature) with an access right beyond their actual privileges.

Another example is paid database services, in which the server acts as an authorized re-distribution agent for the information contained in the outsourced database. Assume that the server charges a fee for each music album queried (downloaded) over the outsourced database. Signature mutability allows an unauthorized splitting and redistribution of authentic query replies. Colluding clients may gather various music albums and their signatures, and combine and re-sell them according to their will (without paying/obtaining any authorization) [START_REF] Mykletun | Signature bouquets: Immutability for aggregated/condensed signatures[END_REF].

Mykletun et al. [START_REF] Mykletun | Signature bouquets: Immutability for aggregated/condensed signatures[END_REF] introduce signature immutability techniques to address these problems. Their RSA-based techniques prevent an adversary from deriving new signatures by hiding the actual aggregate signature via an interactive Guillou-Quisquater (GQ) [START_REF] Guillou | A "paradoxical" identity-based signature scheme resulting from zero-knowledge[END_REF] based protocol. This approach is interactive and therefore introduces high communication overhead and end-to-end delay. Their non-interactive RSA variant uses a signatures of knowledge method, which substantially increases the computational cost and has large signature size. Their BLS signature method iBGLS [START_REF] Boneh | Aggregate and verifiably encrypted signatures from bilinear maps[END_REF] offers a small signature size, but it is very computationally costly due to cryptographic pairing operations. Hence, none of these techniques are suitable for nowadays task-intensive and heterogeneous outsourcing applications.

Our Contribution

To address these limitations, we develop novel cryptographic schemes called Practical Immutable Signature Bouquets (PISB), which is suitable for outsourced database systems. Specifically, we developed a Condensed-RSA (C-RSA) and Sequential Aggregate RSA (SA-RSA) based scheme called PISB -CSA-RSA and a generic scheme called PISB -Generic. We summarize the desirable properties of our schemes below:

• Non-interactive Signature Immutability: PISB schemes do not require any multiround interaction among the server and queriers. Hence, they are much more communication efficient than previous alternatives. For instance, our PISB -CSA-RSA incurs only 1KB communication overhead, while GQ-based scheme in [START_REF] Mykletun | Authentication and integrity in outsourced databases[END_REF][START_REF] Mykletun | Signature bouquets: Immutability for aggregated/condensed signatures[END_REF] requires 9KB. Moreover, the non-interactive nature of our schemes make them packet loss tolerant, which is a desirable property for mobile and ad-hoc clients (queriers). • Analytical comparison, key/parameter sizes and measurement details are given in Section 6.

• The immutable signature size is the aggregate signature size plus the size of additional cryptographic tags transmitted (e.g., protection signatures, values transmitted for multi-rounds).

• PISB-Generic is instantiated with BLS [START_REF] Boneh | Aggregate and verifiably encrypted signatures from bilinear maps[END_REF] as ASig (20 byte aggregate signature) and with ECDSA [START_REF]Public Key Cryptography for the Financial Services Industry: The Elliptic Curve Digital Signature Algorithm[END_REF] as Sig (40 byte protection signature) for pre-computed parameters (0.36 ms) [START_REF]Multiprecision integer and rational arithmetic c/c++ library (MIRACL)[END_REF] or pre-computed tokens [START_REF] Naccache | be improved? Complexity trade-offs with the digital signature standard[END_REF] (0.03 ms).

• End-to-end delay is the sum of client and server execution times plus the estimated communication delay introduced by multi-rounds. Only GQ-based scheme requires multi-rounds, which substantially increase its end-to-end delay.

• Remark: PISB-CSA-RSA is significantly more efficient than all of its counterparts at the client side, which makes it suitable for mobile or resource-constrained queriers. Its end-to-end delay is also 40 to 60 times lower than its alternatives.

PISB-Generic offers various performance trade-offs with its generic structure (e.g., only alternative with pre-computability). This instantiation of PISB-Generic offers small signature/key sizes and high server efficiency simultaneously. PISB-Generic and PISB-CSA-RSA are suitable for cross and non-cross signer models, respectively (see Section 1.2). PISB schemes are also provable secure.

• High Computational Efficiency: PISB schemes are much more computationally efficient than their counterparts. PISB -CSA-RSA is the most client efficient scheme among its counterparts, being a magnitude of time faster than SKROOT-based and iBGLS schemes in [START_REF] Mykletun | Authentication and integrity in outsourced databases[END_REF][START_REF] Mykletun | Signature bouquets: Immutability for aggregated/condensed signatures[END_REF]. Therefore, PISB -CSA-RSA is an ideal alternative for battery and/or computational limited clients (queriers) such as mobile and hand-held devices. It is also plausibly efficient at the server side while achieving this client efficiency. PISB -Generic is the most server efficient scheme among its counterparts due to its pre-computability property. This enables the server to responde large number queries in peak times without being bottlenecked. • Small Signature Sizes: PISB -CSA-RSA is the only RSA-based scheme that can compute a compact immutable aggregate signature, which makes it more communication efficient than its counterparts [START_REF] Mykletun | Authentication and integrity in outsourced databases[END_REF][START_REF] Mykletun | Signature bouquets: Immutability for aggregated/condensed signatures[END_REF]. PISB -Generic has a much smaller signature size than RSA-based schemes and also has a comparable signature size with iBGLS in [START_REF] Mykletun | Authentication and integrity in outsourced databases[END_REF][START_REF] Mykletun | Signature bouquets: Immutability for aggregated/condensed signatures[END_REF] (while being much more computationally efficient). • Minimum End-to-end Delay: PISB schemes have a much smaller end-to-end delay than all of their counterparts, which offers a better service quality. • Provable Security: Previous works (e.g., [START_REF] Mykletun | Authentication and integrity in outsourced databases[END_REF][START_REF] Mykletun | Signature bouquets: Immutability for aggregated/condensed signatures[END_REF]) give only heuristic security arguments regarding the signature immutability. Our work is the only one providing a formal security model and proofs for the signature immutability.

Table 1 outlines the properties and compares PISB schemes with their counterparts.

The remainder of this paper is organized as follows. Section 2 provides definitions used by our schemes. Section 3 defines our security model. Section 4 describes the proposed schemes in detail. Section 5 provides the security analysis. Section 6 gives the performance analysis and compares our schemes with their counterparts. Section 7 outlines related work and Section 8 concludes this paper.

Preliminaries

In this section, we give the preliminary definitions used by our schemes. The standard security notion for a signature scheme is Existential Unforgeability under Chosen Message Attacks (EU -CMA) [START_REF] Katz | Introduction to Modern Cryptography[END_REF], which is defined below. Definition 2. EU -CMA experiment for Sig is defined as follows:

-Setup. Challenger algorithm B runs the key generation algorithm as (sk , pk ) ← Sig.Kg (1 κ ) and provides pk to the adversary A .

-Queries. Beginning from j = 1 and proceeding adaptively, A queries B on any message m j of her choice up to q s messages in total. For each query j, B computes s j ← Sig.Sign(sk , m j ) as the signing oracle of A and returns s j to A .

-Forgery. Finally, A outputs a forgery (m * , s * ) and wins the EU -CMA experiment, if Sig.Ver (pk , m * , s * ) = 1 and m was not queried to B .

Sig is (t, q s , ϵ)-EU -CMA secure, if no A in time t making at most q s signature queries has an advantage at least with probability ϵ in the above experiment.

An aggregate signature scheme (e.g., [START_REF] Boneh | Aggregate and verifiably encrypted signatures from bilinear maps[END_REF]) aggregates multiple signatures of different signers into a single compact signature. Hence, it can be used for cross querier applications. Definition 3. An aggregate signature scheme ASig is a tuple of four algorithms (Kg, Sign, Agg, Ver ) defined as follows: The EU -CMA experiment for ASig is a straightforward extension of Definition 2, in which A is required to produce a forgery under a public key pk ∈ -→ pk that is not under his control during the experiment (see [START_REF] Boneh | Aggregate and verifiably encrypted signatures from bilinear maps[END_REF] for details).

-( -→ sk, -→ pk) ← ASig.
Condensed-RSA (i.e., C -RSA) [START_REF] Mykletun | Authentication and integrity in outsourced databases[END_REF][START_REF] Mykletun | Signature bouquets: Immutability for aggregated/condensed signatures[END_REF] aggregates RSA signatures computed under the same private key. Hence, it is used for non-cross querier (signer) applications. Definition 4. C -RSA is a tuple of three algorithms (Kg, Sig, Ver ) defined as follows:

-(sk , pk ) ← C -RSA.Kg(1 κ ): Given the security parameter 1 κ , the key generation algorithm generates a RSA private/public key pair. That is, it randomly generates two large primes (p, q) and computes n = p • q. The public and secret exponents

(e, d) ∈ Z * ϕ(n) satisfies e • d ≡ 1 mod ϕ(n), where ϕ(n) = (p -1)(q -1).
The key generation algorithm returns sk ← (n, d) and pk ← (n, e) as the output.

σ ← C -RSA.Sig(sk , -→ m): Given sk and messages -→ m = (m 1 , . . . , m l ), the signing algorithm returns a signature σ ← ∏ l j=1 s j mod n as the output, where s j ← [H(m j )] d mod n for j = 1, . . . , l. H is a full domain hash function (e.g., [START_REF] Bellare | The exact security of digital signatures: How to sign with RSA and Rabin[END_REF]) de A sequential aggregate signature (e.g., [START_REF] Lysyanskaya | Sequential aggregate signatures from trapdoor permutations[END_REF]) requires that the signature generation and verification are performed in a specific order. The signature generation and aggregation operations are unified.

In PISB -CSA-RSA, we use a (simplified) single signer (and aggregator) instantiation of SA-RSA [START_REF] Lysyanskaya | Sequential aggregate signatures from trapdoor permutations[END_REF] (also see Remark 1 in Section 4). However, for the sake of completeness, we give the full description of SA-RSA for multiple-signers below. Definition 5. Sequential Aggregate RSA (denoted as SA-RSA) is a tuple of three algorithms (Kg, ASign, Ver ) defined as follows:

-

( -→ sk, -→ pk) ← SA-RSA.Kg(1 κ ):
Given the security parameter 1 κ and a set of signers U = {1, . . . , u}, the key generation algorithm generates a RSA private/public key pair

sk i ← (n i , d i ) and pk i ← (n i , e i ), ensuring that 2 k-1 (1 + (i -1)/u) ≤ n i < 2 k-1 (1 + i/u), where k = |n i | for i = 1, . . . , u. It returns a private/public key pair -→ sk ← {n i , d i } u i=1 and -→ pk ← {n i , e i } u i=1 as the output. -σ 1,u ← SA-RSA.Sig(sk u , {m i } u-1 i=1 , m u , {pk i } u-1 i=1 , pk u , σ 1,u-1 ):
The signer u receives aggregate signature σ 1,u-1 on messages {m i } u-1 i=1 under public keys {pk i } u-1 i=1 . The signer u first verifies σ 1,u-1 with the verification algorithm SA-RSA.Ver . If it succeeds, the signer u computes the signature on -→ m = (m 1 , . . . , m u ) under

-→ pk as h u = H( -→ m|| -→ pk) and y u = h u + σ 1,u-1 . The sequential aggregate signature outputs the signature σ 1,u ← y du u mod n u . -c ← SA-RSA.Ver ( -→ m, -→ pk, σ 1,u ): Given σ 1,u on -→ m under public keys -→ pk = {n i , e i } u i=1 , first check 0 ≤ σ 1,u ≤ n u . If gcd(σ 1,u , n u ) = 1 then y u ← σ eu 1,u mod n u else y u ← σ 1,u . Compute h u ← H( -→ m|| -→ pk) and σ 1,u-1 ← (y u -h u ) mod n u .
Verify signatures recursively as described until the base case u = 1, in which check

(σ 1,1 -h 1 ) mod n 1 = 0 where h 1 ← (m 1 ||pk 1 ). If it holds return c = 1 else c = 0.

Security Model

Our security model reflects how PISB system model works. That is, our security model formally captures the immutability of aggregate signatures for the EU -CMA experiment, which we call Immutable-EU -CMA (I -EU -CMA) experiment. Definition 6. I -EU -CMA experiment for PISB is defined as follows:

-Setup. Challenger algorithm B runs (SK , PK ) ← PISB .Kg (1 κ ) and provides PK to the adversary A . -Queries. A queries B on any message -→ m j = (m j,1 , . . . , m j,l ) of her choice for j = 1, . . . , q s . B replies each query j with a signature γ j computed under PK .

-Forgery. A outputs a forgery (m * , γ * ) and wins the

EU -CMA experiment, if (i) PISB .Ver (PK , m * , γ * ) = 1, (ii) m * ̸ ⊆ { -→ m j } qs j=1 or ∃I ⊆ {1, . . . , q s } : m * ⊆ || k∈I -→ m k
That is, the forgery is valid and m * has not been queried or it is a subset and/or any combination of previously queried data items ( -→ m 1 , . . . , -→ m qs ).

PISB is (t, q s , ϵ)-I -EU -CMA secure, if no A in time t making at most q s signature queries has an advantage at least with probability ϵ in the above experiment.

The Proposed Schemes

In this section, we describe our proposed schemes. For each PISB scheme, we first give the intuition behind the scheme followed by its detailed description.

PISB-CSA-RSA Scheme: An effective way to provide the signature immutability is to compute a protection signature over all data items associated with the query. That is, the server computes a signature on all data items in the query with his own private key. He then aggregates the protection signature over the aggregate signature computed from data owner's signatures. Breaking the immutability of this final aggregate signature is as difficult as forging the server's protection signature [START_REF] Mykletun | Authentication and integrity in outsourced databases[END_REF][START_REF] Mykletun | Signature bouquets: Immutability for aggregated/condensed signatures[END_REF].

Despite its simplicity, this method is not applicable to aggregate signatures such as C -RSA, in which only the signatures computed under the same public key can be aggregated (also called as non-cross signer aggregate signature). Recall that C -RSA cannot aggregate signatures belonging to different signers, since an RSA modulus n can not be safely shared among multiple signers (this leads to the factorization of n, exposing the private keys [START_REF] Ding | Simple identity-based cryptography with mediated rsa[END_REF]). Hence, despite C -RSA is an efficient scheme, its immutable variants (e.g., [START_REF] Mykletun | Authentication and integrity in outsourced databases[END_REF][START_REF] Mykletun | Signature bouquets: Immutability for aggregated/condensed signatures[END_REF]) are inefficient as discussed in Section 1.2.

It is highly desirable to construct a scheme that can compute an aggregate RSA signature involving both a data owner and the server (without exposing their private keys via the factorization of modulo). Our main observation is that, this goal can be achieved by levering the sequential aggregate signatures from trapdoor permutations (e.g., SA-RSA [START_REF] Lysyanskaya | Sequential aggregate signatures from trapdoor permutations[END_REF]) together with C -RSA. They allow distinct signers to sequentially compute an aggregate signature under distinct public keys (Definition 5).

In PISB -CSA-RSA, the data owner computes RSA signatures s 1 , . . . , s l on m 1 , . . . , m l with her keys (n, d). During the query phase, the server computes a C -RSA signature σ ′ by aggregating RSA signatures. The server then uses SA-RSA to compute an immutable aggregate signature γ on m 1 , . . . , m l with his keys (n, d ) by aggregating it on σ ′ . The public key of the system is (⟨n, e⟩, ⟨n, e⟩). The verification order of the client is with SA-RSA under (n, e) for γ and then with C -RSA under (n, e) for σ ′ .

One may observe that breaking the immutability of PISB -CSA-RSA is as difficult as breaking RSA. We give the formal security analysis of PISB -CSA-RSA in Section 5 (Theorem 2).

The PISB -CSA-RSA algorithms are defined below.

′ ← (y ′ -h ′ ) mod n, where h ′ ← H( - → m||pk ). If C -RSA.Ver (pk , - → m, σ ′ ) = 1 then return c = 1 else c = 0.
Remark 1. In PISB -CSA-RSA, we use a simplified SA-RSA variant [START_REF] Lysyanskaya | Sequential aggregate signatures from trapdoor permutations[END_REF] with the following properties: (i) SA-RSA is used in a single signer setting (the server as the signer and aggregator). (ii) The public key correctness controls (e.g., range check and gcd control) are not required, since the public keys are already certified in our system model. That is, n i belongs to a legitimate signer and gcd(e i , ϕ(n i )) = 1 holds. This retains the computational efficiency of traditional small RSA exponents.

PISB-Generic Scheme: Our generic scheme relies on a very simple observation: It is possible to guarantee the immutability of an aggregate signature by simply computing a standard digital signature on it. That is, the server can simply sign the aggregate signature with his private key and define the immutable signature as a signature pair.

PISB -Generic slightly increases the signature size, since a secondary signature is transmitted along with the aggregate signature. However, this is actually more communication efficient than GQ-based and SKROOT-based methods in [START_REF] Mykletun | Authentication and integrity in outsourced databases[END_REF][START_REF] Mykletun | Signature bouquets: Immutability for aggregated/condensed signatures[END_REF]. That is, a secondary standard signature (e.g., ECDSA [START_REF]Public Key Cryptography for the Financial Services Industry: The Elliptic Curve Digital Signature Algorithm[END_REF] with 40 bytes) is much smaller than cryptographic values transmitted (e.g., up to 9 KB) to achieve the immutability in [START_REF] Mykletun | Authentication and integrity in outsourced databases[END_REF][START_REF] Mykletun | Signature bouquets: Immutability for aggregated/condensed signatures[END_REF].

PISB -Generic also allows the server to choose any signature scheme to provide the immutability. For instance, the server may use ECDSA tokens [START_REF] Naccache | be improved? Complexity trade-offs with the digital signature standard[END_REF] or offline/online signatures [START_REF] Catalano | Off-line/on-line signatures: Theoretical aspects and experimental results[END_REF], which enable very fast response times in demand peaks via pre-computability. This flexibility makes PISB -Generic more efficient at the server side than existing alternatives (see Table 1). However, note that, iBGLS has slightly smaller signature size (i.e., 20 byte) than that of PISB -Generic (with the expense of a much higher server computational overhead).

The PISB -Generic algorithms are defined below.

1) (SK , PK ) ← PISB -Generic.Kg(1 κ ): Execute ( -→ sk, -→ pk) ← ASig.Kg(1 κ
) for data owners U = {1, . . . , u}. Execute (sk , pk ) ← Sig.Kg (1 κ ) for the server. The system private and public keys are SK = ( -→ sk, sk ) and PK = ( -→ pk, pk ), respectively.

2)

- → V ← PISB -Generic.Init( -→ M , -→ sk, PK ): Let -→ M = { - → m 1 , . . . , - → m u } be database
elements to be outsourced, where each -→ m i = (m i,1 , . . . , m i,l ) belongs to the data owner

1 ≤ i ≤ u. Each data owner i computes s i,j ← ASig.Sign(sk i , m i,j ) for i = 1, . . . , u and j = 1, . . . , l. Set -→ V ← ( -→ M , -→ S , PK ) and provide - → V to the server, where - → S = {s i,j } u,l i=1,j=1 . 3) γ ← PISB -Generic.Sign(sk , -→ m, -→ V ):
The server receives a cross-signer query -→ m = {m 1 , . . . , m k } on a subset of k data owners U ∈ U. Fetch the corresponding public key and signatures on -→ m from -→ V as V ← {pk i , m i,j , s i,j } i∈U,∃j:mi,j ∈ -→ M and compute σ ← ASig.Agg(V ). Also compute s ′ ← Sig.Sign(sk , σ) and set γ ← (σ, s ′ ).

4) c ← PISB -Generic.Ver (PK , -→ m, γ): Given γ = (σ, s ′ ) and pk ← {pk i } i∈U , if
Sig.Ver (pk , s ′ , γ) = 1 and ASig.Ver ( -→ pk, -→ m, σ) = 1 hold return c = 1, else c = 0.

Security Analysis

We prove that PISB schemes are I -EU -CMA secure in Theorem 1 and Theorem 2.

We ignore terms that are negligible in terms of κ.

Theorem 1 PISB -Generic is (t, q s , ϵ)-I -EU -CMA secure, if ASig is (t ′ , q s , ϵ)-EU -CMA secure and Sig is (t ′ , q s , ϵ)-EU -CMA secure, where t ′ = O(t) + q s • (Op + Op ′ ) and
(Op, Op ′ ) denote the cost of signature generation for ASig and Sig, respectively.

Proof: Suppose algorithm A breaks (t, q s , ϵ)-I -EU -CMA secure PISB -Generic. We then construct a simulator B , which breaks (t ′ , q s , ϵ)-EU -CMA secure ASig or (t ′ , q s , ϵ)-EU -CMA secure Sig by using A as subroutine.

We set the EU -CMA experiments for ASig and Sig. B is given a ASig public key -→ pk and a Sig public key pk as the input, where ( -→ sk, -→ pk) ← ASig.Kg(1 κ ) and (sk , pk ) ← Sig.Kg(1 κ ). B is given an access to ASig.Sign and Sig.Sign oracles under -→ sk and sk up to q s signature queries on both, respectively (as in Definition 2).

We then set the I -EU -CMA experiment for PISB -Generic, in which B executes A as follows:

-Setup: Given ( -→ pk, pk ), B sets the PISB -Generic public key PK ← ( -→ pk, pk ) as in PISB -Generic.Kg algorithm. By Definition 6, B gives PK to A and also permits A to make q s PISB -Generic signature queries.

-Queries: A queries B on messages -→ m j = (m j,1 , . . . , m j,u ) of her choice for j = 1, . . . , q s . B handles these queries as follows:

(a) Given A 's j-th query -→ m j , B queries ASig.Sign oracle on -→ m j under -→ pk. The ASig.Sign oracle returns s j,i ← ASig.Sign(sk i , m j,i ) for i = 1, . . . , u. B then computes the aggregate signature as σ j ← ASig.Agg( -→ pk, -→ m j , s j,1 , . . . , s j,u ).

This step is identical to PISB -Generic.Init algorithm, where -→ M in this experiment is comprised of u vectors each with q s data items. (b) B queries Sig.Sign oracle on σ j under pk . The Sig.Sign oracle returns s ′ j ← Sig.Sign(sk , σ j ) (as in PISB -Generic.Sign algorithm, executed by the server).

B replies A with γ j = (σ j , s ′ j ). -Forgery of A : A outputs a forgery (m * , β * = ⟨σ * , s ′ * ⟩) and wins the I -EU -CMA ex- periment if (i) PISB -Generic.Ver (PK , m * , β * ) = 1, (ii) m * ̸ ⊆ { -→ m 1 , . . . , -→ m qs } or ∃I ⊆ {1, . . . , q s } : m * ⊆ || k∈I -→ m k
If A loses in the I -EU -CMA experiment then B also loses in the EU -CMA experiments for ASig and Sig, and therefore B aborts. Otherwise, B proceeds for two possible forgeries as follows: a) If m * ̸ ⊆ { -→ m 1 , . . . , -→ m qs } then B returns the forgery (m * , σ * ) against ASig, which is non-trivial since B did not ask m * to ASig.Sign. This forgery is valid since

PISB -Generic.Ver (PK , m * , β * ) = 1 implies ASig.Ver ( -→ pk, m * , σ * ) = 1. b) If ∃I ⊆ {1, . . . , q s } : m * ⊆ || k∈I -→ m k then B returns the forgery (σ * , s ′ * ) against
Sig, which is non-trivial since B did not ask σ * to Sig.Sign. This forgery is valid since

PISB -Generic.Ver (PK , m * , β * ) = 1 implies Sig.Ver (pk , σ * , s ′ * ) = 1.
The execution time of B is that of A plus the time required to handle A 's queries. That is, for each query of A , B requests one ASig and Sig signature, whose total costs for handling q s queries is

q s • (Op + Op ′ ). Hence, t ′ = O(t) + q s • (Op + Op ′ ).
A does not abort the during the query phase, as the simulation of B is perfectly indistinguishable. That is, the real and simulated views of A are identical, and each value in these views are computed identically as described during the experiment. The probability that A wins the experiment without querying B is negligible in terms of κ. Therefore, B wins with the probability ϵ that A wins.

Theorem 2 PISB -CSA-RSA is (t, q s , ϵ)-I -EU -CMA secure if RSA signature scheme is (t ′ , (2 • l)q s , ϵ)-EU -CMA secure, where t ′ = O(t) + 2(l • q s )Exp and Exp and l denote modular exponentiation and number of messages in a single PISB -CSA-RSA query, respectively.

Proof: Suppose algorithm A breaks (t, q s , ϵ)-I -EU -CMA secure PISB -CSA-RSA. We then construct a simulator B that breaks (t ′ , (2 • l)q s , ϵ)-EU -CMA secure RSA by using A as subroutine.

We set two separate EU -CMA experiments for B , in which it is given RSA public keys pk = (n, e) and pk = (n, e) and provided signature oracles under their corresponding private keys sk = (n, d) (i.e., oracle O 1 ) and sk = (n, d ) (i.e., oracle O 2 ), respectively. B will simulate A 's signature queries via (O 1 , O 2 ). B then executes A for the I -EU -CMA experiment for PISB -CSA-RSA as follows:

-Setup: Given (pk , pk ), B sets the PISB -CSA-RSA public key PK ← (pk , pk ) as in PISB -CSA-RSA.Kg algorithm. By Definition 6, B gives PK to A and allows A to ask q s PISB -CSA-RSA signatures under PK . -Queries: A queries B on messages -→ m j = (m 1 , . . . , m l ) of her choice for j = 1, . . . , q s . B handles these queries as follows: against O 2 . This forgery is valid and non-trivial as discussed the above.

The execution time and probability analysis are similar to Theorem 1 (i.e., the simulation is perfectly indistinguishable) and therefore are not repeated here.

In this section, we present the performance analysis of PISB schemes and compare them with the existing alternatives. Table 1 (see Section 1) and Table 2 summarize our performance analysis and comparison.

Computational Overhead: In PISB -Generic, the server requires a Sig.Sign plus the aggregation of l individual ASig signatures. The client requires a Sig.Ver plus ASig.Ver for l data items. In PISB -CSA-RSA, the server requires a C -RSA.Sig computation plus l modular multiplications. The client requires a single RSA.Ver plus C -RSA.Ver for l data items.

The PISB -CSA-RSA is the most client efficient scheme among all of its counterparts, since it only requires RSA and C -RSA signature verifications with a small exponent (e.g., e = 3). Therefore, it is an ideal choice for battery or computational limited queriers such as mobile devices. Its server side overhead is also plausible and smaller than SKROOT-based scheme. The end-to-end delay of PISB -CSA-RSA (l = 10) is 50, 65, 41, and 55 times lower than that of PISB -Generic, GQ-based, SKROOT-based and iBGLS schemes, respectively.

The PISB -Generic can be instantiated with various signature schemes, which allows different performance trade-offs. BGLS and ECDSA combination achieves both small signature size and high server efficiency, which is a desirable configuration for many applications. Using ECDSA with pre-computation offers the smallest server response time among all of its counterparts. However, BGLS increases the signature verification cost, incurring high overhead to the resource-constrained verifiers. Another alternative is to combine C -RSA and ECDSA, which achieves both very low server and client computational overheads with the cost of a slightly larger signature size. ECDSA can be replaced with an online/offline [START_REF] Catalano | Off-line/on-line signatures: Theoretical aspects and experimental results[END_REF] or one-time signature [START_REF] Reyzin | Better than BiBa: Short one-time signatures with fast signing and verifying[END_REF], which offers even faster server response with the expense of a very large signature size.

In both PISB and Mykletun et. al. schemes [START_REF] Mykletun | Authentication and integrity in outsourced databases[END_REF][START_REF] Mykletun | Signature bouquets: Immutability for aggregated/condensed signatures[END_REF], the initialization phases are performed offline (before the deployment) by the data owners, whose costs are similar for all schemes and therefore are omitted in this comparison. We focus on the client/server overheads, since they are the online (real-time) overheads and the most important performance metrics for our envisioned applications.

Communication and Storage Overhead: PISB schemes do not require any multiround communication to achieve the immutability. Therefore, their signature overhead is the aggregate signature plus the protection signature in PISB -Generic, and only the aggregate signature itself in PISB -CSA-RSA. The private and public key sizes are the sum of that of their base signature schemes.

PISB -Generic with BGLS and ECDSA has the smallest key and signature sizes among its counterparts with the exception of iBGLS (which has a much larger end-toend delay and client computation overhead). PISB -CSA-RSA also has much smaller signature and key sizes than that of GQ-based and SKROOT-based schemes. Despite GQ-based scheme is client and server computationally efficient, it is not practical due to its multi-round communication requirement (introduces a substantial communication delay as shown in Table 1, Section 1). Note that multi-round communication is undesirable for wireless and low bandwidth applications due to the packet loss potential. 1). • Multi-round schemes: GQ-based scheme needs three communication rounds (each three passes) to achieve κ ≥ 80, in which each pass needs to transmit an element from Z * N . • Measurements: Table 1 (see Section 1.3) shows the estimated execution times for l = 10 data items (query elements).

Estimated execution times are measured on a computer with an Intel(R) Core(TM) i7 Q720 at 1.60GHz CPU and 2GB RAM running Ubuntu 10.10. We used MIRACL [START_REF]Multiprecision integer and rational arithmetic c/c++ library (MIRACL)[END_REF] library.

Overall, our analysis indicates that PISB schemes are much more efficient and practical than Mykletun et. al. immutable signatures for outsourced database systems.

Related Work

Our schemes rely on aggregate signatures as the building block. Aggregate signatures aggregate n individual signatures associated with n different users (or data items) into a single, compact signature. The first aggregate signature scheme was proposed in [START_REF] Boneh | Aggregate and verifiably encrypted signatures from bilinear maps[END_REF], and then several new schemes achieving more advanced properties were developed (e.g., sequentiality [START_REF] Lu | Sequential aggregate signatures and multisignatures without random oracles[END_REF], ID-based for low storage overhead [START_REF] Boldyreva | Ordered multisignatures and identity-based sequential aggregate signatures, with applications to secure routing[END_REF]). We discussed aggregate, sequential aggregate [START_REF] Lysyanskaya | Sequential aggregate signatures from trapdoor permutations[END_REF][START_REF] Zhu | Finding compact reliable broadcast in unknown fixed-identity networks (short paper)[END_REF] and condensed signatures [START_REF] Mykletun | Authentication and integrity in outsourced databases[END_REF][START_REF] Mykletun | Signature bouquets: Immutability for aggregated/condensed signatures[END_REF] in Section 2.

Mykletun et. al. proposed the first immutable aggregate signatures [START_REF] Mykletun | Authentication and integrity in outsourced databases[END_REF][START_REF] Mykletun | Signature bouquets: Immutability for aggregated/condensed signatures[END_REF], which have been extensively compared with our schemes in Section 6. Immutable signatures serve as a cryptographic tool for various data outsourcing applications such as databaseas-a-service [START_REF] Mykletun | Aggregation queries in the database-as-a-service model[END_REF] and data protection methods (e.g., [START_REF] Samarati | Data protection in outsourcing scenarios: issues and directions[END_REF][START_REF] Thompson | Privacy-preserving computation and verification of aggregate queries on outsourced databases[END_REF]). They are also used with other cryptographic primitives such as forward-secure signatures to obtain forwardsecure and aggregate logging systems (e.g., [START_REF] Ma | A new approach to secure logging[END_REF][START_REF] Yavuz | BAF and FI-BAF: Efficient and publicly verifiable cryptographic schemes for secure logging in resource-constrained systems[END_REF][START_REF] Yavuz | Efficient, compromise resilient and append-only cryptographic schemes for secure audit logging[END_REF]). Immutability techniques used in these schemes require linear overhead and therefore are not suitable for our envisioned applications.

Note that our work focuses on the authentication and integrity services. There are extensive studies on the data privacy for outsourced database systems (e.g., [START_REF] Ostrovsky | A survey of single-database private information retrieval: techniques and applications[END_REF][START_REF] Popa | Cryptdb: protecting confidentiality with encrypted query processing[END_REF]), which are complementary to our work.

Conclusion

In this paper, we developed new cryptographic schemes called PISB , which provide practical immutable signatures for outsourced databases. PISB -CSA-RSA provides the signature immutability with a very low verifier computational overhead, which is ideal for battery/computation limited queriers (e.g., mobile devices). It also offers a very low end-to-end delay, which is desirable for task-intensive applications by increasing the service quality. PISB -Generic offers various options such as signature pre-computability with its generic construction, which enables a quick server response during query peak times. Both PISB schemes are non-interactive and have small signature sizes. We demonstrate that PISB schemes are much more efficient than previous immutable signatures. Hence, PISB schemes are ideal choices for providing immutability, authentication and integrity services for outsourced database systems.

( 2 )( 3 )Fig. 1 .

 231 Fig. 1. Mykletun et al.'s Outsourced Database Model (ODB)

Fig. 2 .

 2 Fig. 2. An example of signature mutability in the content access control applications

Definition 1 .

 1 A signature scheme Sig is a tuple of three algorithms (Kg, Sign, Ver ) defined as follows: -(sk , pk ) ← Sig.Kg(1 κ ): Given the security parameter 1 κ , the key generation algorithm returns a private/public key pair (sk , pk ) as the output. -s ← Sig.Sign(sk , m): The signing algorithm takes sk and a message m as the input. It returns a signature s as the output. -c ← Sig.Ver (pk , m, s): The signature verification algorithm takes pk , m and s as the input. It outputs a bit c, with c = 1 meaning valid and c = 0 meaning invalid.

  fined as H : {0, 1} * → Z n . -c ← C -RSA.Ver (pk , -→ m, σ): Given pk = (n, e), -→ m and σ, if σ e = ∏ l j=1 H(m j ) mod n then the signature verification algorithm returns bit c = 1 else c = 0.

1 )

 1 (SK , PK ) ← PISB -CSA-RSA.Kg(1 κ ): The data owner executes (sk , pk ) ← C -RSA.Kg(1 k ), where sk = (n, d) and pk = (n, e). The server generates a RSA private/public key pair sk ← (n, d ) and pk ← (n, e) such that n < n. The system private/public key are SK ← (sk , sk ) and PK ← (pk , pk ).

  -CSA-RSA.Init( -→ m, sk ): The data owner computes an individual signature s j ← [H(m j )] d mod n for j = 1, . . . , l, where -→ m = (m 1 , . . . , m l ). The data owner sets the message-signature pairs as -→ V ← ( -→ m, -→ S ) and provide -→ V to the server, where -→ S = (s 1 , . . . , s l ). 3) γ ← PISB -CSA-RSA.Sign(sk , -→ m, -→ V ): The server receives a non-cross-signer query -→ m = (m 1 , . . . , m l ). It fetches the corresponding signatures (s 1 , . . . , s l ) on -→ m from -→ V and computes σ ′ ← ∏ l j=1 s j mod n. It then computes h ← H( -→ m||pk ), y ← (h + σ ′ ) mod n and γ ← y d mod n. 4) c ← PISB -CSA-RSA.Ver (PK , -→ m, γ): Given γ, the verifier computes y ′ ← γ e mod n and σ

  (a) Given A 's j-th query -→ m j , B queries O 1 on each m i and obtains corresponding s i under pk for i = 1, . . . , l (as in PISB -CSA-RSA.Init, data owner).(b) B computes σ ′ ← ∏ l i=1 s i mod n, h ← H( -→ m j ||pk ) and y ← h + σ ′ . B queries O 2 ony under pk and obtains γ (as in PISB -CSA-RSA.Sign, executed by the server).-Forgery of A : A outputs a forgery (m * , γ * ) and wins theI -EU -CMA experiment if (i) PISB -CSA-RSA.Ver (PK , m * , γ * ) = 1, (ii) m * ̸ ⊆ { -→ m 1 , . . . , -→ m qs } or ∃I ⊆ {1, . . . , q s } : m * ⊆ || k∈I -→ m k If Aloses in the I -EU -CMA experiment then B also loses in the EU -CMA experiments for RSA against O 1 and O 2 , and therefore B aborts. Otherwise, B computes y * ← (γ * ) e mod n and σ * ← y * -H(m * ||pk ) and continues as follows: a) If m * ̸ ⊆ { -→ m 1 , . . . , -→ m qs } then B returns the forgery (m * , s * ) against O 1 , where s * is computed from σ * by removing the corresponding individual signatures of data items in m * that have been queried before (if m * is not a vector then use s * itself). This forgery is non-trivial since B did not ask m * to O 1 during the experiment. B also returns the forgery (y * , γ * ) against O 2 , which is non-trivial since B did not ask y * to O 2 during the experiment. Both forgeries are valid since PISB -CSA-RSA.Ver (PK , m * , γ * ) = 1 implies m * and y * are valid under pk and pk , respectively. b) If ∃I ⊆ {1, . . . , q s } : m * ⊆ || k∈I -→ m k holds then B returns the forgery (σ * , γ * )

  • Parameters: Given κ = 80, we select |n| = 1024, |H| = 160, |q ′ | = 160, |p ′ | = 512, |b| = 30.

Table 1 .

 1 The client/server overhead of PISB and its counterparts for 10 items in a query (in ms)

	-	PISB -GenericPISB -CSA-RSA GQ-based [7] SKROOT [7]iBGLS [7]
	Server Comp.	0.66 / 0.39	4.03	1.5	92.4	2.2
	Client Comp.	224.97	0.46	1.57	92.77	245.7
	Extra rounds	0	0	3 rounds ( each 3 passes)	0	0
	(Est.) End-to-end	225.63	4.49	292	185.17	247.9
	Signature size	60 byte	1 KB	9 KB	4 KB	20 byte
	sk size	40 byte	2 KB	1 KB	5 KB	20 byte
	pk size	80 byte	1 KB	1 KB	1 KB	40 byte
	Aggregation TypeCross/non-cross	Non-cross Non-cross No Non-cross No No	No

  Kg(1 κ ): Given the security parameter 1 κ and a set of signers U = {1, . . . , u}, the aggregate key generation algorithm generates a private/public key pair (sk i , pk i ) for i = 1, . . . , u, as in Definition 1 key generation algorithm. As inDefinition 1 signature generation algorithm. -σ 1,u ← ASig.Agg({pk i , m i , s i } u i=1 ): The aggregation algorithm takes {pk i , m i , s i } u i=1 as the input. It combines individual signatures s i , 1 ≤ i ≤ u and returns an aggregate signature σ as the output. -c ← ASig.Ver ({pk i , m i } u i=1 , σ 1,u ): The aggregate verification algorithm takes {pk i , m i } u i=1 and σ 1,u as the input. It outputs a bit c, with c = 1 meaning valid and c = 0 meaning invalid.

	gregate key generation algorithm returns a private/public key pair and -→ pk = (pk 1 , . . . , pk u ) as the output.	The ag-sk = (sk 1 , . . . , sk u ) -→

s i ← ASig.Sign(sk i , m i ):

Table 2 .

 2 The client and server overhead of PISB and its counterparts for l data items (analytical) Exp |x| |y| denotes a modular exponentiation with a modulus and exponent sizes |y| and |x|, respectively. M ul denotes modular multiplication under modulus n. BM , EAdd, and EM ul denote ECC bilinear map, scalar addition and scalar multiplication over modulus q ′ , respectively. ASig.Ver l denotes the aggregate signature verification for l items (the notation applies to ASig.Agg). We omit constant number of low-cost operations if there is an expensive operation (e.g., a single H or M ul is omitted if there is an Exp). We use double-point scalar multiplication for ECDSA verifications(1.3 • Emul instead of 2 • EM ul). |σ|, |sk | and |pk | denote the bit lengths of signature, private key and public key for Sig, respectively (Sig is selected as ECDSA with |q ′ | in Table

	-	Client Comp.	Server Comp.	Sig. SK	PK
	PISB -Generic Sig.Ver + ASig.Ver l Sig.Sign + ASig.Agg l |σ|	|sk |	|pk |
	PISB -CSA-RSA 3M ul + l(H + M ul)	Exp	|n| |n| + l • M ul	|n| 2|n|	2|n|
	GQ-based	3Exp	|b| |n| + l(H + M ul) 3Exp |b| |n| + l • M ul 9|n| |b| + |n| |b| + |n|
	SKROOT-based 4Exp |n| |2n| + l(H + M ul) 4Exp	|n| |2n| + l • M ul 4|n| 5|n|	|n|
	iBGLS	(l + 1)(BM + H)	EM ul + l • EAdd	|q ′ |	|q ′ | |p ′ | + |q ′ |

• Notation:

http://www.ibm.com/software/data/db2

http://www-935.ibm.com/services/us/en/it-services/ storage-and-data-services.html