*21:17* [Pub][ePrint]
Invertible Polynomial Representation for Private Set Operations, by Hyung Tae Lee and Hyunsook Hong and Jung Hee Cheon
In many private set operations, a set is represented by a polynomial over a ring $\\Z_\\sigma$ for a composite integer $\\sigma$, where $\\Z_\\sigma$ is the message space of some additive homomorphic encryption. While it is useful for implementing set operations with polynomial additions and multiplications, a polynomial representation has a limitation due to the hardness of polynomial factorizations over $\\Z_\\sigma$. That is, it is hard to recover a corresponding set from a resulting polynomial over $\\Z_\\sigma$ if $\\sigma$ is not a prime. In this paper, we propose a new representation of a set by a polynomial over $\\Z_\\sigma$, in which $\\sigma$ is a composite integer with {\\em known factorization} but a corresponding set can be efficiently recovered from a polynomial except negligible probability. Note that $\\Z_\\sigma[x]$ is not a unique factorization domain, so a polynomial may be written as a product of linear factors in several ways. To exclude irrelevant linear factors, we introduce a special encoding function which supports early abort strategy. As a result, our representation can be efficiently inverted by computing all the linear factors of a polynomial in $\\Z_\\sigma[x]$ whose root locates in the image of encoding function.

When we consider group decryption as in most private set operation protocols, inverting polynomial representations should be done without a single party possessing a factorization of $\\sigma$. This is very hard for Paillier\'s encryption whose message space is $\\Z_N$ with unknown factorization of $N$. Instead, we detour this problem by using Naccache-Stern encryption with message space $\\Z_\\sigma$ where $\\sigma$ is a smooth integer with public factorization. As an application of our representation, we obtain a constant round privacy preserving set union protocol. Our construction improves the complexity than the previous without honest majority assumption. It can be also used for constant round multi-set union protocol and private set intersection protocol even when decryptors do not possess a superset of the resulting set.

*21:17* [Pub][ePrint]
Cryptanalysis of a recent two factor authentication scheme , by Michael Scott
Very recently a scheme has been proposed by Wang and Ma for a robust smart-card based password authentication scheme, which claimsto be secure against a Smart Card security breach. In this short note we attempt an initial cryptanalysis of this scheme.

*18:17* [Pub][ePrint]
Optimizing Segment Based Document Protection (Corrected Version), by Miroslaw Kutylowski and Maciej Gebala
In this paper we provide a corrected and generalized version of the scheme presented at SOFSEM\'2012 in our paper ``Optimizing Segment Based Document Protection\'\' (SOFSEM 2012: Theory and Practice of Computer Science, LNCS 7147, pp. 566-575).

We develop techniques for protecting documents with restricted access rights. In these documents so called \\emph{segments} are encrypted. Different segments may be encrypted with different keys so that different user may be given different \\emph{access rights}. Hierarchy of access rights is represented by means of a directed acyclic \\emph{access graph}. The segments are encrypted with keys - where each key corresponds to one node in the access graph. The main feature of the access graph is that if there is an arch $\\overrightarrow{AB}$ in the graph, then all segments labelled with $B$ can be decrypted with the key corresponding to node $A$.

We show how to minimize the space overhead necessary for auxiliary keying information stored in the document. We provide an algorithm based on node disjoint paths in the access graph and key derivation based on one-way functions. Our current solution, based on maximal weighted matchings, provides an optimal solution for creating subdocuments, in case when frequency of creating each subdocument is known.

*18:17* [Pub][ePrint]
Functional Encryption with Bounded Collusions via Multi-Party Computation, by Sergey Gorbunov and Vinod Vaikuntanathan and Hoeteck Wee
We construct a functional encryption scheme secure against an a priori bounded polynomial number of collusions for the class of all polynomial-size circuits. Our constructions require only semantically secure public-key encryption schemes and pseudo-random generators computable by small-depth circuits (known to be implied bymost concrete intractability assumptions). For certain special cases such as predicate encryption schemes with public index, the construction requires only semantically secure encryption schemes, which is clearly the minimal necessary assumption.

Our constructions rely heavily on techniques from secure multiparty computation and randomized encodings. All our constructions are secure under a strong, adaptive simulation-based definition of functional encryption.

*18:17* [Pub][ePrint]
False Positive probabilities in q-ary Tardos codes: comparison of attacks, by A. Simone and B. Skoric
We investigate False Positive (FP) accusation probabilities forq-ary Tardos codes in the Restricted Digit Model.

We employ a computation method recently introduced by us,

to which we refer as Convolution and Series Expansion (CSE).

We present a comparison of several collusion attacks on q-ary codes: majority voting, minority voting, Interleaving, $\\tilde\\mu$-minimizing and Random Symbol (the q-ary equivalent of the Coin Flip strategy).

The comparison is made by looking at the FP rate at approximately fixed False Negative rate.

In nearly all cases we find that the strongest attack is either

minority voting or $\\tilde\\mu$-minimizing, depending on the exact setting of parameters such as alphabet size, code length, and coalition size.

Furthermore, we present results on the convergence speed of the CSE method, and we show how FP rate computations for the Random Symbol strategy can be sped up by a pre-computation step.

*18:17* [Pub][ePrint]
The Curious Case of Non-Interactive Commitments, by Mohammad Mahmoody and Rafael Pass
It is well-known that one-way permutations (and even one-to-one one-way functions) imply the existence of non-interactive commitments. Furthermore the construction is black-box (i.e., the underlying one-way function is used as an oracle to implement the commitment scheme, and an adversary attacking the commitment scheme is used as an oracle in the proof of security).We rule out the possibility of black-box constructions of non interactive commitments from general (possibly not one-to-one) one-way functions. As far as we know, this is the first result showing a natural cryptographic task that can be achieved in a black-box way from one-way permutations but not from one-way functions.

We next extend our black-box separation to constructions of non-interactive commitments from a stronger notion of one-way functions, which we refer to as \\emph{hitting} one-way functions. Perhaps surprisingly, Barak, Ong, and Vadhan (Siam JoC \'07) showed that there does exist a non-black-box construction of non-interactive commitments from hitting one-way functions. As far as we know, this is the first result to establish a ``separation\'\' between the power of black-box and non-black-box use of a primitive to implement a natural cryptographic task.

We finally show that unless the complexity class NP has program checkers, the above separations extend also to non-interactive instance-based commitments, and 3-message public-coin honest-verifier zero-knowledge protocols with O(log n)-bit verifier messages. The well-known classical zero-knowledge proof for NP fall into this category.

*12:51* [Job][New]
TENURE-TRACK OR TENURED POSITION , *Aalto University School of Science, Helsinki, Finland*
The position is located at the Department of Information and Computer Science (http://ics.aalto.fi/ ), and is open to outstanding individuals who hold a doctorate and have excellent potential for a successful scientific career. Research fields compatible with the call are algorithms, logic and complexity. Within these fields the areas of cryptology, combinatorial algorithms, computational logic, and distributed computing are currently represented at the Department.

Aalto University (http://www.aalto.fi/en/) is a new university created in 2010 from the merger of the Helsinki University of Technology TKK, Helsinki School of Economics and the University of Art and Design Helsinki. The University’s cornerstones are its strengths in education and research, with 20,000 basic degree and graduate students, and a staff of 5 000 of whom 350 are professors.