Contribute to Cryptology City: Difference between revisions

From Cryptology City
Jump to navigation Jump to search
No edit summary
Line 76: Line 76:
! Type of result !! Where it should go !! Example
! Type of result !! Where it should go !! Example
|-
|-
| A implies B || B's "Relationship to other primitives" section || [[OWF]] implies [[PRG]]
| A implies B || B's (and optionally A's) "Relationship to other primitives" section || [[OWF]] implies [[PRG]]
|-
|-
| A+B+... implies C || C's "Relationship to other primitives" section || [[SE]] + [[MAC]] implies [[AE]]
| (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 <math>\Omega(\log n)</math> overhead
| 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" section || There is no black-box reduction from [[OWF]] to [[KA]]
| A (probably) does not imply B || Place in both A and B's "Relationship to other primitives" section || There is no black-box reduction from [[OWF]] to [[KA]]
|-
|}
|}

Revision as of 13:47, 28 June 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.

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:

Assumptions:


What to put in a primitive

Categories

Sections

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

Syntax

What to put in an assumption

Categories

Sections

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

Formal Assumption

Parameters

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 overhead
A (probably) does not imply B Place in both A and B's "Relationship to other primitives" section There is no black-box reduction from OWF to KA