International Association
for Cryptologic Research

Physical Unclonable Function (PUF) is the hardware analog of a one-way function which can address hardware security issues such as device authentication, generating secret keys, producing seeds for Random Number Generators, etc. Traditional silicon PUFs are based on delay (Ring Oscillator PUFs and Arbiter PUFs) or memory structures (e.g, SRAM PUFs). In this paper, we propose the design of an aging resistant, lightweight and low-power analog PUF that exploits the susceptibility of Threshold Voltage (Vth) of MOSFETs to process variations. Analysis shows improvement in power consumption, reliability over device aging along with quality metrics like uniformity, reliability and uniqueness for a 64-bit key generation. For 1 GHz clock input, this design consumes 0.18W/bit power with 50 % uniqueness and 51% uniformity along with the independence of these metrics on technology nodes. Experimental results suggest 4% variation in reliability under temperature variation from -55C to 125C and 20% variation in supply voltage. Aging analysis further projects the independence of reliability over device aging.

This paper extends the choice available for secure real number implementations with two new contributions. We will consider the numbers represented in form $a-\varphi b$ where $\varphi$ is the golden ratio, and in form $(-1)^s\cdot2^e$ where $e$ is a fixed-point number. We develop basic arithmetic operations together with some frequently used elementary functions. All the operations are implemented and benchmarked on SHAREMIND secure multi-party computation framework. It turns out that the new proposals provide viable alternatives to standard floating- and fixed-point implementations from the performance/error viewpoint in various settings. However, the optimal choice still depends on the exact requirements of the numerical algorithm to be implemented.

Second-order side-channel attacks are used to break first-order masking protections. A practical reason which often limits the efficiency of second-order attacks is the temporal localisation of the leaking samples. Several leakage samples must be combined which means high computational power. For second-order attacks, the computational complexity is quadratic. At CHES '04, Waddle and Wagner introduced attacks with complexity $\OO{n \log_2 n}$ on hardware traces, where $n$ is the window size, by working on traces auto-correlation. Nonetheless, the two samples must belong to the same window which is (normally) not the case for software implementations. In this article, we introduce preprocessing tools that improve the efficiency of bi-variate attacks (while keeping a complexity of $\OO{n \log_2 n}$), even if the two samples that leak are far away one from the other (as in software). We put forward two main improvements. Firstly, we introduce a method to avoid loosing the phase information. Next, we empirically notice that keeping the analysis in the frequency domain can be beneficial for the attack. We apply these attacks in practice on real measurements, publicly available under the DPA Contest v4, to evaluate the proposed techniques. An attack using a window as large as 4000 points is able to reveal the key in only 3000 traces.

The Fiat-Shamir transformation is the most efficient construction of non-interactive zero-knowledge proofs.

This paper is concerned with two variants of the transformation that appear but have not been clearly delineated in existing literature. Both variants start with the prover making a commitment. The strong variant then hashes both the commitment and the statement to be proved, whereas the weak variant hashes only the commitment. This minor change yields dramatically different security guarantees: in situations where malicious provers can select their statements adaptively, the weak Fiat-Shamir transformation yields unsound/unextractable proofs. Yet such settings naturally occur in systems when zero-knowledge proofs are used to enforce honest behavior. We illustrate this point by showing that the use of the weak Fiat-Shamir transformation in the Helios cryptographic voting system leads to several possible security breaches: for some standard types of elections, under plausible circumstances, malicious parties can cause the tallying procedure to run indefinitely and even tamper with the result of the election.

On the positive side, we define a form of adaptive security for zero-knowledge proofs in the random oracle model (essentially simulation-sound extractability), and show that a variant which we call strong Fiat-Shamir yields secure non-interactive proofs.

This level of security was assumed in previous works on Helios and our results are then necessary for these analyses to be valid. Additionally, we show that strong proofs in Helios achieve non-malleable encryption and satisfy ballot privacy, improving on previous results that required CCA security.

We propose a fast and secure arbitrary output-length hash function aiming at a higher speed than the FIPS 202's SHA-3 and SHAKE functions, while retaining their flexibility and basis of security. Furthermore, it can exploit a high degree of parallelism, whether using multiple cores or the single-instruction multiple-data (SIMD) instruction set of modern processors. On Intel's Haswell and Skylake architectures, KangarooTwelve tops at less than 1.5 cycles/byte for long messages on a single core. Short messages also benefit from about a factor two speed-up compared to the fastest FIPS 202 instance SHAKE128.

In this paper, we present the first systematic investigation of data remanence effects on an intrinsic Static Random Access Memory Physical Unclonable Function (SRAM PUF) implemented on a commercial off-the-shelf (COTS) device in a temperature range between -110° C and -40° C. Although previous studies investigated data remanence in SRAMs only at temperatures above -50° C, our experimental results clearly indicate that the extended temperature region we examine has dramatic effects on the security of intrinsic SRAM PUFs. We propose a number of different attacks and experimentally verify that data remanence effects can be exploited successfully to attack intrinsic SRAM PUFs on a COTS device, where the (micro)processor and the SRAM reside on the same die. Our experimental attack writes a bit-string to memory and freezes the device. Due to data remanence effects the attacker-known bit-string remains in memory and is subsequently read out by the bootloader to generate the PUF response. In this way, the attacker is able to construct a forged secret key by manipulating the PUF response. Finally, we also discuss and assess potential countermeasures against the attacks we examine.

In this paper, we describe a new information-theoretic protocol (and a computationally-secure variant) for secure {\em three}-party computation with an honest majority. The protocol has very minimal computation and communication; for Boolean circuits, each party sends only a single bit for every AND gate (and nothing is sent for XOR gates). Our protocol is (simulation-based) secure in the presence of semi-honest adversaries, and achieves privacy in the client/server model in the presence of malicious adversaries.

On a cluster of three 20-core servers with a 10Gbps connection, the implementation of our protocol carries out over \textit{1.3 million} AES computations per second, which involves processing over \textit{7 billion gates per second}. In addition, we developed a Kerberos extension that replaces the ticket-granting-ticket encryption on the Key Distribution Center (KDC) in MIT-Kerberos with our protocol, using keys/ passwords that are shared between the servers. This enables the use of Kerberos while protecting passwords. Our implementation is able to support a login storm of over 35,000 logins per second, which suffices even for very large organizations. Our work demonstrates that high-throughput secure computation is possible on standard hardware.

In this note, the polar decomposition of binary fields of even extension degree is used to reduce the evaluation of the Walsh transform of binomial Boolean functions to that of Gauss sums. In the case of extensions of degree four times an odd number, an explicit formula involving a Kloosterman sum is conjectured, proved with further restrictions, and supported by extensive experimental data in the general case. In particular, the validity of this formula is shown to be equivalent to a simple and efficient characterization for bentness previously conjectured by Mesnager.

The proceedings for Crypto 2016 are now available via SpringerLink. Through our agreement with Springer, IACR members can access these proceedings for free by logging into this access page. The conference will be held August 14-18 in Santa Barbara.

Event date: 19 September to 24 September 2016

Event date: 24 April to 26 April 2017
Submission deadline: 21 November 2016
Notification: 23 January 2017

Event date: 4 January to 6 January 2017
Submission deadline: 1 October 2017
Notification: 15 November 2017

Event date: 30 November to 2 December 2016
Submission deadline: 12 September 2016

Event date: 24 May to 26 May 2017
Submission deadline: 15 January 2017
Notification: 28 February 2017

We formalize a cryptographic primitive called functional commitment (FC) which can be viewed as a generalization of vector commitments (VCs), polynomial commitments and many other special kinds of commitment schemes. A non-interactive functional commitment allows committing to a message in such a way that the committer has the flexibility of only revealing a function $F(M)$ of the committed message during the opening phase. We provide constructions for the functionality of linear functions, where messages consist of vectors of $n$ elements over some domain $\mathcal{D}$ (e.g., $\vec{m} = (m_1,\ldots,m_n) \in \mathcal{D}^n$) and commitments can later be opened to a specific linear function $\sum_{i=1}^n m_i x_i = y \in \mathcal{R}$ of the vector coordinates. An opening for a function $F: \mathcal{D}^n \rightarrow \mathcal{R}$ thus generates a witness for the fact that $F(\vec{m})$ indeed evaluates to $y$. One security requirement is called \emph{function binding} and requires that it be infeasible open a commitment to two different evaluations $y,y'$ for the same function $F$.

We propose a construction of functional commitment (FC) for linear functions based on constant-size assumptions in composite order groups endowed with a bilinear map. The construction has commitments and openings of constant size (i.e., independent of $n$ or function description) and is \emph{perfectly hiding} -- the underlying message is information theoretically hidden. Our security proofs build on the D\'ej\`a Q framework of Chase and Meiklejohn (Eurocrypt 2014) and its extension by Wee (TCC 2016) to encryption primitives, thus relying on constant-size subgroup decisional assumptions. We show that FCs for linear functions are sufficiently powerful to solve four open problems. They, first, imply polynomial commitments,and, then, give cryptographic accumulators (i.e., an algebraic hash function which makes it possible to efficiently prove that some input belongs to a hashed set). In particular, specializing our FC construction leads to the first pairing-based polynomial commitments and accumulators for large universes, known to achieve security under simple assumptions. We also substantially extend our pairing-based accumulator to handle subset queries which requires a non-trivial extension of the D\'ej\`a Q framework.

These lecture notes survey some of the main ideas and tech- niques used in cryptographic voting systems. The write-up is geared to- wards readers with little knowledge of cryptography and it focuses on the broad principles that guide the design and analysis of cryptographic systems, especially the need for properly designed security models. We use a system proposed by Fujioka, Okamoto and Ohta as starting example to introduce some basic building blocks and desirable security properties. We then slowly build towards a comprehensive description of the Helios voting system, one of the few systems deployed in practice and briefly discuss a few of its security properties.

Location management is a key component of cellular networks. From a privacy perspective, however, it is also a major weakness: location management empowers the network operator to track users. In today's public and scientific discussion, the centralized storage of location data is mostly taken as a fact, and users are expected to trust the network operator. ANOTEL presents a novel, clean-slate approach of location management in cellular networks that challenges this assumption. We developed a design that is able to route calls to users who move through cellular networks, without violating their location privacy. We evaluate our approach using simulations and a practical user tracking algorithm.

This paper proposes a public-key cryptosystem and a short password encryption mode, where traditional hardness assumptions are replaced by specific refinements of the CAPTCHA concept called Decisional and Existential CAPTCHAs.

The public-key encryption method, achieving 128-bit security, typically requires from the sender to solve one CAPTCHA. The receiver does not need to resort to any human aid.

A second symmetric encryption method allows to encrypt messages using very short passwords shared between the sender and the receiver. Here, a simple 5-character alphanumeric password provides sufficient security for all practical purposes.

We conjecture that the automatic construction of Decisional and Existential CAPTCHAs is possible and provide candidate ideas for their implementation.

We propose a new protocol for two-party computation, secure against malicious adversaries, that is significantly faster than prior work in the single-execution (i.e., non-amortized) setting. In particular, our protocol requires only $O(\rho)$ public key operations and $\rho$ garbled circuits, where $\rho$ is the statistical security parameter, whereas previous work with the same number of garbled circuits required either $O(\rho n)$ public-key operations (where n is the input/output length) or another execution of a separate malicious two-party protocol.

We implement our protocol to evaluate its performance. Our prototype is able to securely compute AES in only $65 ms$ over a local-area network using a single thread without any pre-computation, only $3\times$ slower than a semi-honest execution of the same functionality, and $22\times$ faster than the best prior work in the single-execution setting. On a local-area network, our protocol requires around $20 \mu s$ to process each input/output bit and around $4 \mu s$ to process each AND gate, along with a fixed cost of around $23 ms$ to compute the base oblivious transfers.

Authenticated key exchange (AKE) protocol is an important cryptographic primitive that assists communicating entities, who are communicating over an insecure network, to establish a shared session key to be used for protecting their subsequent communication. Lattice-based cryptographic primitives are believed to provide resilience against attacks from quantum computers. An efficient AKE protocol with smaller module over ideal lattices is constructed in this paper, which nicely inherits the design idea of the excellent high performance secure Diffie-Hellman protocol. Under the hard assumption of ring learning with errors (RLWE) hard assumption, the security of the proposed protocol is proved in the Bellare-Rogaway model.