Design, analysis and applications of cryptographic techniques

Chan Yeob Yeun

(2001)

Chan Yeob Yeun (2001) Design, analysis and applications of cryptographic techniques.

Our Full Text Deposits

Full text access: Open

Full Text - 512.61 KB

Links to Copies of this Item Held Elsewhere

Mathematics Departmental Web Page

Abstract

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.

Information about this Version

This is a Published version
This version's date is: 01/11/2001
This item is peer reviewed

Link to this Version

https://repository.royalholloway.ac.uk/items/d0790b37-c06d-61c2-55c9-092c070e96e8/1/

Item TypeMonograph (Technical Report)
TitleDesign, analysis and applications of cryptographic techniques
AuthorsYeun, Chan Yeob
DepartmentsFaculty of Science\Mathematics

Deposited by () on 15-Jul-2010 in Royal Holloway Research Online.Last modified on 09-Dec-2010

Notes

References

[1] “The digital signature standard proposed by NIST”. Communications of the
ACM, 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 using
symmetric techniques”. International Organization for Standardization, 1996.

[5] ISO/IEC 11770-3: 1999. “Key management - Part 3: Mechanisms using asymmetric
techniques”. International Organization for Standardization, 1999.

[6] ISO/IEC 9798. “Entity authentication - Parts 1 to 5”. International Organization
for Standardization.

[7] G.R. Blakley. “Safeguarding cryptographic keys”. In Proceedings of AFIPS
National Computer Conference, pages 313–317, 1979.

[8] R. Blom. “An optimal class of symmetric key generation schemes”. In Advances
in Cryptology – Proceedings of EUROCRYPT ’84, pages 335–338.
Springer-Verlag, 1985.

[9] A. Bosselaers and B. Preneel. “Integrity Primitives for Secure Information
Systems: Final Report of RACE Integrity Primitives Evaluation RIPE-RACE
1042”. In Number 1007 in Lecture Notes in Computer Science. Springer-
Verlag, 1995.

[10] E. Brickell, D. Stinson, and S. Goldwasser. “The detection of cheaters in
threshold schemes”. In S. Goldwasser, editor, Advances in Cryptology – Proceedings
of CRYPTO ’88, pages 564–577. Springer-Verlag, 1988.

[11] E. Brickell, D. Stinson, and S. Goldwasser. “The detection of cheaters in
threshold 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 the
5th 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 with
reusable 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 Transactions
on Information Theory, 22:644–654, 1976.

[19] T. ElGamal. “A public key cryptosystem and a signature scheme based on
discrete logarithms”. IEEE Transactions on Information Theory, 31:469–472,
1985.

[20] A. Fiat and A. Shamir. “How to prove yourself: practical solutions to identification
and signature problems”. In Advances in Cryptology – Proceedings of
CRYPTO ’86, pages 186–194. Springer-Verlag, 1987.

[21] H. Ghodosi, J. Pieprzyk, G.R. Chaudhry, and J. Seberry. “How to prevent
cheating 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 or
a completeness theorem for protocols with honest majority”. In Proceedings
of 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 fitted
to security micoprocessor minimising both transmission and memory”. In
Advances in Cryptology – Proceedings of EUROCRYPT ’88, pages 123–128.
Springer-Verlag, 1988.

[24] L. Harn. “Digital signature with (t; n) shared verification based on discrete
logarithms”. 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”. Electronics
Letters, 34(4):354–355, 1998.

[28] P. Horster, M. Michels, and H. Petersen. “Authenticated encryption schemes
with low communication costs”. Electronics Letters, 30(15):1212–1213, 1994.

[29] C.L. Hsu and T.C. Wu. “Authenticated encryption scheme with (t; n) shared
verification”. 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”. Communication
in ACM, 34:770–772, 1981.

[32] M.D. Larsen. “Introduction to modern algebraic concepts”. Addison-Wesley
Publishing Company, 1969.

[33] W. Lee and C. Chang. “Authenticated encryption scheme without using a
one-way function”. Electronics Letters, 31(19):1656–1657, 1995.

[34] G. Lowe. “An attack on the Needham-Schroeder public-key authentication
protocol”. Information Processing Letters, 56:131–133, 1995.

[35] K. Manders and L. Adleman. “NP-complete decision problems for binary
quadratics”. 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 fields
and 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 the
privacy 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 protocol
and 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 Applied
Cryptography”. 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 message
recovery”. 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 authentication
in large networks of computers”. Communications of the ACM, 21:993–999,
1978.

[44] I. Niven, H. Zuckerman, and H. Montgomery. “An Introduction to the theory
of numbers”. Wiley, 1991.

[45] K. Nyberg. “New digital signature scheme based on discrete logarithm”. Electronics
Letters, 30(6):481, 1994.

[46] K. Nyberg and R.A. Rueppel. “Message recovery for signature schemes based
on the discrete logarithm problem”. In Advances in Cryptology – Proceedings
of EUROCRYPT ’94, pages 175–190. Springer-Verlag, 1995.

[47] H. Petersen and M. Michels. “Crytanalysis and improvement of signcryption
schemes”. 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 logarithms
over GF(P) and its cryptographic significance”. IEEE Transactions
on Information Theory, 24:106–110, 1978.

[50] R.L. Rivest, A. Shamir, and L. Adleman. “A method for obtaining digital
signatures 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 of
Cryptology, 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-way
hash-function”. Electronics Letters, 34(11):1079–1080, 1998.


[55] Z. Shao. “Signature schemes based on factoring and discrete logarithms”. IEE
Proc. Digit. Tech., 145(1):33–36, 1998.

[56] G.J. Simmons. “Contemporary Cryptography: The Science of Information
Integrity”. 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 of
Cryptology, 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 scheme
which identifies all cheaters”. In Proceedings of NORDSEC’98, Trondheim,
Norway, November 1998, and presented at the 1st IMA Conference on Mathematics
in Communication, Loughborough, UK, December 1998.

[61] C.Y. Yeun, C.J. Mitchell, and S.L. Ng. “Comment–Signature scheme based on
discrete 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.

Details