Lattices and lattice-based problems

[Cryptodude !xl.hTjTuwM No.5186741]

Any mathematicians here? I'm currently working on a small project for my Masters, and it's based on quantum/post-quantum cryptography.

Anyway, I'm currently going through lattice-based crypto (Learning With Errors, GGG, etc) and I'm reading a lot that "geometrical" lattice-based problems are difficult, while algebraic lattice-based problems are easier.

Anyone got intuition on why this is the case? Or who wants to talk about quantum cryptography in general?

[Anonymous No.5186755]

Can someone clarify the OP's Picture, I remember reading up on it, but did not understand it.

[Anonymous No.5186770]

>>5186755
http://en.wikipedia.org/wiki/Banach%E2%80%93Tarski_paradox

[Anonymous No.5186773]

>>5186741
Hello OP, i'm a second year math major, so I won't be of any help at all (especially considering how badly i fucked up my first year, I may aswell be a freshman) but i'm very curious about your field. What, in layman terms, do you study? Describe it how you would describe it to a dumb bitch on a first date.

[Cryptodude !xl.hTjTuwM No.5186791]

>>5186773

Well, I finished my bachelor's in mathematics. Very little of it was useful, but I did find out what I loved - cryptography. I'm doing my Masters in crypto and operations research (OR for industry in case I fail at getting a Ph.D.)

Anyway, I'm currently concentrating on quantum and post-quantum cryptography. Quantum cryptography is essentially just quantum key distribution. QKD is where we distributed shared secret keys between two parties. The fascinating thing about QKD is that it's uncomputationally secure - no matter how much computation time and power a theoretical eavesdropper has, they cannot have the shared secret key between the two parties.

This is due to the uncertainty principle, and how measurement destroys quantum information. You see, when the eavesdropper listens in, it collapses the superposition the qubit is in, and that eavesdropping can be detected. When the two parties attempt to correlate their shared key, if there are discrepancies beyond what is expected due to noise, the protocol is restarted, and the eavesdropper loses all information.

Now, post-quantum crypto is different. Shor's Algorithm allows us to solve abelian hidden subgroup problems (like factorisation and discrete log problems) in polynomial-time. And abelian hidden subgroup problem are the problems the majority of modern cryptosystems are based on. So, before quantum computers become a real thing, we need cryptosystems and cryptoprimitives that are efficient to run, but quantum resistant.

That's what I do. I recent did a project where I designed a oblivious transfer protocol in a learning with errors enviroment. It's not efficient, or round-optimal, but I'm working on it.

[Anonymous No.5186799]

I'm a mathematician, but I only know shit about geometry, groups and representations. Can't help you with lattices or cryptography I'm afraid.

[n No.5186836]

>>5186791
holy shit this sounds awesome

[Cryptodude !xl.hTjTuwM No.5187512]

>>5186799

That's a shame. Oh well.

Any other takers?

>>5186836

I find it fascinating, and it's a great field for me because it sits nicely between discrete mathematics and algorithm design, which I find pretty natural