International Association for Cryptologic Research

International Association
for Cryptologic Research

IACR News

If you have a news item you wish to distribute, they should be sent to the communications secretary. See also the events database for conference announcements.

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

email icon
via email
RSS symbol icon
via RSS feed

30 April 2018

Justin Holmgren, Alex Lombardi
ePrint Report ePrint Report
Constructing collision-resistant hash families (CRHFs) from one-way functions is a long-standing open problem and source of frustration in theoretical cryptography. In fact, there are strong negative results: black-box separations from one-way functions that are $2^{-(1-o(1))n}$-secure against polynomial time adversaries (Simon, EUROCRYPT '98) and even from indistinguishability obfuscation (Asharov and Segev, FOCS '15).

In this work, we formulate a mild strengthening of exponentially secure one-way functions, and we construct CRHFs from such functions. Specifically, our security notion requires that every polynomial time algorithm has at most $2^{-n - \omega(\log(n))}$ probability of inverting two independent challenges.

More generally, we consider the problem of simultaneously inverting $k$ functions $f_1,\ldots, f_k$, which we say constitute a ``one-way product function'' (OWPF). We show that sufficiently hard OWPFs yield hash families that are multi-input correlation intractable (Canetti, Goldreich, and Halevi, STOC '98) with respect to all sparse (bounded arity) output relations. Additionally assuming indistinguishability obfuscation, we construct hash families that achieve a broader notion of correlation intractability, extending the recent work of Kalai, Rothblum, and Rothblum (CRYPTO '17). In particular, these families are sufficient to instantiate the Fiat-Shamir heuristic in the plain model for a natural class of interactive proofs.

An interesting consequence of our results is a potential new avenue for bypassing black-box separations. In particular, proving (with necessarily non-black-box techniques) that parallel repetition amplifies the hardness of specific one-way functions -- for example, all one-way permutations -- suffices to directly bypass Simon's impossibility result.
Expand
Ioana Boureanu, David Gerault, Pascal Lafourcade2
ePrint Report ePrint Report
Distance-bounding (DB) protocols are being adopted in different applications, e.g., contactless payments, keyless entries. For DB to be application-ready, "pick-and-choose" corruption models and clear-cut security definitions in DB are needed. Yet, this is virtually impossible using the four existing formalisms for distance-bounding (DB), whereby each considers around five different security properties, arguably intertwined and hard to compare amongst each other.

In particular, terrorist-fraud resistance has been notoriously problematic to formalise in DB. Also, achieving this property, often weakness a protocol's general security. We demonstrate that --in fact-- terrorist-fraud resistance cannot be achieved, under standard assumptions made for DB protocols. Our result wraps up terrorist-fraud resistance in provable-security in DB.

As a consequence of terrorist-fraud resistance being made irrelevant, and to address application-ready DB, we present a new, provable-security model for distance-bounding. It formalises fine-grained corruption-modes (i.e., white-box and black-box corrupted provers) and this allows for clearer security definitions driven by the separation in corruption-modes. Also, our model explicitly includes a security-property generalising key-leakage, which per se --before this-- was studied only implicitly or as a by-product of other DB-security properties.

In all, our formalism only requires three, clear-cut security definitions which can be "picked and chosen" based on the application-driven prover-corruption modes.
Expand
Wouter Castryck, Tanja Lange, Chloe Martindale, Lorenz Panny, Joost Renes
ePrint Report ePrint Report
We propose an efficient commutative group action suitable for non-interactive key exchange in a post-quantum setting. Our construction follows the layout of the Couveignes-Rostovtsev-Stolbunov cryptosystem, but we apply it to supersingular elliptic curves defined over a large prime field ${\mathbb F_p}$, rather than to ordinary elliptic curves. The Diffie-Hellman scheme resulting from the group action allows for public-key validation at very little cost, runs reasonably fast in practice, and has public keys of only 64 bytes at the AES-128 security level, matching NIST's post-quantum security category I.
Expand
Donghoon Chang, Amit Kumar Chauhan, Sandeep Kumar, Somitra Kumar Sanadhya
ePrint Report ePrint Report
In this paper, we present an identity-based encryption scheme from codes with efficient key revocation. Recently, in Crypto 2017, Gaborit et al. proposed a first identity-based encryption scheme from codes with rank metric, called RankIBE. To extract the decryption key from any public identity, they constructed a trapdoor function which relies on RankSign, a signature scheme proposed by Gaborit et al. in PQCrypto 2014. We adopt the same trapdoor function to add efficient key revocation functionality in the RankIBE scheme. Our revocable IBE scheme from codes with rank metric makes use of a binary tree data structure to reduce the amount of work in terms of key updates for the key authority. The total size of key updates requires logarithmic complexity in the maximum number of users and linear in the number of revoked users. We prove that our revocable IBE scheme is selective-ID secure in the random oracle model, under the hardness of three problems: the Rank Syndrome Decoding (RSD) problem, the Augmented Low-Rank Parity Check Code (LRPC+) problem, and the Rank Support Learning (RSL) problem.
Expand
Gilles Barthe, Sonia Belaïd, Thomas Espitau, Pierre-Alain Fouque, Benjamin Grégoire, Mélissa Rossi, Mehdi Tibouchi
ePrint Report ePrint Report
Abstract. Recently, numerous physical attacks have been demonstrated against lattice- based schemes, often exploiting their unique properties such as the reliance on Gaussian distributions, rejection sampling and FFT-based polynomial multiplication. As the call for concrete implementations and deployment of postquantum cryptography becomes more pressing, protecting against those attacks is an important problem. However, few counter- measures have been proposed so far. In particular, masking has been applied to the decryp- tion procedure of some lattice-based encryption schemes, but the much more difficult case of signatures (which are highly non-linear and typically involve randomness) has not been considered until now. In this paper, we describe the first masked implementation of a lattice-based signature scheme. Since masking Gaussian sampling and other procedures involving contrived prob- ability distribution would be prohibitively inefficient, we focus on the GLP scheme of Gu ̈neysu, Lyubashevsky and Po ̈ppelmann (CHES 2012). We show how to provably mask it in the Ishai–Sahai–Wagner model (CRYPTO 2003) at any order in a relatively efficient man- ner, using extensions of the techniques of Coron et al. for converting between arithmetic and Boolean masking. Our proof relies on a mild generalization of probing security that supports the notion of public outputs. We also provide a proof-of-concept implementation to assess the efficiency of the proposed countermeasure.
Expand
Jonathan Bootle, Andrea Cerulli, Jens Groth, Sune Jakobsen, Mary Maller
ePrint Report ePrint Report
There have been tremendous advances in reducing interaction, communication and verification time in zero-knowledge proofs but it remains an important challenge to make the prover efficient. We construct the first zero-knowledge proof of knowledge for the correct execution of a program on public and private inputs where the prover computation is nearly linear time. This saves a polylogarithmic factor in asymptotic performance compared to current state of the art proof systems.

We use the TinyRAM model to capture general purpose processor computation. An instance consists of a TinyRAM program and public inputs. The witness consists of additional private inputs to the program. The prover can use our proof system to convince the verifier that the program terminates with the intended answer within given time and memory bounds. Our proof system has perfect completeness, statistical special honest verifier zero-knowledge, and computational knowledge soundness assuming linear-time computable collision-resistant hash functions exist.

The main advantage of our new proof system is asymptotically efficient prover computation. The prover's running time is only a superconstant factor larger than the program's running time in an apples-to-apples comparison where the prover uses the same TinyRAM model. Our proof system is also efficient on the other performance parameters; the verifier's running time time and the communication are sublinear in the execution time of the program and we only use a log-logarithmic number of rounds.
Expand
Wilson Alberto Torres, Ron Steinfeld, Amin Sakzad, Joseph K. Liu, Veronika Kuchta, Nandita Bhattacharjee, Man Ho Au, Jacob Cheng
ePrint Report ePrint Report
In this paper, we construct a Lattice-based one-time Linkable Ring Signature (L2RS) scheme, which enables the public to verify if two or more signatures were generated by same signatory, whilst still preserving the anonymity of the signatory. The L2RS provides unconditional anonymity and security guarantees under the Ring Short Integer Solution (Ring-SIS) lattice hardness assumption. The proposed L2RS scheme is extended to be applied in a protocol that we called Lattice Ring Con dential transaction (Lattice RingCT) RingCT v1.0, which forms the foundation of the privacy-preserving protocol in any post-quantum secure cryptocurrency such as Hcash.
Expand
Christian Badertscher, Peter Ga{\v{z}}i, Aggelos Kiayias, Alexander Russell, Vassilis Zikas
ePrint Report ePrint Report
Proof-of-stake-based (in short, PoS-based) blockchains aim to overcome scalability, effi- ciency, and composability limitations of the proof-of-work paradigm, which underlies the security of several mainstream cryptocurrencies including Bitcoin. Our work puts forth the first (global universally) composable (GUC) treatment of PoS-based blockchains in a setting that captures—for the first time in GUC—arbitrary numbers of parties that may not be fully operational, e.g., due to network problems, reboots, or updates of their OS that affect all or just some of their local resources including their network interface and clock. This setting, which we refer to as dynamic availability, naturally captures decentralized environments within which real-world deployed blockchain protocols are assumed to operate. We observe that none of the existing PoS-based blockchain protocols can realize the ledger functionality under dynamic availability in the same way that bitcoin does (using only the information available in the genesis block). To address this we propose a new PoS-based protocol, “Ouroboros Genesis”, that adapts one of the latest cryptographically-secure PoS-based blockchain protocols with a novel chain selection rule. The rule enables new or offline parties to safely (re-)join and bootstrap their blockchain from the genesis block without any trusted advice—such as checkpoints—or assumptions regarding past availability. We say that such a blockchain protocol can “bootstrap from genesis.” We prove the GUC security of Ouroboros Genesis against a fully adaptive adversary controlling less than half of the total stake. Our model allows adversarial scheduling of messages in a network with delays and captures the dynamic availability of participants in the worst case. Importantly, our protocol is effectively independent of both the maximum network delay and the minimum level of availability— both of which are run-time parameters. Proving the security of our construction against an adaptive adversary requires a novel martingale technique that may be of independent interest in the analysis of blockchain protocols.
Expand
Jing Chen, Sergey Gorbunov, Silvio Micali, Georgios Vlachos
ePrint Report ePrint Report
We present a simple Byzantine agreement protocol with leader election, that works under > 2/3 honest majority and does not rely on the participants having synchronized clocks. When honest messages are delivered within a bounded worst-case delay, agreement is reached in expected constant number of steps when the elected leader is malicious, and is reached after two steps when the elected leader is honest. Our protocol is resilient to arbitrary network partitions with unknown length, and recovers fast after the partition is resolved and bounded message delay is restored. We will briefly discuss how the protocol applies to blockchains in a permissionless system. In particular, when an honest leader proposes a block of transactions, the first voting step happens in parallel with the block propagation. Effectively, after the block propagates, a certificate is generated in just one step of voting.
Expand
Joppe W. Bos, Simon Friedberger
ePrint Report ePrint Report
In this paper we investigate various arithmetic techniques which can be used to potentially enhance the performance in the supersingular isogeny Diffie-Hellman (SIDH) key-exchange protocol which is one of the more recent contenders in the post-quantum public-key arena. Firstly, we give a systematic overview of techniques to compute efficient arithmetic modulo $2^xp^y\pm 1$. Our overview shows that in the SIDH setting, where arithmetic over a quadratic extension field is required, the approaches based on Montgomery reduction for such primes of a special shape are to be preferred. Moreover, the outcome of our investigation reveals that there exist moduli which allow even faster implementations.

Secondly, we investigate if it is beneficial to use other curve models to speed-up the elliptic curve scalar multiplication. The use of twisted Edwards curves allows one to search for efficient addition-subtraction chains for fixed scalars while this is not possible with the differential addition law when using Montgomery curves. Our preliminary results show that despite the fact that we found such efficient chains, using twisted Edwards curves does not result in faster scalar multiplication arithmetic in the setting of SIDH.
Expand
Zvika Brakerski, Yael Tauman Kalai
ePrint Report ePrint Report
Consider an access policy for some resource which only allows access to users of the system who own a certain set of attributes. Specifically, we consider the case where such an access structure is defined by a monotone formula (or logarithmic depth circuit) $F:\{0,1\}^N\rightarrow\{0,1\}$, where $N$ is the number of possible attributes.

In this work we present two results, which we believe to be of individual interest even regardless of the above application, and show how to combine them to achieve a succinct single-round private access control protocol. That is, a verifier can be convinced that an approved user (i.e. one which holds an approved set of attributes) is accessing the system, without learning any additional information about the user or the set of attributes.

First, assuming a computational PIR scheme (which can be based, for example, on the polynomial hardness of the LWE assumption), we construct for any $NP$ language $L$, a succinct single-round (2-message) protocol for delegating \monotone batch $L$ computations. Explicitly, for every $N\in \mathbb{N}$, every $x_1,\ldots,x_N\in \{0,1\}^n$, and every monotone formula $F:\{0,1\}^N\rightarrow \{0,1\}$, a prover can succinctly prove that $F(1_{x_1\in L},\ldots,1_{x_N\in L})=1$, where $1_{x_i\in L}=1$ if and only if $x_i\in L$, and where the communication complexity is $m \cdot polylog(N)$ where $m$ is the length of a single witness.

Second, assuming a quasi-polynomially secure two-message oblivious transfer scheme with statistical sender privacy (which can be based on quasi-polynomial hardness of the DDH, QR or DCR assumptions), we show how to convert any single-round protocol into a witness indistinguishable one, with similar communication complexity.
Expand
Zhenzhen Bao, Jian Guo, Lei Wang
ePrint Report ePrint Report
We provide a survey about generic attacks on cryptographic hash constructions including hash-based message authentication codes and hash combiners.

We look into attacks involving iteratively evaluating identical mappings many times. The functional graph of a random mapping also involves iteratively evaluating the mapping. These attacks essentially exploit properties of the functional graph. We map the utilization space of those properties from numerous proposed known attacks, draw a comparison among classes of attacks about their advantages and limitations.

We provide a systematic exposition of concepts of cycles, deep-iterate images, collisions and their roles in cryptanalysis of iterated hash constructions. We identify the inherent relationship between these concepts, such that case-by-case theories about them can be unified into one knowledge system, that is, theories on the functional graph of random mappings. We show that the properties of the cycle search algorithm, the chain evaluation algorithm and the collision search algorithm can be described based on statistic results on the functional graph. Thereby, we can provide different viewpoints to support previous beliefs on individual knowledge.

In that, we invite more sophisticated analysis of the functional graph of random mappings and more future exploitations of its properties in cryptanalysis.
Expand
Sarvar Patel, Giuseppe Persiano, Mariana Raykova, Kevin Yeo
ePrint Report ePrint Report
We present PanORAMa, the first Oblivious RAM construction that achieves communication overhead $O(\log N \cdot \log \log N)$ for database of N blocks and for any block size $B = \Omega(\log N)$ while requiring client memory of only a constant number of memory blocks. Our scheme can be instantiated in the ”balls and bins” model in which Goldreich and Ostrovsky [JACM 96] showed an $\Omega(\log N)$ lower bound for ORAM communication.

Our construction follows the hierarchical approach to ORAM design and relies on two main building blocks of independent interest: a new oblivious hash table construction with improved amortized $O(\log N + poly(\log \log \lambda))$ communication overhead for security parameter $\lambda$ and $N = \mathsf{poly}(\lambda)$, assuming its input is randomly shuffled; and a complementary new oblivious random multi-array shuffle construction, which shuffles N blocks of data with communication $O(N \log \log \lambda + \frac{N \log N}{\log \lambda})$ when the input has a certain level of entropy. We combine these two primitives to improve the shuffle time in our hierarchical ORAM construction by avoiding heavy oblivious shuffles and leveraging entropy remaining in the merged levels from previous shuffles. As a result, the amortized shuffle cost is asymptotically the same as the lookup complexity in our construction.
Expand
Alexander R. Block, Divya Gupta, Hemanta K. Maji, Hai H. Nguyen
ePrint Report ePrint Report
Most secure computation protocols can be effortlessly adapted to offload a significant fraction of their computationally and cryptographically expensive components to an offline phase so that the parties can run a fast online phase and perform their intended computation securely. During this offline phase, parties generate private shares of a sample generated from a particular joint distribution, referred to as the correlation. These shares, however, are susceptible to leakage attacks by adversarial parties, which can compromise the security of the entire secure computation protocol. The objective, therefore, is to preserve the security of the honest party despite the leakage performed by the adversary on her share.

Prior solutions, starting with $n$-bit leaky shares, either used 4 messages or enabled the secure computation of only sub-linear size circuits. Our work presents the first 2-message secure computation protocol for 2-party functionalities that have $\Theta(n)$ circuit-size despite $\Theta(n)$-bits of leakage, a qualitatively optimal result. We compose a suitable 2-message secure computation protocol in parallel with our new 2-message correlation extractor. Correlation extractors, introduced by Ishai, Kushilevitz, Ostrovsky, and Sahai (FOCS--2009) as a natural generalization of privacy amplification and randomness extraction, recover ``fresh'' correlations from the leaky ones, which are subsequently used by other cryptographic protocols. We construct the first 2-message correlation extractor that produces $\Theta(n)$-bit fresh correlations even after $\Theta(n)$-bit leakage.

Our principal technical contribution, which is of potential independent interest, is the construction of a family of multiplication-friendly linear secret sharing schemes that is simultaneously a family of small-bias distributions. We construct this family by randomly ``twisting then permuting'' appropriate Algebraic Geometry codes over constant-size fields.
Expand

29 April 2018

Fuzhou, China, 14 December - 16 December 2018
Event Calendar Event Calendar
Event date: 14 December to 16 December 2018
Submission deadline: 14 August 2018
Notification: 14 October 2018
Expand

28 April 2018

Barcelona, Spain, 6 September - 7 September 2018
Event Calendar Event Calendar
Event date: 6 September to 7 September 2018
Submission deadline: 11 June 2018
Notification: 18 July 2018
Expand
Nanyang Technological University, Singapore
Job Posting Job Posting
The Nanyang Technological University in Singapore is offering scholarship for Ph.D students on the field of cryptography, inclusive of symmetric-key cryptography, cryptanalysis, lightweight cryptography etc.

The Ph.D. program at NTU is usually for 4 years, which comprises some coursework in the first year and intensive research for all years. The research scholarship offers full coverage of tuition fees, support of conference trips, tax-free living allowance of 2000 SGD/month for the first year, and 2500 SGD/month for the subsequence years after passing the Ph.D candidate qualification examination, further top-up is possible for exceptional good candidates, Singapore citizens and permanent residents. For more information about the requirements of admission and application procedure, refer to here: http://admissions.ntu.edu.sg/graduate/Pages/home.aspx

These positions will be available until filled. For the Jan 2019 intake, submit by 30th September 2018, and by 31st March 2019 for the August 2019 intake. More information about the CATF research team can be found here: http://catf.crypto.sg

Closing date for applications: 31 December 2019

Contact: Jian Guo, Assistant Professor, guojian (at) ntu.edu.sg for more information.

Expand
Ant Financial Service Group
Job Posting Job Posting
Ant Financial is a technology company that brings inclusive financial services to the world.Ant Financial, officially founded in October 2014, originated from Alipay founded in 2004.

Ant Financial is dedicated to bringing the world more equal opportunities through building a technology-driven open ecosystem and working with other financial institutions to support the future financial needs of society.

We are hiring:

- Applied Cryptography

- Crypto-currencies, smart-contracts, financial cryptography

- Privacy enhancing technologies

- Distributed consensus protocols

- Cybersecurity

Requirements:

- M.S. or Ph.D. in Cryptographic, System Security, Computer Science or related field, or equivalent experience.

- Good programming skills - C/C++, Go

- Good knowledge in Blockchain technology

- Chinese Mandarin can be used as work language

Interested candidates kindly contact Email: lewis.ls (at) antfin.com

Closing date for applications: 31 October 2018

More information: https://www.antfin.com/index.htm?locale=en_US

Expand
China, Guangzhou, 8 October - 12 October 2018
Event Calendar Event Calendar
Event date: 8 October to 12 October 2018
Submission deadline: 8 June 2018
Notification: 8 July 2018
Expand
Chengdu, China, 5 November - 7 November 2018
Event Calendar Event Calendar
Event date: 5 November to 7 November 2018
Submission deadline: 10 June 2018
Notification: 10 August 2018
Expand
◄ Previous Next ►