Protocols

Contents

Authentication

Basics

Password based

Other authentication protocols

NextAuth Powerauth OPAQUE

Secret sharing and thresholds

Basics

Commitment

Applications include secure coin flipping, zero-knowledge proofs, and secure computation.

Basics

Pedersen commitments

Secure verifiable secret sharing. Takes SSS further. The verifiable secret sharing schemes allow each receiver of information about the secret (share of the secret) to verify that the share is consistent with the other shares.

Shows how to distribute a secret to n persons such that each person can verify that he has received correct information about the secret without talking with other persons. Any k of these persons can later find the secret (1 ≤ k ≤ n), whereas fewer than k persons get no (Shannon) information about the secret. The information rate of the scheme is 1/2 and the distribution as well as the verification requires approximately 2k modular multiplications per bit of the secret. It is also shown how a number of persons can choose a secret “in the well” and distribute it verifiably among themselves.

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

Privacy related

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

The creation of a ZK solution typically involves the following steps:

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:

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.

Overviews

Voting

See e.g. Helios voting by Ben Adida (used by e.g. KU-Leuven). Here the proof is a Chaum-Pedersen proof of a DDH tuple.

SNARKS (Succinct Non-Interactive Arguments of Knowledge)

As per 'The Hunting of the SNARK', a SNARG is a triple of algorithms (P, GV, V). For security parameter k, V runs GV to generate (vgrs, priv) where vgrs is a public verifier-generated reference string, and priv are corresponding private verification coins. The honest prover P(y, w, vgrs) produces a proof PI for statement y=(M, x, t). Here M is a Turing machine, x is in the language L. (ref Bitansky).

A SNARG can be adaptive (prover may choose the statement to prove after seeing vgrs) or non-adaptive (otherwise).

A SNARK is an adaptive 'SNARG of Knowledge' where soundness is strengthened through the existence of an extractor. Bitansky et al.'s SNARK may be based on an Extractable Collision-Resistant Hash (ECRH), i.e. a hashfunction for which an extractor function can create a pre-image of a hash.

zk SNARKS (Zero Knowledge Succinct Non-Interactive Arguments of 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: Rank-1 Constraint Systems - R1CS

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+

Refer also to local BBS signature information.

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.

BBS+ signatures require a pairing-friendly curve, such as BLS12-381.

ISO/IEC 18013-5:2021

Included in the eIDAS's successor as requirement, 'EUDI Wallet Solution [...] support MUST Selective Disclosure of attributes as specified in ISO/IEC 18013-5:2021.' ISO Mobile Security Object (MSO), part of the ISO 18013-5 mDL standard, contains hash values of ISO mDL attributes combined with random values (salts).

SD-JWT

Included in the eIDAS's successor as requirement, 'EUDI Wallet Solution [...] support MUST Selective Disclosure of attributes as specified in SD-JWT.'

Contains hash values of JSON attributes combined with random salts.

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: 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. 'ssh -Q cipher-auth' queries symmetric ciphers that support authenticated encryption), e.g. 'ssh -Q mac' queries macs, e.g. 'ssh -Q key', 'ssh -Q key-cert' and 'ssh -Q key-plain' query key types.

'ssh -Q kex' queries key exchange algorithms, e.g.

'ssh -Q sig' queries signature algorithms, e.g.

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.

Noise

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.