# 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 |
| :--------: | :--------: | :--------: |
|  |  |  |
| [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)
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
```
Sign in with Wallet
Connect another wallet