International Association
for Cryptologic Research

This paper proposes the computation of the Tate pairing,

Ate pairing and its variations on the special Jacobi quartic elliptic curve

Y^2 = dX^4 +Z^4. We improve the doubling and addition steps in Miller\'s

algorithm to compute the Tate pairing. We use the birational equivalence

between Jacobi quartic curves and Weierstrass curves, together with a

specific point representation to obtain the best result to date among

curves with quartic twists. For the doubling and addition steps in Miller\'s

algorithm for the computation of the Tate pairing, we obtain a theoretical

gain up to 27% and 39%, depending on the embedding degree and the

extension field arithmetic, with respect to Weierstrass curves [2] and

previous results on Jacobi quartic curves [3]. Furthermore and for the

first time, we compute and implement Ate, twisted Ate and optimal

pairings on the Jacobi quartic curves. Our results are up to 27% more

ecient, comparatively to the case of Weierstrass curves with quartic

twists [2].

We examine the widespread SimonsVoss digital locking system

3060 G2 that relies on an undisclosed, proprietary protocol to mutually authenticate transponders and locks. For assessing the security of the system, several tasks have to be performed: By decapsulating the used microcontrollers with acid and circumventing their read-out protection with UV-C light, the complete program code and data contained in door lock and transponder are extracted. As a second major step, the multi-pass challenge-response protocol and corresponding cryptographic primitives are recovered via low-level reverse-engineering. The primitives turn out to be based on DES in combination with a proprietary construction.

Our analysis pinpoints various security vulnerabilities that enable practical key-recovery attacks. We present two different approaches for unauthorizedly gaining access to installations. Firstly, an attacker having physical access to a door lock can extract a master key, allowing to mimic transponders, in altogether 30 minutes. A second, purely logical attack exploits an implementation flaw in the protocol and works solely via the wireless interface. As the only prerequisite, a valid ID of a transponder needs to be known (or guessed). After executing a few (partial) protocol runs in the vicinity of a door lock, and some seconds of computation, an adversary obtains all of the transponder\'s access rights.

An attacker can efficiently factor at least 184 distinct 1024-bit RSA keys from Taiwan\'s national \"Citizen Digital Certificate\" database. The big story here is that these keys were generated by government-issued smart cards that were certified secure. The certificates had all the usual buzzwords: FIPS certification from NIST (U.S. government) and CSE (Canadian government), and Common Criteria certification from BSI (German government).

These 184 keys include 103 keys that share primes and that are efficiently factored by a batch-GCD computation. This is the same type of computation that was used last year by two independent teams (USENIX Security 2012: Heninger, Durumeric, Wustrow, Halderman; Crypto 2012: Lenstra, Hughes, Augier, Bos, Kleinjung, Wachter) to factor tens of thousands of cryptographic keys on the Internet.

The remaining 81 keys do not share primes. Factoring these 81 keys requires taking deeper advantage of randomness-generation failures: first using the shared primes as a springboard to characterize the failures, and then using Coppersmith-type partial-key-recovery attacks. This is the first successful public application of Coppersmith-type attacks to keys found in the wild.

In this article, we propose an improved cryptanalysis of the double-branch hash function standard RIPEMD-160. Using a carefully designed non-linear path search tool, we study the potential differential paths that can be constructed from a difference in a single message word and show that some of these message words can lead to very good differential path candidates. Leveraging the recent freedom degree utilization technique from Landelle and Peyrin to merge two branch instances, we eventually manage to obtain a semi-free-start collision attack for 42 steps of the RIPEMD-160 compression function, while the previously best know result reached 36 steps. In addition, we also describe a 36-step semi-free-start collision attack which starts from the first step.

One fundamental complexity measure of an MPC protocol is its {\\em round complexity}. Asharov et al. recently constructed the first three-round protocol for general MPC in the CRS model. Here, we show how to achieve this result with only two rounds. We obtain UC security with abort against static malicious adversaries, and fairness if there is an honest majority. Additionally the communication in our protocol is only proportional to the input and output size of the function being evaluated and independent of its circuit size. Our main tool is indistinguishability obfuscation, for which a candidate construction was recently proposed by Garg et al.

The technical tools that we develop in this work also imply virtual black box obfuscation of a new primitive that we call a \\emph{dynamic point function}. This primitive may be of independent interest.

We present a study of the concrete complexity of solving instances of the unique shortest vector problem (uSVP). In particular, we study the complexity of solving the Learning with Errors (LWE) problem by reducing the Bounded-Distance Decoding (BDD) problem to uSVP and attempting to solve such instances using the \'embedding\' approach. We experimentally derive a model for the success of the approach, compare to alternative methods and demonstrate that for the LWE instances considered in this work, reducing to uSVP and solving via embedding compares favorably to other approaches.

The Department of Computer Science at the Florida State University invites applications for multiple tenure-track Assistant Professor positions to begin August 2014. Positions are 9-mo, full-time, tenure-track, and benefits eligible. Outstanding applicants with strengths in the areas of Big Data and Cyber Security are particularly encouraged to apply. Outstanding applicants specializing in other emerging research areas are also welcome to apply. Applicants should hold a PhD in Computer Science or closely related field, and have excellent research and teaching accomplishments or potential. The department offers degrees at the BS, MS, and PhD levels. The department is an NSA/DHS Center of Academic Excellence in Information Assurance Education (CAE-IAE) and Research (CAE-R).

FSU is classified as a Carnegie Research I university. Its primary role is to serve as a center for advanced graduate and professional studies while emphasizing research and providing excellence in undergraduate education.

Screening will begin January 1, 2014 and will continue until the position is filled. Please apply online with curriculum vitae, statements of teaching and research philosophy, and the names of five references, at

http://www.cs.fsu.edu/positions/apply.html

Questions can be e-mailed to Prof. Mike Burmester, Faculty Search Committee Chair, recruitment (at) cs.fsu.edu or to Prof. Robert van Engelen, Department Chair, chair (at) cs.fsu.edu.

The Florida State University is a Public Records Agency and an Equal Opportunity/Access/Affirmative Action employer, committed to diversity in hiring.

I am looking for a few excellent Ph.D. candidates (preferably with proven research capabilities) and post-docs in cryptography (mostly cryptanalysis of symmetric-key primitives), privacy (privacy of biometric databases/schemes) and computer security.

An MSc position in the area of cryptography in the Cryptography and Data Security Group at the Department of Mathematics, Informatics and Mechanics at University of Warsaw is available. The position is supported by the EU FNP Welcome Grant \\\"Cryptographic Protocols Provably-Secure Against Physical Attacks\\\". This project is about the design of cryptographic schemes that are provably-secure against physical attacks, such as side-channel leakages, tampering, or malware intrusion. We offer excellent networking and training opportunities, including participation in international workshops and conferences.

Job profile: All candidates with background in theoretical computer science and mathematics are encouraged to apply and will be carefully considered. Knowledge of Polish is not required, but a good knowledge of English is essential.

Successful candidates can start from 10.2013. Funding is available until 5.2015 (extensions are possible depending on the funding availability)

A PhD position in the area of cryptography in the Cryptography and Data Security Group at the Department of Mathematics, Informatics and Mechanics at University of Warsaw is available. The position is supported by the EU FNP Welcome Grant \\\"Cryptographic Protocols Provably-Secure Against Physical Attacks\\\". This project is about the design of cryptographic schemes that are provably-secure against physical attacks, such as side-channel leakages, tampering, or malware intrusion. We offer excellent networking and training opportunities, including participation in international workshops and conferences.

All candidates with background in theoretical computer science and mathematics are encouraged to apply and will be carefully considered. Knowledge of Polish is not required, but a good knowledge of English is essential.

Successful candidates can start from 10.2013. Funding is available until 5.2015 (extensions are possible depending on the funding availability)

Stipend: 3000 PLN / month

A post-doc position in the area of cryptography in the Cryptography and Data Security Group at the Department of Mathematics, Informatics and Mechanics at University of Warsaw is available. The position is supported by the EU FNP Welcome Grant \\\"Cryptographic Protocols Provably-Secure Against Physical Attacks\\\". This project is about the design of cryptographic schemes that are provably-secure against physical attacks, such as side-channel leakages, tampering, or malware intrusion. We offer excellent networking and training opportunities, including participation in international workshops and conferences.

All candidates with PhD in cryptography are encouraged to apply and will be carefully considered. Knowledge of Polish is not required, but a good knowledge of English is essential.

Successful candidates can start from 10.2013. Funding is available until 5.2015 (extensions are possible depending on the funding availability)

Submission: 23 February 2014
Notification: 13 April 2014
From July 7 to July 9
Location: Wollongong, Australia
More Information: https://ssl.informatics.uow.edu.au/acisp2014/

MASH-1 is modular arithmetic based hash function. It is presented in Part 4 of ISO/IEC 10118

standard for one and a half decade. Cryptographic strength of MASH-1 hash function is based on

factorization problem of an RSA modulus along with redundancy in the input blocks of compression

functions. Despite of this, we are able to introduce two large classes of moduli which allow

practical time collision finding algorithm for MASH-1. In one case even multicollisions of

arbitrary length can be constructed.

We introduce EyeDecrypt, a novel technology for privacy-preserving human-computer interaction. EyeDecrypt allows only authorized users to decipher data shown on a public display, such as an electronic screen or printed material; in the former case, the authorized user can then interact with the system (e.g., by pressing buttons), without revealing the details of the interaction to others who may be watching.

The user views data on a closely-held personal device, such as a pair of smart glasses with a camera and heads-up display, or a smartphone. The decrypted data is displayed as an image overlay on the personal device--a form of augmented reality. The user\'s inputs are protected through randomization.

EyeDecrypt consists of three main components: a visualizable encryption scheme; a dataglyph-based visual encoding scheme for the ciphertexts generated by the encryption scheme; and a randomized input and augmented reality scheme that protects user inputs without harming usability. We describe all aspects of EyeDecrypt, from security definitions, constructions and formal analysis, to implementation details of a prototype developed on a smartphone.

Cryptanalytic time memory tradeoff is a tool for inverting one-way functions, and the rainbow table method, the best-known tradeoff algorithm, is widely used to recover passwords. Even though extensive research has been performed on the rainbow tradeoff, the algorithm actually used in practice differs from the well-studied original algorithm. This work provides a full analysis of the rainbow tradeoff algorithm that is used in practice. Unlike existing works on the rainbow tradeoff, the analysis is done in the external memory model, so that the practically important issue of table loading time is taken into account. As a result, we are able to provide tradeoff parameters that optimize the wall-clock time.

In 2009 and 2011, Toorani and Falahati introduced two variants of the classical Hill Cipher, together with protocols for the exchange of encrypted messages. The designers claim that the new systems overcome the weaknesses of the original Hill Cipher, and are resistant to any ciphertext-only, known-plaintext, chosen-plaintext, or chosen-ciphertext attack. However, we describe a chosen-plaintext attack that easily breaks both Toorani-Falahati Hill Ciphers, and we present computational results that confirm the effectiveness of our attack.

Adaptive security is a strong security notion that captures additional security threats that are not addressed by static corruptions. For instance, it captures scenarios in which the attacker chooses which party to corrupt based on the protocol communication. It further captures real-world scenarios where ``hackers\'\' actively break into computers, possibly while they are executing secure protocols. Studying this setting is interesting from both theoretical and practical points of view. The former is because the theoretical understanding of this setting is not yet profound and important questions are still unresolved; a notable example is the question regarding the feasibility of constant round adaptively secure protocols. From practical viewpoint, generic adaptively secure protocols are far more complicated and less efficient than static protocols.

A primary building block in designing adaptively secure protocols is a non-committing encryption or NCE that implements secure communication channels in the presence of adaptive corruptions. Current NCE constructions require a number of public key operations that grows linearly with the length of the message. Furthermore, general two-party protocols require a number of NCE calls that is linear in the circuit size (or otherwise the protocol is not round efficient). As a result the number of public key operations is inflated and depends on the circuit size as well.

In this paper we study the two-party setting in which at most one of the parties is adaptively corrupted, which we believe is the right security notion in the two-party setting. We study the feasibility of (1) NCE with constant number of public key operations for any message space. (2) Oblivious transfer with constant number of public key operations for any sender\'s input space, and (3) constant round secure computation protocols with a number of NCE calls, and an overall number of public key operations, that are independent of the circuit size. Our study demonstrates that such primitives indeed exist in the presence of single corruptions, while this is not the case for fully adaptive security (where both parties may get corrupted).

We construct an innovative SVP(CVP) solver for ideal lattices in case of any relative extension of number fields L/K of degree n where L is real(contained in R). The solver, by exploiting the relationships between the so-called local and global number fields, reduces solving SVP(CVP) of the input ideal A in field L to solving a set of (at most n) SVP(CVP) of the ideals Ai in field Li with relative degree 1≤ni

The ``certificate authority\'\' model for authenticating public keys of websites has been attacked in recent years, and several proposals have been made to reinforce it. We develop and extend ``certificate transparency\'\', a proposal in this direction, so that it efficiently handles certificate revocation. We show how this extension can be used to build a secure end-to-end email or messaging system using PKI with no requirement to trust certificate authorities, or to rely on complex peer-to-peer key-signing arrangements such as PGP. We believe this finally makes end-to-end encrypted email as usable as encrypted web browsing is today, addressing the concerns of a classic paper explaining the difficulties users face in encrypting emails (``Why Johnny can\'t encrypt\'\', 1999). Underlying these ideas is a new attacker model appropriate for cloud computing, which we call ``malicious-but-cautious\'\'.

At ASIACRYPT 2012, Petit and Quisquater suggested that there may be a subexponential-time index-calculus type algorithm for the Elliptic Curve Discrete Logarithm Problem (ECDLP) in characteristic two fields. This algorithm uses Semaev polynomials and Weil Descent to create a system of polynomial equations that subsequently is to be solved with Gröbner basis methods. Its analysis is based on heuristic assumptions on the performance of Gröbner basis methods in this particular setting. While the subexponential behaviour would manifest itself only far beyond the cryptographically interesting range, this result, if correct, would still be extremely remarkable. We examined some aspects of the work by Petit and Quisquater experimentally.