International Association for Cryptologic Research

# IACR News Central

Get an update on changes of the IACR web-page here. For questions, contact newsletter (at) iacr.org. You can also get this service via

You can also access the full news archive.

Further sources to find out about changes are CryptoDB, ePrint RSS, ePrint Web, Event calender (iCal).

2012-12-14
22:17 [Pub][ePrint]

In this paper we consider the problem of secure pattern matching that allows

single-character wildcards and substring matching in the malicious (stand-alone) setting.

Our protocol, called 5PM, is executed between

two parties: Server, holding a text of length $n$, and

Client, holding a pattern of length $m$ to be matched

against the text, where our notion of matching is more general and includes non-binary alphabets, non-binary Hamming distance and non-binary substring matching.

5PM is the first secure expressive pattern matching protocol designed to optimize round complexity by carefully specifying the entire protocol round by round. In the malicious model, 5PM requires $O((m+n)k^2)$ bandwidth and $O(m+n)$ encryptions, where $m$ is the pattern length and $n$ is the text length. Further, 5PM can hide pattern size with no asymptotic additional costs in either computation or bandwidth. Finally, 5PM requires only two rounds of communication

in the honest-but-curious model and eight rounds in the malicious model. Our techniques reduce

pattern matching and generalized Hamming distance problems to a novel linear algebra formulation that allows for generic solutions based on any additively homomorphic encryption. We believe our efficient algebraic techniques are of independent interest.

22:17 [Pub][ePrint]

We conduct a practically oriented study of the cryptosystem suggested by Alekhnovich based on the Learning Parity with Noise (LPN) problem. We consider several improvements to the scheme, inspired by similar existing variants of Regev\'s LWE-based cryptosystem. Our conclusion is that LPN-based public-key cryptography indeed seems practical. Based on known attacks on LPN, we found that for 80-bit security, while making very conservative choices of parameters for LPN, the timings for transmitting a key for a symmetric cryptosystem are somewhat worse than for RSA, but not prohibitive for practical use.

22:17 [Pub][ePrint]

We present a general framework for efficient, universally composable oblivious transfer (OT) protocols in which a single, global common reference string (CRS) can be used for multiple invocations of oblivious transfer, by arbitrary pairs of parties. In addition:

* Our framework is round-efficient. In particular, under the DLIN or SXDH assumptions we achieve (round-optimal) two-round protocols with static security, or three-round protocols with adaptive security (assuming erasure).

* Our protocols are more efficient than any known previously, and in particular yield protocols for string OT using O(1) exponentiations and sending O(1) group elements. Our result improves upon that of Peikert et al. (Crypto 2008) which requires a CRS of length

linear in the number of parties and achieves only static security. Compared to Garay et al. (Crypto 2009), we achieve better efficiency and can rely on a larger class of assumptions.

19:17 [Pub][ePrint]

\\emph{Randomized encodings of functions} can be used to replace a complex\'\' function $f(x)$

by a simpler\'\' randomized mapping $\\hat{f}(x;r)$ whose output

distribution on an input $x$ encodes the value of $f(x)$ and hides any other information.

One desirable feature of randomized encodings is low \\emph{online complexity}. That is, the goal is to obtain a randomized encoding

$\\hat{f}$ of $f$ in which most of the output can be precomputed and published before seeing the input $x$. When the input $x$ is available, it remains to publish only a short string $\\hat{x}$, where the online complexity of computing $\\hat{x}$ is independent of (and is typically much smaller than) the complexity of computing $f$. Yao\'s garbled circuit construction gives rise to such randomized encodings in which the online part $\\hat{x}$ consists of $n$ encryption keys of length $\\kappa$ each, where $n=|x|$ and $\\kappa$ is a security parameter. Thus, the {\\em online rate} $|\\hat{x}|/|x|$ of this encoding is proportional to the security parameter $\\kappa$.

In this paper, we show that the online rate can be dramatically improved. Specifically, we show how to encode any polynomial-time computable function $f:\\bit^n\\to\\bit^{m(n)}$ with online rate of $1+o(1)$ and with nearly linear online computation. More concretely, the online part $\\hat{x}$ consists of an $n$-bit string and a single encryption key. These constructions can be based on the decisional Diffie-Hellman assumption (DDH), the Learning with Errors assumption (LWE), or the RSA assumption. We also present a variant of this result which applies to \\emph{arithmetic formulas}, where the encoding only makes use of arithmetic operations, as well as several negative results which complement our positive results.

Our positive results can lead to efficiency improvements in most contexts where randomized encodings of functions are used. We demonstrate this by presenting several concrete applications. These include protocols for secure multiparty computation and for non-interactive verifiable computation in the preprocessing model which achieve, for the first time, an optimal online communication complexity, as well as non-interactive zero-knowledge proofs which simultaneously minimize the online communication and the prover\'s online computation.

19:17 [Pub][ePrint]

In this paper we cryptanalyze two protocols: Grigoriev-Shpilrain

authentication protocol and Wang et al. public key encryption protocols

that use computational hardness of some variations of the conjugacy search problem

in noncommutative monoids. We devise a practical heuristic algorithm

solving those problems.

As a conclusion we claim that these protocols are insecure for the proposed parameter values.

19:17 [Pub][ePrint]

Verifiable security is an emerging approach in cryptography that

advocates the use of principled tools for building machine-checked

security proofs of cryptographic constructions. Existing tools

following this approach, such as EasyCrypt or CryptoVerif, fall short

of finding proofs automatically for many interesting constructions. In

fact, devising automated methods for analyzing the security of large

classes of cryptographic constructions is a long-standing problem

which precludes a systematic exploration of the space of possible

schemes, a class of public-key encryption schemes built from hash

functions and trapdoor permutations, which includes widely used

constructions such as RSA-OAEP.

Firstly, we provide algorithms to search for proofs of security

against chosen-plaintext and chosen-ciphertext attacks in the random

oracle model. These algorithms are based on domain-specific logics

with a computational interpretation and yield quantitative security

guarantees; for proofs of chosen-plaintext security, we output

machine-checked proofs in EasyCrypt. Secondly, we provide a crawler

for exhaustively exploring the space of padding-based encryption

schemes under user-specified restrictions (e.g. on the size of their

description), using filters to prune the search space. Lastly, we

provide a calculator that computes the security level and efficiency

of provably secure schemes that use RSA as trapdoor permutation.

Using these three tools, we explore over 1.3 million encryption

schemes, including more than 100 variants of OAEP studied in the

literature, and prove chosen-plaintext and chosen-ciphertext security

for more than 250,000 and 17,000 schemes, respectively.

2012-12-11
08:57 [Job][New]

The School of Computer and Communication Sciences at EPFL invites applications for faculty positions in computer and communication sciences. We are primarily seeking candidates for tenure-track assistant professor positions; suitably qualified candidates for senior positions will also be considered.

Successful candidates will develop an independent and creative research program, participate in both undergraduate and graduate teaching, and supervise PhD students.

Candidates from all areas of computer science will be considered, but preference will be given to candidates in the fields of machine learning or system security, as well as of computer science theory or human-computer-interaction (HCI). An explicit interest in the fields of medicine or energy is a plus.

EPFL offers internationally competitive salaries, significant start-up resources, and outstanding research infrastructure.

The following documents are requested in PDF format: curriculum vitae, including publication list, brief statements of research and teaching interests, names and addresses (including e-mail) of 3 references for junior positions, and 6 for senior positions. Screening will start on January 15, 2013. Further questions can be addressed to :

Prof. Ruediger URBANKE

Chairman of the recruiting committee

School of Computer and Communication Sciences

EPFL

CH-1015 Lausanne

recruiting.ic (at) epfl.ch

http://www.epfl.ch or http://ic.epfl.ch

EPFL is an equal opportunity employer.

06:38 [Job][New]

The post-doctoral researcher will have the opportunity to work in a dynamic and interdisciplinary team, to pursue research in the area of information security. The post-doctoral researcher will be expected to oversee projects, procedures and students, prepare data and write reports/articles for technical publications as well as participate in future grant proposal development.

2012-12-10
13:17 [Pub][ePrint]

In the setting of secure multiparty computation, a set of parties wish to compute a joint function of their inputs, while preserving properties like privacy, correctness, and independence of inputs. One security property that has typically not been considered in the past relates to the length or size of the parties inputs. This is despite the fact that in many cases the size of a party\'s input can be confidential. The reason for this omission seems to have been the folklore belief that, as with encryption, it is impossible to carry out non-trivial secure computation while hiding the size of parties\' inputs. However some recent results (e.g., Ishai and Paskin at TCC 2007, Ateniese, De Cristofaro and Tsudik at PKC 2011) showed that it is possible to hide the input size of one of the parties for some limited class of functions, including secure two-party set intersection. This suggests that the folklore belief may not be fully accurate.

In this work, we initiate a theoretical study of input-size hiding secure computation, and focus on the two-party case. We present definitions for this task, and deal with the subtleties that arise in the setting where there is no a priori polynomial bound on the parties\' input sizes. Our definitional study yields a multitude of classes of input-size hiding computation, depending on whether a single party\'s input size remains hidden or both parties\' input sizes remain hidden, and depending on who receives output and if the output size is hidden from a party in the case that it does not receive output. We prove feasibility and impossibility results for input-size hiding secure two-party computation. Some of the highlights are as follows:

Under the assumption that fully homomorphic encryption (FHE) exists, there exist non-trivial functions (e.g., the millionaire\'s problem) that can be securely computed while hiding the input size of both parties.

Under the assumption that FHE exists, every function can be securely computed while hiding the input size of one party, when both parties receive output (or when the party not receiving output does learn the size of the output). In the case of functions with fixed output length, this implies that every function can be securely computed while hiding one party\'s input size.

There exist functions that cannot be securely computed while hiding both parties\' input sizes. This is the first formal proof that, in general, some information about the size of the parties\' inputs must be revealed.

Our results are in the semi-honest model. The problem of input-size hiding is already challenging in this scenario. We discuss the additional difficulties that arise in the malicious setting and leave this extension for future work.

13:17 [Pub][ePrint]

We present new families of access structures that, similarly to the multilevel and compartmented access structures introduced in previous works, are natural generalizations of threshold secret sharing. Namely, they admit an ideal linear secret sharing schemes over

every large enough finite field, they can be described by a small number of parameters, and they have useful properties for the applications of secret sharing. The use of integer polymatroids makes it possible to find many new such families and it simplifies in great measure

the proofs for the existence of ideal secret sharing schemes for them.

13:17 [Pub][ePrint]

The stream cipher WG-7 is a lightweight variant of the well-known Welch-Gong (WG) stream cipher family, targeting for resource-constrained devices like RFID tags, smart cards, and wireless sensor nodes. Recently, a distinguishing attack was discovered against the stream cipher WG-7 by Orumiehchiha, Pieprzyk and Steinfeld. In this paper, we

extend their work to a general distinguishing attack and suggest criteria to protect the WG stream cipher family from this attack. Our analysis shows that by properly choosing the minimal polynomial of the linear feedback shift register for a WG stream cipher, the general distinguishing attack can be easily thwarted.