Thesis Proposal

On October 2, 2007, I brought my laptop into the lab along with two-way USB speakers for my thesis proposal. The thesis proposal was to start at ten-thirty so I headed to the room, Babbio 210, at nine-thirty to get my equipment set up. My plan was to connect my laptop into the Internet though the jack in the classroom and use Skype to connect my west-coast committee member, Josh, into the presentation. I had on dockers and a dress shirt. A tie was in my backpack.

I found that I could not get IP numbers from the classroom's wired network connection, even with my PEAP information. The crappy wireless card on my laptop couldn't pull in the wireless connection, either. I tried to call the lab, but my cellphone didn't work and wouldn't without an application of money. I spent a lot of time trying to get things to work and then Onur came in.

``Onur, I can't get an Internet connection. Can I use your laptop to connect my west-coast committee member?''

``Sure. I have Skype installed.''

``That's great.''

I put my tie on while he went back to the lab. I learned to tie a Windsor knot at an early age as I went to private schools where the wearing of a coat and tie were mandatory. Onur reappeared about ten minutes later with his laptop which was able to connect to the wireless. I plugged my USB speakers into his laptop and logged into my Skype account. My telephone list came up and I selected Josh Benaloh's home number and told it it to connect.

``Can you hear me?'' I asked.

``Yes.'' Josh said.

``Great. We will start shortly.''

People started filing in and soon the classroom was full. We were missing the committee member from the math department, Bob Gilman, and I proposed that we wait for him. We waited for about ten minutes, and he didn't come so we started.

My adviser introduced me, ``This is my PhD student Michael de Mare and he is going to give his thesis proposal on post-quantum cryptography using complexity.''

``Thank you.

``In 1994 Shor showed how to efficiently factor and compute discrete logarithms using quantum computers. In order to do cryptography with a quantum adversary, it is necessary to make new security assumptions that quantum computers can't easily defeat.

``Fortunately, it appears that there are problems that are hard for a quantum computer. Bennett et al. showed that relative to a random oracle, NP requires $2^{n/2}$ oracle queries. This holds for all black-box methods. Grover's algorithm shows that NP can, in fact, be solved in $2^{n/2}$ oracle queries. Bennett et al. also showed that the intersection of NP and co-NP, where most cryptography is, requires at least $2^{n/3}$ oracle queries.

``Another problem that needs to be taken into account is that a general discrete log algorithm would break almost all public-key cryptosystems. Factoring and elliptic log can both be solved efficiently with a discrete log oracle. Benaloh and I developed the factoring result in 1992 and it appears in my 2004 masters thesis. There will be a chapter in my thesis on this.''

I then put up a slide with the algorithm for factoring with a discrete log oracle and went over it.

I continued, ``The research for the number theory chapter is complete, but the chapter itself needs a complete rewrite. We also need to describe the significance of the result to cryptography.

``There are theoretical limits on the use of NP-hardness in cryptography. Brassard showed that one-way permutations can not be hard unless NP=co-NP. This is because the decision problem is expressed as $f(x)=y, x>t?$. An $x'$ such that $f(x')=y$ and $x'<t$ is a witness that the answer is no, so therefore the problem is in co-NP. To deal with this limitation, we propose a system that is weaker than one-way permutations.

``Our system is a solution to the secure set membership problem. The idea behind the secure set membership problem is that we can check if a string is a member of a set but we can not efficiently use the set to learn a member. An example might be a credit card with multiple users and pins. We would like to test if a pin is valid without storing the actual pins.

``The structure of a solution to this problem consists of two protocols. A set establishment protocol where the set membership operator is created and a set membership protocol which determines whether a string is a member of a set.

``One solution to this problem is one-way accumulators which were invented by Benaloh and I at Eurocrypt '93. One-way accumulators require the prover to remember a second value which hashes with the string to give the accumulator. The hash function needs to have an associative property. The only known way to implement this assumes that factoring is hard, which is not true in the post-quantum model.

``3SAT is a logic statement on the bits of a string. If the string makes it true, it is said to satisfy the formula and is called a witness. Deciding if a formula is satisfiable is NP-complete. Deciding 3SAT is polynomially equivalent to computing a witness. 3SAT formulas are in conjunctive normal form with three terms per clause. Each term is a literal or the complement of a literal.

``In order to solve the set membership problem using 3SAT, we want to generate a 3SAT formula: $\phi$. $\phi$ should be satisfied by the chosen witnesses, it should also be a `hard' instance of 3SAT. We use an algorithm that chooses any formula that is satisfied by the witnesses and has the right number of clauses with equal probability.

``Esponda et al. proposed an algorithm to generate a SAT formula from a specified set of witnesses. SAT is like 3SAT without a limit on the number of terms per clause. Their algorithm may generate a SAT formula that is exponentially long. They don't make any security claims about the security of the generated formulas. They proposed it as a method of storing security parameters on a network.

``Our proposal is a system to generate 3SAT clauses of a specified length which is satisfied by the given witnesses. Not every formula is hard, but we conjecture that, for appropriately chosen parameters, most are.

``The idea behind the protocol is to generate random clauses. We accept a clause if it is satisfied by the witnesses. The resulting formula is satisfied by all of the witnesses.''

I then went through graphic slides describing the centralized and distributed protocols. After explaining them, I continued, ``In the distributed protocol, participants vote using secure elections to determine if a clause should be accepted. We modify an election scheme by Benaloh to count the number of `no' votes cast by each participant to detect cheating. The security of the election scheme is based on secret-sharing.

``The reason that we need to count the `no' votes is that with an unlimited number of `no' votes a participant can insert extra witnesses or even create trap doors allowing many unauthorized witnesses to satisfy the formula. If a participant exceeds the threshold for `no' votes, the protocol is aborted and restarted from the beginning.

``An important parameter for security is the clause density which is clauses divided by variables. The phase boundary is the clause density at which the formulas go from mostly satisfiable to mostly unsatisfiable. The decision problem is believed to be hardest just above the phase boundary. We conjecture that the problem of finding witnesses is hardest well above the phase boundary where the formulas are over-constrained.

``The difficulty of brute-force search is exponential on the number of variables. We recommend a clause density of eight. To square the difficulty of breaking the system, as is needed for the post-quantum model, it is necessary to double the number of variables and clauses.

``Grover's algorithm is a quantum algorithm which provides quadratic speed-up for search problems. It has been shown optimal for the general search problem on a random oracle. This suggests that it may be optimal for 3SAT.

``We recommend the following parameters for our system. For a classical adversary we suggest 128 variables and 1024 clauses, for a quantum adversary we suggest 256 variables and 2048 clauses.''

Someone asked how I chose the clause density.

``I wanted the clause density to be as high as possible without imposing excessive combinatorial limits on the number of witnesses. Eight turned out to be a near-optimal choice.

``The algorithm is exponential on the number of witnesses, but since it is a small base, $8/7$, the computational limits don't become a factor until we reach a hundred witnesses. We determined what the combinatorial limits are through experimentation and computation-''

``What do you mean by combinatorial limits?'' someone asked.

``The combinatorial limit is the number of witnesses for which there are enough satisfying clauses to make the clause density. We found the combinatorial limit for the recommended values for the classical model to be seventy-two witnesses. We experimentally tested it with seventy witnesses.''

I put up a scatter graph showing the number of rejected clauses for each of the 1024 clauses for seventy witnesses. ``As you can see for seventy witnesses, the maximum number of rejections is 14,000 clauses.'' I put up another graph with the same information for fifty witnesses. ``For fifty witnesses the maximum number of rejections is seven hundred. That means that fifty witnesses is twenty times more efficient than seventy witnesses. Our maxreject formula for determining the threshold of rejections is seldom exceeded by honest participants but will be exceeded if a participant tries to cheat.

``The 3SAT chapter is mostly complete. We need to formalize the set establishment function and describe the distributed protocol in terms of cloned probabilistic Turing machines.

``The 3SAT system requires random numbers. In order to generate these numbers we need a secure and efficient pseudorandom number generator. To develop this we created the Dragonfire cipher.

``The Dragonfire cipher uses balanced keyed S-boxes based on exponentiation modulo a Fermat prime. It is intended to demonstrate that Feistel ciphers can be used to generate random numbers in the post-quantum model. Routine cryptanalytic tests were run using 2,000 hours on the ISSA cluster.

``The idea behind Dragonfire is to choose generators mod 257 from a table. S-boxes are created by exponentiating the generators. Subkeys are created by encrypting bits of the key with another cipher resulting in a property called pseudo-independence. The design is the standard Feistel design with 128-bit blocks.

``We built a random-number generator from Dragonfire with two modes, fast and secure. The random number generator is keyed as well as taking a seed. The NIST randomness test suggests that the output bits look random. The fact that it is deterministic allows participants in a protocol to synchronously generate the same random bits.

``Key features of the Dragonfire cipher include key lengths from 256 bits to 1024 bits. The post-quantum model requires at least 384 bits. The S-boxes are balanced and keyed. They are selected with a sixty-four bit hash of the key. And it has pseudo-independent subkeys so that learning a bit of a subkey doesn't easily lead to a bit of another subkey.

``The research for Dragonfire is complete. The language of the chapter needs work. Stevens filed a provisional patent on Dragonfire in March 2007.''

``Hello, are we going to start soon?'' Josh said over the USB speakers.

``Josh, can you hear us?''

``Hello? Hello?''

``Call him on the cellphone,'' my adviser said.

``My cellphone isn't working.''

She came to the front of the room with her Treo and I gave her the phone number. She called him on speaker. ``Can you hear us?''

``Yes. What happened?'' he asked.

I was examining Onur's laptop, ``It looks like Windows reset the input from the USB speakers to the microphone plug,'' I said.

``Okay, continue the presentation. I can figure out what we covered from the slides.''

``The remaining work to be done on the thesis includes writing the introduction, and conclusion. Also, the related work chapter and quantum adversary section need to be improved.

``The plan is to complete the Dragonfire chapter in December, number theory in February, 3SAT in April, definitions in June, related work in September, and defend the thesis in October 2008. These dates are highly speculative, though.

``Any questions?''

``Yes,'' Josh said through my adviser's cellphone. ``Why not just use the original Shmuely's algorithm.''

I paused to think. I didn't want to even begin to unpack the question with all the history from 1992 and Kevin McCurley's survey, so I decided to address the actual algorithm that Shmuely put out. ``Shmuely's algorithm has an asymptotically large component.''

``I don't remember there being an asymptotically large component, but okay.''

There were a couple of other questions and then the committee repaired to Professor Wetzel's office on the sixth floor of the Babbio Center to discuss the outcome of the proposal. I gave my adviser Josh's number so that they could include him on the speakerphone. I also gave her a USB stick with my presentation on it in case they needed to consult my slides.

After I packed up my laptop and other equipment I went to the sixth floor, which I hadn't been to before as it had just opened the previous month, and found that there were two glass doors coming out from the elevator lobby. I tried the door to the left and it was locked. I assumed that the door on the right was locked and knocked on it until someone let me in. As it turned out, it wasn't locked. I went through a maze of offices looking for one that had Professor Wetzel's name on it. After wandering around for about ten minutes I found it. There was a lounge nearby with a view of the Manhattan skyline and I took a seat in it.

I sat there for what seemed like days. Then I heard my adviser's voice as Professor Wetzel's door opened. I went to Professor Wetzel's office and people were leaving. ``Congratulations,'' my adviser said, ``you passed.''

``Thank you.''

``The committee will send you an email in the next week detailing suggestions that you must do for your final thesis.''

``Okay thanks. Do you have my thumb drive?''

``Yes. Let me find it.'' She started going through her bag. It didn't immediately turn up. She searched for a while and eventually came up with my USB drive. ``Here it is,'' she said. I guessed that they hadn't consulted my slides.

When I got back to the lab, I emailed Josh to apologize for losing him during the presentation. He replied that with my document and my slides he had enough to go on for the process. I promised to find a better technical solution for the thesis defense.