Here you can see all recent updates to the IACR webpage. These updates are also available:

14
April
2017

Event Calendar
FDTC'17: Fourteenth Workshop on Fault Diagnosis and Tolerance in Cryptography
Taipei, Taiwan, 25 September - 25 September 2015

Event date: 25 September to 25 September 2015

Submission deadline: 9 June 2017

Notification: 6 July 2017

Submission deadline: 9 June 2017

Notification: 6 July 2017

ePrint Report
Lattice-based Revocable Identity-based Encryption with Bounded Decryption Key Exposure Resistance
Atsushi Takayasu, Yohei Watanabe

A revocable identity-based encryption (RIBE) scheme, proposed by Boldyreva et al.\ (CCS'08), provides a revocation functionality for managing a number of users dynamically and efficiently. To capture a realistic scenario, Seo and Emura (PKC'13) introduced an additional important security notion, called {\em decryption key exposure resistance} (DKER), where an adversary is allowed to query short-term decryption keys.Although several RIBE schemes that satisfy DKER have been proposed, all the lattice-based RIBE schemes, e.g., Chen et al.'s scheme (ACISP'12), do not achieve DKER, since they basically do not have {\em the key re-randomization property}, which is considered to be an essential requirement for achieving DKER.In particular, in every existing lattice-based RIBE scheme, an adversary can easily recover plaintexts if the adversary is allowed to issue even a single short-term decryption key query.In this paper, we propose a new lattice-based RIBE scheme secure against exposure of a-priori bounded number of decryption keys (for every identity).We believe that this bounded notion is still meaningful and useful from a practical perspective. Technically, to achieve the bounded security without the key re-randomization property, key updates in our scheme are short vectors whose corresponding syndrome vector changes in each time period. For this approach to work correctly and for the scheme to be secure, {\em cover free families} play a crucial role in our construction.

ePrint Report
Approximate Polynomial Common Divisor Problem Relates to Noisy Multipolynomial Reconstruction
Jun Xu, Santanu Sarkar, Lei Hu

In this paper, we investigate the hardness of the approximate polynomial common divisor problem, which is regarded as a polynomial analogy of the approximate integer common divisor problem. In order to solve this problem, we present a simple method by using the polynomial lattice reduction algorithm and contain complete theoretical analyses. Further, we propose an improved lattice attack to reduce both space and time costs. Moreover, these two attacking methods can be directly applied to solving the noisy multipolynomial reconstruction problem in the field of error-correcting codes. On the basis of the above situations, our improved lattice attack performs fastest.

Known approaches for obfuscating a circuit are only feasible in theory: the complexity polynomially depends on the security parameter and circuit measures, but with too large polynomials and/or holds only with large enough security parameters, which leaves the methods not implementable for almost all applications at a required security level, say 128 bits. In this work, we initiate the task of exploiting ideas from theoretical constructions towards practical obfuscation. The starting concern is: how much do empirical methods help to improve efficiency? We followed the approach of Zimmerman and Applebaum et al.: obfuscating the randomized encodings (RE) with Graded Encoding Scheme (GES) over composites. We gave a new design of RE which is based on a new pseudorandom function and a new garbled circuit from a pseudorandom generator, whose obfuscation only needs GES of degree linear with $n$, the number of input variables. We also developed various techniques that further reduce the degree by a significant constant factor. These resulted a general obfuscator with code size $\left((28\lambda |C|+ \frac{2^c}{c})10n\lambda\right)\mathrm{GES}(\frac{5n}{2c}+6,\lambda)$, where $\mathrm{GES}(\mu,\lambda)$ denotes the size of a single ring element of the Graded Encoding Scheme with multilinearity $\mu$ and security level $\lambda$. Based on our implementation of the required GES with a simplified CLT multilinear map, we may assume $\mathrm{GES}(\mu,\lambda) \approx \mu^2\lambda$. When $n=128$, we may get $\mu=31$; for example, our obfuscated AES will have code size $<10^{14}$ bits, whereas no implementable solution is known prior to this work. Our construction achieves VBB security if our pseudorandom function and pseudorandom generator and application of the CLT multilinear map are all secure.

This paper presents faster inversion-free point addition formulas for the curve y*(1+a*x^2)=c*x*(1+d*y^2). The proposed formulas improve the point doubling operation count record from 6M+5S to 8M and mixed-addition operation count record from 10M to 8M. Both sets of formulas are shown to be 4-way parallel, leading to an effective cost of 2M per either of the group operations.

ePrint Report
Encrypt-Augment-Recover: Computationally Function Private Predicate Encryption in the Public-Key Setting
Sikhar Patranabis, Debdeep Mukhopadhyay

We solve the open problem of constructing \emph{computationally function private} public-key predicate encryption schemes. Existing public-key constructions for predicate encryption satisfy a \emph{statistical} notion of function privacy, that was introduced for equality predicates by Boneh, Raghunathan and Segev in CRYPTO'13, and was generalized for subspace-membership predicates in ASIACRYPT'13. The secret-keys in these constructions are \emph{statistically indistinguishable} from random as long the underlying predicates are sampled from sufficiently unpredictable distributions. The alternative notion of computational function privacy, where the secret-keys are \emph{computationally indistinguishable} from random, has only been concretely realized in the private-key setting, to the best of our knowledge.

\hspace*{5mm}In this paper, we present the first computationally function private constructions for public-key predicate encryption. Our framework for computational function privacy requires that a secret-key corresponding to a predicate sampled from a distribution with min-entropy super logarithmic in the security parameter $\lambda$, is \emph{computationally indistinguishable} from another secret-key corresponding to a uniformly and independently sampled predicate. Within this framework, we develop a novel approach, denoted as \emph{encrypt-augment-recover}, that takes an existing predicate encryption scheme and transforms it into a computationally function private one while retaining its original data privacy guarantees. Our approach leads to public-key constructions for identity-based encryption and inner-product encryption that are fully data private and computationally function private under a family of weaker variants of the DLIN assumption. Our constructions, in fact, satisfy an \emph{enhanced} notion of function privacy, requiring that an adversary learns nothing more than the minimum necessary from a secret-key, even given corresponding ciphertexts with attributes that allow successful decryption.

\hspace*{5mm}In this paper, we present the first computationally function private constructions for public-key predicate encryption. Our framework for computational function privacy requires that a secret-key corresponding to a predicate sampled from a distribution with min-entropy super logarithmic in the security parameter $\lambda$, is \emph{computationally indistinguishable} from another secret-key corresponding to a uniformly and independently sampled predicate. Within this framework, we develop a novel approach, denoted as \emph{encrypt-augment-recover}, that takes an existing predicate encryption scheme and transforms it into a computationally function private one while retaining its original data privacy guarantees. Our approach leads to public-key constructions for identity-based encryption and inner-product encryption that are fully data private and computationally function private under a family of weaker variants of the DLIN assumption. Our constructions, in fact, satisfy an \emph{enhanced} notion of function privacy, requiring that an adversary learns nothing more than the minimum necessary from a secret-key, even given corresponding ciphertexts with attributes that allow successful decryption.

ePrint Report
Key-Aggregate Searchable Encryption with Constant-Size Trapdoors for Fine-Grained Access Control in the Cloud
Sikhar Patranabis, Debdeep Mukhopadhyay

Fine-grained access control, especially in shared data environments such as the cloud, is a common scenario. Suppose a data owner encrypts and stores a collection of $N$ documents in the cloud, and wishes to grant access to a subset $\mathcal{S}$ of these to a data user. The data user must therefore be able to perform search operations only on the subset $\mathcal{S}$ of documents, and nothing else. For example, the user may want to store the documents in separate folders pertaining to work, family, personal etc., and selectively grant search access to one or more folders among different users. This is a commonly encountered in document sharing environments such as Dropbox and Google Drive. Most existing searchable encryption schemes today assume that a user has search permissions over the entire document collection, and are hence not designed explicitly to address such a controlled-search scenario. The only previous work in this direction by Cui et al. possesses inherent security weaknesses that can be exploited to trivially break the privacy of their system.
\noindent In this paper, we provide a novel, efficient and secure solution to this problem by introducing a new public-key searchable encryption primitive referred to as the key-aggregate searchable encryption~(KASE). KASE is secure under well-defined cryptographic assumptions, and requires optimal network communication between the server and the data owners/data users. KASE is the first public key searchable encryption scheme to achieve performance and security at par with the most efficient symmetric key searchable encryption constructions. Additionally, while all existing schemes produce trapdoors that grow linearly with the size of the document collection, KASE produces constant-size trapdoors that are independent of the document collection size. KASE is also efficient and scalable with respect to data updates, making it ideal for use in dynamic cloud-based search applications.

ePrint Report
Solidus: Confidential Distributed Ledger Transactions via PVORM
Ethan Cecchetti, Fan Zhang, Yan Ji, Ahmed Kosba, Ari Juels, Elaine Shi

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.

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.

ePrint Report
Exploring Potential 6LoWPAN Traffic Side Channels
Yan Yan, Elisabeth Oswald, Theo Tryfonas

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.

ePrint Report
Multimodal Indexable Encryption for Mobile Cloud-based Applications (Extended Version)
Bernardo Ferreira, Joaão Leitão, Henrique Domingos

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.

ePrint Report
Post-quantum cryptography---dealing with the fallout of physics success
Daniel J. Bernstein, Tanja Lange

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.

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.

12
April
2017

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*

Job Posting
Researcher positions (postdoc) in Verification of Quantum Cryptography
University of Tartu

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

11
April
2017

ePrint Report
A Generic Approach to Identity-based Sequential Aggregate Signatures: New constructions from 2-level HIBE Schemes
Yanqing Yao, Hua Guo, Zhoujun Li

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.

ePrint Report
Limits on Low-Degree Pseudorandom Generators (Or: Sum-of-Squares Meets Program Obfuscation)
Boaz Barak, Zvika Brakerski, Ilan Komargodski, Pravesh K. Kothari

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.

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.

ePrint Report
Constructing Multidimensional Differential Addition Chains and their Applications
Aaron Hutchinson, Koray Karabina

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.

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.

ePrint Report
Perfectly Secure Message Transmission Scheme against Rational Adversaries
Maiki Fujita, Takeshi Koshiba

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}

10
April
2017

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.

ePrint Report
Faster Gaussian Sampling for Trapdoor Lattices with Arbitrary Modulus
Nicholas Genise, Daniele Micciancio

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.

ePrint Report
Practical Synchronous Byzantine Consensus
Ling Ren, Kartik Nayak, Ittai Abraham, Srinivas Devadas

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.

ePrint Report
Cube Attacks on Non-Blackbox Polynomials Based on Division Property
Yosuke Todo, Takanori Isobe, Yonglin Hao, Willi Meier

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.

ePrint Report
A Zero Knowledge Sumcheck and its Applications
Alessandro Chiesa, Michael A. Forbes, Nicholas Spooner

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.

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.

ePrint Report
Provably Secure NTRUEncrypt over More General Cyclotomic Rings
Yang Yu, Guangwu Xu, Xiaoyun Wang

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.

ePrint Report
Locally Decodable and Updatable Non-Malleable Codes in the Bounded Retrieval Model
Dana Dachman-Soled, Mukul Kulkarni, Aria Shahverdi

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.

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.

ePrint Report
Quantum preimage, 2nd-preimage, and collision resistance of SHA3
Jan Czajkowski, Leon Groot Bruinderink andAndreas Hülsing, Christian Schaffner

SHA3 and its extendable output variant SHAKE belong to the family of sponge functions. In this work, we present formal security arguments for the quantum preimage, $2^{\text{nd}}$-preimage, and collision resistance of any sponge function. We just assume that the internally used transformation behaves like a random transformation.
These are the first formal arguments that sponge functions (incl. SHA3 and SHAKE) are secure in the post-quantum setting.

We even go one step further and prove that sponges are collapsing (Unruh, EUROCRYPT'16). Thereby, we can also derive the applicability of sponge functions for collapse-binding commitments.

In addition to the security arguments, we also present a quantum collision attack against sponges. The complexity of our attack asymptotically matches the proven lower bound up to a square root.

We even go one step further and prove that sponges are collapsing (Unruh, EUROCRYPT'16). Thereby, we can also derive the applicability of sponge functions for collapse-binding commitments.

In addition to the security arguments, we also present a quantum collision attack against sponges. The complexity of our attack asymptotically matches the proven lower bound up to a square root.

9
April
2017

ePrint Report
On the Non-Existence of Blockwise 2-Local PRGs with Applications to Indistinguishability Obfuscation
Alex Lombardi, Vinod Vaikuntanathan

Lin and Tessaro (Eprint 2017/250) recently proposed indistinguishability obfuscation and functional encryption candidates and proved their security based on a standard assumption on bilinear maps and a non-standard assumption on ``Goldreich-like'' pseudorandom generators (PRG). In a nutshell, they require the existence of pseudo-random generators $G:\Sigma^n \rightarrow \{0,1\}^m$ for some $\mathsf{poly}(n)$-size alphabet $\Sigma$ where each output bit depends on at most two input alphabet symbols, and which achieve sufficiently large stretch. We show a polynomial-time attack against such generators.

Our attack uses tools from the literature on two-source extractors (Chor and Goldreich, SICOMP 1988) and efficient refutation of 2-CSPs over large alphabets (Allen, O'Donnell and Witmer, FOCS 2015). Finally, we propose new ways to instantiate the Lin-Tessaro construction that do not immediately fall to our attacks. While we cannot say with any confidence that these modifications are secure, they certainly deserve further cryptanalysis.

Our attack uses tools from the literature on two-source extractors (Chor and Goldreich, SICOMP 1988) and efficient refutation of 2-CSPs over large alphabets (Allen, O'Donnell and Witmer, FOCS 2015). Finally, we propose new ways to instantiate the Lin-Tessaro construction that do not immediately fall to our attacks. While we cannot say with any confidence that these modifications are secure, they certainly deserve further cryptanalysis.

7
April
2017

Event Calendar
CARDIS 2017: 16th Smart Card Research and Advanced Application Conference
Lugano, Switzerland, 13 November - 15 November 2017

Event date: 13 November to 15 November 2017

Submission deadline: 21 July 2017

Notification: 12 September 2017

Submission deadline: 21 July 2017

Notification: 12 September 2017