Functional Encryption for Regular Languages

Authors

Brent Waters

Abstract

We provide a functional encryption system that supports functionality for regular languages. In our system a secret key is associated with a Deterministic Finite Automata (DFA) M. A ciphertext CT encrypts a message m and is associated with an arbitrary length string w. A user is able to decrypt the ciphertext CT if and only if the DFA M associated with his private key accepts the string w. Compared with other known functional encryption systems, this is the first system where the functionality is capable of recognizing an unbounded language. For example, in (Key-Policy) Attribute-Based Encryption (ABE) a private key SK is associated with a single boolean formula φ which operates over a fixed number of boolean variables from the ciphertext. In contrast, in our system a DFA M will meaningfully operate over an arbitrary length input w. We propose a system that utilizes bilinear groups. Our solution is a “public index” system, where the message m is hidden, but the string w is not. We prove security in the selective model under a variant of the decision l-Bilinear Diffie-Hellman Exponent (BDHE) assumption that we call the decision l-Expanded BDHE problem.

Usage


1    package it.unisa.dia.gas.crypto.arcanum.fe.rl.w12;
2    
3    import it.unisa.dia.gas.crypto.dfa.DFA;
4    import it.unisa.dia.gas.crypto.dfa.DefaultDFA;
5    import it.unisa.dia.gas.crypto.arcanum.fe.rl.w12.engines.RLW12KEMEngine;
6    import it.unisa.dia.gas.crypto.arcanum.fe.rl.w12.generators.RLW12KeyPairGenerator;
7    import it.unisa.dia.gas.crypto.arcanum.fe.rl.w12.generators.RLW12ParametersGenerator;
8    import it.unisa.dia.gas.crypto.arcanum.fe.rl.w12.generators.RLW12SecretKeyGenerator;
9    import it.unisa.dia.gas.crypto.arcanum.fe.rl.w12.params.*;
10   import it.unisa.dia.gas.crypto.kem.KeyEncapsulationMechanism;
11   import PairingFactory;
12   import org.bouncycastle.crypto.AsymmetricCipherKeyPair;
13   import org.bouncycastle.crypto.CipherParameters;
14   import org.bouncycastle.crypto.InvalidCipherTextException;
15   
16   import java.security.SecureRandom;
17   import java.util.Arrays;
18   
19   import static org.junit.Assert.*;
20   
21   /**
22    * @author Angelo De Caro (arcanumlib@gmail.com)
23    */
24   public class RLW12KEM {
25   
26   
27       public RLW12KEM() {
28       }
29   
30   
31       public AsymmetricCipherKeyPair setup(DFA.Alphabet alphabet) {
32           RLW12KeyPairGenerator setup = new RLW12KeyPairGenerator();
33           setup.init(new RLW12KeyPairGenerationParameters(
34                   new SecureRandom(),
35                   new RLW12ParametersGenerator().init(
36                           PairingFactory.getPairingParameters("params/curves/a.properties"),
37                           alphabet).generateParameters()
38           ));
39           return setup.generateKeyPair();
40       }
41   
42       public byte[][] encaps(CipherParameters publicKey, String w) {
43           try {
44               KeyEncapsulationMechanism kem = new RLW12KEMEngine();
45               kem.init(true, new RLW12EncryptionParameters((RLW12PublicKeyParameters) publicKey, w));
46   
47               byte[] ciphertext = kem.process();
48   
49               assertNotNull(ciphertext);
50               assertNotSame(0, ciphertext.length);
51   
52               byte[] key = Arrays.copyOfRange(ciphertext, 0, kem.getKeyBlockSize());
53               byte[] ct = Arrays.copyOfRange(ciphertext, kem.getKeyBlockSize(), ciphertext.length);
54   
55               return new byte[][]{key, ct};
56           } catch (InvalidCipherTextException e) {
57               e.printStackTrace();
58               fail(e.getMessage());
59           }
60           return null;
61       }
62   
63       public CipherParameters keyGen(CipherParameters publicKey, CipherParameters masterSecretKey, DFA dfa) {
64           RLW12SecretKeyGenerator keyGen = new RLW12SecretKeyGenerator();
65           keyGen.init(new RLW12SecretKeyGenerationParameters(
66                   (RLW12PublicKeyParameters) publicKey,
67                   (RLW12MasterSecretKeyParameters) masterSecretKey,
68                   dfa
69           ));
70   
71           return keyGen.generateKey();
72       }
73   
74       public byte[] decaps(CipherParameters secretKey, byte[] ciphertext) {
75           try {
76               KeyEncapsulationMechanism kem = new RLW12KEMEngine();
77   
78               kem.init(false, secretKey);
79               byte[] key = kem.processBlock(ciphertext);
80   
81               assertNotNull(key);
82               assertNotSame(0, key.length);
83   
84               return key;
85           } catch (InvalidCipherTextException e) {
86               e.printStackTrace();
87               fail(e.getMessage());
88           }
89   
90           return null;
91       }
92   
93   
94       public static void main(String[] args) {
95           DefaultDFA dfa = new DefaultDFA(2);
96           dfa.addFinalState(0);
97           dfa.addTransition(0, '0', 1);
98           dfa.addTransition(0, '1', 0);
99           dfa.addTransition(1, '0', 0);
100          dfa.addTransition(1, '1', 1);
101  
102          DefaultDFA.DefaultAlphabet alphabet = new DefaultDFA.DefaultAlphabet();
103          alphabet.addLetter('0', '1');
104  
105          RLW12KEM rlw12KEM = new RLW12KEM();
106  
107          // setup
108          AsymmetricCipherKeyPair keyPair = rlw12KEM.setup(alphabet);
109  
110          // keygen
111          CipherParameters secretKey = rlw12KEM.keyGen(keyPair.getPublic(), keyPair.getPrivate(), dfa);
112  
113          // Encaps/Decaps for accepting word
114          String w = "00111100";
115          assertTrue(dfa.accept(w));
116          byte[][] ct = rlw12KEM.encaps(keyPair.getPublic(), w);
117          assertEquals(true, Arrays.equals(ct[0], rlw12KEM.decaps(secretKey, ct[1])));
118  
119          // Encaps/Decaps for non-accepting word
120          w = "01111100";
121          assertFalse(dfa.accept(w));
122          ct = rlw12KEM.encaps(keyPair.getPublic(), "01111100");
123          assertEquals(false, Arrays.equals(ct[0], rlw12KEM.decaps(secretKey, ct[1])));
124      }
125  }
126  
127