28 Post Quantum Crypto for Dummies text as error, i.e., as a weight bit string. Instead of a generator matrix �� pub, a parity-check matrix �� pub is used as the public key. The sender encodes the plain text as a bit string ⃗�� with weight w and computes the syndrome ⃗�� = �� pub �� ⃗�� The receiver uses a syndrome-decoding algorithm to recover the original error vector ⃗��. Again, the public parity check matrix �� pub must be »scrambled« such that the underlying secret structure is not revealed to an attacker 47. This process is particularly suitable when sender and receiver want to share a random bit string, e.g., as key for symmetric encryption. In this case, the sender simply generates a random bit string with weight w and transmits it to the receiver as described. Then both the sender and the receiver hash the bit string in order to obtain a shared secret key for symmetric encryption. The cryptographic community has strong confidence in the McEliece cryptosystem and in Niederreiter’s cryptosystem using Goppa codes. The main problem of code-bases systems is the huge size of the public key. There have been several attempts to reduce key sizes by using different codes that have some »compressible « redundant structure in the public key (e.g., quasi-cyclic moderate parity check codes (QCMDPC) 45); however, in many cases, this structure has led to efficient classical (i.e. non-quantum) attacks on the cryptosystems. Apart from public-key cryptosystems, there are also signature schemes 22, hash functions 5, and random-number generators 31 based on code-based cryptography. Lattice-based Cryptography The underlying hard problem for lattice-based cryptography is the shortest vector problem: it is computationally hard to find the shortest vector in a highdimensional lattice. The basic idea for constructing public-key encryption schemes using lattices is to use a well-formed high-dimensional lattice base s as secret private key and a scrambled version p of this base as public key (see Figure 3.2). For encryption, the sender of a message maps the message to a point ⃗ �� in the lattice using the public scrambled base. Then, the sender adds a random error to the lattice point such that the
PQC_for_Dummies
To see the actual publication please follow the link above