Are My Interests More Suited for PhD in CS or Mathematics? So let me give a little info of who I am and what my interests are. I just graduated with a BA in Mathematics, concentrating almost exclusively in pure math courses (favoring analysis, algebra, topology, number theory, and combinatorics over computational/applied classes). Next semester I'm beginning a 2-year masters program in computational mathematics (at a group-1 public school, under old AMS rankings). 

My research interests are currently strongest in the following areas: 


Combinatorics, especially algorithmic/computational and combinatorial optimization
Cryptography, information encryption/decryption and security
Number theory, but really just for the purposes of encryption/decryption


After doing some research on the Web, it seems to be the case that my interests fall into the field of theoretical computer science and discrete mathematics. 

At this point in time, my idea of an ideal career would be a professor of math or CS at a university, probably a doctoral-granting university. I might also consider working for the government in information security, data analysis, etc. 

Also, I definitely want a PhD. It's just been one of the constants in my life as a goal. 

So, I pose the question. Given the above information, would a PhD in Math be more appropriate, or would a PhD in CS (probably concentrating in Theoretical CS) be more appropriate?
After doing some research on the Web, it seems to be the case that my interests fall into the field of theoretical computer science and discrete mathematics. 


Yes, I agree.  Moreover these fields have substantial overlap, and your interests lie safely in this intersecting region.  You could plausibly attend either program, and the post-PHD opportunities and career trajectories would be very similar.

One way to think about the decision is that the differences between a math program and a CS program will be more cultural and incidental.  In a US PhD program there are going to be a lot of required components besides your thesis work.  If you attend a math PhD program you will be required to take courses and pass qualifying exams in areas of mathematics somewhat removed from your stated research interests: e.g. I don't know any math PhD program in which you would not have to take graduate level analysis, including measure theory.  Similarly, in a CS program you're going to have to take coursework and pass exams on non-theoretical, non-cryptographic computer science.  Which of these sets of requirements sounds better to you?

If it's really a coin flip, then I would argue in favor of breadth and diversity of skills.  At a certain point you have to specialize, but all other things being equal, I find basic knowledge more useful: it is so much easier to learn more about something than to get a first, rudimentary clue.  Your undergraduate career gave you training in many theoretical areas of mathematics that are not directly related to your current research interests: great!  Now give yourself the advantage of getting some broad training in CS topics as well.

Anyway, it ought to be clear from this answer that I think there is no bad choice.  Good luck!