These protocols are meant for rapid development of new protocol aimed to solve business problems, where (generally) there is a confilct of interest. You can focus on the 'objective' and the 'applications' field to know whether this particular cryptographic protocol is suitable for your needs or not. New protocols will be added as I study new cryptographic protocols. I haven't put reference papers yet, but I extracted many of these protocols from (His Holliness Saint) Bruce Schneier's "Applied Cryptography", 2nd ed, 1996. I will be happy if you ask my assistance to solve a business problem by using cryptography.
| Name | Objective | Description | Applications |
|---|---|---|---|
| All or nothing disclosure | to let Bob deliberately choose a choosen secret from a set of 'labeled' secret | Alice has a list of several secret informations. Alice may 'label' each secret, but not their answers. Bob wants to buy the secret but doesn't want Alice to know which secret he is interested in. As soon as Bob has learned one secret, he can not learn any more Alice's secret. | To let other party choose a single message out of several ones, but not at random. |
| Anonymous Message Broadcast | to anonymously send a message to the group | Uses fair 2-coin flip thrown by neighboring members. If he wants to say '1'/'Yes', he must say the opposite what he sees. If he didn't pay, he must say exactly the state of the coins ('same' or 'different' side). Odd number of 'differencies' uttered at the table indicates one of them said '1'/'Yes'. | |
| Bit commitment | to commit on a message / an option, without revealing the message/option | Alice wants to commit to a prediction, but doesn't want to reveal her prediction until sometime later. Bob wants to make sure that she can not change her mind after she has commited a prediction. There are at least three variant: 1. Bit-commitment with symmetric key 2. Bit-commitment using one-way function 3. Bit-commitment using pseudo-random-sequence generator |
Alice can make a promise, without revealing the promise until the promise has been fulfilled. She can prove what he just did, is the promise she promised. |
| Blind Signatures | to sign a document without knowing exactly what the document is | Alice puts 100 message with unique serial number each into 100 envelopes. Alice gives the envelopes to Bob which will open the 99 envelopes and verifies them. The last envelope will not be opened, and Bob signs through the envelope. Bob returns the envelope to Alice and she will take out the message with Bob's signature. Chaum has several patent: Blind Unanticipated signature, one-show blind sig, returned-value blind sig, unpredictable blind sig. |
Serial number of an electronic cash. |
| Blob | this is not a protocol, but very important to note | the string that Alice sends to Bob to commit on a bit. Properties: - Alice can commit to blobs. - Alice can open any blob she has commited to, convince Bob, but cannot choose to open any blob as either 1 or 0. - Bob cannot learn how Alice opens any unopened blob. - Bob cannot learn any more information other than the bit Alice committed to. |
|
| Computing with encrypted data | to compute encrypted data (without knowing the data) | Also called hiding information from an oracle. Usefull when Alice wanted to compute an data M, but she doesn't have the calculator. She will encrypt M, and send it to Bob to let him compute the results. | |
| Desinated confirmer signatures | to let a third party be the confirmer of the undeniable/non-transferanle signature | Alice need Carol's (the third party) public key. This protocol can prevent false application, protects Alice if she loose her key, take charge when Alice is not available. On the other hand, it limits Alice control. The signature is more enforced with Carol, when Alice refuses to cooperate to verify her signature.. |
The protocol allows organization to separate the people who sign documents from who help confirms/verify signatures. |
| Entrusted undeniable signature | to let trusted party to run an undeniable signature disavowal protocol | Alice works for Bob. Alice gives the press Bob's secret. Alice can proof to press her signature, but not to anyone else. Bob suspects Alice. He demands Alice to run the disavowal protocol, but Alice refuses. Bob fires Alice. But actually only Trent can run the disavowal protocol to resolve the conflict. |
|
| Fail-stop digital signatures | to prove that Alice didn't sign the disputed signature | - Eve do a brute force attack to find Alice's private key. - Basic idea: a public key has many private key pairs. Alice only has 1 private key. Which means if Eve signs the same document, the signature will be different from Alice's. In court, Alice must convince judge by presenting a verifyable signature which is different from Eve's signature on the disputed document. |
repudiation of a signature in case the public key is brute-force attacked to find its (other) private key pair |
| Fair coin flips | to allow a fair random choice between two parties | Basically XOR's Alice bit with Bob's bit. Either Alice or Bob must use bit-commitment protocol so he cannot cheat later (after the coin has landed). There also exist a variant which uses public key. Using this scheme, the algorithm need to commute: Da(Eb(Ea(M))) = Eb(M) |
To make random choice without any arbitrator. |
| Flipping coins into a well | to force both parties to know the results of a coin flip at the same time | A fix from previous fair coin flip protocols, where either Alice or Bob would be the one who knows first the flipping result. The idea is Bob throws the coin into the well from a distance, so Alice can see the results, but Alice can't change the results. | To make random choice without any arbitrator. Session key generation with coin flipping, where no one can influence what the session key will be. |
| General secret sharing | to spit messages with restrictions on who can reconstruct the message | The restrictions may include all boolean logic (AND, OR, etc) and what-if's. Very powerfull. | |
| Group signature, with new member enrollment | to allow group signature with a new member | ||
| Group signatures | to allow a member signs a signature on behalf of his group, but in case of dispute his identity can be revealed | Characteristics: - only members of the group can sign messages - the reciever of the signature can verify that it is a valid signature from the group - the reciever of the signature can not detemine which member of the group is the signer - in case of dispute, the signature can be 'opened' to reveal the identity of the signer How: Trent created mxn public key pairs for n members. Trent publishes all the public key. When there's a need to open a signature, Trent will be consulted since he knows which keys belongs to whom. The problem is, Trent knows everybody's signature and can forge sigantures. |
A company has a shared facility, for use only with their employee. The boss can not tell which employee uses the facility, but whenever in dispute, the signature can be opened to reveal the identity of the signer. |
| Group signatures, Trent is forced to be honest | to disallow Trante to forge member's signature | Trent will not be able to fake signatures | |
| Group signatures, without Trent | to create a group signature without an arbitrator | ||
| Identity-based public key cryptography | to create a public key from a particular identity (address, name, etc.) | Also known as 'non-interactive key sharing'. Trent generates the private key. This protocol has serious flaws according to St.Bruce Schneier. | |
| Key Escrow (fair cryptosystem) | to verify the validity of a splitted public & private key pieces | Alice can create her own private key and give a piece to n trusties. None of these trusties can recover her private key. However each trustee can verify that his piece is a valid one. Alice can not send random bit string. Having a piece of public/private key pair, the trusties check them, then sends the public key piece to a KDC which will check the public pieces with Alice's public key. This protocol can be extended to let only a subset of trusties to reconstruct the keys, or with oblivious transfer so the trustees don't know whose private key is being reconstructed. |
For use by law enforcement agencies to wiretap a suspect of crime. |
| Mental poker | to randomly choose from a set of messages | Uses commutative algorithm like fair coin flip using public-key. In the original protocol using RSA, there is a leak. But a fix for n-mental protocol exist. | When people can not (are not allowed to) generate their [session] key, they may given a very wide range of keys which will work, but Trent (KDC) can not determine which key was given to Alice. |
| Multiple-key Public-key Cryptography | to encrypt-decrypt to sub-groups in a group | - If only 2: Alice 'public key' (Kb) is given to Bob. Alice keeps her secret Ka. Bob can decrypt Alice's message. - Multi-person Alice Ka, Bob Kb, Carol Kc, Dave Ka & Kb, Ellen Kb & Kc, Frank Kc and Ka. Bob can send messages to Frank. Ellen can encrypt a message to Alice, Dave or Frank. -Given a subset of keys is used to encrypt the message, then the other keys are required to decrypt the message. So we can send a message to any subset of the group. |
subliminal group communication |
| Non-interactive zero knowledge | to let verification of a secret non-interactively | Uses hash function of the solution to force Peggy commit. Must use higher rounds to ensure safety. | Publishing a data that cointains no information about a secret, but can be used to convince anyone of the secret's existance. |
| Oblivious signatures | 1. Alice has n different messages. Bob can randomly choose one of the n messages for Alice to sign, and Alice has no way of knowing which one she has signed. 2. Alice has one message. Bob can randomly choose one of n keys for Alice to use in the signing message, and Alice will not know which key was used. |
||
| Oblivious transfer | to let Bob pick randomly one message out of n messages | This protocol guarantees that Alice sends Bob one of the two messages, it does nothing to ensure what Bob wants to receive either of them. It doesn't stop Alice to send completely useless messages. | Alice has n secrets Bob gets one. Alice doesn't know Bob's random choice. |
| One-way accumulator | to allow commutative hashing | Some sort of one-way hash function, except that it is commutative. It is possible to hash the database member in any order, but still produce the same result. Alice creates an accumulator, minus her and Bob's. Masih nggak jelas…! |
digital signatures without centralized signer. |
| Proxy signatures | to allow Bob to sign on behalf of Alice, without giving her private key | The properties are: a) Distinguishablility: normal and proxy signatures are different b) Unforgeability: only the signer and the designated proxy can create a valid proxy signature c) Proxy signer's deviation: a proxy cannot create a proxy signature without detected as a proxy signature d) Identifiability: an original signer can determine the proxy signer's identity from a proxy signature e) Undeniability: a proxy signer cannot disavow an accepted proxy signature he created f) Verifyability: from a proxy signature, a verifier can be convinced of original signer's agreement on the signed message Optional desired property: anyone can determine the proxy signer's identity (identifiability by anyone). |
to designate someone to sign on behalf of the original signer |
| Secret sharing schemes with prevention | Basicaly, each person is given a "yes" and a "no" share. When reconstructing, each person decides whether he wanted the secret to be reconstructed or not. If Y >=m and N < n, then the secret can be reconstructed. | Can be used as a building block for voting protocols. | |
| Secret sharing with cheaters | to handle cheaters in secret sharing | a. when Carol gives a random key to Alice and Bob instead of her key. b. when Mallory fools Alice and Bob to reconstruct the secret, then Mallory takes their shadows c. gue nggak ngerti yang c ini |
|
| Secret sharing with disenrollment | to allow secret sharing continue whenever one of the member become untrustworthy | There's no need to set up a new scheme. | |
| Secret sharing without arbitrator | to enable absolutely no one to know the secret key until reconstruction | Can be used like (m,n) threshold scheme | |
| Secret sharing without revealing shares | if the shared secret is a privat key (to a signature), then n shareholders can each do a partial signature of the document. After the n-th partial signature, the documents has been signed with the shared private key and none of the shareholders learns any others. | Needed when the secret can be reused. | |
| Secret sharing, (m,n) threshold scheme | to split message to n pieces, so m of them can reconstruct the message | Two approaches: a. Geometry based algorithm b. Polynomial based algorithm (use this one because it only uses integers). To extend it to three colonel and one general problem, simply give the general 2 colonel keys. |
In the need of permission or agreement of several people. |
| Secret splitting | to split sharing between multiple parties | - Involves Trent which XORs the message with his random key. | |
| Secure Multiparty Computation | to allow members submit their variables into a particular function | Computing average salary with privacy, voting with 'super vote', variable differencies, etc. | |
| Simultaneous contract signing | to sign a contract simultaneously | This protocol is a step by step protocol, but doesn't require Trent. The confidence is measured in percentage. There exist other protocol with Trent which is not a step by step protocol. | |
| Simultaneous exchange of secrets | allows Alice and Bob to exchange secrets simultaneously | This protocol does not ensure the quality of the secrets exchanged. Based on digital certified mail. | |
| Subliminal channel | to send innocous signed message with hidden message | The subliminal messages are hidden in what looks like normal signatures. Even Walter has know idea that one is present. It uses a secret key for both Alice and Bob. Walter needs the secret key to read the message. DSA can be used for subliminal channel. | In spying network, signing under pressure, marking a digital cash/check. |
| Subliminal-free signatures | to disallow subliminal message within signatures | Counterspying | |
| Undeniable digital signatures | to force signature verification with signer's consent. | Also called 'non-transferable signature'. Alice shows Bob her signature. Bob sends random number to Alice. Alice calculates the random number with her private keys, and sends Bob the results. Alice could only do this if the signature is valid. Bob confirms. This protocol is weak against man-in-the-middle attack. | Personal correspondence cannot be verified by press. |
| Verifiable secret sharing | to allow each individual to verify their shadows without reconstructing | This protocol needs Trent. | |
| Zero knowledge (perfect) | to verify a secret without revealing the secret | 1. Peggy knows that graph G1 and G2 are isomorphic. Peggy creates H isomorphic. Victor will ask Peggy to prove either G1-H or G2-H is isomorphic. Repeat n times. 2. Hamiltonian cycle: From graph G create isomorphic graph H. Encrypt the edges into H'. Victor will ask Peggy either to (a) prove that H' is an encryption of an isomorphic copy of G -> decrypting everything, without showing Hamiltonian cycle of G or H. (b) shows the Hamiltonian cycle of H by only decrypting only those lines that constiute a Hamiltonian cycle, without proving G & H isomorphic. Repeat n times. Perfect means there is a simulator that gives transcripts identically distributed to real transcripts. |
May be used to prove that Peggy knows a secret, and can prove a secret. Suppose Peggy is a member of an organization O, there exist isomorphic graph Gp and Go. Peggy's secret is the isomorphic proof. |
| Zero knowledge proofs of identity | to prove identity with the knowledge of a secret key | Can be abused in man-in-the-middle attack. A solution uses accurate clocks to disallow conspirators to communicate. Each step must be done in a given time. |