International Association
for Cryptologic Research

The block Lanczos algorithm proposed by Peter Montgomery is an efficient means to tackle the sparse linear algebra problem which arises in the context of the number field sieve factoring algorithm and its predecessors. We present here a modified version of the algorithm, which incorporates several improvements: we discuss how to efficiently handle homogeneous systems and how to reduce the number of vectors stored in the course of the computation. We also provide heuristic justification for the success probability of our modified algorithm.

While the overall complexity and expected number of steps of the block Lanczos is not changed by the modifications presented in this article, we expect these to be useful for implementations of the block Lanczos algorithm where the storage of auxiliary vectors sometimes has a non-negligible cost.

Given a CM sextic field K, we give an explicit method for finding and constructing all genus 3 hyperelliptic curves whose Jacobians have complex multiplication by the maximal order of this field. Our algorithm works in complete generality, for any CM sextic field K, and for any period matrix for the Jacobian.

Proxy re-encryption (PRE) is a cryptographic primitive in which a proxy can transform Alice's ciphertexts into ones decryptable by Bob. Key-private PRE specifies an additional level of security, requiring that proxy keys leak no information on the identities of Alice and Bob. In this paper, we build two key-private PRE schemes: (1) we propose a CPA-secure key-private PRE scheme in the standard model, and (2) we then transform it into a CCA-secure scheme in the random oracle model. Both schemes enjoy following properties: both are uni-directional and the CPA-secure one is a multi-hop scheme. In addition, the security of our schemes is based on the hardness of the standard Learning-With-Errors (LWE) problem, itself reducible from worst-case lattice hard problems that are conjectured immune to quantum cryptanalysis, or ``post-quantum''. We implement the CPA-secure scheme and point out that, among many applications, it can be sufficiently used for the practical task of key rotation over encrypted data.

Kiasu-BC is a tweakable block cipher presented within the TWEAKEY framework at AsiaCrypt 2014. Kiasu-BC is almost identical to AES-128, the only difference to AES-128 is the tweak addition, where the 64-bit tweak is xored to the first two rows of every round-key. The security analysis of the designers focuses primarily on related-key related-tweak differential characteristics and meet-in-the-middle attacks. For other attacks, they conclude that the security level of Kiasu-BC is similar to AES-128. In this work, we provide the first third-party analysis of Kiasu-BC. We show that we can mount Square attacks on up to 7-round Kiasu-BC with a complexity of about $2^{48.5}$ encryptions, which improves upon the best published 7-round attacks for AES-128. Furthermore, we show that such attacks are applicable to the round-reduced OCB3-like mode of the CAESAR candidate Kiasu. To be specific, we show a key-recovery attack on 7-round Kiasu$\neq$ with a complexity of about $2^{82}$ encryptions.

Helper Data Systems are a cryptographic primitive that allows for the reproducible extraction of secrets from noisy measurements. Redundancy data called Helper Data makes it possible to do error correction while leaking little or nothing ("Zero Leakage") about the extracted secret string. We study the case of non-discrete measurement outcomes. In this case a quantization step is required. Recently de Groot et al described a generic method to perform the quantization in a Zero Leakage manner. We extend their work and show how the quantization intervals should be set to maximize the amount of extracted secret key material when noise is taken into account.

Event date: 2 November to 4 November 2016
Submission deadline: 1 July 2016
Notification: 15 August 2016

We study *interactive oracle proofs* (IOPs) (Ben-Sasson, Chiesa, Spooner '16), which combine aspects of probabilistically checkable proofs (PCPs) and interactive proofs (IPs). We present IOP constructions and general techniques that enable us to obtain tradeoffs in proof length versus query complexity that are not known to be achievable via PCPs or IPs alone. Our main results are:

1. Circuit satisfiability has 3-round IOPs with linear proof length (counted in bits) and constant query complexity. 2. Reed--Solomon codes have 2-round IOPs of proximity with linear proof length and constant query complexity. 3. Tensor product codes have 1-round IOPs of proximity with sublinear proof length and constant query complexity. For all of the above, known PCP constructions give *quaslinear* proof length and constant query complexity [BS08,Dinur07]. In addition, for circuit satisfiability, [BKKMS13] obtain PCPs with linear proof length but *sublinear* query complexity. As in [BKKMS13], we rely on algebraic-geometry codes to obtain our first result; but, unlike [BKKMS13], our use of such codes is much "lighter" because we do not rely on any automorphisms of the code.

We obtain our results in a modular way by proving and combining "IOP-analogues" of two fundamental tools:

Interactive proof composition.

Proof composition is used to reduce the query complexity of PCP verifiers, but the proof length of the composed proof system depends exponentially on the randomness complexity of the outer proof system. We prove a composition theorem for IOPs that does not suffer from this inefficiency. Sublinear sumcheck. The sumcheck protocol is an IP that enables an IP verifier to check the sum of values of a low-degree polynomial on an exponentially-large hypercube, but the verifier running time depends linearly on the individual degree. We prove a sumcheck protocol for IOPs that does not suffer from this inefficiency.

Overall, our work demonstrates that even constant-round IOPs are more efficient than known PCPs and IPs.

Many lattice based cryptosystems are based on the Ring learning with errors (Ring-LWE) problem. The most critical and computationally intensive operation of these Ring-LWE based cryptosystems is polynomial multiplication over rings. In this paper, we exploit the number theoretic transform (NTT) to build a family of scalable polynomial multiplier architectures, which provide designers with a trade-off choice of speed vs. area. Our polynomial multipliers are capable to calculate the product of two $n$-degree polynomials in about $(1.5n\lg n + 1.5n)/b$ clock cycles, where $b$ is the number of the butterfly operators. In addition, we exploit the cancellation lemma to reduce the required ROM storage. The experimental results on a Spartan-6 FPGA show that the proposed polynomial multiplier architectures achieve a speedup of 3 times on average and consume less Block RAMs and slices when compared with the compact design. Compared with the state of the art of high-speed design, the proposed hardware architectures save up to 46.64\% clock cycles and improve the utilization rate of the main data processing units by 42.27\%. Meanwhile, our designs can save up to 29.41\% block RAMs.

Job Overview Systems Security Architect is responsible for working with R&D projects within QUALCOMM to research, design and develop the right security architecture and protocols for these projects and standardize them as needed. Ability to perform systems security or vulnerability analysis and design is a must. This position requires a strong understanding of the mobile systems architecture and protocols as defined by standards such as 3GPP, ETSI, IEEE, IETF. The successful candidate will demonstrate prior experience in one or more of these areas and a passion for architecting secure systems.

Ability to work in groups as well as independently with minimal supervision is a must.

This position requires some travel (up to 20% of the time). Travel may involve participating in standards meetings and/or interacting with QUALCOMM\'s customers/partners in the industry.

Minimum Qualifications

5+ years experience in one or more of the following areas :

- Embedded platforms security (e.g., ARM TrustZone, TPM, smartcards)

- Wireless communication systems and protocols (CDMA/UMTS/LTE, Bluetooth, 802.11)

- Hardware / SoC security

- Cryptography

- Participation in standards organizations like IETF/3GPP/3GPP2

Preferred Qualifications

- Prior software development experience (C, C++, C#, Java, Windows, Linux) and knowledge of software vulnerabilities

- OS architectures (e.g., Android, Linux, iOS)

- IP security protocols (IPsec, SSL/TLS)/ Packet data network security

- Multimedia systems security design (e.g.VoIP/IMS)

- Web technologies or applications (e.g., HTTP, HTML5, XML)

Education Requirements Required:

Master\'s, Computer Engineering and/or Computer Networks & Systems and/or Computer Science and/or Electrical Engineering or equivalent experience

Preferred:

Doctorate, Computer Engineering and/or Computer Networks & Systems and/or Computer Science and/or Electrical Engineering or equivalent experience

Closing date for applications: 21 March 2016

Contact: Vivian Smith, Staffing Specialist

More information: https://jobs.qualcomm.com/public/jobDetails.xhtml?requisitionId=1940091

Event date: 21 September to 22 September 2016
Submission deadline: 24 June 2016
Notification: 29 July 2016

Event date: 31 August to 2 September 2016
Submission deadline: 18 April 2016
Notification: 10 June 2016

Event date: 13 July to 15 July 2016
Submission deadline: 18 April 2016
Notification: 6 June 2016

We continue investigations on the use of so-called Strong PUFs as a cryptographic primitive in realistic attack models. We focus on two scenarios: Firstly, the {\it PUF re-use model}, where PUFs are being used in more than one protocol run, implying that adversaries may gain {\it retrospective access} to PUFs after the completion of an earlier protocol. Such re-use appears indispensible in economically and practically viable PUF-applications, but can lead to unexpected attacks. Secondly, the {\it bad} (or {\it malicious}) {\it PUF model}, in which the employed PUFs have been manipulated to possess additional, hidden properties, which enable adversaries to cheat. For the first time, we consider adversaries who build new, malicious PUFs by using old, possibly benign PUFs as subparts of the new PUF, naming this scenario the {\it PUFs-inside-PUFs model}. In these three models, we obtain and/or formally prove the following results:

\begin{itemize}

\item {\sc PUF re-use, part I:} Any PUF that is {\it ``ideal''} and retrospectively accessible can be replaced by a standard random oracle. By applying the famous Impagliazzo-Rudich result \cite{IR}, this means that the power of plain Strong PUFs under retrospective access is severely limited; for example, it does not suffice to implement key exchange (KE) or oblivious transfer (OT).

\item {\sc PUF re-use, part II:} Any PUF that is both bad/malicious and retrospectively accessible can be completely eliminated from the protocol. The protocol can be compiled into an information-theoretically equivalent one without this PUF.

\item {\sc Bad PUFs and Simplification:} As a minor contribution, we simplify a recent OT-protocol for malicious PUFs by Dachman-Soled et al.~\cite{Dachman-Soled} from CRYPTO 2014. We can achieve the same security properties under the same assumptions, but use only one PUF instead of two.

\item {\sc PUFs-inside-PUFs, part I:} We propose the new adversarial model of {\it ``PUFs-inside-PUF attacks''}, and show that the earlier protocol of Dachman-Soled et al.\ \cite{Dachman-Soled} is vulnerable in this model (which lies outside the original framework of \cite{Dachman-Soled}).

\item {\sc PUFs-inside-PUFs, part II:} We construct a new PUF-based OT-protocol, which is secure against PUFs-inside-PUFs attacks if the used bad PUFs are stateless. Our protocol introduces the technique of interleaved challenges. We illustrate why the use of interactive hashing in the protocol is necessary, and why a first protocol attempt without interactive hashing fails.

\end{itemize}

Our findings are not restricted to the UC-framework or its peculiarities, but also apply in stand-alone settings. They have immediate relevance for PUF hardware design: The secure re-use of PUFs in protocols like KE or OT requires properties beyond unpredictability and unclonability. These include {\it reconfigurability} or {\it erasability} as well as {\it certifiability}. Their effective implementation is posed as a central new design goal by our work. Finally, we stress that the secure use of Strong PUFs in standard PUF-based identification protocols remains mostly unaffected by our results, and by attacks in the bad PUF model and the PUF re-use model alike.

The probing security model is very popular to prove the side-channel security of cryptographic implementations protected by masking. A common approach to secure nonlinear functions in this model is to represent them as polynomials over a binary field and to secure their nonlinear multiplications thanks to a method introduced by Ishai, Sahai and Wagner at Crypto 2003. Several schemes based on this approach have been published, leading to the recent proposal of Coron, Roy and Vivek which is currently the best known method when no particular assumption is made on the algebraic structure of the function. In the present paper, we revisit this idea by trading nonlinear multiplications for low-degree functions. Specifically, we introduce an algebraic decomposition approach in which a nonlinear function is represented as a sequence of functions with low algebraic degrees. We therefore focus on the probing-secure evaluation of such low-degree functions and we introduce three novel methods to tackle this particular issue. The paper concludes with a comparative analysis of the proposals, which shows that our algebraic decomposition method outperforms the method of Coron, Roy and Vivek in several realistic contexts.

Physically Unclonable Functions (PUFs) have been an emerging topic in hardware security and trust in recent years, and many different kinds of PUFs have been presented in the literature. An important criterion is always the diversity of PUF responses for different devices, called inter-device uniqueness. A very popular uniqueness metric consists of calculating the pairwise hamming distance between the response bit-strings of all devices, assuming that all response bits are uncorrelated. Such correlations, however, should be regarded when a statement about inter-device uniqueness is made. We therefore propose a novel correlation metric to fulfil this requirement. Furthermore, we show that the hamming distance metric is actually redundant when at the same time the also popular bit-aliasing metric is applied.

The costs of designing, building, launching and maintaining satellites make satellite operators extremely motivated to protect their on-orbit assets. Unfortunately, privacy concerns present a serious barrier to coordination between different operators. One obstacle to improving safety arises because operators view the trajectories of their satellites as private, and refuse to share this private information with other operators. Without data-sharing, preventing collisions between satellites becomes a challenging task.

A 2014 report from the RAND Corporation proposed using cryptographic tools from the domain of secure Multiparty Computation (MPC) to allow satellite operators to calculate collision probabilities (conjunction analyses) without sharing private information about the trajectories of their satellites.

In this work, we report on the design and implementation of a powerful new MPC framework for high-precision arithmetic on real-valued variables in a two-party setting where, unlike previous works, there is no honest majority, and where the players are not assumed to be semi-honest. We show how to apply this new solution in the domain of securely computing conjunction analyses. Our solution extends existing protocols, in particular the integer-based Goldreich-Micali-Wigderson (GMW) protocol, whereby we use combine and optimize GMW with Garbled Circuits (GC). We prove security of our protocol in the two party, semi-honest setting, assuming only the existence of one-way functions and Oblivious Transfer (the OT-hybrid model). The protocol allows a pair of satellite operators to compute the probability that their satellites will collide without sharing their underlying private orbital information. Techniques developed in this paper would potentially have a wide impact on general secure numerical analysis computations. We also show how to strengthen our construction with standard arithmetic message-authentication-codes (MACs) to enforce honest behavior beyond the semi-honest setting.

Computing a conjunction analysis requires numerically estimating a complex double integral to a high degree of precision. The complexity of the calculation, and the possibility of numeric instability presents many challenges for MPC protocols which typically model calculations as simple (integer) arithmetic or binary circuits.

Our secure numerical integration routines are extremely stable and efficient, and our secure conjunction analysis protocol takes only a few minutes to run on a commodity laptop.

Confidentiality and message authentication are the most important security goals that can be achieved simultaneously by Signcryption scheme. It is a cryptographic technique that performs both the functions of digital signature and public key encryption in a single logical step significantly at a lower cost than that of conventional method of signature-then-encryption. The paper proposes an efficient Certificateless Signcryption Scheme(CLSC) in random oracle model on bilinear mapping. It is provably secure under the assumptions of intractability of k-CAA, Inv-CDH, q-BDHI and CDH problems.

Semi-adaptive security is a notion of security that lies between selective and adaptive security for Attribute-Based Encryption (ABE) and Functional Encryption (FE) systems. In the semi-adaptive model the attacker is forced to disclose the challenge messages before it makes any key queries, but is allowed to see the public parameters.

We show how to generically transform any selectively secure ABE or FE scheme into one that is semi-adaptively secure with the only additional assumption being public key encryption, which is already naturally included in almost any scheme of interest. Our technique utilizes a fairly simple application of garbled circuits where instead of encrypting directly, the encryptor creates a garbled circuit that takes as input the public parameters and outputs a ciphertext in the underlying selective scheme. Essentially, the encryption algorithm encrypts without knowing the `real' public parameters. This allows one to delay giving out the underlying selective parameters until a private key is issued, which connects the semi-adaptive to selective security. The methods used to achieve this result suggest that the moral gap between selective and semi-adaptive security is in general much smaller than that between semi-adaptive and full security.

Finally, we show how to extend the above idea to generically bundle a family of functionalities under one set of public parameters. For example, suppose we had an inner product predicate encryption scheme where the length of the vectors was specified at setup and therefore fixed to the public parameters. Using our transformation one could create a system where for a single set of public parameters the vector length is not apriori bounded, but instead is specified by the encryption algorithm. The resulting ciphertext would be compatible with any private key generated to work on the same input length.

Mahmoody et al. (TCC 2016-A) showed that basing indistinguishability obfuscation (IO) on a wide range of primitives in a semi-black-box way is as hard as basing public-key cryptography on one-way functions. The list included any primitive $P$ that can be realized relative to random trapdoor permutations or degree-$O(1)$ graded encoding model for any finite ring secure against computationally unbounded polynomial-query attackers.

In this note, we rely on the recent result of Brakerski, Brzuska, and Fleischhacker (ePrint 2016/226) and rule out fully black-box constructions of IO from any such primitive $P$, assuming the existence of one-way functions and $\mathbf{NP} \not \subseteq \mathbf{coAM}$. At a technical level, we show that attacks in idealized (randomized) oracle models that succeed with constant advantage over the trivial bound (e.g., guessing the obfuscated circuit with probability $1/2+1/10$) would remain successful for an infinite sequence of security parameters for a non-zero measure of the oracles.

In less than a decade fully homomorphic encryption has made significant advances. Despite all these improvements it is quite a challenge to reduce the parameter sizes and specifically evaluation keys. Eliminating the need for such prohibitively large evaluation keys and expensive noise management techniques has become a significant thrust among homomorphic encryption researchers. In a notable attempt, Gentry, Sahai, and Waters (GSW) introduced a scheme based on the approximate eigenvector problem that eliminates evaluation keys and costly key switching operations. In another very recent development, the Subfield Lattice Attack was introduced by Albrecht, Bai, and Ducas showing that the asymptotic security level with narrow key distributions may be far less than assumed in NTRU based FHE proposals. In this paper, we propose a new FHE scheme F-NTRU that adopts the flattening technique proposed in GSW to derive an NTRU based scheme that (similar to GSW) does not require evaluation keys or key switch- ing. Our scheme eliminates the decision small polynomial ratio (DSPR) assumption but relies only on the standard R-LWE assumption. Our scheme uses wide key distributions, and hence is immune to the Subfield Lattice Attack. We provide implementation results which show reason- able evaluation times compared to existing schemes while eliminating the need for storing and managing costly evaluation keys.