IACR News
Here you can see all recent updates to the IACR webpage. These updates are also available:
26 August 2016
Carmen Hazay, Muthuramakrishnan Venkitasubramaniam
Next, we revisit the zero-one law for two-party secure functions evaluation initiated by the work of Maji, Prabhakaran and Rosulek (CRYPTO 2010). According to this law, every two-party functionality is either trivial (meaning, such functionalities can be reduced to any other functionality) or complete (meaning, any other functionality can be reduced to these functionalities) in the Universal Composability (UC) framework. As our second contribution, assuming the existence of a simulatable public-key encryption scheme, we establish a zero-one law in the adaptive setting. Our result implies that every two-party non-reactive functionality is either trivial or complete in the UC framework in the presence of adaptive, malicious adversaries.
Sanjay Garg, Eric Miles, Pratyay Mukherjee, Amit Sahai, Akshayaram Srinivasan, Mark Zhandry
However, this model is inadequate: there have been several attacks on multilinear maps that exploit extra information revealed by the zero-test procedure. In particular, Miles, Sahai and Zhandry [Crypto'16] recently gave a polynomial-time attack on several iO candidates when instantiated with the multilinear maps of Garg, Gentry, and Halevi [Eurocrypt'13], and also proposed a new "weak multilinear map model" that captures all known polynomial-time attacks on GGH13.
In this work, we give a new iO candidate which can be seen as a small modification or generalization of the original candidate of Garg, Gentry, Halevi, Raykova, Sahai, and Waters [FOCS'13]. We prove its security in the weak multilinear map model, thus giving the first iO candidate that is provably secure against all known polynomial-time attacks on GGH13. The proof of security relies on a new assumption about the hardness of computing annihilating polynomials, and we show that this assumption is implied by the existence of pseudorandom functions in $\text{NC}^1$.
25 August 2016
Mark Bun, Thomas Steinke
Sanjay Garg, Divya Gupta, Peihan Miao, Omkant Pandey
In this work, we consider the multi-party case and obtain the following results:
1. Semi-honest model: We present a constant-round black-box secure computation protocol for RAM programs. This protocol is obtained by building on the new black-box garbled RAM construction by Garg, Lu, and Ostrovsky [FOCS 2015], and constant-round secure computation protocol for circuits of Beaver, Micali, and Rogaway [STOC 1990]. This construction allows execution of multiple programs on the same persistent database.
2. Malicious model: Next, we show how to extend our semi-honest results to the malicious setting, while ensuring that the new protocol is still constant-round and black-box in nature.
Zahra Jafargholi, Daniel Wichs
A recent work of Hemenway et al. (CRYPTO '16) modifies Yao's construction and shows that the resulting scheme is adaptively secure. This is done by encrypting the garbled circuit from Yao's construction with a special type of ``somewhere equivocal encryption'' and giving the key together with the garbled input. The efficiency of the scheme and the security loss of the reduction is captured by a certain pebbling game over the circuit.
In this work we prove that Yao's construction itself is already adaptively secure, where the security loss can be captured by the same pebbling game. For example, we show that for circuits of depth $d$, the security loss of our reduction is $2^{O(d)}$, meaning that Yao's construction is adaptively secure for NC1 circuits without requiring complexity leveraging.
Our technique is inspired by the ``nested hybrids'' of Fuchsbauer et al. (Asiacrypt '14, CRYPTO '15) and relies on a careful sequence of hybrids where each hybrid involves some limited guessing about the adversary's adaptive choices. Although it doesn't match the parameters achieved by Hemenway et al. in their full generality, the main advantage of our work is to prove the security of Yao's construction as is, without any additional encryption layer.
Benny Applebaum, Pavel Raykov
Our proofs are based on a new search-to-decision reduction for expander-based functions. This extends a previous reduction of the first author (STOC 2012) which was applicable for the special case of \emph{random} local functions. Additionally, we present a new family of highly efficient hash functions whose output on exponentially many inputs jointly forms (with high probability) a good expander graph. These hash functions are based on the techniques of Miles and Viola (Crypto 2012). Although some of our reductions provide only relatively weak security guarantees, we believe that they yield novel approach for constructing PRFs, and therefore enrich the study of pseudorandomness.
Dana Dachman-Soled
Specifically, we introduce the notion of $\textsf{BBN}^-$ reductions (similar to the $\textsf{BBN}\text{p}$ reductions of Baecher et al. (ASIACRYPT, 2013)), in which the construction $E$ accesses the underlying primitive in a black-box way, but wherein the universal reduction $R$ receives the efficient code/circuit of the underlying primitive as input and is allowed oracle access to the adversary $\textsf{Adv}$. We additionally require that the number of oracle queries made to $\textsf{Adv}$, and the success probability of $R$ are independent of the run-time/circuit size of the underlying primitive. We prove that there is no non-adaptive, $\textsf{BBN}^-$ reduction from PKE to one way function, under the assumption that certain types of strong one way functions exist. Specifically, we assume that there exists a regular one way function $f$ such that there is no Arthur-Merlin protocol proving that ``$z \not\in \textsf{Range}(f)$'', where soundness holds with high probability over ``no instances,'' $y \sim f(U_n)$, and Arthur may receive polynomial-sized, non-uniform advice. This assumption is related to the average-case analogue of the widely believed assumption $\textbf{coNP} \not\subseteq \textbf{NP}/\textbf{poly}$.
Ling Sun, Wei Wang, Meiqin Wang
24 August 2016
Center For Cyber Security in New York University Abu Dhabi
The goal of this research project is to provide a wider analysis of the existing cryptologic constructions in order to provide the possibility of new approaches in the designs and analysis of cryptographic components. The conducted research will be in the context of symmetric cryptology and secure hardware implementations. A particular focus will be on the hardware design and analysis of symmetric-key primitives and components.
Required Qualifications
Candidates should have a PhD degree or equivalent experience. Candidates should have a background in symmetric cryptology, hardware cryptology, hardware security or related areas. The following are a list of essential skills for the considered post: Circuit Analysis and Design, Cryptographic Hardware Design (Reconfigurable Hardware, random number generation, lightweight cryptographic design, ALTERA hardware, FPGAs and Verilog VHDL programming), and Cryptographic Design and Cryptanalysis.
Terms of employment
The period of employment is one to two year(s) from the initiation of the contract. The potential start date is November 2016. The main location of the post is Center for Cyber Security in NYU Abu Dhabi.
Application Process
Submissions will be accepted through our online application no later than October 15, 2016. Please fill in the online application form, and attach all your materials in English. This includes a cover letter, research statement, curriculum vitae, diploma (an official translation into English), list of publications and three letters of reference. Applications and enclosures received beyond the stated deadline will not be considered.
Further information
Further information may be obtained from Hoda A. Alkhzaimi at Hoda.alkhzaimi (at) nyu.edu.
(All interested candidates regardless of gender, disability, race, religion or ethnic background are encouraged to apply)
EOE/AA/Minorities/Females/Vet/Disabled/Sexual Orientation/Gender Identity Employer
Closing date for applications: 15 October 2016
Contact:
Hoda A.Alkhzaimi
Hoda.Alkhzaimi (at) nyu.edu
More information: https://apply.interfolio.com/36948
Colin O'Flynn
Daniel Genkin; Yuval Ishai; Mor Weiss
Genkin et al. (STOC 2014, Crypto 2015) introduced AMD circuits as a means for protecting MPC protocols against active attacks, and showed that every arithmetic circuit C over F can be transformed into an equivalent AMD circuit of size $O(|C|)$ with $O(1/|\mathbb F|)$ simulation error. However, for the case of the binary field $\mathbb F=\mathbb F_2$, their constructions relied on a tamper-proof output decoder and could only realize a weaker notion of security.
We obtain the first constructions of fully secure binary AMD circuits. Given a boolean circuit $C$ and a statistical security parameter $s$, we construct an equivalent binary AMD circuit $C'$ of size $|C|*polylog(|C|,s)$ (ignoring lower order additive terms) with $2^{-s}$ simulation error. That is, the effect of toggling an arbitrary subset of wires can be simulated by toggling only input and output wires.
Our construction combines in a general way two types of ``simple'' honest-majority MPC protocols: protocols that only offer security against passive adversaries, and protocols that only offer correctness against active adversaries. As a corollary, we get a conceptually new technique for constructing active-secure two-party protocols in the OT-hybrid model, and reduce the open question of obtaining such protocols with constant computational overhead to a similar question in these simpler MPC models.
Maciej Skorski
(a) We present a novel boosting algorithm for constructing the simulator. This boosting proof is of independent interest, as it shows how to handle "negative mass" issues when constructing probability measures by shifting distinguishers in descent algorithms. Our technique essentially fixes the flaw in the TCC'14 paper "How to Fake Auxiliary Inputs".
(b) The complexity of our simulator is better than in previous works, including results derived from the uniform min-max theorem due to Vadhan and Zheng. To achieve $(s,\epsilon)$-indistinguishability we need the complexity $O\left(s\cdot 2^{5\ell}\epsilon^{-2}\right)$ in time/circuit size, which improve previous bounds by a factor of $\epsilon^{-2}$. In particular, with we get meaningful provable security for the EUROCRYPT'09 leakage-resilient stream cipher instantiated with a standard 256-bit block cipher, like $\mathsf{AES256}$.
Our boosting technique utilizes a two-step approach. In the first step we shift the current result (as in gradient or sub-gradient descent algorithms) and in the separate step we fix the biggest non-negative mass constraint violation (if applicable).
Hyunjin Ahn, Dong-Guk Han
Mohammad Hadi Valizadeh
ISARA Corporation, Waterloo, Canada
We are looking for cryptographic researchers, with a PhD in Mathematics or Computer Science, to join our team. The ISARA Research Department is a group of dedicated individuals who focus on researching the latest advances in cryptography and pushing the envelope of what is possible. They are responsible for understanding the current state of the art and focusing on improvements in security and efficiency.
Closing date for applications: 31 December 2016
Contact: info (at) isara (dot) com with your resume.
More information: http://www.isara.com
Radboud University, Nijmegen, The Netherlands
A successful candidate is expected to supervise PhD and MSc students, collaborate with the researchers from the DiS group (http://www.ru.nl/ds/) and perform research. He/she should ideally have background in some of the following areas:
1. Proofs of security by reduction
2. Mathematical tools for symmetric-key cryptanalysis
3. Design and analysis of cryptographic protocols
4. Cryptographic implementations and attacks (side-channel and fault attacks)
5. Systems security e.g. Android
Applicants should have already completed (or be close to completing) a PhD in computer science, mathematics, or a related discipline. We also expect an excellent research track record. The application requires: curriculum vitae, a motivation letter, and names of 3 persons that can provide reference about the applicant and her/his work.
Applications will be considered until the position is filled. Suitable candidates can be hired immediately.
Applicants interested in the position should send an email to the faculty members they would like to work with.
Contact: For enquiries about the positions, please contact
Lejla Batina, lejla (at) cs.ru.nl
Joan Daemen, joan (at) cs.ru.nl
Closing date for applications: 31 October 2016