*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

*16:17* [Pub][ePrint]
New Constructions of Revocable Identity-Based Encryption from Multilinear Maps, by Seunghwan Park and Kwangsu Lee and Dong Hoon Lee
A revocation mechanism in cryptosystems for a large number of users is absolutely necessary to maintain the security of whole systems. A revocable identity-based encryption (RIBE) provides an efficient revocation method in IBE that a trusted authority periodically broadcasts an update key for non-revoked users and a user can decrypt a ciphertext if he is not revoked in the update key. Boldyreva, Goyal, and Kumar (CCS 2008) defined RIBE and proposed an RIBE scheme that uses a tree-based revocation encryption scheme to revoke users. However, this approach has an inherent limitation that the number of private key elements and update key elements cannot be constant. In this paper, to overcome the previous limitation, we devise a new technique for RIBE and propose RIBE schemes with a constant number of private key elements. We achieve the following results: - We first devise a new technique for RIBE that combines hierarchical IBE (HIBE) scheme and a public-key broadcast encryption (PKBE) scheme by using multilinear maps. In contrast to the previous technique for RIBE, our technique uses a PKBE scheme in bilinear maps for revocation to achieve short private keys and update keys.

- Following our new technique for RIBE, we propose an RIBE scheme in 3-leveled multilinear maps that combines the HIBE scheme of Boneh and Boyen and the PKBE scheme of Boneh, Gentry, and Waters. The private key and update key of our scheme have a constant number of group elements. To prove the security of our scheme, we introduce a new complexity assumption in multilinear maps, and prove its security in the selective revocation list model.

- Next, we propose another RIBE scheme that reduces the number of public parameters by using the parallel construction technique of PKBE. We could reduce the number of public parameters by using the fact that only the trusted authority in RIBE can broadcast an update key.

*16:17* [Pub][ePrint]
Can Bitcoin Scale? Secure High-Rate Transaction Processing in The Bitcoin Network, by Yonatan Sompolinsky and Aviv Zohar
Bitcoin is a potentially disruptive new crypto-currency based on a decentralized open-source protocol which is gradually gaining popularity. Perhaps the most important question that will affect Bitcoin\'s success, is whether or not it will be able to scale to support the high volume of transactions required from a global currency system.We investigate the restrictions on the rate of transaction processing in Bitcoin as a function of both the bandwidth available to nodes and the network delay, both of which lower the efficiency of Bitcoin\'s transaction processing.

The security analysis done by Bitcoin\'s creator Satoshi Nakamoto~\\cite{nakamoto2008bitcoin} assumes that block propagation delays are negligible compared to the time between blocks---an assumption that does not hold when the protocol is required to process transactions at high rates. We improve upon the original analysis and remove this assumption.

Using our results, we are able to give bounds on the number of transactions per second the protocol can handle securely. Building on previously published measurements by Decker and Wattenhofer~\\cite{Decker2013Information}, we show these bounds are currently more restrictive by an order of magnitude than the bandwidth needed to stream all transactions. We additionally show how currently planned improvements to the protocol, namely the use of transaction hashes in blocks (instead of complete transaction records), will dramatically alleviate these restrictions.

Finally, we present an easily implementable modification to the way Bitcoin constructs its main data structure, the blockchain, that immensely improves security from attackers, especially when the network operates at high rates. This improvement allows for further increases in the number of transactions processed per second. We show that with our proposed modification, significant speedups can be gained in confirmation time of transactions as well. The block generation rate can be securely increased to more than one block per second -- a 600 fold speedup compared to today\'s rate, while still allowing the network to processes many transactions per second.

*06:37* [Job][New]
Computer Engineering, *Ariel University, Israel, Mediterranean*
The Department of Electrical and Electronic Engineering at Ariel University (Israel) invites applications for a tenure-track Lecturer or Senior Lecturer (Assistant Professor) position to begin in 2014. The position is full-time, tenure-track, with eligible benefits. The candidate will teach undergraduate and graduate courses in the computer engineering track, including required courses such as Introduction to programming in C, Introduction to microprocessors, and elective courses such as Computer networking laboratory and Assembly language.

The candidate\\\'s areas of research should be in one of the following areas:

Coding, cryptography, information protection, cyber security

Computer network design and analysis

Computer architecture and parallel distributed processing

Data storage

Compilers and operating systems

Wireless sensor networks

Cloud computing

Quantum computers

*22:17* [Pub][ePrint]
MQ Signature and Proxy Signature Schemes with Exact Security Based on UOV Signature, by Shaohua Tang, Jiahui Chen, Lingling Xu, Xiaoyu Li
Multivariate public key cryptography which relies on MQ (Multivariate Quadratic) problems is one of the main approaches to guarantee the security of communication in the post-quantum world. In this paper, we propose a combined MQ signature scheme based on the yet unbroken UOV (Unbalanced Oil and Vinegar) signature if parameters are properly chosen. Our scheme can not only reduce the public key size of the UOV signature, but also provide more tighter bound of security against chosen-message attack in the random oracle model. On the other hand, we propose a proxy signature scheme based on our proposed combined signature scheme. Additionally, we give a strict security proof for our proxy signature scheme. Finally, we present experiments for all of our proposed schemes and the baseline schemes. Comparisons with related schemes show that our work has some advantages on performance alongwith more strict security.