Very, very simple. I assume you can provision a per device symmetric key and a back-end database containing under 1KB per device is fine.

Devices keep a sequential nonce counter which starts at zero.

we derive a k_nonce_hint key from the main device symmetric key.

Each nonce is used to generate a nonce_hint byte string. This can be as simple as nonce_hint(nonce)=AES_enc(nonce,k_nonce_hint)[:HINTLEN] or use a hash function or something.

messages sent over the air look like nonce_hint || AEAD(M,nonce) where AEAD is some encrypt+MAC scheme.

Note:Device ID and message sequence number are sent implicitly via the nonce hint. The MAC tag provides message integrity and further validates the device ID and nonce.

At the other end

For each (device,nonce) pair there's an associated nonce hint that can be stored in a database. Assuming not too many messages get lost, you only need to keep some small number 10-100 for each device in the DB.

The application server after receiving a message queries the DB to find a matching (Device,Nonce) pair(s) and tries decrypting the message with that(or those) device key(s) and nonce(s). If it works, they update the list of nonce hints for that device in the DB.

Note that if the nonce hint is derived reversibly (EG:16 byte nonce length derived using AES encryption) nonce hints can be checked against all device keys as a fallback option. A 64 bit block cipher like XTEA would be perfect for this.

Why This Works

Symmetric crypto and databases are cheap. Adding a DB and structuring appropriately turns an O(k) problem (decrypt one message from one of k devices) into an O(1) problem (database lookup). For sufficiently large values of k this is worthwhile.

Other Nonce Patterns

If the devices have a clock inside them, you could do something time based (EG:32-bit day || 32 bit sequence counter).

If an attacker jams messages from one device, they can cause desynchronisation and subsequently sent nonce hints won't be in the database. This fixes that.

Some BLE location beacons use this to restrict use to paying customers. Beacons generate time based pseudorandom values every 15s or so and end-user devices submit these values to a commercial API. The service generates every expected value for the current time (±1 min to account for clock drift) and then does a lookup for submitted values. The cost to run such a service for a few million beacons is a fraction of a CPU core + <1KB RAM per device.

Suggested implementation

• 64 bit block cipher for nonce hints (EG:XTEA)
  • hint=block_encrypt(UINT32(0) || UINT32(counter))
• An AEAD of your choice with 64 bit tag

This has an overhead of 16 bytes with message sequence numbers and device IDs sent implicitly.

Fallback decryption of messages is possible by trying all device keys although an attacker could DOS the fallback path by sending lots of garbage messages.

Message validity for random attacker supplied garbage requires:

• a well formed nonce hint
  • bits of security:32 - log2(device_count)
  • unless you make >4 billion of these things you won't have to cut into your MAC security margin and this adds to that
• a well formed MAC tag
  • bits of security:(whatever you decide on)
  • I suggest 64 bits
• total security margin is MAC_bits + 32 - log2(device_count)
  • attacker has 2^-margin chance of forging a message by guessing randomly
  • attacker has 2^-MAC_bits chance of modifying legitimate message payload to forge a new valid message

Note that in the case devices sending 1M messages over their lifetime, that's 12MB of DB space per device, plausibly a 12TB database for 1M devices which isn't that big allows decrypting all possible messages with just a DB lookup. Optimizations are possible of course.

Comparing to Asymmetric options

Cheapest secure option that meets your requirements would be unauthenticated ECDH encryption + symmetric MAC using per device keys. This meets your security requirements.

• ECDH_point,ECDH_secret=Curve25519_ECDH_public()
• ciphertext = encrypt(device_ID || message,k=ECDH_secret)
• tag = HMAC(ciphertext , device_MAC_key)[:MAC_LENGTH]
• send(ECDH_point || ciphertext || tag)

On the backend:

• ECDH_point,ciphertext,tag=split_message(recv())#get a message
• ECDH_secret=Curve25519_ECDH_private(ECDH_point,EC_private_key)
• plaintext=decrypt(device_ID || message,k=ECDH_secret)
• device_MAC_key=DB_lookup_key(plaintext[:DEVICE_ID_LEN])
• correct_tag=HMAC(ciphertext , device_MAC_key)[:MAC_LENGTH]
• if(tag!=correct_tag){return invalid_message}
• return plaintext

Overhead is

• 32 B (ECDH point)
• 4 B (device ID)
• 8 B (MAC)

That's a lot more than the symmetric options suggested above and you don't get an implicit sequence number. Also EC point multiplication is SLOOOW.