Last ned (Gratis)

Abstrakt

In this paper we investigate the possibilities of building Zero Knowledge
Identity-Based Identification Schemes relying on the problem of Isotopy
of Left Multivariate Quasigroups (LMQIsot) and the MQ problem. We
determine the connection between LMQIsot and the already well studied
problem of Isomorphism of Polynomials (IP), and as a result we propose
a novel way of creating an Identity-Based version of a multivariate
Identification Scheme through two examples: Patarin’s IP2S (IP with
two secrets) scheme, and Wolf and Preneel’s MQ∗-IP scheme.

Referanser

[1] M. Bardet, J.C. Faug`ere and B. Salvy, “On the complexity of Grobner basis computation of semiregular overdetermined algebraic equations”, ICPSS, pp. 71–75, 2004.

[2] O. Billet and J. Ding, “Overview of cryptanalysis techniques in multivariate public key cryptography”, Gr¨obner bases, coding and cryptography, pp. 263– 283. Springer Verlag, 2009.

[3] C. Bouillaguet, J.C. Faug`ere, P.A. Fouquem and L. Perret, “Practical Cryptanalysis of the Identification Scheme Based on the Isomorphism of

Polynomial with One Secret Problem”, PKC 2011.

[4] N. Courtois, “Efficient Zero-Knowledge Authentication Based on a Linear Algebra Problem MinRank”, ASIACRYPT ’01, 402–421, 2001.

[5] L. Guillou and J.J. Quisquater, “A “paradoxical” identity-based signature scheme resulting from zero-knowledge”, CRYPTO ’88, LNCS vol. 403, Springer- Verlag, 1988.

[6] J.C. Faug`ere, “A new efficient algorithm for computing Gr¨obner basis (F4)”, J. Pure Appl. Algebra 139, pp.1-3, 61–88, 1999.

[7] A. Fiat and A. Shamir, “How to prove yourself: Practical solutions to identification and signature problems”, CRYPTO ’86, LNCS vol. 263, pp. 186– 194, Springer 1986.

[8] M. R. Garey and D. S. Johnson. “Computers and Intractability - A Guide to the Theory of NP-Completeness”. W.H. Freeman and Company, 1979.

[9] D. Gligoroski, S. Markovski, and S.J. Knapskog, “Multivariate quadratic trapdoor functions based on multivariate quadratic quasigroups”, ACAM, 2008. [10] O. Goldreich, S. Micali, and A. Wigderson, “Proofs that Yield Nothing But Their Validity for All Languages in NP Have Zero-Knowledge Proof Systems”, J. ACM, pp. 691–729, 1991.

[11] S. Goldwasser, S. Micali and C. Rackoff. “The knowledge complexity of interactive proof-systems”, STOC 1985, pp. 291–304, ACM Press, 1985. [12] G. L. Miller, “On the O(nlogn) isomorphism technique,” Proc. 12th STOC 1978. [13] J. Patarin, ”Hidden Fields Equations (HFE) and Isomorphisms of Polynomials (IP): two new Families of asymmetric Algorithms”, EUROCRYPT ’96, pp. 33– 48, Springer-Verlag, 1996.

[14] J. Patarin and L. Goubin, “Trapdoor one-way permutations and multivariate polynomials”, ICISC 1997, LNCS vol. 1334 , pp. 356–368, Springer, 1997. [15] D. Pointcheval, “A new Identification Scheme Based on the Perceptrons Problem”, EUROCRYPT ’95, LNCS 921, pp.319–328, Springer-Verlag, 1995. [16] C. P. Schnorr, “Efficient signature generation by smart cards”, Journal of Cryptology, vol. 4(3), pp.161–174, 1991.

[17] A. Shamir, “Identity-Based Cryptosystems and Signature Schemes”, CRYPTO ’84, LNCS, vol. 7, pp. 47–53, 1984.

[18] J. Stern, “A new identification scheme based on syndrome decoding”, CRYPTO ’93, LNCS vol. 773, pp. 13–21, Springer-Verlag, 1993.

[19] J. Stern, “Designing identification schemes with keys of short size”, CRYPTO ’94, LNCS vol. 839, pp. 164–73, Springer-Verlag, 1994.

[20] A. Shamir, “An efficient Identification Scheme Based on Permuted Kernels”, CRYPTO ’89, LNCS vol. 435, pp. 606–609, Springer-Verlag, 1989.

[21] S. Samardjiska, S. Markovski and D. Gligoroski, “Multivariate Quasigroups Defined by T-functions”, Proceedings of SCC2010, London, 2010.

[22] C. Wolf and B. Preneel, “MQ∗-IP: An Identity-based Identification Scheme without Number-theoretic Assumptions”, Cryptology ePrint Archive, Report 2010/087, 2010. Available: http://eprint.iacr.org/2010/087

[23] M. J. Wolf, “Nondeterministic circuits, space complexity and quasigroups”, Theoretical Computer Science vol. 125 (2), pp. 295–313, 1994.




Forrige artikkel      Neste artikkel