International Association
for Cryptologic Research

The possibility of basing the security of cryptographic objects on the (minimal) assumption that $\\comp{NP} \\nsubseteq \\comp{BPP}$ is at the very heart of complexity-theoretic cryptography. Most known results along these lines are negative, showing that assuming widely believed complexity-theoretic conjectures, there are no reductions from an $\\comp{NP}$-hard problem to the task of breaking certain cryptographic schemes. We make progress along this line of inquiry by showing that the security of single-server single-round private information retrieval schemes cannot be based on $\\comp{NP}$-hardness, unless the polynomial hierarchy collapses. Our main technical contribution is in showing how to break the security of a PIR protocol given an $\\comp{SZK}$ oracle. Our result is tight in terms of both the correctness and the privacy parameter of the PIR scheme.

The Computer Science and Engineering (CSE) and Electrical and Computer Engineering (ECE) Departments at the University of Connecticut invite applications for two tenure-track faculty positions, one at the assistant, associate or full professor level and the other at the assistant professor level. Both positions have an expected start date of August 23, 2016. The research specialties of interest are Cryptography, Computer Security, and Security Engineering.

For full job description please visit our website at http://www.cse.uconn.edu/current-job-listings/. UConn is an EEO/AA Employer.

We are looking for postdoc fellow with expertise on Cryptographic Protocols (UC-security, multi-party computations), Information Security, Cloud Computing and Big Data Analytics. The candidates should have PhD in Cryptography and Information Security or Cloud Computing or Database Engineering with track record of strong R&D capability.

Interested applicants are advised to email the following documents to

Dr. Huafei Zhu (zhuhf (at) zucc.edu.cn)

CV

Three reference letters

Personal statement outlining your interest in the position

In 2014, Peikert described the first practical lattice-based key exchange that is provably secure and provides perfect forward security. However, his presentation lacks concrete proposals for parameters. We aim to provide a clear description of how the algorithm can be implemented along with some analysis for potential parameters.

Previously in 2015, Singh considered the simpler case, as chosen by Bos, Costello, Naehrig and Steblia in 2014, of cyclotomic rings with power-of-two degree. In this work we focus on the case of cyclotomic rings with degree p-1 for prime p. This allows for a greater degree of flexibility in choosing lattice dimension, which determines the security level and efficiency of the scheme. We describe the necessary arithmetic setup and then present Peikert\'s Diffie-Hellman-like key exchange along with security, correctness and implementation analysis.

We give an alternative approach and improvements on bounds developed by Hodges, Petit and Schlather, and Petit and Quisquater concerning the first fall degree of algebraic equations. In particular, we improve on the first fall degree bound of polynomial systems that arise from a Weil descent along Semaev\'s summation polynomials.

A theorem by Galbraith, Malone-Lee, and Smart (GMLS) from 2002 showed that, for Schnorr signatures, single-user security tightly implies multi-user security. Recently, Bernstein pointed to an error in the above theorem and promoted a key-prefixing variant of Schnorr signatures for which he proved a tight implication from single to multi-user security. Even worse, he identified an \"apparently insurmountable obstacle to the claimed [GMLS] theorem\".

This paper shows that, without key prefixing, single-user security of Schnorr signatures tightly implies multi-user security of the same scheme.

Lattice reduction algorithms are notoriously hard to predict, both in terms of running time and output quality, which poses a major problem for cryptanalysis. While easy to analyze algorithms with good worst-case behavior exist, previous experimental evidence suggests that they are outperformed in practice by algorithms whose behavior is still not well understood, despite more than 30 years of intensive research. This has lead to a situation where a rather complex simulation procedure seems to be the most common way to predict the result of their application to an instance. In this work we present new algorithmic ideas towards bridging this gap between theory and practice. We report on an extensive experimental study of several lattice reduction algorithms, both novel and from the literature, that shows that theoretical algorithms are in fact surprisingly practical and competitive. In light of our results we come to the conclusion that in order to predict lattice reduction, simulation is superfluous and can be replaced by a closed formula using weaker assumptions.

One key technique to achieving this goal is a novel algorithm to solve the Shortest Vector Problem (SVP) in the dual without computing the dual basis. Our algorithm enjoys the same practical efficiency as the corresponding primal algorithm and can be easily added to an existing implementation of it.

Due to the demand for low-cost cryptosystems from industry, there spring up a lot of lightweight block ciphers which are excellent for some different implementation features. An innovative design is the block cipher PRINCE. To meet the requirement for low-latency and instantaneously encryption, NXP Semiconductors and its academic partners cooperate and design the low-latency block cipher PRINCE. Another good example is the block cipher LED which is very compact in hardware, and whose designers also aim to maintain a reasonable software performance. In this paper, we demonstrate how to achieve high software performance of these two ciphers on the AVR 8-bit microcontrollers using bitslice technique. Our bitsliced implementations speed up the execution of these two ciphers several times with less memory usage than previous work. In addition to these two nibble-oriented ciphers, we also evaluate the software performance of a newly proposed lightweight block cipher RECTANGLE, whose design takes bitslicing into consider. Our results show that RECTANGLE has very high performance ranks among the existing block ciphers in the real-world usage scenarios on 8-bit microcontrollers.

In 2010 Hao, Ryan and Zielinski proposed a simple decentralized e- voting protocol that only requires 2 rounds of communication. Thus, for k elections their protocol needs 2k rounds of communication. Observing that the first round of their protocol is aimed to establish the public-keys of the voters, we propose an extension of the protocol as a non-interactive e-voting scheme in the public-key setting (NIVS) in which the voters, after having published their public-keys, can use the corresponding secret-keys to participate in an arbitrary number of one-round elections. We first construct a NIVS with a standard tally function where the number of votes for each candidate is counted. Further, we present constructions for two alternative types of elections. Specifically in the first type (dead or alive elections) the tally shows if at least one voter cast a vote for the candidate. In the second one (elections by unanimity), the tally shows if all voters cast a vote for the candidate. Our constructions are based on bilinear maps of prime order. As definitional contribution we provide formal computational definitions for privacy and verifiability of NIVSs. We conclude by showing intriguing relations between our results, secure computation, electronic exams and conference management systems.

Submission: 11 December 2015
Notification: 8 February 2016
From April 14 to April 15
Location: Graz, Austria
More Information: https://www.cosade.org/index.html

The School of Electrical Engineering and Computer Science is seeking a Lecturer in Cryptography. The successful candidate will have a strong theoretical background and familiarity with modern developments in mathematical cryptography, as well as demonstrated capacity for creative research. Women, Indigenous Australians and Torres Strait Islander people are strongly encouraged to apply. Open to Australian and International applicants.

Position Purpose: The successful candidate will teach and coordinate at both the undergraduate and postgraduate levels. This position will work closely with an ARC Future Fellow in the area of cryptographic protocol design, with a focus on lightweight, useable and human-driven cryptography. A strong theoretical background and familiarity with modern developments in mathematical cryptography, as well as demonstrated capacity for creative research are essential.

Recently there has been much interest in performing database queries over encrypted data to enable functionality while protecting sensitive data. One particularly efficient mechanism for executing such queries is order-preserving encryption/encoding (OPE) which results in ciphertexts that preserve the relative order of the underlying plaintexts thus allowing range and comparison queries to be performed directly over the ciphertext. In particular, Popa et al. (S&P 2013) recently gave the first interactive, mutable order-preserving encoding scheme achieving the strongest possible security for OPE while allowing for efficient range queries. However, this construction requires the bulk of the work to be performed when inserting data into the database, something that is not desirable for the high insertion rates of today\'s big data databases.

In this paper, we propose an alternative approach to range queries over encrypted data that is optimized for efficient insert while still maintaining search functionality. Specifically, we propose a new primitive called partial order preserving encoding (POPE) that achieves ideal OPE security while providing extremely fast insertion and efficient (amortized) search. Our scheme is better suited to today\'s insert-heavy database scenarios. For example, with about one million insertions and one thousand range queries, our POPE scheme is 20X faster than the scheme by Popa et al.

We also propose a new form of frequency-hiding security for POPE, as recently studied by Kerschbaum (CCS 2015) for OPE, and show how to extend our scheme to satisfy it.

Recently, Goyal (STOC\'13) proposed a new non-black box simulation techniques for fully concurrent zero knowledge with straight-line simulation.

Unfortunately, so far this technique is limited to the setting of concurrent zero knowledge.

The goal of this paper is to study what can be achieved in the setting of concurrent secure computation using non-black box simulation techniques, building upon the work of Goyal.

The main contribution of our work is a secure computation protocol in the fully concurrent setting

with a straight-line simulator, that allows us to achieve several new results:

\\begin{itemize}

\\item We give first positive results for concurrent blind signatures and verifiable random functions in the plain model \\emph{as per the ideal/real world security definition}. Our positive result is somewhat surprising in light of the impossibility result of Lindell (STOC\'03) for black-box simulation. We circumvent this impossibility using non-black box simulation. This gives us a quite natural example of a functionality in concurrent setting which is impossible to realize using black-box simulation but can be securely realized using non-black-box simulation.

\\item Moreover, we expand the class of realizable functionalities in the concurrent setting. Our main theorem is a positive result for concurrent secure computation as long as the ideal world satisfies the \\emph{bounded pseudo-entropy condition} (BPC) of Goyal (FOCS\'12). The BPC requires that in the ideal world experiment, the total amount of information learnt by the adversary (via calls to the ideal functionality) should have ``bounded pseudoentropy\".

\\item We also improve the round complexity of protocols in the single-input setting of Goyal (FOCS\'12) both qualitatively and quantitatively. In Goyal\'s work, the number of rounds depended on the length of honest party inputs. In our protocol, the round complexity depends only on the security parameter, and is completely independent of the length of the honest party inputs.

\\end{itemize}

Our results are based on a non-black-box simulation technique using a new language (which allows the simulator to commit to an Oracle program that can access information with bounded pseudoentropy), and a simulation-sound version of the concurrent zero-knowledge protocol of Goyal (STOC\'13). We assume the existence of collision resistant hash functions and constant round semi-honest oblivious transfer.

Instead of simply using two-dimensional $User \\times Item$ features, advanced recommender systems rely on more additional dimensions (e.g. time, location, social network) in order to provide better recommendation services. In the first part of this paper, we will survey a variety of dimension features and show how they are integrated into the recommendation process. When the service providers collect more and more personal information, it brings great privacy concerns to the public. On another side, the service providers could also suffer from attacks launched by malicious users who want to bias the recommendations. In the second part of this paper, we will survey attacks from and against recommender service providers, and existing solutions.

In this paper an efficient high-speed architecture of Gaussian normal basis multiplier over binary finite field GF(2m) is presented. The structure is constructed by using regular modules for computation of exponentiation by powers of 2 and low-cost blocks for multiplication by normal elements of the binary field. Since the exponents are powers of 2, the modules are implemented by some simple cyclic shifts in the normal basis representation. As a result, the multiplier has a simple structure with a low critical path delay. The efficiency of the proposed structure is studied in terms of area and time complexity by using its implementation on Vertix-4 FPGA family and also its ASIC design in 180nm CMOS technology. Comparison results with other structures of the Gaussian normal basis multiplier verify that the proposed architecture has better performance in terms of speed and hardware utilization.

Besides the opportunities o ered by the all-embracing Internet of Things (IoT) technology, it also poses a tremendous threat to the privacy of the carriers of these devices. In this work, we build upon the idea of an RFID-based IoT realized by means of standardized and well-established Internet protocols. In particular, we demonstrate how the Internet Protocol Security protocol suite (IPsec) can be applied in a privacy-aware manner. Therefore, we introduce a privacy-aware mutual authentication protocol compatible with restrictions imposed by the IPsec standard and analyze its privacy and security properties. In order do so, we revisit and adapt the RFID privacy model (HPVP) of Hermans et al. (ESORICS\'11). With this work, we show that privacy in the IoT can be achieved without relying on proprietary protocols and on the basis of existing Internet standards.

Physical unclonable functions (PUF) are a promising approach in design for trust and security. A PUF derives a unique identifier for different similar dies using some of their physical characteristics, so it can be used to authenticate chips and to fight against counterfeiting and theft of devices. The transient effect ring oscillator (TERO) PUF is based on the extraction of the entropy of the process variations by comparison between TERO cells characteristics. This TERO cells need to be carefully designed in order to construct a PUF. This task need to be done with precision especially in the size of used gates and in the delays of all connections inside the element which is particularly challenging in FPGA. This paper presents the design of TERO cells in two FPGA families: Xilinx Spartan 6 and Altera Cyclone V. In addition, the result of the characterization of the TERO-PUF are compared for the two technologies.

One way to guarantee security against malicious voting servers is to use NIZK shuffle arguments. Up to now, only two NIZK shuffle arguments in the CRS model have been proposed. Both arguments are relatively inefficient compared to known random oracle based arguments. We propose a new, more efficient, shuffle argument in the CRS model. Importantly, its online prover\'s computational complexity is dominated by only two $(n + 1)$-wide multi-exponentiations, where $n$ is the number of ciphertexts. Compared to the previously fastest argument by Lipmaa and Zhang, it satisfies a stronger notion of soundness.

Multi-input functional encryption (MIFE) was introduced by Goldwasser \\emph{et al.} (EUROCRYPT 2014) as a compelling extension of functional encryption. In MIFE, a receiver is able to compute a joint function of multiple, independently encrypted plaintexts. Goldwasser \\emph{et al.} (EUROCRYPT 2014) show various applications of MIFE to running SQL queries over encrypted databases, computing over encrypted data streams, etc.

The previous constructions of MIFE due to Goldwasser \\emph{et al.} (EUROCRYPT 2014) based on indistinguishability obfuscation had a major shortcoming: it could only support encrypting an \\emph{a priori bounded} number of message. Once that bound is exceeded, security is no longer guaranteed to hold. In addition, it could only support \\emph{selective-security}, meaning that the challenge messages and the set of ``corrupted\'\' encryption keys had to be declared by the adversary up-front.

In this work, we show how to remove these restrictions by relying instead on \\emph{sub-exponentially secure} indistinguishability obfuscation. This is done by carefully adapting an alternative MIFE scheme of Goldwasser \\emph{et al.} that previously overcame these shortcomings (except for selective security wrt.~the set of ``corrupted\'\' encryption keys) by relying instead on differing-inputs obfuscation, which is now seen as an implausible assumption. Our techniques are rather generic, and we hope they are useful in converting other constructions using differing-inputs obfuscation to ones using sub-exponentially secure indistinguishability obfuscation instead.

In this article we present how we can use fast F_{p²} multiplication to speed-up arithmetic on elliptic curves. We use parallel computations for multiplication in F_{p²} which is not much slower than multiplication in F_{p}. We show two applications of this method.

In the first we show that using twisted Edwards curves over F_{p²} with fast computable endomorphism (GLV-GLS method) may be nowadays on of the fastest (or even the fastest) solution in hardware applications.

In the second we show how we can speed-up point scalar multiplication on NIST P-224 and NIST P-256 curves. We use field extension (F_{p²}) to find isomorphic to these curves twisted Hessian curves over F_{p²}. Our solution is faster than classic solutions up to 28.5% for NIST P-256 and up to 27.2% for NIST P-224 if we consider solution invulnerable for side channel attacks. We can also use different formula for point doubling and points addition and then our solution is faster up to 21.4% for NIST P-256 and up to 19.9% for NIST P-224 comparing to classic solutions.