International Association
for Cryptologic Research

We present efficient protocols for amortized secure multiparty computation with penalties and secure cash distribution, of which poker is a prime example. Our protocols have an initial phase where the parties interact with a cryptocurrency network, that then enables them to interact only among themselves over the course of playing many poker games in which money changes hands. The high efficiency of our protocols is achieved by harnessing the power of stateful contracts. Compared to the limited expressive power of Bitcoin scripts, stateful contracts enable richer forms of interaction between standard secure computation and a cryptocurrency. We formalize the stateful contract model and the security notions that our protocols accomplish, and provide proofs in the simulation paradigm. Moreover, we provide a reference implementation in Ethereum/Solidity for the stateful contracts that our protocols are based on. We also adapt our off-chain cash distribution protocols to the special case of stateful duplex micropayment channels, which are of independent interest. In comparison to Bitcoin based payment channels, our duplex channel implementation is more efficient and has additional features.

A witness encryption (WE) scheme can take any NP statement as a public-key and use it to encrypt a message. If the statement is true then it is possible to decrypt the message given a corresponding witness, but if the statement is false then the message is computationally hidden. Ideally, the encryption procedure should run in polynomial time, but it is also meaningful to define a weaker notion, which we call non-trivially exponentially efficient WE (XWE), where the encryption run-time is only required to be much smaller than the trivial $2^{m}$ bound for NP relations with witness size $m$. We show how to construct such XWE schemes for all of NP with encryption run-time $2^{m/2}$ under the sub-exponential learning with errors (LWE) assumption. For NP relations that can be verified in NC1 (e.g., SAT) we can also construct such XWE schemes under the sub-exponential Decisional Bilinear Diffie-Hellman (DBDH) assumption. Although we find the result surprising, it follows via a very simple connection to attribute-based encryption.

We also show how to upgrade the above results to get non-trivially exponentially efficient indistinguishability obfuscation for null circuits (niO), which guarantees that the obfuscations of any two circuits that always output 0 are indistinguishable. In particular, under the LWE assumptions we get a XniO scheme where the obfuscation time is $2^{n/2}$ for all circuits with input size $n$. It is known that in the case of indistinguishability obfuscation (iO) for all circuits, non-trivially efficient XiO schemes imply fully efficient iO schemes (Lin et al., PKC '16) but it remains as a fascinating open problem whether any such connection exists for WE or niO.

Lastly, we explore a potential approach toward constructing fully efficient WE and niO schemes via multi-input ABE.

We introduce an algorithm called Cycle Slicer that gives new solutions to two important problems in format-preserving encryption: domain targeting and domain completion. In domain targeting, where we wish to use a cipher on domain $\mathcal{X}$ to construct a cipher on a smaller domain $\mathcal{S} \subseteq \mathcal{X}$, using Cycle Slicer leads to a significantly more efficient solution than Miracle and Yilek's Reverse Cycle Walking (ASIACRYPT 2016) in the common setting where the size of $\mathcal{S}$ is large relative to the size of $\mathcal{X}$. In domain completion, a problem recently studied by Grubbs, Ristenpart, and Yarom (EUROCRYPT 2017) in which we wish to construct a cipher on domain $\mathcal{X}$ while staying consistent with existing mappings in a lazily-sampled table, Cycle Slicer provides an alternative construction with better worst-case running time than the Zig-Zag construction of Grubbs et al. Our analysis of Cycle Slicer uses a refinement of the Markov chain techniques for analyzing matching exchange processes, which were originally developed by Czumaj and Kutylowski (Rand. Struct. \& Alg. 2000).

We give computationally efficient zero-knowledge proofs of knowledge for arithmetic circuit satisfiability over a large field. For a circuit with N addition and multiplication gates, the prover only uses O(N) multiplications and the verifier only uses O(N) additions in the field. If the commitments we use are statistically binding, our zero-knowledge proofs have unconditional soundness, while if the commitments are statistically hiding we get computational soundness. Our zero-knowledge proofs also have sub-linear communication if the commitment scheme is compact.

Our construction proceeds in three steps. First, we give a zero-knowledge proof for arithmetic circuit satisfiability in an ideal linear commitment model where the prover may commit to secret vectors of field elements, and the verifier can receive certified linear combinations of those vectors. Second, we show that the ideal linear commitment proof can be instantiated using error-correcting codes and non-interactive commitments. Finally, by choosing efficient instantiations of the primitives we obtain linear-time zero-knowledge proofs.

We study the problem of non-interactive multiparty computation (NI-MPC) where a group of completely asynchronous parties can evaluate a function over their joint inputs by sending a single message to an evaluator who computes the output. Previously, the only general solutions to this problem that resisted collusions between the evaluator and a set of parties were based on multi-input functional encryption and required the use of complex correlated randomness setup.

In this work, we present a new solution for NI-MPC against arbitrary collusions using a public-key infrastructure (PKI) setup supplemented with a common random string. A PKI is, in fact, the minimal setup that one can hope for in this model in order to achieve a meaningful ``best possible'' notion of security, namely, that an adversary that corrupts the evaluator and an arbitrary set of parties only learns the residual function obtained by restricting the function to the inputs of the uncorrupted parties. Our solution is based on indistinguishability obfuscation and DDH both with sub-exponential security. We extend this main result to the case of general interaction patterns, providing the above best possible security that is achievable for the given interaction.

Our main result gives rise to a novel notion of (public-key) multiparty obfuscation, where $n$ parties can independently obfuscate program modules $M_i$ such that the obfuscated modules, when put together, exhibit the functionality of the program obtained by ``combining'' the underlying modules $M_i$. This notion may be of independent interest.

We carry out a concrete security analysis of signature schemes obtained from five-move identification protocols via the Fiat-Shamir transform. Concretely, we obtain tightly-secure signatures based on the computational Diffie-Hellman (CDH), the short-exponent CDH, and the Factoring (FAC) assumptions. All our signature schemes have tight reductions to search problems, which is in stark contrast to all known signature schemes obtained from the classical Fiat-Shamir transform (based on three-move identification protocols), which either have a non-tight reduction to a search problem, or a tight reduction to a (potentially) stronger decisional problem. Surprisingly, our CDH-based scheme turns out to be (a slight simplification of) the Chevallier-Mames signature scheme (CRYPTO 05), thereby providing a theoretical explanation of its tight security proof via five-move identification protocols.

Cryptographic implementations are vulnerable to Side Channel Analysis (SCA), where an adversary exploits physical phenomena such as the power consumption to reveal sensitive information. One of the most widely studied countermeasures against SCA are masking schemes. A masking scheme randomizes intermediate values thereby making physical leakage from the device harder to exploit. Central to any masking scheme is the use of randomness, on which the security of any masked algorithm heavily relies. But since randomness is very costly to produce in practice, it is an important question whether we can reduce the amount of randomness needed while still guaranteeing standard security properties such as $t$-probing security introduced by Ishai, Sahai and Wagner (CRYPTO 2003). In this work we study the question whether internal randomness can be re-used by several gadgets, thereby reducing the total amount of randomness needed. We provide new techniques for masking algorithms that significantly reduce the amount of randomness and achieve better overall efficiency than known constructions for values of $t$ that are most relevant for practical settings.

Chen et al. proved that two variants of the two-round n-bit Even-Mansour ciphers are secure up to 22n/3 queries against distinguish- ing attacks. These constructions can be regarded as minimal two-round Even-Mansour ciphers delivering security beyond the birthday bound, since removing any component from the ciphers causes security to drop back to 2n/2 queries. On the other hand, for the minimal two-round con- structions, the proved lower bounds on the product of data and time complexities (DT) against the other attacks including key recovery at- tacks is 2n. However, an attack requiring DT close to the lower bound has not been known yet, and thus its tightness is not clear. In this pa- per, we propose new key recovery attacks on the two minimal two-round Even-Mansour ciphers by using the advanced meet-in-the-middle tech- nique. In particular, we introduce novel matching techniques called partial invariable pair and matching with input-restricted public permutation , which enable us to compute one of permutations without knowing a part of the key information. Moreover, we present two improvements of the proposed attack: one significantly reduces data complexity and the other reduces time complexity by dynamically finding partial invariant pairs. Compared with the previously known attacks, when blocksize is 64 bits, our attacks drastically reduce the required data from 245 to 226 with keeping time complexity required by the previous attacks, though our attack requires chosen plaintexts. Importantly, the previous attacks never break the birthday barrier of data complexity due to the usage of multicollisions in the internal state. Furthermore, by increasing time complexity up to 262, the required data is further reduced to 28, and DT = 270 which is close to the proved lower bound 264. We show that our data-optimized attack on the minimal two-round Even-Mansour ci- phers requires DT = 2n+6 in general cases. This implies that adding one round does not sufficiently improve the security against key recovery attacks of the Even-Mansour ciphers.

Proxy re-encryption (PRE) is a cryptographic primitive introduced by Blaze, Bleumer and Strauss to provide delegation of decryption rights. A semi-trusted proxy agent re-encrypts ciphertexts under the public key of Alice into ciphertexts under the public key of Bob, without learning anything about the underlying message. In IWSEC 2017, Kuchta et al. presented a pairing-free certificateless proxy re-encryption scheme, and claimed that their scheme is the first to provide the certificateless property without resorting to pairing. They proved their construction is CCA-secure in the random oracle model, under the Computational Diffie-Hellman assumption. In this work, we show that the recently proposed construction of Kuchta et al. is vulnerable to several attacks.

The security models for Authenticated Key Exchange do not consider leakages on pre–computed ephemeral data before their use in sessions. We investigate the consequences of such leakages and point out damaging consequences. As an illustration, we show the HMQV–C protocol vulnerable to a Bilateral Unknown Key Share (BUKS) and an Unilateral Unknown Key Share (UUKS) Attack, when precomputed ephemeral public keys are leaked. We point out some shades in the seCK model in multi–certification authorities setting. We propose an enhancement of the seCK model, which uses a liberal instantiation of the certification systems model from the ASICS framework, and allows reveal queries on precomputed ephemeral (public and private) keys. We propose a new protocol, termed eFHMQV, which in addition to provide the same efficiency as MQV, is particularly suited for implementations wherein a trusted device is used together with untrusted host machine. In such settings, the non–idle time computational effort of the device safely reduces to one digest computation, one integer multiplication, and one integer addition. The eFHMQV protocol meets our security definition, under the Random Oracle Model and the Gap Diffie–Hellman assumption.

Hardware Trojans have gained high attention in academia, industry and by government agencies. The effective detection mechanisms and countermeasures against such malicious designs are only possible when there is a deep understanding of how hardware Trojans can be built in practice. In this work, we present a mechanism which shows how easily a stealthy hardware Trojan can be inserted in a provably-secure side-channel analysis protected implementation. Once the Trojan is triggered, the malicious design exhibits exploitable side-channel leakage leading to successful key recovery attacks. Such a Trojan does not add or remove any logic (even a single gate) to the design which makes it very hard to detect. In ASIC platforms, it is indeed inserted by subtle manipulations at the sub-transistor level to modify the parameters of a few transistors. The same is applicable on FPGA applications by changing the routing of particular signals, leading to null resource utilization overhead. The underlying concept is based on a secure masked hardware implementation which does not exhibit any detectable leakage. However, by running the device at a particular clock frequency one of the requirements of the underlying masking scheme is not fulfilled anymore, i.e., the Trojan is triggered, and the device's side-channel leakage can be exploited. Although as a case study we show an application of our designed Trojan on an FPGA-based threshold implementation of the PRESENT cipher, our methodology is a general approach and can be applied on any similar circuit.

The current paper presents a new quantum algorithm for finding multicollisions, often denoted by $l$-collisions, where an $l$-collision for a function is a set of $l$ distinct inputs having the same output value. Although it is fundamental in cryptography, the problem of finding multicollisions has not received much attention \emph{in a quantum setting}. The tight bound of quantum query complexity for finding $2$-collisions of random functions has been revealed to be $\Theta(N^{1/3})$, where $N$ is the size of a codomain. However, neither the lower nor upper bound is known for $l$-collisions. The paper first integrates the results from existing research to derive several new observations, e.g.~$l$-collisions can be generated only with $O(N^{1/2})$ quantum queries for a small constant $l$. Then a new quantum algorithm is proposed, which finds an $l$-collision of any function that has a domain size $l$ times larger than the codomain size. A rigorous proof is given to guarantee that the expected number of quantum queries is $O\left( N^{(3^{l-1}-1)/(2 \cdot 3^{l-1})} \right)$ for a small constant $l$, which matches the tight bound of $\Theta(N^{1/3})$ for $l=2$ and improves the known bounds, say, the above simple bound of $O(N^{1/2})$.

Event date: 16 November to 18 November 2017
Submission deadline: 30 September 2017

Event date: 1 May to 10 May 2018
Submission deadline: 25 September 2017
Notification: 15 January 2018

LearnRnD is the highly scientific research firm based on collaborative R&D knowledge findings, among the major universities, R&D organizations of the Asia, Africa and Europe regions. LearnRnD is the purely scientific firm to enhance the Research culture without financial constraints and geographical boundaries. Our main focus is to enhance the visibility of latest cutting edge research. Moreover, our all research contents are peer review and authentic material. Researchers make proper review before uploading the contents. On other hand, we also collaborate with different institutions and research labs like Stanford University, Cornel University, Seoul University, and National university of Singapore on different levels such as academic research publishers like Springer, Nature, IEEE, ACM, Taylor and Francis. So, LearnRnD is the unique multi-disciplinary R&D Company with latest research of Natural science, Engineering and Information Technology, Future innovations, Medical Science, Biohacking Economic Development,Bio warefares, English Literal and Social Science.

Closing date for applications: 19 December 2017

Contact: Software Development Engineer-Cryptography

Your responsibilities include:

- owning the complete software development life-cycle; defining, prioritizing, designing, implementing, and testing new features for Cryptography.

Skills require in Java or C++

Contact:admin (at) learnrnd.com

More information: http://learnrnd.com

Surrey Centre for Cyber Security (SCCS) and Department of Computer Science at the University of Surrey seeks to recruit an outstanding post-doctoral researcher in the fields of Security and Privacy for a full-time position, starting in November/December 2017. The initial contract is for 24 months.

The research fellow will be working under supervision of Dr Mark Manulis in the interdisciplinary EPSRC funded project “TAPESTRY: Trust, Authentication and Privacy over a DeCentralised Social Registry” that develops and demonstrates new cryptographic protocols to enable people, businesses and services to connect safely online.

Successful applicants will have core skills in the design, analysis and implementation of privacy-oriented cryptographic protocols (e.g. zero-knowledge protocols) and experience in the implementation of distributed/web-based applications (incl. browser plugins). They are expected to hold a PhD, be able to drive their own research direction within the scope of the project and engage with project partners. Funding for conference travel and other dissemination activities will be provided through the project.

Surrey Centre for Cyber Security is an Academic Centre of Excellence in Cyber Security Research recognized by the British Government. More information about SCCS can be found at http://sccs.surrey.ac.uk/

Closing date for applications: 7 October 2017

Contact: Informal inquiries can be sent to Dr Mark Manulis (m.manulis (at) surrey.ac.uk)

More information: https://jobs.surrey.ac.uk/vacancy.aspx?ref=079116-R

Stipends are available for students to attend RWC 2018. This year, there are three sources of stipends: The general fund for RWC stipends from the IACR/RWC Committee, a fund from the NSF for US students, and a fund from Google to encourage female participation. The deadline for stipend applications is October 1. Information about applying can be found at https://rwc.iacr.org/2018/stipends.html.

The contributed talks committee is seeking submissions to be considered for presentation at RWC. The deadline for full consideration is October 5. Information is available at https://rwc.iacr.org/2018/contributed.html.

RWC 2018 will be held in Zurich, Switzerland, January 10-12.

The elegant “five-card trick” of den Boer (EUROCRYPT 1989) allows two players to securely compute a logical AND of two private bits, using five playing cards of symbols $\heartsuit$ and $\clubsuit$. Since then, card-based protocols have been successfully put to use in classroom environments, vividly illustrating secure multiparty computation – and evoked research on the minimum number of cards needed for several functionalities.

Securely computing arbitrary circuits needs protocols for negation, AND and bit copy in committed-format, where outputs are commitments again. Negation just swaps the bit's cards, computing AND and copying a bit $n$ times can be done with six and $2n+2$ cards, respectively, using the simple protocols of Mizuki and Sone (FAW 2009).

Koch, Walzer and Härtel (ASIACRYPT 2015) showed that five cards suffice for computing AND in finite runtime, albeit using relatively complex and unpractical shuffle operations. In this paper, we show that if we restrict shuffling to closed permutation sets, the six-card protocol is optimal in the finite-runtime setting. If we additionally assume a uniform distribution on the permutations in a shuffle, we show that restart-free four-card AND protocols are impossible. These shuffles are easy to perform even in an actively secure manner (Koch and Walzer, ePrint 2017).

For copying bit commitments, the protocol of Nishimura et al. (ePrint 2017) needs only $2n+1$ cards, but performs a number of complex shuffling steps that is only finite in expectation. We show that it is impossible to go with less cards. If we require an a priori bound on the runtime, we show that the $(2n+2)$-card protocol is card-minimal.

In the setting of secure multiparty computation, a set of mutually distrustful parties carry out a joint computation of their inputs, without revealing anything but the output. Over recent years, there has been tremendous progress towards making secure computation practical, with great success in the two-party case. In contrast, in the multiparty case, progress has been much slower, even for the case of semi-honest adversaries.

In this paper, we consider the case of constant-round multiparty computation, via the garbled circuit approach of BMR (Beaver et al., STOC 1990). In recent work, it was shown that this protocol can be efficiently instantiated for semi-honest adversaries (Ben-Efraim et al., ACM CCS 2016). However, it scales very poorly with the number of parties, since the cost of garbled circuit evaluation is quadratic in the number of parties, per gate. Thus, for a large number of parties, it becomes expensive. We present a new way of constructing a BMR-type garbled circuit that can be evaluated with only a constant number of operations per gate. Our constructions use key-homomorphic pseudorandom functions (one based on DDH and the other on Ring-LWE) and are concretely efficient. In particular, for a large number of parties (e.g., 100), our new circuit can be evaluated faster than the standard BMR garbled circuit that uses only AES computations. Thus, our protocol is an important step towards achieving concretely efficient large-scale multiparty computation for Internet-like settings (where constant-round protocols are needed due to high latency).

Oblivious Parallel RAM (OPRAM), first proposed by Boyle, Chung, and Pass, is the natural parallel extension of Oblivious RAM (ORAM). OPRAM provides a powerful cryptographic building block for hiding the access patterns of programs to sensitive data, while preserving the paralellism inherent in the original program. All prior OPRAM schemes adopt a single metric of ``simulation overhead'' that characterizes the blowup in parallel runtime, assuming that oblivious simulation is constrained to using the same number of CPUs as the original PRAM.

In this paper, we ask whether oblivious simulation of PRAM programs can be further sped up if the OPRAM is allowed to have more CPUs than the original PRAM. We thus initiate a study to understand the true depth of OPRAM schemes (i.e., when the OPRAM may have access to unbounded number of CPUs). On the upper bound front, we construct a new OPRAM scheme that gains a logarithmic factor in depth and without incurring extra blowup in total work in comparison with the state-of-the-art OPRAM scheme. On the lower bound side, we demonstrate fundamental limits on the depth any OPRAM scheme --- even when the OPRAM is allowed to have an unbounded number of CPUs and blow up total work arbitrarily. We further show that our upper bound result is optimal in depth for a reasonably large parameter regime that is of particular interest in practice.