Basics of R-LWE key exchange (more information here):

Alice: $e, s \leftarrow \chi$ $b=as+e$

Bob: $e', s' \leftarrow \chi$ $b'=as'+e'$

Alice’s key: $\to s*(as' + e') = ass' + se'$

Bob’s key: $\to s'*(as + e) = ass' + s'e$

As you can see, $\to s*(as' + e')$$\neq$$s'*(as + e)$ but they are close considering that error is relatively small. This is why we need a reconciliation method that sends an special signal (such that message interceptor cannot use that signal to learn about the shared key) to other party.

Regev method: In 2005, Prof. Oded Regev introduced a R-LWE key exchange protocol. The reconciliation was simple did not need have any signal to be sent. Thus, there was a probability of $\frac{1}{2^{10}}$ that shared key did not match. This method is not practical but it was a great starting point (implementation, test the code).

Ding method: In 2012, Prof. Ding introduced a R-LWE key exchange reconciliation method that I think it was revolutionary. For the first time, it intruded the concept of signaling (or some reconciliation information). This method generated biased key and it should not be used in a real world environment (implementation, test the code).

Peikert method: In 2014, Prof. Peikert introduced a R-LWE key exchange reconciliation method that used the concept of signaling similar to Prof. Ding’s method but fixed the issue of biased key using randomized doubly function. This method is practical, easy to implement and it can be used in a read world environment (implementation, test the code).

newHope method: In 2015, Prof. Schwabe introduced a R-LWE key exchange reconciliation method that used the concept of signaling similar to Prof. Ding’s method, and a generalized randomized doubly function similar to Prof. Peikert’s method but faster to implement (thanks to optimizations in the implementation) and more secure by using relatively smaller modulus, hence, increasing impact of error. This method can be used in a read world environment (implementation, test the code).

Writing a blog which is something I have never done before and by reading my previous blog posts, it is clear that I struggled with a proper number theory library. NTL and FLINT are great number theory packages written in C for people who have studied and used number theory for a long time and speed is their primary concern. On the other hand, there are people like me who have just learned about number theory and want to implement something without spending so much time learning a different programming language and a library that has been around for 10+ years (constantly being improved and new functionalities being introduced to).

I am not a expert in Python (i.e. specially with data structures and dictionaries) but I can implement something in Python although it would take more time in comparison to java. Sage was a perfect combination for me because I am familiar with both Python and some NTL. I was able to quickly start coding with Sage and I never went back to use NTL or trying to re-implement the library in java and then write my code in java.

I give Sage a lot of credit for it’s powerful polynomial parser. After trying to implement Implement a Multivariable Polynomial ring using java and seeing how difficult it is to implement a proper polynomial parser to works with edge cases, although it was a rewarding experience, it was time consuming. It took my about a month to write a library by working day and night.

I also give Sage credit for it’s LLL implementation. I used NTL’s LLL implementation. Getting it working with NTL’s BigInteger implementation is not straightforward. However, using LLL in sage is just one line of code: LLL(matrix)

Sage uses many open source libraries and links them all together using Python. It is a simple idea but it required clever implementation which Sage truly delivers. It is fascinating to see a smart type system that handle the linkage between all those open source libraries.

I highly recommend to watch the following presentation by William Stein (creator of Sage) in which he discusses history behind Sage and why it is truly a programming language to rule them all!

Fresh out of my summer internship at Northwestern mutual and working extensively with JavaScript and Node.js, I was reading about LLL and basics of lattice and lattice cryptography. I tried installing NTL on my Windows machine. It was a nightmare. Lack of documentation for such an important library was just astonishing. I did not have any success with Windows. Thereafter, I installed Ubuntu (in fact, I never switched backed to Windows) and had some success with NTL on Ubuntu. But the complication of NTL’s type system and again lack of documentation halted my efforts.

I decided to implement LLL myself to see how complicated it would be. My language of choice was JavaScript. Bad idea. Lack of built-in BigInteger was a limitation. Not to mention, concept of Matrix does not exist in JavaScript, I simply used 2 dimensional array instead. Furthermore, I had to implement Gram-Schmidt process and Matrix determinant for an arbitrarily sized matrix all from scratch. My code worked after all, but slow speed and lack of modular implementation turned this mini project to one of my least favorite and cumbersome projects. Most importantly, it was a rewarding effort. I was able to see the promise of polynomial running time of lattice reduction with respect to delta constant.

Shortly after I finished implementing the code, I learned that Sage math has a built-in LLL implementation which I did not know about. After learning about it, I started reading more about Sage math.

GitHub link

After disappointing and certainty a long fail journey trying to learn NTL (Number Theory package written in C++), I decided to write my own Ring implementation. In short, it was a difficult talk but I learned a lot.

Let’s discuss the details. I needed a two classes: Monomial and Ring plus enum class to handle operations. Now, the key design choice is how to store the relationships between Monomials and operations. For example, this library written in java as well, uses String to store the relationship. The last thing a programmer wants is being confused by String manipulations. Therefore, I used Array of Objects to store the relationships.

After successfully implementing Monomial, Ring and operations (enum) classes, it was a time to tackle the most challenging part. Handling evaluation and making sure order of operations is preserved. To handle that, I needed to loop through the Array 4 times (add, multiply, divide, subtract). Thereafter, for every two Monomial in Array (first pass is for multiplication, second for division and so on), evaluate them and replace them with the evaluated result back in the Array. In the end, result Array should contain only one element it should be a BigInteger value.

As of now, code supports String parsing a complex Polynomial Ring including nested Rings. The followings are just some examples that code is able evaluate correctly thanks to the specified order of operations for each operation:

java docs (Hosted by GitHub).

As part of Intelligent user interface course, we‌ (students) were asked to come up with a project that demonstrates our understanding on course materials. By materials, I mean research papers that we read every week. To come up with a project idea, I looked for a problem. Something that I can do better.

That thing for me was UWM website (main page). It is inefficient in delivering the content. It is too simply designed that we can question it’s existence. Navigating a website is unhelpful. I believe that home page of university website should be customized based on user’s classes after user (i.e. student) is logged in. To make the matter worse, UWM students have to go to another website called “D2L“, log-in and then see their class discussions. To see the official class schedule, students have to visit another website called “PAWS“. This is what I call inconvenience. Now, what is not very easy to see in class discussions section of D2L is that Professors/Instructors are also able to see the discussion. Hence, students may feel uncomfortable sharing their thoughts and asking certain questions (e.g. about homework that is due). It is a recipe for failure.

I came up with a portal/website called “UWM Now” that addresses these issue. It provides a prejudice-free environment for students to communicate, discuss and learn together. This portal addresses all the deficiency that I mentioned plus interesting features such as weather (current temperature, forecast hourly and daily), news (Twitter style, 140 words) and a simple tool for evaluating a difficulty of student’s schedule.

Now, let’s focus on the code that make such a system possible. I used Node.js, Express.js and SQLite. However, this was the time I used a ORM to handle database interactions. The ORM I chose was Sequelize.js which was initially difficult to learn but I quickly got used to it. Learning a promises and resolving a promise was definitely a challenge. But it was worth the time learning a new tool. I will always try to avoid writing a pure SQL queries in String and executing them. It takes too much time.

My portal got a mixed reaction by my Professor. She liked some parts and expected more in other parts. But, the fact is all other teams had active team members. But my team mate was not helpful at all. He did not write a single line of code. I practically did everything by myself and I simply run out of time and patience. However, I hope my code would act as a good starting point for others.

Demo video (Hosted by GitHub).

Overview video (Hosted by GitHub).

PowerPoint presentation (Hosted by GitHub).

Project report (Hosted by GitHub).

I believe it is not practical to go to an exam without proper studying and major part of any study is to look over sample questions or previous exams. As a person who was going to take a naturalization exam, which is a exam that I needed to pass in order to become U.S. citizen after five years of waiting. It is an important exam for any green card holder. It is a major step forward.

While studying the preparation handbook, I felt the need of a website that uses scoring system to make the learning more enjoyable (gamification). A website that simplifies the learning and make it more efficient. I could not find such a website on the web. Hence, I wrote my own. I used “free to download” audio and photos from USCIS website and created a data structure of them to present to user. In addition, I used SQLite to create a simple to use database of users and their scores.