Applying Cryptographic Acceleration Techniques to Error Correction

Modular reduction is the basic building block of many public-key cryptosystems. BCH codes require repeated polynomial reductions modulo the same constant polynomial. This is conceptually very similar to the implementation of public-key cryptography where repeated modular reduction in \(\mathbb {Z}_n\) or \(\mathbb {Z}_p\) are required for some fixed n or p. It is hence natural to try and transfer the modular reduction expertise developed by cryptographers during the past decades to obtain new BCH speed-up strategies. Error correction codes (ECCs) are deployed in digital communication systems to enforce transmission accuracy. BCH codes are a particularly popular ECC family. This paper generalizes Barrett’s modular reduction to polynomials to speed-up BCH ECCs. A BCH(15, 7, 2) encoder was implemented in Verilog and synthesized. Results show substantial improvements when compared to traditional polynomial reduction implementations. We present two BCH code implementations (regular and pipelined) using Barrett polynomial reduction. These implementations, are respectively 4.3 and 6.7 faster than an improved BCH LFSR design. The regular Barrett design consumes around 53 \(\%\) less power than the BCH LFSR design, while the faster pipelined version consumes 2.3 times more power than the BCH LFSR design.

1. 1.

   The scalar product of the two vectors is equal to 0.

2. 2.

   where b(x) is the remainder of the division of c(x) by g(x).

3. 3.

   Considered in big endian order.

Authors and Affiliations

1. Sorbonne Universités, Université Paris II, 12 Place du Panthéon, 75231, Paris, France

   David Naccache & Rodrigo Portella do Canto

2. Département d’Informatique, École Normale Supérieure, 45, Rue d’Ulm, 75230, Paris Cedex 05, France

   Rémi Géraud, Diana-Ştefania Maimuţ & David Naccache

3. University Politehnica of Bucharest, 313 Splaiul Independenţei, Bucharest, Romania

   Emil Simion

4. Ingenico Group, 28–32 Boulevard de Grenelle, 75015, Paris, France

   Rémi Géraud

Corresponding author

Correspondence to Diana-Ştefania Maimuţ .

Editors and Affiliations

1. Bucharest, Romania

   Ion Bica

2. Departement d Informatique, Ecole Normale Superieure, Paris, France

   David Naccache

3. Advanced Technologies Institute , University Politehnica of Bucharest, Bucharest, Romania

   Emil Simion

A Polynomial Barrett Complexity

We decompose the algorithm’s analysis into steps and determine at each step the cost and the size of the result. Size is measured in the number of terms. In all the following we assume that polynomial multiplication is performed using traditional cross product. Faster (e.g. \(\nu \)-dimensional FFT [13]) polynomial multiplication strategies may grandly improve the following complexities for asymptotically increasing \({\varvec{L}}\) and \(\nu \).

Given our focus on on-line operations we do not count the effort required to compute K (that we assume given). We also do not account for the partial multiplication trick for the sake of clarity and conciseness.

Let \(\varvec{\omega } \in \mathbb {Z}^{\nu }\), in this appendix we denote by \(||\varvec{\omega }||\) the quantity

1. 1.

   \(Q \gg {\varvec{y}}_\mathbf 0 \)

   1. 1.1.

      Cost: lm(Q) is at most \(\langle L,... , L \rangle \) hence Q has at most \(L^{\nu }\) monomials. Shifting discards all monomials having exponent vectors \(\varvec{\omega }\) for which \(\exists j\) such that \(\omega _j < y_{j,0}\). The number of such discarded monomials is \(\mathrm{O}(||{\varvec{y}}_\mathbf 0 ||)\), hence the overall complexity of this step is:

      $$\begin{aligned}\mathrm{cost}_1 = \mathrm{O}((L^{\nu }-||{\varvec{y}}_\mathbf 0 ||)\nu ) = \mathrm{O}((L^{\nu }-\prod _{j=1}^{\nu }y_{j,0})\nu ).\end{aligned}$$
   2. 1.2.

      Size: The number of monomials remaining after the shift is

      $$\begin{aligned}\mathrm{size}_1 = \mathrm{O}(L^{\nu } -||{\varvec{y}}_\mathbf 0 ||) = \mathrm{O}(L^{\nu }-\displaystyle \prod _{j=1}^{\nu }y_{j,0}).\end{aligned}$$
2. 2.

   \(K(Q \gg {\varvec{y}}_\mathbf 0 )\)

   Because K is the result of the division of \(h(L) = \displaystyle \prod _{j=1}^{\nu } x_j^L\) by P, the leading term of K has an exponent vector equal to \({\varvec{L}}-{\varvec{y}}_\mathbf 0 \). This means that K’s second biggest term can be \(x_1^{L-y_{1,0}} \displaystyle \prod _{j=2}^{\nu }x_j^L.\) Hence, the size of K is

   $$\begin{aligned}\mathrm{size}_K = \mathrm{O}((L-y_{1,0})L^{\nu -1}).\end{aligned}$$
   1. 2.1.

      Cost: The cost of computing \(K(Q \gg {\varvec{y}}_\mathbf 0 )\) is

      $$\begin{aligned} \mathrm{cost}_2 = \mathrm{O}(\nu \times \mathrm{size}_1 \times \mathrm{size}_K).\end{aligned}$$
   2. 2.2.

      Size: The size of \(K(Q \gg {\varvec{y}}_\mathbf 0 )\) is determined by lm\((K(Q \gg {\varvec{y}}_\mathbf 0 ))=\) lm\((K) \times \)lm\((Q \gg {\varvec{y}}_\mathbf 0 )\) which has the exponent vector \({\varvec{u}}=({\varvec{L}}-{\varvec{y}}_\mathbf 0 ) + \langle L-y_{1,0},L,... , L \rangle \).

      $$\begin{aligned} \mathrm{size}_2 = \mathrm{O}(||{\varvec{u}}||)&= \mathrm{O}(2(L-y_{1,0})\displaystyle \prod _{j=2}^{\nu }(2L - y_{j,0}))\\&= \mathrm{O}((L-y_{1,0})\displaystyle \prod _{j=2}^{\nu }(2L - y_{j,0})). \end{aligned}$$
3. 3.

   \(B=(K(Q \gg {\varvec{y}}_\mathbf 0 ))\gg ({\varvec{L}}-{\varvec{y}}_\mathbf 0 )\)

   1. 3.1.

      Cost: The number of discarded monomials is \(\mathrm{O}(||{\varvec{L}}- {\varvec{y}}_\mathbf 0 ||)\), hence the cost of this step is

      $$\begin{aligned} \mathrm{cost}_3 = \mathrm{O}((2(L-y_{1,0}) \prod _{j=2}^{\nu }(2L-y_{j,0})- \prod _{j=1}^{\nu }(L-y_{j,0}))\nu ).\end{aligned}$$
   2. 3.2.

      Size: The leading monomial of B has the exponent vector \({\varvec{u}}-{\varvec{L}}-{\varvec{y}}_\mathbf 0 \) which is equal to \(\langle L-y_{1,0} ,L,... ,L\rangle \). We thus have \(\mathrm{size}_B = \mathrm{size}_K\).

4. 4.

   BP

   The cost of this step is

   $$\begin{aligned} \mathrm{cost}_4 = \mathrm{O}(\nu \times \mathrm{size}_B \times \mathrm{size}_P) = \mathrm{O}(\nu \times \mathrm{size}_B \times ||{\varvec{y}}_\mathbf 0 ||).\end{aligned}$$
5. 5.

   Final subtraction \(Q-BP\)

   The cost of polynomial subtraction is negligible with respect to \(\mathrm{cost}_4\).

6. 6.

   Overall complexity

   The algorithm’s overall complexity is hence

   $$\begin{aligned}\max (\mathrm{cost}_1, \mathrm{cost}_2,\mathrm{cost}_3,\mathrm{cost}_4) = \mathrm{cost}_2.\end{aligned}$$

B Polynomial Barrett: Scheme Code

\(p_1(x)=\sum _{i=0}^{7}(10+i)x^i\) and \(p_2(x)=x^3+x^2+110\)

(define p1 ’((7 17) (6 16) (5 15) (4 14) (3 13) (2 12) (1 11) (0 10)))

(define p2 ’((3 1) (2 1) (0 110)))

;shifting a polynomial to the right

(define shift (lambda (l q)

if (or (null? l) ( \(<\) (caar l) q)) ’() (cons (cons (- (caar l) q) (cdar  l))

(shift (cdr l) q)))))

;adding polynomials

(define add (lambda (p q)

(degre (if ( \(>\) = (caar p) (caar q)) (cons p (list q)) (add q p)))))

;multiplying a term by a polynomial, without monomials \(\prec x^{\text{ lim }}\)

(define txp (lambda (terme p lim)

(if (or (null?p) ( \(>\) lim (+ (car terme) (caar p)))) ’() (cons (cons (+ (car terme)

(caar p)) (list (* (cadr terme) (cadar p)))) (txp terme (cdr p) lim)))))

;multiplying a polynomial by a polynomial, without monomials \(\prec x^{\text{ lim }}\)

(define mul (lambda (p1 p2 lim)

(if p1 (cons (txp (car p1) p2 lim) (mul (cdr p1) p2 lim)) ’())))

;management of the exponents

(define sort (lambda (p n)

(if p (+ ((lambda(x) (if x (cadr x) 0)) (assoc n (car p))) (sort (cdr p) n)) 0)))

(define order (lambda (p n)

(if( \(>\) 0 n) ’() (let ((factor (sort p n))) (if (not (zero?factor))

(cons (cons n (list factor)) (order p (-n 1))) (order p (-n 1)))))))

(define degre (lambda(p) (order p ((lambda(x)(if x x -1)) (caaar p)))))

;Euclidean division

(define divide (lambda (q p r)

(if (and p ( \(<\) = (caar p) (caar q))) (let ((tampon (cons (- (caar q)(caar p))

(list (/ (cadar q) (cadar p)))))) (divide (add (map (lambda(x) (cons (car x)

(list (-cadr x)))))(txp tampon p -1)) q) p (cons tampon r))) (reverse r)))

(define division (lambda (q p) (divide q p ’())))

;Barrett(k, L, last_P and Y representing K, L, P and \({\varvec{y}}\))

(define k)

(define y)

(define L 8)

(define last)

(define barrett (lambda (q p)

(if (eq ? last p) (letrec ((g (caar q)) (h (- (+ g 1) y))) (shift (degre (mul

(shift k (-L g 1)) (shift q y) h)) h)) (begin (set! k (division (list (cons L ’(1) )) p)) (set! y (caar (set! last p))) (barrett q p)))))

Reprints and permissions

© 2015 Springer International Publishing Switzerland

Policies and ethics