II Advanced School on Cryptology and Information Security in Latin America, FlorianÃşpolis, Brazil, 2013 Simple Matrix Scheme for Encryption Jintai Ding JointworkwithChengdongTao,AdamaDiene,AlbrechtPetzoldt October, 2013 Outline 1 Introduction 2 The Basic ABC Encryption Scheme Key Generation Encryption Decryption Security analysis and practical parameters 3 The Improved Scheme A failed attempt Key Generation Encryption Decryption Outline 1 Introduction 2 The Basic ABC Encryption Scheme Key Generation Encryption Decryption Security analysis and practical parameters 3 The Improved Scheme A failed attempt Key Generation Encryption Decryption Hash-based signature systems. Lattice-based public key cryptosystems Multivariate public key cryptosystems – MPKC Post-quantum cryptography Public key cryptosystems that could resist the future quantum computer attack. Code-based public key cryptosystems Lattice-based public key cryptosystems Multivariate public key cryptosystems – MPKC Post-quantum cryptography Public key cryptosystems that could resist the future quantum computer attack. Code-based public key cryptosystems Hash-based signature systems. Multivariate public key cryptosystems – MPKC Post-quantum cryptography Public key cryptosystems that could resist the future quantum computer attack. Code-based public key cryptosystems Hash-based signature systems. Lattice-based public key cryptosystems Post-quantum cryptography Public key cryptosystems that could resist the future quantum computer attack. Code-based public key cryptosystems Hash-based signature systems. Lattice-based public key cryptosystems Multivariate public key cryptosystems – MPKC G can be viewed as a map from kn to km. G mostly quadratic maps, where g are quadratic polynomials: i X X g (x ,..x ) = α x x + β x +γ . i 1 n lij i j li i l i,j i What is a MPKC ? Multivariate Public Key Cryptosystems - Cryptosystems with public keys as a set of multivariate functions Public key: G(x ,...,x ) = 1 n (g (x ,...,x ),...,g (x ,...,x )) = L ◦F ◦L . 1 1 n m 1 n 2 1 over k, a small finite field. What is a MPKC ? Multivariate Public Key Cryptosystems - Cryptosystems with public keys as a set of multivariate functions Public key: G(x ,...,x ) = 1 n (g (x ,...,x ),...,g (x ,...,x )) = L ◦F ◦L . 1 1 n m 1 n 2 1 over k, a small finite field. G can be viewed as a map from kn to km. G mostly quadratic maps, where g are quadratic polynomials: i X X g (x ,..x ) = α x x + β x +γ . i 1 n lij i j li i l i,j i Any plaintext M = (x0,...,x0) is encrypted via polynomial 1 n evaluation: G(M) = G(x0,...,x0) = (y0,...,y0 ). 1 n 1 m To decrypt the ciphertext (y0,...,y0), one needs to know a 1 n secret (the private key) to compute the inverse map G−1 = L−1◦F−1◦L−1 1 2 to find the plaintext (x0,...,x0) = G−1(y0,..,y0). 1 n 1 n What is MPKC for encryption The public key is given as: G(x ,...,x ) = (G (x ,...,x ),...,G (x ,...,x )) = L ◦F ◦L . 1 n 1 1 n m 1 n 2 1 F is called the central map and easy to invert. L and L 1 2 serve as ”locks”.