Reciprocity laws and identity-based encryption
Abstract/Contents
- Abstract
- Identity-based encryption (IBE) is a longstanding challenge in cryptography: can we securely encrypt a message to somebody if we only know their identifier (such as an email address, URL, etc.), without the need to first obtain their public key? In an IBE system, there is a single central trusted party who possesses a "universal key", allowing them to derive the secret key for all users. This arrangement provides much more stringent constraints on the mathematical objects used to build the system than in the usual public-key setting: the relationship between each identities and its corresponding secret keys needs to be cryptographically hard to compute, but knowledge of a single "universal key" must be enough to compute the secret key for every identity. While the problem of identity-based encryption was first posed by Shamir in 1985, the first construction of an IBE system was not until 2001, when Boneh-Franklin built an IBE system using the Weil pairing for elliptic curves. Also in 2001, Cocks constructed an IBE system based on the arithmetic of quadratic residues. Given an RSA number N = pq, the problem of determining which integers are quadratic residues modulo N is believed to be intractable, but knowledge of the factorization of N is sufficient to solve the problem. In this thesis, we provide an abstract-algebraic framework for Cocks' construction, resulting in a large family of possible generalizations. At this level of abstraction, we construct an IBE system and prove that its security reduces to the hardness of an underlying mathematical problem. However, it is not clear from the general definitions that encryption and decryption can be implemented using efficient (i.e. polynomial time) algorithms. To address this challenge, we fix our attention on the problem of detecting l-th powers modulo an RSA composite N = pq in a number field K containing the l-th roots of unity. Then, by applying the Artin reciprocity law of class field theory, we show that the corresponding IBE system can be realized with efficient algorithms.
Description
| Type of resource | text |
|---|---|
| Form | electronic resource; remote; computer; online resource |
| Extent | 1 online resource. |
| Place | California |
| Place | [Stanford, California] |
| Publisher | [Stanford University] |
| Copyright date | 2023; ©2023 |
| Publication date | 2023; 2023 |
| Issuance | monographic |
| Language | English |
Creators/Contributors
| Author | Dore, Daniel Nelson |
|---|---|
| Degree supervisor | Conrad, Brian, 1970- |
| Thesis advisor | Conrad, Brian, 1970- |
| Thesis advisor | Vakil, Ravi |
| Thesis advisor | Vondrak, Ján, (Mathematician) |
| Degree committee member | Vakil, Ravi |
| Degree committee member | Vondrak, Ján, (Mathematician) |
| Associated with | Stanford University, School of Humanities and Sciences |
| Associated with | Stanford University, Department of Mathematics |
Subjects
| Genre | Theses |
|---|---|
| Genre | Text |
Bibliographic information
| Statement of responsibility | Daniel Nelson Dore. |
|---|---|
| Note | Submitted to the Department of Mathematics. |
| Thesis | Thesis Ph.D. Stanford University 2023. |
| Location | https://purl.stanford.edu/vp300vn1983 |
Access conditions
- Copyright
- © 2023 by Daniel Nelson Dore
- License
- This work is licensed under a Creative Commons Attribution Non Commercial Share Alike 3.0 Unported license (CC BY-NC-SA).
Also listed in
Loading usage metrics...