Multisigning—a protocol for robust multiple party digital signatures

Embodiments describe a system and/or method for multiple party digital signatures. According to a first aspect a method comprises establishing a first validity range for a first key, establishing a first validity range for at least a second key, and determining if the validity range of the first key overlaps the first validity range of the at least a second key. A certificate is signed with the first validity range of the first key and the first validity range of the at least a second key if the validity ranges overlap. According to another embodiment, signage of the certificate is refused if the first validity range of the first key does not overlap with the first validity range of the at least a second key.

BACKGROUND

The following description relates generally to data protection and more particularly to multiple party digital signatures.

When a mobile device downloads data (or has data pushed to it in some fashion), it makes an assessment of such data's trustworthiness. This is particularly important for executable data or code, for example. Conversely, if an attacker can convince a device that malicious data is trustworthy such attacker has a way of subverting the device's integrity.

The creation of digital signatures by use of public key techniques is typically utilized to ensure trustworthiness of data. Typically, a private key is used to generate a signature, the authenticity of which may then be verified by using the conjugate public key. Public keys are commonly transmitted and stored in certificates, which bear the key itself and associated validity and policy meta-information, and which are signed by a higher order certification authority. The public key of each certification authority may also be stored in a certificate, thereby implying a chain of trust and a certification hierarchy.

A private key is compromised whenever it is disclosed to unauthorized parties or used in an unauthorized way. Once a key is compromised, the chain of trust is broken. Additionally, a private key may be lost, and therefore rendered unusable. In both scenarios, the key should be revoked, and a new key generated.

If a single key is used to sign blocks of data, then a single compromise will allow an attacker to exploit the system. If the signer becomes aware of the compromise, then the key may be revoked. However, there are isolated environments (such as bootstrap loaders) that may not have real-time access to certificate revocation information. Furthermore, if the compromise occurs because the signer has “turned rogue,” there is no effective countermeasure.

Once a mobile device has been compromised, it may not, or it may be difficult to, be returned to a trustworthy state without physical access to the device. In the case of cell phones, for example, the cost of recalling devices after a widespread security breach is immense. Furthermore, the attacker may be in physical possession of the device and thus has no motivation to return the device to a trustworthy state.

Therefore, a high-level assurance of the trustworthiness of data on a mobile device, at not only download time but also whenever it is used, is needed. While contemporary digital signature techniques go some way to solving this problem, they do not provide the necessary assurance under certain conditions. For example, when a mobile device is booting it has no access to a network and hence no access to revocation information, however the integrity of the bootstrap mechanism is fundamental.

In addition, there are multiple legitimate stakeholders involved in determining what data should be trusted by a mobile device. Assurance mechanisms need to account for multiple authorities, and furthermore account for the case where an authority acts improperly.

SUMMARY

The following presents a simplified summary of one or more embodiments in order to provide a basic understanding of some aspects of such embodiments. This summary is not an extensive overview of the one or more embodiments, and is intended to neither identify key or critical elements of the embodiments nor delineate the scope of such embodiments. Its sole purpose is to present some concepts of the described embodiments in a simplified form as a prelude to the more detailed description that is presented later.

According to an aspect of the invention is a method of verifying multiple party digital signatures. The method includes signing a block of data by multiple parties, verifying the block of data with a correct number of verified signatures, and determining if the number of verified signatures satisfies a verification policy.

GLOSSARY OF TERMS

Blob—Refers to a block of data to be signed.

Certificate—A public key and associated annotations, signed by a certification authority.

Compromise—Refers to unauthorized use, or potential unauthorized use, of a private key.

Digital Signature—A unique digest of a blob, computed using the private key of the signer.

Multisigning—A protocol whereby multiple parties independently sign a blob in such a way that the blob can be verified without certificate revocation information.

OpenPGP—The web of trust public key certificate standard.

Private Key—Refers to a secret half of a public key pair, typically used to generate signatures.

Public Key—Refers to a publishable half of a public key pair, typically used to verify signatures.

Revocation—Refers to a notification that a key is no longer to be trusted.

Validity Range—The contiguous time frame for which a certificate is nominally valid.

X.509—A hierarchical public key certificate standard.

DETAILED DESCRIPTION

With reference now to the drawings,FIG. 1is a block diagram of a system100that provides a digital signature. A digital signature is a way of authenticating that data is received from the true originator and that the data is trustworthy. System100includes a user device102and a certificate authority104. User device102may be implemented in a portable device, a portable phone, a personal data assistant, a personal computer (desktop or laptop), a moving vehicle (autos, trucks, ships, etc.), or other electronic devices. Certificate authority104may be implemented by entities such as banks, cellular service providers, security service providers, or other trusted third parties. Although only one certificate authority104is shown, it should be appreciated that there may be one or more certificate authorities.

User device102includes a processor106that generates cryptographic keys, a publisher component108that publishes a certificate112, and an annotation component110that annotates the published certificate with necessary information. Cryptographic keys include a private key and a corresponding public key. The private key is usually retained in user device102to maintain such key's secrecy while the public key is published and utilized for verification purposes and stored in certificates.

Publish component108allows the owner of user device102to publish a certificate112containing an associated public key114. Public-key certificate112is a digitally signed statement that certifies or validates that the public key belongs to the sender and associates a level of confidence or trustworthiness to the information. Certificate authority104may also sign certificate112.

Annotation component110annotates public key114with a start timestamp and an end timestamp, or validity range. Public key114is valid only during such validity range. It is not necessary that the timestamps be related to real time, although they may be. The validity range could be a numbered sequence or a range that is generated by a hash function. The range can be temporal-based, numerical-based, or based on any other criteria, provided there is a system and/or method for determining when the validity range starts and ends. For example, time can be utilized as part of the X.590 standard. The X.509 standard defines the information that can go into a particular certificate and describes the data format of the certificate. It should be noted that the various embodiments described herein could be implemented by a plurality of public key certification standards, including X.509 and OpenPGP, which support validity ranges and revocation mechanisms.

User device102can generate a sequence of keys and certificates for a given purpose over time. Successive keys replace those keys that have expired or that have been revoked. However, each key should have a validity range that is disjoint from the validity range of each preceding and successive key. In other word, no validity ranges should overlap. For example, a first validity range starts on January 1 and ends on January 7, if a second validity range starts on January 8 and ends on January 13 they are disjoint. However, if the second validity range begins on January 6, it is invalid and cannot be associated with the first validity range because the validity ranges are joined.

Each key is only to be utilized for the pre-determined lifetime (validity range). This allows for regular expiration of keys and is generally unrelated to a timestamp of certificate112. The validity range of the key does not have to be contained in certificate112, although it can be included in certificate112. Additionally, validity range of the key may not be determinable from the timestamp of the certificate.

If a private key, stored in user device102, is expired, it should be destroyed to reduce the chances of the old keys being compromised. New signing keys are generated to replace expired keys and can be created on or before the time of expiration.

Referring now toFIG. 2, a block diagram of a multiple party digital signature system200is illustrated. System200includes a first user device202and a second user device204and a certificate206signed by first and second user devices202and204and/or a certificate authority (not shown). While only two user devices are shown, it will be understood by those skilled in the art that there may be more than two devices. Each user device includes respective processors208and214that generate cryptographic keys, publish components210and216that publish a certificate for multiple party digital signatures, and annotate components212and218that annotate information to the certificate.

Multiple parties, through respective user devices202and204, digitally sign certificate206to allow for an assessment of trustworthiness of data when that data is to be downloaded or utilized by a user. The certificate published by respective user devices202and204contain respective public keys220and222with a validity range that includes a start timestamp and an end timestamp. The timestamp associated with public key220does not have to be identical to the time stamp of public key222. However, each respective validity range should overlap. For example, if public key220has a validity range from Monday to Wednesday and public key222has a validity range from Monday to Thursday, there is sufficient overlap. However, if public key222has a validity range from Thursday to Friday, the overlap is not sufficient.

There are several ways a certificate can be signed with more than one signature, known as multisigning. A few multisigning techniques are cosigning, countersigning, and cross signing and will be briefly discussed.

The most basic form of multisigning is cosigning. In cosigning, there is a signature of first key “A” with a message on it and a signature of second key “B” with a message on it. When cosigning is used, each party is independent, that is, each party is not aware that the other party is signing the certificate.
SigA(m),SigB(m)

Another type of multisigning is countersigning. This is typically used on digital authorization services, such as a commercial service. There is a signature of A with a message, and a signature of B with a message, off the signature and message of A. Essentially, B is attesting to the fact that A signed the message.
SigA(m),SigB(m,SigA(m))

Cross signing is another type of multisigning where there is a signature of A with a message and an indicator that B should also sign. Essentially, what it indicates is that A is going to sign the message and knows it should also be signed by B. A is further concluding that A's signature is optional.
SigA(m,[A],B)

B would also sign a signature, similar to that described with reference to A above, concluding B's signature is optional.
SigA(m,A,[B])

While A does not have to include [A] and B does not have to include [B], including such indications provides that the actual content both A and B sign are the same. Having the same content is a verification issue. If A and B do not include themselves, the respective signatures would be as indicated below.
SigA(m,B)
SigA(m,A)

While the above are examples of multisigning, a plurality of multiple party signature schemes can be utilized according to the embodiments disclosed herein.

Each blob, or block of data, is signed by multiple parties, thereby creating a signature set of <n> signatures. Each signature is independent and may be generated in any order, or even at a substantially similar time.

To verify a blob, each <n> signature is independently verified by using the appropriate certificate. The number of correctly verified signatures is defined as <v>, where <v> is greater than or equal to zero and less then or equal to <n>:
0≦<v>≦<n>

The minimum number of correct signatures that will satisfy the verification policy is defined as <m>. That is, not every verified signature, <v>, need to be retrieved to satisfy verification policy. Verification succeeds when <v> is greater than or equal to <m> guaranteeing that at least <m> signers have independently verified the blob.
<v>≧<m>

Additionally the intersection of the valid time windows of the <v> certificates is a non-zero range. This guarantees that at the time each signature was generated, no revocation notice of one or more of the other keys had been received by the signer or user device. In some embodiments, the verification of the intersection of the valid time windows of the <v> certificates is performed by a verifier (e.g., verifier device).

In a simple case where the minimum number of correct signatures that will satisfy the verification policy, <m>, is equal to the number of signatures that signed the blob, <n>, all signatures need to be correct. This is expressed as:
<m>=<n>

This provides maximal assurance. However, it also means that a single revocation prevents further signing until the <n> signers have regenerated keys. More generally, the condition is less stringent when the minimum number of correct signatures that will satisfy the verification policy, <m>, is less than the number of signatures that signed the blob, <n>.
<m><<n>

In this case, the protocol permits there to be a number of contemporaneous revocations equal to the number of signatures <n> minus the number of <m> correct signatures without preventing further signing from taking place.
(<n>−<m>)

Verification does not necessitate access to a particular type of time keeping, as the time comparisons are relative and the timestamps are against an arbitrary time base. However, a verifier (e.g., verifier device) may choose to apply real time constraints as part of its policy if the timestamps are defined to be relative to real time, or if additional time information is carried in the certificate.

Whenever a key is revoked, the signers should regenerate new keys that do not overlap with the revoked key, known as compromise recovery. For example, at substantially the same time as there is one more signer than the total number of signatures, <n>, minus the number of <m> signers, overlapping keys are revoked, and a new key is generated to allow signing to continue.
(<n>−<m>+1)

Given that the validity range of new keys should not overlap with the validity range of a revoked key, the certificate can be generated with an inception timestamp that indicates a start and end time that takes place in the future. In general, this is not a problem as timestamps are treated by this protocol as purely relative values. That is to say, the validity range can be based upon a plurality of values, provided there is a mechanism to determine the start and end of the range and if the relative validity ranges of the multiple signers overlap.

FIG. 3is an illustration of validity ranges associated with respective keys. Line300is a time representation of a validity range, and real time is used for simplicity of illustration only and not by way of limitation. Two signers illustrated as “A” and “B,” with A's keys represented above line300and B's keys represented below line300.

A has five validity ranges represented as keys KA-0, KA-1, KA-2, KA-3, and KA-4. B has three validity ranges represented as keys KB-0, KB-1, and KB-2. As illustrated, KA-0and KB-0, have substantially similar validity ranges with a start timestamp at302and an end timestamp at304. Thus, the respective validity ranges KA-0and K13-0are overlapping and can generate a valid signature of the certificate during that validity range.

The respective validity ranges KA-1and KB-1are similarly sufficiently overlapping. KB-1has a start timestamp306that is before KA-1's start timestamp308. However, KA-1's end timestamp310is before KB-1's end timestamp312. However, because KB-1's validity range sufficiently overlaps KA-1's validity range it allows for generation of a valid signature. Thus, the validity ranges do not have to be equally overlapping or have the same start timestamp and same end timestamp to be valid.

KA-2and KB-2illustrate partially overlapping validity ranges. KB-2has a start timestamp314that is before KA-2's start timestamp316and KB-2's end timestamp318expires before KA-2's end time stamp320. The overlapping range in which a valid signature can be generated is between KA-2's start time stamp316and KB-2's end time stamp318.

KA-3and KB-3illustrate non-overlapping validity ranges. KA-3has a start time stamp322and an end time stamp324that are distinct from KB-3's start time stamp326and end time stamp328. Thus, KA-3and KB-3are not overlapping and generation of a valid signature for A and/or B is not possible during validity ranges KA-3and KB-3.

It should be noted that the validity ranges should be disjoint. For example, validity ranges KA-0, KA-1and KA-2are disjoint. However, validity ranges KA-4and KA-5are not disjoint. That is the validity ranges KA-4and KA-5overlap at330. Thus, A cannot validly sign a certificate during validity ranges KA-4and KA-5.

Since the validity range of multiple party signatures should overlap during the same validity range, signatures that do not overlap cannot create a valid signature. For example, KA-0cannot create a valid signature with KB-1and/or KB-2. Likewise, KB-1cannot create a valid signature with KA-0and/or KA-2. The other keys operate in a similar fashion.

Referring now toFIG. 4a certification hierarchy400is illustrated. Certification hierarchy400includes parent key KA-0and child keys KA-1, KA-2, and KA-3contained within the validity range of parent key KA-0. While a certification hierarchy is in force, the validity range of each child key KA-1, KA-2, and KA-3is entirely contained in the validity range of its parent KA-0. Child keys KA-1, KA-2, and KA-3that do not meet this condition are not trusted. A compromise at any point in the hierarchy necessitates the revocation and regeneration of that key. The new key, as per a key management criteria, is assigned a validity range that does not overlap with the previous key. Thus, the child keys are also recursively revoked and regenerated.

It can be argued that the more often a key is used, the more it is exposed to potential compromise. Therefore, a certification hierarchy of several levels can be utilized when implementing this protocol. Keys at a higher level are longer lived, while keys at lower levels are regenerated more frequently. For example, a three level hierarchy may use root keys with a lifetime of one decade, intermediate keys with an intermediate level lifetime of one year, and interval duration keys with a lower level lifetime of one month. In this case, the maximum time an undetected compromise of a lower level key (arguably the most exposed) could be exploited for is one month.

With continuing reference toFIG. 4, an entity, A, has validity ranges KA-0, KA-1, KA-2and KA-3represented above line400. An entity, B, has validity ranges KB-0, KB-1, KB-2and KB-3represented below line400. It should be appreciated that line400represents a value that can be used for validity range purposes and by way of illustration and not limitation, is described as a time line. For simplicity purposes, the validity ranges of A and B are shown as encompassing the same range, however, it should be appreciated that the validity ranges may be different, provided they sufficiently overlap.

Entity A of the hierarchy400includes a root key KA-0, an intermediate key KA-1, and interval duration keys KA-2and KA-3. Similarly, B has a root key KB-0, an intermediate key KB-1, and interval duration keys KB-2and KB-3. The root keys and intermediate keys can also reside at a server when various computations are performed. Root keys KA-0and KB-0are at respective primary levels and associated with respective certificate authorities. Root keys KA-0and KB-0can be valid for a substantially indefinite range of time, as illustrated at start timestamp402and end timestamp404.

Validity ranges KA-1and KB-1are of a lesser duration and have start timestamp406and end timestamp408. KA-1and KB-1are sufficiently included in the validity range of KA-0and KB-0. That is to say, the validity ranges of KA-0and KB-0are longer in duration than the validity ranges of KA-1and KB-1. For example, root keys KA-0and KB-0can have a validity range of ten years and intermediate keys KA-1and KB-1can have validity ranges of one year, for example.

The validity ranges of duration keys KA-2, KA-3, KB-2, and KB-3fall within respective validity ranges of KA-1and KB-1. The duration keys can have a validity range less than the validity range of intermediate keys, for example, one week. Thus, because they are included in the validity range of both the intermediate key(s) and root(s), the certification hierarchy is satisfied.

Certificate hierarchy can be supported by various standards, including X.509 and OpenPGP. However, the embodiments disclosed herein can be implemented utilizing a plurality of hierarchy standards and is not limited to X.509 and/or OpenPGP.

A web of trust is more general than a strict certification hierarchy. In general, each certificate can have more than one certifier, and the trust relationships form a directed graph. This protocol can be implemented with a web of trust by applying the constraint that the validity range of certificates are entirely contained by those of its certifiers. This implies that the trust web is acyclical unless the validity ranges of the keys are congruent. OpenPGP is an example of one standard that supports webs of trust and can be utilizing according to one or more of the disclosed embodiments.

Referring now toFIG. 5a hierarchy protocol for multiple party signatures is illustrated. The hierarchy is discussed in relation to a first entity, A, that has a root key KA-0, intermediate key KA-1, and three duration keys KA-2, KA-3, and KA-4. If a certification hierarchy is in force, the validity range of each certificate KA-2and KA-3is entirely contained in the validity range of its parent KA-1and KA-0, and is thus valid. However, the certificate of key KA-4is outside the hierarchy of parent key KA-1and thus, is not a valid certificate under a hierarchy protocol. It should be appreciated that the range from 502 to 504 can be verified by key KA-1itself and/or a duration key.

While the figures and examples discussed herein refer to two sets of keys and/or three levels of keys in a certificate hierarchy, it should be appreciated that there may be more than two sets of keys and more (or less) than three key levels.

Referring toFIGS. 6-10, methodologies relating to multiple party signatures are illustrated. While, for purposes of simplicity of explanation, the methodologies are shown and described as a series of acts, it is to be understood and appreciated that the methodologies are not limited by the order of acts, as some acts may, in accordance with these methodologies, occur in different orders and/or concurrently with other acts from that shown and described herein. For example, those skilled in the art will understand and appreciate that a methodology could alternatively be represented as a series of interrelated states or events, such as in a state diagram. Moreover, not all illustrated acts may be required to implement the following methodologies.

Each signer holds a private key, and publishes a certificate containing the associated public key. Each certificate annotates its key with a start timestamp and an end timestamp. The key is generally valid only in the range between these two instances, known as the validity range.

Signers typically generate sequences of keys and certificates for a given purpose over time, with successive keys replacing those expired or revoked. There is no need for the timestamps to be related to real time (although they may be). However, keys in a sequence should possess disjoint validity ranges. In other words, none of the validity ranges should overlap. The signers should cooperate when generating keys to ensure that the set of keys used contemporaneously do possess overlapping validity ranges.

Each key is used only for a pre-determined lifetime and keys are regularly expired. Note that the validity range of the key is, in general, unrelated to the certificate's end timestamp. Validity range information may or may not be carried in the certificate and may or may not be determinable from the end timestamp. Expired private keys should be destroyed, to reduce the likelihood of old keys being compromised. New signing keys should be generated to replace expired keys; this can happen on or before the end of the validity range.

If a key is compromised or lost, its owner notifies the other signers that the key is revoked. Notification may be by a plurality of mechanisms; a certificate revocation list would be typical. If a certificate revocation is received (and verified), the signer should treat the other key(s) with a validity range overlapping the revoked key as expired. Corresponding private key(s) should be consequently destroyed. This synchronization guarantees that overlapping keys are only used for signing in the absence of revocation notices.

FIG. 6is a flow diagraph of a methodology600for creating a valid signature authentication range for different keys for use with multiple party signatures. It should be appreciated that while the flow diagram is discussed with regard to a first key, A, and a second key, B, the methodology supports more than two keys and is not limited as such.

At602, a validity range is established with regard to key A. The validity range has both a start timestamp and an end timestamp. A plurality of means can be utilized to establish the validity range and is not limited to a duration of time, although it is easy to think of a validity range in terms of time. Key A has a public key and an associated private key. This validity range is associated with the public key of a user device and a certificate is signed by such public key.

At least one other party or entity creates key B, at604, having a public key and a private key. A validity range is established for the public key of key B with both a start timestamp and an end timestamp. A certificate is signed by B's public key and associated validity range.

In order for the certificate that is signed by both A and B to be valid, the respective validity ranges should overlap. A determination is made at606whether there is sufficient overlap. That is to say, both validity ranges encompass the same range allowing for toggling or staggering of the start timestamps and end timestamps. Thus, the validity ranges of the keys that sign the certificate do not have to be equal or have the same start timestamp and end timestamp.

If the validity ranges overlap, at608the certificate and associated digital signatures are deemed trustworthy. If, however, there is not sufficient overlap of the validity ranges, the certificate is not trustworthy and at610, it is not validated with trustworthy digital signatures.

FIG. 7is a flow diagram of a methodology700for generating consecutive validity ranges for a plurality of keys for use with multiple party signatures. At702validity ranges for at least two entities are created with sufficient overlap, as determined by a methodology, such as the one illustrated and described with regard toFIG. 6. At704, a second validity range is established. This second validity range is disjoined from the respective first validity ranges. That is to say, there can be no overlap between first validity range and second validity range. It should be noted that a second validity range is created for both entities to avoid, for example, a first validity range of the first entity overlapping both a first and a second validity range of the second entity. If the first validity range of the first entity is overlapping both validity ranges of the second entity and one of the keys is compromised, there is a greater opportunity for the system to be exploited.

At706a determination is made whether the second validity ranges of both entities overlap, and can be determined in the same manner as the overlap of the first validity ranges are established. If there is not sufficient overlap, access and signature of the certificate is denied at708.

If sufficient overlap is determined at706, access and signature of the certificate is allowed. It should be noted that subsequent validity ranges (e.g. third, fourth, fifth, . . . ) can be established and verified in the same manner as that illustrated and described with reference to first and second validity ranges.

FIG. 8is a flow diagram of a methodology800for establishing consecutive validity ranges for a single key for use with multiple party signatures. A first and second validity range associated with a first public key is created at802. The first and second validity ranges have a start timestamp and an end time stamp. While the creation of the first and second validity ranges is shown at a similar time, it should be understood that the creation of the second (and subsequent) validity ranges can be created before or at a substantially similar time as a validity range expires. That is to say, the second validity range should be created at or before the end timestamp of the first validity range.

At804, a determination is made whether the first and second validity ranges are disjoint with separate and distinct validity ranges. That is to say, the first and second validity ranges associated with the same public key cannot occur or exist during the same validity range or portion(s) thereof. This may necessitate generating a certificate with an inception timestamp in the future. This is not a problem since timestamps are treated as purely relative values.

If at804it is determined that the validity ranges are not disjoint, the certificate, represented by the second validity range, is not associated with a digital signature of this user. If the validity ranges are disjoint, the certificate is digitally signed and can be utilized for verification. If there is overlapping, those overlapping keys are revoked and new keys are regenerated before signing can continue.

At810, a third, or subsequent validity ranges (e.g. fourth, fifth, sixth . . . ) are created either at or before the time the previous validity range expires. The subsequent validity ranges should be disjoint from previous validity ranges of the preceding validity ranges.

FIG. 9is a flow diagram of a hierarchy methodology900for multiple party signatures. A root key is created at902, this root key can be stored on both a user device and on a server. The root key contains a start timestamp and an end timestamp. The root key has a longer validity range and can be represented by a number of years, for example.

An intermediate key is created at904, the intermediate key can be stored both on a user device and on a server. The intermediate key has an associated start timestamp and end timestamp. According to hierarchy protocol, the validity range of the intermediate key should be completely contained in the validity range of the root key. A certificate generated by intermediate key that is not within the validity range of the root key, cannot be trusted. Since the intermediate key has a validity range shorter than that of the root key, it can be represented, for example, by month(s).

A duration key at a third level is created at906. Duration key has a start timestamp and an end timestamp, which should be contained within the validity ranges of both the root key and the intermediate key. A hierarchy having several layers helps to mitigate potential compromises of the key's integrity. The duration key has a short, expendable time range, and for purposes of illustration, can be represented by a week. Thus, if the duration key is compromised, the longest that this lower level key (and potentially the most exposed) can be compromised and exploited is for is one week.

At908, a determination is made whether the root key validity range contains the validity range(s) of the intermediate key(s) and if the intermediate key(s) validity range(s) contain the validity range(s) of the duration key(s). If no, then at910keys with validity ranges outside the hierarchy cannot be trusted. At this point, that key is revoked and a new key is generated. However, if the determination at908is yes, the key can be trusted and at912is used to digitally sign certificates.

FIG. 10is a flow diagram of a methodology1000for verification of multiple party signatures. At1002, a blob is signed by multiple parties creating a signature set of <n> signatures. Each signature is generated independently, in any order, and may be generated at a substantially similar time.

At1004the blob is verified by <v> signatures where <v> is the number of correctly verified signatures. Each <v> signature is to be independently verified by using the appropriate certificate. The correct number of signatures can be a number greater than zero and less than or equal to <n>.
0≦<v>≦<n>

A determination is made at1006whether there are a minimum number of correct signatures <m> that satisfy the verification policy. That is to say, the verification succeeds if the number of correctly verified signatures <v> is equal to, or more than, the minimum number of correct signatures <m> necessary to verify the certificate.
<v>≧<m>

Additionally, for verification to succeed at the time each signature was generated the signer should not have been notified of revocation of one or more of the other keys. If the above two conditions are satisfied, at1008, the certificate is trusted. If the conditions are not satisfied, the certificate is not trusted at1010.

FIG. 11shows an exemplary wireless communication system1100. The wireless communication system1100depicts one base station and one terminal for sake of brevity. However, it is to be appreciated that the system can include more than one base station and/or more than one terminal, wherein additional base stations and/or terminals can be substantially similar or different for the exemplary base station and terminal described below. In addition, it is to be appreciated that the base station and/or the terminal can employ the systems (FIGS. 1-3) and/or methods (FIGS. 6-10) described herein to facilitate wireless communication there between. Although the system is primarily described within the context of an orthogonal frequency multiplex modulation system, it is to be appreciated that any suitable protocol/system (e.g., code division multiplex access (CDMA)) may be employed in connection with the various embodiments described herein.

Referring now toFIG. 11, on a downlink, at access point1105, a transmit (TX) data processor1110receives, formats, codes, interleaves, and modulates (or symbol maps) traffic data and provides modulation symbols (“data symbols”). An OFDM modulator1115receives and processes the data symbols and pilot symbols and provides a stream of OFDM symbols. An OFDM modulator1120multiplexes data and pilot symbols on the proper subbands, provides a signal value of zero for each unused subband, and obtains a set of N transmit symbols for the N subbands for each OFDM symbol period. Each transmit symbol may be a data symbol, a pilot symbol, or a signal value of zero. The pilot symbols may be sent continuously in each OFDM symbol period. Alternatively, the pilot symbols may be time division multiplexed (TDM), frequency division multiplexed (FDM), or code division multiplexed (CDM). OFDM modulator1120can transform each set of N transmit symbols to the time domain using an N-point IFFT to obtain a “transformed” symbol that contains N time-domain chips. OFDM modulator1120typically repeats a portion of each transformed symbol to obtain a corresponding OFDM symbol. The repeated portion is known as a cyclic prefix and is used to combat delay spread in the wireless channel.

A transmitter unit (TMTR)1120receives and converts the stream of OFDM symbols into one or more analog signals and further conditions (e.g., amplifies, filters, and frequency upconverts) the analog signals to generate a downlink signal suitable for transmission over the wireless channel. The downlink signal is then transmitted through an antenna1125to the terminals. At terminal1130, an antenna1135receives the downlink signal and provides a received signal to a receiver unit (RCVR)1140. Receiver unit1140conditions (e.g., filters, amplifies, and frequency downconverts) the received signal and digitizes the conditioned signal to obtain samples. An OFDM demodulator1145removes the cyclic prefix appended to each OFDM symbol, transforms each received transformed symbol to the frequency domain using an N-point FFT, obtains N received symbols for the N subbands for each OFDM symbol period, and provides received pilot symbols to a processor1150for channel estimation. OFDM demodulator1145further receives a frequency response estimate for the downlink from processor1150, performs data demodulation on the received data symbols to obtain data symbol estimates (which are estimates of the transmitted data symbols), and provides the data symbol estimates to an RX data processor1155, which demodulates (i.e., symbol demaps), deinterleaves, and decodes the data symbol estimates to recover the transmitted traffic data. The processing by OFDM demodulator1145and RX data processor1155is complementary to the processing by OFDM modulator1115and TX data processor1110, respectively, at access point1100.

On the uplink, a TX data processor1160processes traffic data and provides data symbols. An OFDM modulator1165receives and multiplexes the data symbols with pilot symbols, performs OFDM modulation, and provides a stream of OFDM symbols. The pilot symbols may be transmitted on subbands that have been assigned to terminal1130for pilot transmission, where the number of pilot subbands for the uplink may be the same or different from the number of pilot subbands for the downlink. A transmitter unit1170then receives and processes the stream of OFDM symbols to generate an uplink signal, which is transmitted by the antenna1135to the access point1110.

At access point1110, the uplink signal from terminal1130is received by the antenna1125and processed by a receiver unit1175to obtain samples. An OFDM demodulator1180then processes the samples and provides received pilot symbols and data symbol estimates for the uplink. An RX data processor1185processes the data symbol estimates to recover the traffic data transmitted by terminal1135. A processor1190performs channel estimation for each active terminal transmitting on the uplink. Multiple terminals may transmit pilot concurrently on the uplink on their respective assigned sets of pilot subbands, where the pilot subband sets may be interlaced.

Processors1190and1150direct (e.g., control, coordinate, manage, etc.) operation at access point1110and terminal1135, respectively. Respective processors1190and1150can be associated with memory units (not shown) that store program codes and data. Processors1190and1150can also perform computations to derive frequency and impulse response estimates for the uplink and downlink, respectively.

For a multiple-access OFDM system (e.g., an orthogonal frequency division multiple-access (OFDMA) system), multiple terminals may transmit concurrently on the uplink. For such a system, the pilot subbands may be shared among different terminals. The channel estimation techniques may be used in cases where the pilot subbands for each terminal span the entire operating band (possibly except for the band edges). Such a pilot subband structure would be desirable to obtain frequency diversity for each terminal. The techniques described herein may be implemented by various means. For example, these techniques may be implemented in hardware, software, or a combination thereof. For a hardware implementation, the processing units used for channel estimation may be implemented within one or more application specific integrated circuits (ASICs), digital signal processors (DSPs), digital signal processing devices (DSPDs), programmable logic devices (PLDs), field programmable gate arrays (FPGAs), processors, controllers, micro-controllers, processors, other electronic units designed to perform the functions described herein, or a combination thereof. With software, implementation can be through modules (e.g., procedures, functions, and so on) that perform the functions described herein. The software codes may be stored in memory unit and executed by the processors1190and1150.

It is to be understood that the embodiments described herein may be implemented by hardware, software, firmware, middleware, microcode, or any combination thereof. When the systems and/or methods are implemented in software, firmware, middleware or microcode, program code or code segments, they may be stored in a machine-readable medium, such as a storage component. A code segment may represent a procedure, a function, a subprogram, a program, a routine, a subroutine, a module, a software package, a class, or any combination of instructions, data structures, or program statements. A code segment may be coupled to another code segment or a hardware circuit by passing and/or receiving information, data, arguments, parameters, or memory contents. Information, arguments, parameters, data, etc. may be passed, forwarded, or transmitted using any suitable means including memory sharing, message passing, token passing, network transmission, etc.

What has been described above includes examples of one or more embodiments. It is, of course, not possible to describe every conceivable combination of components or methodologies for purposes of describing these embodiments, but one of ordinary skill in the art may recognize that many further combinations and permutations of such embodiments are possible. Accordingly, the embodiments described herein are intended to embrace all such alterations, modifications, and variations that fall within the spirit and scope of the appended claims. Furthermore, to the extent that the term “includes” is used in either the detailed description or the claims, such term is intended to be inclusive in a manner similar to the term “comprising” as “comprising” is interpreted when employed as a transitional word in a claim.