KR20030094217A - Threshold cryptography scheme for message authentication systems - Google Patents

Abstract

In a method and apparatus for authenticating a message, the method comprises receiving at the device data indicative of a first share, constructing a key using the first share, and at least two additional shares stored in the device, And authenticating the message using the configured key.

Description

Threshold encryption architecture for message authentication system {THRESHOLD CRYPTOGRAPHY SCHEME FOR MESSAGE AUTHENTICATION SYSTEMS}

In modern electronic distribution networks, message authentication is an important goal of information security. This goal is satisfied by assuring the identity of the transmitter to the receiver of the message. Since physical protection such as sealed envelopes is not possible for messages displayed in binary sequences, digital means using encryption techniques have been developed. The main weakness of all encryption methods for message authentication is that it uses an algorithm with a fixed symmetric or public key. We describe a new key transmission scheme based on secret sharing, whereby each new message is authenticated using a new key, thereby enhancing the system's resistance to key or message attacks.

One of the four most important goals of information security is authentication. Other goals are confidence, data integrity and non-repudiation. In a communication network, some or all of these goals may need to be met.

Note that for reliability, there are applications in which information must be kept confidential. Encryption techniques provide reliability by converting data into unknown formats. This can be reversed and an entity with the correct key can recover the data.

For data integrity, the user needs to be assured that the information has not been altered in an unauthorized manner. Hashing functions that produce a short data representation are commonly used to check data integrity.

Finally, if disputes arise as a result of a party's denial of non-repudiation, such as a related electronic transaction, it can be resolved with the participation of a trusted third party acting as a judge.

There are two basic types of authentication: 'entity' authentication and 'message' authentication. Message authentication guarantees the identity of the sender of the message. Entity authentication not only guarantees the identity of the sender of the message, but also ensures the active participation of the sender of the message.

6 shows a communication channel in which two parties A and B communicate using a protocol to exchange messages. Party A is the sender of message M and Party B is the recipient. Depending on the type of communication network, Party B wants at least three pieces of information upon receipt of the message: (1) The assurance of the identity of the part that sent the message M (commonly referred to as the 'message' authentication). ), (2) evidence that the message (M) was not altered during transmission (data integrity), and (3) an indication that the party A (i.e. the sender) was active at the time the message was sent (commonly known as an 'entity' Mentioned).

As mentioned above, message authentication guarantees the identity of party A, the sender of message M. In addition, the message authentication includes evidence of data integrity, since party A cannot be the originator if message M has been changed during transmission. On the other hand, entity authentication guarantees Party B's active participation as well as Party A's identity. Sometimes the two parts need to authenticate each other that the message flows in either direction. Challenge-response protocols based on symmetric or public key structures, and zero-knowledge protocols are commonly used for mutual authentication.

While there is no guarantee that message authentication is permanent or unique, it is very useful in communications where one part (for example, Party A) is inactive during the execution of a message protocol. To pretend to be and to send a previously used message in an attempt to obtain a protocol, time variant data (e.g., sequence number, time stamp, etc.) is appended to the message (M). Can be.

Encryption processing, known as "hashing", is an integral part of the data integrity and message authentication structure. The hashing function takes a message of arbitrary finite length and produces a fixed length output. In cryptographic applications, hash values are considered to represent shorter actual messages. Hash functions can be classified into two groups: (1) unsolved hash functions (ie, messages are the only input parameters), and (2) unwrapped hash functions (ie, messages and private keys are input parameters).

Certain classes of hash functions that are not solved include Manipulation Detection Code (MDC). MDC differs in the way the message M is compressed. Some examples include: (a) a hash function based on block ciphers, (b) a hash function based on modular operations, and (c) a customized hash function.

Pulley hash functions used for message authentication are grouped under Message Authentication Code (MAC). The MAC may be custom configured, may be configured using a block cipher, or may be derived from the MDC.

The message authentication method may be classified into (a) MAC, (b) message encryption, and (c) digital signature according to a method using symmetric key or public key cryptography.

7 shows a block diagram of a message authentication method using a MAC. The message M is input into a MAC algorithm that calculates the MAC using the key K shared by both parts (i.e., the transmitter (A party) and the receiver (B party)). The party A then attaches the MAC to the message M and sends the composite signal to the party B.

8 shows a block diagram of a message authentication method using message encryption. Message encryption can be realized in two ways: symmetric key encryption and public key encryption. Using symmetric key encryption, the message M is encrypted using the symmetric key before being sent to the receiver (e.g., party B). The receiver (e.g., party B) uses a copy of the symmetric key to decrypt the message. Using public key encryption, the message M is encrypted using the public key and decrypted using the corresponding private key at the receiver. As shown in Fig. 8, under either method, the message M is input to an encryption algorithm using a (symmetric or public) key K to generate an encrypted message E _k (M).

9 shows a block diagram of a message authentication method using a digital signature. In this way, the sender (e.g., party A) uses the private key K _private to digitally sign the message M. Depending on the size of the message M, an appropriate signature algorithm can be used. The receiver (e.g., party B) is assured that message M has been generated by A because A is the only part that owns the private key.

If a static key is used for the generation of MAC, message encryption and digital message signing (ie all three message authentication types), then the security level is limited, exposing the system for decryption.

For the 'MAC' method, the symmetric key shared by the transmitter and receiver needs to be used for all messages during its lifetime. This makes the method vulnerable to intrusions for MAC forgery and key recovery. There are two possible intrusions: (1) intrusion into key space, and (2) intrusion into MAC value. If the attacker can determine the MAC key, he may generate a MAC value for any message. With a key size of 't' bits and a fixed input, the probability of finding the correct n-bit MAC is about 2- ^t . The goal of MAC forgery is either to generate a MAC for a given message, or to find a message for a given MAC without knowing the key. In the n-bit MAC algorithm, the probability of ^meeting this goal is about 2- ⁿ . In short, the effort required for violent intrusion into the MAC algorithm is at a minimum (2 ^t , 2 ⁿ ).

As for the message encryption method, the method is also vulnerable to violent intrusions. For example, in a 56 bit DES (symmetric) algorithm, the key can be determined by testing all 2 ⁵⁵ DES operations. More efficient intrusions, such as linear or differential cryptography, allow keys to be recovered with less processor time.

For the digital signature method, no public key signature algorithm has been found to be insecure. The security of public key algorithms is based on the difficulty of computing discrete algebra or factoring large numbers. Using a fixed public / private key pair, it can be exploited using the public key or signature of a message. In some applications, there is a big problem that the authenticity of the transmitter's public key requires a complex public key infrastructure.

Therefore, there is a current need for a system that provides a higher level of security but provides message authentication that does not use a fixed key.

The present invention relates to a method and system for providing message authentication. Using the concept of secret sharing, the system does not require the entire key to be sent to the receiver of the message. Instead, the key is recovered using at least one share received from the transmitter and at least two shares stored at the receiver.

1 is a block diagram illustrating a message authentication system according to a first exemplary embodiment of the present invention.

Fig. 2A is a graphical representation of the determination of an authentication key according to a first exemplary embodiment of the invention.

2b graphically illustrates a unique, non-overlapping range of allocation for each transmitter according to FIG.

Fig. 3 graphically illustrates the determination of an authentication key according to a second exemplary embodiment of the invention.

4 graphically illustrates the determination of an authentication key according to a third exemplary embodiment of the present invention.

Fig. 5 is a graphical representation of the determination of a plurality of authentication keys according to the first to third embodiments of the present invention.

6 is a block diagram showing a conventional message authentication system.

7 is a block diagram illustrating a message authentication system using a MAC.

8 is a block diagram illustrating a message authentication system using message encryption.

9 is a block diagram illustrating a message authentication system using a digital signature.

The present invention defines a method and apparatus for providing authentication of a message, the method comprising receiving data at a receiver station indicative of a first share, constructing a key using the first share and at least two additional shares. As a step, the at least two additional shares comprise a key construction step, stored at the receiver station, and authenticating a message using the configured key.

According to a first exemplary embodiment of the invention, first and second shares are used. The first and second shares are points on the Euclidean plane, and the constructing of the keys comprises calculating a Y-intercept of straight lines formed on the Euclidean plane by the first and second shares. Include.

According to a second exemplary embodiment of the invention, first, second and third shares are used. The first, second and third shares comprise calculating the Y-intercept of a parabolic curve formed on the Euclidean plane by the first, second and third shares.

According to a third exemplary embodiment of the invention, first, second, third and fourth shares are used. The first, second, third and fourth shares are points on the Euclidean plane, and the construction of the key calculates the Y-intercept of the curves formed on the Euclidean plane by the first, second, third and fourth shares. It includes a step. Typically, any number of shares can be used depending on the level of security required.

The present invention includes a message authentication system, wherein a message sent between two or more portions of the message authentication system is authenticated using a prepositioned secret sharing structure. By using a pre-deployed secret sharing structure, the security and flexibility of the message authentication system is increased (eg using different keys).

The present invention takes advantage of the application of a secret sharing scheme known as the 'threshold scheme' first developed by Adi Shamir {"How to share a secret" by Adi Shamir) (See Communications of the ACM, Vol. 22, No. 11, pp. 612-613, November 1979). A (t, n) threshold structure, such as the threshold structure proposed by Shamir, has n secrets ('share' or 'shadow') in a manner that requires at least t (≤n) pieces to reconstruct the secret. (Also called ""). A perfect threshold structure is a threshold structure in which (t-1) or fewer pieces of knowledge ('share' or 'shadow') do not provide any information about the secret.

For example, in the (2,5) threshold structure, the secret is divided into five shares, but only two of the shares are needed to reconstruct the secret. A threshold structure (2,5), such as the threshold structure described above, can be used by the bank manager to divide the custom number for the main safe into five tellers. In this manner, any two of the cashiers working together may open the safe, but not one cashier alone can open the safe. In Shamir's (t, n) threshold structure, selecting a higher value for t and storing the (t-1) secret on the smart card only increases the system's resistance to intrusion with cryptography, but with polynomial construction Will result in more computation for.

Such threshold structure reduces computational requirements in symmetric key recovery. In each new key, only a simple operation is performed compared to the RSA cryptography associated with modular exponentiation (ie, the value of the polynomial with x = 0 is calculated). Also, security is perfect (ie, for a given (x ₁ , y ₁ ) carry, all values of the secret remain equally likely).

The present invention uses Shamir's principle of secret sharing to hide the identity of the key for authenticating a message. In particular, the inventors propose a structure in which the key comprises a particular straight or curved Y-intercept formed by two or more points on the Euclidean plane.

In the simplest embodiment of this structure, the device (e.g. receiver) is manufactured using share (s) already stored therein (these are often referred to as 'predeployed' shared secret structures as described below. do). This stored share is used to calculate a key, which is then used to obtain a message authenticator. The message authenticator may be of the type described above with reference to FIG. 7, for example, MAC, or may be another authenticator known to those skilled in the art. When a message signal is sent, an additional or 'activating' share is sent with the signal. Note that the 'activation' share does not need to be encrypted in this structure, because the carry of the activation share does not mean anything without the stored share. Upon receipt of the 'activate' share, the device calculates the message authenticator using the key calculated by finding the Y-intercept of the straight line formed by the stored share and the 'activate' share. Each time a new key is needed, a new 'active' share can be selected at the transmitter, changing the Y-intercept of the straight line formed by the stored share and the 'active' share. In this way, the number of infinite keys can be limited and used without changing the hardware or software of the device. Note that the above-mentioned 'devices' may include many other types of equipment such as analog or digital television sets, set top boxes, video cassette recorders (VCRs), and other equivalent equipment known to those skilled in the art. For simplicity, the foregoing description will focus on the general "receiver" structure.

Key generation and distribution processing can be automated by developing a program to perform the following steps:

(a) select a secret (S); This will be the value along the Y axis of the Euclidean plane.

(b) Create a message authenticator using S. Such a message authenticator may for example be a MAC.

(c) Construct a first order polynomial f (x) passing through point (0, S) and another point (x ₀ , y ₀ ).

(d) to calculate f (x) at x _1, where the x ₁ ≠ x _0.

(e) Distribute (x ₁ , y ₁ ) with the message and the message authenticator (eg, MAC).

The structure as described above is sometimes referred to as a 'predeployed' shared secret structure because a portion of the secret is 'predeployed' to the device (eg receiver). In this example, the 'predeployed' share is the share stored at the receiver. The 'predeployed' shared secret structure has been discussed by others in the cryptography field. "How to (really) share a secret" by G.J. Simmons (Advances in Cryptology-CRYPTO '88 Proceedings, Springer-Verlag, pp. 390-448, 1990); J. Jay. Simons' "Prepositioned shared secret and / or shared control schemes" (Advances in Cryptology-EUROCRYPT '89 Proceedings, Springer-Verlag, pages 436-467, 1990 ). By predeploying certain share (s), the key can be changed relatively easily without having to change any circuitry at the receiver; Only the 'active' share needs to be changed.

Note that the algorithm outlines a previously deployed secret sharing structure using secret S with only two shares (ie, two points on a straight line on the Euclidean plane). Of course, other secrets S can be computed from more shares, making cryptography more difficult. An important aspect of a predeployed secret sharing structure is that some of the shares are 'deployed' to the receiver.

The present invention relates to storing at least one of the secret shares in a specific location (eg in receiver hardware). The stored share is then used in conjunction with the 'active' share to construct a secret. In the (4,4) structure, for example, three out of four shares are preferably stored at a specific location (eg receiver). Then, the last share (also referred to herein as the 'activation' share) is sent to the location to obtain a secret. In the present invention, it is important to note that although the secret is not the share itself, it is the Y-intercept of the straight line or curve (in higher order polynomials) formed by the share when represented as a point on the Euclidean plane.

1, 2A, and 2B together illustrate a message authentication system 100 according to a first exemplary embodiment of the present invention. The message authentication system 100 includes a message source (transmitter) 40 and a message receiver 50. The message source 40 typically uses a secret key to generate from the message a message authenticator that is sent to the receiver 50 with the message. Receiver 50 constructs the same key and uses the key to calculate the authenticator. If the authenticator configured at the receiver and the authenticator sent with the message are the same, the message is determined to be authenticated. In a first exemplary embodiment, a secret is obtained from two shares. As mentioned above, each share is defined at a point on the Euclidean plane.

In particular, a secret first share (or data point) is stored in the receiver 50. The first share can be thought of as a single point on the Euclidean plane (for example in the form of (x ₀ , y ₀ )). Message source 40 sends a message to receiver 50 along with a specific authentication protocol. In addition to the message, message source 40 sends a message authenticator and a second (or 'active') share (which is the second part of the secret). Similar to the first share, the second share can be a second single point from the same Euclidean plane (eg in the form of (x1, y1)).

In the first exemplary embodiment, the message, message authenticator (eg, MAC), and second ('activation') share are received by the receiver 50 and processed within the receiver. Receiver 50 is configured to reconstruct (or recover) the key (i.e., secret) with a second ('activation') share {e.g. (x ₁ , y ₁ )} and a stored first share {e.g. ( x ₀ , y ₀ )}. The receiver 50 then uses the reconstructed key to generate a message authenticator (eg MAC). If the message authenticator (e.g., MAC) calculated at the receiver 50 is the same as the message authenticator sent from the message source 40, the message is considered authenticated, and if the message authenticator is not the same, the message Is rejected.

Recovery of the key is realized by constructing a polynomial using the first and second shares; The y-intercept of the constructed polynomial is the key. For example, given (x ₀ , y ₀ ) and (x ₁ , y ₁ ), the key is constructed by calculating the S value in a given finite field, where:

FIG. 2A is a graphical representation of a first exemplary embodiment of the present invention showing an exemplary share (x ₀ , y ₀ ) and (x ₁ , y ₁ ) and thereby a straight line formed to intersect the Y axis at a particular point (key in) Represented by For illustrative purposes, the plot of FIG. 2A is obtained using real numbers rather than modular arithmetic.

An approach such as the method described above with reference to the first exemplary embodiment allows more than one message source 40 to share the stored (first) share (x ₀ , y ₀ ) stored in the receiver 50. do. Each message source 40 is then free to choose its own 'activation' (second) share (i.e., (x ₁ , y ₁ )) to define a broad secret. The probability of constructing a polynomial using the same y-intercept (ie, the same key) is low. However, the range of possible second ('active') shares may be allocated such that each service provider has a unique and non-overlapping range (see FIG. 2B).

To consider one example according to the first exemplary embodiment of the present invention, points (x ₀ , y ₀ ) = (17,15) and (x ₁ , y ₁ ) = (5,10) and p = Assume 23. First-order polynomial through (x ₀ , y ₀ ) and (x ₁ , y ₁ ):

silver

And

Can be configured by loosening.

The solution (a ₁ , a ₀ ) = (10,6) gives the following polynomial:

The value of the secret S can be recovered by calculating f (0).

Thus, according to the above example, the secret value and thus the key is 6 (mod 23). Of course, the value of this secret will change with each different value of (x ₁ , y ₁ ).

3 shows a key recovery structure according to a second exemplary embodiment of the present invention using three shares (relative to the two shares of the first exemplary embodiment). In the second exemplary embodiment, two using the first, second and third shares {eg, (x ₀ , y ₀ ), (x ₁ , y ₁ ), (x ₂ , y ₂ )} By constructing a differential polynomial (ie parabola), recovery of the key is realized; The y-intercept of the constructed quadratic polynomial is key.

To consider one example according to the second exemplary embodiment of the present invention, points (x ₀ , y ₀ ) = (17,15), (x ₁ , y ₁ ) = (5,10), and (x Assume ₂ , y ₂ ) = (12,6) and p = 23. Quadratic polynomials through (x ₀ , y ₀ ), (x ₁ , y ₁ ), and (x ₂ , y ₂ ):

silver

And

Can be configured by loosening.

The solution (a2, a1, a0) = (10,20,5) gives the following polynomial:

The value of the secret S can be recovered by calculating f (0):

As shown in FIG. 3, the first, second and third shares may be represented by points on the Euclidean plane. For illustrative purposes, the plot of FIG. 4 is obtained using real numbers rather than modular arithmetic.

4 illustrates a key recovery structure according to a third exemplary embodiment of the present invention using four shares. In a third exemplary embodiment, the first, second, third and fourth shares {eg, (x ₀ , y ₀ ), (x ₁ , y ₁ ), (x ₂ , y ₂ ), ( x ₃ , y ₃ )} to construct a cubic polynomial (ie curve) to recover the key; The y-intercept of the constructed cubic polynomial is the key.

In order to consider one example according to the third exemplary embodiment of the present invention, points (x ₀ , y ₀ ) = (17,15), (x ₁ , y ₁ ) = (5,10), (x ₂ Assume that y ₂ ) = (12,6), (x ₃ , y ₃ ) = (3,12), and p = 23. Third order polynomial through (x ₀ , y ₀ ), (x ₁ , y ₁ ), (x ₂ , y ₂ ), and (x ₃ , y ₃ ):

silver

Can be configured by loosening.

The solution (a ₃ , a ₂ , a ₁ , a ₀ ) = (18,19,0,22) gives the following polynomial:

The value of the secret S can be recovered by calculating f (0):

As shown in FIG. 4, the first, second, third and fourth shares may be represented by points on the Euclidean plane. For illustrative purposes, the plot of FIG. 4 is obtained using real numbers rather than modular arithmetic.

Multiple shares can also be used to create a convenient key transport structure in a communication network. Code authentication, an important issue in digital networks, can be used as a case study. In the future, complex home entertainment devices that process audio / video data will receive software for a variety of applications over digital distributed networks (eg, satellite, cable, terrestrial, Internet). Identification of the source of such code is a necessary requirement for both the service provider delivering the content and the manufacturer of the device using the content. The service provider wants to be assured that the application is only used by the received and authorized device. The device manufacturer in turn is concerned about unauthorized services to use the device. It is assumed that different device groups are authorized in different ways in a given broadcasting system. The example described below will discuss how pre-deployed secret sharing can be used to establish the required key hierarchy.

Consider a broadcast system with three different levels of authentication for code authentication:

(1) Level 1 Receivers-All receivers of a broadcast 'region' are assigned one common share (i.e., a common share for all receivers in that region).

(2) Level 2 Receivers-All receivers in a particular group are assigned an additional common share (ie, another share that is common for all receivers in a particular group).

(3) Level 3 Receivers-Each receiver is assigned a unique additional share.

The receiver described above can be used in connection with an 'activation' share to authenticate a particular message. Since a level 1 receiver contains only one share, a level 2 receiver contains two shares, and a level 3 receiver contains three shares, each receiver will provide a different set of keys. Thus, all receivers in the broadcast area (ie, level 1 receivers) will have the ability to receive and authenticate general messages, but only level 2 receivers will have the ability to receive and authenticate some additional messages, and only level 3 receivers. It will have the ability to receive and authenticate certain other additional messages. It should be noted that shares located at level 1 to 3 receivers contain 'predeployed' information that can be used in connection with an 'activating' share to compute secrets (eg, keys).

5 illustrates how multiple share structures are constructed using the Euclidean plane. As can be appreciated, three different authentication levels correspond to three y-intercepts (ie, "local key", "group key", "individual key"). The first order polynomial (corresponding to level 1 or 'local' authorization) includes a straight line passing through the 'activating share' and the level 1 common share. Quadratic polynomials (corresponding to level 2 or 'group' authorization) include parabolic passes through the 'active' share, the level 1 common share, and the level 2 share. Tertiary polynomials (corresponding to level 3 or 'individual' authentication) include curves passing through an 'activation share', a level 1 common share, a level 2 share, and a level 3 share. Note that in the above example, the 'activation' share is used to calculate each different key (ie, individual, group, and region). For illustrative purposes, the plot of FIG. 5 is obtained using real numbers rather than modular arithmetic.

Using the above example, the table below illustrates the relationship between share and different levels of authorization.

Point 1st level 1 2nd level 2 3rd level 3 Activation Share = (5,10) Yes Yes Yes Level 1 Common Share = (17,15) Yes Yes Yes Level 2 Share = (12,6) Yes Yes Level 3 Share = (3,12) Yes

Although the foregoing method and apparatus have been described in the context of a message authentication system for transferring authentication messages between users, the principles of the present invention may also be applied to methods and apparatus for providing conditional access to multimedia content.

Some of the advantages of the methods and apparatus described above include:

(a) Reduction of the computational requirements for the receiver in key recovery (ie, for each key only simple operations are performed). This is in contrast to the RSA decryption method, which is related to the modular power of law.

(b) Security is 'perfect'. In other words, given an activation share, all secret values remain equally likely. In higher order polynomials, the task of determining the secret given by the activation share becomes even more difficult.

(c) In a given set of 'predeployed' information shared between a transmitter and a receiver, another key can be easily delivered and used frequently (ie, by changing the 'activation' share).

(d) Different authorization levels can be defined by assigning different shares to each receiver.

(e) Security does not rely on unproven mathematical assumptions (ie, RSA's security is based on the difficulty of integer factorization problems).

The above structure effectively combines the advantages of symmetric and public key systems. 'Predeployed' information can be considered to be the receiver's private key. The symmetric key to be constructed is determined by the public information sent as part of the ECM. Since the key is not generated at the message source, no additional cryptography is needed to protect the key during distribution.

The effectiveness of the foregoing structures can be increased in a variety of ways, including:

(1) Defining a Key as a Function of a Shared Secret: Typically, a key can be generated by evaluating a predefined function at the value of the secret. For example, if the shared secret (eg Y-intercept of function f (x)) is real 7, then the key is It can be defined as. In this way, even if someone has recovered the secret, it does not necessarily have the ability to calculate the key. Alternatively, any other definition may be used once the coefficients of the polynomial are obtained. For practical purposes, it may be necessary for the function to have entropy retention properties (ie entropy (secret) = entropy [f (secret)]).

(2) Making the order of the polynomial function (and thus the number of shares needed to recover the secret) into a time-dependent secret system parameter: for example, the order of the polynomial f (x) defining the secret is in units of one day, The unit of time is changed. Cryptography is an additional demanding task for the counterpart because it must first determine the order of the polynomial.

(3) Masking the activation share before transmission: The activation share transmitted with the message may not be masked by the receiver in the predefined processing. One example of masking is to use the hash of the activation share for authentication, but instead send the activation share. At this time, the receiver performs hashing to determine the actual value.

(4) Add an extra activation share: The additional activation share sent with the actual activation share is filtered by the receiver in a predefined process.

Any combination of the above improvements will serve to hide the actual value of the activation share in transmission and introduce an additional level of security for the message.

While the above discussion focuses primarily on using MAC as the message authenticator, those skilled in the art will recognize that other message authentication methods may be used without departing from the scope of the present invention (eg, message encryption; the present application and See FIG. 8 of the detailed description).

Although the present invention has been described in terms of secret sharing structures that may use primary, secondary and tertiary polynomials to form a secret, one of ordinary skill in the art can use any order of polynomials (e.g., quaternary, fifth order, etc.). I will understand. In fact, higher order polynomial functions would be desirable in that they provide additional security in lower order polynomial functions because the number of shares to be estimated increases. Further, while the above description focuses on systems having a single smart card (eg smart card), those skilled in the art will understand that multiple smart cards can be used, with each smart card having one or more share values stored therein. will be.

As noted above, the present invention is available in systems and methods that provide a high level of security but provide message authentication without using a fixed key.

Claims (20)

As a method of authenticating a message, Receiving at the device data indicative of a first share; Constructing a key using the first share and at least two additional shares stored in the device; And Authenticating a message using the configured key. The method of claim 1, wherein the first, second, and third shares are points on an Euclidean plane. 2. The method of claim 1, wherein said message authenticating step comprises authenticating a message using a message authentication code (MAC). 2. The method of claim 1, wherein said message authentication step comprises authenticating a message using a decryption key. A method of providing authentication of a message, Receiving a message authenticator and the message at a device; Receiving at the device data indicative of a first share; Constructing a key using the first share and second and third shares stored in the device; And Authenticating the message using the configured key and the message authenticator, Constructing the key comprises calculating a Y-intercept of a curve formed on the Euclidean plane by the first, second, and third shares. 6. The method of claim 5, wherein said message authenticator comprises a message authentication code. A system for authenticating a message sent from a first device to a second device, the second device comprising: Receiving a message and a message authenticator; Receiving data representing the first share; Constructing a key using the first share and second and third shares stored in the second device; And Authenticating the message using the configured key and the message authenticator, Constructing the key comprises calculating a Y-intercept of a curve formed on the Euclidean plane by the first, second and third shares. As a message authentication system, At least one message source; And A message authentication system comprising at least one message receiver for receiving a message, a message authenticator and a first share sent by the at least one message source, Wherein the at least one message receiver comprises second and third shares stored therein for authenticating the message, wherein the second and third shares are used in connection with the first share to authenticate the message. Authentication system. The method of claim 1, wherein the first share and the at least two additional shares are points on at least a second order polynomial function. The method of claim 1, wherein the at least two additional shares comprise at least three additional shares such that the first share and the at least three dml additional shares are points on at least a third order polynomial function. The method of claim 1, wherein the key comprises a secret value calculated from the first and the at least two additional shares. The method of claim 1, wherein the key comprises a function of a secret value calculated from the first and the at least two additional shares. The method of claim 1, wherein the first share and the at least two additional shares comprise points on a polynomial function. The method of claim 13, wherein the order of the polynomial function is changed periodically. 2. The method of claim 1, further comprising masking the first share before receiving the first share at the device. 16. The method of claim 15, further comprising calculating the first share from a masked version of the first share. 10. The method of claim 1, further comprising transmitting a first share and at least one redundant share. 18. The method of claim 17, further comprising filtering the at least one redundant share after receiving the first share. A method of operating a message authentication system, Sending a message, a message authenticator, and a first share from a transmitter station to a receiver station; Receiving the message, the message authenticator, and the first share at the receiver station; Constructing a key using the first share and at least two additional shares stored at the receiver station; And Authenticating the message using the configured key and the message authenticator. telautograph; And A message authentication system comprising a message sent by the transmitter, a message authenticator and a receiver receiving a first share, The receiver includes second and third shares stored therein for authenticating the message, wherein the second and third shares are used in connection with the first share to authenticate the message.