*09:30*[PhD][New] Luk Bettale: Algebraic Cryptanalysis: Tools and Applications

Name: Luk Bettale

Topic: Algebraic Cryptanalysis: Tools and Applications

Category: applications

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

- eMail subscription
- RSS (select channels below)
- Web (all channels)

To receive your credentials via mail again, please click here.

You can also access the full news archive.

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

Name: Luk Bettale

Topic: Algebraic Cryptanalysis: Tools and Applications

Category: applications

2012-05-10

We are seeking someone with specialized experience developing cryptographic and hash algorithms including but not limited to triple DES,AES, SHA, etc. Demonstrated experience in developing, analyzing, testing, and researching Public Key Infrastructures using X.509 certificates, symmetric and public key algorithms, hash functions and quantum cryptography.

Duties may include but are not limited to: Performs complex analysis, design, development, integration, testing and debugging cryptographic and hashing algorithms. Apply cryptography-based solutions to contemporary use cases such as evaluating for FIPS 140 compliance, electronic voting, smart grid, health care, and resource constrained environments including but not limited to smart meters, smart cards, and medical devices.

We have two positions: Intermediate Cryptographer (5yrs exp) and Senior Cryptographer (10+ years exp)

Submission: 2 July 2012

Notification: 31 August 2012

From October 30 to October 30

Location: Austin, TX, USA

More Information: http://www.cse.msu.edu/~feichen/NPSec2012

The Linux pseudorandom number generator (PRNG) is a PRNG with entropy

inputs which is widely used in many security related applications and

protocols. This PRNG is written as an open source code which is

subject to regular changes. It was last analyzed in the work of

Gutterman et al. in 2006 [GPR06] but since then no new

analysis has been made available, while in the meantime several changes have been applied to the code,

among others, to counter the attacks presented

[GPR06]. Our work describes the Linux PRNG of kernel

versions 2.6.30.7 and upwards. We detail the PRNG architecture

in the Linux system and provide its first accurate mathematical

description and a precise analysis of the building blocks, including entropy estimation and extraction. Subsequently, we give a security analysis including the feasibility of cryptographic attacks and an empirical test of the entropy estimator..

Finally, we underline some important changes to the previous

versions and their consequences.

A private set intersection (PSI) protocol allows two parties to compute the intersection of their input sets privately. Most of the previous PSI protocols only output the result to one party and the other party gets nothing from running the protocols. However, a mutual PSI protocol in which both parties can get the output is highly desirable in many applications. A major obstacle in designing a mutual PSI protocol is how to ensure fairness. In this paper we present the first fair mutual PSI protocol which is efficient and secure. Fairness of the protocol is obtained in an optimistic fashion, i.e. by using an offline third party arbiter. In contrast to many optimistic protocols which require a fully trusted arbiter, in our protocol the arbiter is only required to be semi-trusted, in the sense that we consider it to be a potential threat to both parties\' privacy but believe it will follow the protocol and not collude with any of the two parties. The arbiter can resolve disputes blindly without knowing any private information belongs to the two parties. This feature is appealing for a PSI protocol in which privacy may be of ultimate importance.

Recently, He et al. [D. He, J. Chen, J. Hu, A pairing-free certificateless authenticated key agreement protocol, International Journal of Communication Systems, 25(2), pp. 221-230, 2012] proposed a pairing-free certificateless authenticated key agreement protocol and demonstrated that their protocol is provable security in the random oracle model. However, in this paper, we show that t He et al. protocol is completely broken.

We propose a novel small-domain pseudo-random permutation, also referred to as a small-domain cipher or small-domain (deterministic) encryption. We prove that our construction achieves \"strong security\", i.e., is indistinguishable from a random permutation even when an adversary has observed all possible input-output pairs. More importantly, our construction is 1,000 to 8,000 times faster in most realistic scenarios, in comparison with the best known construction (also achieving strong security). Our implementation leverages the extended instruction sets of modern processors, and we also introduce a smart caching strategy to freely tune the tradeoff between time and space.

Yao\'s garbled circuit construction transforms a boolean circuit $C:\\{0,1\\}^n\\to\\{0,1\\}^m$ into a ``garbled circuit\'\' $\\hat{C}$ along with $n$ pairs of $k$-bit keys, one for each input bit, such that $\\hat{C}$ together with the $n$ keys corresponding to an input $x$ reveal $C(x)$ and no additional information about $x$. The garbled circuit construction is a central tool for constant-round secure computation and has several other applications.

Motivated by these applications, we suggest an efficient arithmetic variant of Yao\'s original construction. Our construction transforms an arithmetic circuit $C : \\mathbb{Z}^n\\to\\mathbb{Z}^m$ over integers from a bounded (but possibly exponential) range into a garbled circuit $\\hat{C}$ along with $n$ affine functions $L_i : \\mathbb{Z}\\to \\mathbb{Z}^k$ such that $\\hat{C}$ together with the $n$ integer vectors $L_i(x_i)$ reveal $C(x)$ and no additional information about $x$. The security of our construction relies on the intractability of the learning with errors (LWE) problem.

A prominent strand within the side-channel literature is the quest for generic strategies: methods by which data-dependent leakage measurements may be fruitfully analysed with minimal a priori insight into the processes occasioning that leakage. In this paper, we introduce a well-reasoned formal definition for `a generic strategy\', enabling us, for the first time, to clarify precise conditions (on the target function) under which (asymptotic) success is possible. The range of vulnerable targets is shown to be limited---noninjectivity and nonlinearity being minimal requirements---and so the `myth\' is somewhat dispelled. However, we then explore the particular opportunities presented by linear regression-based methods, which are able to operate generically, but can in fact be leveraged by non-specific intuition about the leakage through the application of a model building technique called stepwise regression. Thus a minor relaxation of the strict generic assumptions `magically\' produces asymptotically successful outcomes even against injective targets.