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:
30 April 2018
Justin Holmgren, Alex Lombardi
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.
Ioana Boureanu, David Gerault, Pascal Lafourcade2
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.
Wouter Castryck, Tanja Lange, Chloe Martindale, Lorenz Panny, Joost Renes
Donghoon Chang, Amit Kumar Chauhan, Sandeep Kumar, Somitra Kumar Sanadhya
Gilles Barthe, Sonia Belaïd, Thomas Espitau, Pierre-Alain Fouque, Benjamin Grégoire, Mélissa Rossi, Mehdi Tibouchi
Jonathan Bootle, Andrea Cerulli, Jens Groth, Sune Jakobsen, Mary Maller
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.
Wilson Alberto Torres, Ron Steinfeld, Amin Sakzad, Joseph K. Liu, Veronika Kuchta, Nandita Bhattacharjee, Man Ho Au, Jacob Cheng
Christian Badertscher, Peter Ga{\v{z}}i, Aggelos Kiayias, Alexander Russell, Vassilis Zikas
Jing Chen, Sergey Gorbunov, Silvio Micali, Georgios Vlachos
Joppe W. Bos, Simon Friedberger
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.
Zvika Brakerski, Yael Tauman Kalai
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.
Zhenzhen Bao, Jian Guo, Lei Wang
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.
Sarvar Patel, Giuseppe Persiano, Mariana Raykova, Kevin Yeo
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.
Alexander R. Block, Divya Gupta, Hemanta K. Maji, Hai H. Nguyen
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.
29 April 2018
Fuzhou, China, 14 December - 16 December 2018
Submission deadline: 14 August 2018
Notification: 14 October 2018
28 April 2018
Barcelona, Spain, 6 September - 7 September 2018
Submission deadline: 11 June 2018
Notification: 18 July 2018
Nanyang Technological University, Singapore
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.
Ant Financial Service Group
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
China, Guangzhou, 8 October - 12 October 2018
Submission deadline: 8 June 2018
Notification: 8 July 2018
Chengdu, China, 5 November - 7 November 2018
Submission deadline: 10 June 2018
Notification: 10 August 2018