อะไรจะเป็นปฏิปักษ์เวลา O(n) สำหรับโครงการประเภทนี้

สมมติว่าเรามีรหัสลับ $$E:\{0,1\}^k \text{ x } \{0,1\}^{2k} \rightarrow \{0,1\}^{2n} \quad \text{ กับ } \ รูปสี่เหลี่ยม k,n\geq128$$ K คืออัลกอริธึมการสร้างคีย์ที่ส่งคืนคีย์ k-บิตแบบสุ่ม ให้ SE = (K,Enc,Dec) เป็นโครงร่างการเข้ารหัสแบบสมมาตรด้วยอัลกอริทึมการเข้ารหัสและถอดรหัสตามที่อธิบายไว้ด้านล่างในโค้ด ข้อความอินพุตสำหรับ Enc เป็นสตริง n บิต และข้อความเข้ารหัสสำหรับ Dec เป็นสตริง 4 บิต

def Enc(K,M):
    ถ้า len(M) != n_bytes : 
        กลับไม่มี
    
    A1 = Random_string (n_bytes)
    A2 = xor_strings(ม,A1)
    ค = []
    C.ต่อท้าย(E(K,( A1 + "\x00" * n_bytes )))
    C.ต่อท้าย(E(K,( A2 + "\xFF" * n_bytes )))
    กลับเข้าร่วม (C)


def ธ.ค. (K, C):
    ถ้า len(C) != 4 * n_bytes : 
        กลับไม่มี

    C = แยก (C,2 * n_bytes)
    X1 = E_I(K,C[0]) #X1 = A1 || P1 ในรหัสเทียม
    X2 = E_I(K,C[1]) #X2 = A2 || P2 ในรหัสเทียม
    X1 = แยก(X1,n_bytes) #A1 คือ X1[0] ; P1 คือ X1[1]
    X2 = แยก(X2,n_bytes) #A2 คือ X2[0] ; P2 คือ X2[1]

    ถ้า (X1[1] != "\x00" * n_bytes) หรือ (X2[1] != "\xFF" * n_bytes) :
        กลับไม่มี
    
    M = xor_strings(X1[0],X2[0])
    คืน M

#นี่คือที่มาของรหัสฝ่ายตรงข้าม ----- ต้องกรอกสิ่งนี้
def A(เข้ารหัส):
    """
    :param enc: นี่คือ oracle ที่จัดทำโดยเกม
    กลับ: ciphertext ปลอมแปลง
    """
    ผ่าน

#ด้านล่างคือการทดสอบรหัสเพื่อดูว่าได้รับฝ่ายตรงข้ามที่ถูกต้องหรือไม่
ถ้า __name__ == '__main__':    
    กิโล = 128
    n = 128
    k_bytes = k//8
    n_bytes = n//8
 
    EE = BlockCipher(k_bytes, 2*n_bytes)
    E = EE.เข้ารหัส
    E_I = EE.ถอดรหัส

    g = GameINTCTXT(2, Enc, ธ.ค., k_bytes)
    s = CTXTSim(g, A2)

    พิมพ์ ("เมื่อ k=128, n=128:")
    พิมพ์ ("ข้อได้เปรียบของฝ่ายตรงข้าม A2 คือ ~" + str(s.compute_advantage()))

    k = 256
    n = 128
    k_bytes = k//8
    n_bytes = n//8

    EE = BlockCipher(k_bytes, 2*n_bytes)
    E = EE.เข้ารหัส
    E_I = EE.ถอดรหัส

    g = GameINTCTXT(2, Enc, ธ.ค., k_bytes)
    s = CTXTSim(g, A2)

    พิมพ์ ("เมื่อ k=256, n=128:")
    พิมพ์ ("ข้อได้เปรียบของฝ่ายตรงข้าม A2 คือ ~" + str(s.compute_advantage()))

O(n)-time Adversary ใดที่สามารถแสดงว่า SE ไม่ปลอดภัยสำหรับ INT-CTXT โดยทำการสืบค้นได้สูงสุด 2 รายการโดยมีข้อได้เปรียบ = 1 - 2^(-n)

นี่คือโครงร่างการเข้ารหัสและถอดรหัสเวอร์ชันลาเท็กซ์เพื่อความสะดวกในการอ่าน:

การเข้ารหัส:

$\ขีดเส้นใต้{ Alg E_K(M)}$

$\text{if } |M| \neq n \text{ จากนั้นส่งคืน } \perp$

$A[1] \leftarrow{$} \{0,1\}^n; A[2] \leftarrow M \oplus A[1]$

$C[1] \leftarrow E_K (A[1] || 0^n)$

$C[2] \leftarrow E_K (A[2] || 0^n)$

$\text{return } C$

ถอดรหัส:

$\ขีดเส้นใต้{ Alg D_K(M)}$

$\text{if } |C| \neq 4n \text{ แล้วคืนค่า } \perp$

$C[1]C[2] \leftarrow C$

$A[1] || P[1] \leftarrow E^{-1}_K(C[1]) ; ก[2] || P[2] \leftarrow E^{-1}_K(C[2])$

$\text{if }(P[1] \neq 0^n \text{ หรือ } P[2] \neq 1^n) \text{ แล้วคืนค่า } \perp$

$M \leftarrow A[1] \oบวก A[2]$

$\text{return } M$

นี่คือสิ่งที่ฉันได้ลองไปแล้ว:

def A(เข้ารหัส):

    ครึ่ง = n_bytes // 2
 
    C1 = เข้ารหัส (random_string (n_bytes))
    C2 = เข้ารหัส ("\x00" * n_bytes)
    C_split1 = C1[:ครึ่ง]
    C_split2 = C2[ครึ่ง:]
       
    กลับ C_split1 + C_split2;

แต่ได้ผลลัพธ์:

เมื่อ k=128, n=128:
ความได้เปรียบของศัตรู A2 คือ ~0.0
เมื่อ k=256, n=128:
ความได้เปรียบของศัตรู A2 คือ ~0.0
```