##plugins.themes.academic_pro.article.main##
Abstract
In this thesis we present new results in two areas – cryptographic protocols and lattice problems.
- We present a new protocol for electronic cash which is designed to function on hardware with limited computing power. The scheme has provable security properties and low computational requirements, but it still gives a fair amount of privacy. Another feature of the system is that there is no master secret that could be used for counterfeiting money if stolen.
- We introduce the notion of hierarchical group signatures. This is a proper generalization of group signatures, which allows multiple group managers organized in a tree with the signers as leaves. For a signer that is a leaf of the sub tree of a group manager, the group manager learns which of its children that (perhaps indirectly) manages the signer. We provide definitions for the new notion and construct a scheme that is provably secure given the existence of a family of trapdoor permutations. We also present a construction which is relatively practical, and prove its security in the random oracle model under the strong RSA assumption and the DDH assumption.
- We show a weakness in the specification for offline capable EMV payment cards. The weakness, which applies to cards without RSA capability, enables an attacker to duplicate a card and make transactions that cannot be tied to the original card.
- We give a method for approximating any n-dimensional lattice with a lattice Λ whose factor group Zn /Λ has (n – 1) cycles of equal length with arbitrary precision. We also show that a direct consequence of this is that the Shortest Vector Problem and the Closest Vector Problem cannot be easier for this type of lattices than for general lattices.
##plugins.themes.academic_pro.article.details##
How to Cite
Venugopal, D. D. (2015). Network Security Cryptographic Protocols and Lattice Problems. International Journal of Emerging Trends in Science and Technology, 2(03). Retrieved from https://igmpublication.org/ijetst.in/index.php/ijetst/article/view/526
References
1. M. Ajtai. Generating hard instances of lattice problems. In 28th ACM Sym-posium on the Theory of Computing (STOC), pages 99–108. ACM Press, 1996.
2. M. Ajtai. The shortest vector problem in ℓ2 is NP-hard for randomized reduc-tions. In 30th ACM Symposium on the Theory of Computing (STOC), pages 10–19. ACM Press, 1998.
3. G. Ateniese, J. Camenisch, M. Joye, and G. Tsudik. A practical and provably secure coalition-resistant group signature scheme. In Advances in Cryptology
– CRYPTO 2000, volume 1880 of Lecture Notes in Computer Science, pages 255–270. Springer Verlag, 2000.
4. G. Ateniese and G. Tsudik. Some open issues and directions in group signa-tures. In Financial Cryptography ’99, volume 1648 of Lecture Notes in Com-puter Science, pages 196–211. Springer Verlag, 1999.
5. L. Babai. Trading group theory for randomness. In 17th ACM Symposium on the Theory of Computing (STOC), pages 421–429. ACM Press, 1985.
6. Bellare and O. Goldreich. On defining proofs of knowledge. In Advances in Cryptology – CRYPTO’92, volume 740 of Lecture Notes in Computer Science, pages 390–420. Springer Verlag, 1992.
7. M. Bellare, D. Micciancio, and B. Warinschi. Foundations of group signatures: Formal definitions, simplified requirements, and a construction based on gen-eral assumptions. In Advances in Cryptology – EUROCRYPT 2003, volume 2656 of Lecture Notes in Computer Science, pages 614–629. Springer Verlag, 2003.
8. M. Blum, P. Feldman, and S. Micali. Non-interactive zero-knowledge and its applications. In 20th ACM Symposium on the Theory of Computing (STOC), pages 103–118. ACM Press, 1988.
9. F. Boudot. Efficient proofs that a committed number lies in an interval. In Advances in Cryptology – EUROCRYPT 2000, volume 1807 of Lecture Notes in Computer Science, pages 431–444. Springer Verlag, 2000.
10. F. Boudot and J. Traoré. Efficient publicly veriable secret sharing schemes with fast or delayed recovery. In 2nd International Conference on Information and Communication Security (ICICS), volume 1726 of Lecture Notes in Computer Science, pages 87–102. Springer Verlag, 1999.
11. S. Brands. Untraceable off-line cash in wallets with observers. In Advances in Cryptology – CRYPTO’93, volume 773 of Lecture Notes in Computer Science, pages 302–318. Springer Verlag, 1994.
12. E. Brickell, P. Gemmell, and D. Kravitz. Tracing extensions to anonymous cash and the making of anonymous change. In 6th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 457–466. ACM Press, 1995.
13. J-Y. Cai and A. Nerurkar. An improved worst-case to average-case connection for lattice problems. In 38th IEEE Symposium on ACM Symposium on the Theory of Computing (STOC), pages 468–477. IEEE Computer Society Press, 1997.
14. J. Camenisch. Efficient and generalized group signature. In Advances in Cryptology – EUROCRYPT’97, volume 1233 of Lecture Notes in Computer Science, pages 465–479. Springer Verlag, 1997.
15. J. Camenisch and M. Michels. A group signature scheme with improved effi-ency. In Advances in Cryptology – ASIACRYPT’98, volume 1514 of Lecture Notes in Computer Science, pages 160–174. Springer Verlag, 1999.
16. J. Camenisch and M. Michels. Separability and efficiency for generic group signature schemes. In Advances in Cryptology – CRYPTO’99, volume 1666 of Lecture Notes in Computer Science, pages 413–430. Springer Verlag, 1999.
17. J. Camenisch and M. Stadler. Efficient group signature schemes for large groups. In Advances in Cryptology – CRYPTO’97, volume 1294 of Lecture Notes in Computer Science, pages 410–424. Springer Verlag, 1997.
18. R. Canetti, O. Goldreich, and S. Halevi. The random oracle model revisited. In 30th ACM Symposium on the Theory of Computing (STOC), pages 209–218. ACM Press, 1998.
19. D. Chaum, A. Fiat, and M. Naor. Untraceable electronic cash. In Advances in Cryptology – CRYPTO’88, volume 403 of Lecture Notes in Computer Science, pages 319–327. Springer Verlag, 1990.
20. D. Chaum, E. van Heijst, and B. Pfitzmann. Cryptographically strong undeni-able signatures, unconditionally secure for the signer. In Advances in Crypto-logy – CRYPTO’91, volume 576 of Lecture Notes in Computer Science, pages 470–484. Springer Verlag, 1991.
21. D. Chaum and E. van Heyst. Group signatures. In Advances in Cryptology – EUROCRYPT’91, volume 547 of Lecture Notes in Computer Science, pages 257–265. Springer Verlag, 1991.
22. L. Chen and T.P. Pedersen. New group signature schemes. In Advances in Cryptology – EUROCRYPT’94, volume 950 of Lecture Notes in Computer Sci-ence, pages 171–181. Springer Verlag, 1994.
23. R. Cramer, I. Damgård, and B. Schoenmakers. Proofs of partial knowledge and simplified design of witness hiding protocols. In Advances in Cryptology – CRYPTO’94, volume 839 of Lecture Notes in Computer Science, pages 174– 187. Springer Verlag, 1994.
24. R. Cramer and V. Shoup. A practical public key cryptosystem provably se-cure against adaptive chosen ciphertext attack. In Advances in Cryptology – CRYPTO’98, volume 1462 of Lecture Notes in Computer Science, pages 13–25. Springer Verlag, 1998.
25. R. Cramer and V. Shoup. Signature schemes based on the strong RSA as-sumption. In 6th ACM Conference on Computer and Communications Security (CCS), pages 46–51. ACM Press, 1999.
26. D. Chaum and E. van Heyst. Group signatures. In Advances in Cryptology – EUROCRYPT’91, volume 547 of Lecture Notes in Computer Science, pages 257–265. Springer Verlag, 1991.
27. L. Chen and T.P. Pedersen. New group signature schemes. In Advances in Cryptology – EUROCRYPT’94, volume 950 of Lecture Notes in Computer Sci-ence, pages 171–181. Springer Verlag, 1994.
28. R. Cramer, I. Damgård, and B. Schoenmakers. Proofs of partial knowledge and simplified design of witness hiding protocols. In Advances in Cryptology – CRYPTO’94, volume 839 of Lecture Notes in Computer Science, pages 174– 187. Springer Verlag, 1994.
29. R. Cramer and V. Shoup. A practical public key cryptosystem provably se-cure against adaptive chosen ciphertext attack. In Advances in Cryptology – CRYPTO’98, volume 1462 of Lecture Notes in Computer Science, pages 13–25. Springer Verlag, 1998.
30. R. Cramer and V. Shoup. Signature schemes based on the strong RSA as-sumption. In 6th ACM Conference on Computer and Communications Security (CCS), pages 46–51. ACM Press, 1999.
2. M. Ajtai. The shortest vector problem in ℓ2 is NP-hard for randomized reduc-tions. In 30th ACM Symposium on the Theory of Computing (STOC), pages 10–19. ACM Press, 1998.
3. G. Ateniese, J. Camenisch, M. Joye, and G. Tsudik. A practical and provably secure coalition-resistant group signature scheme. In Advances in Cryptology
– CRYPTO 2000, volume 1880 of Lecture Notes in Computer Science, pages 255–270. Springer Verlag, 2000.
4. G. Ateniese and G. Tsudik. Some open issues and directions in group signa-tures. In Financial Cryptography ’99, volume 1648 of Lecture Notes in Com-puter Science, pages 196–211. Springer Verlag, 1999.
5. L. Babai. Trading group theory for randomness. In 17th ACM Symposium on the Theory of Computing (STOC), pages 421–429. ACM Press, 1985.
6. Bellare and O. Goldreich. On defining proofs of knowledge. In Advances in Cryptology – CRYPTO’92, volume 740 of Lecture Notes in Computer Science, pages 390–420. Springer Verlag, 1992.
7. M. Bellare, D. Micciancio, and B. Warinschi. Foundations of group signatures: Formal definitions, simplified requirements, and a construction based on gen-eral assumptions. In Advances in Cryptology – EUROCRYPT 2003, volume 2656 of Lecture Notes in Computer Science, pages 614–629. Springer Verlag, 2003.
8. M. Blum, P. Feldman, and S. Micali. Non-interactive zero-knowledge and its applications. In 20th ACM Symposium on the Theory of Computing (STOC), pages 103–118. ACM Press, 1988.
9. F. Boudot. Efficient proofs that a committed number lies in an interval. In Advances in Cryptology – EUROCRYPT 2000, volume 1807 of Lecture Notes in Computer Science, pages 431–444. Springer Verlag, 2000.
10. F. Boudot and J. Traoré. Efficient publicly veriable secret sharing schemes with fast or delayed recovery. In 2nd International Conference on Information and Communication Security (ICICS), volume 1726 of Lecture Notes in Computer Science, pages 87–102. Springer Verlag, 1999.
11. S. Brands. Untraceable off-line cash in wallets with observers. In Advances in Cryptology – CRYPTO’93, volume 773 of Lecture Notes in Computer Science, pages 302–318. Springer Verlag, 1994.
12. E. Brickell, P. Gemmell, and D. Kravitz. Tracing extensions to anonymous cash and the making of anonymous change. In 6th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 457–466. ACM Press, 1995.
13. J-Y. Cai and A. Nerurkar. An improved worst-case to average-case connection for lattice problems. In 38th IEEE Symposium on ACM Symposium on the Theory of Computing (STOC), pages 468–477. IEEE Computer Society Press, 1997.
14. J. Camenisch. Efficient and generalized group signature. In Advances in Cryptology – EUROCRYPT’97, volume 1233 of Lecture Notes in Computer Science, pages 465–479. Springer Verlag, 1997.
15. J. Camenisch and M. Michels. A group signature scheme with improved effi-ency. In Advances in Cryptology – ASIACRYPT’98, volume 1514 of Lecture Notes in Computer Science, pages 160–174. Springer Verlag, 1999.
16. J. Camenisch and M. Michels. Separability and efficiency for generic group signature schemes. In Advances in Cryptology – CRYPTO’99, volume 1666 of Lecture Notes in Computer Science, pages 413–430. Springer Verlag, 1999.
17. J. Camenisch and M. Stadler. Efficient group signature schemes for large groups. In Advances in Cryptology – CRYPTO’97, volume 1294 of Lecture Notes in Computer Science, pages 410–424. Springer Verlag, 1997.
18. R. Canetti, O. Goldreich, and S. Halevi. The random oracle model revisited. In 30th ACM Symposium on the Theory of Computing (STOC), pages 209–218. ACM Press, 1998.
19. D. Chaum, A. Fiat, and M. Naor. Untraceable electronic cash. In Advances in Cryptology – CRYPTO’88, volume 403 of Lecture Notes in Computer Science, pages 319–327. Springer Verlag, 1990.
20. D. Chaum, E. van Heijst, and B. Pfitzmann. Cryptographically strong undeni-able signatures, unconditionally secure for the signer. In Advances in Crypto-logy – CRYPTO’91, volume 576 of Lecture Notes in Computer Science, pages 470–484. Springer Verlag, 1991.
21. D. Chaum and E. van Heyst. Group signatures. In Advances in Cryptology – EUROCRYPT’91, volume 547 of Lecture Notes in Computer Science, pages 257–265. Springer Verlag, 1991.
22. L. Chen and T.P. Pedersen. New group signature schemes. In Advances in Cryptology – EUROCRYPT’94, volume 950 of Lecture Notes in Computer Sci-ence, pages 171–181. Springer Verlag, 1994.
23. R. Cramer, I. Damgård, and B. Schoenmakers. Proofs of partial knowledge and simplified design of witness hiding protocols. In Advances in Cryptology – CRYPTO’94, volume 839 of Lecture Notes in Computer Science, pages 174– 187. Springer Verlag, 1994.
24. R. Cramer and V. Shoup. A practical public key cryptosystem provably se-cure against adaptive chosen ciphertext attack. In Advances in Cryptology – CRYPTO’98, volume 1462 of Lecture Notes in Computer Science, pages 13–25. Springer Verlag, 1998.
25. R. Cramer and V. Shoup. Signature schemes based on the strong RSA as-sumption. In 6th ACM Conference on Computer and Communications Security (CCS), pages 46–51. ACM Press, 1999.
26. D. Chaum and E. van Heyst. Group signatures. In Advances in Cryptology – EUROCRYPT’91, volume 547 of Lecture Notes in Computer Science, pages 257–265. Springer Verlag, 1991.
27. L. Chen and T.P. Pedersen. New group signature schemes. In Advances in Cryptology – EUROCRYPT’94, volume 950 of Lecture Notes in Computer Sci-ence, pages 171–181. Springer Verlag, 1994.
28. R. Cramer, I. Damgård, and B. Schoenmakers. Proofs of partial knowledge and simplified design of witness hiding protocols. In Advances in Cryptology – CRYPTO’94, volume 839 of Lecture Notes in Computer Science, pages 174– 187. Springer Verlag, 1994.
29. R. Cramer and V. Shoup. A practical public key cryptosystem provably se-cure against adaptive chosen ciphertext attack. In Advances in Cryptology – CRYPTO’98, volume 1462 of Lecture Notes in Computer Science, pages 13–25. Springer Verlag, 1998.
30. R. Cramer and V. Shoup. Signature schemes based on the strong RSA as-sumption. In 6th ACM Conference on Computer and Communications Security (CCS), pages 46–51. ACM Press, 1999.