Chan Yeob Yeun (2001) Design, analysis and applications of cryptographic techniques.
Full text access: Open
Cryptographic techniques, such as encipherment, digital signatures, key management and secret sharing schemes, are important building blocks in the implementation of all security services. In this thesis, we present a general model for online secret sharing schemes and investigate the design of online secret sharing schemes which are derived from this model such as Cachin and Pinch’s schemes. We propose a modified version of the Pinch multiple secret sharing protocol, which identifies all cheaters, regardless of their number, improving on previous results by Ghodosi et al. A new scheme is then proposed for computationally secure online secret sharing, in which the shares of the participants can be reused. The security of the scheme is based on the intractability of factoring. This scheme has the advantage that it detects cheating and it enables the identification of all cheaters by an arbitrator, regardless of their number. The scheme does not rely on a 'last participant' who reconstructs the secret on behalf of a minimal trusted set: the responsibility is diffused among all participants. In addition, we cryptanalyse the recently proposed signature scheme by Shao, based on the discrete logarithm problem, and show it is subject to homomorphism attacks, despite a claim to the contrary. Moreover, we show that there are major differences between a digital signature with message recovery scheme and an authenticated encryption scheme and point out that the signature with message recovery scheme that was recently proposed by Chen is actually not a signature scheme. It would more accurately be described as an authenticated encryption scheme. Furthermore, we propose a modification to the Helsinki protocol which prevents attacks by an adversary. Some of the material in Chapters 2, 3 and 4 of the thesis has appeared in published papers.
This is a Published version This version's date is: 01/11/2001 This item is peer reviewed
https://repository.royalholloway.ac.uk/items/d0790b37-c06d-61c2-55c9-092c070e96e8/1/
Deposited by () on 15-Jul-2010 in Royal Holloway Research Online.Last modified on 09-Dec-2010
[1] “The digital signature standard proposed by NIST”. Communications of theACM, 35(7):36–40, 1992.
[2] ISO 7498-2: 1989. “Open systems Interconnection - Basic reference Model -Part 2: Security Architecture”. International Organization for Standardization,1989.
[3] ISO/IEC 9796: 1991. “Digital signature scheme giving message recovery”.International Organization for Standardization, 1991.
[4] ISO/IEC 11770-2: 1996. “Key management - Part 2: Mechanisms usingsymmetric techniques”. International Organization for Standardization, 1996.
[5] ISO/IEC 11770-3: 1999. “Key management - Part 3: Mechanisms using asymmetrictechniques”. International Organization for Standardization, 1999.
[6] ISO/IEC 9798. “Entity authentication - Parts 1 to 5”. International Organizationfor Standardization.
[7] G.R. Blakley. “Safeguarding cryptographic keys”. In Proceedings of AFIPSNational Computer Conference, pages 313–317, 1979.
[8] R. Blom. “An optimal class of symmetric key generation schemes”. In Advancesin Cryptology – Proceedings of EUROCRYPT ’84, pages 335–338.Springer-Verlag, 1985.
[9] A. Bosselaers and B. Preneel. “Integrity Primitives for Secure InformationSystems: Final Report of RACE Integrity Primitives Evaluation RIPE-RACE1042”. In Number 1007 in Lecture Notes in Computer Science. Springer-Verlag, 1995.
[10] E. Brickell, D. Stinson, and S. Goldwasser. “The detection of cheaters inthreshold schemes”. In S. Goldwasser, editor, Advances in Cryptology – Proceedingsof CRYPTO ’88, pages 564–577. Springer-Verlag, 1988.
[11] E. Brickell, D. Stinson, and S. Goldwasser. “The detection of cheaters inthreshold schemes”. In Advances in Cryptology – Proceedings of CRYTO ’88,pages 564–577. Springer-Verlag, 1990.
[12] David M. Burton. “Elementary number theory”. Wm. C. Brown Publishers,1994.
[13] C. Cachin. “On-line secret sharing”. In C. Boyd, editor, Proceedings of the5th IMA Conference on Cryptography and Coding, pages 190–198. Springer-Verlag, 1995.
[14] K. Chen. “Signature with message recovery”. Electronics Letters, 34(20):1934,1998.
[15] L. Chen, D. Gollmann, C.J. Mitchell, and P. Wild. “Secret sharing withreusable polynomials”. In Vijay Varadharajan, Josef Pieprzyk, and Yi Mu,editors, Proceedings of ACISP ’97, pages 183–193. Springer-Verlag, 1997.
[16] P. Cohn. “Algebra, volume 1”. Wiley, 1982.
[17] D. Denning. “Digital signatures with RSA and other public-key cryptosystems”.Communications of the ACM, 27(4):388–392, 1984.
[18] W. Diffie and M.E. Hellman. “New directions in cryptography”. IEEE Transactionson Information Theory, 22:644–654, 1976.
[19] T. ElGamal. “A public key cryptosystem and a signature scheme based ondiscrete logarithms”. IEEE Transactions on Information Theory, 31:469–472,1985.
[20] A. Fiat and A. Shamir. “How to prove yourself: practical solutions to identificationand signature problems”. In Advances in Cryptology – Proceedings ofCRYPTO ’86, pages 186–194. Springer-Verlag, 1987.
[21] H. Ghodosi, J. Pieprzyk, G.R. Chaudhry, and J. Seberry. “How to preventcheating in Pinch’s scheme”. Electronics Letters, 33(17):1453–1454, 1997.
[22] O. Goldreich, S. Micali, and A. Widgerson. “How to play any mental game ora completeness theorem for protocols with honest majority”. In Proceedingsof 19th ACM Symposium on the Theory of Computing, pages 218–229, 1987.
[23] L.C. Guillou and J.J. Quisquater. “A practical zero knowledge protocol fittedto security micoprocessor minimising both transmission and memory”. InAdvances in Cryptology – Proceedings of EUROCRYPT ’88, pages 123–128.Springer-Verlag, 1988.
[24] L. Harn. “Digital signature with (t; n) shared verification based on discretelogarithms”. Electronics Letters, 29(24):2094–2095, 1993.
[25] J. He and T. Kiesler. “Enhancing the security of ElGamal’s signature scheme”.IEE Proc. Digit. Tech., 141(4):249–252, 1994.
[26] I. Herstein. “Topics in Algebra”. Wiley, 1987.
[27] G. Horng and C.K. Hsu. “Weakness in the Helsinki protocol”. ElectronicsLetters, 34(4):354–355, 1998.
[28] P. Horster, M. Michels, and H. Petersen. “Authenticated encryption schemeswith low communication costs”. Electronics Letters, 30(15):1212–1213, 1994.
[29] C.L. Hsu and T.C. Wu. “Authenticated encryption scheme with (t; n) sharedverification”. IEE Proc. Digit. Tech., 145(2):117–120, 1998.
[30] N. Koblitz. “Algebraic aspects of cryptography”. Springer-Verlag, 1998.
[31] L. Lamport. “Password authentication with insecure communication”. Communicationin ACM, 34:770–772, 1981.
[32] M.D. Larsen. “Introduction to modern algebraic concepts”. Addison-WesleyPublishing Company, 1969.
[33] W. Lee and C. Chang. “Authenticated encryption scheme without using aone-way function”. Electronics Letters, 31(19):1656–1657, 1995.
[34] G. Lowe. “An attack on the Needham-Schroeder public-key authenticationprotocol”. Information Processing Letters, 56:131–133, 1995.
[35] K. Manders and L. Adleman. “NP-complete decision problems for binaryquadratics”. Journal of Computer and System Sciences, 16:168–184, 1978.131
[36] J.L. Massey and J.K. Omura. “A new multiplicative algorithm over finite fieldsand its applicability in public key cryptography”. Presented at EUROCRYPT’83 Udine, Italy, 1983.
[37] J.L. Massey and J.K. Omura. “Method and apparatus for maintaining theprivacy of digital messages conveyed by public transmission”. U.S Patent No:4,567,600 28 Jan, 1986.
[38] U.M. Maurer. “Towards the equivalence of breaking the Diffie Hellman protocoland discrete logarithms”. In Y.G. Desmedt, editor, Advances in Cryptology– Proceedings of CRYPTO ’94, pages 271–281. Springer-Verlag, 1994.
[39] A.J. Menezes, P.C. van Oorschot, and S.A. Vanstone. “Handbook of AppliedCryptography”. CRC Press, 1996.
[40] C.J. Mitchell and C.Y. Yeun. “Fixing a problem in the Helsinki protocol”.ACM Operating Systems Review, 32(4):21–24, 1998.
[41] C.J. Mitchell and C.Y. Yeun. “Comment–Signature scheme with messagerecovery”. Electronics Letters, 35(3):217, 1999.
[42] T. Nagell. “Introduction to number theory”. Chelsea Publishing Company,1981.
[43] R.M. Needham and M.D. Schroeder. “Using encryption for authenticationin large networks of computers”. Communications of the ACM, 21:993–999,1978.
[44] I. Niven, H. Zuckerman, and H. Montgomery. “An Introduction to the theoryof numbers”. Wiley, 1991.
[45] K. Nyberg. “New digital signature scheme based on discrete logarithm”. ElectronicsLetters, 30(6):481, 1994.
[46] K. Nyberg and R.A. Rueppel. “Message recovery for signature schemes basedon the discrete logarithm problem”. In Advances in Cryptology – Proceedingsof EUROCRYPT ’94, pages 175–190. Springer-Verlag, 1995.
[47] H. Petersen and M. Michels. “Crytanalysis and improvement of signcryptionschemes”. IEE Proceedings on Computers and Digital Techniques, 145:149–151, 1998.
[48] R.G.E. Pinch. “Online multiple secret sharing”. Electronics Letters,32(12):1087–1088, 1996.
[49] S. Pohlig and M.E. Hellman. “An improved alogrithm for computing logarithmsover GF(P) and its cryptographic significance”. IEEE Transactionson Information Theory, 24:106–110, 1978.
[50] R.L. Rivest, A. Shamir, and L. Adleman. “A method for obtaining digitalsignatures and public key cryptosystems”. Communications of the ACM,21:120–126, 1978.
[51] K. H. Rosen. “Elementary number theory and its applications”. Wiley, 1993.
[52] C.P. Schnorr. “Efficient signature generation by smart cards”. Journal ofCryptology, 4(3):161–174, 1991.
[53] A. Shamir. “How to share a secret”. Communications of the ACM, 22:612–613,1979.
[54] Z. Shao. “Signature scheme based on discrete logarithm without using one-wayhash-function”. Electronics Letters, 34(11):1079–1080, 1998.
[55] Z. Shao. “Signature schemes based on factoring and discrete logarithms”. IEEProc. Digit. Tech., 145(1):33–36, 1998.
[56] G.J. Simmons. “Contemporary Cryptography: The Science of InformationIntegrity”. IEEE Press, 1992.
[57] D.R. Stinson. “Cryptography theory and practice”. CRC Press, 1995.
[58] M. Tompa and H. Woll. “How to share a secret with cheaters”. Journal ofCryptology, 1(2):133–138, 1988.
[59] C.Y. Yeun and C.J. Mitchell. “How to identify all cheaters in Pinch’s scheme”.In Proceedings of JWIS’98, Singapore, pages 129–133, 1998.
[60] C.Y. Yeun, C.J. Mitchell, and M.Burmester. “An online scret sharing schemewhich identifies all cheaters”. In Proceedings of NORDSEC’98, Trondheim,Norway, November 1998, and presented at the 1st IMA Conference on Mathematicsin Communication, Loughborough, UK, December 1998.
[61] C.Y. Yeun, C.J. Mitchell, and S.L. Ng. “Comment–Signature scheme based ondiscrete logarithm without using one-way hash-function”. Electronics Letters,34(24):2329–2330, 1998.
[62] Y. Zheng. “Digital signcryption or how to achieve cost(signature+encryption) << cost(signature)+cost(encryption)”. In Advances in Cryptology – Proceedings of Crypto ’97, pages 165–179. Springer-Verlag, 1997.