Contribute to Cryptology City: Difference between revisions

From Cryptology City
Jump to navigation Jump to search
No edit summary
 
(11 intermediate revisions by the same user not shown)
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)]]
* [[One-way Function (OWF)]]
* [[Public Key Encryption (PKE)]]
* [[Public Key Encryption (PKE)]]
* [[Oblivious RAM (ORAM)]]


''Assumptions'':
''Assumptions'':
* [[Decision Diffie-Hellman (DDH)]]
* [[Decision Diffie-Hellman (DDH)]]
* [[The RSA Assumption (RSA)]]
* [[Computational Diffie-Hellman (CDH)]]
* [[Discrete Logarithm (DLOG)]]
* [[Learning with Errors (LWE)]]
* [[Learning with Errors (LWE)]]


Line 29: Line 24:
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.
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 [[SE#CPA-secure|CPA-security]] and [[SE#CCA-secure|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.
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.
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.
Line 35: Line 30:
=== Categories ===
=== 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.
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"
{| class="wikitable"
|-
|-
Line 45: Line 41:
| Minicrypt || primitives which are implied by the existence of [[OWF | One-way functions]] (and are not unconditional) || [[Pseudorandom Function (PRF)]]
| Minicrypt || primitives which are implied by the existence of [[OWF | One-way functions]] (and are not unconditional) || [[Pseudorandom Function (PRF)]]
|-
|-
| Cryptomainia || primitives which are implied by [[TDP | Trapdoor Permutations]] (and not [[OWF]]s) || [[Public Key Encryption (PKE)]]
| 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]]
| Obfustopia || primitives which are implied by [[IO | Indistinguishability Obfuscation]] (and not [[TDP]]s) || [[Deniable Encryption]]
Line 52: Line 48:
|-
|-
|}
|}
</center>


So, at the top of a page like, e.g., [[PRF]], we would put
So, at the top of a page like, e.g., [[PRF]], we would put
Line 63: Line 60:


=== Sections ===
=== 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.
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.
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"
{| class="wikitable"
|-
|-
Line 86: Line 83:
|-  
|-  
|}
|}
</center>


=== Syntax ===
=== 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 ==
== 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 ===
=== 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 ===
=== Sections ===
* Implied primitives
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.
* Formal Assumption
<center>
* Parameters
{| class="wikitable"
* Relationship to other assumptions
|-
* Other Notes
! Section Title !! Content || How Necessary?
 
|-
=== Formal Assumption ===
| Parameters || discussion and list of parameters made in the assumption || Sometimes
 
|-
=== Parameters ===
| 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 ==
Line 123: Line 144:


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.
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"
{| class="wikitable"
|+ Where should my result go?
|+ Where should my result go?
Line 140: Line 161:
|-
|-
|}
|}
</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