Network Security Cryptographic Protocols and Lattice Problems

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 Zⁿ /Λ 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.

Keywords: Security properties;  Counterfeiting;  Hierarchical group ;  RSA assumption ;   DDH assumption;  EMV payment cards; Dimensional lattice ;  Arbitrary precision