Protecting my encryption algorithm if the attacker knows the key
You are asked to provide a program doing the encryption but not the decryption. That means the obvious solution is to use asymmetrical cryptography. Any standard asymmetrical encryption algorithm will do.
You say:
If the program uses a key or some other parameter necessary for the decryption of the ciphertext, we must provide it to him.
But you only stated that you had to hand in a program for encryption not decryption. Obviously with asymmetrical encryption the program you hand in for encryption will not make use of the decryption key.
If you had to hand in both decryption code and decryption key, there would be nothing you could do to protect your cihpertext. If you have to hand in only the key and not the code, this opens op a major loophole, you could take advantage of.
Many cryptographic algorithms include random looking constants. If you are free to design your own algorithm, the boundary between constants in the algorithm and the key can be manipulated as you wish. Take any standard algorithm call the constants in the algorithm the key and hand those over and call the key of the original algorithm constants (which will then be hardcoded in the decryption program, which you do not have to hand in).
That would certainly be bending the rules to your advantage, but it would still be within the word of the rules as stated in your question. Of course I cannot rule out the possibility that you accidentally worded the constraints differently from how it was intended, in which case this solution may not apply.
You also ask:
So it boils down to making something original I guess
I would be surprised if that was the intention. Certainly coming up with an original algorithm is not considered to be the way in which security is achieved.
Maybe the professor wanted to make a point about the security about original algorithms by showing how all the original algorithms would be broken. However if that's the intention of the challenge, then the professor is running the risk that one of the solutions only has vulnerabilities too subtle for the professor to immediately exploit.
So your professor is forcing you to use Security through Obscurity. Interesting. In the real world you design a security system around Kerckhoffs's principle that you should assume that an attacker knows everything about your system except the keys. This assignment is the exact opposite, interesting.
First, a nit-picky but important point: the sentence "We win if he cannot decrypt the given ciphertext." should set off warning bells because the idea that you can make a system which is "unbreakable" is one of the biggest misconceptions about information security: you cannot.
Given enough time and effort, a clever attacker can break any crypto system, no matter how well-built. This is why I love the phrase "hardening a system" because it implies that you're making things harder for the attacker, but it admits that it's still possible to break.
As for your assignment, I guess the main question is to figure out what the professor is looking for. I would guess that he is looking to see that you've thought about a range of possible attacks, and that you can put the crypto building-blocks together in a sensible way. (He may also be hoping that a student will surprise him with some clever new system that he's never thought of before.)
Your idea to do everything server-side so that he has no executable to decompile is a great idea.
Some other things to think about (off the top of my head):
Don't invent your own, it's a better use of your time to combine together common building blocks in a clever way.
It sounds like he's expecting you to chain together several encryption algorithms. As pointed out in the linked question, it doesn't get used much in practice because it violates Kerckhoffs's principle, but it makes perfect sense for your assignment so start with that.
You have to give him all key / initialization material, so he's probably going to try to make some guesses based on the size of the keys ("ah, this looks like a 1024-bit RSA key, let's try RSA..."). But nothing says that real keys have to be the same ones that the prof has, just that you have to be able to derive the real keys from the keying material that you give him. I would look at Key Derivation Functions and Key Stretching Functions as ways to roll around the key material before actually using it (concatenating / truncating hashes is also a good trick).
If you are allowed to use your fully server-side idea, then think about rate-limiting how often he can send in a plaintext to get encrypted (ie only 1 attempt per 5 seconds).
Even if you have to give him a binary, use a really slow hash function / key stretching function so he has to waste lots of time waiting for it to run.
As @Schroeder said, this is a fun problem and I would love to keep thinking about it, but I should probably get back to work...