Electrical computers and digital processing systems: support – Data processing protection using cryptography
Reexamination Certificate
1998-11-18
2001-10-09
Peeso, Thomas R. (Department: 2132)
Electrical computers and digital processing systems: support
Data processing protection using cryptography
C713S152000, C713S152000
Reexamination Certificate
active
06301664
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates generally to cryptography, and more particularly, to a method and system for non-malleable and non-interactive cryptographic commitment in a network.
The widespread use of computers and computer networks has heightened the need for security. The explosive growth of, for example, the Internet, including electronic commercial transactions and funds transfer, has increased the need for security in communications, data storage and management. It has also served to demonstrate that designing secure communication protocols is a complex issue, requiring considerable expertise and research.
Although the Internet has become the most economical means for communication between two or more remote sites, it does not provide protection for transmitted information. As a result, cryptographic protocols have been developed for securing electronic communication between two or more sites.
A fundamental cryptographic protocol is a “commitment” protocol. A commitment protocol generally specifies the steps for secured communication between two probabilistic polynomial-time players (i.e., a sender and a receiver). The communication between the sender and the receiver includes a commitment phase and a de-commitment phase.
In the commitment phase, based on information a sender desires to communicate to a receiver, the sender builds and sends to the receiver a commit message, such that when the receiver receives the commit message the receiver cannot retrieve the information from the commit message. In the de-commitment phase, the sender builds and sends to the receiver a de-commit message, which enables the receiver to retrieve the information from the commit message, such that the receiver is assured that the retrieved information is the information the sender committed to in the commitment phase.
The commitment protocol is used in a wide variety of cryptographic applications, including electronic contract signing (or bidding) and multi-party computations. In an electronic contract bidding application, two or more senders, for example bidders, communicate via, for example the Internet, bids on a contract to a receiver. In such an application, each sender commits to a bid by sending a commit message to the receiver. Once the receiver receives all of the bids, each sender de-commits its respective bid by sending a de-commit message to the receiver. The receiver then determines to grant the contract to a sender that, for example, submits the lowest bid.
In an electronic contract bidding application, one problem with known commitment protocols is that the communication between a sender and a receiver is malleable. Malleable means that even if the particular commitment protocol used by each sender is computationally secure against any polynomially-bounded receiver, a sender can still potentially intercept another sender's commit message and build a related commitment message based on the intercepted commit message without determining the underlying bid in the intercepted commit message. Furthermore, the intercepting sender can also intercept the other sender's de-commit message and build a related de-commit message, such that the related de-commit message includes, for example, a lower bid than the intercepted de-commit message. Hence, the intercepting sender can underbid the other sender without explicitly determining the other sender's bid.
To address the problem of malleable commitment, D. Dolev, C. Dwork, and M. Naor, “Non-Malleable Cryptography,” in Proceedings of Symposium On The Theory Of Computing (1991), discloses a non-malleable commitment protocol. The Dolev, Dwork and Naor protocol, however, is interactive, and thus inefficient, as it requires a logarithmic number of rounds of two way communication between a sender and a receiver. In addition, the protocol requires costly zero-knowledge proofs, which renders communication between the sender and receiver inefficient.
A. De Santis and G. Persiano, “Zero-Knowledge Proofs Of Knowledge Without Interaction,” in the Proceedings of IEEE Foundations Of Computer Science (1996), disclose a non-interactive zero-knowledge proof of knowledge. Using the De Santis and Persiano techniques, one can implement a non-malleable commitment protocol that is non-interactive. This commitment protocol, however, can only be implemented using dense crypto-systems that are based on one or more strong algebraic assumptions. Furthermore, like the Dolev, Dwork and Naor protocol, the De Santis and Persiano commitment protocol requires costly zero-knowledge proofs.
M. Bellare and P. Rogaway, “Random Oracles Are Practical: A Paradigm For Designing Efficient Protocols,” in the Proceedings of ACM Conference On Computer And Communication Security (1993), discloses a non-malleable and non-interactive commitment protocol, which uses cryptographic hash functions that behave as random oracles. The Bellare and Rogaway protocol, however, does not enable one of ordinary skill in the art to implement (or even define) such random oracles with the requisite properties for complexity-theoretic assumptions. Furthermore, because the protocol is based on heuristic assumptions, the communication between a sender and a receiver is not as secure as when using other known commitment protocols.
Therefore, it is desirable to have a method and system for overcoming the above and other disadvantages of the prior art.
DESCRIPTION OF THE INVENTION
Methods and systems consistent with the present invention perform non-malleable commitment to data, which is communicated by a sender to a receiver. At a commitment phase, the sender selects a first string having a first portion and a second portion, and based on the first portion of the first string, establishes a first commitment to an authentication key. The sender divides the second portion of the first string into a set of segments each including two or more sub-segments, and based on the first commitment, selects one of the sub-segments in each of the segments. The sender combines the selected sub-segments together, and establishes a second commitment to the data based on the combined selected sub-segments such that the second commitment is equivocable. The sender authenticates the second commitment by using the authenticating key. At a de-commitment phase, the sender de-commits the data and the authentication key.
Methods and systems consistent with the present invention have two advantages over the prior art. First, such methods and systems are non-interactive, and thus efficient, as a sender engages in a one-way communication with a receiver. Second, such methods and systems do not require costly zero-knowledge proofs and/or strong algebraic assumptions for securing the communication between the sender and the receiver.
The description of the invention and the following description for carrying out the best mode of the invention should not restrict the scope of the claimed invention. Both provide examples and explanations to enable others to practice the invention. The accompanying drawings, which form part of the description for carrying out the best mode of the invention, show several embodiments of the invention, and together with the description, explain the principles of the invention.
REFERENCES:
patent: 6219694 (2001-04-01), Lazaridis et al.
patent: 6219788 (2001-04-01), Flavin et al.
patent: 6219790 (2001-04-01), Lloyd et al.
patent: 6219791 (2001-04-01), Blanchard et al.
Di-Crescenzo Giovanni
Ishai Yuval
Ostrovsky Rafail
Giordano Joseph
Peeso Thomas R.
Telcordia Technologies Inc.
LandOfFree
Method and system for non-malleable and non-interactive... 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 system for non-malleable and non-interactive..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for non-malleable and non-interactive... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2605221