International Association for Cryptologic Research

IACR News Central

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-17
07:01 [Event][New]

Submission: 15 January 2013
From July 3 to July 5
Location: Taichung, Taiwan

2012-12-15
13:12 [Event][New]

Submission: 17 March 2013
From July 10 to July 12
Location: Tarragona, Catalonia, Spain

13:11 [Job][Update]

The Government Communications Headquarters (GCHQ) in Cheltenham has agreed in principle to sponsor a PhD/Doctoral Studentship at CSIT, Queens University Belfast in the area of Novel Application of Advanced Machine Learning Techniques for use in Side Channel Analysis Attacks.

This GCHQ-sponsored PhD studentship provides funding for 3.5 years and commences on 31 September 2013 with a proposed end date of March/April 2017. GCHQ will cover the costs of university fees and will provide an annual stipend to the student corresponding to the National Minimum Stipend (currently £13,590 per annum) plus an additional sum of £7,000 per annum (both tax free). For comparison this is equivalent to approx. £26,555 annual salary. A further £5k of funding will also be available per annum for travel to conferences, collaborative partners, and GCHQ visits.

The studentship is only open to UK nationals and the successful candidate will be required to spend in the region of 2 - 4 weeks per year at GCHQ headquarters in Cheltenham. To be considered for this studentship, candidates must therefore be prepared to undergo GCHQ\\\'s security clearance procedures.

13:11 [Job][New]

The Government Communications Headquarters (GCHQ) in Cheltenham has agreed in principle to sponsor a PhD/Doctoral Studentship at CSIT, Queens University Belfast in the area of Novel Application of Advanced Machine Learning Techniques for use in Side Channel Analysis Attacks.

This GCHQ-sponsored PhD studentship provides funding for 3.5 years and commences on 31 September 2013 with a proposed end date of March/April 2017. GCHQ will cover the costs of university fees and will provide an annual stipend to the student corresponding to the National Minimum Stipend (currently £13,590 per annum) plus an additional sum of £7,000 per annum (both tax free). For comparison this is equivalent to approx. £26,555 annual salary. A further £5k of funding will also be available per annum for travel to conferences, collaborative partners, and GCHQ visits.

The studentship is only open to UK nationals and the successful candidate will be required to spend in the region of 2 - 4 weeks per year at GCHQ headquarters in Cheltenham. To be considered for this studentship, candidates must therefore be prepared to undergo GCHQ\'s security clearance procedures.

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

RAKAPOSHI is a hardware oriented stream cipher designed by Carlos Cid et al. in 2009. The stream cipher is based on Dynamic Linear Feedback Shift Registers, with a simple and potentially scalable design, and is particularly suitable for hardware applications with restricted resources. The RAKAPOSHI stream cipher offers 128-bit security. In this paper, we point out some weaknesses in the cipher. Firstly, it shows that there are 2^192 weak (key, IV) pairs in RAKAPOSHI stream cipher. Secondly, for weak (key, IV) pairs of RAKAPOSHI, they are vulnerable to linear distinguishing attack and algebraic attack. Finally, we propose a real time related key chosen IV attack on RAKAPOSHI. The attack on RAKAPOSHI recovers the 128-bit secret key of with a computational complexity of 2^37, requiring 47 related keys, 2^8 chosen IVs and 2^14.555 keystream bits. The success probability of this attack is 0.999, which is quite close to 1. The experimental results corroborate our assertion.

22:17 [Pub][ePrint]

In order to guarantee a fair and transparent voting process, electronic voting schemes must be verifiable. Most of the time, however, it is important that elections also be anonymous. The notion of a verifiable shuffle describes how to satisfy both properties at the same time: ballots are submitted to a public bulletin board in encrypted form, verifiably shuffled by several mix servers (thus guaranteeing anonymity), and then verifiably decrypted by an appropriate threshold decryption mechanism. To guarantee transparency, the intermediate shuffles and decryption results, together with proofs of their correctness, are posted on the bulletin board throughout this process.

In this paper, we present a verifiable shuffle and threshold decryption scheme in which, for security parameter k, L voters, M mix servers, and N decryption servers, the proof that the end tally corresponds to the original encrypted ballots is only O(k(L + M + N)) bits long. Previous verifiable shuffle constructions had proofs of size O(kLM + kLN), which, for elections with thousands of voters, mix servers, and decryption servers, meant that verifying an election on an ordinary computer in a reasonable amount of time was out of the question.

The linchpin of each construction is a controlled-malleable proof (cm-NIZK), which allows each server, in turn, to take a current set of ciphertexts and a proof that the computation done by other servers has proceeded correctly so far. After shuffling or partially decrypting these ciphertexts, the server can also update the proof of correctness, obtaining as a result a cumulative proof that the computation is correct so far. In order to verify the end result, it is therefore sufficient to verify just the proof produced by the last server.

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.