實作密碼學系統時,常見許多多維代數結構間的運算。若要在較低階的組合語言上實作,必須轉換成基本元素的運算。運算數量龐大時,必須有自動化工具來輔助。此外,在低階語言上無法高階地描述系統或演算法,增加程式設計者的困難,以及出錯的可能性。
我們提出一個嵌於Haskell中的特定領域語言,讓程式設計者能以方便的語法和多維的代數結構,描述密碼演算法和系統。程式會被表示成樹狀的表示式,並且由編譯器自動展開代數結構的運算,轉成中間語言,再進行優化並產生目標語言。
編譯器結合了兩個優化器,並且實作了兩種目標語言,分別是Hydra處理器上的組合語言,以及C++,支援的代數結構有擴張體和矩陣。程式設計者也能加入自己所需的代數結構、優化或是目標語言。我們在此特定領域語言上實作了兩個應用:最佳配對和一個基於LWE的密鑰交換系統。
使用此特定領域語言實作密碼系統,可將數學演算法、優化和輸出語言各自獨立,節省重複的工作,並且程式設計者在實作時可把重點放在密碼系統高階的描述。

Multidimensional algebraic structures are common in the description of cryptographic systems. They have to be translated to computations between basic elements by automation before being implemented on low-level assembly languages. Besides, the programmer cannot write programs in a high-level way, which makes them more error-prone.
In this thesis, we propose a domain-specific language embedded in Haskell, so that the programmer can implement cryptographic systems in convenient syntax. The computations of algebraic structures will be expanded, supporting extension fields and matrices.
Our compiler is combined with two optimizers, and supports two target languages: Hydra assembly and C++. The programmer can add his own algebraic structures, optimizations, and target language as needed. We also implement two applications in this DSL: optimal pairing and a key exchange with LWE.
The algorithm description, optimizations and code generations is separated and independent. The programmer can focus on the high-level descriptions of the cryptographic systems.

1 Introduction 1
1.1 Embedded Domain-Specific Language.................. 2
1.2 Hydra ................................... 3
1.3 Contribution................................ 3
2 Overall Structure 5
3 Language Embedding 6
3.1 Expressions ................................ 6
3.1.1 Standard Mathematical Operators................ 7
3.1.2 Functions ............................. 7
3.2 Let-sharing ................................ 8
3.3 Control Flow ............................... 10
4 Algebraic Structure Expansion 11
4.1 ExtensionField .............................. 11
4.2 A Small Example............................. 11
4.3 Haskell For Maths............................. 12
4.3.1 BaseField............................. 13
4.3.2 Extension Field.......................... 13
4.4 For General Algebraic Structures .................... 15
5 Compiling Embedded Language 17
5.1 Intermediate Representation....................... 17
5.2 Expressions to IR............................. 18
5.2.1 Type Class ............................ 18
5.2.2 Default Implementation ..................... 18
5.2.3 Instance Example......................... 19
6 Optimizations and Code Generation 21
6.1 Common Subexpression Elimination .................. 21
6.2 Linear Register Allocation ........................ 21
6.3 Code Generation ............................. 22
6.3.1 Hydra ............................... 22
6.3.2 C++................................ 23
7 Applications 24
7.1 Pairing................................... 24
7.2 Key Exchange Protocol from LWE ................... 25
8 Summary 26
8.1 RelatedWork ............................... 26
8.2 Future Work................................ 26
Bibliography 28

[Axe12] Emil Axelsson. A generic abstract syntax model for embedded languages. In ACM SIGPLAN Notices, volume 47, pages 323–334. ACM, 2012.
[BCSS98] Per Bjesse, Koen Claessen, Mary Sheeran, and Satnam Singh. Lava: hardware design in haskell. In ACM SIGPLAN Notices, volume 34, pages 174–184. ACM, 1998.
[Che14] W.-H. Chen. A simplification tool for expressions over binary fields using max-sat solver. Master’s thesis, National Taiwan University, June 2014.
[CHH+] Y.-A. Chang, W.-C. Hong, M.-C. Hsiao, B.-Y. Yang, A.-Y. Wu, and C.-M. Cheng. Hydra: An energy-efficient programmable cryptographic coprocessor supporting elliptic-curve pairing over fields of large char- acteristics. To appear in the 9th International Workshop on Security (IWSEC 2014), Hirosaki, Japan, Aug. 2014.
[CKL+ 11] Manuel MT Chakravarty, Gabriele Keller, Sean Lee, Trevor L McDonell, and Vinod Grover. Accelerating haskell array codes with multicore gpus. In Proceedings of the sixth workshop on Declarative aspects of multicore programming, pages 3–14. ACM, 2011.
[DL12] Jintai Ding and Xiaodong Lin. A simple provably secure key exchange scheme based on the learning with errors problem. IACR Cryptology ePrint Archive, 2012:688, 2012.
[EFDM03] Conal Elliott, Sigbjorn Finne, and Oege De Moor. Compiling embedded languages. Journal of Functional Programming, 13(3):455–481, 2003.
[Gil09] Andy Gill. Type-safe observable sharing in haskell. In Proceedings of the 2nd ACM SIGPLAN symposium on Haskell, pages 117–128. ACM, 2009.
[Hug95] John Hughes. The design of a pretty-printing library. In Advanced Functional Programming, pages 53–96. Springer, 1995.
[Hut92] Graham Hutton. Higher-order functions for parsing. J. Funct. Program., 2(3):323–343, 1992.
[KO63] Anatolii Karatsuba and Yu Ofman. Multiplication of multidigit numbers on automata. In Soviet physics doklady, volume 7, page 595, 1963.
[LM99] Daan Leijen and Erik Meijer. Domain specific embedded compilers. In ACM Sigplan Notices, volume 35, pages 109–122. ACM, 1999.
[MCKL13] Trevor L McDonell, Manuel MT Chakravarty, Gabriele Keller, and Ben Lippmeier. Optimising purely functional gpu programs. In Proceedings of the 18th ACM SIGPLAN international conference on Functional programming, pages 49–60. ACM, 2013.
[MM10] Geoffrey Mainland and Greg Morrisett. Nikola: embedding compiled gpu functions in haskell. In ACM Sigplan Notices, volume 45, pages 67–78. ACM, 2010.
[Mon85] Peter L Montgomery. Modular multiplication without trial division. Mathematics of computation, 44(170):519–521, 1985.
[PNH02] Izzet Pembeci, Henrik Nilsson, and Gregory Hager. Functional reactive robotics: An exercise in principled integration of domain-specific languages. In Proceedings of the 4th ACM SIGPLAN international conference on Principles and practice of declarative programming, pages 168–179. ACM, 2002.
[SHH+13] Jie-Ren Shih, Yongbo Hu, Ming-Chun Hsiao, Ming-Shing Chen, Wen- Chung Shen, Bo-Yin Yang, An-Yeu Wu, and Chen-Mou Cheng. Securing m2m with post-quantum public-key cryptography. IEEE J. Emerg. Sel. Topics Circuits Syst., 3(1):106–116, 2013.
[Ver10] Frederik Vercauteren. Optimal pairings. Information Theory, IEEE Transactions on, 56(1):455–461, 2010.
[Yan13] S.-Y. Yang. Code generation for fast pseudo-mersenne prime field arithmetic on arm processors. Master’s thesis, National Taiwan University, July 2013.