Applied Cryptography and Network Security

This paper describes new attacks on

pkcs

#1 v1.5, a deprecated but still widely used

rsa

encryption standard.

The first cryptanalysis is a broadcast attack, allowing the opponent to reveal an identical plaintext sent to different recipients. This is nontrivial because different randomizers are used for different encryptions (in other words, plaintexts coincide only partially).

The second attack predicts, using a

single

query to a validity checking oracle, which of two chosen plaintexts corresponds to a challenge ciphertext. The attack’s success odds are very high.

The two new attacks rely on different mathematical tools and underline the need to accelerate the phase out of

pkcs

#1 v1.5.

In a broadcast encryption system with a total of

n

users, each user is assigned with a unique index

i

 ∈ [1,

n

]. An encryptor can choose a receiver set

S

 ⊆ [1,

n

] freely and encrypt a message for the recipients in

S

such that only those receivers can open the message. The transmission overload of most previous broadcast encryption systems grows in line with the number of revoked users

r

and thus they are suitable for the scenario where the target receiver set is large when

r

 ≪ 

n

holds. Some other recently proposed constructions for arbitrary receiver set require a unreasonably large user storage and long decryption time. On the other hand, it is observed that, in a practical broadcast encryption system, the receiver set can be regarded as a collection of

k

natural intervals, where the interval number

k

should be much less than

r

for most cases. This observation motivates us to introduce a novel type of encryption, called interval encryption, which could realize a more efficient broadcast encryption. To achieve this, we first present a generic way to transform a binary tree encryption scheme into interval encryption. One concrete instantiation of this method based on the hierarchical identity based encryption scheme by Boneh et al. only requires a

$\mathcal{O}(k)$

transmission cost and

$\mathcal{O}(\log n)$

private storage consumption, while the decryption is dominated by

$\mathcal{O}(\log n)$

group operations. With detailed performance analysis, we demonstrate that the proposed interval encryption strategy has the superiority on improved efficiency and thus is expected to serve as a more efficient solution in more cases than the traditional systems in practice. Interestingly, our methodology can also be employed to transform a fully secure hierarchical identity based encryption scheme proposed by Lewko and Waters into an adaptively secure interval encryption scheme with a

$\mathcal{O}(k)$

transmission cost and

$\mathcal{O}(\log n)$

private storage consumption. Finally, we also discuss several other promising applications of interval encryption.

To this day, realizations in the standard-model of (lossy) trapdoor functions from discrete-log-type assumptions require large public key sizes, e.g., about Θ(

λ

2

) group elements for a reduction from the decisional Diffie-Hellman assumption (where

λ

is a security parameter). We propose two realizations of lossy trapdoor functions that achieve public key size of only Θ(

λ

) group elements in bilinear groups, with a reduction from the decisional Bilinear Diffie-Hellman assumption.

Our first construction achieves this result at the expense of a long common reference string of Θ(

λ

2

) elements, albeit reusable in multiple LTDF instantiations. Our second scheme also achieves public keys of size Θ(

λ

), entirely in the standard model and in particular without any reference string, at the cost of a slightly more involved construction.

The main technical novelty, developed for the second scheme, is a compact encoding technique for generating compressed representations of certain sequences of group elements for the public parameters.

A sanitizable signature scheme allows a signer to partially delegate signing rights on a message to another party, called a sanitizer. After the message is signed, the sanitizer can modify pre-determined parts of the message and generate a new signature on the sanitized message without interacting with the signer. At ACNS 2008, Canard et al. introduced trapdoor sanitizable signatures based on identity-based chameleon hashes, where the power of sanitization for a given signed message can be delegated to possibly several entities, by giving a trapdoor issued by the signer at any time. We present a generic construction of trapdoor sanitizable signatures from ordinary signature schemes. The construction is intuitively simple and answers the basic theoretic question about the minimal computational complexity assumption under which a trapdoor sanitizable signature exists; one-way functions imply trapdoor sanitizable signatures.

Verifiably encrypted signature schemes (VES) allow a signer to encrypt his or her signature under the public key of a trusted third party, while maintaining public signature verifiability. With our work, we propose two generic constructions based on Merkle authentication trees that do not require non-interactive zero-knowledge proofs (NIZKs) for maintaining verifiability. Both are stateful and secure in the standard model. Furthermore, we extend the specification for VES, bringing it closer to real-world needs. We also argue that statefulness can be a feature in common business scenarios.

Our constructions rely on the assumption that CPA (even slightly weaker) secure encryption, “maskable” CMA secure signatures, and collision resistant hash functions exist. “Maskable” means that a signature can be hidden in a verifiable way using a secret masking value. Unmasking the signature is hard without knowing the secret masking value. We show that our constructions can be instantiated with a broad range of efficient signature and encryption schemes, including two lattice-based primitives. Thus, VES schemes can be based on the hardness of worstcase lattice problems, making them secure against subexponential and quantum-computer attacks. Among others, we provide the first efficient pairing-free instantiation in the standard model.

Kundu and Bertino (VLDB 2008) recently introduced the idea of structural signatures for trees which support public redaction of subtrees (by third-party distributors) while pertaining the integrity of the remaining parts. An example is given by signed XML documents of which parts should be sanitized before being published by a distributor not holding the signing key. Kundu and Bertino also provide a construction, but fall short of providing formal security definitions and proofs. Here we revisit their work and give rigorous security models for the redactable signatures for tree-structured data, relate the notions, and give a construction that can be proven secure under standard cryptographic assumptions.

Impossible differential cryptanalysis is well known to be effective in analyzing the security of block ciphers. Known result shows that there always exists 5-round impossible differentials of a Feistel cipher with bijective round function. However, if more details of the round function are known, the result could be improved. This paper mainly studies the impossible differentials of Feistel ciphers with both

SP

and

SPS

round functions where the linear transformation

P

is defined over

${\mathbb F}_2^{n\times n}$

. For Feistel ciphers with

SP

round functions, any column of

P

 ⊕ 

P

− 1

whose Hamming weight is greater than 1 corresponds to some 6-round impossible differentials. The existence of some 7-round impossible differentials can be determined by counting the times that 1 appears at some special positions of

P

and

P

− 1

. Some 8-round impossible differentials can be found by computing the rank of some sub-matrix of

P

. Impossible differentials of Camellia found by these techniques are well consistent with previously known results. For Feistel ciphers with

SPS

round functions, by determining the rank of some sub-matrix of

P

, 6-round impossible differentials can be found, which improves the results on E2 by one round. These results tell that when designing a Feistel cipher with

SP

or

SPS

round function where the diffusion layer is selected from

${\mathbb F}_2^{n\times n}$

, the linear transformation should be chosen carefully to make the cipher secure against impossible differential cryptanalysis.

Statistical Saturation Attacks have been introduced and applied to the block cipher PRESENT at CT-RSA 2009. In this paper, we consider their natural extensions. First, we investigate the existence of better trails than the one used in the former attack. For this purpose, we provide a theoretical evaluation of the trail distributions using probability transition matrices. Since the exhaustive evaluation of all possible distributions turned out to be computationally hard, we additionally provide a heuristic branch-and-bound algorithm that allows us to generate a large number of good trails. These tools confirm that the trail of CT-RSA 2009 was among the best possible ones, but also suggest that numerous other trails have similar properties. As a consequence, we investigate the use of multiple trails and show that it allows significant improvements of the previous cryptanalysis attempts against PRESENT. Estimated complexities indicate that PRESENT-80 is safe against key recovery, by a small security margin. We also discuss the impact of multiple trails for the security of the full PRESENT-128. We finally put forward a “statistical hull” effect that makes the precise theoretical analysis of our results difficult, when the number of block cipher rounds increases.

The stream cipher SNOW 3G designed in 2006 by ETSI/SA-GE is a base algorithm for the second set of 3GPP confidentiality and integrity algorithms. In this paper we study the resynchronization mechanism of SNOW 3G and of a similar cipher SNOW 3G

 ⊕ 

using multiset collision attacks. For SNOW 3G we show a simple 13-round multiset distinguisher with complexity of 2

8

steps. We show full key recovery chosen IV resynchronization attacks for up to 18 out of 33 initialization rounds of SNOW3G

 ⊕ 

with a complexity of 2

57

to generate the data and 2

53

steps of analysis.

This work presents a new method to compute the GHASH function involved in the Galois/Counter Mode of operation for block ciphers. If

X

 = 

X

1

...

X

n

is a bit string made of

n

blocks of 128 bits each, then the GHASH function effectively computes

$X_1H^n + X_2H^{n-1} + \ldots X_nH$

, where

H

is an element of the binary field

${\mathbb{F}}_{2^{128}}$

. This operation is usually computed by using

n

successive multiply-add operations over

${\mathbb{F}}_{2^{128}}$

. In this work, we propose a method to replace all but a fixed number of those multiplications by additions on the field. This is achieved by using the characteristic polynomial of

H

. We present both how to use this polynomial to speed up the GHASH function and how to efficiently compute it for each session that uses a new

H

.

The Advanced Encryption Standard (AES) is a 128-bit block cipher that is currently being widely used in smartcards. Differential Power Analysis (DPA) is a powerful technique used to attack a cryptographic implementation in a resource-limited application environment like smartcards. Despite the extensive research on DPA of AES, it seems none has explicitly addressed the fundamental issue: How many rounds of the beginning and end parts of an AES implementation should be protected in order to resist practical DPA attacks, namely first and second-order DPA attacks? Implementation designers may think that it is sufficient to protect the first and last one (or one and a half) rounds of AES, leaving the inner rounds unprotected or protected by simple countermeasures. In this paper, we show that power leakage of some intermediate values from the more inner rounds of AES can be exploited to conduct first and/or second-order DPA attacks by employing techniques such as fixing certain plaintext/ciphertext bytes. We give five general principles on DPA vulnerability of unprotected AES implementations, and then give several general principles on DPA vulnerability of protected AES implementations. These principles specify which positions of AES are vulnerable to first and second-order DPA. To justify the principles, we attack two recently proposed AES implementations that use two kinds of countermeasures to achieve a high resistance against power analysis, and demonstrate that they are even vulnerable to DPA. Finally, we conclude that at least the first two and a half rounds and the last three rounds should be secured for an AES implementation to be resistant against first and second-order DPA in practice.

Most side-channel attacks that have been published in the open literature assume known- or chosen-message adversarial scenarios. In this paper, we analyze the increase of the attacks’ efficiencies that can be obtained by adaptively selecting the messages. For this purpose, we first describe a generic strategy that allows an adversary to take advantage of this capability. We show that it can be applied to any differential power or electromagnetic analysis attack, against unprotected or protected devices and exploiting profiled or non-profiled leakage models. Then, we provide various experiments to quantify these improvements. Finally, we discuss the optimality of our strategy and its implications for the security evaluation of leakage-resilient cryptographic hardware.

Side Channel Analysis (SCA) is a powerful key recovery attack that efficiently breaks block ciphers implementations. In software, it is usually counteracted by applying a technique called masking, that combines the key dependent variables with random values. When the block cipher to protect mixes affine functions and power functions, a natural strategy is to additively mask the first category of functions and to multiplicatively mask the second one. Several works that follow this strategy have been proposed in the literature, but all of them have been proved to be flawed or very costly. The main difficulty comes from the multiplicative masking of the zero value in a finite field. In this paper, we propose a scheme to multiplicatively mask power functions in such a way that the security against first-order SCA is maintained. We moreover show how to securely combine additive masking of affine transformations with multiplicative masking of power functions. We then apply our method to protect the AES implementation and we show that our proposal offers good timing/memory performances.

In 2008, Groth and Sahai proposed a general methodology for constructing non-interactive zero-knowledge (and witness-indistinguishable) proofs in bilinear groups. While avoiding expensive NP-reductions, these proof systems are still inefficient due to the number of pairing computations required for verification. We apply recent techniques of

batch verification

to the Groth-Sahai proof systems and succeed to improve significantly the complexity of proof verification. We give explicit batch-verification formulas for generic Groth-Sahai equations (whose cost is less than a tenth of the original) as well as for specific popular protocols relying on their methodology (namely Groth’s group signatures and the P-signatures by Belenkiy, Chase, Kohlweiss and Lysyanskaya).

In this work, we design two-party and multiparty protocols for evaluating multivariate polynomials at participants’ inputs with security against a

malicious adversary

who may corrupt all but one of the parties. Our protocols are round and communication efficient, and use the underlying cryptographic primitives in a black-box way. Our construction achieves optimal communication complexity for degree 2 and 3 polynomials.

Our constructions can be used to securely and efficiently realize a wide range of functionalities. For instance, we demonstrate how our techniques lead to efficient protocols for secure linear algebra with security against malicious adversaries. Other applications include secure evaluation of DNF/CNF formulas, and conditional secret reconstruction (or conditional oblivious transfer) for a large family of condition functions.

We present an efficient implementation of the Orlandi protocol which is the first implementation of a protocol for multiparty computation on arithmetic circuits, which is secure against up to

n

 − 1 static, active adversaries. An efficient implementation of an actively secure self-trust protocol enables a number of multiparty computation where one or more of the parties only trust himself. Examples includes auctions, negotiations, and online gaming. The efficiency of the implementation is largely obtained through an efficient implementation of the Paillier cryptosystem, also described in this paper.

A traitor tracing scheme is a multiuser encryption that has a built-in key leakage deterrence mechanism : the sender is capable of utilizing a tracing process that can interact with any adversarial decoder and reveal the identities of the users whose keys are employed by the decoder. A number of desired design goals have been put forth for traitor tracing schemes, notably the minimization of the length of the ciphertexts, the length of the encryption key and the storage for private keys. An important efficiency parameter that is not as widely investigated is the round complexity of the tracing process, i.e., the number of rounds of interaction that is required for the tracing process to terminate. In this work we provide (1) a general formalization of this important design consideration, (2) a novel tracing procedure that exhibits an asymptotic improvement over the previously known approaches. Our first result is achieved by casting the tracing process as a game between the tracer and the adversary where the objective of the tracer is to reveal the identity of the corrupted users while the adversary wishes to prevent that while still meeting a minimum functionality requirement. The second result involves a novel application of fingerprinting codes.

We here describe a new Password-based Authenticated Key Exchange (PAKE) protocol based on elliptic curve cryptography. We prove it secure in the Bellare-Pointcheval-Rogaway (BPR) model. A significant novelty in our work is that the elliptic curve public parameters remain private. This is important in the context of ID contactless devices as, in this case, there will exist most probably a way to link these parameters with the nationality of the ID document owners.

This paper investigates the question of whether a key agreement protocol with the same communication complexity as the original Diffie-Hellman protocol (DHP) (

two

messages with a

single

group element per message), and similar low computational overhead, can achieve forward secrecy against active attackers in a

provable

way. We answer this question in the affirmative by resorting to an old and elegant key agreement protocol: the Okamoto-Tanaka protocol [22]. We analyze a variant of the protocol (denoted

mOT

) which achieves the above goal. Moreover, due to the identity-based properties of

mOT

, even the sending of certificates (typical for authenticated DHPs) can be avoided in the protocol.

As additional contributions, we apply our analysis to prove the security of a recent multi-domain extension of the Okamoto-Tanaka protocol by Schridde et al. and show how to adapt

mOT

to the (non id-based) certificate-based setting.

In this work, we develop a family of

non-malleable

and

deniable

Diffie-Hellman key-exchange (DHKE) protocols, named deniable Internet key-exchange (DIKE). The newly developed DIKE protocols are of conceptual clarity, provide much remarkable privacy protection to protocol participants, and are of highly practical (online) efficiency.

For the security of the DIKE protocols, we formulate the notion of

tag-based robust non-malleability

(TBRNM) for DHKE protocols, which ensures robust non-malleability for DHKE protocols against concurrent man-in-the-middle (CMIM) adversaries and particularly implies concurrent forward deniability for both protocol participants. We show that the TBRNM security and the session-key security (SK-security) in accordance with the Canetti-Krawczyk framework are mutually complementary, thus much desirable to have DHKE protocols that enjoy both of them simultaneously. We prove our DIKE protocol indeed satisfies both (privacy preserving) TBRNM security and SK-security (with post-specified peers). The TBRNM analysis is based on a variant of the knowledge-of-exponent assumption (KEA), called concurrent KEA assumption introduced and clarified in this work, which might be of independent interest.

We propose a new protocol providing cryptographically secure authentication to unaided humans against passive adversaries. We also propose a new generic passive attack on human identification protocols. The attack is an application of Coppersmith’s baby-step giant-step algorithm on human identification protcols. Under this attack, the achievable security of some of the best candidates for human identification protocols in the literature is further reduced. We show that our protocol preserves similar usability while achieves better security than these protocols. A comprehensive security analysis is provided which suggests parameters guaranteeing desired levels of security.

Secure sketches are useful in extending cryptographic schemes to biometric data since they allow recovery of fuzzy secrets under inevitable noise. In practice, secrets derived from biometric data are seldom used alone, but typically employed in a multi-factor or a multimodality setting where multiple secrets with different roles and limitations are used together. To handle multiple secrets, we can generate a sketch for each secret independently and simply concatenate them. Alternatively, we can “mix” the secrets and individual sketches, for example, by taking the first secret as the key to encrypt the sketches of all other secrets. Hence, it is interesting to investigate how the secrets are to be mixed so as to cater for different requirements of individual secrets. We found that, by appropriate mixing, entropy loss on more important secrets (e.g., biometrics) can be “diverted” to less important ones (e.g., password or PIN), thus providing more protection to the former. On the other hand, we found that mixing may not be advisable if the amount of randomness invested in sketch construction is large, or the sketch contains high redundancy, or all secrets are of the same importance. Our analysis provides useful insights and guidelines in the applications of secure sketches in biometric systems.

We look at the problem of designing Message Recognition Protocols (MRP) and note that all proposals available in the literature have relied on security proofs which hold in the random oracle model or are based on non-standard assumptions.

Incorporating random coins, we propose a new MRP using a pseudorandom function

F

and prove its security based on new assumptions. Then, we show that these new assumptions are equivalent to the standard notions of preimage resistance, second preimage resistance, and existential unforgeability given that

F

is a pseudorandom function.

Privacy-preserving techniques are increasingly important in our highly computerized society where privacy is both precious and elusive. Affiliation-Hiding Authenticated Key Exchange (AH-AKE) protocols offer an appealing service: authenticated key agreement coupled with privacy of group memberships of protocol participants. This type of service is essential in privacy-conscious p2p systems, mobile ad hoc networks and social networking applications. Prior work has succeeded in constructing a number of secure and efficient AH-AKE protocols which all assume full trust in the Group Authority (GA) — the entity that sets up the group as well as registers and (optionally) revokes members. In this paper, we argue that, for many anticipated application scenarios, the trusted GA model should be relaxed to allow for certain types of malicious behavior. We examine the consequences of malicious GAs and explore the design of stronger AH-AKE protocols that withstand GA attacks. Our results demonstrate that such protocols are both feasible and practical.

Affiliation-Hiding Authenticated Key Exchange (AH-AKE) protocols enable two distrusting users, being in possession of membership credentials for some group, to establish a secure session key without leaking any information about this group to non-members. In practice, users might be members of several groups, and such protocols must be able to generate session keys between users who have one or more groups in common. Finding efficient solutions for this

group discovery

problem has been considered an open research problem, inherent to the practical deployment of these protocols.

We show how to solve the privacy-preserving group discovery problem with

linear

computational and communication complexity, namely

O

(

n

) complexity where

n

is the number of groups per user. Our generic solution is based on a new primitive —

Index-Hiding Message Encoding (IHME)

, for which we provide definitions and an unconditionally secure construction. Additionally, we update the syntax and the security model of AH-AKE protocols to allow multiple input groups per participant and session. Furthermore, we design a concrete multi-group AH-AKE protocol by applying IHME to a state-of-the-art single-group scheme.

Assume that a client outsources his database to a remote storage-provider (the server), so that for privacy reasons, the client’s database is encrypted by his secret key. During a PIR-writing protocol, the client updates one element of the encrypted database without revealing to the semi-honest server which element was updated and, of course, to which value. The best previous PIR-writing protocols had square-root communication complexity. In this paper, we propose two new PIR-writing protocols. The first one can be based on (say) the Damgård-Jurik additively homomorphic public-key cryptosystem, and it has (amortized) polylogarithmic communication for a limited number of updates. The second one is based on a fully-homomorphic public-key cryptosystem, a much stronger primitive, but it achieves optimal logarithmic communication.

We introduce WORM-ORAM, a first mechanism that combines Oblivious RAM (ORAM) access privacy and data confidentiality with Write Once Read Many (WORM) regulatory data retention guarantees. Clients can outsource their database to a server with full confidentiality and data access privacy, and, for data retention, the server ensures client access WORM semantics. In general

simple confidentiality

and

WORM

assurances are easily achievable e.g., via an encrypted outsourced data repository with server-enforced read-only access to existing records (albeit encrypted). However, this becomes hard when also

access privacy

is to be ensured – when client access patterns are necessarily hidden and the server cannot enforce access control directly. WORM-ORAM overcomes this by deploying a set of zero-knowledge proofs to convince the server that all stages of the protocol are WORM-compliant.

Recently, there have been several attempts in establishing formal RFID privacy models in the literature. These models mainly fall into two categories: one based on the notion of indistinguishability of two RFID tags, denoted as

ind

-privacy, and the other based on the unpredictability of the output of an RFID protocol, denoted as

unp

-privacy. Very recently, at CCS’09, Ma et al. proposed a modified

unp

-privacy model, referred to as

unp

′

-privacy. In this paper, we first revisit the existing RFID privacy models and point out their limitations. We then propose a new RFID privacy model, denoted as

unp

*

-privacy, based on the indistinguishability of a real tag and a virtual tag. We provide justification for the new model and formally clarify its relationship with

ind

-privacy model. Finally, we modify Ma et al.’s 2-round RFID protocol to a 3-round mutual authentication RFID protocol and prove that it is of

unp

*

-privacy.

RFID systems have become increasingly popular and are already used in many real-life applications. Although very useful, RFIDs also introduce privacy risks since they carry identifying information that can be traced. Hence, several RFID privacy models have been proposed. However, they are often incomparable and in part do not reflect the capabilities of real-world adversaries. Recently, Paise and Vaudenay presented a general RFID security and privacy model that abstracts and unifies most previous approaches. This model defines mutual authentication (between the RFID tag and reader) and several privacy notions that capture adversaries with different tag corruption behavior and capabilities.

In this paper, we revisit the model proposed by Paise and Vaudenay and investigate some subtle issues such as tag corruption aspects. We show that in their formal definitions tag corruption discloses the temporary memory of tags and leads to the impossibility of achieving both mutual authentication and any reasonable notion of RFID privacy in their model. Moreover, we show that the strongest privacy notion (narrow-strong privacy) cannot be achieved simultaneously with reader authentication even if the adversary is not capable of corrupting a tag during the protocol execution.

Although our results are shown on the privacy definition by Paise and Vaudenay, they give insight to the difficulties of setting up a mature security and privacy model for RFID systems that aims at fulfilling the sophisticated requirements of real-life applications.

Botnets have become a major threat in cyberspace. In order to effectively combat botnets, we need to understand a botnet’s Command-and-Control (C&C), which is challenging because C&C strategies and methods evolve rapidly. Very recently, botmasters have begun to exploit social network websites (e.g.,

Twitter.com

) as their C&C infrastructures, which turns out to be quite stealthy because it is hard to distinguish the C&C activities from the normal social networking traffic. In this paper, we study the problem of using social networks as botnet C&C infrastructures. Treating as a starting point the current generation of social network-based botnet C&C, we envision the evolution of such C&C methods and explore social networks-based countermeasures.

We propose COP, a client-side system for protecting children’s online privacy and empowering parental control over children’s information disclosure with little manual effort. COP is compliant with the Children’s Online Privacy Protection Act (COPPA) in the United States and it implements acquisition of parental consent before any private information submitted online by children, e.g., registration to a Web service. Instead of restricting access to certain Web services or blocking sensitive data from websites, COP employs perturbation techniques over personal data with the goal of concealing the sensitive information while providing certain usability of the data to the websites. We address several challenges in the implementation of COP, e.g., perturbation of different types of data, parsing user input and retaining transparency to children without obstructing their normal Web surfing activities. We apply COP in registrations to 23 most popular websites. The results indicate COP’s effectiveness as a privacy protection tool. We also discuss some potential security attacks against COP’s design and provide our countermeasures.

Web advertisers prefer the cost-per-action (CPA) advertisement model whereby an advertiser pays a web publisher according to the actual amount of transactions, rather than the volume of advertisement clicks. The main obstacle for a wide deployment of this model is the deflation fraud. Namely, a dishonest advertiser under-reports the transaction count in order to discharge less. In this paper, we present a mechanism to detect such a fraud using a hybrid of cryptography and probability tools. With the assistance from a small number of users, the publisher can detect deflation fraud with a success probability growing exponentially with the fraud amount, and can estimate the amount of frauds. Our scheme is amiable to both the advertiser and the users because the existing transaction model remains unchanged. It is also efficient and scalable as the incurred communication, computation and storage costs are independent of the number of transactions.