Report

Towards Practical Lattice-Based Public-Key Encryption on Reconfigurable Hardware SAC 2013, Burnaby, Canada Thomas Pöppelmann and Tim Güneysu Horst Görtz Institute for IT-Security, Ruhr-University Bochum, Germany 14. Aug. 2013 Agenda • • • • • Introduction Ring-LWE Encryption Lattice Processor Results Conclusion 14. Aug. 2013 2 Motivation • Advantages of lattices: – Post-quantum security – Security proofs – Versatility • Goal of this work: – Provide a simple and reusable hardware building block • Starting point to solve more advanced implementation problems • Make source code available – Deal with aspects important in practice • Ciphertext expansion • Error rate 14. Aug. 2013 3 Agenda • • • • • Introduction Ring-LWE Encryption Lattice Processor Results Conclusion 14. Aug. 2013 4 Recap: Ideal Lattices • Ideal lattices correspond to ideals in the ring R = / + 1 with being a power of two and being a prime such that = 1 mod 2 (*) – Introduces algebraic structure into previously random lattices – no serious advantage for attackers so far – Most standard lattice problems have an ideal lattice counterpart • Polynomial multiplication is the basic operation – Runtime ( log()) when using the number theoretic transform (NTT) – ∗ = INTT NTT ∘ NTT with , ∈ • Ring-LWE problem requires to distinguish whether samples 1 , 1 , … , are = + with , ∈ , ← or uniformly random – Decisional problem as hard as search – is a small discrete Gaussian distribution (*) Other choices are also possible but this one has emerged as standard for security and efficiency. 14. Aug. 2013 5 LWE-Encryption Gen: Choose ← and 1 , 2 ← . Compute = 1 − ⋅ 2 ∈ R ): , , 1 2 3 Enc(, , ∈ 0,1 ← . = . Ciphertext: [1 = ⋅ 1 +2 , 2 = ⋅ 1 +3 + ] x + x Dec( = [1 , 2 ], 2 ): Output (1 ⋅ 2 +2 ) 1 1 + + 2 x + 1 2 [LP11] Richard Lindner, Chris Peikert: Better Key Sizes (and Attacks) for LWE-Based Encryption. CT-RSA 2011 14. Aug. 2013 6 LWE-Encryption • Parameters: 128-bit CPA security (=256,=7681,=11.32) – Approx. 1600 bit secret key – 3328 bit public key – Message expansion factor 26 • Encoding/Decoding: Small noise 1 1 + 2 2 + 3 still present after decryption – One message bit is encoded into one coefficient of the polynomial (0 ⇒ 0, 1 ⇒ q/2) – May fail with low probability • Optimization – Use different encoding – Remove some LSBs of ciphertext coefficients 14. Aug. 2013 7 Agenda • • • • • Introduction Ring-LWE Encryption Lattice Processor Results Conclusion 14. Aug. 2013 8 Reconfigurable Hardware (FPGA) • Field Programmable Gate Array (FPGA) – A chip containing programmable logic blocks – Logic blocks are connected by a configurable interconnect – Limited number of dedicated „hard-cores“ like block memory or embedded multipliers (DSPs) are available • Hardware is inherently parallel – Time vs. area 14. Aug. 2013 9 The Challenge • Ring-LWE encryption and also other schemes (e.g., signature schemes) basically just require polynomial arithmetic – So far results are only available for polynomial multiplication – Temporary values have to be stored – Operations for addition and subtraction are necessary – An easy interface is required Solution: Build a lattice processor/micro-code engine 14. Aug. 2013 10 Lattice Processor • Supports any power of two > 64 and prime satisfying 1 = mod 2 • Configurable amount of registers (register = polynomial) • Discrete Gaussian sampler using the inverse transform method • Instruction set (simplified): – – – – – – NTT: Perform NTT on register ( log() cycles) 2 PW_MUL: Point-wise multiplication of two polynomials ( cycles) INTT: Perform inverse NTT on register ( log() cycles) 2 ADD: Add two polynomials ( cycles) SUB: Subtract two polynomials ( cycles) MOV: Transfer polynomial or obtain polynomial from the sampler 14. Aug. 2013 11 Lattice Processor 14. Aug. 2013 12 Optimizing Encryption Key Generation 1. 1 , 2 ← . Compute = 1 − ⋅ 2 ∈ R 2. = NTT (), = NTT (), Encryption 1. 1 , 2 , 3 ← 2. 3. 4. 5. 1 = NTT ( 1 ) ℎ1 = ∘ 1 ℎ2 = ∘ 1 6. 2 = INTT ℎ2 + 3 + () 1 = INTT ℎ1 + 2 Note: Straightforward version would require at least two multiplications: 3 log +6n 14. Aug. 2013 3 1 2 log(n) + 2 1 log() + 2 2 1 log + 3 2 3 = log + 12 2 13 Agenda • • • • • Introduction Ring-LWE Encryption Lattice Processor Results Conclusion 14. Aug. 2013 14 Results • Implemented encryption scheme on Spartan-6 and Virtex-6 for medium security (n=256,q=7681) and high security (n=512, q=12289) • Core supports encryption, decryption and key generation • Gaussian sampler is bounded with relatively low precision 14. Aug. 2013 15 Performance and Resources Post-place-and-route performance on a Virtex-6 LX75T FPGA. 14. Aug. 2013 16 Comparison with Previous Work • Compared to previous implementation by Göttert et al. from CHES 2012 – Three times slower – Up to 60 times lower area • While speed is important the design has to fit onto a reasonably sized FPGAs – Hardware allows parallel placement to make up for lower speed • Higher flexibility with one general purpose core (Gen/Enc/Dec) [Göttert et al.] Norman Göttert, Thomas Feller, Michael Schneider, Johannes Buchmann, Sorin A. Huss: On the Design of Hardware Building Blocks for Modern Lattice-Based Encryption Schemes. CHES 2012 14. Aug. 2013 17 Comparison with Other Schemes 14. Aug. 2013 18 Agenda • • • • • Introduction Ring-LWE Encryption Lattice Processor Results Conclusion 14. Aug. 2013 19 Future Work and Conclusion Conclusion • Flexible building block for a large number of applications in ideal lattice-based cryptography • Source code (VHDL) of the encryption scheme/lattice processor available for evaluation at http://www.sha.rub.de/research/projects/lattice/ Future Work • Side-channel evaluation • Bimodal Lattice Signature Scheme (BLISS), Crypto 2013 • Performance and resource optimization • Implementation and acceleration of high-level constructions like homomorphic encryption or IBE 14. Aug. 2013 20 Towards Practical Lattice-Based Public-Key Encryption on Reconfigurable Hardware SAC 2013, Burnaby, Canada Thomas Pöppelmann and Tim Güneysu Horst Görtz Institute for IT-Security, Ruhr-University Bochum, Germany 14. Aug. 2013 Thank You for Your Attention! Any Questions?