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. Here I'm most focused on page layouts and where results should be placed in the wiki, but for more information about the formatting markup language, you can go here.

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 examples of Cryptology City pages.

Primitives:

• Pseudorandom Function (PRF)
• Public Key Encryption (PKE)

Assumptions:

• Decision Diffie-Hellman (DDH)
• Learning with Errors (LWE)

Primitive pages

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. Also, the page titles are generally singular as a standard (e.g. Pseudorandom Function (PRF) rather than Pseudorandom Functions]]). Although, it is also ok to redirect from one to the other.

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.

Categories

The first part of a primitive page should be focused on setting the categories (which ironically appear at the bottom). This is very easy in the current version of the website, because there aren't many categories. I'm interested in creating more or more detailed ones later, but for now I have a list of the ones to use below.

Category	What goes there?	Example
Primitives	all primitive pages should have this category	Everything
Unconditional	primitives which satisfy their key properties unconditionally	Fingerprinting Code
Minicrypt	primitives which are implied by the existence of One-way functions (and are not unconditional)	Pseudorandom Function (PRF)
Cryptomania	primitives which are implied by Trapdoor Permutations (and not OWFs)	Public Key Encryption (PKE)
Obfustopia	primitives which are implied by Indistinguishability Obfuscation (and not TDPs)	Deniable Encryption
Quantum	primitives which have quantum algorithms (i.e. syntax with quantum inputs or outputs)	Pseudorandom Quantum State (PRQS)

So, at the top of a page like, e.g., PRF, we would put

<noinclude>
[[Category:Primitives]]
[[Category:Minicrypt]]

which indicates that a PRF is a primitive and that it exist in Minicrypt (i.e. implied by the existence of OWFs).

In the future, these categories may become more complicate, based on number of parties, threat models, statistical/computational security, etc. This would be an interesting contribution for those interested, but is not necessary now.

Sections

The next (and main) part of a primitives page involves describing the actual primitive, and it's relationship to other primitives. Below is a list of the suggested sections for a very complete entry. It's definitely possible that a primitive does not need all of these sections (or maybe requires more), but this is what we try to keep as the standard format.

It is probably best to look at an example like PRFs to see how each should be implemented. You can also look at the adding a new result section for more details on where results should be placed.

Section Title	Content	How Necessary?
Formal Definition	syntax and common properties (e.g. security, privacy, soundness)	Almost always
Equivalent Definitions	either a brief discussion or alternative syntax which is directly equivalent to the version introduced earlier in the section	Rarely
Relationship to other primitives	a list of known implications and relationships to other primitives with cited works	Often
Impossibilities	known barriers to constructing the primitive listed	Sometimes
Minimally sufficient assumptions	the weakest assumptions necessary to construct the primitive, as best we know	Sometimes
Variations	other primitives that are clearly related to the topic primitive in terms of syntax/properties/etc. often just more specific versions of general primitives (e.g. iPRF is a variation of a PRF)	Sometimes
Other Notes	any other observations related to the primitive	Sometimes

Syntax

There is a lot of variation in naming conventions throughout the cryptographic literature. Ideally, the notation across the website will remain consistent whenever possible, but this is really just a preference. When possible, I hope people stick with the convention to give primitives as tuples of algorithms or protocols, each with a semantically relevant sans-serif or the standard name. Hopefully, this allows newcomers to understand the meaning of algorithms when they engage with them. So, for example, the syntax for a Language Model Watermark is $({\mathsf {Gen}},{\mathsf {Wat}},{\mathsf {Extract}})$.

Assumption pages

In addition to primitive definitions, Cryptology City also can serve as a repository for the types of assumptions make throughout the cryptographic literature. It's useful to understand how different attacks cut against the known security of certain types of primitives. Also, it can hopefully let people identify where primitive constructions could be strengthened.

Categories

The first part of an assumption page should set the categories for the relevant assumption. The only categories that are currently considered for assumptions are the broad Assumptions category and the Pre-quantum category (things which are known to not be post-quantum secure). In the future, there may be more but for now this is all we consider. So, for example the top of LWE looks like,

<noinclude>
[[Category:Assumptions]]

but the DDH page is:

<noinclude>
[[Category:Assumptions]]
[[Category:Pre-quantum]]

as it is not secure against quantum adversaries.

Sections

The main part of an assumption page should formally describe what an assumption assumes to be heard, as well as its relationship to other assumptions and primitives. Below is a list of the suggested sections. It's definitely possible that an assumption does not need all of these sections (or maybe requires more), but this is what we try to keep as the standard format.

Section Title	Content	How Necessary?
Formal assumption	formally stating the problem that is assumed to be difficult	Always
Parameters	discussion and list of parameters made in the assumption	Sometimes
Known attacks	discussion of best attacks against the assumption (and the parameters they work in)	Often
Relationship to other assumptions	a list of known implications and relationships to other assumptions with cited works	Rarely
Implied primitives	list of primitives that are directly implied by the assumption with cited works	Sometimes
Other Notes	any other observations related to the assumption	Sometimes

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	Fingerprinting Code + Language Model Watermark implies Multi-user Watermark
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