International Association
for Cryptologic Research

The security of public key validation protocols for web-based applications has recently attracted attention because of weaknesses in the certificate authority model, and consequent attacks.

Recent proposals using public logs have succeeded in making certificate management more transparent and verifiable. How- ever, those proposals involve a fixed set of authorities which create a monopoly, and they have heavy reliance on trusted parties that monitor the logs.

We propose a distributed transparent key infrastructure (DTKI), which greatly reduces the monopoly of service providers and removes the reliance on trusted parties. In addition, this paper formalises the public log data structure and provides a formal analysis of the security that DTKI guarantees.

We show that for certain class of unconditionally secure protocols and

target functionalities, static security implies adaptive security in the UC

model. Similar results were previously only known for models with

weaker security and/or composition guarantees. The result is, for

instance, applicable to a wide range of protocols based on secret

sharing. It ``explains\'\' why an often used proof technique for such

protocols works, namely where the simulator runs in its head a copy of

the honest players using dummy inputs and generates a protocol

execution by letting the dummy players interact with the

adversary. When a new player $P_i$ is corrupted, the simulator

adjusts the state of its dummy copy of $P_i$ to be consistent with

the real inputs and outputs of $P_i$ and gives the state to the

adversary. Our result gives a characterisation of the cases where this

idea will work to prove adaptive security. As a special case,

we use our framework to give the first proof of adaptive security

of the seminal BGW protocol in the UC framework.

Payments through cards have become very popular in today\'s world. All businesses now have options to receive payments through this instrument, moreover most organizations store card information of its customers in

some way to enable easy payments in future. Credit card data is a very sensitive information and theft of this data is a serious threat to any company. Any organization that stores credit card data needs to achieve payment card industry (PCI) compliance, which is an intricate process where the organization needs to demonstrate that the data it stores is safe. Recently there has been a paradigm shift in treatment of the problem of storage of payment card information. In this new paradigm instead of the real credit card data a token is stored, this process is called ``tokenization\". The token resembles the

credit/debit card number but is in no way related to it. This solution relieves the merchant from the burden of PCI compliance in several ways.

Though tokenization systems are heavily in use, to our knowledge, a formal cryptographic study of this problem has not yet been done. In this paper we initiate a study in this direction. We formally define the syntax of a tokenization system, and several notions of security for such systems. Finally, we provide some constructions of tokenizers and analyze their security in the light of our definitions.

Submission: 31 August 2014
Notification: 7 November 2014
From December 13 to December 15
Location: Beijing, China
More Information: http://www.inscrypt.cn/2014/

Submission: 19 January 2015
Notification: 2 March 2015
From April 13 to April 17
Location: Paris, France
More Information: http://wcc2015.inria.fr/

Submission: 20 October 2014
Notification: 20 December 2014
From April 20 to April 24
Location: San Francisco, USA
More Information: http://www.rsaconference.com/events/us15

- Conception and definition of cryptographic algorithms (block ciphers, hash functions, asymmetric primitives, protocols)

- Implementation cryptographic primitives and protocols in C/C++/Python languages

- Definitions of related tests for validation

- Definition and implementation of dedicated tools to aid implementation and analysis of cryptographic algorithms

- Work closely with HW design and verification team

- Close collaboration with software teams for system validation

- Working closely with security architects and system architects for definition of requirements

- Follow-up of related academic literature and developments

- Deliver crypto specifications documents to internal teams

- Provide guidance and support to peers in tools and IP design

The Digital Security group at the Radboud University Nijmegen invites

applications for PhD and PostDoc positions in applied cryptography and embedded security.

The research envisioned is on side-channel cryptanalysis, fault attacks and countermeasures and/or lightweight cryptography (protocols, crypto primitives and implementations).

The project has sufficient funds to support career development, conference visits, summer schools, and similar scientific activities.

Requirements

For PhD students:

Successful candidates must hold an M.Sc. degree (or equivalent) from the university study of Computer Science, Mathematics or Engineering. Applications from students that are expected to finish their master thesis within 1 year will also be considered. Prior background/experience in cryptography and/or computer security is an asset.

For PostDocs:

Applicants should have a Ph.D. and expertise in at least one of the following research areas:

- applied cryptography

- embedded security

- hardware design for cryptography/cryptanalysis

- side-channel analysis and countermeasures

- machine learning and data mining

We expect proven expertise in your area of research by publications at top conferences and journals, some experience with EU projects, student supervision etc.

Conditions of employment

PhD positions are for 4 years, PostDoc positions are for up to 2 years, the expected starting dates are flexible.

Candidates moving to the Netherlands from abroad may qualify for a tax incentive scheme, where 30% of your income is tax-free.

For additional information, see http://www.ru.nl/ds, and for the positions contact:

Lejla Batina (http://www.cs.ru.nl/~lejla/), lejlaATcs.ru.nl

<

Submission: 8 January 2015
From January 28 to January 30
Location: Dubai, UAE
More Information: http://sdiwc.net/conferences/ebecegc2015/

Non-interactive zero-knowledge proofs of knowledge for general NP statements are a powerful cryptographic primitive, both in theory and in practical applications. Recently, much research has focused on achieving an additional property, succinctness, requiring the proof to be very short and easy to verify. Such proof systems are known as zero-knowledge succinct non-interactive arguments of knowledge (zk-SNARKs), and are desired when communication is expensive, or the verifier is computationally weak.

Existing zk-SNARK implementations have severe scalability limitations, in terms of space complexity as a function of the size of the computation being proved (e.g., running time of the NP statement\'s decision program). First, the size of the proving key is quasilinear in the upper bound on the computation size. Second, producing a proof requires \"writing down\" all intermediate values of the entire computation, and then conducting global operations such as FFTs.

The bootstrapping technique of Bitansky et al. (STOC \'13), following Valiant (TCC \'08), offers an approach to scalability, by recursively composing proofs: proving statements about acceptance of the proof system\'s own verifier (and correctness of the program\'s latest step). Alas, recursive composition of known zk-SNARKs has never been realized in practice, due to enormous computational cost.

Using new elliptic-curve cryptographic techniques, and methods for exploiting the proof systems\' field structure and nondeterminism, we achieve the first zk-SNARK implementation that practically achieves recursive proof composition. Our zk-SNARK implementation runs random-access machine programs and produces proofs of their correct execution, on today\'s hardware, for any program running time. It takes constant time to generate the keys that support all computation sizes. Subsequently, the proving process only incurs a constant multiplicative overhead compared to the original computation\'s time, and an essentially-constant additive overhead in memory. Thus, our zk-SNARK implementation is the first to have a well-defined, albeit low, clock rate of \"verified instructions per second\".

The increasing availability and use of biometric data for authentication and

other purposes leads to situations when sensitive biometric data is to be

handled or used in computation by entities who may not be fully trusted or

otherwise authorized to have full access to such data. This calls for

mechanisms of provably protecting biometric data while still allowing the

computation to take place. In this work, we treat the problem of

privacy-preserving matching of two fingerprints, which can be used for

secure fingerprint authentication and identification. We utilize traditional

minutia-based representation of fingerprints that leads to the most

discriminative (i.e., accurate) fingerprint comparisons. Unlike prior work,

we design a data-oblivious algorithm that results in the most accurate

outcome of fingerprint matching through a more complex minutia pairing

approach based on maximum flow in bipartite graphs. This algorithm then

leads to secure fingerprint matching solutions of high security standards.

The complexity of our solution is higher than those of some other available

protocols, but nevertheless we show that our techniques still efficiently

compare two fingerprints with provable security guarantees. That is, they

run in a similar amount of time to those with simpler matching mechanisms

which are not guaranteed to find the best matching.

In this paper we revisit the notion of generalized universal composability (GUC)

introduced by Canetti, Dodis, Pass and Walfish in 2007. The GUC model was

intended to model a practical setting where setup parameters, like a PKI or a CRS,

are made public once and for all and then used by many different protocols.

We show that there exist protocols which can be proven secure in the GUC model,

but which are obviously insecure in practice, in the setting that the GUC model was

intended to capture. We then proceed to revise the GUC model to a version that

better models the intended practical setting. We call the new notion strong generalized

UC. We finally prove that the GUC protocols proposed by Canetti, Dodis, Pass and Walfish

are also strong GUC secure, i.e., whereas there is a problem with the model, the

protocols seem to be secure in the intended setting.

In the last few years garbled circuits (GC) have been elevated from being merely a component in Yao\'s protocol for secure two-party computation, to a cryptographic primitive in its own right, following the growing number applications that use GCs.

Zero-Knowledge (ZK) protocols is one of these examples: In a recent paper Jawurek et al. [JKO13] showed that GCs can be used to construct efficient ZK for unstructured languages. In this work we show that due to the property of this particular scenario (i.e., one of the party knows all the secret input bits, and therefore all intermediate values in the computation), we can construct more efficient garbled schemes specifically tailored to this goal.

As a highlight of our result, in one of our constructions only one encryption per gate needs to be communicated, and XOR gates never require any cryptographic operation.

In addition to making a step forward towards more practical ZK, we believe that our contribution is also interesting from a conceptual point of view: in the terminology of Bellare et al. [BHR12] our garbling schemes achieve authenticity, but no privacy nor obliviousness, therefore representing the first natural separation between those notions.

Lattice-based cryptographic primitives are believed to offer resilience against attacks by quantum computers. We demonstrate the practicality of post-quantum key exchange by constructing ciphersuites for the Transport Layer Security (TLS) protocol that provide key exchange based on the ring learning with errors (R-LWE) problem; we accompany these ciphersuites with a rigorous proof of security. Our approach ties lattice-based key exchange together with traditional authentication using RSA or elliptic curve digital signatures: the post-quantum key exchange provides forward secrecy against future quantum attackers, while authentication can be provided using RSA keys that are issued by today\'s commercial certificate authorities, smoothing the path to adoption.

Our cryptographically secure implementation, aimed at the 128-bit security level, reveals that the performance price when switching from non-quantum-safe key exchange is not too high. With our R-LWE ciphersuites integrated into the OpenSSL library and using the Apache web server on a 2-core desktop computer, we could serve 506 RLWE-ECDSA-AES128-GCM-SHA256 HTTPS connections per second for a 10 KiB payload. Compared to elliptic curve Diffie--Hellman, this means an 8 KiB increased handshake size and a reduction in throughput of only 21%. This demonstrates that post-quantum key-exchange can already be considered practical.

A 4 year PhD student position is available at the Department of Informatics of the University of Bergen. Some of the possible research directions are coding theory, cryptography, Boolean functions, sequence design.

Information on application requirements and work conditions can be found at http://www.jobbnorge.no/ledige-stillinger/stilling/103925/stipendiat-i-informatikk

A machine is said to be {\\em oblivious} if the sequences of memory accesses made by the machine for two inputs with the same running time are identically (or close to identically) distributed. Oblivious RAM (ORAM) compilers -- compilers that turn any RAM program $\\Pi$ into an oblivious RAM $\\Pi\'$, while incurring only a \"small\", polylogarithmic, slow-down -- have been extensively studied since the work of Goldreich and Ostrovsky (JACM 1996), and have numerous fundamental applications. These compilers, however, do not leverage parallelism: even if $\\Pi$ can be heavily parallelized, $\\Pi\'$ will be inherently sequential.

In this work, we present the first {\\em Oblivious Parallel RAM (OPRAM)} compiler, which compiles any PRAM into an oblivious PRAM while incurring only a polylogarithmic slowdown.

Submission: 6 October 2014
Notification: 28 December 2014
From March 23 to March 25
Location: Warsaw, Poland
More Information: http://www.iacr.org/workshops/tcc2015/

This paper presents new speed records for multiprecision multiplication on the AVR ATmega family of 8-bit microcontrollers. For example, our software takes only 1976 cycles for the multiplication of two 160-bit integers; this is more than 15% faster than previous work. For 256-bit inputs, our software is not only the first to break through the 6000-cycle barrier; with only 4797 cycles it also breaks through the 5000-cycle barrier and is more than 21% faster than previous work.We achieve these speed records by carefully optimizing the Karatsuba multiplication technique for AVR ATmega. One might expect that subquadratic-complexity Karatsuba multiplication is only faster than algorithms with quadratic complexity for large inputs. This paper shows that it is in fact faster than fully unrolled product-scanning multiplication already for surprisingly small inputs, starting at 48 bits. Our results thus make Karatsuba multiplication the method of choice for high-performance implementations of elliptic-curve cryptography on AVR ATmega microcontrollers.

The paper is about algorithms for the inhomogeneous short integer solution problem: Given A, b to find a short vector s such that As \\equiv b (mod q). We consider algorithms for this problem due to Camion and Patarin; Wagner; Schroeppel and Shamir; Howgrave-Graham and Joux; Becker, Coron and Joux. Our main results include: Applying the Hermite normal form (HNF) to get faster algorithms; A heuristic analysis of the HGJ and BCJ algorithms in the case of density greater than one; An improved cryptanalysis of the SWIFFT hash function.

Structure-preserving signature schemes can be very useful in the construction of new cryptographic operations like blind signatures. Recently several of these schemes have been proposed. The security of signature-preserving signature schemes is still proved by hand, which can be a laborious task. One of the ways to prove security of these schemes algebraic analysis can be used. We present an approach to perform this analysis and the first tool, CheckSPS, that can do an algebraic security analysis of these schemes, using SMT solvers as backend. This can help in constructing new schemes and analyse existing schemes. Our tool can handle all the common security objectives for signature schemes, i.e. existential unforgeability and strong existential unforgeability, and all the common capabilities for adversaries, i.e. random message attacks, non-adaptive chosen message attacks and adaptive chosen message attacks. The tool is sound, so if an attack is found it is actually possible to construct a forged signature.