How to Compress (Reusable) Garbled Circuits

Authors

Craig Gentry and Sergey Gorbunovy and Shai Haleviz and Vinod Vaikuntanathan and Dhinakaran Vinayagamurthy

Abstract

A fundamental question about (reusable) circuit garbling schemes is: how small can the garbled circuit be? Our main result is a reusable garbling scheme which produces garbled circuits that are the same size as the original circuit plus an additive poly(λ) bits, where λ is the security parameter. Save the additive poly(λ) factor, this is the best one could hope for. In contrast, all previous constructions of even single-use garbled circuits incurred a multiplicative poly(λ) blowup. Our techniques result in constructions of attribute-based and (single key secure) functional encryption schemes where the secret key of a circuit C consists of C itself, plus poly(λ) additional bits. All of these constructions are based on the subexponential hardness of the learning with errors problem. We also study the dual question of how short the garbled inputs can be, relative to the original input. We demonstrate a (different) reusable circuit garbling scheme, based on multilinear maps, where the size of the garbled input is the same as that of the original input, plus a poly(λ) factor. This improves on the result of Applebaum, Ishai, Kushilevitz and Waters (CRYPTO 2013) who showed such a result for single-use garbling. Similar to the above, this also results in attribute-based and (single key secure) functional encryption schemes where the size of the ciphertext encrypting an input x is the same as that of x, plus poly(λ) additional bits.

Usage of the ABE based on multilinear maps


1    package it.unisa.dia.gas.crypto.arcanum.fe.abe.gghvv13;
2    
3    import it.unisa.dia.gas.crypto.circuit.Circuit;
4    import it.unisa.dia.gas.crypto.circuit.DefaultCircuit;
5    import it.unisa.dia.gas.crypto.arcanum.fe.abe.gghvv13.engines.GGHVV13KEMEngine;
6    import it.unisa.dia.gas.crypto.arcanum.fe.abe.gghvv13.generators.GGHVV13KeyPairGenerator;
7    import it.unisa.dia.gas.crypto.arcanum.fe.abe.gghvv13.generators.GGHVV13ParametersGenerator;
8    import it.unisa.dia.gas.crypto.arcanum.fe.abe.gghvv13.generators.GGHVV13SecretKeyGenerator;
9    import it.unisa.dia.gas.crypto.arcanum.fe.abe.gghvv13.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 it.unisa.dia.gas.crypto.circuit.Circuit.Gate.Type.*;
20   import static it.unisa.dia.gas.crypto.circuit.DefaultCircuit.DefaultGate;
21   import static org.junit.Assert.*;
22   
23   /**
24    * @author Angelo De Caro (arcanumlib@gmail.com)
25    */
26   public class GGHVV13KEM {
27   
28       public GGHVV13KEM() {
29       }
30   
31   
32       public AsymmetricCipherKeyPair setup(int n) {
33           GGHVV13KeyPairGenerator setup = new GGHVV13KeyPairGenerator();
34           setup.init(new GGHVV13KeyPairGenerationParameters(
35                   new SecureRandom(),
36                   new GGHVV13ParametersGenerator().init(
37                           PairingFactory.getPairing("params/mm/ctl13/toy.properties"),
38                           n).generateParameters()
39           ));
40   
41           return setup.generateKeyPair();
42       }
43   
44       public byte[][] encaps(CipherParameters publicKey, String w) {
45           try {
46               KeyEncapsulationMechanism kem = new GGHVV13KEMEngine();
47               kem.init(true, new GGHVV13EncryptionParameters((GGHVV13PublicKeyParameters) publicKey, w));
48   
49               byte[] ciphertext = kem.process();
50   
51               assertNotNull(ciphertext);
52               assertNotSame(0, ciphertext.length);
53   
54               byte[] key = Arrays.copyOfRange(ciphertext, 0, kem.getKeyBlockSize());
55               byte[] ct = Arrays.copyOfRange(ciphertext, kem.getKeyBlockSize(), ciphertext.length);
56   
57               return new byte[][]{key, ct};
58           } catch (InvalidCipherTextException e) {
59               e.printStackTrace();
60               fail(e.getMessage());
61           }
62           return null;
63       }
64   
65       public CipherParameters keyGen(CipherParameters publicKey, CipherParameters masterSecretKey, Circuit circuit) {
66           GGHVV13SecretKeyGenerator keyGen = new GGHVV13SecretKeyGenerator();
67           keyGen.init(new GGHVV13SecretKeyGenerationParameters(
68                   (GGHVV13PublicKeyParameters) publicKey,
69                   (GGHVV13MasterSecretKeyParameters) masterSecretKey,
70                   circuit
71           ));
72   
73           return keyGen.generateKey();
74       }
75   
76       public byte[] decaps(CipherParameters secretKey, byte[] ciphertext) {
77           try {
78               KeyEncapsulationMechanism kem = new GGHVV13KEMEngine();
79   
80               kem.init(false, secretKey);
81               byte[] key = kem.processBlock(ciphertext);
82   
83               assertNotNull(key);
84               assertNotSame(0, key.length);
85   
86               return key;
87           } catch (InvalidCipherTextException e) {
88               e.printStackTrace();
89               fail(e.getMessage());
90           }
91   
92           return null;
93       }
94   
95   
96       public static void main(String[] args) {
97           int n = 4;
98           int q = 3;
99           Circuit circuit = new DefaultCircuit(n, q, 3, new DefaultGate[]{
100                  new DefaultGate(INPUT, 0, 1),
101                  new DefaultGate(INPUT, 1, 1),
102                  new DefaultGate(INPUT, 2, 1),
103                  new DefaultGate(INPUT, 3, 1),
104  
105                  new DefaultGate(AND, 4, 2, new int[]{0, 1}),
106                  new DefaultGate(OR, 5, 2, new int[]{2, 3}),
107  
108                  new DefaultGate(AND, 6, 3, new int[]{4, 5}),
109          });
110  
111          GGHVV13KEM kem = new GGHVV13KEM();
112  
113          // Setup
114          AsymmetricCipherKeyPair keyPair = kem.setup(n);
115  
116          // Keygen
117          CipherParameters secretKey = kem.keyGen(keyPair.getPublic(), keyPair.getPrivate(), circuit);
118  
119          // Encaps/Decaps for satisfying assignment
120          String assignment = "1101";
121          byte[][] ct = kem.encaps(keyPair.getPublic(), assignment);
122          assertEquals(true, Arrays.equals(ct[0], kem.decaps(secretKey, ct[1])));
123  
124          // Encaps/Decaps for not-satisfying assignment
125          assignment = "1001";
126          ct = kem.encaps(keyPair.getPublic(), assignment);
127          assertEquals(false, Arrays.equals(ct[0], kem.decaps(secretKey, ct[1])));
128      }
129  
130  }