International Association
for Cryptologic Research

To accomplish effective privacy protection in smart grid systems, various approaches were proposed combining information security technology with the smart grid\'s new features. Diao et al. proposed a privacy-preserving scheme using linkable anonymous credential based on CL signature, and demonstrated its identity anonymity, message authentication and traceability of broken smart meters. In this paper, a forgery attack is presented to point out the protocol dissatisfies message authentication and unforgeability. We hold the idea that this scheme doesn\'t have basic safety requirements and application value.

The Department of Computer Science and Engineering, HKUST (http://www.cse.ust.hk/) will have substantiation-track faculty openings in the area of cyber security at all levels of Professor, Associate Professor and Assistant Professor for the 2016-2017 academic year.

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.

The Department of Computer Science and Engineering, HKUST (http://www.cse.ust.hk/) will have substantiation-track faculty openings at all levels of Professor, Associate Professor and Assistant Professor for the 2016-2017 academic year. Cybersecurity is a major area with several faculty openings.

The McEliece cryptosystem is an asymmetric type of cryptography based on error correction code. The classical McEliece used irreducible binary Goppa code which considered unbreakable until now especially with parameter [1024, 524, and 101], but it is suffering from large public key matrix which leads to be difficult to be used practically. In this work Irreducible and Separable Goppa codes have been introduced. The Irreducible and Separable Goppa codes used are with flexible parameters and dynamic error vectors. A Comparison between Separable and Irreducible Goppa code in McEliece Cryptosystem has been done. For encryption stage, to get better result for comparison, two types of testing have been chosen; in the first one the random message is constant while the parameters of Goppa code have been changed. But for the second test, the parameters of Goppa code are constant (m=8 and t=10) while the random message have been changed. The results show that the time needed to calculate parity check matrix in separable are higher than the one for irreducible McEliece cryptosystem, which is considered expected results due to calculate extra parity check matrix in decryption process for g2(z) in separable type, and the time needed to execute error locator in decryption stage in separable type is better than the time needed to calculate it in irreducible type. The proposed implementation has been done by Visual studio C#.

Cao-Cao\'s recently proposed an identity-based proxy signature scheme

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.

A silicon Physical Unclonable Function (PUF) is a hardware security primitive which implements a unique and unclonable function on a chip which, given a challenge as input, computes a response by measuring and leveraging (semiconductor process) manufacturing variations which differ from PUF to PUF. In this paper, we observe that by equipping a PUF with a small, constant-sized, tamper-resistant state, whose content cannot be modified, but can be read by adversaries, new and powerful cryptographic applications of PUFs become feasible. In particular, we show a new hardware concept which we call a Programmable Logically erasable PUF (PLayPUF). Its distinctive feature is that it allows the selective erasure of single challenge-response pairs (CRPs) without altering any other PUF-CRPs. The selective erasure of a CRP can be programmed a-priori by using a counter to indicate how many times the CRP can be read out before erasure.

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.

Oblivious RAM (ORAM) garbles read/write operations by a client (to

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.

We provide a symbolic model for multi-party computation

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.

A Probabilistically Checkable Proof (PCP) allows a randomized verifier, with oracle access to a purported proof, to probabilistically verify an input statement of the form ``$x\\in L$\'\' by querying only few bits of the proof. A zero-knowledge PCP (ZKPCP) is a PCP with the additional guarantee that the view of any verifier querying a bounded number of proof bits can be efficiently simulated given the input $x$ alone, where the simulated and actual views are statistically close.

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}

Error correcting codes, though powerful, are only applicable in scenarios where the adversarial channel does not introduce ``too many\" errors into the codewords. Yet,

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.

In the study of differential privacy, composition theorems (starting with the original paper of Dwork, McSherry, Nissim, and Smith (TCC\'06)) bound the degradation of privacy when composing several differentially private algorithms. Kairouz, Oh, and Viswanath (ICML\'15) showed how to compute the optimal bound for composing k arbitrary (epsilon,delta)-differentially private algorithms. We characterize the optimal composition for the more general case of k arbitrary (epsilon_1, delta_1),...,(epsilon_k, delta_k)-differentially private algorithms where the privacy parameters may differ for each algorithm in the composition. We show that computing the optimal composition in general is #P-complete. Since computing optimal composition exactly is infeasible (unless FP=#P), we give an approximation algorithm that computes the composition to arbitrary accuracy in polynomial time. The algorithm is a modification of Dyer\'s dynamic programming approach to approximately counting solutions to knapsack problems (STOC\'03).

Rational proofs, introduced by Azar and Micali (STOC 2012) are a variant of interactive proofs in which the prover is neither honest nor malicious, but rather rational. The advantage of rational proofs over their classical counterparts is that they allow for extremely low communication and verification time. In recent work, Guo et al. (ITCS 2014) demonstrated their relevance to delegation of computation by showing that, if the rational prover is additionally restricted to being computationally bounded, then every language in NC1 admits a single-round delegation scheme that can be verified in sublinear time.

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.

A redactable signature scheme (RSS) allows removing parts of a signed message by any party without invalidating the respective signature. State-of-the-art constructions thereby focus on messages represented by one specific data structure, e.g., lists, sets or trees, and adjust the security model accordingly. To overcome the necessity for this myriad of models, we present a general framework covering arbitrary data-structures and even more sophisticated possibilities. For example, we cover fixed elements which must not be redactable and dependencies between elements. Moreover, we introduce the notion of designated redactors, i.e., the signer can give some extra information to selected entities which become redactors. In practice, this often allows to obtain more efficient schemes. We then present two RSSs; one for sets and one for lists, both constructed from any EUF-CMA secure signature scheme and indistinguishable cryptographic accumulators in a black-box way and show how the concept of designated redactors can be used to increase the efficiency of these schemes. Finally, we present a black-box construction of a designated redactor RSS by combining an RSS for sets with non-interactive zero knowledge proof systems. All the three constructions presented in this paper provide transparency, which is an important property, but quite hard to achieve, as we also conceal the length of the original message and the positions of the redactions.

An elliptic curve addition law is said to be complete if it correctly computes the sum of any two points in the elliptic curve group. One of the main reasons for the increased popularity of Edwards curves in the ECC community is that they can allow a complete group law that is also relatively efficient (e.g., when compared to all known addition laws on Edwards curves). Such complete addition formulas can simplify the task of an ECC implementer and, at the same time, can greatly reduce the potential vulnerabilities of a cryptosystem. Unfortunately, until now, complete addition laws that are relatively efficient have only been proposed on curves of composite order and have thus been incompatible with all of the currently standardized prime order curves.

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.

The possibility of basing the security of cryptographic objects on the (minimal) assumption that $\\NP \\nsubseteq \\BPP$ is at the very heart of

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.

Since the seminal work of Garg \\etal (FOCS\'13) in which they proposed the first candidate construction for indistinguishability obfuscation (iO for short), iO has become a central cryptographic primitive with numerous applications. The security of the proposed construction of Garg \\etal and its variants are proved based on multi-linear maps (Garg \\etal Eurocrypt\'13) and their idealized model called the graded encoding model (Brakerski and Rothblum TCC\'14 and Barak \\etal Eurocrypt\'14).

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.

Non-malleable codes are a generalization of classical error-correcting codes where the act of ``corrupting\'\' a codeword is replaced by a ``tampering\'\' adversary. Non-malleable codes guarantee that the message contained in the tampered codeword is either the original message m, or a completely unrelated one. In the common split-state model, the codeword consists of multiple blocks (or states) and each block is tampered with independently.

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.

Submission: 12 February 2016
Notification: 1 March 2016
From May 30 to May 30
Location: Xi'an, China
More Information: https://sites.google.com/site/iotpts2016/

Guess-and-determine attacks are based on guessing a subset of internal state bits and subsequently using these guesses together with the cipher\'s output function to determine the value of the remaining state. These attacks have been successfully employed to break NFSR-based stream ciphers. The complexity of a guess-and-determine attack is directly related to the number of state bits used in the output function. Consequently, an opportunity exits for efficient cryptanalysis of NFSR-based stream ciphers if NFSRs used can be transformed to derive an equivalent stream cipher with a simplified output function.

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.

G\\\"o\\\"os, Pitassi and Watson (ITCS, 2015) have recently introduced the notion of \\emph{Zero-Information Arthur-Merlin Protocols} (ZAM). In this model, which can be viewed as a private version of the standard Arthur-Merlin communication complexity game, Alice and Bob are holding a pair of inputs $x$ and $y$ respectively, and Merlin, the prover, attempts to convince them that some public function $f$ evaluates to 1 on $(x,y)$. In addition to standard completeness and soundness, G\\\"o\\\"os et al., require an additional ``zero-knowledge\'\' property which asserts that on each yes-input, the distribution of Merlin\'s proof leaks no information about the inputs $(x,y)$ to an external observer.

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.