International Association
for Cryptologic Research

Different transforms used in binding a secret key to correlated physical-identifier outputs are compared. Decorrelation efficiency is the metric used to determine transforms that give highly-uncorrelated outputs. Scalar quantizers are applied to transform outputs to extract uniformly distributed bit sequences to which secret keys are bound. A set of transforms that perform well in terms of the decorrelation efficiency is applied to ring oscillator (RO) outputs to improve the uniqueness and reliability of extracted bit sequences, to reduce the hardware area and information leakage about the key and RO outputs, and to maximize the secret-key length. Low-complexity error-correction codes are proposed to illustrate two complete key-binding systems with perfect secrecy, and better secret-key and privacy-leakage rates than existing methods. A reference hardware implementation is also provided to demonstrate that the transform-coding approach occupies a small hardware area.

Recently, Faust et al. (TCC'14) introduced the notion of continuous non-malleable codes (CNMC), which provides stronger security guarantees than standard non-malleable codes, by allowing an adversary to tamper with the codeword in continuous way instead of one-time tampering. They also showed that CNMC with information theoretic security cannot be constructed in 2-split-state tampering model, and presented a construction of the same in CRS (common reference string) model using collision-resistant hash functions and non-interactive zero-knowledge proofs.

In this work, we ask if it is possible to construct CNMC from weaker assumptions. We answer this question by presenting lower as well as upper bounds. Specifically, we show that it is impossible to construct 2-split-state CNMC, with no CRS, for one-bit messages from any falsifiable assumption, thus establishing the lower bound. We additionally provide an upper bound by constructing 2-split-state CNMC for one-bit messages, assuming only the existence of a family of injective one way functions.

We also present a construction of 4-split-state CNMC for multi-bit messages in CRS model from the same assumptions. Additionally, we present definitions of the following new primitives: (1) One-to-one commitments, and (2) Continuous Non-Malleable Randomness Encoders, which may be of independent interest.

The Cryptography, Security, and Privacy (CrySP) research group at the University of Waterloo is seeking applications for a postdoctoral research position in the field of data security and applied cryptography, preferably on topics related differential privacy and secure computation. This position will be held in the Cheriton School of Computer Science.

Applicants must hold a PhD in a related field, and should have a proven research record, as demonstrated by publications in top security and privacy or database venues (such as Oakland, CCS, SIGMOD, VLDB) and/or top venues specific to data security (such as DBSEC).

The start date of the position is negotiable. The position may be for one or two years.

Applicants should submit a CV, a research plan, two or three selected papers, and the names and contact information of three references. For further information about the position, or to apply, please send email to Florian Kerschbaum with \"Postdoctoral position\" in the subject line. Applications may be considered as they arrive.

Closing date for applications: 1 September 2018

Contact: Florian Kerschbaum with \"Postdoctoral position\" in the subject line. Applications may be considered as they arrive.

Cryptography, Security, and Privacy Research Group

David R. Cheriton School of Computer Science

University of Waterloo

Waterloo, Ontario, Canada N2L 3G1

Tel: 519-888-4567 x36163

Fax: 519-885-1208

More information: https://crysp.uwaterloo.ca/prospective/postdoc/

he Cryptography, Security, and Privacy (CrySP) research group at the University of Waterloo is seeking applications for a postdoctoral research position in the field of privacy-enhancing technologies. This position will be held in the Cheriton School of Computer Science.

Applicants must hold a PhD in a related field, and should have a proven research record, as demonstrated by publications in top security and privacy venues (such as Oakland, CCS, USENIX Security, and NDSS) and/or top venues specific to privacy-enhancing technologies (such as PETS/PoPETs).

The start date of the position is negotiable. The position may be for one or two years.

Applicants should submit a CV, a research plan, two or three selected papers, and the names and contact information of three references.

Closing date for applications: 1 September 2018

Contact: Ian Goldberg with \"Postdoctoral position\" in the subject line. Applications may be considered as they arrive.

Cryptography, Security, and Privacy Research Group

David R. Cheriton School of Computer Science

University of Waterloo

Waterloo, Ontario, Canada N2L 3G1

Tel: 519-888-4567 x36163

Fax: 519-885-1208

More information: https://crysp.uwaterloo.ca/prospective/postdoc/

Thus far, several lattice-based algorithms for partial key exposure attacks on RSA, i.e., given the most/least significant bits (MSBs/LSBs) of a secret exponent $d$ and factoring an RSA modulus $N$, have been proposed such as Bl\"omer and May (Crypto'03), Ernst et al. (Eurocrypt'05), and Aono (PKC'09). Due to Boneh and Durfee's small secret exponent attack, partial key exposure attacks should always work for $d<N^{0.292}$ even without any partial information. However, it was difficult task to make use of the given partial information without losing the quality of Boneh-Durfee's attack. In particular, known partial key exposure attacks fail to work for $d<N^{0.292}$ with only few partial information. Such unnatural situation stems from the fact that the additional information makes underlying modular equations involved. In this paper, we propose improved attacks when a secret exponents $d$ is small. Our attacks are better than all known previous attacks in the sense that our attacks require less partial information. Specifically, our attack is better than all known ones for $d<N^{0.5625}$ and $d<N^{0.368}$ with the MSBs and the LSBs, respectively. Furthermore, our attacks fully cover the Boneh-Durfee bound, i.e., they always work for $d<N^{0.292}$. At a high level, we obtain the improved attacks by fully utilizing unravelled linearization technique proposed by Herrmann and May (Asiacrypt'09). Although Herrmann and May (PKC'10) already applied the technique to Boneh-Durfee's attack, we show elegant and impressive extensions to capture partial key exposure attacks. More concretely, we construct structured triangular matrices that enable us to recover more useful algebraic structures of underlying modular polynomials. We embed the given MSBs/LSBs to the recovered algebraic structures and construct our partial key exposure attacks. In this full version, we provide overviews and explicit proofs of the triangular matrix constructions. We believe that the additional explanations help readers to understand our techniques.

Private function evaluation aims to securely compute a function f (x_1 , . . ., x_n ) without leaking any information other than what is revealed by the output, where f is a private input of one of the parties (say Party_1) and x_i is a private input of the i-th party Party_i. In this work, we propose a novel and secure two-party private function evaluation (2PFE) scheme based on DDH assumption. Our scheme introduces a reusability feature that significantly improves the state-of-the-art. Accordingly, our scheme has two variants, one is utilized in the first evaluation of the function f, and the other is utilized in its subsequent evaluations. To the best of our knowledge, this is the first and most efficient special purpose PFE scheme that enjoys a reusablity feature. Our protocols achieve linear communication and computation complexities and a constant number of rounds which is at most three.

We point out an implicit unproven assumption underlying the security of rational proofs of storage that is related to a concept we call weak randomized compression. This is a class of interactive proofs designed in a security model with a rational prover who is encouraged to store data (possibly in a particular format), as otherwise it either fails verification or does not save any storage costs by deviating (in some cases it may even increase costs by ``wasting" the space). Weak randomized compression is a scheme that takes a random seed $r$ and a compressible string $s$ and outputs a compression of the concatenation $r \circ s$. Strong compression would compress $s$ by itself (and store the random seed separately). In the context of a storage protocol, it is plausible that the adversary knows a weak compression that uses its incompressible storage advice as a seed to help compress other useful data it is storing, and yet it does not know a strong compression that would perform just as well. It therefore may be incentivized to deviate from the protocol in order to save space. This would be particularly problematic for proofs of replication, designed to encourage provers to store data in a redundant format, which weak compression would likely destroy. We thus motivate the question of whether weak compression can always be used to efficiently construct strong compression, and find (negatively) that a black-box reduction would imply a universal compression scheme in the random oracle model for all compressible efficiently sampleable sources. Implausibility of universal compression aside, we conclude that constructing this black-box reduction for a class of sources is at least as hard as directly constructing a universal compression scheme for that class.

Unspent Transaction Outputs (UTXOs) are the internal mechanism used in many cryp- tocurrencies to represent coins. Such representation has some clear benefits, but also entails some complexities that, if not properly handled, may leave the system in an inefficient state. Specifically, inefficiencies arise when wallets (the software responsible for transferring coins between parties) do not manage UTXOs properly when performing payments. In this paper, we study three cryptocurrencies: Bitcoin, Bitcoin Cash and Litecoin, by analyzing the actual state of their UTXO sets, that is, the status of their sets of spendable coins. These three cryptocurrencies are the top-3 UTXO based cryptocurrencies by market capitalization. Our analysis shows that the usage of each cryptocurrency is quite different, and let to different results. Furthermore, it also points out that the management of the transactions has not been always performed efficiently and then the actual state of the UTXO set for each cryptocurrency is far from ideal.

Braid group is a very important non-commutative group. It is also an important tool of quantum field theory, and has good topological properties. This paper focuses on the provable security research of cryptosystem over braid group, which consists of two aspects: One, we proved that the Ko's cryptosystem based on braid group is secure against chosen-plaintext-attack(CPA) which proposed in CRYPTO2000, while it dose not resist active attack. The other is to propose a new public key cryptosystem over braid group which is secure against adaptive chosen-ciphertext-attack(CCA2). Our proofs are based on random oracle models, under the computational conjugacy search assumption(CCS assumption). This kind of results have never been seen before

The GGH15 multilinear maps have served as the foundation for a number of cutting-edge cryptographic proposals. Unfortunately, many schemes built on GGH15 have been explicitly broken by so-called ``zeroizing attacks,'' which exploit leakage from honest zero-test queries. The precise settings in which zeroizing attacks are possible have remained unclear. Most notably, none of the current indistinguishability obfuscation (iO) candidates from GGH15 have any formal security guarantees against zeroizing attacks.

In this work, we demonstrate that all known zeroizing attacks on GGH15 implicitly construct algebraic relations between the results of zero-testing and the encoded plaintext elements. We then propose a ``GGH15 zeroizing model" as a new general framework which greatly generalizes known attacks.

Our second contribution is to describe a new GGH15 variant, which we formally analyze in our GGH15 zeroizing model. We then construct a new iO candidate using our multilinear map, which we prove secure in the GGH15 zeroizing model. This implies resistance to all known zeroizing strategies. The proof relies on the Branching Program Un-Annihilatability (BPUA) Assumption of Garg et al. [TCC 16-B] (which is implied by PRFs in NC^1 secure against P/Poly) and the complexity-theoretic p-Bounded Speedup Hypothesis of Miles et al. [ePrint 14] (a strengthening of the Exponential Time Hypothesis).

The ICAO-standardized Password Authenticated Connection Establishment (PACE) protocol is used all over the world to secure access to electronic passports. Key-secrecy of PACE is proven by first modeling it as an Observational Transition System (OTS) in CafeOBJ, and then proving invariant properties by induction.

In this paper, we propose a new cryptanalysis method to mount collision attack on RIPEMD-160. Firstly, we review two existent cryptanalysis methods to mount (semi-free-start) collision attack on MD-SHA hash family and briefly explain their advantages and disadvantages. To make the best use of the advantages of the two methods, we come up with a new model to mount collision attack. Applying the new technique, we improve the only existent collision attack on the first 30-step RIPEMD-160 presented at Asiacrypt 2017 by a factor of $2^{11}$. Moreover, our new method is much simpler than that presented at Asiacrypt 2017 and there is no need to pre-determine many bit conditions for multi-step modification, thus leaving sufficient freedom degree of the message words. Besides, we further evaluate the pros and cons of the new method and describe how to carefully apply it in future research. We also implement this attack in C++ and can find the message words to ensure the dense right branch with time complexity $2^{30}$.

Private linear key agreement (PLKA) enables a group of users to agree upon a common session key in a broadcast encryption (BE) scenario, while traitor tracing (TT) system allows a tracer to identify conspiracy of a troop of colluding pirate users. This paper introduces a key encapsulation mechanism in BE that provides the functionalities of both PLKA and TT in a unified cost-effective primitive. Our PLKA based traitor tracing offers a solution to the problem of achieving full collusion resistance property and public traceability simultaneously with significant efficiency and storage compared to a sequential improvement of the PLKA based traitor tracing systems. Our PLKA builds on a prime order multilinear group setting employing indistinguishability obfuscation (iO) and pseudorandom function (PRF). The resulting scheme has a fair communication, storage and computational efficiency compared to that of composite order groups. Our PLKA is adaptively chosen ciphertext attack (CCA)-secure and based on the hardness of the multilinear assumption, namely, the Decisional Hybrid Diffie-Hellman Exponent (DHDHE) assumption in standard model and so far a plausible improvement in the literature. More precisely, our PLKA design significantly reduces the ciphertext size, public parameter size and user secret key size. We frame a traitor tracing algorithm with shorter running time which can be executed publicly.

A searchable symmetric encryption (SSE) scheme enables a client to store data on an untrusted server while supporting keyword searches in a secure manner. Recent experiments have indicated that the practical relevance of such schemes heavily relies on the tradeoff between their space overhead, locality (the number of non-contiguous memory locations that the server accesses with each query), and read efficiency (the ratio between the number of bits the server reads with each query and the actual size of the answer). These experiments motivated Cash and Tessaro (EUROCRYPT '14) and Asharov et al. (STOC '16) to construct SSE schemes offering various such tradeoffs, and to prove lower bounds for natural SSE frameworks. Unfortunately, the best-possible tradeoff has not been identified, and there are substantial gaps between the existing schemes and lower bounds, indicating that a better understanding of SSE is needed.

We establish tight bounds on the tradeoff between the space overhead, locality and read efficiency of SSE schemes within two general frameworks that capture the memory access pattern underlying all existing schemes. First, we introduce the ``pad-and-split'' framework, refining that of Cash and Tessaro while still capturing the same existing schemes. Within our framework we significantly strengthen their lower bound, proving that any scheme with locality $L$ must use space $\Omega ( N \log N / \log L )$ for databases of size $N$. This is a tight lower bound, matching the tradeoff provided by the scheme of Demertzis and Papamanthou (SIGMOD '17) which is captured by our pad-and-split framework.

Then, within the ``statistical-independence'' framework of Asharov et al. we show that their lower bound is essentially tight: We construct a scheme whose tradeoff matches their lower bound within an additive $O(\log \log \log N)$ factor in its read efficiency, once again improving upon the existing schemes. Our scheme offers optimal space and locality, and nearly-optimal read efficiency that depends on the frequency of the queried keywords: For a keyword that is associated with $n = N^{1 - \epsilon(n)}$ document identifiers, the read efficiency is $\omega(1) \cdot \epsilon(n)^{-1}+ O(\log\log\log N)$ when retrieving its identifiers (where the $\omega(1)$ term may be arbitrarily small, and $\omega(1) \cdot \epsilon(n)^{-1}$ is the lower bound proved by Asharov et al.). In particular, for any keyword that is associated with at most $N^{1 - 1/o(\log \log \log N)}$ document identifiers (i.e., for any keyword that is not exceptionally common), we provide read efficiency $O(\log \log \log N)$ when retrieving its identifiers.

We consider information-theoretic secure two-party computation in the plain model where no reliable channels are assumed, and all communication is performed over the binary symmetric channel (BSC) that flips each bit with fixed probability. In this reality-driven setting we investigate feasibility of communication-optimal noise-resilient semi-honest two-party computation i.e., efficient computation which is both private and correct despite channel noise.

We devise an information-theoretic technique that converts any correct, but not necessarily private, two-party protocol that assumes reliable channels, into a protocol which is both correct and private against semi-honest adversaries, assuming BSC channels alone. Our results also apply to other types of noisy-channels such as the elastic-channel.

Our construction combines tools from the cryptographic literature with tools from the literature on interactive coding, and achieves, to our knowledge, the best known communication overhead. Specifically, if $f$ is given as a circuit of size $s$, our scheme communicates $O(s + \kappa)$ bits for $\kappa$ a security parameter. This improves the state of the art (Ishai et al., CRYPTO' 11) where the communication is $O(s) + \text{poly}(\kappa \cdot \text{depth}(s))$.

Refreshing algorithms are a critical ingredient for secure masking. They are instrumental in enabling sound composability properties for complex circuits, and their randomness requirements dominate the performance overheads in (very) high-order masking. In this paper, we improve a proposal of mask refreshing algorithms from EUROCRYPT 2017, that has excellent implementation properties in software and hardware, in two main directions. First, we provide a generic proof that this algorithm is secure at arbitrary orders -- a problem that was left open so far. We introduce Parametrized Non-Interference as a new technical ingredient for this purpose, that may be of independent interest. Second, we use automated tools to further explore the design space of such algorithms and provide the best known parallel mask refreshing gadgets for concretely relevant security orders. Incidentally, we also prove the security of a recent proposal of mask refreshing with improved resistance against horizontal attacks from CHES 2017.

Post-quantum cryptography has attracted much attention from worldwide cryptologists. However, most research works are related to public-key cryptosystem due to Shor's attack on RSA and ECC ciphers. At CRYPTO 2016, Kaplan et al. breaks many secret-key (symmetric) systems using quantum period finding algorithm, which arises researcher's attentions to evaluate the symmetric systems against quantum attackers.

In this paper, we continue to study the symmetric ciphers against quantum attackers. First, we convert the classical advanced slide attacks (introduced by Biryukov and Wagner) to a quantum one, that gains an exponential speed-up of the time complexity. Thus, we could break 2/4K-Feistel and 2/4K-DES in polynomial time. Second, we give a new quantum key-recovery attack on full-round GOST, a Russian standard, with $2^{112}$ Grover iterations, which is faster than a quantum brute force search attack by a factor $2^{16}$.

By representing data in a unary way, the identity of the bits can be used as a printing pad to stain the data with the identity of its handlers. Passing data will identify its custodians, its pathway, and its bona fide. This technique will allow databases to recover from a massive breach as the thieves will be caught when trying to use this 'sticky data'. Heavily traveled data on networks will accumulate the 'fingerprints' of its holders, to allow for a forensic analysis of fraud attempts, or data abuse. Special applications for the financial industry, and for intellectual property management. Fingerprinting data may be used for new ways to balance between privacy concerns and public statistical interests. This technique might restore the identification power of the US Social Security Number, despite the fact that millions of them have been compromised. Another specific application regards credit card fraud. Once the credit card numbers are 'sticky' they are safe. The most prolific application though, may be in conjunction with digital money technology. The BitMint protocol, for example, establishes its superior security on 'sticky digital coins'. Advanced fingerprinting applications require high quality randomization. The price paid for the fingerprinting advantage is a larger data footprint -- more bits per content. Impacting both storage and transmission. This price is reasonable relative to the gained benefit.

Secure multi-party computation (MPC) is a general cryptographic technique that allows distrusting parties to compute a function of their individual inputs, while only revealing the output of the function. It has found applications in areas such as auctioning, email filtering, and secure teleconference. Given their importance, it is crucial that the protocols are specified and implemented correctly. In the programming language community, it has become good practice to use computer proof assistants to verify correctness proofs. In the field of cryptography, EasyCrypt is the state of the art proof assistant. It provides an embedded language for probabilistic programming, together with a specialized logic, embedded into an ambient general purpose higher-order logic. It allows us to conveniently express cryptographic properties. EasyCrypt has been used successfully on many applications, including public-key encryption, signatures, garbled circuits and differential privacy. Here we show for the first time that it can also be used to prove security of MPC against a malicious adversary. We formalize additive and replicated secret sharing schemes and apply them to Maurer’s MPC protocol for secure addition and multiplication. Our method extends to general polynomial functions. We follow the insights from EasyCrypt that security proofs can often be reduced to proofs about program equivalence, a topic that is well understood in the verification of programming languages. In particular, we show that for a class of MPC protocols in the passive case the non-interference-based (NI) definition is equivalent to a standard simulation-based security definition. For the active case, we provide a new non-interference based alternative to the usual simulation-based cryptographic definition that is tailored specifically to our protocol.

MapReduce programming paradigm allows to process big data sets in parallel on a large cluster. We focus on a scenario where the data owner outsources her data on an honest-but-curious server. Our aim is to evaluate grouping and aggregation with SUM, COUNT, AVG, MIN, and MAX operations for an authorized user. For each of these five operations, we assume that the public cloud provider and the user do not collude i.e., the public cloud does not know the secret key of the user. We prove the security of our approach for each operation.