---
# System prepended metadata

title: 2020summerIntern wiki

---

# 2020summerIntern wiki
## Home
Welcome to the 2020summerIntern wiki!

This wiki is the main source of documentation for developers working with (or contributing to) the 2020summerIntern project. 

| About 2020summerIntern | Setup Guide | Technical Documentation |
| :--------: | :--------: | :--------: |
| ![](https://i.imgur.com/yuDFrbe.png) | ![](https://i.imgur.com/w7GFrUj.png) | ![](https://i.imgur.com/fgqjqiV.png) |
| [About 2020summerIntern](Introduction) | [Setup Guide](SetupGuide) | [Technical Documentation](TechnicalDocumentation) |
| Introducing 2020summerIntern - why we built it and what it does.    | A step-by-step guide to running 2020summerIntern.     | Detailed technical documentation on 2020summerIntern.    |

## <a name="Introduction">Intorduction
This repository implements multiplication with NTT on different post quantum schemes (see [NIST Round2](https://csrc.nist.gov/projects/post-quantum-cryptography/round-2-submissions) and [NIST Round3](https://csrc.nist.gov/Projects/post-quantum-cryptography/round-3-submissions)).

Tutor by [Bo-Yin Yang](https://github.com/boyin) during 2020 summer Intern.

Meeting photos can be found [here](https://drive.google.com/drive/folders/1XCzXYBdd-T1l_sjrhZ52pq8GvpXZk_Ot?usp=sharing).

## <a name="TechnicalDocumentation">Technaical Documentation
- [NTRUPrime_test](#NTRUPrime_test)
- LAC
- ntruhrss701_test
- ntruhps_test
- saber_test

## <a name="NTRUPrime_test"> NTRUPrime_test
### 2048NTT
#### This directory is made for NTRUPrime where prime p is from 768 to 1024.
The inverse NTT is designed with Gentleman-Sande algorithm.
- NTT_c_functions.h  
Write 2048NTT assembly logic with c codes.
- 2048NTT is designed as  
    - forward  
        3 layers -> 3 layers -> 3 layers  
    - multiply     
        4x4 convolution 
    - inv  
        3 layers <- 3 layers <- 3 layers 
    - pack to  
        $x^{p}$ $-1$

### 7x256_NTT
#### This directory is made for NTRUPrime where prime p is from 769 to 896.
The inverse NTT is designed with Gentleman-Sande algorithm.
- 7x256_NTT is with cooley-tukey    
    - forward NTT7 -> 7 forward NTT256 ( 3 layers -> 3 layers -> 4x4 convolution) -> 7 inv NTT256 (overlap with convolution) -> inv NTT7
    - pack to  
        $x^{p}$ $-1$

### For prime p from 513 to 768, please reference [NTRUPrime with Good's trick](https://github.com/strongshih/NTRUPrime)

![](https://i.imgur.com/iRNZU6d.png)

We do the Good's trick by b method. (When we mention Good's mapping in this repository we usually mean CRT mapping.)

image reference: [Fast Fourier Transforms: A Tutorial Review and a State of the Art: Chapter 7.5](http://www.dsp-book.narod.ru/DSPMW/07.PDF)

## <a name="ntruhrss701_test"> ntruhrss701_test
### ntruhrss701_test
#### Good's trick 
The inverse NTT is designed with Cooley-Tukey algorithm.
- With Good's trick 768 (3x512)
    - forward 3 layers with Good mapping (positions of zero values won't be loaded ) -> forward 3 layers -> forward 3 layers -> inv 3 layers -> inv 3 layers -> inv 3 layers with Good mapping -> pack to x^701 -1
- related work
    - [ntruhrss701_test](ntruhrss701_test)
    - [NTRUPrime](https://github.com/strongshih/NTRUPrime)

## <a name="LAC"> LAC
### LAC_1024
#### This directory is made with NTT1024 for lac-192 and lac-256 multiplication.
- big and small are both 8 bit
- forward 3 layers -> forward 3 layers -> forward 3 layers -> 2x2 convolution -> inv 3 layers -> inv 3 layers -> inv 3 layers
### LAC_512
#### This directory is made with NTT512 for lac-128 and lac-LIGHT multiplication.
- big and small are both 8 bit
- forward 3 layers -> forward 3 layers -> forward 3 layers -> point to point mul -> inv 3 layers -> inv 3 layers -> inv 3 layers
### refer to our [public repo](https://github.com/MarvinChung/LAC-m4/tree/master/LAC) for more informtaion

## <a name="ntruhps"> ntruhps
### ntruhps
#### length_509
The inverse NTT is designed with Gentleman-Sande algorithm.
- big and small are both 16 bit
- with NTT1024
    - forward 4 layers -> forward 4 layers -> 4x4 convolution -> inv 3 layers -> inv 3 layers -> inv 3 layers -> inv 2 layers with pack

#### length_677
The inverse NTT is designed with Cooley-tukey algorithm.
- big and small are both 16 bit
- with Good's trick 768 (3x512)
- forward 3 layers with Good mapping (positions of zero values won't be loaded ) -> forward 3 layers(4,5,6) -> forward 3 layers(7,8,9) -> inv 3 layers(1,2,3) -> inv 3 layers(4,5,6) -> inv 3 layers with Good mapping -> pack to $x^{821} -1$
- related work
    - [ntruhrss701_test](ntruhrss701_test)
    - [NTRUPrime](https://github.com/strongshih/NTRUPrime)

#### length_821_64x27
The inverse NTT is designed with Gentleman-Sande algorithm.
- big and small are both 16 bit
- with mixed radix Cooley-Tukey (9x64x3)
    - 9  
     Implement with radix 3 NTT
    - 64  
     Implement with NTT64 
         - forward 3 layers -> forward 3 layers -> inv 3 layers -> inv 3 layers 
    - 3  
        3x3 convolution
    - Inverse :  
    reverse above      
    
## <a name="saber"> saber
### saber

#### firesaber_MatrixVector
The inverse NTT is designed with Gentleman-Sande algorithm.
- matrix dimension
    4x4
- with NTT256
    - forward 3 layers -> forward 3 layers -> 4x4 convolution -> inv 3 layers -> inv 3 layers
- 4x4 x 4x1 -> 4x1
    - 20 forward NTT256, 4 inv NTT256
#### saber_MatrixVector
The inverse NTT is designed with Gentleman-Sande algorithm.
- matrix dimension
    3x3
- with NTT256
    - forward 3 layers -> forward 3 layers -> 4x4 convolution -> inv 3 layers -> inv 3 layers
- 3x3 x 3x1 -> 3x1
    - 12 forward NTT256, 3 inv NTT256
#### lightsaber_MatrixVector
The inverse NTT is designed with Gentleman-Sande algorithm.
- matrix dimension
    2x2
- with NTT256
    - forward 3 layers -> forward 3 layers -> 4x4 convolution -> inv 3 layers -> inv 3 layers
- 2x2 x 2x1 -> 2x1
    - 6 forward NTT256, 2 inv NTT256

### Setup Guide
#### Installation
- arm-none-eabi-toolchain  
- [stlink](https://github.com/stlink-org/stlink) (use brew for mac)
- [driver for mac](http://www.prolific.com.tw/US/ShowProduct.aspx?p_id=229&pcid=41)
- [For ubuntu see this tutorial](https://github.com/shigurefox/Tutorial-for-stm32f429/blob/master/README.md)
- perpare arm-none-eabi-gdb (ubuntu shold be gdb-multiarch)

#### Prepare libopencm3

```
cd libopencm3
make
```

#### Preprare Cortex m4
```
ls /dev/
should see tty.usbserial-0001 or ttyUSB0 
```