Contribute to Cryptology City: Difference between revisions

From Cryptology City
Jump to navigation Jump to search
(add keybase team link)
No edit summary
 
(24 intermediate revisions by the same user not shown)
Line 1: Line 1:
[[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.
[[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.
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 [https://www.mediawiki.org/wiki/Help:Formatting go here].


For people are more interested in the broader direction of the website or would like to
For people are more interested in the broader direction of the website or would like to
Line 8: Line 8:
Feel free to join me there!
Feel free to join me there!


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


''Primitives'':
''Primitives'':
* [[Pseudorandom Function (PRF)]]
* [[Pseudorandom Function (PRF)]]
* [[Puncturable PRF]]
* [[Public Key Encryption (PKE)]]
* [[Private Information Retrieval (PIR)]]
* [[Oblivious RAM (ORAM)]]
* [[One-way Function (OWF)]]


''Assumptions'':
''Assumptions'':
* [[Decision Diffie-Hellman (DDH)]]
* [[Decision Diffie-Hellman (DDH)]]
* [[Computational Diffie-Hellman (CDH)]]
* [[Learning with Errors (LWE)]]
* [[Learning with Errors (LWE)]]




== Creating a new primitive ==
== 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.


== Creating a new assumption ==
Howerver the ''properties'' of primitives are '''not''' on separate pages. For example, both [[SE#CPA-security|CPA-security]] and [[SE#CCA-security|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.
<center>
{| class="wikitable"
|-
! 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 [[OWF | One-way functions]] (and are not unconditional) || [[Pseudorandom Function (PRF)]]
|-
| Cryptomania || primitives which are implied by [[TDP | Trapdoor Permutations]] (and not [[OWF]]s) || [[Public Key Encryption (PKE)]]
|-
| Obfustopia || primitives which are implied by [[IO | Indistinguishability Obfuscation]] (and not [[TDP]]s) || [[Deniable Encryption]]
|-
| Quantum || primitives which have quantum algorithms (i.e. syntax with quantum inputs or outputs) || [[Pseudorandom Quantum State (PRQS)]]
|-
|}
</center>
So, at the top of a page like, e.g., [[PRF]], we would put
<nowiki>
<noinclude>
[[Category:Primitives]]
[[Category:Minicrypt]]</nowiki>
which indicates that a [[PRF]] is a primitive and that it exist in Minicrypt (i.e. implied by the existence of [[OWF]]s).
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 [[PRF]]s to see how each should be implemented. You can also look at [[Contribute_to_Cryptology_City#Adding_a_new_result | the adding a new result section]] for more details on where results should be placed.
<center>
{| class="wikitable"
|-
! 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
|-
|}
</center>
=== 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 <math>(\mathsf{Gen},\mathsf{Wat},\mathsf{Extract})</math>.
== 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,
<nowiki>
<noinclude>
[[Category:Assumptions]]</nowiki>
but the [[DDH]] page is:
<nowiki>
<noinclude>
[[Category:Assumptions]]
[[Category:Pre-quantum]]</nowiki>
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.
<center>
{| class="wikitable"
|-
! Section Title !! Content || How Necessary?
|-
| Parameters || discussion and list of parameters made in the assumption || Sometimes
|-
| Formal assumption || formally stating the problem that is assumed to be difficult || Always
|-
| 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
|-
|}
</center>


== Adding citations ==
== 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:
<nowiki>{{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
}}</nowiki>


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) "<nowiki>[[ccref#cdh20 | [CDH20]]]</nowiki>" which renders as [[ccref#cdh20 | [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 ==
== 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.
<center>
{| class="wikitable"
|+ 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 <math>\Omega(\log n)</math> 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]]
|-
|}
</center>

Latest revision as of 15:41, 4 July 2024

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:

Assumptions:


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 .

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?
Parameters discussion and list of parameters made in the assumption Sometimes
Formal assumption formally stating the problem that is assumed to be difficult Always
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 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