International Association
for Cryptologic Research

Blockchains and more general distributed ledgers are becoming increasingly popular as efficient, reliable, and persistent records of data and transactions. Unfortunately, they ensure reliability and correctness by making all data public, raising confidentiality concerns that eliminate many potential uses.

In this paper we present Solidus, a protocol for confidential transactions on public blockchains, such as those required for asset transfers with on-chain settlement. Solidus operates in a framework based on real-world financial institutions: a modest number of banks each maintain a large number of user accounts. Within this framework, Solidus hides both transaction values and the transaction graph (i.e., the identities of transacting entities) while maintaining the public verifiability that makes blockchains so appealing. To achieve strong confidentiality of this kind, we introduce the concept of a Publicly-Verifiable Oblivious RAM Machine (PVORM). We present a set of formal security definitions for both PVORM and Solidus and show that our constructions are secure. Finally, we implement Solidus and present a set of benchmarks indicating that the system is efficient in practice.

The Internet of Things (IoT) has become a reality: small connected devices feature in everyday objects including childrens' toys, TVs, fridges, heating control units, etc. Supply chains feature sensors throughout, and significant investments go into researching next-generation healthcare, where sensors monitor wellbeing. A future in which sensors and other (small) devices interact to create sophisticated applications seems just around the corner. All of these applications have a fundamental need for security and privacy and thus cryptography is deployed as part of an attempt to secure them. In this paper we explore a particular type of flaw, namely side channel information, on the protocol level that can exist despite the use of cryptography. Our research investigates the potential for utilising packet length and timing information (both are easily obtained) to extract interesting information from a system. We find that using these side channels we can distinguish between devices, different programs running on the same device including which sensor is accessed. We also find it is possible to distinguish between different types of ICMP messages despite the use of encryption. Based on our findings, we provide a set of recommendations to efficiently mitigate these side channels in the IoT context.

In this paper we propose MIE, a Multimodal Indexable Encryption framework that for the first time allows mobile applications to securely outsource the storage and search of their multimodal data (i.e. data containing multiple media formats) to public clouds with privacy guarantees. MIE is designed as a distributed framework architecture, leveraging on shared cloud repositories that can be accessed simultaneously by multiple users. At its core MIE relies on Distance Preserving Encodings (DPE), a novel family of encoding algorithms with cryptographic properties that we also propose. By applying DPE to multimodal data features, MIE enables high-cost clustering and indexing operations to be handled by cloud servers in a privacy-preserving way. Experiments show that MIE achieves better performance and scalability when compared with the state of art, with measurable impact on mobile resources and battery life.

Cryptography is essential for the security of Internet communication, cars, and implanted medical devices. However, many commonly used cryptosystems will be completely broken once big quantum computers exist.

Post-quantum cryptography is cryptography under the assumption that the attacker has a large quantum computer; post-quantum cryptosystems strive to remain secure even in this scenario. This relatively young research area has seen some successes in identifying mathematical operations for which quantum algorithms offer little speedup, and then building cryptographic systems around those. The central challenge in post-quantum cryptography is to meet demands for cryptographic usability and flexibility without sacrificing trust.

Applications are invited in the prescribed format to recruit one JRF for a period of 3 Years (Initially for 1 year) for the project \"Design and development of an Automatic Kinship Verification system for Indian faces with possible integration of AADHAR Database\"

Closing date for applications: 26 April 2017

Contact: Dr. T. Meenpal

Assistant Professor,

Electronics & Telecommunication Engineering

Department

NIT Raipur,Chhattisgarh- 492010

Email: tmeenpal.etc (at) nitrr.ac.in

More information: http://www.nitrr.ac.in/downloads/recruitment/recruitment2017/project_fellow/JRF_EnTC_advertisement_ETC_10042017.pdf

This is an urgent call for interested applicants. A funded Ph.D. student position is available starting August 2017 to work on different aspects of Cryptographic Engineering in the CSE department at USF.

USF is an R1 university and among the leading institutions in Florida. We are looking for motivated, talented, and hardworking applicants who have background and are interested in working on different aspects of Cryptographic Engineering with emphasis on:

- Cryptographic hardware systems

- Side-channel attacks, particularly fault and power analysis attacks

The required expertise includes:

- Masters (or Bachelors with outstanding background) in Computer Engineering or Electrical Engineering

- Solid background in digital design, VLSI, computer arithmetic, and ASIC/FPGA implementations

- Solid HDL expertise

- Outstanding English (if English tests are taken) to be eligible for department funding

- Motivation to work beyond the expectations from an average Ph.D. student and publish in top tier venues

Please closely observe the admission requirement details here before emailing:

http://www.usf.edu/engineering/cse/graduate/phd-program.aspx

Please send me your updated CV (including list of publications, language test marks, and references), transcripts for B.Sc. (and M.Sc.), and a statement of interest at usfcrypto2017 (at) gmail.com as soon as possible.

NOTE: At this time, I consider only the applicants who have already taken TOEFL/IELTS and GRE exams with excellent marks. The successful candidate will be asked to apply formally very soon to the USF CSE department, so all the material has to be already ready.

Closing date for applications: 20 April 2017

The position is connected to the project “Construction of optimal Boolen functions”. The prime objectives of this project are Boolean functions with optimal resistance to various cryptographic attacks (differential, linear, algebraic et al.) and their applications in discrete mathematics (such as commutative semifields, o-polynomials, difference sets, dual hyperovals, regular graphs, m-sequences, codes et al.).

For further information and for application for the position see the webpage:

https://www.jobbnorge.no/en/available-jobs/job/137029/phd-position-in-boolean-functions

Closing date for applications: 15 May 2017

Contact: Dr. Lilya Budaghyan lilya.budaghyan (at) uib.no

At the Quantum Cryptography Group, University of Tartu, we have two open postdoc positions on Verification of Quantum Cryptography.

We are starting a project in which we will develop methods for the verification of proofs in quantum cryptography. Similar to what the EasyCrypt tool does in classical cryptography. The scope of the project covers everything from the logical foundations, through the development of tools, to the verification of real quantum protocols.

The ideal candidate would have experience in:

• Semantics
• Theorem proving
• Verification of classical cryptography
• Quantum cryptography
• Quantum computation / communication

Of course, expertise in all those areas is very rare, so candidates who are strong in some of those areas and are interested in the others are encouraged to apply!

Please contact Dominique Unruh if you have more questions about the project, the required background, Estonia, the position itself, or the application process.

The salary range is 30000-36000 Euro per year (depending on experience), which is highly competitive in Estonia due to low costs of living and low income tax rate (20%), pension contributions and health insurance are covered by the employer.

The position is for three years, September 1, 2017 till August 31, 2020. The starting date and duration can be negotiated (in both directions).

For application instructions, see the link below.

Closing date for applications: 1 June 2017

Contact: Dominique Unruh
Professor of Information Security
Department of Computer Science
University of Tartu
unruh (at) ut.ee

More information: http://crypto.cs.ut.ee/Main/PostdocInVerificationOfQuantumCryptography

Identity-based sequential aggregate signature (IBSAS) schemes are usually applied to secure network routing and sensor networks, since they allow multiple signers to sequentially produce a short signature of different messages to reduce bandwidth overhead and storage space for signatures, and allow signers to attest to these messages as well as the order in which they signed using their identities. In CCS’07, Boldyreva et al. introduced this concept and constructed the first IBSAS scheme in the random oracle model. After that, a couple of IBSAS schemes are proposed and proved. Unfortunately, none of them is constructed based on a standard computational problem and secure in the standard model (i.e., without random oracles). How to construct this kind of scheme is still an open problem. In this paper, we propose a generic construction of IBSAS schemes by employing 2-level Hierarchical Identity-based Encryption Schemes, and then prove its security in the security model proposed by Boldyreva et al. in CCS'07. Afterwards, we instantiate the generic construction to obtain a concrete IBSAS scheme secure under the Computational Diffie-Hellman (CDH) assumption in the standard model, thus solving the above open problem. An extra fruit of our generic construction is that it can be used to construct the first lattice-based IBSAS scheme, which is secure in the random oracle model. Finally, we show the performance comparisons between our schemes and previous ones.

We prove that for every function $G\colon\{0,1\}^n \rightarrow \mathbb{R}^m$, if every output of $G$ is a polynomial (over $\mathbb{R}$) of degree at most $d$ of at most $s$ monomials and $m > \widetilde{O}(sn^{\lceil d/2 \rceil})$, then there is a polynomial time algorithm that can distinguish a vector of the form $z=G(x)$ from a vector $z$ where each coordinate is sampled independently according to the marginal distributions of the coordinates of $G$ (assuming the latter satisfy some non-degeneracy condition).

In particular, if $G\colon\{0,1\}^n \rightarrow \{0,1\}^m$ and $m$ is as above, then $G$ cannot be a pseudorandom generator. Our algorithm is based on semidefinite programming and in particular the sum of squares (SOS) hierarchy.

As a corollary, we refute some conjectures recently made in the cryptographic literature. This includes refuting the assumptions underlying Lin and Tessaro's recently proposed candidate construction for indistinguishability obfuscation from bilinear maps, by showing that any block-wise 2-local PRG with block size $b$ cannot go beyond $m \approx 2^{2b}\cdot n$. We give an even stronger bound of $m \approx 2^b n$ on the output length of random block-wise 2-local PRGs. We also show that a generalized notion of generators runs into similar barriers.

We complement our algorithm by presenting a class of candidate generators with block-wise locality $3$ and constant block size, that resists both Gaussian elimination and SOS algorithms whenever $m = n^{1.5-\varepsilon}$. This class is extremely easy to describe: Let $\mathbb{G}$ be any simple non-abelian group, and interpret the blocks of $x$ as elements in $\mathbb{G}$, then each output of the generator is of the form $x_i \ast x_j \ast x_k$, where $i,j,k$ are random and "$\ast$" is the group operation.

We propose new algorithms for constructing multidimensional differential addition chains and for performing multidimensional scalar point multiplication based on these chains. Our algorithms work in any dimension and offer some key efficiency and security features. In particular, our scalar point multiplication algorithm is uniform, it has high potential for constant time implementation, and it can be parallelized. It also allows trading speed for precomputation cost and storage requirements. These key features and our theoretical estimates indicate that this new algorithm may offer significant performance advantages over the existing point multiplication algorithms in practice. We also report some experimental results and verify some of our theoretical findings.

The Learning Parity with Noise (LPN) problem has found many applications in cryptography due to its conjectured post-quantum hardness and simple algebraic structure. Over the years, constructions of different public-key primitives were proposed from LPN, but most of them are based on the LPN assumption with _low noise_ rate rather than _constant noise_ rate. A recent breakthrough was made by Yu and Zhang (Crypto'16), who constructed the first Public-Key Encryption (PKE) from constant-noise LPN. However, the problem of designing a PKE with _Key-Dependent Message_ (KDM) security from constant-noise LPN is still open.

In this paper, we present the first PKE with KDM-security based on constant-noise LPN, where the number of users is predefined. The technical tool is two types of _multi-fold LPN on squared-log entropy_, one having _independent secrets_ and the other _independent sample subspaces_. We establish the hardness of the multi-fold LPN variants on constant-noise LPN. Two squared-logarithmic entropy sources for multi-fold LPN are carefully chosen, so that our PKE is able to achieve correctness and KDM-security simultaneously.

Secure Message Transmission (SMT) is a two-party cryptographic scheme by which a sender securely and reliably sends messages to a receiver using $n$ channels. Suppose that an adversary corrupts at most $t$ out of $n$ channels and makes eavesdropping or tampering over the corrupted channels. It is known that if $t < n/2$ then the perfect SMT (PSMT) in the information-theoretic sense is achievable and if $t\ge n/2$ then no PSMT scheme is possible to construct. If we are allowed to use a public channel in addition to the normal channels, we can achieve the almost reliable SMT (ARSMT), which admits transmission failures of small probability, against $t < n$ corruptions. In the standard setting in cryptography, the participants are classified into honest ones and corrupted ones: every honest participant follows the protocol but corrupted ones are controlled by the adversary and behave maliciously. As a real setting, the notion of rationality in the game theory is often incorporated into cryptography. In this paper, we first consider ``rational adversary'' who behaves according to his own preference in SMT. We show that it is possible to achieve PSMT even against any $t < n$ corruptions under some reasonable settings for rational adversaries. \end{abstract}

The proceedings for Eurocrypt 2017 are now available via SpringerLink. Through our agreement with Springer, IACR members can access these proceedings for free by logging into this access page. The conference will be held Apr 30 - May 4 in Paris.

We present improved algorithms for gaussian preimage sampling using the lattice trapdoors of (Micciancio and Peikert, CRYPTO 2012). The MP12 work only offered a highly optimized algorithm for the on-line stage of the computation in the special case when the lattice modulus $q$ is a power of two. For arbitrary modulus $q$, the MP12 preimage sampling procedure resorted to general lattice algorithms with complexity cubic in the bitsize of the modulus (or quadratic, but with substantial preprocessing and storage overheads.) Our new preimage sampling algorithm (for any modulus $q$) achieves linear complexity, and has very modest storage requirements. As an additional contribution, we give a new off-line quasi-linear time perturbation sampling algorithm, with performance similar to the (expected) running time of an efficient method proposed by (Ducas and Nguyen, Asiacrypt 2012) for power-of-two cyclotomics, but without the (matrix factorization) preprocessing and (lattice rounding) postprocessing required by that algorithm. All our algorithms are fairly simple, with small hidden constants, and offer a practical alternative to use the MP12 trapdoor lattices in a broad range of cryptographic applications.

We present new protocols for Byzantine state machine replication and Byzantine agreement in the synchronous and authenticated setting. The celebrated PBFT state machine replication protocol tolerates $f$ Byzantine faults in an asynchronous setting using $3f+1$ replicas, and has since been studied or deployed by numerous works. In this work, we improve the Byzantine fault tolerance to $n=2f+1$ by utilizing the synchrony assumption. The key challenge is to ensure a quorum intersection at one \emph{honest} replica. Our solution is to rely on the synchrony assumption to form a \emph{post-commit} quorum of size $2f+1$, which intersects at $f+1$ replicas with any \emph{pre-commit} quorums of size $f+1$. Our protocol also solves synchronous authenticated Byzantine agreement in fewer rounds than the best existing solution (Katz and Koo, 2006). A challenge in this direction is to handle non-simultaneous termination, which we solve by introducing a notion of \emph{virtual} participation after termination. Our protocols may be applied to build practical synchronous Byzantine fault tolerant systems and improve cryptographic protocols such as secure multiparty computation and cryptocurrencies when synchrony can be assumed.

The cube attack is one of powerful cryptanalytic techniques and is especially powerful against stream ciphers. Since we need to analyze the complicated structure of a stream cipher in the cube attack, the cube attack basically analyzes it by regarding as a blackbox. Therefore, the cube attack is an experimental attack, and we cannot evaluate the security when the size of cube exceeds an experimental range, e.g., 40. In this paper, we propose cube attacks on non-blackbox polynomials. Our attacks are developed by using the division property, which is recently applied to various block ciphers. The clear advantage is that we can exploit large number of cube size because it never regards the cipher as a blackbox. We apply the new cube attack to Trivium, Grain128a, and ACORN. As a result, the secret keys of 832-round Trivium, 183-round Grain128a, and 704-round ACORN are recovered. These attacks are the current best key-recovery attack.

Many seminal results in Interactive Proofs (IPs) use algebraic techniques based on low-degree polynomials, the study of which is pervasive in theoretical computer science. Unfortunately, known methods for endowing such proofs with zero knowledge guarantees do not retain this rich algebraic structure.

In this work, we develop algebraic techniques for obtaining zero knowledge variants of proof protocols in a way that leverages and preserves their algebraic structure. Our constructions achieve unconditional (perfect) zero knowledge in the Interactive Probabilistically Checkable Proof (IPCP) model of Kalai and Raz [KR08] (the prover first sends a PCP oracle, then the prover and verifier engage in an Interactive Proof in which the verifier may query the PCP).

Our main result is a zero knowledge variant of the sumcheck protocol [LFKN92] in the IPCP model. The sumcheck protocol is a key building block in many IPs, including the protocol for polynomial-space computation due to Shamir [Sha92], and the protocol for parallel computation due to Goldwasser, Kalai, and Rothblum [GKR15]. A core component of our result is an algebraic commitment scheme, whose hiding property is guaranteed by algebraic query complexity lower bounds [AW09,JKRS09]. This commitment scheme can then be used to considerably strengthen our previous work [BCFGRS16] that gives a sumcheck protocol with much weaker zero knowledge guarantees, itself using algebraic techniques based on algorithms for polynomial identity testing [RS05,BW04].

We demonstrate the applicability of our techniques by deriving zero knowledge variants of well-known protocols based on algebraic techniques. First, we construct zero knowledge IPCPs for NEXP starting with the Multi-prover Interactive Proofs of Babai, Fortnow, and Lund [BFL91]. This result is a direct application of our zero knowledge sumcheck and our algebraic commitment scheme, augmented with the use of `randomized' low-degree extensions.

We also construct protocols in a more restricted model where the prover and verifier engage in a standard Interactive Proof with oracle access to a uniformly random low-degree polynomial (soundness holds with respect to any oracle). In this setting we achieve zero knowledge variants of the protocols of Shamir and of Goldwasser, Kalai, and Rothblum.

NTRUEncrypt is a fast and standardized lattice-based public key encryption scheme, but it lacks a solid security guarantee. In 2011, Stehl\'{e} and Steinfeld first proposed a provably secure variant of NTRUEncrypt, denoted by pNE, over power-of-2 cyclotomic rings. The IND-CPA security of pNE is based on the quantum worst-case hardness of classical problems over ideal lattices. Recently, Yu, Xu and Wang constructed pNE variants over prime cyclotomic rings. In this paper, we further extend the previous results to the case of general prime power cyclotomic rings, which allows a more flexible choice of parameters. We discover a potential trade-off between the power exponent of the ring order and the minimal magnitude of modulus. Moreover, we discuss the case of pNE over general rings assuming the hardness of corresponding RLWE, and propose three attributes of the ring mattering to parameter selection.

In a recent result, Dachman-Soled et al.(TCC '15) proposed a new notion called locally decodable and updatable non-malleable codes, which informally, provides the security guarantees of a non-malleable code while also allowing for efficient random access. They also considered locally decodable and updatable non-malleable codes that are leakage-resilient, allowing for adversaries who continually leak information in addition to tampering.

The bounded retrieval model (BRM) (cf. [Alwen et al., CRYPTO '09] and [Alwen et al., EUROCRYPT '10]) has been studied extensively in the setting of leakage resilience for cryptographic primitives. This threat model assumes that an attacker can learn information about the secret key, subject only to the constraint that the overall amount of leaked information is upper bounded by some value. The goal is then to construct cryptosystems whose secret key length grows with the amount of leakage, but whose runtime (assuming random access to the secret key) is independent of the leakage amount.

In this work, we combine the above two notions and construct locally decodable and updatable non-malleable codes in the split-state model, that are secure against bounded retrieval adversaries. Specifically, given leakage parameter l, we show how to construct an efficient, 3-split-state, locally decodable and updatable code (with CRS) that is secure against one-time leakage of any polynomial time, 3-split-state leakage function whose output length is at most l, and one-time tampering via any polynomial-time 3-split-state tampering function. The locality we achieve is polylogarithmic in the security parameter.