Documentation

Overview

The Oblivious Printing scheme delivers a novel approach to secret printing. By combining computational and physical cryptography, the scheme keeps the intended message oblivious to all but its source and destination.

Computationally:

• Mix Network is used to ensure the privacy of the retrieved data
• Shadow Mix is used to ensure the integrity of the servers performing the mixing
• Plaintext Equality Test is used to retrieve the intended data

Physically:

• Multi-party Visual Cryptography is used to ensure the privacy of the printed data

The implementation proceeds according to the following 5 steps:

1. Translation table
2. Mix Network
3. Shadow Mix
4. Plaintext Equality Test
5. Visual Cryptography

1. Translation Table

Walkthrough:

• Read sample alphabet from /test directory
• ElGamal encrypt each message with default random factor
• Insert ciphertexts row-wise into Translation Table

TranslationTable.java: table of (key, value) pairs where "key" is a unique representation of a letter in the alphabet, "value" stores the bit-wise representation of the letter - the tuple is represented by the Message class

PlaintextMessage.java: plaintext (key, value) pair

CipherMessage.java: ElGamal encrypted (key, value) pair where every element in "value" is encrypted individually

[A sample alphabet is provided in /test]

2. Mixing

Walkthrough:

• Instantiate Server objects
• (Each Server) Commit to a FactorTable (table of random factors) and a Permutation
• (Each Server) Randomize and permute TranslationTable according to the commitments
• (Each Server) Publish mixed TranslationTable

Mixnet.java - execute(): general driver coordinating the mix network

Server.java: each instance represents a single party - randomizes and permutes the translation table

Permutation.java: representation of individual permutations

FactorTable.java: stores all random factors used in a single randomization process, for e.g. if value.length == n then (n+1) random factors would be stored: n for reencrypting "value", 1 for reencryting "key"

3. Shadow Mix

Walkthrough:

For each Server

• Create a Challenge instance for the proof of knowledge of FactorTable and Permutation commitments - create two sets of commitments which together form an isomorphism to the original set of FactorTable and Permutation commitment
• Receive a secure random Heads or Tails judgement
• Publish a ChallengeProof - a decommitment to either set of commitments depending on the coin toss
• Reiterate with new Challenges until desired level of confidence is acquired

Mixnet.java - validate(): coordinates the validation process

Challenge.java: represents a single Shadow Mix challenge

ChallengeProof.java: represents the Heads or Tails decommitment of the challenge

4. Plaintext Equality Test

Walkthrough:

• Randomly select a key from the plaintext alphabet
• ElGamal encrypt selected key
• Extract corresponding encrypted value from the mixed TranslationTable via Plaintext Equality Test

TranslationTable.java - extract(): performs the multiparty PET to extract the desired ciphertext

5. Visual Crytography

Walkthrough:

ObliviousPrint:

• Receive encrypted value
• Create alpha instances of PrinterDrivers
• Reveal alpha-1 instances
• Verifies the integrity and validity of the revealed instances
• Finalize remaining instance

PrinterDriver:

• Create instances of Printer
• (Each Printer) Commits to random share
• (Each Printer) Homomorphic xor random share with encrypted value
• (Each Printer) Prints random share

If PrinterDriver is revealed:

• Decrypt encrypted value resulting from all homomorphic xor's
• (Each Printer) Decommits to random share
• Check for validity

BasisMatrix.java: a n x 2^(n-1) binary matrix where each column has even Hamming weight

ObliviousPrint.java: generic coordinator of the visual crypto process, coordinates cut-and-choose process, printer challenges, and finalization

PrinterDriver.java: specific coordinator of multiparty share creation and printing

Printer.java: represents single printing party, creates and prints a single share