*13:17* [Pub][ePrint]
Efficient Non-Interactive Zero Knowledge Arguments for Set Operations, by Prastudy Fauzi and Helger Lipmaa and Bingsheng Zhang
We propose a non-interactive zero knowledge \\emph{pairwise multiset sum equality test (PMSET)} argument in the common reference string (CRS) model that allows a prover to show that the given committed multisets $\\AAA_j$ for $j \\in \\set{1, 2, 3, 4}$ satisfy $\\AAA_1 \\uplus \\AAA_2 = \\AAA_3 \\uplus \\AAA_4$, i.e., every element is contained in $\\AAA_1$ and $\\AAA_2$ exactly as many times as in $\\AAA_3$ and $\\AAA_4$.As a corollary to the $\\PUTME$ argument, we present arguments that enable to efficiently verify the correctness of various (multi)set operations, for example, that one committed set is the intersection or union of two other committed sets.

The new arguments have constant communication and verification complexity (in group elements and group operations, respectively), whereas the CRS length and the prover\'s computational complexity are both proportional to the cardinality of the (multi)sets.

We show that one can shorten the CRS length at the cost of a small increase of the communication and the verifier\'s computation.

*13:17* [Pub][ePrint]
A Certificate-Based Proxy Signature with Message Recovery without Bilinear Pairing, by Ali Mahmoodi, Javad Mohajeri, Mahmoud Salmasizadeh
In this paper, we propose the first provable secure certificate-based proxy signature with message recovery without bilinear pairing. The notion of certificate-based cryptography was initially introduced by Gentry in 2003, in order to simplify certificate management in traditional public key cryptography(PKC)and to solve the key escrow problem in identity-based cryptosystems. To date, a number of certificate-based proxy signature(CBPS)schemes from bilinear pairing have been proposed. Nonetheless, the total computation cost of a pairing is higher than that of scalar multiplication(e.g., over elliptic curve group). Consequently, schemes without pairings would be more appealing in terms of efficiency. According to the available research in this regard, our scheme is the first provable secure CBPS scheme with message recovery which is based on the elliptic curve discrete logarithm problem. We prove the security of the presented scheme against existential forgery under adaptive chosen message and ID attacks in the random oracle model. Moreover, the paper will also show how it would be possible to convert this scheme to the CBPS scheme without message recovery. This scheme has more applications in situations with limited bandwidth and power-constrained devices.

*10:17* [Pub][ePrint]
MaxMinMax problem and sparse equations over finite fields, by Igor Semaev
Asymptotical complexity of sparse equation systems over finite field $F_q$ is studied. Let the variable sets belong to a fixed family $\\mathcal{X}=\\{X_1,\\ldots,X_m\\}$ while

the polynomials $f_i(X_i)$ are taken independently and uniformly at random from the set of all polynomials

of degree $\\leq q-1$ in each of the

variables in $X_i$. In particular, for $|X_i|\\le3$, $m=n$, we prove

the average complexity of finding all solutions to $f_i(X_i)=0, i=1,\\ldots,m$ by Gluing algorithm ( Semaev, Des. Codes Cryptogr., vol. 49 (2008), pp.47--60) is at most $

q^{\\frac{n}{5.7883}+O(\\log n)}$ for arbitrary $\\mathcal{X}$ and $q$. The proof results from a detailed analysis of 3-MaxMinMax problem, a novel problem for hyper-graphs.

*10:17* [Pub][ePrint]
Pseudorandom Generator Based on Hard Lattice Problem, by Kuan Cheng
This paper studies how to construct a pseudorandom generator using hard lattice problems.We use a variation of the classical hard problem \\emph{Inhomogeneous Small Integer Solution} ISIS of lattice, say \\emph{Inhomogeneous Subset Sum Solution} ISSS. ISSS itself is a hash function. Proving the preimage sizes ISSS hash function images are almost the same, we construct a pseudorandom generator using the method in \\cite{GKL93}. Also, we construct a pseudoentropy generator using the method in \\cite{HILL99}. Most theoretical PRG constructions are not feasible in fact as they require rather long random bits as seeds. Our PRG construction only requires seed length to be $O(n^{2}\\log_{2} n)$ which is feasible practically.

*10:17* [Pub][ePrint]
$GF(2^n)$ Bit-Parallel Squarer Using Generalized Polynomial Basis For a New Class of Irreducible Pentanomials, by Xi Xiong and Haining Fan
We present explicit formulae and complexities of bit-parallel $GF(2^{n})$ squarers for a new class of irreducible pentanomials$x^{n}+x^{n-1}+x^{k}+x+1$, where $n$ is odd and $1