New foundations for efficient authentication, commutative cryptography, and private disjointness testing
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2006.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2007
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/37842 |
| _version_ | 1811076409851904000 |
|---|---|
| author | Weis, Stephen August, 1978- |
| author2 | Ronald L. Rivest. |
| author_facet | Ronald L. Rivest. Weis, Stephen August, 1978- |
| author_sort | Weis, Stephen August, 1978- |
| collection | MIT |
| description | Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2006. |
| first_indexed | 2024-09-23T10:21:19Z |
| format | Thesis |
| id | mit-1721.1/37842 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T10:21:19Z |
| publishDate | 2007 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/378422019-04-11T09:35:51Z New foundations for efficient authentication, commutative cryptography, and private disjointness testing Weis, Stephen August, 1978- Ronald L. Rivest. Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science. Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science. Electrical Engineering and Computer Science. Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2006. This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections. Includes bibliographical references (p. 105-115). This dissertation presents new constructions and security definitions related to three areas: authentication, cascadable and commutative crytpography, and private set operations. Existing works relevant to each of these areas fall into one of two categories: efficient solutions lacking formal proofs of security or provably-secure, but highly inefficient solutions. This work will bridge this gap by presenting new constructions and definitions that are both practical and provably-secure. The first contribution in the area of efficient authentication is a provably-secure authentication protocol named HB+. The HB+ protocol is efficient enough to be implemented on extremely low-cost devices, or even by a patient human with a coin to flip. The security of HB+ is based on the hardness of a long-standing learning problem that is closely related to coding theory. HB+ is the first authentication protocol that is both practical for low-cost devices, like radio frequency identification (RFID) tags, and provably secure against active adversaries. The second contribution of this work is a new framework for defining and proving the security of cascadable cryptosystems, specifically commutative cryptosystems. (cont.) This new framework addresses a gap in existing security definitions that fail to handle cryptosystems where ciphertexts produced by cascadable encryption and decryption perations may contain some message-independent history. Several cryptosystems, including a new, practical commutative cryptosystem, are proven secure under this new framework. Finally, a new and efficient private disjointness testing construction named HW is offered. Unlike previous constructions, HW is secure in the face of malicious parties, but without the need for random oracles or expensive zero-knowledge protocols. HW is as efficient as previous constructions and may be implemented using standard software libraries. The security of HW is based on a novel use of subgroup assumptions. These assumptions may prove useful in solving many other private set operation problems. by Stephen A. Weis. Ph.D. 2007-07-17T19:40:14Z 2007-07-17T19:40:14Z 2006 2006 Thesis http://hdl.handle.net/1721.1/37842 132732685 eng M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission. http://dspace.mit.edu/handle/1721.1/7582 115 p. application/pdf Massachusetts Institute of Technology |
| spellingShingle | Electrical Engineering and Computer Science. Weis, Stephen August, 1978- New foundations for efficient authentication, commutative cryptography, and private disjointness testing |
| title | New foundations for efficient authentication, commutative cryptography, and private disjointness testing |
| title_full | New foundations for efficient authentication, commutative cryptography, and private disjointness testing |
| title_fullStr | New foundations for efficient authentication, commutative cryptography, and private disjointness testing |
| title_full_unstemmed | New foundations for efficient authentication, commutative cryptography, and private disjointness testing |
| title_short | New foundations for efficient authentication, commutative cryptography, and private disjointness testing |
| title_sort | new foundations for efficient authentication commutative cryptography and private disjointness testing |
| topic | Electrical Engineering and Computer Science. |
| url | http://hdl.handle.net/1721.1/37842 |
| work_keys_str_mv | AT weisstephenaugust1978 newfoundationsforefficientauthenticationcommutativecryptographyandprivatedisjointnesstesting |