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-10
13:17 [Pub][ePrint]

This paper presents a comprehensive study of the computation of square roots over finite extension fields.

We propose two novel algorithms for computing square roots over even field extensions

of the form $\\F_{q^{2}}$, with $q=p^n,$ $p$ an odd prime and $n\\geq 1$. Both algorithms have an associate

computational cost roughly equivalent to one exponentiation in $\\F_{q^{2}}$.

The first algorithm is devoted to the case when $q\\equiv 1 \\bmod 4$, whereas the second one handles the case when

$q\\equiv 3 \\bmod 4$. Numerical comparisons show that the two algorithms presented in this paper are competitive

and in some cases more efficient than the square root methods previously known.

13:17 [Pub][ePrint]

Gr{\\o}stl is one of the five finalists in the third round of SHA-3

competition hosted by NIST. In this paper, we use many techniques to

improve the pseudo preimage attack on Gr{\\o}stl hash function, such

as subspace preimage attack and guess-and-determine technique. We

present improved pseudo preimage attacks on 5-round Gr{\\o}stl-256

and 8-round Gr{\\o}stl-512 respectively. The complexity of the above

two attacks are ($2^{239.90},2^{240.40}$) (in time and memory) and

($2^{499.50},2^{499}$) respectively. Furthermore, we propose pseudo

preimage attack and pseudo second preimage attack on 6-round

Gr{\\o}stl-256. The complexity of our 6-round pseudo preimage and

second preimage attack is ($2^{253.26},2^{253.67}$) and

($2^{251.0},2^{252.0}$) respectively. As far as we know, these are

the best known attacks on round-reduced Gr{\\o}stl hash function.

13:17 [Pub][ePrint]

Over the past decade bilinear maps have been used to build a large variety of cryptosystems.

In addition to new functionality, we have concurrently seen the emergence of many strong assumptions.

In this work, we explore how to build bilinear map cryptosystems under progressively weaker assumptions.

We propose $k$-BDH, a new family of progressively

weaker assumptions that generalizes the decisional bilinear

Diffie-Hellman (DBDH) assumption. We give evidence in the generic

group model that each assumption in our family is strictly weaker

than the assumptions before it. DBDH has been used for proving many

schemes secure, notably identity-based and functional encryption

schemes; we expect that our $k$-BDH will lead to generalizations of

many such schemes.

To illustrate the usefulness of our $k$-BDH family, we

construct a family of selectively secure Identity-Based Encryption (IBE) systems based on it. Our system can be viewed

as a generalization of the Boneh-Boyen IBE, however, the construction and proof require new ideas to

fit the family. We then extend our methods to produces hierarchical IBEs and CCA

security; and give a fully secure variant. In addition, we discuss the opportunities and challenges of building

new systems under our weaker assumption family.

13:17 [Pub][ePrint]

We use a variant of learning with errors (LWE) problem, a simple and direct extension of the original LWE problem to the case of a small secret, which we call

a small LWE problem (SLWE), to build a new simple and provably secure key exchange scheme. The basic idea behind the construction can be viewed as certain type of bilinear pairing with errors (PE). We build a more efficient implementation of our scheme using a similar LWE problem but solely based on matrices, and we extend our construction further using the ring LWE problem, where the provable security is based on the hardness of the ring LWE problem.

13:17 [Pub][ePrint]

A \\captcha is a puzzle that is easy for humans but hard to solve for computers.

A formal framework,

modelling \\captcha puzzles (as hard AI problems), was introduced by

Ahn, Blum, Hopper, and Langford (\\cite{AhnBHL03}, Eurocrypt 2003). Despite their

attractive features and wide adoption in practice, the use of \\captcha puzzles

for general cryptographic applications has been limited.

In this work, we explore various ways to formally model \\captcha puzzles and their human component

and

explore new applications for \\captcha. We show that by defining \\captcha with

it is possible to broaden \\captcha applicability, including using it to learning a machine\'s

secret internal state.\'\'

To facilitate this, we introduce

the notion of an human-extractable \\captcha, which we believe may be of independent interest.

We show that this type of \\captcha yields a \\emph{constant round} protocol for \\emph{fully}

concurrent non-malleable zero-knowledge. To enable this we also define and

construct a \\captcha -based commitment scheme which admits straight line\'\' extraction.

We also explore

\\captcha definitions in the setting of Universal Composability (UC). We show that there are two (incomparable) ways to

In particular, we show that in the so called

\\emph{indirect access model}, for every polynomial time functionality $\\calf$

there exists a protocol that UC-realizes $\\calf$ using human-extractable \\captcha, while for the so-called

\\emph{direct access model}, UC is impossible, even with the help of human-extractable \\captcha.

The security of our constructions using human-extractable \\captcha

is proven against the (standard) class of

all polynomial time adversaries. In contrast, most previous works guarantee

security only against a very limited class of adversaries, called the

13:17 [Pub][ePrint]

In this paper, we concentrate on the security issues of the integrity protection of LTE and present two different forgery attacks. For the first attack, referred to as a {\\em linear forgery attack}, EIA1 and EIA3, two integrity protection algorithms of LTE, are insecure if the initial value (IV) can be repeated twice during the life cycle of an integrity key (IK). Because of the linearity of EIA1 and EIA3, given two valid Message Authentication Codes (MACs) our algorithm can forge up to $2^{32}$ valid MACs. Thus, the probability of finding a valid MAC is dramatically increased. Although the combination of IV and IK never repeats in the ordinary case, in our well-designed scenario, the attacker can make the same combination occur twice. The duplication provides the opportunity to conduct our linear forgery attack, which may harm the security of communication. To test our linear forgery attack algorithm, we generate two counter check messages and successfully forge the third one. We also examine the attack timing by simulating real communication. From the experimental results, our attack is applicable. The second attack is referred to as a {\\em trace extension forgery attack}, which works only in theory. However, this attack is more general than the linear forgery attack. Known only one MAC and message pair, we can construct a different message, who has the same MAC as the original one, with the probability $\\frac{1}{2^{16}}$. In this attack, trace function is applied to the message to shrink the guessing space.

13:17 [Pub][ePrint]

The general number field sieve (GNFS) is the most efficient

algorithm known for factoring large integers. It consists of several

stages, the first one being polynomial selection. The quality of the

chosen polynomials in polynomial selection can be modelled in terms of

size and root properties. In this paper, we describe some algorithms for

selecting polynomials with very good root properties.

13:17 [Pub][ePrint]

In this paper we investigate the security for integrated public-key encryption (PKE)

and public-key encryption with keyword search (PEKS) schemes. We observe that the security

notions for integrated PKE and PEKS schemes considered in the existing literature are not strong

enough to capture practical attacks, thus define a new notion named joint CCA-security which is

shown to be stronger than the previous ones. We also propose two simple and efficient constructions

of jointly CCA-secure integrated PKE and PEKS schemes from anonymous (hierarchical) identity-

based encryption schemes. Besides, we review the consistency for PEKS schemes and improve

previous results.

2012-12-08
22:30 [Job][New]

The Information Security discipline at the Queensland University of Technology (QUT) in Brisbane, Australia, invites applications for a 2-year post-doctoral researcher position in cryptography starting in 2013. The focus of the position is on analyzing and characterizing the overall security of real-world cryptographic protocols such as TLS. We are looking for outstanding candidates with experience in cryptographic modelling, provable security, and key exchange protocols. The position is supported by an Australia Research Council (ARC) Discovery Project grant.

Applicants should have recently completed, be under examination for, or be close to submitting a PhD. Starting salary is between AUD$57,187 and$77,598 per annum, plus 17% pension contribution. Funds for relocation and travel will also be available.

QUT\'s Science and Engineering Faculty has an active and growing group with research strengths in cryptography, network security, and digital forensics, with a leading national profile and strong international links. QUT is investing heavily in science and technology research, with a new \$240 million facility in the heart of Brisbane\'s central business district housing many interdisciplinary research groups, including information security. Brisbane is a city of 2 million people with a high quality of living, and many of Queensland\'s stunning beaches and wilderness are less than half an hour away.

2012-12-07
10:05 [Event][New]

Submission: 11 March 2013
From June 23 to June 24
Location: Ekaterinburg, Russia

2012-12-06
15:56 [Job][New]

The Government Communications Headquarters (GCHQ) in Cheltenham, UK, has agreed in principle to sponsor two PhD/Doctoral Studentships to be held with the Information Security Group of Royal Holloway (University of London) in the area of cryptography. The studentships will be funded for a period of 3.5 years, starting in September 2013. The two studentships available are as follows:

A Computational Algebra Approach to Learning with Errors

Supervisors: Dr Carlos Cid and Prof. Sean Murphy

Randomness in Cryptography – Theory Meets Practice

Supervisor: Prof. Kenny Paterson

Note that the studentships are only open to UK nationals and the successful candidates 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.