Analysis of Ring-LWE Ciphertext Compression and Error Correction

This report summarizes the paper "Ring-LWE Ciphertext Compression and Error Correction" by Markku-Juhani O. Saarinen, focusing on lattice-based cryptography for lightweight post-quantum applications. The paper explores ciphertext transformation to compress Ring-LWE ciphertexts, enabling efficient decryption in ultra-lightweight environments like IoT devices and smart cards. It introduces XECC, a fast multi-error correcting code, and discusses the construction of trunc8, a Ring-LWE encryption and authentication system. The analysis includes implementation, security, and performance, demonstrating significant ciphertext size reduction while maintaining security. The author emphasizes the importance of error analysis and the derivation of failure bounds for n-bit error correction. The report highlights the paper's structured approach, detailed methodology, and comparison with other lattice-based encryption schemes, showcasing trunc8's ability to exceed 128-bit security against quantum attacks. The recommendation section suggests that the paper would benefit from more detailed explanations of the methodologies used and a more comprehensive conclusion to summarize the key findings. The report also includes a comparison of trunc8 with other encryption methods and discusses the potential of the system in lightweight authentication tokens.

Running head: Ring-LWE Ciphertext Compression and Error Correction
Ring-LWE Ciphertext Compression and Error Correction
Name of the student
Name of the university
Author note

Introduction
The Literature “Ring-LWE Ciphertext
Compression and Error Correction”, presented by
Markku-Juhani O. Saarinen is based on tools for
lightweight post-quantum cryptography. Usually,
cryptosystems uses private or public keys to
encrypt and decrypt cypher text. In this literature
author describes the about some specific lattice
based public key cryptosystems which capable of
transforming cipher text from one lattice to another
without utilizing the any public or private key
knowledge. The working mechanism of such
cryptography is explored with the properties of
lattice transmission. Author used a different
approach by transforming cypher text to achieve
Ring lightweight texts. The other approach is
considered effective decryption of ultra-lightweight
execution marks such as Smart Cards, Internet of
Things and RFID applications [1]. These approach
needs no modification of original encryption
process and any security restrictions. These are
very unique flexibility which can be achieved
through real application based on the lattice-based
cryptography.
Structure:
The Author and publication were able to
provide a professional structure which make the
paper very easy to read and follow the contents
precisely. The writings are presented and divided
into several heading and sub headings along with
the some table and visualizations which makes the
paper more precise and understanding the concept
effectively. The heading of the report is self-
explanatory and the abstract sparks the description
of the Ring-LWE Cryptography. After listed some
of the keywords, author provided a broad
description on the topic which includes
Polynomial-time Quantum algorithms, quantum
technologies, future asymmetric requirement and
other key technology associated with the Ring-
LWE Cryptography [2]. The structure of the paper
is also summarized in the below section of the
introduction. After a basic discussion on several
technology in the introduction section, the broad
description and mechanism is described in the next
sections. They describes the Ring-LWE public key
encryption scheme Lindner-Peikert in the second
section while in section there cypher text
compression technique is introduced. In the next
section, a constant-time error correction as novel
auxiliary algorithms is described along with the
application to authentication, Related Hardware
Considerations, Security and Failure Rate
Estimates, Side-Channel Security and lightweight
implementation [3]. At last the section five draw a
small conclusion on the description. Author also
used forty references to support his approaches
which are also in texted accordingly.
Summary:
Markku-Juhani O. Saarinen were focused
on some certain tools to explore and construct
trunc8, a concrete Ring-LWE encryption and
authentication system. The whole discussion is
around this key area. Author also states in the
literature that the probability of the decryption error
can be increased due to the Cipher text
compression. Author also provide a basic
description of the XECC which is code for fast
multi-error correction. This code enable the
constant time implementation in software. Author
also believes that the error could be measured and
analyzed which will be very useful to derive failure
bonds for n-bit error correction. Author also
performs an experiment on public key encryption
along with an 8 bit AVR target authentication
system. The result shows that the performance
results exceeds the elliptic curve [4]. The result is
also compared with RSA based proposal along with
implementation of Cortex M0 and similar result has
been found with same security level. Author
analyze the result performance along with security
and implementation. The literature shows that
lattice compression technique deduces cipher text
size by more than forty percent at with similar
security level. Previously unreachable ultra-
lightweight platforms are also accessible while
enabling the public key cryptography.
RING-LWEPUBLICKEYENCRYPTION
Author provides a well-structured Ring-
LWE encryption algorithm, “Lindner-Peikert”
which is mentioned in the several light weight
targets in both software and hardware. Firstly,
Author defines the key conventions and notation.
The implementation schema is referred as trunc8,
encompassing of a certain set of parameters and
algorithms. The arithmetic calculation is presented
with several modulo and coefficient. Next, a key is
generated based on global parameter which is
shared among the huge number of public keys [5].
The n-bit strings are the private keys and public
keys. Then the encryption is conducted based on
the n-bit message where author added 0 or 0.5 to
coefficients. The decryption can be done while
decoding the cypher text. Author presents the
following ring multiplication for decryption:
Input: Ciphertext (u,v) and private key s.
1: m ← v
2: for i = 0,1,...n−1 do
3: if si = 1 then
4: for j = 0,1,...,n−i−1 do
5: m[i + j] ← m[i + j] + u[j]
6: end for
7: for j = n−i,...,n−1 do

8: m[i + j −n] ← m[i + j −n]−u[j]
9: end for
10: end if
11: end for Output: Uudecoded plaintext
vector m.
Author adopted the parameter set as a “high-
security”Ring-LWE encryption which was
previously proposed by the G¨ottert [6]. This
parameter set is very popular and utilized in
numerous works of subsequent Ring-LWE
Encryption studies. Author also used other experts
methodology to compare the result with to other
lattice-based encryption.
Attack
parame
ters
Typ
e
(m,
b)
Know
n
Quant
um
Know
n
Classi
cal
Possib
le
Quant
um
JarJar [2] q = 12289, n = 512, σ = 3.464
Primal
(623,
449)
Dua
l
(602
,
448)
119
118
131
130
93
92
NewHope [2] q = 12289, n = 1024, σ =
2.828
Primal
(1100,
967)
Dua
l
(110
0,
962)
256
255
282
281
200
199
BCNS [4] q = 232, n = 1024, σ = 3.192
Primal
(1062,
296)
Dua
l
(105
5,
296)
78
78
86
86
61
61
NTRU-743 [18] q = 212, n = 743, σ =
0.8164
Primal
(613,
603)
Dua
l
(635
,
600)
159
159
176
175
125
124
Medium-Security LWE [17] q = 7681, n
= 256, σ = 4.512
Primal
(345,
222)
Dua
l
(360
,
58
58
64
64
46
46
222)
trunc8 [this work] q = 12289, n = 512, σ
= 4.859
Primal
(660,
496)
Dua
l
(674
,
494)
131
131
144
144
102
102
The above table shows the comparison
result of the presented schema and some other
lattice-based encryption. The result shows that
trunc8 was able to exceed 128 bit security
comparing to other quantum attacks. According to
the methodology, attack exceeds 128-bit security
against all known quantum attacks; attack progress
up to 2012 are plausibly expected.
This figure shows Probability dispersal of
the estimation error specified by Equation. It is
noted that approximation error does not need to be
0 for successful decryption. Usually |x| < q/4 still
works with the scheme.
Application of light weight authentication
tokens
Long term experience has revealed that
the oretical constructs is progressing steadily in this
field. Therefore, higher level attention must be
given to all aspects of secure quantum, practical
and efficient safe executions which could be useful
to develop more effective algorithms. This
embraces auxiliary algorithms and protocols such
as error correcting codes. In order to develop a
simple authentication tokens such as RFID key
only private key implementation is necessary.
Random sampling does not require to decrypt the
trunc8 where such heavier lifting can be achieved
by the interrogator . The token must just be able to
use its secret key to decrypt a test message and to
generate an appropriate response. The ultra-
lightweight public key validation issue has been
earlier noted with elliptic curves in different fields.
Listing : Correct Errors
void xecc fixerr ( uint32 t v [16])
{

int i ;
uint32 t r32 , r31 , r29 , r27 ;
xecc compute (v ); // recompute
r32 = v [ 8 ] ; // get codes
r31 = v [ 9 ] ; // (now ”d i f f s ”)
r29 = v [ 1 0 ] ; r27 = v [ 1 1 ] ;
for ( i = 7; i >= 0; i−−) {
r31 &= 0x7FFFFFFF;
r31 = ( r31 << 1) | ( r31 >> 30);
r29 &= 0x1FFFFFFF;
r29 = ( r29 << 3) | ( r29 >> 26);
r27 &= 0x07FFFFFF;
r27 = ( r27 << 5) | ( r27 >> 22);
// 3−of−4 rule for correcting
v [ i ] ˆ= ( r32 & r31 & ( r29 | r27 ))
| (( r32 | r31 ) & r29 & r27 ); }
}
Recommendation:
The whole literature was consist of
numerous equation and technical terms which
needs very much field knowledge to understand.
Other than that, author used several theories and
methodologies of several experts which are not
explained in the literature. Author could have
mention those theories and methodologies more
precisely. Even though the structure of the
literature is very god and maintained, the
conclusion part is too short and does not summarize
the whole literatures at all.
Conclusion:
They labelled a method for compacting
Ring-LWE cipher texts and the associated
decryption algorithm. The new algorithm enables
comprehension on hardware and microcontroller
targets which previously have not allowed
implementation of private key operationsIn this
literature author describes the about some specific
lattice based public key cryptosystems which
capable of transforming cipher text from one lattice
to another without utilizing the any public or
private key knowledge. The working mechanism of
such cryptography is explored with the properties
of lattice transmission.
References:
[1] Boorghany, S. B. Sarmadi, and R. Jalili.
On constrained implementation of lattice-
based cryptographic primitives and
schemes on smart cards. ACM
Transactions on Embedded Computing
Systems (TECS), 14(3):42:1–42:25, May
2015. URL:
https://eprint.iacr.org/2014/514,
doi:10.1145/2700078.
[2] E. Alkim, L. Ducas, T. P¨oppelmann, and
P. Schwabe. Newhope without
reconciliation. IACR ePrint 2016/1157,
2016. URL:
https://eprint.iacr.org/2016/1157.
[3] J. W. Bos, C. Costello, M. Naehrig, and D.
Stebila. Post-quantum key exchange for
the TLS protocol from the ring learning
with errors problem. In 2015 IEEE
Symposium on Security and Privacy, SP
2015, San Jose, CA, USA, May 17-21,
2015, pages 553–570. IEEE Computer
Society, 2015. Extended version available
as IACR ePrint 2014/599. URL:
https://eprint.iacr.org/2014/599,
doi:10.1109/SP.2015.40.
[4] M. R. Albrecht, R. Player, and S. Scott.
On the concrete hardness of learning with
errors. Journal of Mathematical
Cryptology, 9(3):169–203, October 2015.
URL: https://eprint.iacr.org/2015/046,
doi:10.1515/jmc-2015-0016.
[5] Saarinen. Markku-Juhani Olavi. Ring-
LWE ciphertext compression and error
correction: Tools for lightweight post-
quantum cryptography. In Proceedings of
the 3rd ACM International Workshop on
IoT Privacy, Trust, and Security, pp. 15-
22. ACM, 2017.
[6] Z. Brakerski, A. Langlois, C. Peikert, O.
Regev, and D. Stehl’e. Classical hardness
of learning with errors. In STOC ’13,
pages 575–584. ACM, 2013.
doi:10.1145/2488608.2488680.