DIMACS

About Me

me

This website is no longer being updated. My personal website can be found here. You can find the REU homepage here.

Project Background

The field of cryptography is highly reliant on numerous assumptions about computational hardness that are unknown to be true or, in some cases, likely to be untrue. Even the best practices in the real world are based on optimistic assumptions about computational problems that have stood the test of time, at least until now. This is not only slightly unsatisfying from an academic perspective, but also has serious implications should these cryptographic foundations eventually be broken, either from advances in quantum computing or a surprise breakthrough in algorithms research. In this project, we examine and try to extend the results of Naor and Yung, who showed signatures are possible to construct from private-key cryptographic primitives, a massive relaxation from what was previously thought to be possible.

A digital signature scheme is a protocol that is meant to be the digital analog of the physical process of signing a document. In this system, a signer first makes an initial value publically known. Then, using a randomly chosen secret key, the signer computes a signature on any message, and this signature should be easily verifiable by anyone with the public key. Additionally, it should be impossible for anyone else who doesn't know the signer's private key to compute a verifiable signature without just guessing the private key.

Research Log

Week 1 (5.28-6.2)

This week consisted mainly of reading an introductory text on cryptography (Introduction to Modern Cryptography by Katz & Lindell), as it has been a little while since I have done work in this field. I made considerable progress on this book, and my mentor gave me a paper to read that is an accessible introduction to the topic.

Week 2 (6.3-6.9)

Again, this week I primarily focused on reading. On Tuesday, I presented a brief overview on the problem that I will be working on this summer, but as I was preparing for that presentation, I realized that I have significant gaps in my understanding of both the background knowledge as well as what exactly I am working on this summer. I just about finished reading the text (up until chapter 13, and omitting some of the more technical sections).

I also finished my first reading of the paper ([NY89]) that my mentor gave me, as well as some of the referenced papers from it. Unfortunately, I was not able to meet with my mentor this week due to schedule conflicts, so for the remainder of the week I tried some ideas to no avail, and read some more papers that I thought might be useful.

Week 3 (6.10-6.16)

This week, I managed to meet with my mentor, and the exact setting of our project is starting to be more concrete to me. We discussed on a very high level some general ideas and principles might be useful in this project. Still, the main part of the project still feels a little out of reach for me, and at the beginning of next week I will hopefully be able to present the complete digital signature scheme that I have been reading about.

Week 4 (6.17-6.23)

On Tuesday, I had a brutally long but productive meeting where I attempted to present a digital signature scheme which is secure given the existence of injective one-way functions. We worked through the details of the proof, and I gained a more concrete understanding of the protocol overall as a result. Later, I realized that a part of the proof that I had previously skimmed over is a lot more complicated than I had initially thought. In re-creating this proof on my own, I got much more proficient dealing with reductions in this setting.

This paper presents a digital signature scheme that is stateful, meaning the digital signature of a message depends on which messages were sent before it. This isn't practical for many applications, and it is much more ideal to have a stateless, or "memoryless" digital signature scheme, in which a signature can be validated without the messages that were sent before. [GMR88] presents a signature scheme that has a similar structure to Naor and Yung's construction, and it admits a relatively simple transformation that makes it memoryless. However, GMR uses trapdoor one-way functions which are invertible, whereas our assumptions are much weaker and therefore our one-way functions are not invertible. Naor and Yung claim that similar techniques can be used to make their construction memoryless, but they leave essentially no justification in the paper. I am currently trying to figure this out.

Week 5 (6.24-6.30)

On Tuesday, I finally successfully presented Naor and Yung's construction of digital signatures from one-way permutations. However, I still was not able to produce a construction of the memoryless version, which they only briefly mentioned to be possible but offeredn painfully little elaboration. As of writing this (Thursday), I met with my advisor one more time since then, and I think I have figured it out, however the proof of security is still unclear and I have to work on it to really feel like my knowledge is complete. This update is brief, but it has taken me numerous peripheral papers and outside resources to understand what is going on in this paper, which is clearly meant to be understood by people in the field of cryptography at the time.

Week 6 (7.1-7.7)

This week, I finally figured out a way to prove my construction of the stateless signature scheme. We met on Monday to make sure I adequately understood the proof, and although it was still a bit shaky, I was good enough to get started with writing up a full paper on the construction and proof of this scheme. This process will be a very long one, and I intend to publish it to arxiv when it's done and polished. This week, I took the weekend off for July 4th so not much was finished (roughly a third of the first draft is done).

Week 7 (7.8-7.14)

I mainly just worked on my writeup this week. I fully wrote up a proof and finally solidified it in my mind, and on our meeting on Tuesday, I presented a satisfactory proof of security. There aren't many updates, except for the fact that I finished a first draft on Friday and sent it to my mentor, who is currently reviewing it and will send me a list of things to fix. We are still working on some research questions regarding the project, but this will continue after the program has finished.

Week 8 (7.15-7.21)

I have been dealing with a sickness from last week, and the final presentations for the REU are happening on Wednesday and Thursday. I fortunately got well quickly and was able to prepare and deliver my final presentation. On Friday, we left for Prague. In the small amounts of free time I've had in between, I have been working a little bit on writing my final report and cleaning it up.

Week 9 (7.22-7.28)

This is the last full week of the program. This week, along with the rest of the Prague group we attended a series of talks given by various faculty members from Charles University. We did a lot of exploring the beautiful city, and I finished up my final report this week. Next week, we will have the opportunity to attend the Midsummer Combinatorial Workshop held in Prague.

Readings

Acknowledgements

This research was conducted while I was a participant in the 2024 DIMACS REU program at Rutgers University, supported by NSF grants CCF-1836666 and CNS-2150186.