DIMACS

About Me

me

Project Information

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 unsatisfying from an academic perspective, but also has serious implications in the event that these cryptographic foundations are broken. In this project, we are exploring cryptography that is resilient to even a computationally unbounded adversary.

Generally, security by obscurity is not practical, and in proofs of security we always assume that the adversary has complete understanding of how our cryptographic protocol operates. Security should depend on the random choice of a secret value (known as a private key) which has a significant and unpredictable effect on the execution of the protocol when changed even slightly. This ideology stems from the fact that it is significantly easier to change this secret value (should it somehow get found out) than it is to design an entirely new security protocol that relies on obscurity. An example of this (sort of) happened in WWII, when the Allies managed to recover some of Germany's Enigma machines (thus finding out the mechanism by which their radio messages were encrypted). Despite gaining this, the Allies weren't immediately able to decode German communication because decryption relied on the knowledge of a secret key, which was constantly changing.

Intuitively, a secure cryptographic protocol is a function (defined with some secret key parameter) that is impossible to replicate with non-negligible probability without guessing the exact value of the secret key (which if the key space is chosen to be large enough, and the key sampled randomly, is extremely unlikely). These protocols usually rely on computationally difficult problems like factorization of two primes, which is hoped to be impossible to accomplish efficiently, but with the slow realization of quantum machines, may possibly be broken eventually. Many of these problems are thought to be computationally hard simply because they have stood the test of time, and oftentimes the protocols designed around them may still be breakable even if their individual components were to be provably hard. Ideally, we want a protocol that achieves security even against an all-powerful adversary, a type of security called information-theoretic security.

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.

We are exploring digital signature schemes that have information-theoretic security, meaning they are resilient to a computationally unbounded adversary.

Research Log

Week 1 (5.28-6.1)

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 he thinks we can adapt to use in our research project.

Week 2 (6.2-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), and I also skimmed through Shannon's book on information theory to refresh myself on it.

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. The methods used in this paper vaguely resemble some techniques I remember seeing when I briefly worked with zero-knowledge proofs a while ago. 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, and I was happy to find out that my mentor also thinks that some ideas from multiparty computation might be useful here. 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.

Most of the reading that I have been doing is just making me feel a little more comfortable in this topic, and some of the statistical/information theoretic ideas are starting to feel more natural to me. I hope to start actually trying to make progress toward our digital signature scheme soon.

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 Periklis 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.

Readings (under construction)

Acknowledgements

I would like to thank Prof. Periklis Papakonstantinou for giving me this interesting project and guiding me throughout this summer. 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.