Protocols
Contents
Authentication
Basics
- Cryptographic Protocol - Wikipedia
- Authentication - Wikipedia - can be considered to be of three types:
- Accepting proof of identity given by a credible person who has first-hand evidence that the identity is genuine. This can be organised centralised or decentralised.
- Comparing the attributes of the object itself to what is known about objects of that origin (e.g. a painting).
- Relying on documentation or other external affirmations. In criminal courts, the rules of evidence often require establishing the chain of custody of evidence presented.
- Authentication Protocol - Wikipedia
Password based
- PACE Password Authenticated Connection Establishment
- Developed by the German Bundesamt für Sicherheit in der Informationstechnik (BSI), free of patents
- Establishes a shared session key between a contactless smartcard and terminal using the DH key agreement protocol
- As DH key agreement does not support authentication it is vulnerable to man-in-the-middle at-tacks. To prevent this and to ensure user consent, PACE uses a password-based protocol to protect the wireless communication interface between the terminal and the card before the card is accessed. In the most common scenario a PIN, permanently stored in the card and entered into the terminal by the user.
- As the password is used during the calculation of the session key, entering a wrong password leads to different session keys on both sides which causes the connection establishment to fail.
Other authentication protocols
- Wultra Powerauth
- Wultra Powerauth developer doc
- A protocol for a key exchange and for subsequent request signing
- Based on a used cryptography, a security scheme and standard RESTful API end-points
- OPAQUE
- A secure asymmetric password-authenticated key exchange (aPAKE) that supports mutual authentication in a client-server setting without reliance on PKI and with security against pre-computation attacks upon server compromise
Secret sharing and thresholds
Basics
- Secret Sharing (splitting) - Wikipedia - Shamir's scheme (SSS), Blakley's scheme
- Verifiable Secret Sharing (VSS) - Wikipedia Feldman's scheme, Benaloh's scheme, secret ballot elections
- A secret sharing scheme is verifiable if auxiliary information is included that allows players to verify their shares as consistent.
- VSS ensures that even if the dealer is malicious there is a well-defined secret that the players can later reconstruct. In standard secret sharing, the dealer is assumed to be honest.
- VSS was first introduced in 1985 by Benny Chor, Shafi Goldwasser, Silvio Micali and Baruch Awerbuch.
- The dealer is a distinguished player who wants to share the secret
- The protocol consists of two phases: a sharing phase and a reconstruction phase.
- Sharing: Initially the dealer holds secret as input and each player holds an independent random input. The sharing phase may consist of several rounds. At each round each player can privately send messages to other players and can also broadcast a message. Each message sent or broadcast by a player is determined by its input, its random input and messages received from other players in previous rounds.
- Reconstruction: In this phase each player provides its entire view from the sharing phase and a reconstruction function is applied and is taken as the protocol's output.
- An alternative definition given by Oded Goldreich defines VSS as a secure multi-party protocol for computing the randomized functionality corresponding to some (non-verifiable) secret sharing scheme. This definition is stronger than that of the other definitions and is very convenient to use in the context of general secure multi-party computation.
- Verifiable secret sharing is important for MPC, which is typically accomplished by making secret shares of the inputs, and manipulating the shares to compute some function.
- To handle "active" adversaries (that is, adversaries that corrupt nodes and then make them deviate from the protocol), the secret sharing scheme needs to be verifiable to prevent the deviating nodes from throwing off the protocol.
- Publicly Verifiable Secret Sharing - Wikipedia
- A secret sharing scheme is publicly verifiable (PVSS) if it is a verifiable secret sharing scheme and if any party (not just the participants of the protocol) can verify the validity of the shares distributed by the dealer.
- Chaum-Pedersen protocol - ref voting infra
- A simple PVSS and its application to e-voting - Berry Schoenmakers
Commitment
Applications include secure coin flipping, zero-knowledge proofs, and secure computation.
Basics
- Commitment scheme - Wikipedia
- Allows one to commit to a chosen value (or chosen statement) while keeping it hidden to others, with the ability to reveal the committed value later.
- Notion of commitments appeared earliest in works by Manuel Blum, Shimon Even, and Shamir et al. The terminology seems to have been originated by Blum.
- Formalized by Gilles Brassard, David Chaum, and Claude Crepeau in 1988 as part of various Zero-Knowledge protocols for NP.
- Use in ZK:
- To allow the prover to participate in "cut and choose" proofs where the verifier will be presented with a choice of what to learn, and the prover will reveal only what corresponds to the verifier's choice. Commitment schemes allow the prover to specify all the information in advance, and only reveal what should be revealed later in the proof.
- To allow a verifier to specify their choices ahead of time in a commitment. This allows zero-knowledge proofs to be composed in parallel without revealing additional information to the prover.
Polynomial commitments
A polynomial commitment scheme allows a prover to compute a commitment to a polynomial, with the properties that this commitment can later be opened at any position: The prover shows that the value of the polynomial at a certain position is equal to a claimed value.
It is called a commitment, because having sent the commitment value (an elliptic curve point) to someone (the verifier), the prover cannot change the polynomial they are working with. They will only be able to provide valid proofs for one polynomial, and if they are trying to cheat, they will either fail to produce a proof or the proof will be rejected by the verifier.
Oblivious Transfer - Private Information retrieval (PIR)
Basics
- Oblivious transfer protocol - Wikipedia
- Protocol in which a sender transfers one of potentially many pieces of information to a receiver, but remains oblivious as to what piece (if any) has been transferred.
- The first form of OT was introduced in 1981 by Michael O. Rabin./li>
- A more useful form called 1–2 OT or "1 out of 2 OT" was developed by Even, Goldreich, and Lempel. Useful in MPC.
- Generalized to 1 out of n OT where the user gets exactly one database element without the server getting to know which element was queried, and without the user knowing anything about the other elements that were not retrieved. The latter notion of oblivious transfer is a strengthening of private information retrieval, in which the database is not kept private.
- k-n OT is a special case of generalized oblivious transfer.
- Rabin OT - IPython
Refer also to privacy information.
Intro PETs
Fiat-Shamir (creating a signature on a proof of knowledge)
The Fiat–Shamir heuristic is a technique for taking an interactive proof of knowledge and creating a digital signature based on it. This way, some fact (for example, knowledge of a certain secret number) can be publicly proven without revealing underlying information. The technique is due to Amos Fiat and Adi Shamir (1986). For the method to work, the original interactive proof must have the property of being public-coin, i.e. verifier's random coins are made public throughout the proof protocol.
Feige-Fiat-Shamir (ZK identification based on modular arithmetic)
A type of parallel zero-knowledge proof developed by Uriel Feige, Amos Fiat, and Adi Shamir in 1988. Like all zero-knowledge proofs, it allows one party, the Prover, to prove to another party, the Verifier, that they possess secret information without revealing to Verifier what that secret information is. The Feige–Fiat–Shamir identification scheme, however, uses modular arithmetic and a parallel verification process that limits the number of communications between Prover and Verifier.
Direct Anonymous Attestation
A protocol that enables remote authentication of a trusted computer (TPM) whilst preserving privacy of the platform's user. It has been adopted by the Trusted Computing Group (TCG). See also ISO/IEC 20008.
Zero Knowledge
Goldreich: Zero-knowledge proofs are probabilistic and interactive proofs that efficiently demonstrate membership in the language without conveying any additional knowledge. The wide applicability of zero-knowledge was demonstrated in Proofs that Yield Nothing But their Validity or All Languages in NP have Zero-Knowledge Proofs, coauthored by Goldreich, Micali and Wigderson [JACM, July 1991]. In particular, assuming the existence of one-way functions, it is shown that every language in NP has a zero-knowledge proof system.
ZK introduction
- ZK proof - Wikipedia
- Interactive Proof System (IPS) - Wikipedia Arthur-Merlin, Public coin, private coin protocols, Probabilistic Checkable Proofs, ...
- If we allow the probabilistic verifier machine and the all-powerful prover to interact for a polynomial number of rounds, we get the class of problems called IP. In 1992, Adi Shamir revealed in one of the central results of complexity theory that IP equals PSPACE, the class of problems solvable by an ordinary deterministic Turing machine in polynomial space
- ZKPs were first mentioned in the original 1985 paper on IP by Goldwasser, Micali and Rackoff, but the extent of their power was shown by Oded Goldreich, Silvio Micali and Avi Wigderson.
- Goldwasser in 1988 introduced "Multi prover interactive proofs: How to remove intractability assumptions", which defines a variant of IP called MIP in which there are two independent provers. The two provers cannot communicate once the verifier has begun sending messages to them. Just as it's easier to tell if a criminal is lying if he and his partner are interrogated in separate rooms, it's considerably easier to detect a malicious prover trying to trick the verifier into accepting a string not in the language if there is another prover it can double-check with.
- Non-interactive ZK proof - Wikipedia
- Cryptographic primitives where information between a prover and a verifier can be authenticated by the prover, without revealing any of the specific information beyond the validity of the statement itself.
- This makes direct communication between the prover and verifier unnecessary, effectively removing any intermediaries.
- The core trustless cryptography "proofing" involves a hash function generation of a random number, constrained within mathematical parameters (primarily to modulate hashing difficulties) determined by the prover and verifier.
- Key advantage is that they can be used in situations where there is no possibility of interaction between the prover and verifier, such as in online transactions where the two parties are not able to communicate in real time.
- Useful in decentralized systems like blockchains, where transactions are verified by a network of nodes and there is no central authority to oversee the verification process.
- Mostly based on elliptic curve cryptography or pairing-based cryptography, which allow for the creation of short and easily verifiable proofs of the truth of a statement.
- Unlike interactive zero-knowledge proofs, which require multiple rounds of interaction between the prover and verifier, non-interactive zero-knowledge proofs are designed to be efficient and can be used to verify a large number of statements simultaneously.
- Some history:
- Blum, Feldman, and Micali (1988) showed that a common reference string (crs) shared between the prover and the verifier is sufficient to achieve computational zero-knowledge without requiring interaction.
- Goldreich and Oren gave impossibility results for one shot zero-knowledge protocols in the standard model.
- In 2003, Shafi Goldwasser and Yael Tauman Kalai published an instance of an identification scheme for which any hash function will yield an insecure digital signature scheme. These results are not contradictory, as the impossibility result of Goldreich and Oren does not hold in the crs model or the random oracle model. Non-interactive zero-knowledge proofs however show a separation between the cryptographic tasks that can be achieved in the standard model and those that can be achieved in 'more powerful' extended models.
- The model influences the properties that can be obtained from a zero-knowledge protocol. Pass showed that in the crs model non-interactive zero-knowledge protocols do not preserve all of the properties of interactive zero-knowledge protocols; e.g., they do not preserve deniability.
- Non-interactive zero-knowledge proofs can also be obtained in the random oracle model using the Fiat–Shamir heuristic.
- zk-SNARKS: Chiesa et al developed the zk-SNARK protocol (2012), used in the Zerocash blockchain. Zcash utilized zk-SNARKs to facilitate four distinct transaction types: private, shielding, deshielding, and public. This allowed users to determine how much data was shared with the public ledger for each transaction.
- Ethereum zk-Rollups also utilize zk-SNARKs to increase scalability.
- In 2017, Bulletproofs was released, which enable proving that a committed value is in a range using a logarithmic (in the bit length of the range) number of field and group elements. Bulletproofs was later implemented into Mimblewimble protocol (the basis for Grin and Beam, and Litecoin via extension blocks) and Monero cryptocurrency.
- zk-STARKs: In 2018, the zk-STARK (zero-knowledge Scalable Transparent Argument of Knowledge) protocol was introduced by Eli Ben-Sasson, Iddo Bentov, Yinon Horesh, and Michael Riabzev, offering transparency (no trusted setup), quasi-linear proving time, and poly-logarithmic verification time. zk-STARKs are a type of cryptographic proof system that enables one party (the prover) to prove to another party (the verifier) that a certain statement is true, without revealing any additional information beyond the truth of the statement itself. zk-STARKs are succinct, meaning that they allow for the creation of short proofs that are easy to verify, and they are transparent, meaning that anyone can verify the proof without needing any secret information.
- Unlike the first generation of zk-SNARKs, zk-STARKs, by default, do not require a trusted setup, which makes them particularly useful for decentralized applications like blockchains. Additionally, zk-STARKs can be used to verify many statements at once, making them scalable and efficient.
- In 2019, HALO recursive zk-SNARKs without a trusted setup were presented.
- ZK background at circom
- Oded Goldreich - Wikipedia - books, GMW papers, ...
- 'A Graduate Course in Applied Cryptography' - Dan Boneh and Victor Shoup, part III protocols (proving properties in zero-knowledge)
- ZK proof - Wikipedia
ZK basics
A ZK proof is a protocol that enables a prover to convince a verifier, that a statement is true without revealing any information beyond the veracity of the statement. For example, a prover can create proofs for statements like:
- "I know the private key that corresponds to this public key" : in this case, the proof would not reveal any information about the private key.
- "I know a private key that corresponds to a public key from this list" : as before, the proof would not reveal information about the private key but in this case, the associated public key would also remain private.
- "I know the preimage of this hash value" : in this case, the proof would show that the prover knows the preimage but it would not reveal any information about the value of that preimage.
- "This is the hash of a blockchain block that does not produce negative balances" : in this case, the proof would not reveal any information about the amount, origin or destination of the transactions included in the block.
Consider a client owning a public input x, a server owns a private input w, and the client wishes to learn z := F (x, w) for a program F known to both parties. For instance, x may be a query, w a confidential database, and F the program that executes the query on the database.
- Security.
- The client is concerned about integrity of computation: how can he ascertain that the server reports the correct output z?
- In contrast, the server is concerned about confidentiality of his own input: how can he prevent the client from learning information about w?
- The server, acting as the prover, attempts to convince the client, acting as the verifier, that the following NP statement is true: “there exists w such that z = F (x, w)”. Indeed:
- The soundness property of the proof system guarantees that, if the NP statement is false, the prover cannot convince the verifier (with high probability). Thus, soundness addresses the client’s integrity concern.
- The zero-knowledge property of the proof system guarantees that, if the NP statement is true, the prover can convince the verifier without leaking any information about w (beyond was is leaked by the output z). Thus, zero knowledge addresses the server’s confidentiality concern.
- Moreover, the client sometimes not only seeks soundness but also proof of knowledge which guarantees that, whenever he is convinced, not only can he deduce that a witness w exists, but also
that the server knows one such witness. This stronger property is often necessary to security if F encodes cryptographic computations, and is satisfied by most zero-knowledge proof systems.
Overviews
- ZKproof.org standardize and mainstream cryptography by building a community-driven trust ecosystem
Voting
See https://documentation.heliosvoting.org/verification-specs/helios-v1-and-v2-verification-specs
In Helios voting (used by e.g. KU-Leuven) the proof is a Chaum-Pedersen proof of a DDH tuple.
See https://en.wikipedia.org/wiki/Publicly_Verifiable_Secret_Sharing
zk SNARKS (Succinct Non-Interactive Zero Knowledge)
For a taxonomy of snarks see e.g. 'Proofs, Arguments, and Zero-Knowledge' Justin Thaler, 2023, Chapter 19.
Building block: trusted setup
ZK-SNARKs depend on trusted setups. A trusted setup ceremony is a procedure that is done once to generate a piece of data that must then be used every time some cryptographic protocol is run. Generating this data requires some secret information; the "trust" comes from the fact that some person or some group of people has to generate these secrets, use them to generate the data, and then publish the data and forget the secrets. But once the data is generated, and the secrets are forgotten, no further participation from the creators of the ceremony is required.
See a.o. this Vitalik Buterin's post
Building block: R1CS
- Some SNARKS supports proving/verifying membership in a specific NP-complete language such as R1CS (rank-1 constraint systems). An instance of the language is specified by a set of equations over a prime field F, and each equation looks like: < A, (1,X) > * < B , (1,X) > = < C, (1,X) > where A,B,C are vectors over F, and X is a vector of variables.
- Arithmetic (as well as boolean) circuits are easily reducible to R1CS by converting each gate into a rank-1 constraint. See Ben-Sasson Appendix E (and "System of Rank 1 Quadratic Equations").
- R1CS in Rust
Groth16
An R1CS-based zkSNARK with tooling such as bellman, zokrates and circom. The proof system used by ZCash, Hermez, DarkForest, TornadoCash, Semaphore, Loopring, and others.
Tooling
Some other Snarks
Other
Anonymous Credentials
Camenisch and IDEMIX
Refer also to entity authentication local information.
Idemix is based on 'J. Camenisch and A. Lysyanskaya. Efficient non-transferable anonymous multi-show credential system with optional anonymity revocation'
Other
Privacy Pass
Provides anonymous single-use tokens, based on oblivious pseudorandom functions on elliptic curve. Standardised by IETF.
Selective Disclosure
SD basics
Brands and Microsoft U-Prove
BBS and BBS+
The BBS+ signature scheme, described by Ho Au et al. as an extension of the BBS group signature scheme by Boneh et al. , is a signature scheme often adapted to support a feature called selective
disclosure.
SD-JWT
TOR
TLS
IPSEC
IPSEC is a network protocol suite that authenticates and encrypts the packets of data to provide secure encrypted communication between two computers over an Internet Protocol network. It is used in virtual private networks (VPNs).
SSH
SSH basics
SSH is a network protocol for operating network services securely over an unsecured network. Its most notable applications are remote login and command-line execution.
SSH operates as a layered protocol suite comprising three principal hierarchical components:
- the transport layer provides server authentication, confidentiality, and integrity
- the user authentication protocol validates the user to the server
- the connection protocol multiplexes the encrypted tunnel into multiple logical communication channels
SSH may be used in several ways. In the simplest manner, both ends of a communication channel use automatically generated public-private key pairs to encrypt a connection, and then use a password to authenticate the user.
Command: 'ssh -V' gives version (OpenSSH), 'man ssh' gives info.
'ssh -Q cipher' queries symmetrical ciphers, e.g.
- 3des-cbc
- aes128-cbc
- aes192-cbc
- aes256-cbc
- rijndael-cbc@lysator.liu.se
- aes128-ctr
- aes192-ctr
- aes256-ctr
- aes128-gcm@openssh.com
- aes256-gcm@openssh.com
- chacha20-poly1305@openssh.com
'ssh -Q cipher-auth' queries symmetric ciphers that support authenticated encryption), e.g.
- aes128-gcm@openssh.com
- aes256-gcm@openssh.com
- chacha20-poly1305@openssh.com
'ssh -Q mac' queries macs, e.g.
- hmac-sha1
- hmac-sha1-96
- hmac-sha2-256
- hmac-sha2-512
- hmac-md5
- hmac-md5-96
- umac-64@openssh.com
- umac-128@openssh.com
- hmac-sha1-etm@openssh.com
- hmac-sha1-96-etm@openssh.com
- hmac-sha2-256-etm@openssh.com
- hmac-sha2-512-etm@openssh.com
- hmac-md5-etm@openssh.com
- hmac-md5-96-etm@openssh.com
- umac-64-etm@openssh.com
- umac-128-etm@openssh.com
'ssh -Q key', 'ssh -Q key-cert' and 'ssh -Q key-plain' query key types.
'ssh -Q kex' queries key exchange algorithms, e.g.
- diffie-hellman-group1-sha1
- diffie-hellman-group14-sha1
- diffie-hellman-group14-sha256
- diffie-hellman-group16-sha512
- diffie-hellman-group18-sha512
- diffie-hellman-group-exchange-sha1
- diffie-hellman-group-exchange-sha256
- ecdh-sha2-nistp256
- ecdh-sha2-nistp384
- ecdh-sha2-nistp521
- curve25519-sha256
- curve25519-sha256@libssh.org
'ssh -Q sig' queries signature algorithms, e.g.
- ssh-ed25519
- ssh-rsa
- rsa-sha2-256
- rsa-sha2-512
- ssh-dss
- ecdsa-sha2-nistp256
- ecdsa-sha2-nistp384
- ecdsa-sha2-nistp521
SSH other
Quantum Key Distribution
A secure communication method which implements a cryptographic protocol involving components of quantum mechanics. It enables two parties to produce a shared random secret key known only to them, which can then be used to encrypt and decrypt messages.
Signal
The Signal protocol is a cryptographic messaging protocol that provides end-to-end encryption for instant messaging in WhatsApp, Wire, and Facebook Messenger among many others,
serving well over 1 billion active users.
It requires servers so it's not P2P.
It includes several uncommon security properties (such as "future secrecy" or "post-compromise security"), enabled by a technique called *ratcheting* in which session keys are updated with every message sent.
The protocol combines the Double Ratchet algorithm, prekeys, and a triple Elliptic-curve Diffie–Hellman (3-DH) handshake,
and uses Curve25519, AES-256, and HMAC-SHA256 as primitives.
Peer2peer
I2P
I2P is a scalable, self organizing, resilient packet switched anonymous network layer, upon which any number of different anonymity or security conscious applications can operate. Each of these applications may make their own anonymity, latency, and throughput tradeoffs without worrying about the proper implementation of a free route mixnet, allowing them to blend their activity with the larger anonymity set of users already running on top of I2P.
- I2P doc
- I2P ntcp
- I2P ntcp2
- NTCP2 is an authenticated key agreement protocol that improves the resistance of NTCP to various forms of automated identification and attacks
Noise
- NoiseProtocol - WhatsApp, I2P, ...
- Noise is a framework for crypto protocols based on Diffie-Hellman key agreement.
Nebula
Nebula is a scalable overlay networking tool with a focus on performance, simplicity and security. It lets you seamlessly connect computers anywhere in the world. Nebula is portable, and runs on Linux, OSX, Windows, iOS, and Android. It can be used to connect a small number of computers, but is also able to connect tens of thousands of computers.