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)

What to put in a primitive

Sections

• Formal Definition: syntax and common properties
• Relationship to other primitives
• Minimally sufficient assumptions
• Variations
• Other Notes

What to put in an assumption

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