IACR News
Here you can see all recent updates to the IACR webpage. These updates are also available:
02 November 2015
Haipeng Qu, Peng Shang, Xi-Jun Lin, and Lin Sun
31 October 2015
The Hong Kong University of Science and Technology, Hong Kong
Salary is highly competitive and will be commensurate with qualifications and experience. Fringe benefits include medical/dental benefits and annual leave. Housing will also be provided where applicable.
Applications including a cover letter, curriculum vitae (including the names and contact information of at least three referees), a research statement and a teaching statement (all in PDF format) should be sent through e-mail to csrecruit (at) cse.ust.hk. Priority will be given to applications received by 15 December 2015. Applicants will be promptly acknowledged through e-mail upon receiving the electronic application material.
Department of Computer Science and Engineering, The Hong Kong University of Science and Technology
30 October 2015
Thuraya M. Qaradaghi, Newroz N. Abdulrazaq
Jayaprakash Kar
and claim that the scheme is provably secure in random oracle model. In this paper we have reviewed the scheme and proven that the scheme is vulnerable to chosen message attack under the defined security model. To prevent this attack, we propose an improved version of the scheme. A Proxy multi-signature scheme allows an authorized proxy signer to sign on a message on behalf of a group of original signers.
Chenglu Jin, Xiaolin Xu, Wayne Burleson, Ulrich Rührmair, Marten van Dijk
We show PLayPUFs can realize forward and {\\it backward} secure key management schemes for public key encryption. The new notion of backward security informally means that even if an attacker uncovers a session key through the key management interface, the legitimate user will detect this leakage before he will ever use the session key. Backward security and its implementation via PLayPUFs allow the construction of novel, self-recovering certificate authorities (CAs) without relying on a digital master key. Our new CAs immediately detect key exposure through their interfaces, and recover from it without stopping their service, and without ever issuing certificates based on such exposed keys. This is a crucial step forward in implementing secure key management. We deliver a full proof-of-concept implementation of our new scheme on FPGA together with detailed performance data, as well as formal definitions of our new concepts, including the first definition of stateful PUFs.
Binyi Chen; Huijia Lin; Stefano Tessaro
access a remote storage server or a random-access memory) so that an
adversary observing the garbled access sequence cannot infer any
information about the original operations, other than their overall
number. This paper considers the natural setting of Oblivious
Parallel RAM (OPRAM) recently introduced by Boyle, Chung, and
Pass (TCC 2016A), where $m$ clients simultaneously access in
parallel the storage server. The clients are additionally
connected via point-to-point links to coordinate their
accesses. However, this additional inter-client communication must
also remain oblivious.
The main contribution of this paper is twofold: We construct the
first OPRAM scheme that (nearly) matches the storage and
server-client communication complexities of the most efficient
single-client ORAM schemes. Our scheme is based on an extension of
Path-ORAM by Stefanov et al (CCS 2013). Moreover, we present a
generic transformation turning any (single-client) ORAM scheme
into an OPRAM scheme.
HUI ZHAO, Kouichi Sakurai
based on linear secret-sharing scheme, and prove that this model is com-
putationally sound: if there is an attack in the computational world, then
there is an attack in the symbolic (abstract) model. Our original contri-
bution is that we deal with the uniformity properties, which cannot be
described using a single execution trace, while considering an unbounded
number of sessions of the protocols in the presence of active and adaptive
adversaries.
Yuval Ishai; Mor Weiss; Guang Yang
Originating from the first ZKPCP construction of Kilian et~al.(STOC~\'97), all previous constructions relied on locking schemes, an unconditionally secure oracle-based commitment primitive.
The use of locking schemes makes the verifier \\emph{inherently} adaptive, namely, it needs to make at least two rounds of queries to the proof.
Motivated by the goal of constructing non-adaptively verifiable ZKPCPs, we suggest a new technique for compiling standard PCPs into ZKPCPs. Our approach is based on leakage-resilient circuits, which are circuits that withstand certain ``side-channel\'\' attacks, in the sense that these attacks reveal nothing about the (properly encoded) input, other than
the output. We observe that the verifier\'s oracle queries constitute a side-channel attack on the wire-values of the circuit verifying membership in $L$, so a PCP constructed from a circuit resilient against such attacks would be ZK. However, a leakage-resilient circuit evaluates the desired function \\emph{only if} its input is properly encoded, i.e., has a specific structure, whereas by generating a ``proof\'\' from the wire-values of the circuit on an \\emph{ill-formed} ``encoded\'\' input, one can cause the verification to accept inputs $x\\notin L$ \\emph{with probability 1}. We overcome this obstacle by constructing leakage-resilient circuits with the additional guarantee that ill-formed encoded inputs are detected. Using this approach, we obtain the following results:
\\begin{itemize}
\\sloppy
\\item We construct the first \\emph{witness-indistinguishable} PCPs (WIPCP) for NP with non-adaptive verification. WIPCPs relax ZKPCPs by only requiring that different witnesses be indistinguishable. Our construction combines strong leakage-resilient circuits as above with the PCP of Arora and Safra (FOCS \'92), in which queries correspond to side-channel attacks by shallow circuits, and with correlation bounds for shallow circuits due to Lovett and Srivinasan (RANDOM \'11).
\\item Building on these WIPCPs, we construct non-adaptively verifiable \\emph{computational} ZKPCPs for NP in the common random string model, assuming that one-way functions exist.
\\item As an application of the above results, we construct \\emph{3-round} WI and ZK proofs for NP in a distributed setting in which the prover and the verifier interact with multiple servers of which $t$ can be corrupted, and the total communication involving the verifier consists of $\\poly\\log\\left(t\\right)$ bits.
\\end{itemize}
Nishanth Chandran; Bhavana Kanukurthi; Srinivasan Raghuraman
the question of having guarantees even in the face of many errors is well-motivated. Non-malleable codes, introduced by Dziembowski, Pietrzak and Wichs (ICS 2010), address precisely this question. Such codes guarantee that even if an adversary completely over-writes the codeword, he cannot transform it into a
codeword for a related message. Not only is this a creative solution to the problem mentioned above, it is also a very meaningful one. Indeed, non-malleable codes have inspired a rich body of theoretical constructions as well as applications to tamper-resilient cryptography, CCA2 encryption schemes and so on.
Another remarkable variant of error correcting codes were introduced by Katz and Trevisan (STOC 2000) when they explored the question of decoding ``locally\". Locally decodable codes are coding schemes which have an additional ``local decode\" procedure: in order to decode a bit of the message, this procedure accesses only a few bits of the codeword. These codes too have received tremendous attention from researchers and have applications to various primitives in cryptography such as private information retrieval. More recently, Chandran, Kanukurthi and Ostrovsky (TCC 2014) explored the converse problem of making the ``re-encoding\" process local. Locally updatable codes have an additional ``local update\" procedure: in order to update a bit of the message, this procedure accesses/rewrites only a few bits of the codeword.
At TCC 2015, Dachman-Soled, Liu, Shi and Zhou initiated the study of locally decodable and updatable non-malleable codes, thereby combining all the important properties mentioned above into one tool. Achieving locality and non-malleability is non-trivial. Yet, Dachman-Soled \\etal \\ provide a meaningful definition of local non-malleability and provide a construction that satisfies it. Unfortunately, their construction is secure only in the computational setting.
In this work, we construct information-theoretic non-malleable codes which are locally updatable and decodable. Our codes are non-malleable against $\\s{F}_{\\textsf{half}}$, the class of tampering functions where each function is arbitrary but acts (independently) on two separate parts of the codeword. This is one of the strongest adversarial models for which explicit constructions of standard non-malleable codes (without locality) are known. Our codes have $\\bigo(1)$ rate and locality $\\bigo(\\lambda)$, where $\\lambda$ is the security parameter. We also show a rate $1$ code with locality $\\omega(1)$ that is non-malleable against bit-wise tampering functions. Finally, similar to Dachman-Soled \\etal, our work finds applications to information-theoretic secure RAM computation.
Jack Murtagh, Salil Vadhan
Siyao Guo; Pavel Hubacek; Alon Rosen; Margarita Vald
We extend the Guo et al. result by constructing a single-round delegation scheme with sublinear verification for all languages in P. Our main contribution is the introduction of {\\em rational sumcheck protocols}, which are a relaxation of classical sumchecks, a crucial building block for interactive proofs. Unlike their classical counterparts, rational sumchecks retain their (rational) soundness properties, {\\em even if the polynomial being verified is of high degree} (in particular, they do not rely on the Schwartz-Zippel lemma). This enables us to bypass the main efficiency bottleneck in classical delegation schemes, which is a result of sumcheck protocols being inapplicable to the verification of the computation\'s input level.
As an additional contribution we study the possibility of using rational proofs as efficient blocks within classical interactive proofs. Specifically, we show a composition theorem for substituting oracle calls in an interactive proof by a rational protocol.
David Derler, Henrich C. Pöhls, Kai Samelin, Daniel Slamanig
Joost Renes, Craig Costello, Lejla Batina
In this paper we present optimized addition formulas that are complete on every prime order short Weierstrass curve defined over a field k with char(k) not 2 or 3. Compared to their incomplete counterparts, these formulas require a larger number of field additions, but interestingly require fewer field multiplications. We discuss how these formulas can be used to achieve secure, exception-free implementations on all of the prime order curves in the NIST (and many other) standards.
Tianren Liu; Vinod Vaikuntanathan
complexity-theoretic cryptography. Unfortunately, most known results along these lines are negative, showing that, assuming widely believed complexity-theoretic conjectures, there are no reductions from an $\\NP$-hard problem to the task of breaking certain cryptographic schemes. For example, the work of Brassard (FOCS 1979) showed that one-way permutations cannot be based on $\\NP$-hardness; Akavia, Goldreich, Goldwasser and Moshkovitz (STOC 2006) and Bogdanov and Brzuska (TCC 2015) showed that size-verifiable one-way functions cannot be based on $\\NP$-hardness; and Bogdanov and Lee (CRYPTO 2013) showed that even simple homomorphic encryption schemes cannot be based on $\\NP$-hardness.
We make progress along this line of inquiry by showing that single-server private information retrieval schemes cannot be based on $\\NP$-hardness, unless the polynomial hierarchy collapses.
Our result is tight in terms of both the correctness and the privacy parameter of the PIR scheme.
Mohammad Mahmoody; Ameer Mohammed; Soheil Nematihaji; Rafael Pass; Abhi Shelat
Whether or not iO could be based on standard and well-studied hardness assumptions has remain an elusive open question.
In this work we prove \\emph{lower bounds} on the assumptions that imply iO in a black-box way, based on computational assumptions. Note that any lower bound for iO needs to somehow rely on computational assumptions, because if $\\P = \\NP$ then statistically secure iO does exist. Our results are twofold:
1. There is no fully black-box construction of iO from (exponentially secure) collision-resistant hash functions unless the polynomial hierarchy collapses. Our lower bound extends to (separate iO from) any primitive implied by a random oracle in a black-box way.
2. Let $\\cP$ be any primitive that exists relative to random trapdoor permutations, the generic group model for any finite abelian group, or degree-$O(1)$ graded encoding model for any finite ring. We show that achieving a black-box construction of iO from $\\cP$ is \\emph{as hard as} basing public-key cryptography on one-way functions.
In particular, for any such primitive $\\cP$ we present a constructive procedure that takes any black-box construction of iO from $\\cP$ and turns it into a a construction of semantically secure public-key encryption form any one-way functions.
Our separations hold even if the construction of iO from $\\cP$ is \\emph{semi-}black-box (Reingold, Trevisan, and Vadhan, TCC\'04) and the security reduction could access the adversary in a non-black-box way.
Divesh Aggarwal; Shashank Agrawal; Divya Gupta; Hemanta K. Maji; Omkant Pandey; Manoj Prabhakaran
The central goal in the split-state model is to construct high rate non-malleable codes against all functions with only two states (which are necessary). Following a series of long and impressive line of work, constant rate, two-state, non-malleable codes against all functions were recently achieved by Aggarwal et al. (STOC 2015). Though constant, the rate of all known constructions in the split state model, is very far from optimal (even with more than two states).
In this work, we consider the question of improving the rate of split-state non-malleable codes. In the ``information theoretic\'\' setting, it is not possible to go beyond rate 1/2. We therefore focus on the standard computational setting. In this setting, each tampering function is required to be efficiently computable, and the message in the tampered codeword is required to be either the original message m or a ``computationally\'\' independent one.
In this setting, assuming only the existence of one-way functions, we present a compiler which converts any poor rate, two-state, (sufficiently strong) non-malleable code into a rate 1, two-state, computational non-malleable code. These parameters are asymptotically optimal. Furthermore, for the qualitative optimality of our result, we generalize the result of Cheraghchi and Guruswami (ITCS 2014) to show that the existence of one-way functions is necessary to achieve rate >1/2 for such codes.
Our compiler requires a stronger form of non-malleability, called augmented non-malleability. This notion requires a stronger simulation guarantee for non-malleable codes and simplifies their modular usage in cryptographic settings where composition occurs. Unfortunately, this form of non-malleability is neither straightforward nor generally guaranteed by known results. Nevertheless, we prove this stronger form of non-malleability for the two-state construction of Aggarwal, Dodis, and Lovett (STOC 14). This result is of independent interest.
29 October 2015
Xi'an, China, May 30
Notification: 1 March 2016
From May 30 to May 30
Location: Xi'an, China
More Information: https://sites.google.com/site/iotpts2016/
Gefei Li, Yuval Yarom, Damith C. Ranasinghe
In this paper, we present a new technique for transforming NFSRs. We show how we can use this technique to transform NFSRs to equivalent NFSRs with simplified output functions. We explain how such transformations can assist in cryptanalysis of NFSR-based ciphers and demonstrate the application of the technique to successfully cryptanalyse the lightweight cipher Sprout. Our attack on Sprout has a time complexity of 2^70.87, which is 2^3.64 times better than any published non-TMD attack, and requires only 164 bits of plaintext-ciphertext pairs.
Benny Applebaum; Pavel Raykov
In this paper, we relate this new notion to the well-studied model of \\emph{Private Simultaneous Messages} (PSM) that was originally suggested by Feige, Naor and Kilian (STOC, 1994). Roughly speaking, we show that the randomness complexity of ZAM essentially corresponds to the communication complexity of PSM, and that the communication complexity of ZAM essentially corresponds to the randomness complexity of PSM. This relation works in both directions where different variants of PSM are being used. Consequently, we derive better upper-bounds on the communication-complexity of ZAM for arbitrary functions. As a secondary contribution, we reveal new connections between different variants of PSM protocols which we believe to be of independent interest.