International Association
for Cryptologic Research

A postdoctoral research fellow position in cybersecurity is available in the Virginia Modeling, Analysis and Simulation Center (VMASC) at Old Dominion University , for an initial appointment of one year, renewable based on the performance.

The incumbent is expected to participate in the cybersecurity research lab at VMASC led by Dr. Sachin Shetty

Responsibilities include conducting fundamental research in IoT security and publishing in leading conferences and journals, participation in proposal development, and some supervision of graduate students. This position is ideally suited for a recent Ph.D. graduate who plans to pursue a future research career. A completed Ph.D. degree in ECE or CS is required by the time of the appointment. Solid background in network security, game theory, distributed systems, protocols and algorithms, is highly desirable.

Closing date for applications: 1 September 2018

Contact: Dr. Sachin Shetty (sshetty (at) odu.edu)

More information: http://ww2.odu.edu/~sshetty/PostDoc_Cyber_2018.htm

This work advances the study of secure stream-based channels (Fischlin et al., CRYPTO ’15) by considering the multiplexing of many data streams over a single channel. This is an essential feature of real-world protocols such as TLS. Our treatment adopts the definitional perspective of Rogaway and Stegers (CSF ’09), which offers an elegant way to reason about what standardizing documents actually provide: a partial specification of a protocol that admits a collection of compliant, fully realized implementations. We formalize partially specified channels as the component algorithms of two parties communicating over a channel. Each algorithm has an oracle that services specification detail queries; intuitively, the algorithms abstract the things that are explicitly specified, while the oracle abstracts the things that are not. Our security notions, which capture a variety of privacy and integrity goals, allow the adversary to respond to these oracle queries; security relative to our notions implies that the channel withstands attacks in the presence of worst-case (i.e., adversarial) realizations of the specification details. Our formalization is flexible enough to provide the first provable security treatment of the TLS 1.3 record layer that does not elide optional behaviors and unspecified details.

Constructing indistinguishability obfuscation (iO) [BGI+01] is a central open question in cryptography. We provide new methods to make progress towards this goal. Our contributions may be summarized as follows:

1. Bootstrapping. In a recent work, Lin and Tessaro [LT17] (LT) show that iO may be constructed using i) Functional Encryption (FE) for polynomials of degree $L$ , ii) Pseudorandom Generators (PRG) with blockwise locality $L$ and polynomial expansion, and iii) Learning With Errors (LWE). Since there exist constructions of FE for quadratic polynomials from standard assumptions on bilinear maps [Lin17, BCFG17], the ideal scenario would be to set $L=2$, yielding iO from widely believed assumptions.

Unfortunately, it was shown soon after [LV17,BBKK17 ] that PRG with block locality $2$ and the expansion factor required by the LT construction, concretely $\Omega(n \cdot 2^{b(3+\epsilon)})$, where $n$ is the input length and $b$ is the block length, do not exist. While [LV17, BBKK17] provided strong negative evidence for constructing iO based on bilinear maps, they could not rule out the possibility completely; a tantalizing gap has remained. Given the current state of lower bounds, the existence of $2$ block local PRG with expansion factor $\Omega(n \cdot 2^{b(1+\epsilon)})$ remains open, although this stretch does not suffice for the LT bootstrapping, and is hence unclear to be relevant for iO.

In this work, we improve the state of affairs as follows.

(a) Weakening requirements on PRGs: In this work, we show that the narrow window of expansion factors left open by lower bounds do suffice for iO . We show a new method to construct FE for $NC_1$ from i) FE for degree $L$ polynomials, ii) PRGs of block locality $L$ and expansion factor $\Omega(n \cdot 2^{b(1+\epsilon)})$, and iii) LWE (or RLWE ). Our method of bootstrapping is completely different from all known methods. This re-opens the possibility of realizing iO from $2$ block local PRG, SXDH on Bilinear maps and LWE.

(b)Broadening class of sufficient PRGs: Our bootstrapping theorem may be instantiated with a broader class of pseudorandom generators than hitherto considered for iO, and may circumvent lower bounds known for the arithmetic degree of iO -sufficient PRGs [LV17 , BBKK17]; in particular, these may admit instantiations with arithmetic degree $2$, yielding iO with the additional assumptions of SXDH on Bilinear maps and LWE. In more detail, we may use the following two classes of PRG:

i) Non-Boolean PRGs: We may use pseudorandom generators whose inputs and outputs need not be Boolean but may be integers restricted to a small (polynomial) range. Additionally, the outputs are not required to be pseudorandom but must only satisfy a milder indistinguishability property. We tentatively propose initializing these PRGs using the multivariate quadratic assumption (MQ) which has been widely studied in the literature [MI88 , Wol05 , DY09] and against the general case of which, no efficient attacks are known.

ii) Correlated Noise Generators: We introduce an even weaker class of pseudorandom generators, which we call correlated noise generators (CNG) which may not only be non-Boolean but are required to satisfy an even milder (seeming) indistinguishability property.

(c) Assumptions and Efficiency. Our bootstrapping theorems can be based on the hardness of the Learning With Errors problem (LWE) or its ring variant (RLWE) and can compile FE for degree $L$ polynomials directly to FE for $NC_1$. Our method for bootstrapping to $NC_1$ does not go via randomized encodings as in previous works, which makes it simpler and more efficient than in previous works.

2. Instantiating Primitives. In this work, we provide the first direct candidate of FE for constant degree polynomials from new assumptions on lattices. Our construction is new and does not go via multilinear maps or graded encoding schemes as all previous constructions. Our construction is based on the ring learning with errors assumption (RLWE) as well as new untested assumptions on NTRU rings.

We provide a detailed security analysis and discuss why previously known attacks in the context of multilinear maps, especially zeroizing attacks and annihilation attacks, do not appear to apply to our setting. We caution that the assumptions underlying our construction must be subject to rigorous cryptanalysis before any confidence can be gained in their security. However, their significant departure from known multilinear map based constructions make them, we feel, a potentially fruitful new direction to explore. Additionally, being based entirely on lattices, we believe that security against classical attacks will likely imply security against quantum attacks.

The Internet of Things (IoT) technology has expanded widely across the world, promising new data management opportunities for industries, companies and individuals in different sectors, such as health services or transport logistics. This trend relies on connecting devices/things to collect, exchange and store data. The exponentially increasing number of IoT devices, their origin diversity, their limited capabilities in terms of resources, as well as the ever-increasing amount of data, raise new challenges for security and privacy protection, precluding traditional access control solutions to be integrated to this new environment. In this paper, we propose a reliable server-aided policy-based access control mechanism, named CHARIOT, that enables an IoT platform to verify credentials of different devices requesting access (read/write) to the data stored within it. CHARIOT permits IoT devices to authenticate themselves to the platform without compromising their privacy by using attribute-based signatures. Our solution also allows secure delegation of costly computational operations to a cloud server, hence relieving the workload at IoT devices' side.

Recently, the Boomerang Connection Table was introduced by Cid et al.~as a tool to better evaluate the probability of a boomerang distinguisher. To compute the BCT of an $n$-bit to $n$-bit S-box, the inventors of the BCT proposed an algorithm that takes $O(2^{3n})$ time. We show that one can construct the same table in only $O(2^{2n})$ time.

Overstretched NTRU, an NTRU variant with a large modulus, has been used as a building block for several cryptographic schemes in recent years. Recently, two lattice subfield attacks and a subring attack were proposed that broke some suggested parameters for overstretched NTRU. These attacks work by decreasing the dimension of the lattice to be reduced, which improves the performance of the lattice basis reduction algorithm. However, there are a number of conflicting claims in the literature over which of these attacks has the best performance. These claims are typically based on experiments more than analysis. Furthermore, the metric for comparison has been unclear in some prior work. In this paper, we argue that the correct metric should be the lattice dimension. We show both analytically and experimentally that the subring attack succeeds on a smaller dimension lattice than the subfield attack for the same problem parameters, and also succeeds with a smaller modulus when the lattice dimension is fixed.

Demanding computations are increasingly outsourced to cloud platforms. For such outsourced computations, the efficient verifiability of results is a crucial requirement. When sensitive data is involved, the verification of a computation should preserve the privacy of the input values: it should be context hiding. Context hiding verifiability is enabled by existing homomorphic authenticator schemes. However, until now, no context hiding homomorphic authenticator scheme supports multiple independent clients, e.g. multiple keys. Multi-key support is necessary for datasets involving input authenticated by different clients, e.g. multiple hospitals in e-health scenarios. In this paper, we propose the first perfectly context hiding, publicly verifiable multi-key homomorphic authenticator scheme supporting linear functions. Our scheme is provably unforgeable in the standard model, and succinct. Verification time depends only linearly on the number of clients, in an amortized sense.

Dynamic searchable symmetric encryption (DSSE) is a useful cryptographic tool in the encrypted cloud storage. However, it has been reported that DSSE usually suffers from the file-injection attacks and content leak of deleted documents. To mitigate these attacks, forward security and backward security have been proposed. Nevertheless, the existing forward/backward-secure DSSE schemes can only support single keyword queries. To address this problem, in this paper, we propose two DSSE schemes supporting range queries. One is forward-secure and supports a large number of documents. The other can achieve both forward security and backward security, while it can only support a limited number of documents. Finally, we also give the security proofs of the proposed DSSE schemes in the random oracle model.

We construct a verifable delay function (or unique publicly verifiable proof of sequential work) by showing how the Rivest-Shamir-Wagner time-lock puzzle can be made publicly verifiable.

Concretely, we give a statistically sound public-coin protocol to prove that a tuple $(N,x,T,y)$ satisfies $y=x^{2^T}\pmod N$ where the prover doesn't know the factorization of $N$ and its running time is dominated by solving the puzzle, that is, compute $x^{2^T}$, which is conjectured to require $T$ sequential squarings.

The motivation for this work comes from the Chia blockchain design, which uses a VDF as a key ingredient. For typical parameters, our proofs are of size around $10KB$ and verification cost around three RSA exponentiations.

Homomorphic encryption schemes allow to perform computations over encrypted data. In schemes based on RLWE assumption the plaintext data is a ring polynomial. In many use cases of homomorphic encryption only the degree-0 coefficient of this polynomial is used to encrypt data. In this context any computation on encrypted data can be performed. It is trickier to perform generic computations when more than one coefficient per ciphertext is used.

In this paper we introduce a method to efficiently evaluate low-degree multivariate polynomials over encrypted data. The main idea is to encode several messages in the coefficients of a plaintext space polynomial. Using ring homomorphism operations and multiplications between ciphertexts, we compute multivariate monomials up to a given degree. Afterwards, using ciphertext additions we evaluate the input multivariate polynomial. We perform extensive experimentations of the proposed evaluation method. As example, evaluating an arbitrary multivariate degree-3 polynomial with 100 variables over Boolean space takes under 13 seconds.

Dear IACR members,

This year holds again great promise for cryptology research with the ongoing interest in blockchain technology and cryptocurrencies. As a sign of this, the word "crypto" has received a new interpretation in newspapers, by the public, and by your favorite search engine: Crypto no longer stands first for the conference that we have held in Santa Barbara since 1981.

This message contains information about recent some developments in IACR. The Board of Directors held a virtual meeting back in March (using Zoom teleconference!) and an in-person meeting at Eurocrypt in Tel-Aviv.

Crypto 2018

The Crypto 2018 conference will accommodate seven "workshops" or affiliated events, taking place from Friday to Sunday before the main conference. Registrations are flowing in at a steady pace. Together with the general chair Tal Rabin, I urge you to register and book your trips early.

https://crypto.iacr.org/2018/

The cutoff date for discounted early registration is July 5th!

Task force on diversity

The IACR has established a task force on diversity, whose goal is to:
a) support women attending IACR events;
b) promote and support IACR and other events that advance diversity (defined broadly);
c) improve diversity, especially representation of women and people from Asia, within IACR governance.

This is a community effort. Tal Rabin and Douglas Stebila are leading the task force and are looking forward to receiving your help, suggestions, and comments.

Code of Conduct for IACR events

The IACR has adopted a code of conduct for its conferences. All events of the IACR must refer to this code of conduct, which starts as follows:

The IACR is committed to providing an experience free of harassment and discrimination in its events, respecting the dignity of every participant. Participants who violate this code may be sanctioned and/or expelled from the event, at the discretion of the General Chair(s). Serious incidents may be referred to the IACR Ethics Committee for further possible action.

You can find the full text in the General Chair guidelines, section 8.10, on the website under:

https://www.iacr.org/docs/minutes/

For supporting this on behalf of the Board, the role of a Code-of-Conduct Liaison has been created. This is a person participating as observer in the Board. The Board has appointed Tal Rabin to this role.

IACR Schools in Cryptology

Cryptology Schools typically provide multiple days of intensive learning and constitute an efficient way to provide high-quality training for graduate students, as well as for professionals. The IACR sponsors such schools with financial contributions. The next schools in 2018 are:

Symmetric Proof Techniques
July 29-August 3, 2018, Bertinoro, Italy.
https://spotniq.school/


School on Modern Cryptography
July 30-August 3, 2018, Buenos Aires, Argentina.
http://www.dc.uba.ar/events/eci/2018/cursos

If you are interested to organize an IACR Cryptology School, please apply by June 30. More information is available on the website at https://iacr.org/schools/

To find out more about your IACR and the discussions of the Board of Directors, read the minutes of meeting at https://www.iacr.org/docs/minutes/

Best regards,

Christian Cachin
IACR President

Event date: 22 April to 24 April 2019

Event date: 18 February to 22 February 2019
Submission deadline: 18 September 2018
Notification: 14 November 2018

The MD transform that underlies the MD and SHA families iterates a compression function $\mathsf{h}$ to get a hash function $\mathsf{H}$. The question we ask is, what property X of $\mathsf{h}$ guarantees collision resistance (CR) of $\mathsf{H}$? The classical answer is that X itself be CR. We show that weaker conditions X, in particular forms of what we call constrained-CR, suffice. This reduces demands on compression functions, to the benefit of security, and also, forensically, explains why collision-finding attacks on compression functions have not, historically, lead to immediate breaks of the corresponding hash functions. We obtain our results via a definitional framework called RS security, and a parameterized treatment of MD, that also serve to unify prior work and variants of the transform.

We analyze the FOO electronic voting protocol in the provable secu- rity model using the technique of Computationally Complete Symbolic Attacker (CCSA). The protocol uses commitments, blind signatures and anonymous chan- nels to achieve vote privacy. Unlike the Dolev-Yao analyses of the protocol, we assume neither perfect cryptography nor existence of perfectly anonymous chan- nels. Our analysis reveals new attacks on vote privacy, including an attack that arises due to the inadequacy of the blindness property of blind signatures and not due to a specific implementation of anonymous channels. With additional assumptions and modifications, we were able to show that the protocol satisfies vote privacy. Our techniques demonstrate effectiveness of the CCSA technique for both attack detection and verification.

We construct an efficiently verifiable slow-timed hash function. A slow-timed hash function is a hash function with the guarantee that its evaluation requires to run a given number of sequential steps, but the result can be efficiently verified. They have applications in decentralised systems, such as the generation of trustworthy public randomness in a trustless environment. To construct a slow-timed hash function, we actually build a trapdoor slow-timed hash function. A trapdoor slow-timed hash function is essentially a slow-timed hash function which can be evaluated efficiently by parties who know a secret (the trapdoor). By setting up this scheme in a way that the trapdoor is unknown (not even by the party running the setup), we obtain a simple slow-timed hash function.

In this paper, we propose a new technique to perform several homomorphic operations in one bootstrapping call over a multi-value plaintext space. Our construction relies on the FHEW-based gate bootstrapping: we analyze its structure and propose a strategy we call multi-value bootstrapping which allows to bootstrap an arbitrary function in an efficient way. The security of our scheme relies on the LWE assumption over the torus. We give three applications: the first one is the efficient evaluation of an arbitrary boolean function (LUT), the second one is the optimization of the circuit bootstrapping from (Asiacrypt'2017) which allows to compose circuits in a leveled mode, the third one is the homomorphic evaluation of a neural network where the linear part is evaluated using a generalization of the key-switching procedure and the non-linear part is evaluated with our multi-value bootstrapping.

We have implemented the proposed method and were able to evaluate arbitrary 6-to-6 LUTs under 1.2 seconds. Our implementation is based on the TFHE library but can be easily integrated into other homomorphic libraries based on the same structure, such as FHEW (Eurocrypt'2015). The number of LUT outputs does not influence the execution time by a lot, e.g. evaluation of additional 128 outputs on the same 6 input bits takes only 0.05 more seconds.

The ARM TrustZone is a security extension which is used in recent Samsung flagship smartphones to create a Trusted Execution Environment (TEE) called a Secure World, which runs secure processes (Trustlets). The Samsung TEE includes cryptographic key storage and functions inside the Keymaster trustlet. The secret key used by the Keymaster trustlet is derived by a hardware device and is inaccessible to the Android OS. However, the ARM32 AES implementation used by the Keymaster is vulnerable to side channel cache-attacks. The Keymaster trustlet uses AES-256 in GCM mode, which makes mounting a cache attack against this target much harder. In this paper we show that it is possible to perform a successful cache attack against this AES implementation, in AES-256/GCM mode, using widely available hardware. Using a laptop's GPU to parallelize the analysis, we are able to extract a raw AES-256 key with 7 minutes of measurements and under a minute of analysis time and an AES-256/GCM key with 40 minutes of measurements and 30 minutes of analysis.

The threat of side-channels is becoming increasingly prominent for resource-constrained internet-connected devices. While numerous power side-channel countermeasures have been proposed, a promising approach to protect the non-invasive electromagnetic side-channel attacks has been relatively scarce. Today's availability of high-resolution electromagnetic (EM) probes mandates the need for a low-overhead solution to protect EM side-channel analysis (SCA) attacks. This work, for the first time, performs a white-box analysis to root-cause the origin of the EM leakage from an integrated circuit. System-level EM simulations with Intel 32 nm CMOS technology interconnect stack reveals that the EM leakage from metals above layer 8 can be detected by an external non-invasive attacker with the commercially available EM probes. This work proposes a two-stage solution to eliminate the critical signal radiation from the higher-level metal layers. Firstly, we propose routing the entire cryptographic core using the local lower-level metal layers, whose leakage cannot be picked up by an external attacker. Then, the entire crypto IP is embedded within a signature attenuation hardware (SAH) which in turn suppresses the critical encryption signature and finally connects to the highly radiating top-level metal layers. We utilize the Attenuated Signature Noise Injection (ASNI) circuit, which was recently proposed as a low-overhead generic power SCA countermeasure, in order to encapsulate the cryptographic core with local low-level metal routing, and thereby significantly suppress the critical signatures even before it reaches to the higher metals. System-level implementation of the ASNI circuit with local lower-level metal layers in TSMC 65 nm CMOS technology, with an AES-128 core (as an example cryptographic engine) operating at 40 MHz, shows that the system remains secure against EM SCA attack even after $1 M$ encryptions, with $67\%$ power efficiency compared to the unprotected AES.

Oblivious RAM (ORAM), introduced by Goldreich and Ostrovsky (JACM 1996), can be used to read and write to memory in a way that hides which locations are being accessed. The best known ORAM schemes have an $O(\log n)$ overhead per access, where $n$ is the data size. The work of Goldreich and Ostrovsky gave a lower bound showing that this is optimal for ORAM schemes that operate in a ``balls and bins'' model, where memory blocks can only be shuffled between different locations but not manipulated otherwise. The lower bound even extends to weaker settings such as offline ORAM, where all of the accesses to be performed need to be specified ahead of time, and read-only ORAM, which only allows reads but not writes. But can we get lower bounds for general ORAM, beyond ``balls and bins''?

The work of Boyle and Naor (ITCS '16) shows that this is unlikely in the offline setting. In particular, they construct an offline ORAM with $o(\log n)$ overhead assuming the existence of small sorting circuits. Although we do not have instantiations of the latter, ruling them out would require proving new circuit lower bounds. On the other hand, the recent work of Larsen and Nielsen (CRYPTO '18) shows that there indeed is an $\Omega(\log n)$ lower bound for general online ORAM.

This still leaves the question open for online read-only ORAM or for read/write ORAM where we want very small overhead for the read operations. In this work, we show that a lower bound in these settings is also unlikely. In particular, our main result is a construction of online ORAM where reads (but not writes) have an $o(\log n)$ overhead, assuming the existence of small sorting circuits as well as very good locally decodable codes (LDCs). Although we do not have instantiations of either of these with the required parameters, ruling them out is beyond current lower bounds.