### slides - SAC 2013

```Towards Practical Lattice-Based Public-Key
Encryption on Reconfigurable Hardware
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
– 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
– 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
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