Cryptographic Test Correction

Cryptographic Test Correction is a technique, published in 2008 by Eric Levieil and David Naccache ^[1] for shifting the burden of correcting Multiple Choice Questionnaires (MQC) to examinees. Because the corrector is only interested in the number of correct answers and not in knowing the examinee's answers to each and every question an ad-hoc cryptosystem was purposely engineered to be additively homomorphic. Levieil-Naccache scheme is multiplicatively homomorphic but only for evaluating functions with a constant depth of operations (a fact not mentioned in Levieil and Naccache's paper).

Levieil and Naccache's encryption method is very closely related to an encryption scheme proposed by Bram Cohen^[2] in 1998.

This cryptosystem is also related to an encryption scheme published in 2009 by Marten van Dijk, Craig Gentry, Shai Halevi and Vinod Vaikuntanathan^[3], who used a somewhat similar encryption process (c_i = pq_i + 2r_i + m_i, using van Dijk et al.'s notations) and extended it using techniques of Gentry to get a fully homomorphic encryption scheme.

The following variable renamings and assignments transform Levieil and Naccache's notations into van Dijk et al.'s notations.

Levieil-Naccache	van Dijk et al.	description.
$v_{i,j}=pr_{i,j}+((a_i+k \tau_i+g\epsilon_{i,j})e \mod p)$	ci = pqi + 2ri + mi	encryption formula
τi	mi	the message
vi,j	ci	ciphertexts (and public keys)
{ai,e,k,g}	{0,1,1,2}	{k,g} = {1,2} means that mi is a bit.
$\epsilon_{i,j}$	ri	first randomizer
ri,j	qi	second randomizer
p	p	secret key

References

1. ^ Cryptographic Test Correction. http://books.google.fr/books?id=xF0krf15L1IC&lpg=PA85&ots=Ju4o3ny_uu&dq=cryptographic%20test%20correction&pg=PA85#v=onepage&q=cryptographic%20test%20correction&f=false. 
2. ^ Bram Cohen. "Simple Public Key Encryption". http://en.wikipedia.org/wiki/Cohen%27s_cryptosystem. 
3. ^ Marten van Dijk; Craig Gentry, Shai Halevi, and Vinod Vaikuntanathan (2009-12-11). "Fully Homomorphic Encryption over the Integers". International Association for Cryptologic Research. http://eprint.iacr.org/2009/616. Retrieved 2010-03-18.