Electrical computers and digital processing systems: support – Multiple computer communication using cryptography – Security kernel or utility
Reexamination Certificate
1999-06-23
2001-02-20
Beausoliel, Jr., Robert W. (Department: 2785)
Electrical computers and digital processing systems: support
Multiple computer communication using cryptography
Security kernel or utility
C713S153000
Reexamination Certificate
active
06192472
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention generally relates to the secure storage and retrieval of information and, more particularly, to a method and apparatus which guarantees the integrity and confidentiality of the stored information.
2. Description of the Prior Art
The problem this invention is concerned with is the secure storage and retrieval of information. Consider a user who stores his or her files on his or her workstation. Random failures (such as a hard disk crash) could cause the loss or the temporary unavailability of the data. Also possibly malicious intrusions may occur which would destroy both the confidentiality and integrity of the data. Ideally, the user would like a fully secure system which provides protection against these and maybe other kinds of faults without overburdening the system with memory and computational requirements.
Typically, protection against random failures is obtained via replication. That is, the data is stored in multiple locations so that failures in some of them can be tolerated. One such example is the Redundant And Inexpensive Drive (RAID) standard commonly used on servers in a Local Area Network (LAN). In order to obtain a significant degree of protection, there is a high cost in terms of memory requirements.
The notion of information dispersal was introduced by M. Rabin in his well-known Information Dispersal Algorithm (IDA) described in “Efficient Dispersal of Information for Security, Load Balancing, and Fault Tolerance”,
Journal of the ACM
, Vol. 36(2), pp. 335-348, 1989. The basic approach taken in IDA is to distribute the information F being stored among n active processors in such a way that the retrieval of F is possible even in the presence of up to t failed (inactive) processors. The salient point was to achieve this goal while incurring a small overhead in needed memory. And in fact Rabin's result is space optimal. Retrieval of F is possible out of n−t pieces, where each piece is of length
&LeftBracketingBar;
F
&RightBracketingBar;
n
-
t
.
The Information Dispersal Algorithm uses a linear transformation to convert m=nt−t bytes of input into m bytes of output. This transformation is given by an m×n matrix T over GF(
2
8
). Moreover, the matrix T has the property that every (n−t) columns of T are linearly independent. Thus, each input and output byte is viewed as an element of GF(2
8
). The block size is m bytes and the operation is repeated for every m bytes.
Let the (i,j)
th
entry of T be represented by T
ij
. Let P
0
, P
1
, . . . , P
m-1
be a block of input. Then the output bytes Q
0
, Q
1
, . . . , Q
n-1
are given by
Q
i
=T
0,i
•P
0
+T
1,i
•P
1
+. . . T
m-1,i
•P
m-1
,
where the arithmetic is performed in the field GF (2
8
)
Given any m output bytes, the input can be recovered because every m columns of T are linearly independent. In other words, the matrix S formed by taking the columns of T which correspond to these m output bytes is invertible. Again, the inverse of this matrix is computed over GF(2
8
).
As an example, let m=3 and n=5. The following matrix T has the property that every three columns of T are linearly independent. Note that we are using polynomials in x for representing elements of GF(2
8
). The polynomial arithmetic can be done modulo x
8
+x
6
+x
5
+x
4
+1, which is an irreducible polynomial over GF(2).
T
=
⌊
1
0
0
1
1
+
x
0
1
0
1
x
0
0
1
1
1
⌋
If, for example, only the first, second and fifth byte of a coded text are known, the plaintext (or original text) can be retrieved by applying the following transformation to the three bytes of coded text:
⌊
1
0
1
+
x
0
1
x
0
0
1
⌋
&AutoRightMatch;
In addition to its optimal space complexity, the IDA technique has the following very attractive properties:
it permits any party in the system to retrieve the distributed information (by communicating with the piece holders);
it does not require a central authority;
it is symmetric with respect to all participants; and
no secret cryptographic keys are involved.
However, this combination of very desirable properties is achieved at the expense of limiting the kind of faults against which the algorithm is robust, namely, by assuming that available pieces are always unmodified.
An enhanced mechanism to reconstruct the information when more general faults occur was presented by H. Krawczyk, in “Distributed Fingerprints and Secure Information Dispersal”,
Proc
. 20
th
Annual ACM Symp. on Principles of Distributed Computing
, pp. 207-218, Ithaca, N.Y., 1993, who called this problem, and its solution, the Secure Information Dispersal problem/algorithm (SIDA). This mechanism is able to tolerate malicious parties that can intentionally modify their shares of the information, and is also space optimal (asymptotically). In a nutshell, SIDA makes use of a cryptographic tool called distributed fingerprints, which basically consists of each processor's share being hashed, i.e., the fingeprints, and then distributing this value among an processors using the coding function of an error correcting code that is able to reconstruct from altered pieces (e.g., the Reed-Solomon code). In this way, the correct processors are able to reconstruct the fingerprints using the code's decoding function, check whether pieces of the tile were correctly returned, and finally reconstruct F from the correct pieces using the IDA algorithm.
A shortcoming of these methods is to assume that the faults only occur at reconstruction time, after the dispersal of the shares has been properly done.
SUMMARY OF THE INVENTION
It is therefore an object of the present invention to provide a solution to the general problem of Secure Storage and Retrieval of Information (SSRI) and guarantee that also the process of storing the information is correct even when some of the processors fail.
We consider the scenario in which a user interacts with the storage system by depositing a file and receiving a proof (in the form of a receipt) that the deposit was correctly executed. For efficiency reasons, we require the distributed nature of the system to be transparent to the user, who will interact with a single distinguished processor which we call the gateway. This distinguished processor does not need to be the same for all users. This adds the extra technical difficulty of designing the protocol in a way that the gateway is not a single point of failure. The invention provides the following:
SSRI with integrity: We introduce a mechanism that extends the above methods to enable storage in the presence of both inactive and maliciously active faults, while maintaining the (asymptotical) space optimality of the above methods. Namely, each share is of size
&LeftBracketingBar;
F
&RightBracketingBar;
n
-
t
plus a small quantity q which does not depend on the size of the file (but on n and a security parameter s defined as the logarithm base two of an acceptable probability of failure of the system).
SSRI with integrity and confidentiality: We also introduce a mechanism for SSRI with the added requirement of confidentiality of information;
i.e., that any collusion of up to t processors (except ones including the rightful owner of the information) should not be able to learn anything about the information. Also, in this case space optimality is preserved.
First we concern ourselves only with the integrity of the information. We introduce simple protocols that extend the above methods to enable storage in the presence of malicious faults, while maintaining the (asymptotical) space optimality of the above methods. Namely, each share is of size
&LeftBracketingBar;
F
&RightBracketingBar;
n
-
t
plus a small quantity q which does not depend on the size of the file (but on n and a security parameter s). Our storage protocol is designed so that some form of consistency is maintained among the processors without incurring the cost of (potentially expensive) agreement protocols. Anoth
Garay Juan Alberto
Gennaro Rosario
Jutla Charanjit Singh
Rabin Tal D.
Beausoliel, Jr. Robert W.
Elisca Pierre Eddy
Herzberg Louis B.
International Business Machines - Corporation
McGuireWoods
LandOfFree
Method and apparatus for the secure distributed storage and... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for the secure distributed storage and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for the secure distributed storage and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2558360