The present invention relates to a method for verifying information, for example in a cloud computing system.

The present invention further relates to a computing system, for example cloud computing system for verifying information.

Although applicable to any kind of method or system for verifying information in general, the present invention will be described with regard to so-called verifiable computation.

Verifiable computation refers in general to a cryptographic protocol running between two parties, a proofer P and verifier V, with the aim to compute a proof or certificate of computation that a party given a function f and holding some potentially private input x has computed f(x). The cryptographic guarantees of the system are:

- Completeness: An honest proofer P computing f(x) from f and x convinces with overwhelming probability a verifier V of the fact that f(x) is computed properly.

- Soundness: A cheating proofer P having computed f (χ') not being equal to f(x) succeeds with negligible probability to convince the verifier of having computed f(x).

- Input Privacy (Zero-Knowledge): A malicious verifier V learns no information about the input x other than the fact that the proofer computed x.

- Function Privacy: The description of function f can be generated by a third party or jointly computed with a multi-party computation protocol such that the verifier does not learn f. - Knowledgeably: The only way of having computed f(x) given f is by knowing the input x. In fact that means, x must have been stored in the memory of the proofer while computing the proof. A possible setting demonstrating verifiable computation is cloud computing, as illustrated in Fig. 1. Here a resource-constraint device outsources a computational task to some powerful cloud and wishes the assurance of the correct computation.

One important application of verifiable computation is the evaluation of the quality of large data sets. Many service providers, e.g. social network providers, Internet and mobile network providers have access to huge amount of data and want to monetize their knowledge. Most importantly are statistics over data sets, such as consume or location behaviour. Verifiable computation allows a party to prove the correct computation of the statistics and probe the "quality of data" without revealing already the inputs. Depending on the quality the provider A1 can offer a price. The soundness property gives the buyer A5 the guarantee that the statistics were inferred over n data sets. The zero-knowledge property ensures that the buyer A5 learns nothing about the data entries. In the non-patent literature of George Danezis, Cedric Fournet, Jens Groth, and Markulf Kohlweiss, "Square span programs with applications to succinct nizk arguments", Cryptology ePrint Archive, Report 2014/718, 2014, http://eprint.iacr.org/ and Helger Lipmaa, "Succinct non-interactive zero knowledge arguments from span programs and linear error-correcting codes", Cryptology ePrint Archive, Report 2013/121 , 2013, http://eprint.iacr.org/ a span program was disclosed enabling a verification of Boolean functions.

In the further non-patent literature of Rosario Gennaro, Craig Gentry, Bryan Parno, and Mariana Raykova, "Quadratic span programs and succinct nizks without peps", Cryptology ePrint Archive, Report 2012/215, 2012, http://eprint.iacr.org/ a verification of arithmetic functions was disclosed based on quadratic arithmetic programs, 'QAP' which detailed implementation was disclosed in the non-patent literature of Gentry and Parno, available under http://research.microsoft.com/pubs/180286/Pinocchio.pdf. Said method was applied to verify random access machine programs as disclosed in the non-patent literature of Eli Ben-Sasson, Alessandro Chiesa, Eran Tromer, and Madars Virza, "Succinct non-interactive zero knowledge for a von neumann architecture", Cryptology ePrint Archive, Report 2013/879, 2013, http://eprint.iacr.org/.

Further in the non-patent literature of Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy, "Proof verification and the hardness of approximation problems", pages 501 -555, 1998 probabilistic checkable proof systems are disclosed being proof systems with a 2-sided error. However, these systems are unpractical, i.e. far away from practice.

In the non-patent literature of Yihua Zhang and Marina Blanton, "Efficient secure and verifiable outsourcing of matrix multiplications", Cryptology ePrint Archive, Report 2014/133, 2014, http://eprint.iacr.org/ and the related work mentioned therein proof systems are disclosed only addressing very special cases.

However, conventional methods for verifiable computation have significant problems. One problem is the computational cost of the verifier: The verifier approves correct computation. The verifier may simply compute the corresponding function alone and cross-check the results. However, if the complexity of computing is high and/or the size of the input x is large, for example the data base of billions of entries, or the input x has to be kept private the trivial solution of self- computing them for verification is not applicable. Another problem is the limited flexibility in terms of which functions can be verified as well as in terms of applicability in different fields.

It is therefore an objective of the present invention to provide a method and a system for verifying information reducing the computational costs of the verifier. In particular it is an objective of the present invention to provide a method and a system for verifying information enabling a verifier to spend time resources sublinear to those of a proofer, i.e. providing a method and a system for verifying information being 'succinct'. It is a further objective of the present invention to provide a method and a system for verifying information which can be easily applied in different fields and allow to verify information in particular in form of any polynomial function. The aforementioned objectives are accomplished by

a method for verifying information, e.g. in a cloud computing system,

the method comprising

by means of one or more computation devices:

generating an evaluation key and a verification key in a memory available to at least one of said computation devices based on a security parameter and a function to be evaluated by a key generator,

computing an output of said function using an input in a memory available to at least one of said computation devices

computing a proof for said outcome using said evaluation key in a memory available to at least one of said computation devices, and

verifying if said proof is valid based on said verification key in a memory available to at least one of said computation devices,

wherein

said function is defined as a mapping between matrix groups over a finite field and encoded into a polynomial in a memory available to at least one computation device.

The aforementioned objectives are also accomplished by a computational system, comprising one or more computation devices communicating with each other and being operable and configured to:

generate an evaluation key and a verification key in a memory available to at least one of said computation devices based on a security parameter and a function to be evaluated by a key generator,

to compute an output of said function using an input in a memory available to at least one of said computation devices,

to compute a proof for said outcome using said evaluation key in a memory available to at least one of said computation devices, and

to verify if said proof is valid based on said verification key in a memory available to at least one of said computation devices, wherein

said function is defined as a mapping between matrix groups over a finite field and encoded into a polynomial in a memory available to at least one computation device.

According to the invention it has been recognized that flexibility is significantly enhanced since for many computational models including linear programming, quadratic programming, convex programming and non-linear programming the present invention can be applied when the underlying functions are defined by polynomials over matrix groups. The present invention is useful inter alia in machine learning, privacy-preserving computation of statistics, benchmarking verification, etc..

According to the invention it has been further recognized that by performing the computations on matrix groups over fields the encoding of the computation can be reduced from O(q ³ ) polynomials to O(q ² ) polynomials.

According to the invention it has been even further recognized that proofs are probabilistically checkable.

According to the invention it has been even further recognized that the present invention is more general and flexible compared with conventional methods and systems allowing to compute any polynomial-size function defined over a matrix group.

According to the invention it has been even further recognized that the present invention has a very wide area of applicability and can in particular be connected to vector computing where owner of big data centers can host outsourced computational power.

Further features, advantages and preferred embodiments are described in the following subclaims. Each subclaim can be dependent of anyone of preceding claims. According to a preferred embodiment the function is encoded such that a target polynomial is generated being an element of said finite fields over the input which always divides said polynomial.

According to a further preferred embodiment the polynomial is described and implemented as an arithmetic circuit.

According to a further preferred embodiment the polynomial is the trace of a difference between the product of left and right input matrix polynomials of all gates of said arithmetic circuit and the output matrix polynomial of all gates of said arithmetic circuit.

According to a further preferred embodiment said input and output matrix polynomials are randomly shifted, 'MP-S', preferably by adding a product of said target polynomial with a random number to said input and output matrix polynomials.

According to a further preferred embodiment when computing said outcome a second polynomial is used with the input and same random information which is used for generating said keys.

According to a further preferred embodiment the proof is computed using said 'MP-S' dependent from said random information.

According to a further preferred embodiment for verifying said validity of the proof the correct structure of the arithmetic circuit is checked.

According to a further preferred embodiment for verifying said validity of the proof it is checked whether the target polynomial divides said MP-S.

According to a further preferred embodiment for verifying said validity of the proof the linear combinations computed over said MP-S are checked if they are in their corresponding spans. According to a further preferred embodiment said input is private.

There are several ways how to design and further develop the teaching of the present invention in an advantageous way. To this end it is to be referred to the patent claims subordinate to patent claim 1 on the one hand and to the following explanation of preferred embodiments of the invention by way of example, illustrated by the figure on the other hand. In connection with the explanation of the preferred embodiments of the invention by the aid of the figure, generally preferred embodiments and further developments of the teaching will be explained.

In the drawings

Fig. 1 shows a conventional cloud computing scenario;

Fig. 2 shows a part of steps of a method according to a first embodiment of the present invention;

Fig. 3 shows steps of a method according to a second embodiment of the present invention; and

Fig. 4 shows a computing system according to a third embodiment of the present invention.

Fig. 1 shows a conventional cloud computing scenario.

In Fig. 1 a provider A1 of the data sends data to a computation provider A3, i.e. a proofer. A function provider A2 sends a function to be computed also to the computation provider A3. The computation provider A3, for example a computation facility, performs computation of the provided function. The result of the computation is sent to a user A4 for further evaluation of the result. The computation provider A3 further sends a proof to a verifier A5 which then needs to verify the result of the function by verifying the received proof. Fig. 2 shows a part of steps of a method according to a first embodiment of the present invention.

In Fig. 2 an interaction between proofer P and verifier V to verify the computation of a function f(x) is shown. In the following definitions and notations are given:

[q] = 1 , . . . , q denotes the set of integers between 1 and q, and [qo, q-i] = qo, . . . , qi denotes the interval between qo and q-i.

Is the set of q x q matrices A = (ay) with elements a e F _p . The identity matrix is denoted by l _q where all element on the diagonal are 1 and the rest are zero. The transpose of the matrix is indicated by A ^T = (aji) and the multiplication of two matrices A, B e M _q (F) : M _q (F) e M _q (F)→ M _q (F) is defined as

and A ^* B e M _q (F) denotes the element-wise multiplication, i.e.

A * B = (ai _j bi _j ). ¥Ϊ, j e [q] g is a generator of a group G of order p. Then g ^A denotes (j ^Ql i } _{e H} € ,(G) Further A, B e M _q (F _p ), then (g ^A ) ^B denotes g ^{A*B =} (g ^a » ^b u) e with ije[q].

In the following the definition of a trace is given: A e is a square matrix. The trace of said matrix A, denoted as Tr{A}, is then defined as the linear operation

The trace induces an inner product <,> in F ^qxq . If A, B e F ^qxq then <A, B>= Tr{A ^T B}, where A ^T is the transpose matrix of A. B(Fq ^x q) = {Xi e Fq ^x q,i e [q ² ]} is a set of q matrices, where for every matrix

such that x'jk = 1 if (j - 1 )q + k = i, and 0 otherwise then B(Fq ^x q) is a basis of Fq ^x q.

This can be seen by inspection, A = E _i e¼ ^J ] ^α · ^χ _«

for some {a, e F, i e [q ² ]}. Actually a, is the value of matrix A where the element of X is non-zero. When A e Fq ^x q is a matrix and X, e B(Fq ^x q) is a basis then A

where a, = Tr{X ^T i A}, which can be seen from the following: The matrix product X ^T i A yields a matrix with the j-th row comprising the k-th row of A. The diagonal element is the (j, k)-th element of the original matrix A. Thus the operation of Tr{X ^T i A} = ajk. This is due to the fact that Tr{X ^T A} = <X,A> is the inner product in the space of Fq ^x q and using the expansion theorem: A =∑, <X,A>Xi.

The previous considerations simply state that the set of matrices X, can be used to sample the original matrix A. From an information-theoretic point of view A and {Tr{X ^T i A}, i e [q ² ], Xi e B(Fq ^x q)} are equivalent.

In the following the quadratic arithmetic programs, 'QAP', according to the nonpatent literature of Bryan Parno, Jon Howell, Craig Gentry, and Mariana Raykova, "Pinocchio: Nearly practical verifiable computation" in Security and Privacy (SP), 2013 IEEE Symposium on, pages 238-252, IEEE, 2013 or Rosario Gennaro, Craig Gentry, Bryan Parno, and Mariana Raykova, "Quadratic span programs and succinct nizks without peps", in Advances in Cryptology-EUROCRYPT 2013, pages 626-645, Springer, 2013 are shown. QAPs are a way to encode a function described as an arithmetic circuit into a polynomial described by a set of polynomials for every wire of the arithmetic circuit. The quadratic arithmetic program QAP according to the non-patent literature of Rosario Gennaro, Craig Gentry, Bryan Parno, and Mariana Raykova, "Quadratic span programs and succinct nizks without peps", in Advances in Cryptology-EUROCRYPT 2013, pages 626-645, Springer, 2013 is shown as follows: A QAP Q over a field F comprises three sets of m + 1 polynomials V = {Vk(x)}, W = {Wk(x)}, Y = {yk(x)}, for k e [m + 1] and a target polynomial t(x). Further F is a function from F ⁿ to F ⁿ ' and N = n+n .

Q "computes" F if there exists c e F ^m such that (c-i, ... ,c _n ) is the input, (C _n +i, . . . , CN) is the output and t x) divides p(x), where

Since t(x) divides p(x), there exists a polynomial h(x), such that p(x) = h(x)t(x).

Building a QAP Q for an arithmetic circuit C is performed as follows: an arbitrary root r _g e F is picked for each multiplication gate g in C and the target polynomial is defined to be t(x) = n _g (x - r _g ). An index k e [m] = {1 , ...,m} to each input of the circuit and to each output from a multiplication gate of said circuit, wherein the addition gates will be compressed into their contributions to the multiplication gates. Finally the polynomials in V, W, and Y are defined by letting the polynomials in V encode the left input into each gate, the W encode the right input into each gate, and the Y encode the outputs. For example, Vk(r _g ) = 1 if the k ^th wire is a left input to gate g, and Vk(r _g ) = 0 otherwise. Similarly, yk(r _g ) = 1 if the k ^th wire is the output of gate g, and yk(r _g ) = 0 otherwise. Thus, if a particular gate g and its root r _g is considered, the above equation simplifies to:

k= k=0 k=0 which says that the output value of the gate is equal to the product of its inputs, the very definition of a multiplication gate. In short, the divisibility check that t(x) divides p(x) decomposes into deg(t(x)) separate checks, one for each gate g and root r _g of t(x), that p(r _g ) = 0. In the following a public verifiable computation method according to the non-patent literature of Rosario Gennaro, Craig Gentry, and Bryan Parno, "Non-interactive verifiable computing: Outsourcing computation to untrusted workers", in Advances in Cryptology - CRYPTO 2010, pages 465-482, Springer Berlin Heidelberg, 2010 is shown. Such a public verifier computation is also disclosed in the non-patent literature of Bryan Parno, Mariana Raykova, and Vinod Vaikuntanathan, "How to delegate and verify in public: Verifiable computation from attribute-based encryption", in Theory of Cryptography, pages 422-439, Springer, 2012.

When F is a function to be outsourced and u the input and y = F(u) the associated output then a public verifiable computation scheme VC comprises of a set of three polynomial-time algorithms VC=(KeyGen, Compute, Verify), defined as follow

(EKF, VKF) <- KeyGen(F, 1 ^λ ): Taking as input the function F to be evaluated and a security parameter λ, the procedure generates/computes the evaluation key EKF and the verification key VK _F

(y. Ty) <- Compute(EKF, x) : The worker computes the output y = F(x) and the proof n _y using the evaluation key EKF and the (private) input x

{0,1} <- Verify(VKF, y, n _y ): from the verification keys VKF and the proof ny, the verifier checks whether n _y is a valid proof for having computed F(x) = y

In the following in more detail an embodiment of the present invention is described:

Said embodiment of the present invention provides an encoding for efficiently verifying the computation of matrix multiplication and additions wherein the encoding following conventional QAP is called here the quadratic matrix program, ΌΜΡ'. QAPs are defined over a finite field F _p of (prime) order p. The matrix group over the field F _p is not commutative, so it is not a field by itself. The results are extended to this context. This allows us to greatly simplify the QAP when matrix operations are involved.

2. Further a cryptographic protocol to verify the computation of QMPs, illustrated in Fig. 2 is given

In the following a variant of QAPs with the property of probabilistically checking the computation of function F is described. The QMP is sampled by means of a matrix X and then compute the trace in order to get a polynomial p(x, X) = h(x, X)t(x).

A QMP Q over a matrix group M _q (l _p ) over the field F _p comprises three sets of m+ 1 matrix polynomials V = {Vk(x)},W = {W _k (x)},Y = {Yk(x)}, for k e [m + 1 ], where Vk(x),Wk(x),Yk(x) <≡ Mq(F _p [x]) and a target matrix polynomial t(x) e F _p [x]. F is defined as a function from M _q (F _p ) ⁿ to M _q (F _p ) ⁿ ' and let N = n + n'. Q "computes" F if there exist coefficients C e M _q (F _p ) such that (C-i ,. . . , CN) is an assignment of the input and output wires, and if there exist coefficient matrices (CN+I, C _M ) such that for every X e M _q (F _p ) it holds that t(x) divides p(x, X), where

p(x, X) = Tr I X ^3" V ₀ (x) + V ^* C _fc * Vk

Tr {X ^T (V(x)W{x) - Y{x)) }

Tr { (V{x)W(x)X ^T ) } - Tr { (Y(x)X ^T ) }

where Vk(x), Wk(x), Yk(x) are matrix polynomials of the form with Lk, Rk, Ok is the set of left, right and output gates in which the connection k is active. The delta functions are here the Lagrange olynomial

Since t(x) divides p(x, X), there exists a polynomial h(x, X), such that

p(x, X) = h(x, X)t(x).

In the following a verifiable computation method allowing to verify a computation of a function is shown. One of the steps of this method is the encoding of the function as so-called pcQMP. The steps as mentioned with QAP, i.e. the key generation, the computation and the verification are also described in more detail for this embodiment of the present invention:

In the following F: M(F) ⁿ → M(F) ⁿ ' is the verification function of an outsourced operation, where N = n + n ^' , F _p is a field and M(F _P ) is the group of matrices on the field F _p and further the associated pcQMP is Q = (t(x), V, W, Y) of size m and degree d associated with F. Further I mid = [N + 1 , m] and o = [N], that corresponds to the indexes associated with the internal state of the arithmetic circuit or the input and output, while lo = [n] and h = [n+1 , n] are the indexes associated with the input and output connection of the circuit, e : G χ G→ GT is a non-trivial bilinear map and g a generator of G.

In the following the key generation is described in more detail: (EKF, VKF) <- KeyGen(F,1 ^A ): starting from the function F the associated pcQMP is generated for some random sample S <- M _q (F _p ). Slightly abusing notation, it is assumed that the polynomials in W and Y are randomly shuffled, i.e. Wk = WkS for every Wk e W and similarly for the polynomials in Y. The procedure then selects some random elements r _v ,r _w ,s,c(v,c(w,c(y,p, γ <- F _p and sets r _y = r _v ^■ r _w , g _v = g ^rv , g _w = g ^rw and g _y = g ^ry .The evaluation key EKF is generated according to

Ek ^p —

, iiC ^¾W }fei _{nil£i 5} te* ^{i ¾ i} %e ifl£* ^¾W }*e/»

- {i ^* k[# {ff ^¾(s ½ ^r gf ^m h ) while the verification key is set as

In the following the Computation of F is described in more detail: (y, n _y ) <- Compute(EKF, x) : The worker computes y = F(x), using the coefficient of the pcQMP {Ci}i _e [m] and then resolve for h(x, S) such that p(x, S) = h(x, S)t(x) and computes the proof as

where V _mid (x) * V _k (x), V (x) = V ₀ (x) +∑k _e[ m] C _k * V _k (x) , W(x) = W ₀ (x) + ∑ke [m] Ck * Wk(x) and Y (s) = Y ₀ (x) +∑k _e[ m] C _k * Y _k (s).

The computation is done directly in the exponent, e.g.

9 ^,1 = S ^¾W n _fcH (9 ^¾,, - In the following the verification is described in more detail:

{0. 1} 4- Verifg( ¥¾ , x, » _» τ¾) ; The verifier checks using the bilinear map c and the verification key VKp, if:

Compute from ike verification key VKF

gi" ^{s) = ΐίι, ΐί^ψι* (and s ^' imilarly for _¾ T" ^W and _% " ^W J, and check

— Check that the linear combinations computed over V. W and y are in their appropriate Bpam:

— Check that the, same coefficients mere used in each of the linear combination over e(g ^z ^) = e(g^g^g^ ^) Fig. 3 shows steps of a method according to a second embodiment of the present invention. In Fig. 3 steps of a method for verifying information are shown.

The method comprising by means of one or more computation devices the following steps: The first step S1 comprises generating an evaluation key and a verification key in a memory available to at least one of said computation devices based on a security parameter and a function to be evaluated by a key generator.

The second step S2 comprises computing an output of said function using an input in a memory available to at least one of said computation devices.

The third step S3 comprises computing a proof for said outcome using said evaluation key in a memory available to at least one of said computation devices, and the fourth step S4 comprises verifying if said proof is valid based on said verification key in a memory available to at least one of said computation devices, wherein said function is defined as a mapping between matrix groups over a finite field and encoded into a polynomial in a memory available to at least one computation device. These steps may be performed by different computation devices or computing entities.

Fig. 4 shows a computing system according to a third embodiment of the present invention.

In Fig. 4 a computing system comprising a plurality of computation devices CD1 , CD2, CD3, CD4 are shown. The first computation device CD1 is configured to generate an evaluation key and verification key in a memory available to at least one of said computation devices based on a security parameter and a function to be evaluated by a key generator.

The second computation device CD2 is configured to compute an output of said functional using an input in a memory available to at least one of said computation devices.

The third computation device CD3 is configured to compute a proof for said outcome using said evaluation key in a memory available to at least one of said computation devices.

The fourth computation device CD4 is configured to verify if said proof is valid based on said verification key in a memory available to at least one of said computation devices, wherein either computation devices CD1 , CD2, CD3, CD4 said function is defined as a mapping between matrix groups over a finite field and encoded into a polynomial in a memory available to at least one computation device.

In particular the present invention, in particular at least one embodiment provides the following:

• A verification paradigm over matrix group that allows to verify a polynomial evaluation efficiently. Conventional methods can be applied to matrix polynomials but not natively in the group of Matrix, since the matrix group is not commutative. In particular the trick to verify computation over Matrix groups is to compute the trace to define an inner product inside the matrix group.

• A construction of sampling matrices reducing the complexity to constant time with respect to the matrix group size. In particular the trick here is that the sampling can be of special shape in order to reduce computational complexity.

The present invention enables an implementation of a complex matrix problem over a cloud system leaving to the verifier constant time verification problem which is practical for all polynomial time-computable functions. Many modifications and other embodiments of the invention set forth herein will come to mind to the one skilled in the art to which the invention pertains having the benefit of the teachings presented in the foregoing description and the associated drawings. Therefore, it is to be understood that the invention is not to be limited to the specific embodiments disclosed and that modifications and other embodiments are intended to be included within the scope of the appended claims. Although specific terms are employed herein, they are used in a generic and descriptive sense only and not for purposes of limitation.