Template:Wikify 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) c_i=pq_i+2r_i+m_i encryption formula
\tau_i m_i the message
v_{i,j} c_i ciphertexts (and public keys)
\{a_i,e,k,g\} \{0,1,1,2\} \{k,g\}=\{1,2\} means that m_i is a bit.
\epsilon_{i,j} r_i first randomizer
r_{i,j} q_i second randomizer
p p secret key

References Edit

  1. Template:Cite web
  2. Template:Cite web
  3. Template:Cite web

Ad blocker interference detected!

Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.