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

26
August
2016

Starting this year, FSE has moved to a new open-access journal/conference hybrid model. Submitted articles undergo a journal-style reviewing process. Accepted papers are published in Gold Open Access (free availability from day one) by the Ruhr University of Bochum in an issue of the newly established journal IACR Transactions on Symmetric Cryptology.

For more information, see the call for papers or submission server.

**Second round deadline:** September 1, 2016

Third round deadline: November 23, 2016

For more information, see the call for papers or submission server.

Third round deadline: November 23, 2016

The list of papers accepted to TCC 2016-B is now available at http://tcc2016b.sklois.cn/accepted-papers.html. TCC will be held October 31 - Nov 3 in Beijing.

Event Calendar
: Summer school on post-quantum cryptography
Eindhoven, Netherlands, 19 June - 23 June 2017

Event date: 19 June to 23 June 2017

Event Calendar
PQCrypto 2017: Workshop on Post-Quantum Cryptography
Utrecht, Netherlands, 26 June - 28 June 2017

Event date: 26 June to 28 June 2017

Event Calendar
: Executive school on post-quantum cryptography
Eindhoven, Netherlands, 22 June - 23 June 2017

Event date: 22 June to 23 June 2017

ePrint Report
Virtual Grey-Boxes Beyond Obfuscation: A Statistical Security Notion for Cryptographic Agents
Shashank Agrawal, Manoj Prabhakaran, Ching-Hua Yu

We extend the simulation-based definition of Virtual Grey Box (VGB) security -- originally proposed for obfuscation (Bitansky and Canetti, 2010) -- to a broad class of cryptographic primitives. These include functional encryption, graded encoding schemes, bi-linear maps (with uber assumptions), as well as unexplored ones like homomorphic functional encryption.

Our main result is a characterization of VGB security, in all these cases, in terms of an indistinguishability-preserving notion of security, called $\Gamma^*-s-\textsf{IND}-\textsf{PRE}$ security, formulated using an extension of the recently proposed Cryptographic Agents framework (Agrawal et al., 2015). We further show that this definition is equivalent to an indistinguishability based security definition that is restricted to 'concentrated' distributions (wherein the outcome of any computation on encrypted data is essentially known ahead of the computation).

A result of Bitansky et al. (2014), who showed that VGB obfuscation is equivalent to strong indistinguishability obfuscation (SIO), is obtained by specializing our result to obfuscation. Our proof, while sharing various elements from the proof of Bitansky et al., is simpler and significantly more general, as it uses $\Gamma^*-s-\textsf{IND}-\textsf{PRE}$ security as an intermediate notion. Our characterization also shows that the semantic security for graded encoding schemes (Pass et al. 2014), is in fact an instance of this same definition.

We also present a composition theorem for rtestfamily-sINDPRE security. We can then recover the result of Bitansky et al. (2014) regarding the existence of VGB obfuscation for all NC1 circuits, simply by instantiating this composition theorem with a reduction from obfuscation of NC1 circuits to graded encoding schemas (Barak et al., 2014) and the assumption that there exists an $\Gamma^*-s-\textsf{IND}-\textsf{PRE}$ secure scheme for the graded encoding schema (Pass et al. 2014).

Our main result is a characterization of VGB security, in all these cases, in terms of an indistinguishability-preserving notion of security, called $\Gamma^*-s-\textsf{IND}-\textsf{PRE}$ security, formulated using an extension of the recently proposed Cryptographic Agents framework (Agrawal et al., 2015). We further show that this definition is equivalent to an indistinguishability based security definition that is restricted to 'concentrated' distributions (wherein the outcome of any computation on encrypted data is essentially known ahead of the computation).

A result of Bitansky et al. (2014), who showed that VGB obfuscation is equivalent to strong indistinguishability obfuscation (SIO), is obtained by specializing our result to obfuscation. Our proof, while sharing various elements from the proof of Bitansky et al., is simpler and significantly more general, as it uses $\Gamma^*-s-\textsf{IND}-\textsf{PRE}$ security as an intermediate notion. Our characterization also shows that the semantic security for graded encoding schemes (Pass et al. 2014), is in fact an instance of this same definition.

We also present a composition theorem for rtestfamily-sINDPRE security. We can then recover the result of Bitansky et al. (2014) regarding the existence of VGB obfuscation for all NC1 circuits, simply by instantiating this composition theorem with a reduction from obfuscation of NC1 circuits to graded encoding schemas (Barak et al., 2014) and the assumption that there exists an $\Gamma^*-s-\textsf{IND}-\textsf{PRE}$ secure scheme for the graded encoding schema (Pass et al. 2014).

ePrint Report
Composable Adaptive Secure Protocols without Setup under Polytime Assumptions
Carmen Hazay, Muthuramakrishnan Venkitasubramaniam

All previous constructions of general multiparty computation protocols that are secure against adaptive corruptions in the concurrent setting either require some form of setup or non-standard assumptions. In this paper we provide the first general construction of secure multi-party computation protocol without any setup that guarantees composable security in the presence of an adaptive adversary based on standard polynomial-time assumptions. We prove security under the notion of ``UC with super-polynomial helpers'' introduced by Canetti et al. (FOCS 2010), which is closed under universal composition and implies ``super-polynomial-time simulation''. Moreover, our construction relies on the underlying cryptographic primitives in a black-box manner.

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.

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.

ePrint Report
Secure Obfuscation in a Weak Multilinear Map Model
Sanjay Garg, Eric Miles, Pratyay Mukherjee, Amit Sahai, Akshayaram Srinivasan, Mark Zhandry

All known candidate indistinguishibility obfuscation (iO) schemes rely on candidate multilinear maps. Until recently, the strongest proofs of security available for iO candidates were in a generic model that only allows "honest" use of the multilinear map. Most notably, in this model the zero-test procedure only reveals whether an encoded element is 0, and nothing more.

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$.

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

ePrint Report
Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds
Mark Bun, Thomas Steinke

"Concentrated differential privacy" was recently introduced by Dwork and Rothblum as a relaxation of differential privacy, which permits sharper analyses of many privacy-preserving computations. We present an alternative formulation of the concept of concentrated differential privacy in terms of the Renyi divergence between the distributions obtained by running an algorithm on neighboring inputs. With this reformulation in hand, we prove sharper quantitative results, establish lower bounds, and raise a few new questions. We also unify this approach with approximate differential privacy by giving an appropriate definition of "approximate concentrated differential privacy."

ePrint Report
Secure Multiparty RAM Computation in Constant Rounds
Sanjay Garg, Divya Gupta, Peihan Miao, Omkant Pandey

Securing computation of a random access machine (RAM) program typically entails that it be first converted into a circuit. This conversion is unimaginable in the context of big-data applications where the size of the circuit can be exponential in the running time of the original RAM program. Realizing these constructions, without relinquishing the efficiency of RAM programs, often poses considerable technical hurdles. Our understanding of these techniques in the multi-party setting is largely limited. Specifically, the round complexity of all known protocols grows linearly in the running time of the program being computed.

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.

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.

A garbling scheme is used to garble a circuit $C$ and an input $x$ in a way that reveals the output $C(x)$ but hides everything else. Yao's construction from the 80's is known to achieve selective security, where the adversary chooses the circuit $C$ and the input $x$ in one shot. It has remained as an open problem whether the construction also achieves adaptive security, where the adversary can choose the input $x$ after seeing the garbled version of the circuit $C$.

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.

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.

We present direct constructions of pseudorandom function (PRF) families based on Goldreich's one-way function. Roughly speaking, we assume that non-trivial local mappings $f:\{0,1\}^n\rightarrow \{0,1\}^m$ whose input-output dependencies graph form an expander are hard to invert. We show that this one-wayness assumption yields PRFs with relatively low complexity. This includes weak PRFs which can be computed in linear time of $O(n)$ on a RAM machine with $O(\log n)$ word size, or by a depth-3 circuit with unbounded fan-in AND and OR gates (AC0 circuit), and standard PRFs that can be computed by a quasilinear size circuit or by a constant-depth circuit with unbounded fan-in AND, OR and Majority gates (TC0).

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.

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.

ePrint Report
Towards Non-Black-Box Separations of Public Key Encryption and One Way Function
Dana Dachman-Soled

Separating public key encryption from one way functions is one of the fundamental goals of complexity-based cryptography. Beginning with the seminal work of Impagliazzo and Rudich (STOC, 1989), a sequence of works have ruled out certain classes of reductions from public key encryption (PKE)---or even key agreement---to one way function. Unfortunately, known results---so called black-box separations---do not apply to settings where the construction and/or reduction are allowed to directly access the code, or circuit, of the one way function. In this work, we present a meaningful, non-black-box separation between public key encryption (PKE) and one way function.

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}$.

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}$.

ePrint Report
MILP-Aided Bit-Based Division Property for Primitives with Non-Bit-Permutation Linear Layers
Ling Sun, Wei Wang, Meiqin Wang

At ASIACRYPT 2016, Xiang et al. applied MILP method to search integral distinguisher based on division property. This method handled the huge time and memory complexities which had constituted the main restriction of the bit-based division property proposed by Todo and Morri, and showed its strength through finding some longer integral distinguishers for various primitives. Although MILP-aided bit-based division property has given many interesting results for some ciphers, the linear layers of these cipher are simple bit-permutations.
Thus, the feasibility of MILP method applying to ciphers with linear layers which are not bit-permutations was left as a future work. In this paper, we handle this problem. Following this way, MILP-aided bit-based division property can operate on more primitives. As an illustration, we apply MILP-aided bit-based division property to find integral distinguishers for AES, LED, Joltik-BC, PHOTON, Serpent, Noekeon, SM4, and SPONGENT-88. We can not find any integral distinguisher whose length is longer than four rounds for AES. But for LED and Joltik-BC, which are AES-like block ciphers, we obtain 6-round integral distinguishers. For PHOTON permutations, which are also AES-like permutations, we obtain some better integral distinguishers comparing with those provided in its design paper. Based on these observations, the security of these AES-like block ciphers may need to be reconsidered and directly copying AES-like security proofs for some attacks seems to be less reasonable. We also find 7-round integral distinguishers for Serpent and Noekeon, which attain 3.5 more rounds than the previous distinguishers found by Z'aba et al. at FSE 2008. For SM4, we find a 12-round integral distinguisher, which attains four more rounds than the previous distinguisher found by Liu et al. at ACISP 2007. A 16-round higher-order integral distinguisher for SPONGENT-88 is proposed and this newly found distinguisher attains two more rounds than the previously known distinguishers.

24
August
2016

Job Posting
Cryptology Research/Hardware Cryptology Postdoctoral Position (Multiple Positions)
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 H*oda.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.A*lkhzaimi (at) nyu.edu*

**More information:** https://apply.interfolio.com/36948

Causing a device to incorrectly execute an instruction or store faulty data is well-known strategy for attacking cryptographic implementations on embedded systems. One technique to generate such faults is to manipulate the supply voltage of the device. This paper introduces a novel technique to introduce those supply voltage manipulations onto existing digital systems, requiring minimal modifications to the device being attacked. This uses a crowbar to short the power supply for controlled periods of time. High-accuracy faults are demonstrated on the 8-bit AVR microcontroller, which can generate both single and multi-bit faults with high repeatability. Additionally this technique is demonstrated on a FPGA where it is capable of generating faults in both internal registers and the configuration fabric.

ePrint Report
Binary AMD Circuits from Secure Multiparty Computation
Daniel Genkin; Yuval Ishai; Mor Weiss

An AMD circuit over a finite field $\mathbb F$ is a randomized arithmetic circuit that offers the ``best possible protection'' against additive attacks. That is, the effect of every additive attack that may blindly add a (possibly different) element of $\mathbb F$ to every internal wire of the circuit can be simulated by an ideal attack that applies only to the inputs and outputs.

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.

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.

For any pair $(X,Z)$ of correlated random variables we can think of $Z$ as a randomized function of $X$. If the domain of $Z$ is small, one can make this function computationally efficient
by allowing it to be only approximately correct. In folklore this problem is known as _simulating auxiliary inputs_.
This idea of simulating auxiliary information turns out to be a very usefull tool, finding applications in complexity theory, cryptography, pseudorandomness and zero-knowledge. In this paper we revisit this problem, achieving the following results:

(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).

(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).

Security requirement of White-Box Cryptography (WBC) is that it should protect secret key from white-box security model permits an adversary who is able to entirely control execution of the cryptographic algorithm and its environment. It has already been demonstrated that most of the primitive is vulnerable to algebraic attacks in the white-box security perspective. In recently, a new Differential Computation Analysis (DCA) attack is proposed that thwarts White-Box AES (WB-AES) by monitoring accessed memory information during execution of the algorithm. Though it requires ability to estimate internal information of memory pattern, the attack retrieves secret key with a few attempts. In addition it is proposed that the existence of vulnerability on hardware implementation of WB-AES against to Differential Power Analysis (DPA) attack. In this paper, we propose DPA based attack which directly exploits intermediate value of WB-AES computation without effort to take memory data. And demonstrate its practicability with respect to public software implementation of WB-AES. Additionally, we investigate vulnerability of our target primitive on DPA by acquiring actual power consumption traces of software implementation.

ePrint Report
Healing the Hill Cipher, Improved Approach to Secure Modified Hill against Zero-plaintext Attack
Mohammad Hadi Valizadeh

Hill Cipher is a symmetric cryptosystem that was claimed to suffer from known-plaintext attack for many years. Different methods have been proposed to make this cipher more secure against known attacks. The introduced classic Hill cipher by Tourani and Falahati in 2011 that was devised in two variants and based upon affine transformation, was considered to be more secure against known attacks. Recently, this well modified Hill cipher is claimed to be vulnerable to zero-plaintext attack. In this paper, by using a chaotic map and scrambling methods, a novel cryptosystem based on Tourani and Falahati Hill cipher is presented which overcomes the zero-plaintext attack. The proposed Hill cipher is more reliable and faster.

Founded in 2015, ISARA Corporation builds quantum resistant cryptographic solutions for today’s computing ecosystems. The ISARA Corporation vision is a world where consumers, enterprises and governments can benefit from the power of quantum computing with protection against quantum attacks. Our team has expertise building high performance cryptographic systems for constrained environments. We’re proud to be part of a collaborative effort with academic and standards institutions to raise awareness of the potential for quantum threats, and design and implement quantum resistant solutions for classical data security systems that will work globally.

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

The Digital Security group from the Radboud University, Nijmegen invites applications for two positions for postdoctoral researchers in the area of cryptography and security of embedded systems. The posts are for 2 years but can be extended upon positive evaluation. Salaries are internationally competitive and candidates moving to the Netherlands from abroad may qualify for a tax incentive scheme, where 30% of your income is tax free.

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

ePrint Report
Constant-Round Maliciously Secure Two-Party Computation in the RAM Model
Carmit Hazay, Avishay Yanai

The random-access memory (RAM) model of computation allows program constant-time memory lookup and is more applicable in practice today, covering many important algorithms. This is in contrast to the classic setting of secure 2-party computation (2PC) that mostly follows the approach for which the desired functionality must be represented as a boolean circuit. In this work we design the first constant round maliciously secure two-party protocol in the RAM model. Our starting point is the garbled RAM construction of Gentry et al. (EUROCRYPT 2014) that readily induces a constant round semi-honest two-party protocol for any RAM program assuming identity-based encryption schemes. We show how to enhance the security of their construction into the malicious setting while facing several challenges that stem due to handling the data memory. Next, we show how to apply our techniques to a more recent garbled RAM construction by Garg et al. (STOC 2015) that is based on one-way functions.

ePrint Report
Multi-Key Homomorphic Authenticators
Dario Fiore, Aikaterini Mitrokotsa, Luca Nizzardo, Elena Pagnin

Homomorphic authenticators (HAs) enable a client to authenticate a large collection of data elements $m_1, . . . , m_t$ and outsource them, along with the corresponding authenticators, to an untrusted server. At any later point, the server can generate a $short$ authenticator $\sigma_{f, y}$ vouching for the correctness of the output $y$ of a function $f$ computed on the outsourced data, i.e., $y = f(m_1,...,m_t)$. Recently researchers have focused on HAs as a solution, with minimal communication and interaction, to the problem of delegating computation on outsourced data. The notion of HAs studied so far, however, only supports executions (and proofs of correctness) of computations over data authenticated by a single user. Motivated by realistic scenarios (ubiquitous computing, sensor networks, etc.) in which large datasets include data provided by multiple users, we study the concept of $multi-key$ $homomorphic$ $authenticators$. In a nutshell, multi-key HAs are like HAs with the extra feature of allowing the holder of public evaluation keys to compute on data authenticated under different secret keys. In this paper, we introduce and formally define multi-key HAs. Secondly, we propose a construction of a multi-key homomorphic signature based on standard lattices and supporting the evaluation of circuits of bounded polynomial depth. Thirdly, we provide a construction of multi-key homomorphic MACs based only on pseudorandom functions and supporting the evaluation of low-degree arithmetic circuits. Albeit being less expressive and only secretly verifiable, the latter construction presents interesting efficiency properties.

—The empowerment in network on chip (NOC) and System on chip (SOC) in Microelectronics and Sensors have developed the various wireless communication Network technologies. In the past few years, many researchers have been focusing on building system architecture of network monitoring to improve the technical requirement specially designed for network security. Less research was found in providing the strong biometric based network security system to provide bulletproof security. The popular MIPS based cryptography processor is used for hardware and software products and standards require big cryptography keys length for higher security level. The major weakness of Normal cryptography system based on asymmetric algorithms need the storage of secret keys. Stored keys are often protected by poorly selected user passwords that can either be guessed or obtained through brute force attacks. Combining biometric with MIPS cryptography processor is as a possible solution. In this paper I propose a new approach to network security using MIPS based crypto processor based on contactless palm vein biometric system. This approach takes into account NOC constraints and its topology. It provides more security with less key length and there is no need to store any private key anywhere.

ePrint Report
Proofs of Data Residency: Checking whether Your Cloud Files Have Been Relocated
Hung Dang, Erick Purwanto, Ee-Chien Chang

While cloud storage services offer manifold benefits such as cost-effectiveness or elasticity, there also exists various security and privacy concerns. Among such concerns, we pay our primary attention to data residency – a notion that requires outsourced data to be retrievable in its entirety from local drives of a storage server in-question. We formulate such notion under a security model called Proofs of Data Residency (PoDR). PoDR can be employed to check whether the data is replicated across different storage servers, or combined with storage server geolocation to “locate” the data in the cloud. We make key observations that the data residency checking protocol should exclude all server-side computation and each challenge should ask for no more than a single atomic fetching operation. We illustrate challenges and subtleties in protocol design by showing potential attacks to naive constructions. Next, we present a secure PoDR scheme structured as a timed challenge-response protocol. Two implementation variants of the proposed solution, namely N-ResCheck and E-ResCheck, describe an interesting use-case of trusted computing, in particular the use of Intel SGX, in cryptographic timed challenge-response protocols whereby having the verifier co-locating with the prover offers security enhancement. Finally, we conduct extensive experiments to exhibit potential attacks to insecure constructions and validate the performance as well as the security of our solution.

ePrint Report
Blind Web Search: How far are we from a privacy preserving search engine?
Gizem S. \c{C}etin, Wei Dai, Yark{\i}n Dor\"{o}z, William J. Martin, Berk Sunar

Recent rapid progress in fully homomorphic encryption (FHE) and somewhat homomorphic encryption (SHE) has catalyzed renewed efforts to develop efficient privacy preserving protocols. Several works have already appeared in the literature that provide solutions to these problems by employing FHE or SHE techniques.
In this work, we focus on a natural application where privacy is a major concern: web search. An estimated 5 billion web queries are processed by the world's leading search engines each day. It is no surprise, then, that
privacy-preserving web search was proposed as the paragon FHE application in Gentry's seminal FHE paper.
Indeed, numerous proposals have emerged in the intervening years that attack various privatized search problems over encrypted user data, e.g. private information retrieval (PIR). Yet, there is no known work that focuses on implementing a completely blind web search engine using an FHE/SHE construction. In this work, we focus first
on single keyword queries with exact matches, aiming toward real-world viability. We then discuss multiple-keyword
searches and tackle a number of issues currently hindering practical implementation,
such as communication and computational efficiency.

ePrint Report
Almost-Optimally Fair Multiparty Coin-Tossing with Nearly Three-Quarters Malicious
Bar Alon, Eran Omri

An $\alpha$-fair coin-tossing protocol allows a set of mutually distrustful
parties to generate a uniform bit, such that no efficient adversary can bias
the output bit by more than $\alpha$. Cleve [STOC 1986] has shown that if half
of the parties can be corrupted, then, no $r$-round coin-tossing protocol is
$o(1/r)$-fair. For over two decades the best known $m$-party protocols,
tolerating up to $t\geq m/2$ corrupted parties, were only
$O(t/\sqrt{r})$-fair.
In a surprising result,
Moran, Naor, and Segev [TCC 2009] constructed an $r$-round two-party
$O(1/r)$-fair coin-tossing protocol, i.e., an optimally fair protocol.
Beimel, Omri, and Orlov [Crypto 2010] extended the results of Moran et al.~to
the {\em multiparty setting} where strictly fewer than 2/3 of the parties are
corrupted. They constructed a $2^{2^k}/r$-fair $r$-round $m$-party protocol,
tolerating up to $t=\frac{m+k}{2}$ corrupted parties.

Recently, in a breakthrough result, Haitner and Tsfadia [STOC 2014] constructed an $O(\log^3(r)/r)$-fair (almost optimal) three-party coin-tossing protocol. Their work brings forth a combination of novel techniques for coping with the difficulties of constructing fair coin-tossing protocols. Still, the best coin-tossing protocols for the case where more than 2/3 of the parties may be corrupted (and even when $t=2m/3$, where $m>3$) were $\theta(1/\sqrt{r})$-fair. We construct an $O(\log^3(r)/r)$-fair $m$-party coin-tossing protocol, tolerating up to $t$ corrupted parties, whenever $m$ is constant and $t<3m/4$.

Recently, in a breakthrough result, Haitner and Tsfadia [STOC 2014] constructed an $O(\log^3(r)/r)$-fair (almost optimal) three-party coin-tossing protocol. Their work brings forth a combination of novel techniques for coping with the difficulties of constructing fair coin-tossing protocols. Still, the best coin-tossing protocols for the case where more than 2/3 of the parties may be corrupted (and even when $t=2m/3$, where $m>3$) were $\theta(1/\sqrt{r})$-fair. We construct an $O(\log^3(r)/r)$-fair $m$-party coin-tossing protocol, tolerating up to $t$ corrupted parties, whenever $m$ is constant and $t<3m/4$.

ePrint Report
Efficient Batched Oblivious PRF with Applications to Private Set Intersection
Vladimir Kolesnikov, Ranjit Kumaresan, Mike Rosulek, Ni Trieu

We describe a lightweight protocol for oblivious evaluation of a pseudorandom function (OPRF) in the presence of semi-honest adversaries. In an OPRF protocol a receiver has an input $r$; the sender gets output $s$ and the receiver gets output $F(s,r)$, where $F$ is a pseudorandom function and $s$ is a random seed. Our protocol uses a novel adaptation of 1-out-of-2 OT-extension protocols, and is particularly efficient when used to generate a large batch of OPRF instances. The cost to realize $m$ OPRF instances is roughly the cost to realize $3.5 m$ instances of standard 1-out-of-2 OTs (using state-of-the-art OT extension).

We explore in detail our protocol's application to semi-honest secure private set intersection (PSI). The fastest state-of-the-art PSI protocol (Pinkas et al., Usenix 2015) is based on efficient OT extension. We observe that our OPRF can be used to remove their PSI protocol's dependence on the bit-length of the parties' items. We implemented both PSI protocol variants and found ours to be 3.1--3.6$\times$ faster than Pinkas et al.\ for PSI of 128-bit strings and sufficiently large sets. Concretely, ours requires only 3.8 seconds to securely compute the intersection of $2^{20}$-size sets, regardless of the bitlength of the items. For very large sets, our protocol is only $4.3\times$ slower than the {\em insecure} na\"{\i}ve hashing approach for PSI.

We explore in detail our protocol's application to semi-honest secure private set intersection (PSI). The fastest state-of-the-art PSI protocol (Pinkas et al., Usenix 2015) is based on efficient OT extension. We observe that our OPRF can be used to remove their PSI protocol's dependence on the bit-length of the parties' items. We implemented both PSI protocol variants and found ours to be 3.1--3.6$\times$ faster than Pinkas et al.\ for PSI of 128-bit strings and sufficiently large sets. Concretely, ours requires only 3.8 seconds to securely compute the intersection of $2^{20}$-size sets, regardless of the bitlength of the items. For very large sets, our protocol is only $4.3\times$ slower than the {\em insecure} na\"{\i}ve hashing approach for PSI.

ePrint Report
On the Practical (In-)Security of 64-bit Block Ciphers: Collision Attacks on HTTP over TLS and OpenVPN
Karthikeyan Bhargavan, Gaëtan Leurent

While modern block ciphers, such as AES, have a block size of at least
128 bits, there are many 64-bit block ciphers, such as 3DES and
Blowfish, that are still widely supported in Internet security
protocols such as TLS, SSH, and IPsec. When used in CBC mode, these
ciphers are known to be susceptible to collision attacks when they are
used to encrypt around $2^{32}$ blocks of data (the so-called birthday
bound). This threat has traditionally been dismissed as impractical
since it requires some prior knowledge of the plaintext and even then,
it only leaks a few secret bits per gigabyte. Indeed, practical
collision attacks have never been demonstrated against any mainstream
security protocol, leading to the continued use of 64-bit ciphers on
the Internet.

In this work, we demonstrate two concrete attacks that exploit collisions on short block ciphers. First, we present an attack on the use of 3DES in HTTPS that can be used to recover a secret session cookie. Second, we show how a similar attack on Blowfish can be used to recover HTTP BasicAuth credentials sent over OpenVPN connections. In our proof-of-concept demos, the attacker needs to capture about 785GB of data, which takes between 19-38 hours in our setting. This complexity is comparable to the recent RC4 attacks on TLS: the only fully implemented attack takes 75 hours. We evaluate the impact of our attacks by measuring the use of 64-bit block ciphers in real-world protocols. We discuss mitigations, such as disabling all 64-bit block ciphers, and report on the response of various software vendors to our responsible disclosure of these attacks.

In this work, we demonstrate two concrete attacks that exploit collisions on short block ciphers. First, we present an attack on the use of 3DES in HTTPS that can be used to recover a secret session cookie. Second, we show how a similar attack on Blowfish can be used to recover HTTP BasicAuth credentials sent over OpenVPN connections. In our proof-of-concept demos, the attacker needs to capture about 785GB of data, which takes between 19-38 hours in our setting. This complexity is comparable to the recent RC4 attacks on TLS: the only fully implemented attack takes 75 hours. We evaluate the impact of our attacks by measuring the use of 64-bit block ciphers in real-world protocols. We discuss mitigations, such as disabling all 64-bit block ciphers, and report on the response of various software vendors to our responsible disclosure of these attacks.