M2R Informatique, Parcours SECR. Proposed assignments.

This page describes the elective assignment for the lectures Security proofs within the module "Security Models, Profs and Protocols" of the M2R Informatique SECR track.

Evaluation rule : Mark = 75% EXAM + 25%*MAX( EXAM, Assignment)

Rules:

Each work consists in an individual homework of about 24 hours.
Each students will deliver:
- a short report (pdf, 4 pages maximum with double columns, see for instance latex2e ACM templates with example );
- a pdf copy of the slides;
- an archive (tar.gz) including all the source codes (including ReadMe and Makefile).
The languages for the report and the defense is to the discretion of the student, either English or French; but the slides are to be written in English.
Intermediate review meeting: 2015, December, 8th (Tuesday), 13h30 - 14h30 ENSIMAG room ???
Timetable and rules for the defense:
The defense will take place on 2016, January, 18th (Monday), 14h - 17h ENSIMAG room ???
Each presentation is 12 minutes (that may be shortened to 10 minutes) followed by 8 minutes of questions at most.
All students have to attend all presentations. After a talk from a student, the other students are expected to ask him questions.
- Boda-Majer Edgar: Verifiable computation with encrypted data
- Bouguera Amira: Code and cryptography: Linear code based cryptographic systems with provable security
- Branco Pedro : Non Interactive Key Exchange (NIKE)
- Espitalier Vincent : Encrypted file system (with a specific generator )
- Mattos Langeloh Gabriel : Complexity of graph and subgraph isomorphism
- Tedesco Alessandro : Verifiable computation of massive inputs
- Touzeau Valentin : Pinocchio (theory or practice)

Subjects proposed in 2015-2016

The proposed subjects are independent but may share or distribute part of the work.

[Paper] Code and cryptography: Linear code based cryptographic systems with provable security

Present the Random Linear Code Based Public Key Encryption Scheme RLCE [1] ans its resistance with respect to classical attacks, such as Mc Elliece. Analyze the security and performance of RLCE with Reed-Solomon code; compare with Mc Elliece encryption with a Goppa code. Why is the security of Mc Elliece with generalized Reed-Solomon code? and with Goppa Code ? e
[1] Yongge Wang: Random Linear Code Based Public Key Encryption Scheme RLCE. IACR Cryptology ePrint Archive 2015: 298 (2015)
Yongge Wang: RLCE implementation http://webpages.uncc.edu/yonwang/rlce, 2015 [2] A. Couvreur, I. Ma ́rquez-Corbella, and R. Pellikaan. A polynomial time attack against algebraic ge- ometry code based public key cryptosystems. In Proc. ISIT, pages 1446–1450. IEEE, 2014.

[Paper] Verifiable Computation on Encrypted Data

Explain how to securely check the result of an outsourced computation on encrypted data (eg on a cloud) based on [1]. How the use of homomorphic hashing improves the efficiency ?
[1] Dario Fiore, Rosario Gennaro, Valerio Pastro: Efficiently Verifiable Computation on Encrypted Data. ACM Conference on Computer and Communications Security 2014: 844-855

[Paper] Non-Interactive Key Exchange

Explain what is non-interactive key exchange (NIKE) and present one (or two at most) protocol and its security proof. How a NIKE can be converted into a public-key encryption scheme ? Illustrate on the chosen protocol and analyze the security of the resulting scheme.
[1] Eduarda S. V. Freire, Dennis Hofheinz, Eike Kiltz, Kenneth G. Paterson: Non-Interactive Key Exchange. Public Key Cryptography 2013, pages 254-271.

[Paper] Security of NMAC and HMAC without relying on resistance of an iterated scheme

Present the scheme of the NMAC and HMAC security proof based on the only pseudo-randomness of the related compression function (PRF hypothesis).
[1] Mihir Bellare: New Proofs for NMAC and HMAC: Security without Collision Resistance. J. Cryptology 28(4): 844-878 (2015)

[Paper] Programmable hash-functions and applications to signature

Explain precisely what are programmable hash functions and their provable security foundation. Present briefly the extension based on homomorphic encryption [1] to provide signatures. Compare with currently standard signatures.
[1] Dario Catalano, Dario Fiore, Luca Nizzardo: Programmable Hash Functions Go Private: Constructions and Applications to (Homomorphic) Signatures with Shorter Public Keys. CRYPTO (2) 2015: 254-274
[2] Dennis Hofheinz, Eike Kiltz: Programmable Hash Functions and Their Applications. CRYPTO 2008,

[Paper] Complexity of graph and subgraph isomorphism. Quasi-polynomial time for Graph isomorphism

Explain the complexity results on both problems; present the main principles of the quasi-polynomial time algorithm for graph isomorphism from Laci Babai. Present subclass of graphs for which isomorphism can be easily verified (in polynomial time); What are the consequence with respect to intermediate-NP Problem and cryptography? What's about NP) ? What's about the security parameters of the zero-knowledge interactive authentication protocol based on graph isomorphism? Provide a zero-knowledge authentication protocol based on subgraph isomorphism (and prove it).
[1] Babai, Laci talks : László Babai's Home Page (video of the first talk)
[2] Richard Lipton and Kenny Regan, A Little More on the Graph Isomorphism Algorithm, 21/11/2015
[3] Jeremy Kun, A Quasipolynomial Time Algorithm for Graph Isomorphism: The Details , 12/11/2015

[Paper and/or software] Interactive proofs for parallel programs

Explain how the result of a parallel computation (circuits) outsourced on a remote client can be checked efficiently and securely. What is the relation to the circuit depth? Explain for circuit with boolean gates and extend the results to arithmetic gates (for instance multiplication or inversion of matrices with rational coefficients). You can focus on an experimental point of view, providing an experimental evaluation (eg for the parity or the sum of n bits).
Justin Thaler. Time-optimal intercative proofs for circuit evaluation. Crypto 2013, Extended version. CoRR abs/1304.3812 (2013)

Verification of computations on massive inputs

Present the interactive protocols (prover and verifier) proposed by Justin Thaller in [1] to securely outsource a computation with massive inputs to a service provider.
[1] Stream Verification. CoRR abs/1507.04188 (2015)

[Paper and/or software] What is a verifiable computation? (Possibility of two projects)

Explain how (either theoretically or practically, both subjects are possible) the Pinocchio system works; illustrate on the verification of the computation of a hash function.
References:
[1] B Parno, C Gentry. Pinocchio: nearly practical verifiable computation. Security&Privacy 2013
[2] Microsoft Research, team Verifiable computing and Pinocchio source code.

[Software] Defense against illegal use by counter increment. (Possibility of two projects)

A company distributes a software and asks the users to pay for each execution of the software. Does this problem has a secure, trustable solution? Analyze several approaches:

when using standard system with no remote access nor specialized hardware;
by using an public-key infrastructure with reliable increment counter
by using a specific hardware token (eg TPM or smart card or ...)

[Paper] Subject SPONGE: Provable security of cryptographic sponge functions

The SHA-3 hash function Keccak is based on a sponge construction. Analyze the provable security of cryptographic sponge functions: what are their indifferentiability properties? How to use them to build cryptographic primitives (eg hash functions, pseudo-random generators, authenticated encryption) ?
References:

, The Sponge Functions Corner, Guido Bertoni1, Joan Daemen1, Michaël Peeters2 and Gilles Van Assche, http://sponge.noekeon.org
On the Indifferentiability of the Sponge Construction Guido Bertoni, Joan Daemen, Micha ̈el Peeters, and Gilles Van Assche

[Paper and/or implementation] Subject CODE-ATTACK: Solving hard knapsack problems and application to attack linear codes such as McEliece public key encryption

Representing the binary vector solution to the knapsack problem by two overlapping vectors with coefficients in {-1,0,1}, Anja Becker & al. proposed a new algorithm to solve knapsack in O(2^{0.291n}). Present this algorithm and compare it with previous existing algorithms. How this algorithm may be used to attack McEliece encryption? Concrete small instance examples are expected to present and illustrate the algorithms.
References:

Improved Generic Algorithms for Hard Knapsacks, Anja Becker and Jean-Sébastien Coron and Antoine Joux, http://eprint.iacr.org/2011/474
Decoding Random Binary Linear Codes in 2^{n/20}: How 1+1=0 Improves Information Set Decoding , Anja Becker and Antoine Joux and Alexander May and Alexander Meurer, http://eprint.iacr.org/2012/026
New generic algorithms for hard knapsacks, Nick Howgrave-Graham1 and Antoine Joux, http://eprint.iacr.org/2010/189

[Paper] Subject VERIFIABLE-COMPUTING: Verifiable computing on untrusted workers

How to provide a computationally-sound, non-interactive proof that n independent computations f(x_i) (for n different values) have all correctly been performed ? Illustrate by analyzing the security tradeoff between computation,verification and trust costs on the computation of n independent FFT of size m.

Non-Interactive Verifiable Computing: Outsourcing Computation to Untrusted Workers , Gennaro, Rosario; Gentry, Craig; Parno, Bryan. CRYPTO 2010.
http://www.cs.utexas.edu/pepper/ PEPPER: Toward practical verified computation

[Paper] Subject CRYPTO-COMPUTING: From zero knowledge to secure non-interactive cryptocomputing and homomorphic encryption

Present the definition of secure cryptocomputing proposed by T. Sander and A. Young in 2000. Is this definition verified by the homomorphic encryption scheme proposed by C. Gentry in his thesis? Illustrate on computing the sum of n (encrypted) bits.
References:

Non-Interactive CryptoComputing for NC1 Tomas Sander , Adam Young , Moti Yung. FOCS '99 Proceedings of the 40th Annual Symposium on Foundations of Computer Science, Page 554
Fully Homomorphic Encryption over the Integers, Craig Gentry , Shai Halevi , Vinod Vaikuntanathan,

[Paper] Subject OBFUSCATION: On the (Im)possibility of Obfuscating Programs

The paper [J. ACM vol. 59, n. 2, April 2012] (see Oded Goldreich's webpage) claims the non-existence of general obfuscators. Why this result is both a strong and weak result with respect to the development of obfuscated programs? Provide two examples to illustrate each.
References:

On the (Im)possibility of Obfuscating Programs, Boaz Barak, Oded Goldreich, Rusell Impagliazzo, Steven Rudich, Amit Sahai, Salil Vadhan, and Ke Yang, J. ACM vol. 59, n. 2, April 2012]
Can We Obfuscate Programs? Boaz Barak, comments on the paper http://www.math.ias.edu/~boaz/Papers/obf_informal.html

[Paper and implementation] Subject: Hash functions and resistance to second preimage.

HAIFA guarantees a lower bound Ω(2^k) for second preimage attacks, while there exist O(2^k-t) second-preimage attacks for 2^t-blocks messages iteratively hashed with Merkle-Damgard. From reading the paper [BF10], establish this result; are there lower bound for first preimage attacks too ? Compare the practical performances (e.g. theoretical and experimental bandwidth) between HAIFA and a standard iterative Merkle-Damgard scheme.
References:

[BF10] Practical Hash Functions Constructions Resistant to Generic Second Preimage Attacks Beyond the Birthday Bound, Charles Bouillaguet∗, Pierre-Alain Fouque, Research report in submission (http://www.di.ens.fr/~bouillaguet/pub/IPL.pdf [ pdf ]
[HAIFA] A Framework for Iterative Hash Functions — HAIFA, Eli Biham, Orr Dunkelman, Cryptology ePrint Archive, Report 2007/278, http://eprint.iacr.org/2007/278 (August 24–25 2006) [ pdf ]
Guido Bertoni, Joan Daemen, Michaël Peeters and Gilles Van Assche, « On the Indifferentiability of the Sponge Construction

[Implementation] Subject BBSCRYPT: Implementation of a Unix file system ciphering based on BBS generator.

The subject consists in implementing a file system cipher that implements basic Unix I/O primitives (read, write, seek, ...) to manage an encrypted file which blocks are ciphered using BBS, and a private seed.

The ciphered file is stored somewhere on a remote volume (disk, USB peripheral, ...). Once opened by an application (for instance vi, latex, gv, vlc, ...), it should behave as if it was a plain text file. This means that deciphering occurred when reading a block from the volume into memory, and ciphering when writing a block from memory to the disk.
The file is encrypted using a cryptographically secure pseudo-random generator: an implementation of BBS is asked for (see [1]) but other generators may be considered such as Fortuna (see [2]). Concerning the BBS generator:
- The modulo n of the BBS generator and its factor p and q are to be managed on a file local to the machine where the encryption/decryption of the block is performed (in the user .ssh directory).
- The BBS generators output one byte at each call which is used for encryption by Vernam cipher.
- The initial seed is based on the hash of the filename with some secret pass phrase.

Focusing on Linux, several implementations are possible among which (this list is by increasing difficulty but not exclusive):

by substituting the standard libc implementation (open, read, write, lseek, close) by a user library that manages correctly ciphered files (or else calls directly the native libc corresponding function). In Linux, this can be done by tuning the dynamic libraries to be used, setting the environment variables LD_LIBRARY_PATH (set of directories where libraries should be searched for first, before the standard set of directories) and LD_PRELOAD (libraries which functions will be used before others of the same name in later libraries).
based on FUSE (Filesystem in Userspace) that enables to mount a device or file with a specific user-tuned library to manage I/O.
by modifying file management in the Linux kernel (open, read, write, lseek, close).

If several students choose this subject, they have to agree to ensure that each student will perform an individual study. For instance, with 4 students choosing this subject, three may implement one of the three different solutions proposed above, and the last one may provide to those three students implementations of BBS (and may be of another generator such as Fortuna (with AES and Counter mode to restart generation from any position, see http://www.citadelsoftware.ca/fortuna/fortuna.htm). The solution will present the implementation choices, and will analyze the trade-off between performance and security (chosen generator, size of the key, ...).

[Implementation] Subject CSPRNGTest: Indistinguishably of probability distributions. Application to BM and BBS.

Implement the three following cryptographically secure pseudo-random generator and, for each, analyze their indistinguishably with respect to NIST recommendations and TestU01 :

Blum-Micali in Fp (precise values of p chosen)
Blum-Blum-Shub modulo a Blum integer n (precise the values of n chosen)
Another chosen generator. It may be an extension of Blum-Micali based on elliptic curve cryptography on a finite field, or another CSPRNG.

[Paper] Subject NPCOMPRESS: Impact of compression of NP instances on provable cryptography

From reading the paper [HN10], analyze both following statements:

The existence of hard-on-average problems (may be not in NP) implies the existence of one-way functions.
The existence of one-way function implies the existence of collision-resistant hash functions.

[HN10] On the Compressibility of NP Instances and Cryptographic Applications. Danny Harnik, Moni Naor, SIAM Journal of Computing, vol. 39 n. 5, pp1667-1713, march 2010. [preprint http://www.cs.technion.ac.il/~harnik/Compress.pdf]

[Paper] Subject CSCOMPOSE: Information-theoretically secure protocols and security under composition

From reading the paper [KLR10], analyze the impact on composition on provable security:

in the perfect secrecy context (information theory)
in the computationally secure context (complexity).

[KLR10] Eyal Kushilevitz, Yehuda Lindell, Tal Rabin Information-Theoretically Secure Protocols and Security Under Composition, STOC 06, SIAM Journal of Computing, vol. 39 n. 5, pp 2090-2112, march 2010. [preprint http://www.cs.biu.ac.il/~lindell/PAPERS/IT-composition.pdf]