The Security of Aguilar-Melchor and Gaborit’s Lattice-Based Private Information Retrieval Protocol Richard Roberts, Dennis Sell, Terry Sun {ricro,selld,terrysun}@seas.upenn.edu March 30, 2015 Abstract Thelattice-basedPrivateInformationRetrieval(PIR)protocolbyAguilar-Melchor and Gaborit [4] provides an alternative to the number-theoretic schemes protocols for single-server computational PIR that came before it. With slightly greater communi- cation costs, their scheme improves the computational performance by two orders of magnitude. However, this scheme has not been reduced to an NP-Hard problem, nor have lattice attack techniques been successful in attacking this protocol. Thus, little is known about the security of this protocol. In this paper, we first provide a summary of the scheme, its background, and its security analysis presented by the original au- thors. We then build upon their work in an attempt to determine security properties of the scheme. 1 Introduction Private Information Retrieval (PIR) schemes are methods of accessing information from a database while at the same time hiding from the server which element is being accessed. There exist both single-server and multi-server PIR schemes, which fall generally into two camps: computational PIR, based on the assumption that a polynomially-bounded adversarial database cannot decipher the query that it’s presented with, and information- theoretic PIR, which posits that it is impossible to calculate (given infinite resources) the targeted information. More formally, we define single-server PIR as follows: Definition 1.1. Single-Server PIR Problem: There is a server which possesses a database M composed of n elements. A requester wishes to access element m from the database. i0 The requester sends a query V to the server and the server computes a response r which is returned. The server must not be able to determine the index k given V and the requester must be able to determine the value of m from r. k The scheme proposed by Aguilar-Melchor and Gaborit, which we will refer to as the Aguilar-Melchor Gaborit Scheme, is a single-server scheme and is an example of compu- tational PIR. A very simple (the "trivial scheme") single-server PIR protocol is to simply have the serverreturntheentiretyofthedatabaseateveryrequest. Thisisinformationtheoretically 1 secure, but it requires a large amount of communication to be sent upon every request. In an attempt to reduce communication requirements, computation-based proposals have beensuggested. Lipmaa[3]andGentryandRamzan[1]providetwosuchschemesagainst which Aguilar-Melchor and Gaborit compare their protocol. These schemes— along with most if not all others—are based on number-theoretic cryptographic primitives, and are amongthemostpracticalofthese. Comparedtothetrivialsolution,theseschemesgreatly reduce the the amount of communication needed but at great computational cost. The Aguilar-Melchor Gaborit Scheme is a a proposed alternative scheme which pro- vides middle ground between the computation-heavy number theoretic schemes and the communication-heavyinformation-theoreticsolutions. Thisscheme,theauthorshope,will provideamorepracticalPIRprotocol,aimingformoderatecomputation,communication, and time costs. However, little is known about the security of this scheme. In the original paper, the authors discussed the connection between the security of this scheme and an NP-Hard problem, but could not show a reduction. The paper also discussed reasons why latticeattackswereunlikelytowork,yetthesecurityoftheschemeisnotwellunderstood, prompting further research into the matter. Our goals for this paper were to attempt to make progress on any of the following regarding the security of the Aguilar-Melchor Gaborit Scheme: 1. Prove the NP-Hardness of the computational problem behind their scheme. 2. Apply lattice attacks and techniques from related work to break or weaken the scheme. 3. Consider the proposed parameters of the scheme, and attempt to see if any opti- mizations can be performed or show that the proposed parameters are insufficient for security. Note that, as with the knapsack-based cryptosystems, we can both reduce the scheme inquestiontoahardproblem,whichprovesthatintheworstcasetheunderlyingproblem isdifficult,andyetalsodevisealattice-basedattack,whichdemonstratesthattheproblem is not as difficult in the average case. Wewillorganizeourpaperasfollows. InSection3,wewilldiscusstheschemeproposed by Aguilar-Melchor and Gaborit, with an emphasis on query formation. Then we will discuss in Section 4 the lattice-based problems upon which the protocol is based, the Hidden Lattice Problem and the similar Differential Hidden Lattice Problem, and their relation to known hard problems. In Section 2, we introduce related work which will be of relevance for analyzing the security of this scheme. Finally, we discuss our attempts to determine security properties of the scheme in Section 5. 2 Related Work We looked to relevant research for help in analyzing the security of the Aguilar-Melchor Gaborit Scheme. The first source we examined was Nguyen and Stern’s overview of the use of lattices in cryptology [6] which summarizes the algorithmic and theoretic work surroundinglattices,theuseoflatticestobreakcryptographicschemes,andtheattempted use of lattices to construct cryptographic schemes. This paper provided useful breadth andunderstandingoflatticetopicsmentionedbrieflyinclass, andgaveusagoodstarting 2 point for this project. However, as we delved deeper into the PIR scheme at hand, we realized that it was less possibly relevant than we originally believed. Additionally, we examined the attack on the Goldreich-Goldwasser-Halevi public key system[5]astheattackalsoinvolvesanalyzingnoiseandusinglatticeattacks. Theattack was performed by first noting that the nature of the noise ensured that information was leaked about the message vector m. This was mainly due to the fact that the noise was of the form {±σ}n for some selected σ. This allows one to find the value of m mod 2σ. From here, one can utilize this information to convert the problem of finding the message to a relatively easy instance of the Closest Vector Problem (CVP). 3 Aguilar-Melchor Gaborit Scheme This scheme is composed of three separate protocols: • Query Formation: a requester computes the query to be sent to the database, ob- fuscating the target in the process • Server Response: the computation done by the database, which must correctly en- code the elements of the database such that the server cannot determine what the target of the query was but the requester will be able to reverse the obfuscation) • Information Extraction: the requester’s final stage, wherein the server response is decoded into the desired database element by using information known only to the requester 3.1 A High-Level Discussion The security of the scheme is dependent on the server being unable to distinguish the target element given generated query, so the focus of our cryptanalysis will lie with the results of the first protocol (Query Formation), as the query comprises the information thattheserverhasaccessto. Themainimportanceoftheothertwoprotocolsisinproving the correctness of the scheme itself, which is shown in the original paper (and discussed here)–after all, if the requester cannot decipher the server’s response, the scheme is as good as useless. Theheartofthisprotocolliesintheadditionofcontrollednoiseintheformofrandomly generated"softnoise"matrices(withelementsin{±1})andasingle"hardnoise"matrix(a softnoisematrix,withelementsalongthediagonalmultipliedbyq). Theschemeproposes thatahardnoisematrix(indicatingthetargetofthequery)isindistinguishablefromaset of soft noise matrices after a series of obfuscastion techniques corresponding to randomly generated elements. The server, which does not have this private information, is unable to discover the target of the query. However, the requester is able to use the knowledge of its randomly chosen matrices—as well as the property that q (cid:29)1—to decipher the server response and recover the desired information. To generate a query, the requester produces an ordered set of n matrices (one for each element in the database), of dimension N×2N. These matrices share a common basis M ofsomelattice,andeachhaveacontrolledamountofnoiseaddedtotheright-handhalfof the matrix (ie. a noise matrix D ∆ is added to a matrix M(cid:48) by computing M(cid:48)+[0|D ∆]). i i i i n−1 of these matrices have a small amount of noise added ("soft noise matrix", or SDM) 3 andthefinalmatrix,whichisthetargetofthequeryandcorrespondstothei thelement, 0 has a larger amount of noise added ("hard noise matrix", or HDM). Then, a common, random permutation is applied to each matrix to form the final set of matrices sent in the query. 3.2 The Protocols The scheme contains some global integer parameters. The database is formed of n l-bit elements, and we denote with i the element in the database which we wish to query for. 0 EachelementinthedatabasewillfurtherbesplitintoN sub-elementsduringtheserver response. (Note that the dimension of the lattice is 2N.) Each sub-element is an integer can be represented in l bits, where l =(cid:100)log(n×N)(cid:101)+1. 0 0 Below, we present the three protocols defined in the Aguilar-Melchor Gaborit Scheme. 3.2.1 Query Formation 1. Fix query parameters q =2l0, and p some prime such that p>23l0. 2. Generate two N ×N matrices in Z/pZ, A and B, such that A is invertible. Create the N ×2N matrix M =[A|B] 3. Generate the N ×N scrambling matrix ∆ ∈ Z/pZ as a random diagonal matrix. This will be applied to both the hard and soft noise matrices to obfuscate them and disguise which type of noise belongs to each matrix. 4. For each i∈{1,...,n}, generate a random N ×N matrix P ∈Z/pZ and compute i the matrix M(cid:48)(cid:48) =P M =[A |B ] i i i i 5. For each M(cid:48)(cid:48) = [A |B ], compute M(cid:48) by adding to B some scrambled noise matrix i i i i i D ∆. D is hard noise for the target of the query and soft noise otherwise. i i • For each i ∈ {1,...,n}\i (that is, for every element other than the query 0 target), generate an N ×N soft noise matrix D over {−1,1}. Compute the i softly disturbed matrix (SDM) by adding D ∆ to the right half of the matrix i M(cid:48)(cid:48). Thus, let M(cid:48) =M(cid:48)(cid:48)+[0|D ∆]=[A |B +D ∆]. i i i i i i i • For i , the target of the query, generate the hard disturbed matrix D by gen- 0 i0 erating a soft noise matrix and replacing each element along the diagonal with q. Then compute the hard disturbed matrix (HDM) M(cid:48) = M(cid:48)(cid:48) +[0|D ∆] = i0 i0 i0 [A |B +D ∆] i i i 6. ChoosearandomcolumnpermutationP(·)andapplyittoeachmatrix,ie.,foreach i∈{1,...,n}, compute M =P(M(cid:48)). i i 7. Send the ordered set {M ,...,M } as the query to the database. 1 n We believe that the security of this scheme lies in its random generation. Because of the scrambling matrix ∆, there is no easily discernable linear relationship between soft and hard noise matrices that are used to create noise in the query. The random permutation, along with multiplication of the original basis M with randomly generated invertible P , renders the server unable to distinguish which columns of the matrix were i disturbed with noise (this is similar to the Hidden Lattice Problem, which is further discussed in Section 4.1. 4 3.2.2 Server Response The server receives the set {M ,...,M } and constructs the response vector V of length 1 n 2N. 1. Split each database element m into a vector of N l -bit integers, {m ,...,m }. i 0 i1 iN N (cid:88) 2. For each vector m , construct the response v = m M . Each jth element in i i ij ij j=1 the vector m is multiplied by the jth row of the matrix M in the query vector. i i N (cid:88) 3. Construct V by summing each element vector, V = v . j j=1 3.2.3 Information Extraction Upon recieving the server response V, the requester is then able to extract the hard noise and determine the element of interest m . This can be done using the values of P, ∆, A, k B, and q decided on in the query formation. 1. Compute the non-permuted noisy vector V(cid:48) =P−1(V). 2. RetrieveS =V −V A−1B, thescramblednoise, V andV beingtheundisturbed D U U D and disturbed halves of V. 3. Compute the unscrambled noise: E =S∆−1. 4. For each e in E =[e ,···e ], round e to the nearest multiple of q giving us values j 1 N j E(cid:48) =[e(cid:48),···e(cid:48) ]. 1 N 5. For each j ∈{1,··· ,N}, compute m =e(cid:48)q−1. i0j j 3.3 Correctness This PIR scheme is built upon the fact that the hard noise is extractable from the server response. As the authors note, each element e will have the value j N (cid:88) (cid:88) e =m q+ m (D ) j kj i0k i jk i∈{1···n}\i0k=1 It is important to note that each element l0-bit integer mij is clearly bounded by 2l0, and each element in any soft noise matrix is ±1. Additionally, the choice of a value for l0 implies that 2l0−1 > n·N. Hence the absolute value of the summation on the right is upper bounded by N (cid:88) (cid:88) 2l0(D ) ≤n·N ·2l0 <2l0−1·2l0 =22l0−1 =q/2 i jk i∈{1···n}\i0 l=1 Hence, the soft noise is less than half of q, so rounding to the nearest value of q will resultinthem q. Thisvalueislessthanp,whichallowsthefinalstepofthelastprotocol i0j to extract m , e(cid:48)q−1 =m qq−1 =m , proving the correctness of this scheme. i0j j i0j i0j 5 Figure 1: Performance Analysis 3.4 Performance Fig. 1 is taken directly from Aguilar-Melchor and Gaborit’s original paper [4]. The com- parison is based on the query and download for a 3Mb file from a database with 1000 elements. OneofthemajoradvantagesofthisPIRschemeoverpreviouslyexistingschemesisits performance. Aguilar-Melchor and Gaborit compare their PIR scheme to two previously existing single-server PIR schemes (Limpaa’s and Gentry and Ramzan’s) with regard to generatedquerysize,querygenerationtime,andserverdownloadtime. WhiletheAguilar- Melchor Gaborit Scheme must transmit a relatively much greater amount of data during its protocols in order to complete a query (resulting in a larger and slower query), the computational performance of the server response protocol mean that this scheme might actuallybepractical, spendingatotalofjust15minutesonthetransferratherthanmore than a 17 hours. It is also clear that computation is the bottleneck in all of the above schemes. The bandwidth usage never reaches above 1.2% in even the Aguilar-Melchor Gaborit Scheme, showing that the communication overhead is low compared to modern available speeds. Additionally, the use of recursion (that is, dividing a single database server into smaller, virtualservers;insteadofsendingasinglequerywiththeindexofthetargetedelement,the requester sends multiple queries, which indicate the indices of the desired virtual server, thenfinallythelocalelementinthesmallerserver)intheAguilar-MelchorGaboritScheme reduces the size of its query significantly, while not changing the download time. Aguilar-Melchor and Gaborit do not include server response computation time or re- sponse size, and do not specify what is included in the server’s "Download time". 4 Equivalent Security Problems The original paper on the Aguilar-Melchor Gaborit Scheme introduces two lattice-based problems: theHiddenLatticeProblem(HLP)andtheDifferentialHiddenLatticeProblem (DHLP). These problems are defined to investigate the structural security of the Aguilar- MelchorGaboritScheme;bycomparingtheproblemstoeachother,totheAguilar-Melchor GaboritScheme,andtoaknownNP-Completeproblem,theauthorsprovidesomemeasure of assurance that an intelligent, computationally-bounded adversary will be unable to obtain undesired information about a client’s queries to the database. Below we restate the two problems from the original paper (with minor alterations for improved clarity) and demonstrate how they relate to the Aguilar-Melchor Gaborit Scheme. 6 4.1 Hidden Lattice Problem Construction: 1. Define a vector space V of dimension k and of length n (such that n > k) over a finite field GF(p). 2. Construct r random basis for V, denoted as {V ,··· ,V }. Denote the jth column of 1 r V as V . i i,j 3. SelectsomesubsetofcolumnsS(cid:48)suchthatS(cid:48)containsklinearlyindependentvectors for every basis V . 1 Choose a nonempty subset of size w values from the set of i columns not in S(cid:48), {1,··· ,r}−S(cid:48). Denote this set as S ={s ,··· ,s }. 1 w 4. ∀i∈{1,··· ,r},∀s∈S: Letq bearandomelementinGF(p). Constructacolumn i,s C from elements in {q ,−q }. Define C as the set of columns for i. i,s i,s i,s i 5. Randomlyselectsomei ∈{i,··· ,r}andsomeq ∈GF(p)where1(cid:28)q (cid:28)p. 0 hard hard 6. For every g ∈{1,··· ,w}, multiply the gth coordinate of C by q . i0,g hard 7. Let U be the set of basis equal to V. Add the values of each C to U . i,s i,s Problem: Given U, determine S; that is, given the set of disturbed basis, determine which set of columns have been disturbed by the addition of noise. Relationship between HLP and AMG scheme: The Aguilar-Melchor Gaborit Scheme is an instance of the Hidden Lattice Problem with the following parameters. The dimension of V equals the number of disturbed columns, which equals the number of bitstrings that each element in the database is separated into (k = w = N). The size of V is equal to two times the number of sub-elements that each element in the database is divided into upon Server Response (n=2N). q =q, the global hard noise parameter. hard C representsthehardnoisematrixaftermultiplyingitbythescramblingmatrix(D ∆). i0 i0 Every other C represents the columns of a soft noise matrix after multiplying by the i scrambling matrix (D ∆). The random selection of columns in S for the HLP is similar i to the permutation of columns in the original scheme. Thus an algorithm that is capable of solving the Hidden Lattice Problem is also capable of determining which columns were disturbed among the query matrices. Theorem 1. If an adversary knows the columns with noise, then they can determine which matrix among the query set is the HDM. Recall that M = [A|B] and for all 0 < i < n, M = P M = [P A|P B]+[0|D ∆]. We i i i i i omitthepermutation,whichisnegatedbytheadversary’sknowledgeofthehiddenlattice. Suppose the adversary knows which columns have noise added (without loss of generality, say these are the first N columns). The following two algorithms shows how to recover the values of all D ∆ given an i adversarythathassolvedtheHLP.ItcomesfromageneralizationofLemma1andanalysis that follows, taken from the Aguilar-Melchor and Gaborit’s paper of interest. 1Weassumesuchaselectionofcolumnsexistswithoutlossofgenerality. Ifsuchagroupingofcolumns didnotexistwecouldrearrangethecolumnsofeachbasisVi duringgenerationuntilasufficientselection ofcolumnsexisted. 7 Algorithm 1. Solving for One Column (In the Noise Matrices) for i←1 to n do for j ←(i+1) to n do First, using Lemma 1 introduced in Aguilar-Melchor and Gaborit’s paper, the adversarycancomputeP P−1. SinceweknowthatthefirstN columnsareunmodified, j i we can determine through inspection the values of P A and P A. Then simply evaluate i j P A(P A)−1 =P AP A−1A−1 =P P−1. j i j i j i The adversary then computes S = P P−1M −M = P P−1(P M +D ∆)− ij j i i j j i i i (P M +D ∆)=[0|P P−1D ∆]−[0|D ∆]. j j j i i j Create a set of N linear equations by using the elements of the (unknown) cth columns of D ∆ and D ∆ and the (known) cth column of S . i j ij end for end for At the end, there should exist nN equations and nN unknowns. This can be solved in O((nN)3) time, obtaining the values of the cth columns of all D ∆. i Algorithm 2. Solving for All Disturbed Matrices for c←1 to 2N do Use Alg. 1 to solve for the values of the cth column of D ∆. i end for Atthisstage,theadversaryhasthecompletevaluesofD ∆foralli∈{1,...,n}. Since i all added soft noise is of the form {−1,+1}, all SDMs are easily relatable to ∆. There shouldbeonlyasinglematrixinthesetforthequerythatdiffersfromthispattern,which will be distinguishable from the HDM. It is not necessary for the hard noise values (originally manifested as q along the diagonal of the HDM) to lie in a particular pattern in the matrix, as the HDM will be the only matrix which contains elements not in ∆. Thus, it is unnecessary for an attacker to exactly reverse the permutation; it is enough to find the disturbed columns in order to distinguish the index of the HDM. This algorithm (which the authors admit is naive in construction) will run in time O((n3N4). The inner loop (pairwise equation generation for each of n matrices) is domi- nated by the O((nN)3) matrix inversion used to solve the system of equations, and must be repeated for each of 2N columsn in the lattice. Anadversarythatisabletodistinguishtheunmodifiedcolumnsofthebasisthatmake upaquerywouldprovetheAguilar-MelchorGaboritSchemeinsecure,butshowingthatan adversaryisunabletodosoisinsufficientforprovingthesecurityofthescheme. Tobreak theAguilar-MelchorGaboritScheme,anadversaryneedonlydistinguishwhichofthebasis corresponds to i (that is, the one basis that corresponds to the element in the database 0 that the client is requesting in a given query). This is equivalent to distinguishing which basis has been disturbed with a hard noise matrix from those disturbed with soft noise matrices. Aguilar-MelchorandGaboritintroduceamorespecificproblem,theDifferential Hidden Lattice Problem, to represent this concept. 8 4.2 Differential Hidden Lattice Problem Construction: 1. Define a a vector space V of dimension k and of length n (such that n > k) over a finite field GF(p).. 2. Construct r random basis for V, denoted as {V ,··· ,V }. Denote the jth column of 1 r V as V . i i,j 3. Define T and T to be two subsets of {1,··· ,r} such that T (cid:54)=T 1 2 1 2 4. SelectsomesubsetofcolumnsS(cid:48)suchthatS(cid:48)containsklinearlyindependentvectors foreverybasisV . Chooseanonemptysubsetofsizewvaluesfromthesetofcolumns i not in S(cid:48), {1,··· ,r}−S(cid:48). Denote this set as S ={s ,··· ,s }. 1 w 5. ∀i∈{1,··· ,r},∀s∈S: Letq bearandomelementinGF(p). Constructacolumn i,s C from elements in {q ,−q }. Define C as the set of columns for i. i,s i,s i,s i 6. Randomly select some d∈{1,2} and some q ∈GF(p) where 1<<q <<p. hard hard Let T =T . d 7. For every g ∈ {1,··· ,w}and every f ∈ T, multiply the gth coordinate of C by f,g q . hard 8. Let U be the set of basis equal to V. Add the values of each C to U . i,s i,s Problem: Given T , T , and U, determine the value of d. That is, given two possible 1 2 sets of basis and the set of disturbed basis, distinguish which of the two sets of basis was given the addition of hard noise. Relationship between DHLP and AMG scheme: The relationship between DHLP and the AMG scheme is similar to the relationship between HLP and the AMG scemeintermsofequivalentparameters. DHLPprovidestwopossiblesubsetsofbasisthat aredisturbedwithhardnoiseandrequiresanadversarytodistinguishwhichonewasused to generate a set of disturbed basis. The Aguilar-Melchor Gaborit Scheme corresponds to a similar case where only one basis is disturbed. Thus if an adversary were able to solve DHLP they would be able to distinguish which basis was disturbed with hard noise and determine which element in the database a client was asking for, breaking the security of Aguilar-Melchor Gaborit Scheme. Relationship between HLP and DHLP: As Aguilar-Melchor and Gaborit claim, HLP is at least as hard as DHLP. An adversary capable of solving HLP is also capable of solvingDHLP.AsshownTheorem1anadversarycapableofsolvingHLPisabletoobtain every matrix D ∆, and can then determine which of these matrices have been disturbed i by the multiplication of q . hard 5 Security Analysis Here, we attempt to build upon the authors’ analysis of the security of their scheme. Our main goals in this section are to reduce an NP-Hard problem to the computational problems underlying the security of the Aguilar-Melchor Gaborit Scheme or to show that 9 itcanbeattackedthroughmethodssuchaslattices. Wehavenotbeensuccessfulindoing either, but we will give an overview of our attempts to do so through analyzing related work in the areas of coding theory, noise, and lattice attacks. 5.1 Reduction to a Hard Problem Aguilar-Melchor and Gaborit state that the Hidden Lattice Problem is "very likely hard" byobservingitssimilaritiestotheCodePunctureSearchProblem(CPSP),avariantofthe known NP-Complete Punctured Code Problem. We take Aguilar-Melchor and Gaborit’s justification a step further by providing a reduction between CPSP and HLP by showing that an instance of CPSP is actually a special case of HLP, and a black box solution of HLP can thus be used to solve CPSP. Below is the definition of CPSP as defined in [4]: Code Puncture Search Problem: Let H be a k×m matrix of rank k and M be a disturbed k×(m+s) matrix obtained by multiplying H by a random non-singular k×k matrix T and by adding to it s random columns in between the m columns of H. Deduce from these two matreices (H and M) which are the s random columns of M. An instance of CPSP is an instance of HLP:2 Letr inHLP(thenumberofbasis to be disturbed) be equal to 1. If |V| = r = 1, we know that i = 1 as there is only one 0 matrix available to recieve the addition of hard noise columns (columns disturbed by the multiplication of q and one element in each column). Let q be smaller than every element in M, and p be a prime number sufficiently large such that no element ever exceeds p. Consider the first random column added to M, s = [s |s |···|s ]. Construct the vector 1 2 k s(cid:48) =[s −q|s −1|···|s −1]. This gives s=s(cid:48)+[q|1|···|1]. s corresponds to a disturbed 1 2 k column in the result of HLP, where r = 1 for the soft noise addition and q = q for the j hard noise addition. This generalizes; all columns randomly added in the instance of the CPSP can be interpreted as columns of the HLP after being disturbed by soft noise equal to 1 and a hard noise coordinate equal to some value q. HLPisNP-Hard. AssumethatanalgorithmthatsolvestheHiddenLatticeProblem in polynomial time exists. Provide this algorithm an instance M of the Code Puncture Search Problem as input. As we have demonstrated above, M can be interpreted as an instanceofHLPwheretherandomlyaddedcolumnsofM correspondtodisturbedcolumns in the HLP. Running the HLP algorithm returns this set of columns, which can then be returned as the solution to CPSP. We have successfully solved CPSP in polynomial time. However, CPSP is proven to be NP-complete. Thus HLP is NP-Hard, as it is at least as hard as CPSP. HLP is verifiable in polynomial time. Theorem 1 in Section 4.1 demonstrates how an adversary with knowledge of the location of permuted columns can construct the matricesD ∆foralliinpolynomialtime. Averifierrunsthisandverifiesthat,forallbut i one D ∆, each column is composed of the same element (positive or negative), and that i foroneD ∆allbutoneelementofeachcolumnarearesame(againpositiveornegative), i0 and that the differing element differs from the rest of the elements of the column by some factor q. NotethatinSection4.1weshowtheAguilar-MelchorGaboritSchemeisaspecialcase of HLP. It is possible that this special case can be solved more efficiently. However, we believeittobeunlikely,andthatanybreakinthesecurityoftheAguilar-MelchorGaborit 2Inthecourseofourresearchthiswasoneoftheproposedreductions. Asagroupwearen’tcurrently sureofitscorrectness,butit’swhatwe’vegot. 10