International Association
for Cryptologic Research

The technology of homomorphic encryption has improved rapidly in a few years. The cutting edge implementations are efficient enough to use in practical applications. Recently, Cheon et al. (ASIACRYPT'17) proposed a homomorphic encryption scheme which supports an arithmetic of approximate numbers over encryption. This scheme shows the current best performance in computation over the real numbers, but its implementation could not employ core optimization techniques based on the Residue Number System (RNS) decomposition and the Number Theoretic Transformation (NTT).

In this paper, we present a variant of approximate homomorphic encryption which is optimal for implementation on standard computer system. We first introduce a new structure of ciphertext modulus which allows us to use both the RNS decomposition of cyclotomic polynomials and the NTT conversion on each of the RNS components. We also suggest new approximate modulus switching procedures without any RNS composition. Compared to previous exact algorithms requiring multi-precision arithmetic, our algorithms can be performed by using only word size (64-bit) operations.

Our scheme achieves a significant performance gain from its full RNS implementation. For example, compared to the earlier implementation, our implementation showed speed-ups 17.3, 6.4, and 8.3 times for decryption, constant multiplication, and homomorphic multiplication, respectively, when the dimension of a cyclotomic ring is 32768. We also give experimental result for evaluations of some advanced circuits used in machine learning or statistical analysis. Finally, we demonstrate the practicability of our library by applying to machine learning algorithm. For example, our single core implementation takes 1.8 minutes to build a logistic regression model from encrypted data when the dataset consists of 575 samples, compared to the previous best result 3.5 minutes using four cores.

ElGamal cryptosystem is typically developed in the multiplicative group $\mathbb{Z}_p^*$ ($p$ is a prime number), but it can be applied to the other groups in which discrete logarithm problem should be computationally infeasible. Practically, instead of ElGamal in $\mathbb Z_p^*$, various variants such as ECElGamal (ElGamal in elliptic curve group), CRTElGamal (ElGamal in subgroup of $\mathbb Z_n^*$ where $n=pq$ and $p,q,(p-1)/2,(q-1)/2$ are primes) have already been used for the semantic security. In this paper, for the fast decryption, we reduced the private CRT exponent $x_p$ ($= x mod (p - 1)$) and $x_q$ ($= x mod (q-1)$)maintaining full sized private exponent $x$ ($0<x<n$) in CRTElGamal as reducing $d_p$ ($= d mod (p - 1)$) and $d_q$ ($= d mod (q-1)$) in RSA for the fast decryption. (i.e. as in rebalanced RSA). In this case, unlike rebalanced RSA, decryption of CRTElGamal can be done faster without losing of encryption speed. As a result, it is possible to propose the fast public key cryptosystem that has fast encryption and fast decryption.

Any $d$-regular graph on $n$ vertices with spectral expansion $\lambda$ satisfying $n = \Omega(d^3\log(d)/\lambda)$ yields a $O\left(\frac{\lambda^{3/2}}{d}\right)$-non-malleable code in the split-state model.

We propose FO-AKE , a generic construction of two-message authenticated key exchange (AKE) from any passively secure public key encryption (PKE) in the quantum random oracle model (QROM). Whereas previous AKE constructions relied on a Diffie-Hellman key exchange or required the underlying PKE scheme to be perfectly correct, our transformation allows arbitrary PKE schemes with non-perfect correctness. Furthermore, we avoid the use of (quantum-secure) digital signature schemes which are considerably less efficient than their PKE counterparts. As a consequence, we can instantiate our AKE transformation with any of the submissions to the recent NIST post-quantum competition, e.g., ones based on codes and lattices. FOAKE can be seen as a generalization of the well known Fujisaki-Okamoto transformation (for building actively secure PKE from passively secure PKE) to the AKE setting. Therefore, as a helper result, we also provide an alternative security proof for the Fujisaki-Okamoto transformation in the QROM that deals with possible correctness errors.

In distributed pseudorandom functions (DPRFs), a PRF secret key $SK$ is secret shared among $N$ servers so that each server can locally compute a partial evaluation of the PRF on some input $X$. A combiner that collects $t$ partial evaluations can then reconstruct the evaluation $F(SK,X)$ of the PRF under the initial secret key. So far, all non-interactive constructions in the standard model are based on lattice assumptions. One caveat is that they are only known to be secure in the static corruption setting, where the adversary chooses the servers to corrupt at the very beginning of the game, before any evaluation query. In this work, we construct the first fully non-interactive adaptively secure DPRF in the standard model. Our construction is proved secure under the LWE assumption against adversaries that may adaptively decide which servers they want to corrupt. We also extend our construction in order to achieve robustness against malicious adversaries.

Motivated by the potential cryptographic application of building a directed transitive signature scheme, the search for a group with infeasible inversion was initiated in the theses of Hohenberger and Molnar in 2003. Later it was also shown to provide a broadcast encryption scheme by Irrer et al. (2004). However, to date the only case of a group with infeasible inversion is implied by the much stronger primitive of self-bilinear map constructed by Yamakawa et al. (2014) based on the hardness of factoring and indistinguishability obfuscation (iO).

We propose a candidate trapdoor group with infeasible inversion without using the heavy machinery of iO. The underlying group is isomorphic to the ideal class group of an imaginary quadratic order, and is represented by the elliptic curve isogeny graph. The hardness of group inversion relies on the conjectured hardness of several problems on the isogeny graphs defined over composite moduli with unknown factorization.

Today’s blockchains do not scale in a meaningful sense. As more nodes join the system, the efficiency of the system (computation, communication, and storage) degrades, or at best stays constant. A leading idea for enabling blockchains to scale efficiency is the notion of sharding: different subsets of nodes handle different portions of the blockchain, thereby reducing the load for each individual node. However, existing sharding proposals achieve efficiency scaling by compromising on trust - corrupting the nodes in a given shard will lead to the permanent loss of the corresponding portion of data. We observe that sharding is similar to replication coding, which is known to be inefficient and fragile in the coding theory community. In this paper, we demonstrate a new protocol for coded storage and computation in blockchains. In particular, we propose PolyShard: “polynomially coded sharding” scheme that achieves information-theoretic upper bounds on the efficiency of the storage, system throughput, as well as on trust, thus enabling a truly scalable system. We provide simulation results that numerically demonstrate the performance improvement over state of the arts, and the scalability of the PolyShard system. Finally, we discuss potential enhancements, and highlight practical considerations in building such a system.

We introduce the forward secure signature scheme XMSS$^{+}$ and present an implementation for smart cards. It is based on the hash-based signature scheme XMSS. In contrast to the only previous implementation of a hash-based signature scheme on smart cards by Rohde et al., we solve the problem of on-card key generation. Compared to XMSS, we reduce the key generation time from $\mathcal{O}(n)$ to $\mathcal{O}(\sqrt{n})$, where $n$ is the number of signatures that can be created with one key pair. To the best of our knowledge this is the first implementation of a forward secure signature scheme and the first full implementation of a hash-based signature scheme on smart cards. The resulting runtimes are comparable to those of RSA and ECDSA on the same device. This shows the practicality of forward secure signature schemes, even on constrained devices.

In a delegatable anonymous credential system, participants may use their credentials anonymously as well as anonymously delegate them to other participants. Such systems are more usable than traditional anonymous credential systems because a popular credential issuer can delegate some of its responsibilities without compromising users' privacy. They also provide stronger privacy guarantees than traditional anonymous credential systems because the identities of credential issuers are hidden. The identity of a credential issuer may convey information about a user's identity even when all other information about the user is concealed.

The only previously known constructions of delegatable anonymous credentials were prohibitively inefficient. They were based on non-interactive zero-knowledge (NIZK) proofs. In this paper, we provide a simple construction of delegatable anonymous credentials and prove its security in the generic group model. Our construction is direct, not based on NIZK proofs, and is therefore considerably more efficient. In fact, in our construction, only five group elements are needed per link to represent an anonymous credential chain.

Our main building block is a new type of signature scheme, a mercurial signature, which allows a signature $\sigma$ on a message $M$ under public key $\mathsf{pk}$ to be transformed into a signature $\sigma'$ on an equivalent but unlinkable message $M'$ under an equivalent but unlinkable public key $\mathsf{pk}'$.

Threshold implementations have emerged as one of the most popular masking countermeasures for hardware implementations of cryptographic primitives. In the original version of TI, the number of input shares was dependent on both security order $d$ and algebraic degree of a function $t$, namely $td + 1$. At CRYPTO 2015, a new method was presented yielding to a $d$-th order secure implementation using $d+1$ input shares. In this work, we first provide a construction for $d+1$ TI sharing which achieves the minimal number of output shares for any $n$-input Boolean function of degree $t=n-1$. Furthermore, we present a heuristic for minimizing the number of output shares for higher order $td + 1$ TI. Finally, we demonstrate the applicability of our results on $d+1$ and $td+1$ TI versions, for first- and second-order secure, low-latency and low-energy implementations of the PRINCE block cipher.

Motivatedbytheoreticalandpracticalconsiderations,anim- portant line of research is to design secure computation protocols that only make black-box use of cryptography. An important component in nearly all the black-box secure computation constructions is a black- box commit-and-prove protocol. A commit-and-prove protocol allows a prover to commit to a value and prove a statement about this value while guaranteeing that the committed value remains hidden. A black- box commit-and-prove protocol implements this functionality while only making black-box use of cryptography. In this paper, we build several tools that enable constructions of round- optimal, black-box commit and prove protocols. In particular, assuming injective one-way functions, we design the first round-optimal, black- box commit-and-prove arguments of knowledge satisfying strong privacy against malicious verifiers, namely: – Zero-knowledge in four rounds and, – Witness indistinguishability in three rounds. Prior to our work, the best known black-box protocols achieving commit- and-prove required more rounds. We additionally ensure that our protocols can be used, if needed, in the delayed-input setting, where the statement to be proven is decided only towards the end of the interaction. We also observe simple applications of our protocols towards achieving black-box four-round constructions of extractable and equivocal commitments. We believe that our protocols will provide a useful tool enabling several new constructions and easy round-efficient conversions from non-black- box to black-box protocols in the future.

We pursue to formalize and instantiate a secure bidirectional channel with message franking properties. Under this model a sender may send an abusive message to the receiver and the latter wish to open it in a verifiable way to a third party. Potential malicious behavior of a sender requires message franking protocols resistant to sending messages that cannot be opened later by the receiver. An adversary impersonated by the receiver may also try to open messages that have not been sent by the sender. Wrapping a message franking protocol in a secure channel requires a more delicate treatment in order to avoid drops or replay of messages and out-of-order delivery. To the best of our knowledge we are the first to model the security of a message franking channel, which apart from integrity, confidentiality, resistance to drops, relays and out-of-order delivery is sender and receiver binding: a sender cannot send a message which cannot be opened in a verifiable way later by the receiver, and the receiver cannot claim a message that had not been truly sent by the receiver. Finally, we instantiate a bidirectional message franking channel from symmetric primitives and analyze its security.

In this work, we introduce the notion of registration-based encryption (RBE for short) with the goal of removing the trust parties need to place in the private-key generator in an IBE scheme. In an RBE scheme, users sample their own public and secret keys. There will also be a ``key curator'' whose job is only to aggregate the public keys of all the registered users and update the short public parameter whenever a new user joins the system. Encryption can still be performed to a particular ecipient using the recipient's identity and any public parameters released subsequent to the recipient's registration. Decryption requires some auxiliary information connecting users' public (and secret) keys to the public parameters. Because of this, as the public parameters get updated, a decryptor may need to obtain a few additional auxiliary information for decryption. More formally, if $n$ is the total number of identities and $\kappa$ is the security parameter, we require the following.

Efficiency requirements: (1) A decryptor only needs to obtain updated auxiliary information for decryption at most $O(\log n)$ times in its lifetime, (2) each of these updates are computed by the key curator in time $poly(\kappa,\log n)$, and (3) the key curator updates the public parameter upon the registration of a new party in time $poly(\kappa,\log n)$. Properties (2) and (3) require the key curator to have \emph{random} access to its data.

Compactness requirements: (1) Public parameters are always at most $poly(\kappa,\log n)$ bit, and (2) the total size of updates a user ever needs for decryption is also at most $poly(\kappa,\log n)$ bits.

We present feasibility results for constructions of RBE based on indistinguishably obfuscation. We further provide constructions of \emph{weakly efficient} RBE, in which the registration step is done in $poly(\kappa, n)$, based on CDH, Factoring or LWE assumptions. Note that registration is done only once per identity, and the more frequent operation of generating updates for a user, which can happen more times, still runs in time $poly(\kappa,\log n)$. We leave open the problem of obtaining standard RBE (with $poly(\kappa,\log n)$ registration time) from standard assumptions.

Bitcoin, the most popular blockchain system, does not scale even under very optimistic assumptions. Lightning networks, a layer on top of Bitcoin, composed of one-to-one lightning channels make it scale to up to 105 Million users.

Recently, Duplex Micropayment Channel factories have been proposed based on opening multiple one-to-one payment channels at once. Duplex Micropayment Channel factories rely on time-locks to update and close their channels. This mechanism yields to situation where users funds time-locking for long periods increases with the lifetime of the factory and the number of users. This makes DMC factories not applicable in real-life scenarios.

In this paper, we propose the first channel factory construction, the Lightning Factory that offers a constant collateral cost, independent of the lifetime of the channel and members of the factory.

We compare our proposed design with Duplex Micropayment Channel factories, obtaining better performance results by a factor of more than 3000 times in terms of the worst-case constant collateral cost incurred when malicious users use the factory. The message complexity of our factory is $n$ where Duplex Micropayment Channel factories need $n^2$ messages where $n$ is the number of users. Moreover, our factory copes with an infinite number of updates while in Duplex Micropayment Channel factories the number of updates is bounded by the initial time-lock.

Finally, we discuss the necessity for our Lightning Factories of BNN, a non-interactive aggregate signature cryptographic scheme, and compare it with Schnorr and ECDSA schemes used in Bitcoin and Duplex Micropayment Channels.

Collaboration between financial institutions helps to improve detection of fraud. However, exchange of relevant data between these institutions is often not possible due to privacy constraints and data confidentiality. An important example of relevant data for fraud detection is given by a transaction graph, where the nodes represent bank accounts and the links consist of the transactions between these accounts. Previous works show that features derived from such graphs, like PageRank, can be used to improve fraud detection. However, each institution can only see a part of the whole transaction graph, corresponding to the accounts of its own customers.In this research a new method is described, making use of secure multiparty computation (MPC) techniques, allowing multiple parties to jointly compute the PageRank values of their combined transaction graphs securely, while guaranteeing that each party only learns the PageRank values of its own accounts and nothing about the other transaction graphs. In our experiments this method is applied to graphs containing up to tens of thousands of nodes. The execution time scales linearly with the number of nodes, and the method is highly parallelizable. Secure multiparty PageRank is feasible in a realistic setting with millions of nodes per party by extrapolating the results from our experiments.

Registration is now open for Real World Crypto 2019, at https://rwc.iacr.org/2019/registration.html. RWC2019 will be held January 9-11 in San Jose, CA, USA.

The School of Computing and Information Technology is seeking a full time Continuing Position Lecturer (Level B) to provide development, teaching and research within the Bachelor of Computer Science (majoring Cybersecurity). The candidate is expected to be a research active in the area of Cybersecurity, and he/she is equipped with sufficient experience for teaching undergraduate and postgraduate studies.

You will be prompted to respond to the selection criteria as part of the online application process, based on the position description below. You will be able to save your application at any time and submit at a later date if required, you will only be able to do this before the closing date of the position.

Closing date for applications: 29 October 2018

Contact: Professor Willy Susilo (wsusilo (at) uow.edu.au)

More information: https://www.uow.edu.au/content/groups/public/@web/@recruit/@pd/documents/doc/uow252142.pdf

Singapore University of Technology and Design (SUTD) is a young university which was established in collaboration with MIT. iTrust is a Cyber Security Research Center which has the world\'s best facilities in cyber-physical systems (CPS) including testbeds for Secure Water Treatment (SWaT), Water Distribution (WADI), Electric Power and Intelligent Control (EPIC), and IoT. (See more info at https://itrust.sutd.edu.sg/research/testbeds/.)

I am looking for PhD interns with interest in cyber-physical system security (IoT, water, power grid, transportation, and autonomous vehicle etc.). The attachment will be at least 3 months. Allowance will be provided for local expenses.

Interested candidates please send your CV with a research statement to Prof. Jianying Zhou. Only short-listed candidates will be contacted for interview.

Closing date for applications: 8 January 2019

Contact: Prof. Jianying Zhou

More information: http://jianying.space/

New York University Abu Dhabi (NYUAD) seeks to recruit tenure-track faculty at Assistant Professor level in the Computer Engineering (CmpE) program who are distinguished in both their research and teaching. As a part of a major multi-year growth plan, the following areas are of particular interest at the present time: Cyber Security, Computer Networks, and Machine Learning.

NYUAD has close collaborations with the faculty and students of the NYU Tandon School of Engineering and has access to world-class research centers in cyber security (cyber.nyu.edu) and wireless communications (wireless.engineering.nyu.edu), among others. Our students are drawn from around the world and surpass all traditional academic benchmarks.

Candidates with a strong record of interdisciplinary research in emerging areas are preferred. Candidates must have a PhD degree in CmpE or related disciplines and must have the ability to develop and lead high-quality research and attract external funding.

Review of applications will begin November 1, 2018, and shortlisted candidates will be invited to visit the campuses in New York and Abu Dhabi at the beginning of the Spring 2019 semester. Candidates should submit a cover letter, curriculum vitae, and statements of teaching and research interests. To complete the online process, applicants will be prompted to enter the names and email addresses of at least three referees. Each referee will be contacted to upload their reference letter only if the candidate is shortlisted for further consideration.

To apply for this position, please visit apply.interfolio.com/52923. If you have any questions, please e-mail nyuad.engineering (at) nyu.edu.

Closing date for applications: 1 November 2018

Contact: nyuad.engineering (at) nyu.edu

More information: https://apply.interfolio.com/52923

TENURE-TRACK FACULTY POSITIONS

The Department of Applied Mathematics at the Naval Postgraduate School, in Monterey, California invites applications for one or more tenure-track positions at the level of Assistant Professor (exceptional candidates at all levels may be considered).

We seek candidates who can teach a wide range of courses (course listings can be found at https://math.nps.edu) primarily as on-campus lectures, but sometimes delivered by VTE. Candidates will also be expected to conduct an active program of research and to direct student theses.

The successful candidate for this position will possess a doctorate in Mathematics or a closely related area from an accredited university. Teaching experience is highly desirable and evidence of exceptional research potential is necessary. All areas of research will be considered, but preference will be given to candidates specializing in areas of computational discrete mathematics that support existing departmental research efforts (cryptography, graph theory, network science, etc.). Effective teaching is essential and candidates must have excellent communication skills (both written and oral), as well as strong interpersonal and organizational abilities. U. S. citizenship is required.

Applicants must submit a cover letter describing their qualifications for these positions, a comprehensive curriculum vitae or resume and contact and e-mail address information for a minimum of three references. The application material must clearly state the applicant’s citizenship. Applications may be submitted electronically or in hard copy to:

Review of applications will begin immediately and applications will be accepted until the positions are filled. Candidates applying by November 1, 2018 will receive full consideration.

The Naval Postgraduate School is an equal opportunity employer. For additional information about NPS, please refer to the website at http://www.nps.edu

Closing date for applications: 1 February 2019

Contact: Prof. Frank Giraldo

Email: fxgirald (at) nps.edu (preferred)

Postal Mail:

Department of Applied Mathematics

Naval Postgraduate School

Monterey, CA 93943-5121

USA

More information: https://math.nps.edu