Contribute to Cryptology City

Cryptology City is a large project and requires many people to work together to create something useful. One reason that it is so difficult to systematize cryptology is that there are a variety of definitions, notations, variations, and colliding terms throughout a lot of the literature. It's very easy to get confused or lost in the details.

This flexibility is often useful! It allows authors to tailor their presentation for their paper, but here we want to try to bring everything under similar(ish) notation and standards where possible. This page should hopefully serve as a guide for contributors who are not sure what to include in their contributions or how to format them.

For people are more interested in the broader direction of the website or would like to help beyond adding to the knowledge base, I have also started a Keybase team to discuss the project in more detail. Feel free to join me there!

For those who are more keen to pattern match, here are some prototypical examples of Cryptology City pages.

Primitives:

• Pseudorandom Function (PRF)
• One-way Function (OWF)
• Public Key Encryption (PKE)
• Oblivious RAM (ORAM)

Assumptions:

• Decision Diffie-Hellman (DDH)
• RSA Assumption
• Computational Diffie-Hellman (CDH)
• Discrete Logarithm (DLOG)
• Learning with Errors (LWE)

How to edit primitives

One of the primary goals of Cryptology City it to accumulate all sorts of different cryptographic primitives that have been introduced throughout lots of literature. However, there are a lot of varieties of primitives, so it's easy to not know where a particular primitive should go or what information it should contain.

If you aren't sure if your new primitive should have its own page, consider whether it requires different syntax from all other (related) primitives. For example, a Symmetric Encryption (SE) has different syntax from a Public Key Encryption (PKE), since the latter has a generation that outputs two keys which are fed into the encryption and decryption differently.

Howerver the properties of primitives are not on separate pages. For example, both CPA-security and CCA-security are both located on the SE page (and also the public key variants on the PKE page. This is because although the security games are different, the syntax does not change for the primitive.

If there's any other confusion about where to place new information, feel free to reach out to other collaborators, or just put it where you think is best.

Sections

• Formal Definition: syntax and common properties (e.g. security, privacy, soundness)
• Equivalent Definitions
• Relationship to other primitives
• Minimally sufficient assumptions
• Variations
• Other Notes

How to edit assumptions

Sections

• Implied primitives
• Formal Assumption
• Parameters
• Relationship to other assumptions
• Other Notes

Adding citations

The best way to add a citation is to add a reference to the References page using the Template:Reference which is made to be used as in the following example:

{{Reference
    |id=cdh20 |tag=CDH20
    |title=A Lower Bound for One-Round Oblivious RAM
    |authors=D. Cash, A. Drucker, and A. Hoover
    |journal=TCC
    |srcdetail=2020
    |link=https://eprint.iacr.org/2020/1195
}}

I try to keep the list in References alphabetized by the author abbreviation, but as long as the first author initial is in the right place it should be easy to fix later on.

To then add the citation to the page in question, you can use (for example) "[[ccref#cdh20 | [CDH20]]]" which renders as [CDH20]. Make sure to use the lower case id after the ccref# to that it creates a direct link to the citation on the References page.

Adding a new result

Some of the best cryptography papers don't introduce new primitives or rely on new assumptions. In fact, it's great to remove/change assumptions or rely on existing primitives to do interesting stuff. If there's a connection between primitives or assumptions that isn't new, it's still very useful to add it to the city!

Below, we outline the convention that we try to stick to for certain types of results between primitives. If there's some other relationship, feel free to create an “Other Notes” section on the relevant page and put it there. If it can be folded in, hopefully someone can come along and do that later. Make sure to add the relevant citations, wherever it is placed, though.

Where should my result go?

Type of result	Where it should go	Example
A implies B	B's (and optionally A's) “Relationship to other primitives” section	OWF implies PRG
(A+B+...) implies A with a new property	A's “Relationship to other primitives” section	CPA-secure SE + MAC implies CCA-secure SE
(A+B+...) implies C	C's “Relationship to other primitives” section	Digital Signatures + Hash Function implies Blockchain
A cannot achieve E	A's “Impossibility results” or “Other Notes” sections	ORAM must have $\Omega (\log n)$ overhead
A (probably) does not imply B	Place in both A and B's “Relationship to other primitives” section	There is no black-box construction of KA from OWF