The Experts below are selected from a list of 11427 Experts worldwide ranked by ideXlab platform
Jean-pierre Tillich - One of the best experts on this subject based on the ideXlab platform.
-
Speeding up decoding a code with a non-trivial automorphism group up to an exponential factor
2019Co-Authors: Rodolfo Canto-torres, Jean-pierre TillichAbstract:We give an algorithm that is able to speed up the decoding of a code with a non-trivial automorphism group, by summing for the word that has to be decoded, all its entries belonging to a same orbit and decoding the resulting word in a reduced code. For a certain range of parameters, this results in a decoding that is faster by an exponential factor in the codelength when compared to the best algorithms for decoding generic linear codes. This algorithm is then used to break several proposals of Public-Key Cryptosystems based on codes with a non-trivial automorphism group.
-
Distinguisher-based attacks on Public-Key Cryptosystems using Reed---Solomon codes
Designs Codes and Cryptography, 2014Co-Authors: Alain Couvreur, Philippe Gaborit, Valérie Gauthier-umaña, Ayoub Otmani, Jean-pierre TillichAbstract:Because of their interesting algebraic properties, several authors promote the use of generalized Reed---Solomon codes in cryptography. Niederreiter was the first to suggest an instantiation of his cryptosystem with them but Sidelnikov and Shestakov showed that this choice is insecure. Wieschebrink proposed a variant of the McEliece cryptosystem which consists in concatenating a few random columns to a generator matrix of a secretly chosen generalized Reed---Solomon code. More recently, new schemes appeared which are the homomorphic encryption scheme proposed by Bogdanov and Lee, and a variation of the McEliece cryptosystem proposed by Baldi et al. which hides the generalized Reed---Solomon code by means of matrices of very low rank. In this work, we show how to mount key-recovery attacks against these Public-Key encryption schemes. We use the concept of distinguisher which aims at detecting a behavior different from the one that one would expect from a random code. All the distinguishers we have built are based on the notion of component-wise product of codes. It results in a powerful tool that is able to recover the secret structure of codes when they are derived from generalized Reed---Solomon codes. Lastly, we give an alternative to Sidelnikov and Shestakov attack by building a filtration which enables to completely recover the support and the non-zero scalars defining the secret generalized Reed---Solomon code.
-
Distinguisher-Based Attacks on Public-Key Cryptosystems Using Reed-Solomon Codes
arXiv: Cryptography and Security, 2013Co-Authors: Alain Couvreur, Philippe Gaborit, Valérie Gauthier-umaña, Ayoub Otmani, Jean-pierre TillichAbstract:Because of their interesting algebraic properties, several authors promote the use of generalized Reed-Solomon codes in cryptography. Niederreiter was the first to suggest an instantiation of his cryptosystem with them but Sidelnikov and Shestakov showed that this choice is insecure. Wieschebrink proposed a variant of the McEliece cryptosystem which consists in concatenating a few random columns to a generator matrix of a secretly chosen generalized Reed-Solomon code. More recently, new schemes appeared which are the homomorphic encryption scheme proposed by Bogdanov and Lee, and a variation of the McEliece cryptosystem proposed by Baldi et \textit{al.} which hides the generalized Reed-Solomon code by means of matrices of very low rank. In this work, we show how to mount key-recovery attacks against these Public-Key encryption schemes. We use the concept of distinguisher which aims at detecting a behavior different from the one that one would expect from a random code. All the distinguishers we have built are based on the notion of component-wise product of codes. It results in a powerful tool that is able to recover the secret structure of codes when they are derived from generalized Reed-Solomon codes. Lastly, we give an alternative to Sidelnikov and Shestakov attack by building a filtration which enables to completely recover the support and the non-zero scalars defining the secret generalized Reed-Solomon code.
Li Yang - One of the best experts on this subject based on the ideXlab platform.
-
public key encryption and authentication of quantum information
Science China-physics Mechanics & Astronomy, 2012Co-Authors: Min Liang, Li YangAbstract:Public-Key Cryptosystems for quantum messages are considered from two aspects: Public-Key encryption and Public-Key authentication. Firstly, we propose a general construction of quantum Public-Key encryption scheme, and then construct an information-theoretic secure instance. Then, we propose a quantum Public-Key authentication scheme, which can protect the integrity of quantum messages. This scheme can both encrypt and authenticate quantum messages. It is information-theoretic secure with regard to encryption, and the success probability of tampering decreases exponentially with the security parameter with regard to authentication. Compared with classical Public-Key Cryptosystems, one private-key in our schemes corresponds to an exponential number of Public-Keys, and every quantum Public-Key used by the sender is an unknown quantum state to the sender.
-
Quantum Public-Key algorithms to encrypt and authenticate quantum messages with information-theoretic security
arXiv: Quantum Physics, 2012Co-Authors: Min Liang, Li YangAbstract:Public-Key Cryptosystems for quantum messages are considered from two aspects: Public-Key encryption and Public-Key authentication. Firstly, we propose a general construction of quantum Public-Key encryption scheme, and then construct an information-theoretic secure instance. Then, we propose a quantum Public-Key authentication scheme, which can protect the integrity of quantum messages. This scheme can both encrypt and authenticate quantum messages. It is information-theoretic secure with regard to encryption, and the success probability of tampering decreases exponentially with the security parameter with regard to authentication. Compared with classical Public-Key Cryptosystems, one private-key in our schemes corresponds to an exponential number of Public-Keys, and every quantum Public-Key used by the sender is an unknown quantum state to the sender.
-
Quantum Public-Key Cryptosystems based on induced trapdoor one-way transformations
arXiv: Quantum Physics, 2010Co-Authors: Li Yang, Bao Li, Min Liang, Lei Hu, Deng-guo FengAbstract:A concept named induced trapdoor one-way quantum transformation (OWQT) has been introduced, and a theoretical framework of Public-Key encryption (PKE) of quantum message is presented based on it. Then several kinds of quantum Public-Key encryption (QPKE) protocols, such as quantum version PKE of RSA, ElGamal, Goldwasser-Micali, elliptic curve, McEliece, Niederreiter and Okamoto-Tanaka-Uchiyama, are given within this framework. Though all of these protocols are only computationally secure, the last three are probably secure in post-quantum era. Besides, theoretical frameworks for Public-Key authentication and signature of quantum message are also given based on the induced trapdoor OWQT. As examples, a Public-Key authentication protocol of quantum message based on SN-S authentication scheme and two quantum digital signature protocols based on RSA and McEliece algorithms respectively are presented.
Tillich Jean-pierre - One of the best experts on this subject based on the ideXlab platform.
-
Distinguisher-based attacks on Public-Key Cryptosystems using Reed-Solomon codes
'Springer Science and Business Media LLC', 2020Co-Authors: Couvreur Alain, Gaborit Philippe, Gauthier-umaña Valérie, Otmani Ayoub, Tillich Jean-pierreAbstract:"Because of their interesting algebraic properties, several authors promote the use of generalized Reed-Solomon codes in cryptography. Niederreiter was the first to suggest an instantiation of his cryptosystem with them but Sidelnikov and Shestakov showed that this choice is insecure. Wieschebrink proposed a variant of the McEliece cryptosystem which consists in concatenating a few random columns to a generator matrix of a secretly chosen generalized Reed-Solomon code. More recently, new schemes appeared which are the homomorphic encryption scheme proposed by Bogdanov and Lee, and a variation of the McEliece cryptosystem proposed by Baldi et al. which hides the generalized Reed-Solomon code by means of matrices of very low rank. In this work, we show how to mount key-recovery attacks against these Public-Key encryption schemes. We use the concept of distinguisher which aims at detecting a behavior different from the one that one would expect from a random code. All the distinguishers we have built are based on the notion of component-wise product of codes. It results in a powerful tool that is able to recover the secret structure of codes when they are derived from generalized Reed-Solomon codes. Lastly, we give an alternative to Sidelnikov and Shestakov attack by building a filtration which enables to completely recover the support and the non-zero scalars defining the secret generalized Reed-Solomon code. © 2014 Springer Science+Business Media New York.
-
Speeding up decoding a code with a non-trivial automorphism group up to an exponential factor
IEEE, 2019Co-Authors: Canto-torres Rodolfo, Tillich Jean-pierreAbstract:International audienceWe give an algorithm that is able to speed up the decoding of a code with a non-trivial automorphism group, by summing for the word that has to be decoded, all its entries belonging to a same orbit and decoding the resulting word in a reduced code. For a certain range of parameters, this results in a decoding that is faster by an exponential factor in the codelength when compared to the best algorithms for decoding generic linear codes. This algorithm is then used to break several proposals of Public-Key Cryptosystems based on codes with a non-trivial automorphism group
Xingkai Zhang - One of the best experts on this subject based on the ideXlab platform.
-
A ring signature scheme over braid groups
Journal of Electronics (China), 2010Co-Authors: Yun Wei, Wansu Bao, Guohua Xiong, Xingkai ZhangAbstract:Quantum algorithms bring great challenges to classical public key Cryptosystems, which makes Cryptosystems based on non-commutative algebraic systems hop topic. The braid groups, which are non-commutative, have attracted much attention as a new platform for constructing quantum attack-resistant Cryptosystems. A ring signature scheme is proposed based on the difficulty of the root extraction problem over braid groups, which can resist existential forgery against the adaptively chosen-message attack under the random oracle model.
Shigenori Uchiyama - One of the best experts on this subject based on the ideXlab platform.
-
CRYPTO - Quantum Public-Key Cryptosystems
Advances in Cryptology — CRYPTO 2000, 2000Co-Authors: Tatsuaki Okamoto, Keisuke Tanaka, Shigenori UchiyamaAbstract:This paper presents a new paradigm of cryptography, quantum Public-Key Cryptosystems. In quantum Public-Key Cryptosystems, all parties including senders, receivers and adversaries are modeled as quantum (probabilistic) poly-time Turing (QPT) machines and only classical channels (i.e., no quantum channels) are employed. A quantum trapdoor one-way function, f, plays an essential role in our system, in which a QPT machine can compute f with high probability, any QPT machine can invert f with negligible probability, and a QPT machine with trapdoor data can invert f. This paper proposes a concrete scheme for quantum Public-Key Cryptosystems: a quantum Public-Key encryption scheme or quantum trapdoor one-way function. The security of our schemes is based on the computational assumption (over QPT machines) that a class of subset-sum problems is intractable against any QPT machine. Our scheme is very efficient and practical if Shor's discrete logarithm algorithm is efficiently realized on a quantum machine.
-
Quantum Public-Key Cryptosystems
Lecture Notes in Computer Science, 2000Co-Authors: Tatsuaki Okamoto, Keisuke Tanaka, Shigenori UchiyamaAbstract:This paper presents a new paradigm of cryptography, quantum Public-Key Cryptosystems. In quantum Public-Key Cryptosystems, all parties including senders, receivers and adversaries are modeled as quantum (probabilistic) poly-time Turing (QPT) machines and only classical channels (i.e., no quantum channels) are employed. A quantum trapdoor one-way function, f, plays an essential role in our system, in which a QPT machine can compute f with high probability, any QPT machine can invert f with negligible probability, and a QPT machine with trapdoor data can invert f. This paper proposes a concrete scheme for quantum Public-Key Cryptosystems: a quantum Public-Key encryption scheme or quantum trapdoor one-way function. The security of our schemes is based on the computational assumption (over QPT machines) that a class of subset-sum problems is intractable against any QPT machine. Our scheme is very efficient and practical if Shor's discrete logarithm algorithm is efficiently realized on a quantum machine.
