A Domain-Specific Language for Efficient Cryptographic Engineering

實作密碼學系統時,常見許多多維代數結構間的運算。若要在較低階的組合語言上實作,必須轉換成基本元素的運算。運算數量龐大時,必須有自動化工具來輔助。此外,在低階語言上無法高階地描述系統或演算法,增加程式設計者的困難,以及出錯的可能性。 我們提出一個嵌於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 2